Lua5.4源码剖析：二. 详解String数据结构及操作算法

技术分享 4年前 (2022-07-02) 0 999+

关注

概述

lua字符串通过操作算法和内存管理，有以下优点：

节省内存。
字符串比较效率高。（比较哈希值）

问题：

相同的字符串共享同一份内存么？
相同的长字符串一定不共享同一份内存么？
lua字符串如何管理内存？

数据结构

lua字符串TString

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;   char contents[1]; } TString;

lu_byte extra的reserved words语义是否是保留字。（保留字：local，if, ...）
char contents[1] 是存放字符串内存数据的指针。
- 与char*相比，使用char[]在struct后面一次分配内存。

全局字符串表stringtable

typedef struct stringtable {   TString **hash;   int nuse;  /* number of elements */   int size; } stringtable;

lua会把所有字符串统一在全局的stringtable结构中管理。
hash 使用散列表存放string。

操作算法

luaS_new 创建字符串对外接口

/* ** Create or reuse a zero-terminated string, first checking in the ** cache (using the string address as a key). The cache can contain ** only zero-terminated strings, so it is safe to use 'strcmp' to ** check hits. */ 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++) {     if (strcmp(str, getstr(p[j])) == 0)  /* hit? */       return p[j];  /* that is it */   }   /* normal route */   for (j = STRCACHE_M - 1; j > 0; j--)     p[j] = p[j - 1];  /* move out last element */   /* new element is first in the list */   p[0] = luaS_newlstr(L, str, strlen(str));   return p[0]; }

先在缓存中查找，命中直接返回结果，否则创建新对象并写入缓存。
一些文章说lua字串是全局表里的唯一对象，情况如下：
- lua5.1:不管长短串，都写入全局表和查重。
- lua5.2:只有短串写入全局表和查重。
- lua5.3&lua5.4:在lua5.2版本的基础上，先查缓存。

luaS_newlstr 创建字符串

/* ** 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 (unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char)))       luaM_toobig(L);     ts = luaS_createlngstrobj(L, l);     memcpy(getstr(ts), str, l * sizeof(char));     return ts;   } }

长串or短串类型测试和处理。
长串长度边界测试。

internshrstr 创建短字符串

/* ** 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);   stringtable *tb = &g->strt;   unsigned int h = luaS_hash(str, l, g->seed, 1);   TString **list = &tb->hash[lmod(h, tb->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;     }   }   /* else must create a new string */   if (tb->nuse >= tb->size) {  /* need to grow string table? */     growstrtab(L, tb);     list = &tb->hash[lmod(h, tb->size)];  /* rehash with new size */   }   ts = createstrobj(L, l, LUA_VSHRSTR, h);   memcpy(getstr(ts), str, l * sizeof(char));   ts->shrlen = cast_byte(l);   ts->u.hnext = *list;   *list = ts;   tb->nuse++;   return ts; }

计算字符串的哈希值，找到对应的桶，在桶查找相同的串，命中进行垃圾收集测试并返回，否则创建新的串放入桶中。
- 垃圾收集测试命中则清除垃圾收集标记。
哈希表装填因子测试，命中哈希表生长。

createstrobj 创建字符串对象

/* ** creates a new string object */ static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {   TString *ts;   GCObject *o;   size_t totalsize;  /* total size of TString object */   totalsize = sizelstring(l);   o = luaC_newobj(L, tag, totalsize);   ts = gco2ts(o);   ts->hash = h;   ts->extra = 0;   getstr(ts)[l] = '';  /* ending 0 */   return ts; }

动态计算内存大小，一次申请内存并填充字符串。（一次申请内存TString的char contents[1]特性）。

sizelstring 动态计算TString结构体内存

#define offsetof(s,m) ((size_t)&(((s*)0)->m)) #define sizelstring(l)  (offsetof(TString, contents) + ((l) + 1) * sizeof(char))

offsetof 语义为成员变量m相对于结构体首地址的内存偏移。
sizelstring(l) 动态计算结构体TString内存大小 = contents内存偏移 + （size + 1）* sizeof(char))。
- （size + 1）包含''字符串结束符。

growstrtab 字符串哈希表生长

