深入Lua - 字元串

來自專欄源碼和原理分析

字元串結構定義

Lua中字元串結構體定義:

/* ** Common Header for all collectable objects (in macro form, to be ** included in other objects) */ #define CommonHeader GCObject *next; lu_byte tt; lu_byte marked ? /* ** Header for string value; string bytes follow the end of this structure ** (aligned according to UTString; see next). */ typedef struct TString { CommonHeader; lu_byte extra; /* reserved words for short strings; "has hash" for longs */ lu_byte shrlen; /* length for short strings */ unsigned int hash; union { size_t lnglen; /* length for long strings */ struct TString *hnext; /* linked list for hash table */ } u; } TString; ? ? /* ** Ensures that address after this type is always fully aligned. */ typedef union UTString { L_Umaxalign dummy; /* ensures maximum alignment for strings */ TString tsv; } UTString;

字元串緩存

在創建字元串時，首先會從global_State的strcache緩存中查找看是否存在:

// #define STRCACHE_N 53 // #define STRCACHE_M 2 ? TString *luaS_new (lua_State *L, const char *str) { unsigned int i = point2uint(str) % STRCACHE_N; /* hash */ int j; TString **p = G(L)->strcache[i]; for (j = 0; j < STRCACHE_M; j++) { // strcmp == 0，兩個str相同 // getstr --> TString轉string if (strcmp(str, getstr(p[j])) == 0) return p[j]; // 找到相同str } for (j = STRCACHE_M - 1; j > 0; j--) p[j] = p[j - 1]; // 移動元素 // 新元素會插入到list最前端 p[0] = luaS_newlstr(L, str, strlen(str)); return p[0]; }

創建一個字元串的時候，首先會在strcache中查找，第7行根據str計算出該str在strcache的索引位置，在該strcache位置上又有一個大小為2( STRCACHE_M )的TString數組，若在這個數組中找到相同的字元串，則返回cache中字元串對應的TString；若未找到，會將p[0]位置的TString挪到p[1]位置，而p[0]位置存放luaS_newlstr新創建的TString。

創建字元串

// #define LUAI_MAXSHORTLEN 40 ? /* ** new string (with explicit length) */ TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { if (l <= LUAI_MAXSHORTLEN) /* short string? */ return internshrstr(L, str, l); else { TString *ts; if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char)) luaM_toobig(L); ts = luaS_createlngstrobj(L, l); memcpy(getstr(ts), str, l * sizeof(char)); return ts; } }

新建一個TString時，會判斷字元串長度是否大於40( LUAI_MAXSHORTLEN )，對於長度大於40的str，會直接創建TString並返回，而對於長度40以內的short string，會從global_State中的一個stringtable(strt)查找並記錄:

/* ** checks whether short string exists and reuses it or creates a new one */ static TString *internshrstr (lua_State *L, const char *str, size_t l) { TString *ts; global_State *g = G(L); unsigned int h = luaS_hash(str, l, g->seed); TString **list = &g->strt.hash[lmod(h, g->strt.size)]; lua_assert(str != NULL); /* otherwise memcmp/memcpy are undefined */ for (ts = *list; ts != NULL; ts = ts->u.hnext) { if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { /* found! */ if (isdead(g, ts)) /* dead (but not collected yet)? */ changewhite(ts); /* resurrect it */ return ts; } } // list中如果沒找到 // resize 擴容 if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) { luaS_resize(L, g->strt.size * 2); list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ } // 不需要擴容的情況 ts = createstrobj(L, l, LUA_TSHRSTR, h); memcpy(getstr(ts), str, l * sizeof(char)); ts->shrlen = cast_byte(l); ts->u.hnext = *list; *list = ts; g->strt.nuse++; return ts; }

strt的數據結構類似於HashMap，它的初始化的數組長度為128，首先根據str計算得到的hash值(0~127),找到數組對應的下標索引，取出對應下標的list鏈表，10 ~ 18行是對該list進行遍歷，若找到則直接返回；如未找到，則繼續向下走。第21行， 如果 nuse(當前strt中TSring總數) 超過容量size(初始128)值，就會進行luaS_resize擴容操作(後續細講)，strt的容量將擴為原來的2倍。如果不需要擴容，第26行開始，會創建一個新的TString，並將其插入到當前list的頭部。

擴容

/* ** resizes the string table */ void luaS_resize (lua_State *L, int newsize) { int i; stringtable *tb = &G(L)->strt; if (newsize > tb->size) { /* grow table if needed */ luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; } for (i = 0; i < tb->size; i++) { /* rehash */ TString *p = tb->hash[i]; tb->hash[i] = NULL; while (p) { // 遍歷每一個節點 TString *hnext = p->u.hnext; unsigned int h = lmod(p->hash, newsize); p->u.hnext = tb->hash[h]; tb->hash[h] = p; p = hnext; } } if (newsize < tb->size) { /* shrink table if needed */ /* vanishing slice should be empty */ lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); } tb->size = newsize; }

第7行，如果需要擴容，則調用luaM_reallocvector將 tb->hash 數組擴大到newsize (2倍)，12行~22行對每一個數組位置list鏈表中每一個TString節點的元素重新計算hash值，並將其插入到對應數組中的鏈表頭部位置處。