• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

概述

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

lua会把所有字符串统一在全局的stringtable管理。

typedef struct stringtable {
  TString **hash;
  int nuse;  /* number of elements */
  int size;
} 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] = '\0';  /* 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) 包含'\0'字符串结束符。

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))))
  • g->frealloc 内存分配器,在创建状态机的时候可以由用户自己指定。
  • 很多内存管理器依据目前内存大小优化内存分配,故传入目前内存大小参数。
  • 尝试分配内存,若分配失败则进行GC后再次尝试。
  • GCdebt GC相关标记。

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
lua支持中文变量名发布时间:2022-07-22
下一篇:
openresty的lua_package_path发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap