Table内部实现

Table 结构定义

Lua 的Table是由数组、哈希表一起实现的。

所以如果不清楚哈希表，建议先看看哈希表。 http://mdgsf.github.io/c/2016/07/01/c-hashtable.html

typedef unsigned char lu_byte;
typedef struct Table {

CommonHeader;

lu_byte flags;  /* 1<<p means tagmethod(p) is not present /

lu_byte lsizenode;  / log2 of size of 'node' 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;

TValue *array; 是数组

unsigned int sizearray; 是数组的大小

Node *node; 应该就是哈希表了。

lu_byte lsizenode; 如果哈希表的容量为Size，那么lsizenode = log2(Size)

其他的成员变量暂时不关心。 等等主要看下 TValue 和 Node 的结构体。

Table *luaH_new (lua_State *L) {
  GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table)); //其实就是分配一款内存空间
  Table *t = gco2t(o); //把指针类型转换为Table类型。
  t->metatable = NULL; //接下来的都是一些初始化的操作。
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0);
  return t;
}
static void setnodevector (lua_State L, Table t, unsigned int size) {

if (size == 0) {  /* no elements to hash part? /

t->node = cast(Node , dummynode);  /* use common 'dummynode' /

t->lsizenode = 0;

t->lastfree = NULL;  / signal that it is using dummy node */

}

else {

… //这里我们暂时不关心，就先不看。

}

}

#define cast(t, exp) ((t)(exp))   //类型转换，把表达式exp转换为t类型。

#define twoto(x) (1<<(x)) //计算2^x

#define sizenode(t) (twoto((t)->lsizenode)) //计算2^(t->lsizenode)的大小

void luaH_free (lua_State *L, Table *t) {
  if (!isdummy(t))
    luaM_freearray(L, t->node, cast(size_t, sizenode(t))); //释放哈希表的空间，大小为2^(t->lsizenode)
  luaM_freearray(L, t->array, t->sizearray); //释放数组的空间，大小为t->sizearray
  luaM_free(L, t); //释放Table的内存空间
}

Node TKey TValue

可以看到，数组是用TValue来保存值的，而哈希表是使用Node来保存值。

TValue *array; 是数组

Node *node; 应该就是哈希表了。

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

typedef union TKey {
  struct {
    TValuefields;
    int next;  /* for chaining (offset for next node) */
  } nk;
  TValue tvk;
} TKey;

/*
** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/
/*

** Union of all Lua values

/

typedef union Value {

GCObject gc;    /* collectable objects /

void p;         /* light userdata /

int b;           / booleans /

lua_CFunction f; / light C functions /

lua_Integer i;   / integer numbers /

lua_Number n;    / float numbers */

} Value;
#define TValuefields Value value_; int tt_



typedef struct lua_TValue {

TValuefields;

} TValue;

其实 TKey 和 TValue 是同一个东西，只不过TKey里面多了一个next，主要是哈希表出现冲突时，用来解决冲突用的。

TKey中tvk是这个key的值，nk中的next则指向key冲突的下一个节点。lua的hash表的hash算法比较特别，一般的hash表都是根据key算出hash(key)，然后把这个key放在hash表的hash(key)位置上，如果有冲突的话，就放在hash(key)位置的链表上。

但是lua的hash表中，如果有冲突的话，lua会找hash表中一个空的位置（从后往前找，假设为x），然后把新的key放在这个空的位置x上，并且让hash表中hash(key)处的节点的nk.next指向x。这个意思就是，假如有冲突的话，不用重新分配空间来存储冲突的key，而是利用hash表上未用过的空格来存储。但是这样会引入另外一个问题，本来key是不应该放在x的，假设有另外一个key2，hash(key2)算出来的位置也在x的话，那就表示本来x这个位置应该是给key2的，但是由于x被key占用了，导致key2没地方放了。这时候lua的处理方式是把key放到另外一个空格，然后让key2占回x。当hash表已经没有空格的时候，lua就会resize这个hash表。这样做的好处主要是不用动态申请内存空间，hash表初始化的时候有多少内存空间就用多少，不够就resize这个hash表。

http://blog.csdn.net/u012611878/article/details/51873648

冲突解决技术可以分为两类：开散列方法( open hashing，也称为拉链法，separate chaining )和闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。

