Lua表的实现

Lua最强大的数据结构就是它的表，那么它是如何实现的呢？ [cpp] 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; [/cpp] 这个是Lua表的定义,其中 lszienode 表示表所分配内存的长度，为2的n次方 array 为表的数组部分,真的是一个数组，长度也为2的n次方 node 为表的哈希表部分，也是一个数组 lastfree 用于指向表中目前为空的部分（实际free为它的地址减一） gclist 用于Lua的GC sizearry 数组部分大小

接下来分析下Lua是如何对表进行管理的： 首先，在定义表的时候，也就是执行虚指令 NEWTABLE的时候，Lua会根据传入的参数预先申请好表的内存，然后将它们全部置为nil。 然后，接下来再往Lua的表填充数据，也就是调用虚指令 SETTABLE，会执行到luaV_settable里，核心代码如下 [cpp] Table *h = hvalue(t); TValue *oldval = luaH_set(L, h, key); /* do a primitive set */ if (!ttisnil(oldval) /* result is no nil? */ (tm = fasttm(L, h->metatable, TM_NEWINDEX)) == NULL) { /* or no TM? */ setobj2t(L, oldval, val); luaC_barriert(L, h, val); return; } [/cpp] luaH_set 这个函数之前分析过了（用于取到Key对应的那个TValue），取到TValue之后将我们要的Vaule赋值进去。那么luaH_set 内部究竟干了什么呢？继续往里看 [cpp] TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { const TValue *p = luaH_get(t, key); t->flags = 0; if (p != luaO_nilobject) return cast(TValue *, p); else { if (ttisnil(key)) luaG_runerror(L, “table index is nil”); else if (ttisnumber(key) && luai_numisnan(nvalue(key))) luaG_runerror(L, “table index is NaN”); return newkey(L, t, key); } } [/cpp] 先找到这个key对应的TValue，然后将它与nil进行比对，如果不是nil（说明之前被赋过值）那么就返回这个TValue，否则执行newkey [cpp] 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); } [/cpp] 依然是先查找Key在表中的位置，如果找到了则将其赋值给返回的指针，并将其返回，否则先查找表中是否还有空闲的内存，如果没有则将表重新哈希一次（数组部分，哈希表部分均会执行一次该操作，但内部会计算重新分配后的大小以便决定哪些部分需要重新申请内存），然后继续执行一次这个函数。如果找到了，则对key进行hash一次，解决hash冲突后并存储。（如何解决，暂没看） 继续看表内部是如何重新分配内存的，代码实现略多，大概就是会根据现有的内存需求分配一个2的n次方大小的内存（类似于STL的Vector）（比如需要1个内存，它会分配给你1个，需要2个，它会分配给你2个，但如果需要3个，分配的就不是3个而是4个了，以此类推，如果需要9个，分配的就会是16个）。然后将原有的所有元素重新哈希一次填入新的内存中，再释放掉原有的内存。 举个例子： local a={} a.x = 1 a.y = 1 我们先看看Lua是怎么解释这几句的，用Lua编译器编译结果看看虚指令： 1 [1] NEWTABLE 0 0 0 2 [2] SETTABLE 0 -1 -2 ; “x” 1 3 [3] SETTABLE 0 -3 -2 ; “y” 1 4 [3] RETURN 0 1 于是我们可以开始追踪表的内存分配情况： 1 [1] NEWTABLE 0 0 0 –预分配空间0，只建立一个表，并不会去申请内存 2 [2] SETTABLE 0 -1 -2 ; “x” 1 –重新哈希一次，分配一个大小为1的内存 3 [3] SETTABLE 0 -3 -2 ; “y” 1 –重新哈希一次，再分配一个大小为2的内存块 4 [3] RETURN 0 1 –返回 可以看出这种写法会导致Lua内部进行了2次哈希和重新分配内存，是很浪费资源的一种写法。 优化的写法： local a={x=1, y=1} 让我们看看这次编译结果： 1 [1] NEWTABLE 0 0 2 2 [1] SETTABLE 0 -1 -2 ; “x” 1 3 [1] SETTABLE 0 -3 -2 ; “y” 1 4 [1] RETURN 0 1 初看似乎差不多，仔细看： 1 [1] NEWTABLE 0 0 2 –这里会一次性就分配个这个表大小为2的预留空间 所以在接下来的2,3的时候就不用再重新申请内存分配了，可以看出来这样可以少一次内存分配，如果表更大一点，可以节省的次数更明显^_^ 看到这里，大概就明白了如何初始化一个Lua的表可以效率更高。