快捷導(dǎo)航

Lua源碼中字符串類型的實(shí)現(xiàn)

更新時(shí)間：2015年04月10日 10:24:51 投稿：hebedich

與其他主流腳本語(yǔ)言不同的是，Lua在實(shí)現(xiàn)字符串類型有兩方面不同。第一，所有的字符串在Lua中都只儲(chǔ)存一份拷貝。第二，所有的字符串變量，只保存字符串引用，而不保存它的buffer。我們來(lái)具體看看lua源碼中如何實(shí)現(xiàn)字符串類型的吧

概述

Lua完全采用8位編碼，Lua字符串中的字符可以具有任何數(shù)值編碼，包括數(shù)值0。也就是說(shuō)，可以將任意二進(jìn)制數(shù)據(jù)存儲(chǔ)到一個(gè)字符串中。Lua的字符串是不可變的值（immutable values）。如果修改，實(shí)質(zhì)上是新建一個(gè)字符串。根據(jù)上文《Lua中數(shù)據(jù)類型的源碼實(shí)現(xiàn)》中知道，在Lua中，字符串是自動(dòng)內(nèi)存管理機(jī)制所管理的對(duì)象，并且由聯(lián)合體TString來(lái)實(shí)現(xiàn)存儲(chǔ)字符串值的。下面將通過(guò)Lua 5.2.1的源碼來(lái)看字符串的實(shí)現(xiàn)以及總結(jié)了在Lua中使用字符串的注意事項(xiàng)。

源碼實(shí)現(xiàn)

首先來(lái)看字符串對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)TString，其源碼如下（lobject.h）：

410 /* 
411 ** Header for string value; string bytes follow the end of this structure 
412 */ 
413 typedef union TString { 
414  L_Umaxalign dummy; /* ensures maximum alignment for strings */ 
415  struct { 
416   CommonHeader; 
417   lu_byte extra; /* reserved words for short strings; "has hash" for longs */ 
418   unsigned int hash; 
419   size_t len; /* number of characters in string */ 
420  } tsv; 
421 } TString;

對(duì)這個(gè)聯(lián)合體定義，有幾點(diǎn)值得說(shuō)明：

I、聯(lián)合體TString中成員L_Umaxalign dummy是用來(lái)保證與最大長(zhǎng)度的C類型進(jìn)行對(duì)齊，其定義如下（llimits.h）：

48 /* type to ensure maximum alignment */ 
49 #if !defined(LUAI_USER_ALIGNMENT_T) 
50 #define LUAI_USER_ALIGNMENT_T  union { double u; void *s; long l; } 
51 #endif 
52    
53 typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;

在其他可會(huì)回收的對(duì)象（比如table）的實(shí)現(xiàn)中，也可看到這個(gè)聯(lián)合體成員，這樣做的目的是通過(guò)內(nèi)存對(duì)齊，加快CPU訪問(wèn)內(nèi)存的速度。

II、聯(lián)合體中成員tsv才是真正用來(lái)實(shí)現(xiàn)字符串的。其中成員CommonHeader用于GC，它會(huì)以宏的形式在所有的可回收對(duì)象中定義，代碼如下（lobject.h）：

74 /* 
75 ** Common Header for all collectable objects (in macro form, to be 
76 ** included in other objects) 
77 */ 
78 #define CommonHeader  GCObject *next; lu_byte tt; lu_byte marked

這個(gè)宏對(duì)應(yīng)的結(jié)構(gòu)體形式如下（lobject.h）：

81 /* 
82 ** Common header in struct form 
83 */ 
84 typedef struct GCheader { 
85  CommonHeader; 
86 } GCheader;

結(jié)構(gòu)體GCheader在通用的可回收對(duì)象union GCObject的定義中有用到。

III、lu_byte extra對(duì)于短字符串，用來(lái)記錄這個(gè)字符串是否為保留字，對(duì)于長(zhǎng)字符串，可以用于惰性求Hash值；unsigned int hash成員是字符串對(duì)應(yīng)的Hash值（在后面會(huì)具體講Lua是怎么計(jì)算字符串的Hash值的）；size_t len用來(lái)表示字符串的長(zhǎng)度。

