首页 > 代码库 > Lua2.4 字符串相关 tree.c
Lua2.4 字符串相关 tree.c
Lua 中字符串管理是核心内容之一（另一个当然就是表的管理）。
Lua 脚本中用到的字符串，解析时用到的符号，及一些运行时相关的字符串都保存在全局字符串表中，全局字符串表就是 tree.c 中的 string_root 数组。
同样的字符串在 Lua 的全局字符串表中只会出现一次，也就是只保存一次。
先看下数据结构 TaggedString
typedef struct TaggedString
{
Word varindex; /* != NOT_USED if this is a symbol */
Word constindex; /* != NOT_USED if this is a constant */
unsigned long hash; /* 0 if not initialized */
int marked; /* for garbage collection; never collect (nor change) if > 1 */
char str[1]; /* \0 byte already reserved */
} TaggedString;
解释下各字段：
varindex : 字符串在符号表中的下标，如果字符串是用做符号的话。
constindex : 如果字符串是字符串常量，该字段表示字符串在常量字符串表中的下标。
hash : 字符串的散列值，没有初始化之前该值为 0 。
marked : 垃圾回收 gc 的标志位，如果不需要垃圾回收，应该给它设置一个大于 1 的值。
str[] : 实际字符串，注意这里已经有一个字符串位置了。
最后一个字符串数组的用法在 C 语言里叫做和柔性数组，也就是数组名字本身只起到占位作用。
实际使用的时候，会给结构体 TaggedString 分配一大块内存，内存的前部由结构体所用，其它的 sizeof(TaggedString) 大小之外的内存，都相当于分配给结构体最后一个数组了，那片内存通过数组名使用。
再看下 stringtable
typedef struct {
int size;
int nuse; /* number of elements (including EMPTYs) */
TaggedString **hash;
} stringtable;
各字段的意思：
size : 表的大小，会随着表项的增加而增加。
nuse : 已经使用的元素个数，包括已经回收的（就是指向一个空元素 EMPTY 的）。
hash : TaggedString 指针的指针，使用时是用做 TaggedString 指针的数组。
再看下全局的字符串表 string_root
static stringtable string_root[NUM_HASHS];
为什么 string_root 有 NUM_HASHS（64）项？ 因为ASCII码 是 128 个，A 的 ASCII 码是 65，ASCII 码 64 之前的字符基本上是不会出现在第一位的字符，所以用一半刚好。
看下对外接口
TaggedString *lua_createstring (char *str)
{
return insert(str, &string_root[(unsigned)str[0]%NUM_HASHS]);
}
其中调用了 insert 函数, insert 函数的第二个参数是一个 stringtable 指针，这里根据字符串的首字母选项 stringtable 表项的结果是把首字母相同字符串存到了一个 stringtable 表项中。然后在存到表项中时再次散列，保存到 stringtable 的 hash 中。这可能也就是明明是字符串处理的文件，却取个名字叫 tree 的原因吧。因为散列的关系，字符串保存完后可不就像是一棵棵树么。不过更严格的说，是不分叉的树，也就是链表了。首字母相同的字符串组成一个链表，首字母不同的在全局字符串表 string_root 的不同的 stringtable 表项中。
看下字符串是如何 insert 到 stringtable 中的
static TaggedString *insert (char *str, stringtable *tb)
{
TaggedString *ts;
unsigned long h = hash(str);
int i;
int j = -1;
if ((Long)tb->nuse*3 >= (Long)tb->size*2)
{
if (!initialized)
initialize();
grow(tb);
}
i = h%tb->size;
while (tb->hash[i])
{
if (tb->hash[i] == &EMPTY)
j = i;
else if (strcmp(str, tb->hash[i]->str) == 0)
return tb->hash[i];
i = (i+1)%tb->size;
}
/* not found */
lua_pack();
if (j != -1) /* is there an EMPTY space? */
i = j;
else
tb->nuse++;
ts = tb->hash[i] = (TaggedString *)luaI_malloc(sizeof(TaggedString)+strlen(str));
strcpy(ts->str, str);
ts->marked = 0;
ts->hash = h;
ts->varindex = ts->constindex = NOT_USED;
return ts;
}
程序一开始，先算出字符串的散列值。计算散列值的函数如下：
static unsigned long hash (char *str)
{
unsigned long h = 0;
while (*str)
h = ((h<<5)-h)^(unsigned char)*(str++);
return h;
}
接下来判断 stringtable 是否是使用超过三分之二，如果是，需要增加 TaggedString 项。
在未初始化时，需要先进行初始化 initialize。
static void initialize (void)
{
initialized = 1;
luaI_addReserved();
luaI_initsymbol();
luaI_initconstant();
}
先设置初始化标签。
添加保留字 luaI_addReserved，就是之前在词法分析中看到的那个函数，注意所有保留字的 TaggedString 的 markded 字段值都是一个比较大的数字，以避免垃圾回收。
初始化符号 luaI_initsymbol，把一些内置的函数名字添加到字符串中，设置一些全局环境（这个到说解释器 table 管理里再说）。
初始化字符串常量 luaI_initconstant， 就是把两个预字义的字符串添加到全局中字符串表中去。
再看下 stringtable 的如何增加表项的：
static void grow (stringtable *tb)
{
int newsize = luaI_redimension(tb->size);
TaggedString **newhash = newvector(newsize, TaggedString *);
int i;
for (i=0; i<newsize; i++)
newhash[i] = NULL;
/* rehash */
tb->nuse = 0;
for (i=0; i<tb->size; i++)
if (tb->hash[i] != NULL && tb->hash[i] != &EMPTY)
{
int h = tb->hash[i]->hash%newsize;
while (newhash[h])
h = (h+1)%newsize;
newhash[h] = tb->hash[i];
tb->nuse++;
}
luaI_free(tb->hash);
tb->size = newsize;
tb->hash = newhash;
}
通过当前的 size 调用 luaI_redimension 函数得到一个 newsize，用这个 newsize 来新建一个 TaggedString 指针数组。
luaI_redimension 定义在 hash.c 中
/* hash dimensions values */
static Long dimensions[] =
{3L, 5L, 7L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
int luaI_redimension (int nhash)
{
int i;
for (i=0; dimensions[i]<MAX_INT; i++)
{
if (dimensions[i] > nhash)
return dimensions[i];
}
lua_error("table overflow");
return 0; /* to avoid warnings */
}
代码相对比较直观，从一个预先定义好的从小到大排列的长整型数组中从前到后取得第一个大于所传参数的值。
回到 grow 函数。数组分配内存之后，把每一项初始化为空。
设置当前的已使用元素 nuse 为 0 。
把原来的不为空的表项，拷贝到新分配的内存中去。拷贝时是根据原来的 TaggedString 的 hash 值来找其在新分配的 newhash 中的位置。相应的已使用元素 nuse 自加。
释放老的 stringtable 中的 hash 数组。
设置 stringtable 的 size 和 hash 分别为新的 newsize 和 newhash。
回到 insert 函数。根据上面计算得到的散列值 h 和 stringtable 的 size 算出字符串应该在表项中的位置。如果相应的位置中已经有值了，就向后找表项中第一个空的位置。如果字符串已经存在，就直接返回相应的 TaggedString。
设置字符串前，时行一次垃圾回收 lua_pack(这个在分析解释器的时候再细看)。
如果找到的位置是 NULL，则 stringtable 的已使用元素个数加一（tb->nuse++）。
如果找到的位置是指向 EMPTY 的，则已经使用元素个数不用自加 (就是 if (j!= -1) 处条件为真时)。
为 TaggedString 分配内存空间，拷贝字符串到 TaggedString 的 str 中。
设置相应字段。
lua_createstring 分析完了，顺便说一下一个和它关系比较密切的函数。就是我们之前遇到的 luaI_createfixedstring。
luaI_createfixedstring 定义于 table.c 中
TaggedString *luaI_createfixedstring (char *name)
{
TaggedString *ts = lua_createstring(name);
if (!ts->marked)
ts->marked = 2; /* avoid GC */
return ts;
}
其内部是调用了 lua_createstring，不过在 TaggedString 建成之后，设置了其 marked 值为 2（大于 1 的值可以避免垃圾回收）。
这样，之前的问题列表 TaggedString 相关的就都回答了。
tree.c 中就只有一个对外接口没有分析了，顺便也看一下它吧。
/*
** Garbage collection function.
** This function traverse the string list freeing unindexed strings
*/
Long lua_strcollector (void)
{
Long counter = 0;
int i;
for (i=0; i<NUM_HASHS; i++)
{
stringtable *tb = &string_root[i];
int j;
for (j=0; j<tb->size; j++)
{
TaggedString *t = tb->hash[j];
if (t != NULL && t->marked <= 1)
{
if (t->marked)
t->marked = 0;
else
{
luaI_free(t);
tb->hash[j] = &EMPTY;
counter++;
}
}
}
}
return counter;
}
这是字符串的垃圾回收，上面提到的垃圾回收 lua_pack 里最终就会调用到它。
这个代码也比较直观，就是遍历全局字符串表，把所有 TaggedString 的 marked 字段为 0 的进行释放，同时设置它在 stringtable 中的表项为空 EMPTY。
如果 marked 字段为一个不为 0 但是又不大于 1 的值的话，设置其为 0，以进行下一次的垃圾回收。（注意，在垃圾回收标记过程中这个值可能为 1。垃圾回收相关在分析解释器时再进行分析。）
返回回收的字符串个数。
----------------------------------------
到目前为止的问题：
> luaI_codedebugline 是什么? 调试相关信息有哪些?
> do_compile 里的 TFunc 是什么？那个初始化 luaI_initTFunc 是什么？
> lua_parser 是什么？ do_dump 方法里调的那几个方法又分别是干什么的？
----------------------------------------
Lua2.4 字符串相关 tree.c