咖啡's blog

专心 专注 专业

0%

Lua源码笔记(7)--字符串的处理

发表于 更新于 分类于 ， Valine：

理解Lua中对字符串的处理方式,可以看到哈希表这种数据结构在实际开发中的作用;从而在开发的过程中对哈希加深理解和运用，顾名思义哈希，有从大的空间哈希到一个小的空间里，也有从小的空间哈希到一个很大的空间里，但在代数学的术语里就是映射,从大的空间映射到小的空间里，固然有可能碰到映射到一个位置上，所以产生了碰撞，处理的方法就是将碰撞的节点链接在一起。

1. 字符串哈希表存放的位置

字符串的哈希表是存放在global_State中,

1
2
3
4
5
6
7
8
9
10
typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse;  /* number of elements */
  int size;
} stringtable;

typedef struct global_State {
  stringtable strt;  
  // ...
} global_State;

2. luaS_newlstr创建TString

luaS_是TString字符串相关的函数的前缀
luaS_newlstr函数创建TString字符串，而luaS_newlstr函数调用newlstr函数创建字符串。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 实际创建一个新的TString的主函数
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);
  // TString字符串后面跟着字符串的实际内容
  // l+1表示字符串的\0结尾符是系统来添加
  ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
  ts->tsv.len = l;
  ts->tsv.hash = h;
  ts->tsv.marked = luaC_white(G(L));
  ts->tsv.tt = LUA_TSTRING;
  ts->tsv.reserved = 0;
  // 有一次memcpy操作
  memcpy(ts+1, str, l*sizeof(char));
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  tb = &G(L)->strt;
  // h是一个哈希值由上层函数计算得出
  // 这里根据哈希表的长度在重新计算一下
  h = lmod(h, tb->size);
  // 位置为h的节点赋值给ts
  // ts放到当前h位置上
  ts->tsv.next = tb->hash[h];  
  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;
}

// 创建字符串的接口这里判断是否已经存在相同字符串
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  unsigned int h = cast(unsigned int, l);  /* seed */
  size_t step = (l>>5)+1;  
  size_t l1;
  // 这里重要的是字符串的哈希算法
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    TString *ts = rawgco2ts(o);
    // 找到相同的字符串就直接返回字符串
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  // 没有找到字符串就创建新的字符串
  return newlstr(L, str, l, h);  /* not found */
}

3. 扩展字符串哈希表

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
void luaS_resize (lua_State *L, int newsize) {
  GCObject **newhash;
  stringtable *tb;
  int i;
  // 回收字符串的时候不扩展字符串哈希表
  if (G(L)->gcstate == GCSsweepstring)
    return;
  newhash = luaM_newvector(L, newsize, GCObject *);
  tb = &G(L)->strt;
  for (i=0; i<newsize; i++) newhash[i] = NULL;
  // 重新哈希
  for (i=0; i<tb->size; i++) {
    GCObject *p = tb->hash[i];
    while (p) {  /* for each node in the list */
      GCObject *next = p->gch.next;  /* save next */
      unsigned int h = gco2ts(p)->hash;
      int h1 = lmod(h, newsize);  /* new position */
      lua_assert(cast_int(h%newsize) == lmod(h, newsize));
      p->gch.next = newhash[h1];  /* chain it */
      newhash[h1] = p;
      p = next;
    }
  }
  // 释放旧的哈希字符串表
  luaM_freearray(L, tb->hash, tb->size, TString *);
  tb->size = newsize;
  tb->hash = newhash;
}