Lua string(字符串)（源码解析）

string类型作为Lua中几种基本数据类型之一，使用频率那是相当的高，所以了解Lua中字符串的实现原理，能够让我们更合理、更高效的使用Lua中的字符串。避免一些误区，提高程序效率。这里介绍的所有代码都基于Lua5.1版本。

一、Lua中string的数据结构

一般来说，要表示一个字符串一般都需要两个关键数据：
（1）字符串的长度
（2）指向字符串首地址的指针。
Lua中的字符串结构设计也是围绕这两个关键数据的。具体我们来看一下Lua中字符串的数据结构：

//（lobject.h）
/*
** String headers for string table
*/
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

接下来我们来理解一下这个共同体(union)中每个字段的含义：
dummy ：表示字符串最大的对齐长度。L_Umaxalign也是一个共同体，具体结构如下：

//(llimits.h)
/* type to ensure maximum alignment */
typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;

//(luaconf.h)
/*
@@ LUAI_USER_ALIGNMENT_T is a type that requires maximum alignment.
** CHANGE it if your system requires alignments larger than double. (For
** instance, if your system supports long doubles and they must be
** aligned in 16-byte boundaries, then you should add long double in the
** union.) Probably you do not need to change this.
*/
#define LUAI_USER_ALIGNMENT_T   union { double u; void *s; long l; }

上面的注释解释的非常清楚了。可以根据系统需要在这个修改最大的对齐长度。
CommonHeader：表示string是需要加入到Lua的GC管理中的。CommonHeader是个宏定义，具体的介绍可以看之前的Lua数据类型（源码解析）
reserved：这个变量用于标记这个字符串是不是Lua虚拟机中的保留字符串。如果这个值不为0，那么将不会在GC阶段被回收，而是一直保留在虚拟机中。只有Lua语言中的关键字才会是保留字符串（eg.local self function）
hash：该字符串的散列值。
len：字符串的长度

二、Lua中string类型的实现

在Lua中，每个字符串数据都只有一份。每当创建一个新的字符串的时候，首先会检查当前是否已经存在这个字符串，如果存在就直接复用，让字符串变量保存这个字符串的引用，不存在则创建一个新的字符串。例如：

a = "1"
a = a.."2"
b = "1"

在Lua中的表示如下图：

Lua中字符串只有一份.png

那么这样的话，在Lua虚拟机中必然有一个全局的地方存放当前系统中的所有字符串。这个地方就是global_State(lstate.h)的strt字段。strt是个stringtable结构体类型，我们看一下stringtable的定义：

//(lstate.h)
typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse;  /* number of elements */
  int size;
} stringtable;

hash ：一个GCObject的二维指针，可以看作二维数组，根据字符串的离散值存放这我们创建的字符串。
nuse ：当前存放的数量
size ： hash至的大小
通过上面可以总结这么几点：
（1）Lua中通过字符串的hash值来对字符串进行查找，对比。
（2）Lua中的字符串变量存放的是字符串的引用，而不是字符串本身。
（3）同一个字符串在Lua虚拟机中只有一份。
（4）Lua虚拟机中global_State的strt字段存放着当前系统中的所有字符串

下面通过具体的代码分析来看看Lua中的具体实现：
创建字符串

//(lstring.h)
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  //默认的hash值
  unsigned int h = cast(unsigned int, l);  /* seed */
  //计算hash值时的步长，如果字符串太长的话，没有必要使用所有的字符来计算hash值，
  //只需要按照步长，取其中的一些字符来计算hash值
  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
  size_t l1;
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    //计算字符串的hash值算法
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  //通过计算出来的hash值，遍历对应的CGObject链表
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    //GCObject类型转换为TString类型
    TString *ts = rawgco2ts(o);
    //比较两个字符串是否相等
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      //可能这个字符串正处于将要被CG回收的阶段，重新设置GC状态
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  //如果该字符串还没有保存在当前的系统中，那么创建一个。
  return newlstr(L, str, l, h);  /* not found */
}

//(lstring.h)
static TString *newlstr (lua_State *L, const char *str, size_t l,unsigned int h) {
  TString *ts;
  stringtable *tb;
  //判断字符串是不是超过了最大范围
  if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
    luaM_toobig(L);
  //分配内存
  ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
  //给TString赋值
  ts->tsv.len = l;
  ts->tsv.hash = h;
  //新创建的GC都标志为白色
  ts->tsv.marked = luaC_white(G(L));
  ts->tsv.tt = LUA_TSTRING;
  //表示不是Lua中保留字符串
  ts->tsv.reserved = 0;
  //拷贝字符
  memcpy(ts+1, str, l*sizeof(char));
  //在末尾加上'\0'标志
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  //将新创建的字符串加入到离散表中
  tb = &G(L)->strt;
  h = lmod(h, tb->size);
  ts->tsv.next = tb->hash[h];  /* chain new entry */
  tb->hash[h] = obj2gco(ts);
  tb->nuse++;
  //判断是否需要扩容
  if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */
  return ts;
}

重新分配字符串的离散数据