static void growstrtab (lua_State *L, stringtable *tb) {   if (unlikely(tb->nuse == MAX_INT)) {  /* too many strings? */     luaC_fullgc(L, 1);  /* try to free some... */     if (tb->nuse == MAX_INT)  /* still too many? */       luaM_error(L);  /* cannot even create a message... */   }   if (tb->size <= MAXSTRTB / 2)  /* can grow string table? */     luaS_resize(L, tb->size * 2); }

一系列边界测试，通过则生长为原来的2倍。

luaS_resize 重置字符串哈希表的大小

/* ** Resize the string table. If allocation fails, keep the current size. ** (This can degrade performance, but any non-zero size should work ** correctly.) */ void luaS_resize (lua_State *L, int nsize) {   stringtable *tb = &G(L)->strt;   int osize = tb->size;   TString **newvect;   if (nsize < osize)  /* shrinking table? */     tablerehash(tb->hash, osize, nsize);  /* depopulate shrinking part */   newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*);   if (unlikely(newvect == NULL)) {  /* reallocation failed? */     if (nsize < osize)  /* was it shrinking table? */       tablerehash(tb->hash, nsize, osize);  /* restore to original size */     /* leave table as it was */   }   else {  /* allocation succeeded */     tb->hash = newvect;     tb->size = nsize;     if (nsize > osize)       tablerehash(newvect, osize, nsize);  /* rehash for new size */   } }

若nsize < osize 先把原来的元素重新散列到nsize长度的桶里，再内存收紧。
若nsize > osize 先内存扩容，若扩容成功把原来的元素散列到桶里，否则保持不变。

tablerehash 重新计算哈希

static void tablerehash (TString **vect, int osize, int nsize) {   int i;   for (i = osize; i < nsize; i++)  /* clear new elements */     vect[i] = NULL;   for (i = 0; i < osize; i++) {  /* rehash old part of the array */     TString *p = vect[i];     vect[i] = NULL;     while (p) {  /* for each string in the list */       TString *hnext = p->u.hnext;  /* save next */       unsigned int h = lmod(p->hash, nsize);  /* new position */       p->u.hnext = vect[h];  /* chain it into array */       vect[h] = p;       p = hnext;     }   } }

重新散列元素
此算法某些元素可能会重复被计算。
- 如元素E本来放在1号桶里，哈希取模后放到了2号桶里。遍历扫到2号桶，E又计算一遍位置还是放在2号桶。

luaS_hash 字符串哈希算法

unsigned int luaS_hash (const char *str, size_t l, unsigned int seed,                         size_t step) {   unsigned int h = seed ^ cast_uint(l);   for (; l >= step; l -= step)     h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));   return h; }

类似线性同余法的随机数生成算法。

lmod

/* ** 'module' operation for hashing (size is always a power of 2) */ #define lmod(s,size)  	(check_exp((size&(size-1))==0, (cast_int((s) & ((size)-1)))))

取余，size必须是2的n次幂，此算法才成立。

luaM_reallocvector 重新分配顺序表内存

#define firsttry(g,block,os,ns)    ((*g->frealloc)(g->ud, block, os, ns))  /* ** Generic allocation routine. ** If allocation fails while shrinking a block, do not try again; the ** GC shrinks some blocks and it is not reentrant. */ void *luaM_realloc_ (lua_State *L, void *block, size_t osize, size_t nsize) {   void *newblock;   global_State *g = G(L);   lua_assert((osize == 0) == (block == NULL));   newblock = firsttry(g, block, osize, nsize);   if (unlikely(newblock == NULL && nsize > 0)) {     if (nsize > osize)  /* not shrinking a block? */       newblock = tryagain(L, block, osize, nsize);     if (newblock == NULL)  /* still no memory? */       return NULL;  /* do not update 'GCdebt' */   }   lua_assert((nsize == 0) == (newblock == NULL));   g->GCdebt = (g->GCdebt + nsize) - osize;   return newblock; }  #define luaM_reallocvector(L, v,oldn,n,t)     (cast(t *, luaM_realloc_(L, v, cast_sizet(oldn) * sizeof(t),                                    cast_sizet(n) * sizeof(t))))