IV、上面的結(jié)構(gòu)體只是描述了一個(gè)字符串的結(jié)構(gòu)，真正的字符串?dāng)?shù)據(jù)保存是緊隨在結(jié)構(gòu)體后面保存。

在Lua5.2.1之前，不區(qū)分字符串長(zhǎng)和短的字符串，所有的字符串保存在一個(gè)全局的Hash表中，對(duì)于Lua虛擬機(jī)來(lái)說(shuō)，相同的字符串只有一份數(shù)據(jù)，從Lua5.2.1開始，只是把短的字符串字符串（當(dāng)前定義是長(zhǎng)度小于等于40）放在全局Hash表中，而長(zhǎng)字符串都是獨(dú)立生成，同時(shí)在計(jì)算Hash值時(shí)，引入一個(gè)隨機(jī)種子，這樣做的目的防止Hash Dos——攻擊者構(gòu)造出非常多相同Hash值的不同字符串，從而降低Lua從外部壓入字符串進(jìn)入全局的字符串Hash表的效率。下面是Lua5.2.1中，生成一個(gè)新字符串的步驟，其相應(yīng)的代碼都在lstring.c中：

（1）若字符串長(zhǎng)度大于LUAI_MAXSHORTLEN（默認(rèn)值是40），則是長(zhǎng)字符串，直接調(diào)用創(chuàng)建字符串接口的函數(shù)createstrobj（當(dāng)然字符串的長(zhǎng)度需要能保存在成員size_t len中，否則直接返回），代碼如下（lstring.c）：

 95 /* 
 96 ** creates a new string object 
 97 */                                                  
 98 static TString *createstrobj (lua_State *L, const char *str, size_t l,                
 99                int tag, unsigned int h, GCObject **list) {              
100  TString *ts;                                            
101  size_t totalsize; /* total size of TString object */                       
102  totalsize = sizeof(TString) + ((l + 1) * sizeof(char));                      
103  ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 
104  ts->tsv.len = l; 
105  ts->tsv.hash = h; 
106  ts->tsv.extra = 0;                                         
107  memcpy(ts+1, str, l*sizeof(char)); 
108  ((char *)(ts+1))[l] = '\0'; /* ending 0 */                            
109  return ts; 
110 }

可以看到把傳入的字符串具體內(nèi)存放在緊隨結(jié)構(gòu)體TString內(nèi)存后面，并且注意108行，字符串以”\0”結(jié)束與C語(yǔ)言字符串兼容的。

（2）若字符串是短字符串，首先計(jì)算字符串的Hash值，找到對(duì)應(yīng)的鏈表（短字符串的全局Hash表，使用的是鏈接法的方法，即把所有沖突的元素放在同一個(gè)鏈表中），查找當(dāng)前要?jiǎng)?chuàng)建的字符串是否已經(jīng)在Hash表中，若已經(jīng)存在，則直接返回這個(gè)字符串。否則會(huì)調(diào)用函數(shù)newshrstr，而函數(shù)newshrstr會(huì)調(diào)用上面的createstrobj函數(shù)創(chuàng)建新字符串，并把新創(chuàng)建的字符串放到Hash表中，代碼如下（lstring.c））：

