lua的字符串和Table类型实现

字符串

实现在lstring.c中。
字符串类型TString定义如下：

typedef union TString {
  L_Umaxalign dummy; /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

字符串内容紧随其后，以\0结尾，用宏getstr来获取字符串指针：

#define getstr(ts)	(const char *)((ts) + 1)

len是字符串的长度，不包括结尾的\0。CommonHeader用于GC。hash是由字符串内容计算出来的哈希值。dummy可能是为了让字符串指针内存对齐，提高访问速度。

lua的字符串内容不可修改，相同字符串会合并存储在一个全局字符串表中，字符串表定义如下：

typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse; /* number of elements */
  int size;
} stringtable;

这是一个开散列的哈希表实现。一个字符串被放入字符串表的时候，先检查一下表中有没有相同的字符串。如果有，则复用己有的字符串；没有则创建一个新的。碰到哈希值相同的字符串，简单的串在同一个哈希位的链表上即可。

创建一个lua字符串的函数如下：

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; /* if string is too long, don't hash all its chars */
  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 */
}

Real-World Impact of Hash DoS in Lua 指出该哈希计算方法面临Dos攻击的风险，攻击者可以轻易构造出上千万拥有相同哈希值的不同字符串，以此数十倍的降低lua从外部压入字符串进入内部字符串表的效率。
Lua 5.2.1为了解决这个问题，把长字符串独立出来，长字符串不再通过哈希内部化进入全局字符串表。同时使用了一个随机种子用于哈希值的计算，使攻击者无法轻易构造出拥有相同哈希值的不同字符串。

userdata在储存形式上和字符串相同，可以看成是拥有独立元表，不被内部化处理，也不需要追加\0的字符串。在实现上，只是对象结构从TString换成了UData，所以实现代码也被放在lstring.c中，其api也以luaS开头。

Table

实现在ltable.c中。
Table类型定义如下：

typedef struct Table {
  CommonHeader;
  lu_byte flags; /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode; /* log2 of size of `node' array */
  struct Table *metatable;
  TValue *array; /* array part */
  Node *node;
  Node *lastfree; /* any free position is before this position */
  GCObject *gclist;
  int sizearray; /* size of `array' array */
} Table;

table的储存分为数组部分和哈希表部分。
数组部分在TValue *array，数组大小是sizearray。
哈希表以闭散列方式实现，节点类型：

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

TKey相比TValue多了一个struct Node *next成员，用以链接冲突的节点。
非dummynode哈希表的大小为2^lsizenode。
为了减少空表的维护成本，定义了一个不可改写的全局空哈希表dummynode，当以大小0初始化或resize哈希表时，node域指向这个dummy节点，此时lsizenode也为0。
云风在 一个链接 lua 引起的 bug , 事不过三 中描述了一个dummynode的问题，用NULL来替换dummynode或许可以更好的解决这个问题。

所以每个table结构，最多会由三块连续内存构成。一个Table结构，一块存放了连续整数索引的数组，和一块大小为2的整数次幂的哈希表。
lastfree最初指向node末尾，每当需要一个空闲节点时，就从lastfree倒着查找，如果lastfree到达node起始位置，说明空间已满，需要扩容了。

是不是所有key是正整数的节点一定在数组部分？
不是的，刚创建的空表数组部分长度为0，哈希表也为空，插入新元素时，如果key是数字但不在[1,sizearray]范围内，会往哈希表里插，如果发现哈希表没有空闲节点，便会执行rehash()，rehash()会依据一定规则（computesizes()函数，调整数组部分的大小使其利用率不小于50%），重新设置数组和哈希表的大小。

往哈希表中插入节点的流程可直接参考newkey()的注释：

/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
static TValue *newkey (lua_State *L, Table *t, const TValue *key);

table的长度定义只对序列表有效，所以在实现的时候，仅需要遍历数组部分。只有当数组部分填满时才需要进一步的去检索哈希表。

元表

实现在ltm.c中。
Lua实现复杂数据结构大量依赖给table附加一个元表（metatable）来实现，故而table本身的一大作用就是作为元表存在。但并非所有元表都提供了所有元方法，对于不存在的元方法查询就是一个浪费了。
在上面代码中，可以看到每个Table结构中都有一个fags域，它记录了那些元方法不存在，查询元方法时用于缓存查询结果：

const TValue *luaT_gettm (Table *events, TMS event, TString *ename) {
  const TValue *tm = luaH_getstr(events, ename);
  lua_assert(event <= TM_EQ);
  if (ttisnil(tm)) { /* no tag method? */
    events->flags |= cast_byte(1u<<event); /* cache this fact */
    return NULL;
  }
  else return tm;
}

lua仅对table的元表做了这个优化，而没有理会其它类型的元表的元方法查询。这大概是因为只有table容易缺失一些诸如__index这样的元方法，而使用table的默认行为。当lua代码把这些操作作用于其它类型如userdata时，它没有table那样的默认行为，故对应的元方法通常存在。

参考

Lua 源码欣赏 云风
lua 5.1.4 源码