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 TString {
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 TString *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.)
*/
#define LUAI_MAXSHORTLEN 40

对于短字符串,在实际使用中一般用来作为索引或需要进行字符串比较,存放在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;
}