Lua中对于String的实现。

Lua使用TString结构体代表一个字符串对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
*/
typedef struct  {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
  unsigned int hash;
  size_t len;  /* number of characters in string */
  struct  *hnext;  /* linked list for hash table */
} 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;

hash用来记录字符串对应的哈希值，len用来记录字符串的长度。

在Lua中，分为长字符串和短字符串，长度大于40的是长字符串，小于40的是短字符串，这部分在luaconf.h中定义：

1
2
3
4
5
6
7

@@ LUAI_MAXSHORTLEN is the maximum length for short strings, that is,
** strings that are internalized. (Cannot be smaller than reserved words
** or tags for metamethods, as these strings must be internalized;
** #("function") = 8, #("__newindex") = 10.)
*/

对于短字符串，在实际使用中一般用来作为索引或需要进行字符串比较，存放在global_State->strt中，这个字符串表（strt）是一个stringtable类型的全局唯一的哈希表，当需要创建一个短字符串对象时，会首先在这个表中查找已有对象。所有的短字符串都是全局唯一的，不会存在两个相同的短字符串对象，如果短字符串对象的extra>0，表示这是一个系统保留的字符串；长字符串一般用来存放文本数据，很少需要比较或者索引，所以长字符串被挂接到allgc链表上当作普通的对象来处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

** 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 {
    if (l + 1 > (MAX_SIZE - sizeof(TString))/sizeof(char))
      luaM_toobig(L);
    return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed);
  }
}

/* 在global_State中存储的哈希表结构体 */
typedef struct stringtable {
  TString **hash;
  int nuse;  /* number of elements  已装元素的个数 */
  int size;	/* 实际hash桶的大小 */
} stringtable;

对于短字符串，在创建的时候，首先计算str的哈希值。计算时会得到一个随机种子，这个种子就是global_State->seed，然后通过LUAI_HASHLIMIT控制步长，每一个步长范围内取字符串中的一个字符，和上次hash的结果相加，得到新的hash结果，计算出hash后，开始找是否存在这个字符串，方法是遍历global_State->strt->hash，短字符串表申请内存的大小和实际使用大小由后两个字段表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

** 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)];
  for (ts = *list; ts != NULL; ts = ts->hnext) {
    if (l == ts->len &&
        (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
      /* found! */
      if (isdead(g, ts))  /* dead (but not collected yet)? */
        changewhite(ts);  /* resurrect it */
      return ts;
    }
  }
  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, str, l, LUA_TSHRSTR, h);
  ts->hnext = *list;
  *list = ts;
  g->strt.nuse++;
  return ts;
}

/* 对字符串按步长hash的函数 */
unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
  unsigned int h = seed ^ cast(unsigned int, l);
  size_t l1;
  size_t step = (l >> LUAI_HASHLIMIT) + 1;
  for (l1 = l; l1 >= step; l1 -= step)
    h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1]));
  return h;
}