近日配置了下终端下的 vim 插件，把 c 相关的开发插件都弄的勉强可以用了，为了熟悉下 GDB 的一些基本操作，就拿读 lua 部分源代码来练手了。
这里所有的内容均基于 lua 5.3 版本。
table 的内部操作定义于文件 ltable.h / ltable.c 中，有以下相关的函数构成:
- luaH_new : 构造一个新的 table
1.初始化
Table *luaH_new (lua_State *L) {
GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
Table *t = gco2t(o);
t->metatable = NULL;
t->flags = cast_byte(~0);
t->array = NULL;
t->sizearray = 0;
setnodevector(L, t, 0);
return t;
}
首先由 lua gc 模块分配一个被托管的垃圾回收对象 GCObject *o, 然后转为一个指向实际的 table 结构的 Table *t 进行初始化操作。
一个 lua table 被分为两个部分：数组部分和哈希表部分。
数组部分的初始化比较粗暴，直接置零。
t->array = NULL; t->sizearray = 0;
则哈希表的部分由 setnodevector 函数来初始化，由于传入的特殊表大小 0，哈希表部分被指向一个 所有哈希部分为空的 table 所共享的一个静态变量 dummynode (此处为一个宏)
static void setnodevector (lua_State *L, Table *t, unsigned int size) {
int lsize;
if (size == 0) { /* no elements to hash part? */
t->node = cast(Node *, dummynode); /* use hashnode 'dummynode' */
lsize = 0;
}
else {
....
struct Table
再回头来看看 Table 的结构:
typedef struct Table {
CommonHeader;
lu_byte flags; /* 1<<next means tagmethod(next) is not present */
lu_byte lsizenode; /* log2 of size of 'hashnode' array */
unsigned int sizearray; /* size of 'array' array */
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
struct Table *metatable;
GCObject *gclist;
} Table;
数组部分用到了字段 sizearray, array 哈希表部分用到了字段 node, lastfree, lsizenode
lsizenode 比较特殊，它存储的不是哈希表部分的真实大小，而是存储了真实大小的2的整数次幂 2^lsizenode，也就是说哈希表部分的大小永远是2的整数次幂。
对于一个空的 table 来说，它会是这样的结构:
需要注意的是：为了简便, lastfree 画出的是指向最后一个可用的节点，实际上指针指向的是最后一个可用节点的下一个位置。
2.数组插入
以下列代码为例:
local t = {}; for i=1, 3 do t[i] = 123456 end
其 lua 字节码含义为:
0+ params, 5 slots, 1 upvalue, 5 locals, 3 constants, 0 functions
1 [2] NEWTABLE 0 0 0
2 [2] LOADK 1 -1 ; 1
3 [2] LOADK 2 -2 ; 10
4 [2] LOADK 3 -1 ; 1
5 [2] FORPREP 1 1 ; to 7
6 [2] SETTABLE 0 4 -3 ; - 123456
7 [2] FORLOOP 1 -2 ; to 6
8 [2] RETURN 0 1
可以在 lvm.c luaV_execute 中的下列分之中打上断点进行观察，对于 GDB 可以使用条件断点 b lvm.c:864 if rc->value_.i == 123456 来调试。
vmcase(OP_SETTABLE) {
TValue *rb = RKB(i);
TValue *rc = RKC(i);
settableProtected(L, ra, rb, rc);
vmbreak;
}
settable 入口
这里的 settableProtected 是一个宏，luaV_fastset 尝试进行快速赋值，如果失败则执行 luaV_finishset插入一个新的键:
#define settableProtected(L,t,k,v) { const TValue *slot; \
if (!luaV_fastset(L,t,k,slot,luaH_get,v)) \
Protect(luaV_finishset(L,t,k,v,slot)); }
宏 luaV_fastset 中，先尝试使用函数 luaH_get 查找在表 t 中已经存在的键 k, 如果该键已经存在于 table 中，那么只需要简单得取出它并修改其值为 v 即可, 这里的 slot 是一个存放查找结果的中间变量:
// lvm.h
#define luaV_fastset(L,t,k,slot,f,v) \
(!ttistable(t) \
? (slot = NULL, 0) \
: (slot = f(hvalue(t), k), \
ttisnil(slot) ? 0 \
: (luaC_barrierback(L, hvalue(t), v), \
setobj2t(L, cast(TValue *,slot), v), \
1)))
// ltable.c
const TValue *luaH_get (Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
case LUA_TNIL: return luaO_nilobject;
case LUA_TNUMFLT: {
lua_Integer k;
if (luaV_tointeger(key, &k, 0)) /* index is int? */
return luaH_getint(t, k); /* use specialized version */
/* else... */
} /* FALLTHROUGH */
default:
return getgeneric(t, key);
}
}
首先进入到了 luaH_get 的分之 case LUA_TNUMIN 中调用 luaH_getint 尝试获取已经存在的索引为正整数值 1 的 TValue 结构用于存放新值。
const TValue *luaH_getint (Table *t, lua_Integer key) {
/* (1 <= key && key <= t->sizearray) */
if (l_castS2U(key) - 1 < t->sizearray)
return &t->array[key - 1];
else {
Node *n = hashint(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
return gval(n); /* that's it */
else {
int nx = gnext(n);
if (nx == 0) break;
n += nx;
}
}
return luaO_nilobject;
}
}
先尝试判断这个整数 key 是否在 table 的数组部分，由于 sizearray 为 0，所以并不会在数组部分。继续尝试从哈希表部分查找，由于哈希表部分是指向 dummynode 的，所以依然未查找，整个函数返回空对象 luaO_nilobject（对于如果存在于哈希表部分的键的查找请往下继续看）。
返回 luaV_execute 函数中继续执行, luaV_fastset 结果为 0，查找已存在的 k 失败。 luaV_finishset 执行最终的插入操作，luaV_finishset 有相关的元表操作，暂且在这里忽略掉它们，通过 luaH_newkey 来扩展一个新的位置来存放值。
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
...
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
Node *othern;
Node *f = getfreepos(t); /* get a free place */
if (f == NULL) { /* cannot find a free place? */
rehash(L, t, key); /* grow table */
/* whatever called 'newkey' takes care of TM cache */
return luaH_set(L, t, key); /* insert key into grown table */
}
...
}
忽略其他条件分之的代码，isdummy(mp) 为 true 进入分之，getfreepos 返回无可用空闲节点，开始执行第一次 rehash 操作。
rehash
static void rehash (lua_State *L, Table *t, const TValue *ek) {
unsigned int asize; /* optimal size for array part */
unsigned int na; /* number of keys in the array part */
unsigned int nums[MAXABITS + 1];
int i;
int totaluse;
for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */
na = numusearray(t, nums); /* count keys in array part */
totaluse = na; /* all those keys are integer keys */
totaluse += numusehash(t, nums, &na); /* count keys in hash part */
/* count extra key */
na += countint(ek, nums);
totaluse++;
/* compute new size for array part */
asize = computesizes(nums, &na);
/* resize the table to new computed sizes */
luaH_resize(L, t, asize, totaluse - na);
}
rehash 函数作用是计算数组部分和哈希部分希望调整到的合适的新长度，然后进行扩展空间。
构造一个 nums[MAXABITS + 1] 数组来记录区间 (2^(i – 1), 2^i] 值不为 nil 的正整数键的数量。
变量 na 记录了所有正整数键的数量。
numusearray 遍历了整个数组部分，以区间 (2^(i – 1), 2^i] 为步长来遍历每个区间的非空的值，记录数量到数组 nums 中，同时最终返回数组中非空值的总数：
static unsigned int numusearray (const Table *t, unsigned int *nums) {
int lg;
unsigned int ttlg; /* 2^lg */
unsigned int ause = 0; /* summation of 'nums' */
unsigned int i = 1; /* count to traverse all array keys */
/* traverse each slice */
for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
unsigned int lc = 0; /* counter */
unsigned int lim = ttlg;
if (lim > t->sizearray) {
lim = t->sizearray; /* adjust upper limit */
if (i > lim)
break; /* no more elements to count */
}
/* count elements in range (2^(lg - 1), 2^lg] */
for (; i <= lim; i++) {
if (!ttisnil(&t->array[i-1]))
lc++;
}
nums[lg] += lc;
ause += lc;
}
return ause;
}
numusehash 遍历了整个哈希表部分来进行计数哈希表部分的使用总数。它也同时统计了哈希部分所有正整数键的数量累加至 na，因为这些键可能会在 rehash 后放入数组部分。
static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
int totaluse = 0; /* total number of elements */
int ause = 0; /* elements added to 'nums' (can go to array part) */
int i = sizenode(t);
while (i--) {
Node *n = &t->node[i];
if (!ttisnil(gval(n))) {
ause += countint(gkey(n), nums);
totaluse++;
}
}
*pna += ause;
return totaluse;
}
na += countint(ek, nums) 如果即将插入的新键是一个正整数，那么也把它记录到 nums 数组里，同时否则什么也不做。
computesizes 通过已知所有的（包括即将插入的）正整数键值在 (2^(i – 1), 2^i] 的分布，和正整数键数量的总数，来计算出一个新的数组部分的大小。在数组范围外的正整数键放到哈希表中：
static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
int i;
unsigned int twotoi; /* 2^i (candidate for optimal size) */
unsigned int a = 0; /* number of elements smaller than 2^i */
unsigned int na = 0; /* number of elements to go to array part */
unsigned int optimal = 0; /* optimal size for array part */
/* loop while keys can fill more than half of total size */
for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) {
if (nums[i] > 0) {
a += nums[i];
if (a > twotoi/2) { /* more than half elements present? */
optimal = twotoi; /* optimal size (till now) */
na = a; /* all elements up to 'optimal' will go to array part */
}
}
}
lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
*pna = na;
return optimal;
}
（注意: 可以跳过下面这里的说明，后面有另一个角度的解释）
以有 16 个连续的已存在的正整数键 1 至 16 为例，如果插入正整数键 17， 那么 rehash 时计算计算出的 nums 如下:
nums[MAXABITS + 1] = {1, 1, 2, 4, 8, 0 ...}
区间 (0.5, 1], (1, 2], (2, 4], (4, 8], (8, 16] 满
算上插入的新键，则所有的正整数键为 17 个。那么会遍历且累加正整数键的合，同时判断累加和是否大于当前右闭区间一半的大小 twotoi (也就是左区间)，如果成立，则记录数组到此大小。
累加到区间 i=4, (8, 16] 时， a = 16, twotoi = 16 时。数组总数为 pna = 17，循环还未终止。
累加到区间 i=5, (16, 32] 时，a = 17, twotoi = 32 时，a > twotoi / 2 成立，且循环终止，数组部分取 32。
如果后面的区间还有正整数键存在，则继续用上面的规则来计算。
但是循环会在正整数键总数 pna 小于等于当前右区间的一半 (twotoi/2) 时停下。因为后面的区间已经不可能成立 累加的正整数键大于当前区间右区间的一半 (twotoi/2)了。
假设这里的 17 个正整数键不是连续的，最后迭代到 (16, 32] 已经够了，因为 17 个正整数键值对已经不可能在 (32, 64] 范围内成立 17 > 64 / 2 。
上面确实很难理解，让我们换一个逆向的方向来理解它：
[1, 2^(MAXABITS + 1)] 范围内有没有一半以上的正整数键？（第一次是不可能的，整数键最大数量为 2^MAXABITS, 至少得 2^MAXABITS + 1 个整数键才算一半以上） 没有，分配这个长度的数组太浪费了，砍一半看看。 [1, 2^MAXABITS] 范围内有没有一半以上的正整数键？ 没有，砍一半。 ... [1, 64] 范围内有没有一半以上的正整数键？ 没有，砍一半。 [1, 32] 范围内有没有一半以上的正整数键？ 有，17 大于 32 / 2，就它了。
computesizes 则是上面说明的顺序遍历版本，所以会比较难理解。
可用下列代码进行测试:
GDB 断点: b rehash if ek->value_.i >= 16 && ek->value_.i < 999
local t = {}; for i=1, 16 do t[i] = 0 end; t[32] = 0
可以看见最终的数组长度 asize 被计算为32，如果最后一次的正整数键赋值改成 t[33] = 0，则键 33 会被放到哈希表部分。
让我们回到首次插入正整数键 1 的时刻，此刻传给 luaH_resize 的分配数组长度 nasize 为 1，哈希表长度 nhsize 为 0。
void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
unsigned int nhsize) {
unsigned int i;
int j;
unsigned int oldasize = t->sizearray;
int oldhsize = t->lsizenode;
Node *nold = t->node; /* save old hash ... */
if (nasize > oldasize) /* array part must grow? */
setarrayvector(L, t, nasize);
/* create new hash part with appropriate size */
setnodevector(L, t, nhsize);
if (nasize < oldasize) { /* array part must shrink? */
t->sizearray = nasize;
/* re-insert elements from vanishing slice */
for (i=nasize; i<oldasize; i++) {
if (!ttisnil(&t->array[i]))
luaH_setint(L, t, i + 1, &t->array[i]);
}
/* shrink array */
luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
}
/* re-insert elements from hash part */
for (j = twoto(oldhsize) - 1; j >= 0; j--) {
Node *old = nold + j;
if (!ttisnil(gval(old))) {
/* doesn't need barrier/invalidate cache, as entry was
already present in the table */
setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
}
}
if (!isdummy(nold))
luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old hash */
}
如果数组部分需要的长度大于原有的长度: 则通过 setarrayvector 分配新的数组长度 1，并且把新增的部分赋值为 nil。如果旧的数组含有数据，分配函数 luaM_reallocvector 会复制这部分数据到新数组中。
static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
unsigned int i;
luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
for (i=t->sizearray; i<size; i++)
setnilvalue(&t->array[i]);
t->sizearray = size;
}
若数组部分被截断: 则遍历被截断部分的正整数键通过 luaH_setint 插入至哈希表（数组长度先已经被标记为较短的新长度 nasize，此时新哈希表空间已被分配），然后再缩小数组部分。
对于哈希部分，则进行一次完整的插入操作。
栈帧最终回退到 luaH_newkey 中，进行 luaH_set 赋值操作，至此对于一个空表的首次数组部分赋值完成, 此时 table 的结构如下:
3.哈希插入
对于哈希的插入使用下列的示例代码:
local t = {}; t["s"] = 123456
再回到函数 luaH_get 中，它返回一个查找到的键的对应的 TValue 结构：
对于短字符串键，使用 luaH_getshortstr 来查找。
对于正整数键，或者可以转换成整数形式的浮点数键，使用 luaH_getint 来查找。
nil 类型返回静态变量 luaO_nilobject (这并不意味着你能插入 nil 键)。
对于其他类型，使用标准查找 getgeneric。
除了正整数键查找 luaH_getint 会先查找数组部分以外，其它查找函数都做的是类似的事情，以 getgeneric 为例:
static const TValue *getgeneric (Table *t, const TValue *key) {
Node *n = mainposition(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
if (luaV_rawequalobj(gkey(n), key))
return gval(n); /* that's it */
else {
int nx = gnext(n);
if (nx == 0)
return luaO_nilobject; /* not found */
n += nx;
}
}
}
通过 mainposition 获得 主位置节点(键哈希值与哈希表长度取模)，然后判断哈希节点的键是否与所查找的键相等，如果相等则返回节点的 TValue。否则通过存储的偏移值查找下一个节点，如果没有，则表明键不在哈希表中。
一种可能的情况：
对于哈希部分是指向 dummynode 的 table 来说，getgeneric 肯定是找不到对应的键的节点的，最终 luaH_get 返回 luaO_nilobject。
接下来的大部分流程与数组插入无异，对于空表来说 getfreepos 返回 NULL, 执行第一次 rehash。
最终传递给 luaH_resize 中的 setnodevector 函数来调整哈希部分大小，对于传入的新的哈希大小，分配的实际尺寸为 2^ceil(log2(size))，所以哈希表部分也是以2的整数次幂增长的。
新的哈希表空间分配完成后，通过 luaH_set 插入被移出数组部分的内容和原哈希表的内容。
TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
const TValue *p = luaH_get(t, key);
if (p != luaO_nilobject)
return cast(TValue *, p);
else return luaH_newkey(L, t, key);
}
由于 rehash 是重新排列，在新表中不可能找到一个已经存在的空键 key，所有逻辑均会执行到调用 luaH_newkey 来分配一个新的哈希节点。
这次让我们来看完整的 luaH_newkey 函数:
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
TValue aux;
if (ttisnil(key)) luaG_runerror(L, "table index is nil");
else if (ttisfloat(key)) {
lua_Integer k;
if (luaV_tointeger(key, &k, 0)) { /* index is int? */
setivalue(&aux, k);
key = &aux; /* insert it as an integer */
}
else if (luai_numisnan(fltvalue(key)))
luaG_runerror(L, "table index is NaN");
}
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */
Node *othern;
Node *f = getfreepos(t); /* get a free place */
if (f == NULL) { /* cannot find a free place? */
rehash(L, t, key); /* grow table */
/* whatever called 'newkey' takes care of TM cache */
return luaH_set(L, t, key); /* insert key into grown table */
}
lua_assert(!isdummy(f));
othern = mainposition(t, gkey(mp));
if (othern != mp) { /* is colliding hashnode out of its main position? */
/* yes; move colliding hashnode into free position */
while (othern + gnext(othern) != mp) /* find previous */
othern += gnext(othern);
gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
*f = *mp; /* copy colliding hashnode into free pos. (mp->next also goes) */
if (gnext(mp) != 0) {
gnext(f) += cast_int(mp - f); /* correct 'next' */
gnext(mp) = 0; /* now 'mp' is free */
}
setnilvalue(gval(mp));
}
else { /* colliding hashnode is in its own main position */
/* new hashnode will go into free position */
if (gnext(mp) != 0)
gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
else lua_assert(gnext(f) == 0);
gnext(mp) = cast_int(f - mp);
mp = f;
}
}
setnodekey(L, &mp->i_key, key);
luaC_barrierback(L, t, key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}
在首次 mainposition 之后，获得的节点 mp 如果是一个空节点且不指向 dummynode 时，则表明该节点可用。否则判断是否需要 rehash (表指向 dummynode 时 getfreepos 一定会返回 NULL)，由于当前的是 rehash 过程中的重排列，所以不可能再次发生 rehash。
当查找的 mp 由于冲突被其它键所占用时，会通过 getfreepos 尝试获取一个可用的节点来存储新的键。
static Node *getfreepos (Table *t) {
while (t->lastfree > t->node) {
t->lastfree--;
if (ttisnil(gkey(t->lastfree)))
return t->lastfree;
}
return NULL; /* could not find a free place */
}
lastfree 初始指向哈希表的最后一个节点的下一个位置，向前迭代直到找到一个空节点，如果迭代到哈希表头则表明无可用节点，返回 NULL。
当返回一个可用的节点时，会判断:
1) 如果属于同一主位置节点链下 (现有的 mp 位置的键的主位置节点和新插入的 key 的主位置节点确实指向的同一个节点)，那么把空节点插入到主位置节点之后（每个节点的 TKey 结构中存储着指向下一个节点的偏移值）。
2) 如果不属于同一主位置节点链下，则意味着原本通过 mainposition(newkey) 直接定位的节点被其它节点链中的某个节点占用：
由 othern (起始位置 上图 key1 位置) 节点开始遍历链表直到 mp 的前一个位置 (指向上图 key2 位置的节点，在这里就是 key1 自己), 然后将 mp 的数据移动到空节点上，othern 指向新的节点，旧的节点用来放入新插入的键：
luaH_newkey 返回新键的 TValue 结构，rehash 中的哈希部分的重新插入全部完成。
最终: 示例代码中的 table 新哈希部分长度为 1，且不会有哈希部分的重新插入，所以执行完毕后直接对插入的新键进行 luaH_newkey 操作，最终得到了一个可用的键位插入新值 123456，至此哈希插入完成。
4.索引
索引函数 luaH_get 上述内容已经描述
5.序列长度
在 lua文档 中，取长操作符的定义是当 table 是一个序列时才有定义。序列意味着正整数键的部分必须是连续的（非正整数键会忽略）。否则是一个 未定义行为，例如：
print(#{nil,nil,0}) => 3
local t = {1,2,3}; t[2] = nil; print(#t) => 3
local t = {1,2,3}; t[2] = nil; t["x"] = nil; print(#t) => 1
local t = {1,2,3,4,5,6,7,8}; t[16] = 0; print(#t) => 16
local t = {1,2,3,4,5,6,7,8}; t[15] = 0; print(#t) => 8
luaH_getn 获取了一个 table 序列的长度 (假定它是一个序列为前提):
int luaH_getn (Table *t) {
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1])) {
/* there is a boundary in the array part: (binary) search for it */
unsigned int i = 0;
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
/* else must find a boundary in hash part */
else if (isdummy(t->node)) /* hash part is empty? */
return j; /* that is easy... */
else return unbound_search(t, j);
}
有三种情况:
1) 数组部分刚好被占满，且没有哈希表部分，则直接返回 sizearray。
2) 数组部分没有被占满，则通过二分查找检索到数组最后的非空位置。最终返回序列长度。
3) 数组部分被占满，且有哈希表部分，执行 unbound_search 传入数组长度，开始搜索在哈希部分的正整数键。
使用下列测试代码可以触发哈希部分的搜索：
local t= {};
for i=1, 8 do
t[i] = 0
end
for i=1, 16 do
t[''..i] = 0
end
for i=1, 16 do
t[''..i] = nil
end
for i=1, 16 do
t[i + 8] = 0
end
print(#t)
数组部分先占用8个长度，再占用16个长度的哈希部分，再清空它们，全部插入整数键，table 的序列长度最终为24，数组长度为8，哈希表长度为 16。
再来看 unbound_search 的实现：
static int unbound_search (Table *t, unsigned int j) {
unsigned int i = j; /* i is zero or a present index */
j++;
/* find 'i' and 'j' such that i is present and j is not */
while (!ttisnil(luaH_getint(t, j))) {
i = j;
if (j > cast(unsigned int, MAX_INT)/2) { /* overflow? */
/* table was built with bad purposes: resort to linear search */
i = 1;
while (!ttisnil(luaH_getint(t, i))) i++;
return i - 1;
}
j *= 2;
}
/* now do a binary search between them */
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(luaH_getint(t, m))) j = m;
else i = m;
}
return i;
}
以每次2倍的增幅向后搜索可能的二分查找用的区间，以 j = 8 为例，则搜索 [9,18], [18,36]，当 j 等于 36 时，哈希部分的键 36 为 nil，则说明序列的末尾在 18 到 36 范围内，然后进行二分查找最终返回序列长度。
如果搜索到正整数即将溢出的范围都还没有到条件 (则说明你构造了一个很糟糕的 table)，则使用线性搜索。
6.迭代器
ipairs
注意：5.2 中的元方法 __ipairs 在 5.3 中已被标记为 deprecated，可以定义宏 LUA_COMPAT_5_2 来开启它。
// lbaselib.c
static int luaB_ipairs (lua_State *L) {
#if defined(LUA_COMPAT_IPAIRS)
return pairsmeta(L, "__ipairs", 1, ipairsaux);
#else
luaL_checkany(L, 1);
lua_pushcfunction(L, ipairsaux); /* iteration function */
lua_pushvalue(L, 1); /* state */
lua_pushinteger(L, 0); /* initial value */
return 3;
#endif
}
ipairs 返回了三个值给 for 循环来进行迭代: 迭代函数, 迭代对象 (函数的第一个参数), 以及迭代初始值 0。迭代函数 ipairsaux 如下:
static int ipairsaux (lua_State *L) {
lua_Integer i = luaL_checkinteger(L, 2) + 1;
lua_pushinteger(L, i);
return (lua_geti(L, 1, i) == LUA_TNIL) ? 1 : 2;
}
它只是简单的每次把传入的迭代值增加 1 再去尝试从 table 中索引，如果没有值返回 nil 停止迭代。
pairs
pairs 迭代器会先尝试取元方法 __pairs，如果成功则调用元方法来获得值用于迭代。否则通过传入的迭代函数 luaB_next，迭代对象，迭代初始值 nil 来进行迭代:
static int pairsmeta (lua_State *L, const char *method, int iszero,
lua_CFunction iter) {
if (luaL_getmetafield(L, 1, method) == LUA_TNIL) { /* no metamethod? */
luaL_checktype(L, 1, LUA_TTABLE); /* argument must be a table */
lua_pushcfunction(L, iter); /* will return generator, */
lua_pushvalue(L, 1); /* state, */
if (iszero) lua_pushinteger(L, 0); /* and initial value */
else lua_pushnil(L);
}
else {
lua_pushvalue(L, 1); /* argument 'self' to metamethod */
lua_call(L, 1, 3); /* get 3 values from metamethod */
}
return 3;
}
static int luaB_pairs (lua_State *L) {
return pairsmeta(L, "__pairs", 0, luaB_next);
}
luaB_next 会压入两个参数给 API 函数 lua_next，被遍历的 table，以及即迭代值，如果没有传入迭代值则压入一个 nil 值作为初始值:
static int luaB_next (lua_State *L) {
luaL_checktype(L, 1, LUA_TTABLE);
lua_settop(L, 2); /* create a 2nd argument if there isn't one */
if (lua_next(L, 1))
return 2;
else {
lua_pushnil(L);
return 1;
}
}
lua_next 会从栈中从指定的 idx 取出被迭代的 table 对象，栈顶被用作迭代值来迭代下一个对象，迭代的核心实现在 table 模块中的 luaH_next。关于 lua_next 的用法可以参考 官方文档
// lapi.c
LUA_API int lua_next (lua_State *L, int idx) {
StkId t;
int more;
lua_lock(L);
t = index2addr(L, idx);
api_check(L, ttistable(t), "table expected");
more = luaH_next(L, hvalue(t), L->top - 1);
if (more) {
api_incr_top(L);
}
else /* no more elements */
L->top -= 1; /* remove key */
lua_unlock(L);
return more;
}
最终的迭代实现在 luaH_next 中:
int luaH_next (lua_State *L, Table *t, StkId key) {
unsigned int i = findindex(L, t, key); /* find original element */
for (; i < t->sizearray; i++) { /* try first array part */
if (!ttisnil(&t->array[i])) { /* a non-nil value? */
setivalue(key, i + 1);
setobj2s(L, key+1, &t->array[i]);
return 1;
}
}
for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
setobj2s(L, key, gkey(gnode(t, i)));
setobj2s(L, key+1, gval(gnode(t, i)));
return 1;
}
}
return 0; /* no more elements */
}
通过 findindex 获得 key 的一个整数表示的搜索位置：
1) 如果位于数组部分，则由搜索位置开始向后索引数组部分的值，查找到一个非 nil 的值则向 lua 栈中压入当前位置的键值对。
2) 如果位于哈希表部分，那么也是类似的，直接按照哈希表的节点顺序遍历每个哈希节点，直到找到一个非 nil 的节点。
一种可能的迭代顺序(这里并不是 i 的值)
实质上 findindex 是将数组部分和哈希表部分当作一个整体，来获得指定的 key 的索引:
/*
** returns the index of a 'key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signaled by 0.
*/
static unsigned int findindex (lua_State *L, Table *t, StkId key) {
unsigned int i;
if (ttisnil(key)) return 0; /* first iteration */
i = arrayindex(key);
if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
return i; /* yes; that's the index */
else {
int nx;
Node *n = mainposition(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
/* key may be dead already, but it is ok to use it in 'next' */
if (luaV_rawequalobj(gkey(n), key) ||
(ttisdeadkey(gkey(n)) && iscollectable(key) &&
deadvalue(gkey(n)) == gcvalue(key))) {
i = cast_int(n - gnode(t, 0)); /* key index in hash table */
/* hash elements are numbered after array ones */
return (i + 1) + t->sizearray;
}
nx = gnext(n);
if (nx == 0)
luaG_runerror(L, "invalid key to 'next'"); /* key not found */
else n += nx;
}
}
}
可以看成数组部分在前，哈希表部分在后的形式：
7.总结
1) 构造 table 时尽量使用构造语句以预分配空间:
local t = {1,2,3,4,5,6 ... }
但是对于会有大量的键的 table 来说只是为了避免几次小范围的 rehash 去这么做，有点不值得，特别是会提升代码维护成本。
2) 尽量避免连续的正整数键和其它键混用，考虑下列情况:
local t = {}
for i=1, 1024 do
t[i] = 0
end
for i=1, 1024 do
t[i] = nil
end
t["s"] = 0
将数组部分扩充至 1024 长度之后再全部置为 nil 后进行一次哈希插入，此时 rehash 会将数组部分全部回收。可使用断点 b ltable.c:346 if nasize < oldasize 观察。
但下列情况:
local t = {}
for i=1,1024 do
t[""..i] = 0
end
for i=1,1024 do
t[""..i] = nil
end
t[1] = 0
正整数键 1 会放入哈希部分 (luaH_get 检查到数组部分没有可用的空间，luaH_newkey 会放入哈希部分)。
结论：数组部分和哈希部分有空间不足的情况时会触发 rehash，但是如果其中有空闲空间比较多的情况，则会减少该部分的使用空间。如果数组空间不够时会先尝试放入哈希部分，如果哈希部分空间不够则才进行 rehash。