Lua这里使用的是闭散列。

增删查改

LUAI_DDEC const TValue luaO_nilobject_;
#define luaO_nilobject (&luaO_nilobject_) //这是一个空对象，这样的好处是可以不需要处理NULL指针，在<<代码整洁之道>>里面有说。

TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  const TValue *p = luaH_get(t, key); //应该是到Table中去查找key是不是存在。
  if (p != luaO_nilobject)
    return cast(TValue *, p); //如果存在，直接返回对应的TValue
  else return luaH_newkey(L, t, key); //如果不存在，则创建一个新的TValue，再返回。
}

很明显，上面有两个重要的函数 luaH_newkey 和 luaH_get。

luaH_newkey 应该就是插入函数了，向Table内插入一个新的值。

luaH_get 则是查找函数，在Table中查找对应的key是不是存在。

luaH_newkey

/*
** 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.
*/
/*
插入一个新的key到Table中。首先，检查key的main position是不是空的，main position 就是key要插入的位置吧。
if(main position != 空)
{
    检查冲突节点的main position是不是在它自己的位置上。
    if(冲突节点不是在它自己的位置上)
    {
        把冲突节点移动到一个空的位置上。
        把新的key放在它自己的main position上。
    }
    else
    {
        把新的key放到一个空的位置上。
    }
}
else //main position == 空
{
    把新的key放在它自己的main position上。
}
*/
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)) {  /* does index fit in an integer? */
      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);  ------------------------------------------//通过key可以获取到Table中的一个位置mp，哈希函数就在mainposition()这函数里面。
  if (!ttisnil(gval(mp)) || isdummy(t)) {  /* 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(t));
    othern = mainposition(t, gkey(mp));  ---------------------------------//获取冲突节点的main position。
    if (othern != mp) {  /* is colliding node out of its main position? */
      /* yes; move colliding node 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 node 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 node is in its own main position */
      /* new node 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);  -------------------------------------//发生冲突时，next保存的是两个指针的差值，也就是当前节点到下一个节点在内存中的距离。
      mp = f;
    }
  }
  setnodekey(L, &mp->i_key, key);
  luaC_barrierback(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}
//这里是上面用到的一些宏

#define gnode(t,i) (&(t)->node[i])

#define gnext(n) ((n)->i_key.nk.next)

#define gkey(n) cast(const TValue*, (&(n)->i_key.tvk))  //获取Node的key

#define gval(n) (&(n)->i_val)  //获取Node的value



/* type casts (a macro highlights casts in the code) */

#define cast(t, exp) ((t)(exp))

#define cast_int(i) cast(int, (i)) //转换为整形



#define isdummy(t) ((t)->lastfree == NULL)



#define LUA_TNIL 0

#define rttype(o) ((o)->tt_)

#define checktag(o,t) (rttype(o) == (t))

#define ttisnil(o) checktag((o), LUA_TNIL)

在这个函数里面，用到了3个函数：getfreepos，mainposition，rehash。我们需要看看到底是怎么实现的。

getfreepos: 获取一个空的位置。

rehash: 重新分配Table的内存空间。

mainposition: 根据key值，通过哈希函数算出在Table中的main position。

getfreepos

static Node *getfreepos (Table *t) {
  if (!isdummy(t)) {
    while (t->lastfree > t->node) {
      t->lastfree--; //这里再不断的向前遍历
      if (ttisnil(gkey(t->lastfree)))
        return t->lastfree;
    }
  }
  return NULL;  /* could not find a free place */
}

看来Table 中的 lastfree 这个变量是用来保存最后一个空闲位置的指针。

rehash

/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
/*
na: Table中数组中的元素个数 和 哈希表中可以放到数组中去的元素的个数 的总和。
totaluse: Table中所有元素的个数，包括数组和哈希表。
*/
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);
}

/*
** Count keys in array part of table 't': Fill 'nums[i]' with
** number of keys that will go into corresponding slice and return
** total number of non-nil keys.
*/
/*
@brief 这个函数是用来计算Table中的数组部分的信息的。
@param t[in]: Table。
@param nums[out]: 这个数组的大小是32。
    nums[0]: array[0]
    nums[1]: array[1 - 2]
    nums[2]: array[2 - 4]
    nums[3]: arr