近日配置了下终端下的 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。