//(lstring.h)
void luaS_resize (lua_State *L, int newsize) {
  //新的离散列表指针
  GCObject **newhash;
  stringtable *tb;
  int i;
  //判断是否在CG回收阶段
  if (G(L)->gcstate == GCSsweepstring)
    return;  /* cannot resize during GC traverse */
  //给新的离散列表分配内存
  newhash = luaM_newvector(L, newsize, GCObject *);
  //获取全局的stringTable
  tb = &G(L)->strt;
  //新的离散列表初始化
  for (i=0; i<newsize; i++) newhash[i] = NULL;
  /* rehash */
  //遍历整个离散列表，重新计算hash索引
  for (i=0; i<tb->size; i++) {
    //同一个hash值链表的首个元素
    GCObject *p = tb->hash[i];
    //遍历整个链表的元素
    while (p) {  /* for each node in the list */
      //保存一下下一个元素，防止操作next指针导致链表断开
      GCObject *next = p->gch.next;  /* save next */
      //将GCObject转换为TString，获取之前的hash值
      unsigned int h = gco2ts(p)->hash;
      //用之前的hash值在新的size中取余，得到新的hash值。
      int h1 = lmod(h, newsize);  /* new position */
      lua_assert(cast_int(h%newsize) == lmod(h, newsize));
      //下面两步就是链表的插入操作，将p加到新的hash链表中
      p->gch.next = newhash[h1];  /* chain it */
      newhash[h1] = p;
      //让指针指向下一个，继续循环
      p = next;
    }
  }
  //释放之前hash列表之内存
  luaM_freearray(L, tb->hash, tb->size, TString *);
  //更新新的hash列表的大小
  tb->size = newsize;
  //更新新的hash列表的引用
  tb->hash = newhash;
}

luaS_resize 操作都是Lua自身触发，无需我们手动维护。主要有3个地方调用：
（1）f_luaopen(lstate.c)在lua虚拟机初始化的时候会给size设置一个默认的大小MINSTRTABSIZE = 32

static void f_luaopen (lua_State *L, void *ud) {
  global_State *g = G(L);
  UNUSED(ud);
  stack_init(L, L);  /* init stack */
  sethvalue(L, gt(L), luaH_new(L, 0, 2));  /* table of globals */
  sethvalue(L, registry(L), luaH_new(L, 0, 2));  /* registry */
  luaS_resize(L, MINSTRTABSIZE);  /* initial size of string table */
  luaT_init(L);
  luaX_init(L);
  luaS_fix(luaS_newliteral(L, MEMERRMSG));
  g->GCthreshold = 4*g->totalbytes;
}

（2）newlstr(lstring.c)创建新的字符串时，判断size是不是不够，如果够则扩容1倍。

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

（3）checkSizes(lgc.c)在CG回收阶段会判断元素的个数是不是比size的1/4还小，如果是则将size缩小为原来的1/2.

 /* check size of string hash */
  if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
      g->strt.size > MINSTRTABSIZE*2)
    luaS_resize(L, g->strt.size/2);  /* table is too big */

保留字符串初始化

//(llex.h)
/*
* WARNING: if you change the order of this enumeration,
* grep "ORDER RESERVED"
*/
//保留字的枚举
enum RESERVED {
  /* terminal symbols denoted by reserved words */
  TK_AND = FIRST_RESERVED, TK_BREAK,
  TK_DO, TK_ELSE, TK_ELSEIF, TK_END, TK_FALSE, TK_FOR, TK_FUNCTION,
  TK_IF, TK_IN, TK_LOCAL, TK_NIL, TK_NOT, TK_OR, TK_REPEAT,
  TK_RETURN, TK_THEN, TK_TRUE, TK_UNTIL, TK_WHILE,
  /* other terminal symbols */
  TK_CONCAT, TK_DOTS, TK_EQ, TK_GE, TK_LE, TK_NE, TK_NUMBER,
  TK_NAME, TK_STRING, TK_EOS
};

//(llex.c)
/* ORDER RESERVED */
//枚举对应的保留字字符串
const char *const luaX_tokens [] = {
    "and", "break", "do", "else", "elseif",
    "end", "false", "for", "function", "if",
    "in", "local", "nil", "not", "or", "repeat",
    "return", "then", "true", "until", "while",
    "..", "...", "==", ">=", "<=", "~=",
    "<number>", "<name>", "<string>", "<eof>",
    NULL
};

/* number of reserved words */
#define NUM_RESERVED    (cast(int, TK_WHILE-FIRST_RESERVED+1))

void luaX_init (lua_State *L) {
  int i;
  for (i=0; i<NUM_RESERVED; i++) {
    TString *ts = luaS_new(L, luaX_tokens[i]);
    //标记字符串的GC回收状态
    luaS_fix(ts);  /* reserved words are never collected */
    lua_assert(strlen(luaX_tokens[i])+1 <= TOKEN_LEN);
    //标记该字符串为保留字字符串
    ts->tsv.reserved = cast_byte(i+1);  /* reserved word */
  }
}

luaX_init 是在虚拟机初始化的时候调用的。f_luaopen(lstate.c)在分配了stringTable的内存后调用。

三、分析与总结

在Lua字符串这一块最主要的是要理解下面几个东西：
（1）Lua字符串是会被GC的
（2）每个字符串在Lua内存中只存在一份
（3）Lua通过一个全局的散列桶(stringTable)管理所有的字符串
下面一张图帮助理解一下Lua字符串存储的结构：

strt结构示意图.png

在我们平时的使用中尽量避免循环拼接字符串，因为没拼接一次就是重新创建一个新的字符串。

a = os.clock()
local s = ""
for i = 1, 100000 do
    s = s.."a"
end
b = os.clock()
print(b-a)
--2.1309999999939s

a = os.clock()
local s = ""
local t = {}
for i = 1, 100000 do
    t[#t+1] = "a"
end
s = table.concat(t,"")
b = os.clock()
print(b-a)
--0.01600000000326s

我们可以看到这差距非常的夸张。第一种方法需要创建大量的字符串，而第二种方法直接使用memcpy拷贝，所以相差巨大。
最后，Lua5.2之后的版本在字符串的实现上有些许的不同，增加长字符串和短字符串的概念，但是大体的设计概念还是一样，之后有时间再补充5.2之后版本的字符串实现。