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