typedefstruct 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;
/*
** `module' operation for hashing (size is always a power of 2)
*/#define lmod(s,size) \
(check_exp((size&(size-1))==0, (cast(int, (s) & ((size)-1)))))
#define twoto(x) (1<<(x))
#define sizenode(t) (twoto((t)->lsizenode))
/*
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/static Node *mainposition (const Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TNUMBER:
return hashnum(t, nvalue(key));
case LUA_TSTRING:
return hashstr(t, rawtsvalue(key));
case LUA_TBOOLEAN:
return hashboolean(t, bvalue(key));
case LUA_TLIGHTUSERDATA:
return hashpointer(t, pvalue(key));
default:
return hashpointer(t, gcvalue(key));
}
}
Code Snippet 3:
ltable.c
针对不同类型详细来看，
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
#define hashstr(t,str) hashpow2(t, (str)->tsv.hash)
#define hashboolean(t,p) hashpow2(t, p)
/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/#define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
#define hashpointer(t,p) hashmod(t, IntPoint(p))
根据代码中的注释，dict 部分的实现 use a mix of chained scatter table with brent’s variation。
8
9
10
11
12
13
14
15
16
17
18
19
/*
** Implementation of tables (aka arrays, objects, or hash tables).
** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest `n' such that at
** least half the slots between 0 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the `original' position that its hash gives
** to it), then the colliding element is in its own main position.
** Hence even when the load factor reaches 100%, performance remains good.
*/
/*
** 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) {
Node *mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || mp == dummynode) {
Node *othern;
Node *n = getfreepos(t); /* get a free place */if (n == NULL) { /* cannot find a free place? */
rehash(L, t, key); /* grow table */return luaH_set(L, t, key); /* re-insert key into grown table */
}
lua_assert(n != dummynode);
othern = mainposition(t, key2tval(mp));
if (othern != mp) { /* is colliding node out of its main position? *//* yes; move colliding node into free position */while (gnext(othern) != mp) othern = gnext(othern); /* find previous */
gnext(othern) = n; /* redo the chain with `n' in place of `mp' */
*n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
gnext(mp) = NULL; /* now `mp' is free */
setnilvalue(gval(mp));
}
else { /* colliding node is in its own main position *//* new node will go into free position */
gnext(n) = gnext(mp); /* chain new position */
gnext(mp) = n;
mp = n;
}
}
gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
luaC_barriert(L, t, key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}
/*
** main search function
*/const TValue *luaH_get (Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TNIL: return luaO_nilobject;
case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
case LUA_TNUMBER: {
int k;
lua_Number n = nvalue(key);
lua_number2int(k, n);
if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */return luaH_getnum(t, k); /* use specialized version *//* else go through */
}
default: {
Node *n = mainposition(t, key);
do { /* check whether `key' is somewhere in the chain */if (luaO_rawequalObj(key2tval(n), key))
return gval(n); /* that's it */else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
}
Code Snippet 8:
ltable.c
核心就是先计算得到 main position，再一路通过 next 向下查找，
如果 k 匹配，就返回相应的 v；否则返回 nil。
/*
** main search function
*/const TValue *luaH_get (Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TNIL: return luaO_nilobject;
case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
case LUA_TNUMBER: {
int k;
lua_Number n = nvalue(key);
lua_number2int(k, n);
if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */return luaH_getnum(t, k); /* use specialized version *//* else go through */
}
default: {
Node *n = mainposition(t, key);
do { /* check whether `key' is somewhere in the chain */if (luaO_rawequalObj(key2tval(n), key))
return gval(n); /* that's it */else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
}
/*
** 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 signalled by -1.
*/staticintfindindex (lua_State *L, Table *t, StkId key) {
int i;
if (ttisnil(key)) return -1; /* first iteration */
i = arrayindex(key);
if (0 < i && i <= t->sizearray) /* is `key' inside array part? */return i-1; /* yes; that's the index (corrected to C) */else {
Node *n = mainposition(t, key);
do { /* check whether `key' is somewhere in the chain *//* key may be dead already, but it is ok to use it in `next' */if (luaO_rawequalObj(key2tval(n), key) ||
(ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) &&
gcvalue(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 + t->sizearray;
}
else n = gnext(n);
} while (n);
luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */return0; /* to avoid warnings */
}
}
intluaH_next (lua_State *L, Table *t, StkId key) {
int i = findindex(L, t, key); /* find original element */for (i++; i < t->sizearray; i++) { /* try first array part */if (!ttisnil(&t->array[i])) { /* a non-nil value? */
setnvalue(key, cast_num(i+1));
setobj2s(L, key+1, &t->array[i]);
return1;
}
}
for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
setobj2s(L, key, key2tval(gnode(t, i)));
setobj2s(L, key+1, gval(gnode(t, i)));
return1;
}
}
return0; /* no more elements */
}
Code Snippet 11:
ltable.c
luaH_next 输入的是 k，
首先，通过 findindex 找到 k 在 array/node 数组中的索引，
然后，将索引 i 自增， Line 164 for (i++, ...)
先遍历 array 部分，再遍历 node 部分，跳过所有 v 为 nil 的项
直到 array 和 node 遍历结束
值得注意的是， luaH_next 返回 0/1 说明是否已经遍历结束，方法内部将 k v 存储在栈上。