130 /* 
131 ** checks whether short string exists and reuses it or creates a new one 
132 */ 
133 static TString *internshrstr (lua_State *L, const char *str, size_t l) { 
134  GCObject *o; 
135  global_State *g = G(L); 
136  unsigned int h = luaS_hash(str, l, g->seed); 
137  for (o = g->strt.hash[lmod(h, g->strt.size)]; 
138    o != NULL; 
139    o = gch(o)->next) { 
140   TString *ts = rawgco2ts(o); 
141   if (h == ts->tsv.hash && 
142     ts->tsv.len == l && 
143     (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 
144    if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ 
145     changewhite(o); /* resurrect it */ 
146    return ts; 
147   } 
148  } 
149  return newshrstr(L, str, l, h); /* not found; create a new string */ 
150 }

全局的字符串Hash表是保存在虛擬機(jī)全局狀態(tài)成員strt中的（lstate.h）：

119  stringtable strt; /* hash table for strings */

而類型stringtable是一個(gè)結(jié)構(gòu)體，其定義如下（lstate.h）：

59 typedef struct stringtable {                                     
60  GCObject **hash; 
61  lu_int32 nuse; /* number of elements */ 
62  int size; 
63 } stringtable;

其中成員GCObject **hash是一個(gè)指針數(shù)組，數(shù)組中每個(gè)成員實(shí)質(zhì)指向TString（注意TString中包括宏CommonHeader，該宏中的next成員可以構(gòu)造出Hash表中開散的鏈表）；nuse是數(shù)組hash中已經(jīng)被使用的元素個(gè)數(shù)；size是當(dāng)前數(shù)組hash的大小。

在函數(shù)newshrstr插入新的字符串前，都會(huì)判斷nuse值是否大于size，若大于，表明Hash表大小不夠需要擴(kuò)充，則把Hash表的大小擴(kuò)充到原來(lái)的2倍，對(duì)應(yīng)的代碼如下（lstring.c）:

121  if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)                 
122   luaS_resize(L, tb->size*2); /* too crowded */

在gc的時(shí)候，會(huì)判斷nuse是否比size/2還?。ㄔ贚ua 5.1中是把nuse與size/4比較），如果是的話就重新resize這個(gè)stringtable的大小為原來(lái)的一半。對(duì)應(yīng)的代碼如下（lgc.c）：

783   int hs = g->strt.size / 2; /* half the size of the string table */               
784   if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half? */            
785    luaS_resize(L, hs); /* halve its size */

對(duì)于字符串比較，首先比較類型，若是不同類型字符串，則肯定不相同，然后區(qū)分短字符串和長(zhǎng)字符串，對(duì)于短字符串，若兩者指針值相等，則相同，否則不相同；對(duì)應(yīng)長(zhǎng)字符串，則首先比較指針值，若不同，則比較長(zhǎng)度值和內(nèi)容逐字符比較。

總結(jié)

（1）Lua中的保留字和元方法名都是做為短字符串的，他們?cè)谔摂M機(jī)啟動(dòng)的時(shí)候就已經(jīng)放入到全局短的字符串Hash表，并且是不回收的。

（2）查找字符是比較高效的，但是修改或插入字符串都是比較低效的，這里面除了計(jì)算外，至少要把外面的字符串拷貝到虛擬機(jī)中。

（3）對(duì)應(yīng)長(zhǎng)字符串的Hash值，Lua是不會(huì)考察每個(gè)字符的，因而能避免快速計(jì)算長(zhǎng)字符串的散列值，其相應(yīng)的代碼如下（lstring.c）：

51 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {               
52  unsigned int h = seed ^ l;                                     
53  size_t l1;                                             
54  size_t step = (l >> LUAI_HASHLIMIT) + 1;                              
55  for (l1 = l; l1 >= step; l1 -= step)                                
56   h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1]));                       
57  return h;                                             
58 }  
21 /*                                                 
22 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to                 
23 ** compute its hash                                         
24 */                                                  
25 #if !defined(LUAI_HASHLIMIT)                                     
26 #define LUAI_HASHLIMIT   5                                    
27 #endif

（4）當(dāng)有多個(gè)字符串連接時(shí)，不應(yīng)該直接用字符串連接運(yùn)算符”..”，而是用table.concat操作或者是string.format來(lái)加快字符串連接的操作。

（5）Lua中字符串Hash算法用的是JSHash，關(guān)于字符串的各種Hash函數(shù)，網(wǎng)絡(luò)有篇文章對(duì)它進(jìn)行了總結(jié)：https://www.byvoid.com/blog/string-hash-compare

以上所述誰(shuí)就是本文的全部?jī)?nèi)容了，希望能對(duì)大家學(xué)習(xí)lua有所幫助。

您可能感興趣的文章: