Lua中table类型的源码实现

? 1、概述
? ? table是lua中唯一的表示数据结构的工具。它可以用于实现数据容器、函数环境（Env）、元表（metatable）、模块（module）和注册表（registery）等其他各种用途。因此了解table的实现是非常有必要的，根据《Lua中数据类型的源码实现》中知道，在Lua中，table是由结构体体Table来实现的。下面将以Lua 5.2.1的源码来看table的实现。
? 2、实现原理
? ? 在Lua5.0以后，table是以一种混合型数据结构来实现的，它包含一个哈希表部分和一个数组部分，比如下面操作的构造table：

local t = {100}
t[2] = 200
table.insert(t,300)
t.x = 9.2
print(t[1],t[2],t[3],t.x)

其可能的实现方式如下图：

注意数组部分不需要保存键值，只要在底层实现时才考虑这种区别，其他情况，即使对虚拟机来说，访问表项也是由底层自动统一的，因为使用的时候无须考虑这种差别。在往表中插入数值时，表会根据key-value的值和表当前的数据内容自动动态地使用这个两个部分：数据部分试图保存所有key值介于1和某个上限n之间的值，非整数key和超过数据范围n的整数key对应的值将存入哈希表部分。
对于数组部分，要求的数组的大小同时满足：1到n之间至少一半的空间被利用（避免像稀疏数组一样浪费空间）；并且n/2+1到n之间的空间至少有一个空间被利用（避免n/2个空间就能容纳所有数据时申请了n个空间浪费）。
对于哈希部分，解决冲突的方式是用开放寻址法（open addressing），即所有的元素都存在哈希表中，使用这种方法往往可以让Hash表内数据更紧凑，有更高效的空间利用率,并且在用这个方法时还做了改进，下面将通过源代码具体分析。
? 3、源码实现
? ?首先来看对应的数据结构Table，其源码如下（lobject.h）：

105 #define TValuefields    Value value_; int tt_ 
544 /*
545 ** Tables 
546 */
547   
548 typedef union TKey {
549   struct { 
550     TValuefields;
551     struct Node *next;  /* for chaining */
552   } nk;
553   TValue tvk;
554 } TKey;
555 
556 
557 typedef struct Node {
558   TValue i_val;
559   TKey i_key;
560 } Node;
561 
562 
563 typedef struct Table {
564   CommonHeader;
565   lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
566   lu_byte lsizenode;  /* log2 of size of `node' array */
567   struct Table *metatable;
568   TValue *array;  /* array part */
569   Node *node;
570   Node *lastfree;  /* any free position is before this position */
571   GCObject *gclist;
572   int sizearray;  /* size of `array' array */
573 } Table;

? Table结构的头CommonHeader与TString中是一样的，用于GC，实质上所有GC类型的头上相同的，都包含这个宏。
? ?成员TValue *array就是Table的数组部分，TValue表示Lua数据类型通用实现，再前面文章已经分析过。成员int sizearray指明了这个数组的大小。
? ?成员Node *node就是Table的哈希表部分，其大小保存在成员lu_byte lsizenode中，注意保存的是哈希表大小的幂次，而不是实质大小。比如哈希表的大小为2^n，则lsizenode中保存的值是n，同时也说明哈希表的长度只能是2的幂次。
? ?结构体Node中包含两个成员i_key和i_val，很显然分别表示key、value，其中value的数据类型就是通用的Lua数据类型TValue；key的数据类型是联合体，除了通常存储数据外，key还有一个作用是保存Node中next指针，也就是说key除了能保存TValue的数据结构外，还多了一个next指针，这个next指针就是用作同一个hash值下冲突时的链表指针。成员Node *lastfree就是链表的最后一个空元素。
? ?成员struct Table *metatable是元表的指针，每个table的元表也是一个table。lu_byte flags用于元表元方法的一些优化手段，一共有8位用于标记是否没有某个元方法，初始值都是有的。成员GCObject *gclist用于GC。下面是创建一个表的接口，代码如下（ltable.c）：

368 Table *luaH_new (lua_State *L) {
369   Table *t = &luaC_newobj(L,LUA_TTABLE,sizeof(Table),NULL,0)->h;
370   t->metatable = NULL;
371   t->flags = cast_byte(~0);
372   t->array = NULL;
373   t->sizearray = 0;
374   setnodevector(L,t,0);
375   return t;
376 }

其中函数luaC_newobj（lgc.c中定义）用来创建一个新的可回收对象，并把创建的对象放到GC的链表中。lua中所有的可回收对象都是调用这个接口来创建的，方便后面GC回收。其中setnodevector用来初始化table的哈希表部分，初始值哈希表大小为1，并且node指向一个静态全局变量dummynode_，而不是NULL，这样做的目的是减少操作表时的判断操作。

? I、查找? ?

? ?首先来看怎么在table中查找一个值，即t[key]操作时所发生的，代码如下（ltable.c）：

478 /*                                                                                                 
479 ** main search function                                                                            
480 */                                                                                                 
481 const TValue *luaH_get (Table *t,const TValue *key) {                                             
482   switch (ttype(key)) {                                                                            
483     case LUA_TNIL: return luaO_nilobject;                                                          
484     case LUA_TSHRSTR: return luaH_getstr(t,rawtsvalue(key));                                      
485     case LUA_TNUMBER: {                                                                            
486       int k;                                                                                       
487       lua_Number n = nvalue(key);                                                                  
488       lua_number2int(k,n);                                                                        
489       if (luai_numeq(cast_num(k),nvalue(key))) /* index is int? */                                
490         return luaH_getint(t,k);  /* use specialized version */                                   
491       /* else go through */                                                                        
492     }                                                                                              
493     default: {                                                                                     
494       Node *n = mainposition(t,key);                                                              
495       do {  /* check whether `key' is somewhere in the chain */                                    
496         if (luaV_rawequalobj(gkey(n),key))                                                        
497           return gval(n);  /* that's it */                                                         
498         else n = gnext(n);                                                                         
499       } while (n);                                                                                 
500       return luaO_nilobject;                                                                       
501     }                                                                                              
502   }                                                                                                
503 }  

从代码可以看出查找的步骤是：
? ?（1）若key是一个nil的类型，则返回nil值，即print(t[nil])，打印的值是nil。
? ?（2）若key是一个短字符串类型LUA_TSHRSTR，则调用函数luaH_getstr来查找。其代码如下（ltable.c）：

463 /*
464 ** search function for short strings
465 */
466 const TValue *luaH_getstr (Table *t,TString *key) {                                               
467   Node *n = hashstr(t,key);                                                                       
468   lua_assert(key->tsv.tt == LUA_TSHRSTR);                                                          
469   do {  /* check whether `key' is somewhere in the chain */                                        
470     if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)),key))                              
471       return gval(n);  /* that's it */                                                             
472     else n = gnext(n);                                                                             
473   } while (n);                                                                                     
474   return luaO_nilobject;                                                                           
475 }     

该函数首先获得相应字符串在哈希表中的链表（使用字符串的值对哈希表取余来确定在node数组中位置的），遍历这个链表，查找字符串。主要对短字符串比较，不用逐个字符去比较，只需要比较地址，因为对整个lua虚拟机来说，短字符串只有一份。若找到了，则返回相应的值，否则返回nil。
? ?（3）若key是一个数字类型LUA_TNUMBER并且是一个int类型，则调用luaH_getint函数去查找。代码如下（ltable.c）：

443 /*
444 ** search function for integers                                                                    
445 */
446 const TValue *luaH_getint (Table *t,int key) {                                                    
447   /* (1 <= key && key <= t->sizearray) */                                                          
448   if (cast(unsigned int,key-1) < cast(unsigned int,t->sizearray))                                
449     return &t->array[key-1];
450   else {
451     lua_Number nk = cast_num(key);                                                                 
452     Node *n = hashnum(t,nk);                                                                      
453     do {  /* check whether `key' is somewhere in the chain */                                      
454       if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)),nk))                                  
455         return gval(n);  /* that's it */                                                           
456       else n = gnext(n);                                                                           
457     } while (n);                                                                                   
458     return luaO_nilobject;                                                                         
459   }
460 }

如果key的值小于等于数组大小，则直接返回相应的值，否则去哈希表中去查找。
? ?（4）对应其他类型，也就是不是nil、整型和短字符串类型，都是计算hash值，然后在链表中去查找（因为拥有相同哈希值的冲突键值对，在哈希表中由Node的next成员链接起来了）。因此，对应长字符串来说，会逐个字符去比较的。这个可以在lvm.c的luaV_equalobj_函数中可以看到各种数据类型比较的方法。
? II、赋值
? ?当给table执行赋值操作时，比如t[“key”] = 1，会调用函数luaH_set，其代码如下（ltable.c）：

510 TValue *luaH_set (lua_State *L,Table *t,const TValue *key) {
511   const TValue *p = luaH_get(t,key);
512   if (p != luaO_nilobject) 
513     return cast(TValue *,p);
514   else return luaH_newkey(L,key);
515 }

它首先查找key是否在table中，若在，则直接替换原来的值，否则调用luaH_newkey，插入新的（key,value）。忘table中插入新的值，其基本思路是检测key的主位置（main position）是否为空，这里主位置就是key的哈希值在node数组中（哈希表）的位置。若主位置为空，则直接把相应的（key,value）插入到这个node中。若主位置被占了，检查占领该位置的（key,value）的主位置是不是在这个地方，若不在这个地方，则移动占领该位置的（key,value）到一个新的空node中，并且把要插入的（key,value）插入到相应的主位置；若在这个地方（即占领该位置的（key,value）的主位置就是要插入的位置），则把要插入的（key,value）插入到一个新的空node中。
函数luaH_newkey代码如下（ltable.c）：

399 ** inserts a new key into a hash table; first,check whether key's main
400 ** position is free. If not,check whether colliding node is in its main
401 ** position or not: if it is not,move colliding node to an empty place and
402 ** put new key in its main position; otherwise (colliding node is in its main
403 ** position),new key goes to an empty position.
404 */
405 TValue *luaH_newkey (lua_State *L,const TValue *key) {
406   Node *mp;
407   if (ttisnil(key)) luaG_runerror(L,"table index is nil");
408   else if (ttisnumber(key) && luai_numisnan(L,nvalue(key)))
409     luaG_runerror(L,"table index is NaN");
410   mp = mainposition(t,key);
411   if (!ttisnil(gval(mp)) || isdummy(mp)) {  /* main position is taken? */
412     Node *othern;
413     Node *n = getfreepos(t);  /* get a free place */
414     if (n == NULL) {  /* cannot find a free place? */
415       rehash(L,key);  /* grow table */
416       /* whatever called 'newkey' take care of TM cache and GC barrier */
417       return luaH_set(L,key);  /* insert key into grown table */
418     }
419     lua_assert(!isdummy(n));
420     othern = mainposition(t,gkey(mp));
421     if (othern != mp) {  /* is colliding node out of its main position? */
422       /* yes; move colliding node into free position */
423       while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
424       gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
425       *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
426       gnext(mp) = NULL;  /* now `mp' is free */
427       setnilvalue(gval(mp));
428     } 
429     else {  /* colliding node is in its own main position */
430       /* new node will go into free position */
431       gnext(n) = gnext(mp);  /* chain new position */
432       gnext(mp) = n;
433       mp = n;
434     }
435   }
436   setobj2t(L,gkey(mp),key);
437   luaC_barrierback(L,obj2gco(t),key);
438   lua_assert(ttisnil(gval(mp)));
439   return gval(mp);
440 }

上面的函数的执行过程如下：
? ?（1）首先检查key值是否合法，若是nil或是NaN，则直接报错返回。
? ?（2）调用函数mainposition获取key在table的主位置，也就是key在table中的hash值。
若主位置被占有了，则调用getfreepos函数，获取空的位置，函数代码如下（ltable.c）：

387 static Node *getfreepos (Table *t) {
388   while (t->lastfree > t->node) {
389     t->lastfree--;
390     if (ttisnil(gkey(t->lastfree)))
391       return t->lastfree;
392   }
393   return NULL;  /* could not find a free place */
394 }

它从lastfree处开始查找，查找第一个空的位置，其中成员lastfree保存的是哈希表中最后一个空的位置。因此它依次往前查找。
? ?（3）若没找到空的位置，则调用函数rehash，增加或减少哈希表的大小找出新位置，然后再调用luaH_set把要插入的（key,value）到新的哈希表中，直接返回LuaH_set的结果。也就是说lua不会在设置键位的值为nil时而回收空间，而是在预先准备好的哈希空间使用完后，才会调用rehash，回收那些值为nil的空间。其中rehash函数代码如下（ltable.c）:

343 static void rehash (lua_State *L,const TValue *ek) {                                    
344   int nasize,na;
345   int nums[MAXBITS+1];  /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */                     
346   int i;
347   int totaluse;                                                                                    
348   for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */                                      
349   nasize = numusearray(t,nums);  /* count keys in array part */                                   
350   totaluse = nasize;  /* all those keys are integer keys */
351   totaluse += numusehash(t,nums,&nasize);  /* count keys in hash part */                         
352   /* count extra key */
353   nasize += countint(ek,nums);
354   totaluse++;
355   /* compute new size for array part */
356   na = computesizes(nums,&nasize);                                                                
357   /* resize the table to new computed sizes */                                                     
358   luaH_resize(L,nasize,totaluse - na);
359 }

? ?rehash首先统计当前table中到底有value值不是nil的键值对的个数，然后根据这个数值确定table中数组部分的大小（其大小保证数组部分的空间利用率必须50%），最后调用luaH_resize函数来重建table。
? ?具体过程是首先调用函数numusearray计算table中数组部分非nil的数值的个数，然后调用numusehash函数计算table中哈希部分的非nil的键值对的个数。调用countint函数来确定将要插入的（key,value）是否可以放在数组部分，接着调用computesizes来计算新的table数组部分的大小，最后调用luaH_resize函数根据原来table中数据构建新的table。
? ?（4）若能得到空的位置，则调用mainposition函数，获取被占的位置相应的key的主位置。若将要插入的（key,value）和当前被占用的位置key的主位置相同，则把要插入的（key,value）放到前面的空的位置，并把他们连接到相应的主位置链表中；若将要插入的（key,value）和当前被占用的位置key的主位置不同，则移动这个占有位置的（key,value）到一个前面找到的空位置，并把要插入的（key,value）放到主位置。
? III、迭代
? ?在Lua中提供了函数next来迭代lua中键值对，即用next(t)或next(t,key)返回下一个键值对。这是在函数luaH_next中来实现的。代码如下（ltable.c）：

169 int luaH_next (lua_State *L,StkId key) {
170   int i = findindex(L,key);  /* find original element */
171   for (i++; i < t->sizearray; i++) {  /* try first array part */
172     if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
173       setnvalue(key,cast_num(i+1));
174       setobj2s(L,key+1,&t->array[i]);
175       return 1;
176     }
177   }
178   for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
179     if (!ttisnil(gval(gnode(t,i)))) {  /* a non-nil value? */
180       setobj2s(L,key,gkey(gnode(t,i)));
181       setobj2s(L,gval(gnode(t,i)));
182       return 1;
183     }
184   }
185   return 0;  /* no more elements */
186 }

首先调用findindex获得开始检索的位置（比如，通常从等于key的位置开始查找），然后因此查找table中的数组部分和哈希部分的第一个非nil的位置。??

? 4、总结? ?

? ?（1）在对table操作时，尽量不要触发rehash操作，因为这个开销是非常大的。在对table插入新的键值对时（也就是说key原来不在table中），可能会触发rehash操作，而直接修改已存在key对于的值，不会触发rehash操作的，包括赋值为nil。

? （2）在遍历一个table时，不允许向table插入一个新键，否则将无法预测后续的遍历行为，但lua允许在遍历过程中，修改table中已存在的键对应的值，包括修改后的值为nil，也是允许的。

? （3）table中要想删除一个元素等同于向对应key赋值为nil，等待垃圾回收。但是删除table一个元素时候，并不会触发表重构行为，即不会触发rehash操作。

? （4）为了减少rehash操作，当构造一个数组时，如果预先知道其大小，可以预分配数组大小。在脚本层可以使用local t = {nil,nil,nil}来预分配数组大小。在C语言层，可以使用接口void lua_createtable (lua_State *L,int narr,int nrec);来预分配数组大小。

? （5）注意在使用长度操作符#对数组其长度时，数组不应该包含nil值，否则很容易出错。比如：

print(#{1,nil})  --1
print(#{1,1}) --3
print(#{1,1,nil}) --1

参考资料

Lua 5.2.1源码 http://blog.aliyun.com/787 Lua数据结构 — Table（三） http://www.codingnow.com/temp/readinglua.pdf 《Lua源码欣赏》（云风）