Lua Source——Table

内容简介：Lua Source——Table

博文内容基于云风前辈的readinglua中对 lua 的源码讲解，本人对lua源码的理解尚浅，所以笔记部分主要是对思路的梳理，以及书中简单带过的地方加以自己的实践，从而加深自己的理解。文中有误的地方望读者指出，原书的pdf在系列文章的第一篇的末尾我也做了链接，有需要的人可以自己下载。

Lua的官方实现，把table的存储分为数组部分和哈希表部分。数组部分从1开始作整数数字索引，不能存储在数组部分的数据全部存放在哈希表中，唯一不能做哈希键值的是nil，这个限制可以帮助我们发现很多运行期错误。Lua哈希表有一个高效的实现，几乎可以认为操作哈希表的时间复杂度为O(l)。

这样分开的存储方案对于使用者来说是完全透明的，并没有强求Lua语言的实现一定要这样分开。但在lua的基础库中，提供了pairs和ipairs两个不同的api来实现两种不同方式的table遍历方案：用#对table取长度时，也被定义成和整数下标有关，而非整个table的尺寸。在Lua的C API中，有独立的api来操作数组的整数下标部分。也就是说，Lua有大量的特性，提供了对整数下标的高效访问途径。

/*
** Tables
*/

typedef union TKey {
  struct {
    TValuefields;
    struct Node *next;  /* for chaining */
  } nk;
  TValue tvk;
} TKey;


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


typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of `node' array */
  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;

/*
** `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))

Table的数组部分存储在TValue *array中，其长度信息存于int sizearray，哈希表存储于Node *node，哈希表的大小用lu_byte lsizenode表示，lsizenode表示的是幂次。

每个table结构，最多会由三块连续内存构成。一个Table结构，一块存放了连续整数索引的数组，和一块大小为2的整数次幂的哈希表。为了减少空表的维护成本，Lua在这里做了一点优化，它定义了一个不可改写的空哈希表：dummynode。让空表初始化时，node域指向这个dummy节点。它虽然是一个全局变量，但因为对其访问是只读的，所以不会引起线程安全问题。不当的链接lua库，有可能造成错误。如果你错误地链接了两份相同的Lua库到你的进程中，大多数情况下，代码可以安全的运行。但在清空table的时候，会因为无法正确地识别dummynode而导致程序崩溃。

#define dummynode        (&dummynode_)

#define isdummy(n)        ((n) == dummynode)

static const Node dummynode_ = {
  {NILCONSTANT},  /* value */
  {{NILCONSTANT, NULL}}  /* key */
};

luaH_new和luaH_free两个api的实现。

Table *luaH_new (lua_State *L) {
  Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h;
  t->metatable = NULL;
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0);
  return t;
}


void luaH_free (lua_State *L, Table *t) {
  if (!isdummy(t->node))
    luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
  luaM_freearray(L, t->array, t->sizearray);
  luaM_free(L, t);
}

内存管理部分使用了luaM的api，setnodevector用来初始化哈希表部分。

Table按照lua语言的定义，需要实现四中基本的操作：读、写、迭代和获取长度。lua中并没有删除操作，而仅仅是把对应键位的值设置为nil。

写操作被实现为查询已有键位，若不存在则创建新键。得到键位后，写入操作只是一次赋值。所以，在table模块中，实际实现的基本操作为：创建、查询、迭代和获取长度。

创建操作的api为luaH_newKey，阅读它的实现就能对整个table有一个全面的认识。它只负责在哈希表中创建出一个不存在的键，而不关数组部分的工作。因为table的数组部分操作和 C语言 数组没有什么不同，不需要特殊处理。

/*
** 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.
*/
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
  Node *mp;
  if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  else if (ttisnumber(key) && luai_numisnan(L, nvalue(key)))
    luaG_runerror(L, "table index is NaN");
  mp = mainposition(t, key);
  if (!ttisnil(gval(mp)) || isdummy(mp)) {  /* main position is taken? */
    Node *othern;
    Node *n = getfreepos(t);  /* get a free place */
    if (n == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /* grow table */
      /* whatever called 'newkey' take care of TM cache and GC barrier */
      return luaH_set(L, t, key);  /* insert key into grown table */
    }
    lua_assert(!isdummy(n));
    othern = mainposition(t, gkey(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;
    }
  }
  setobj2t(L, gkey(mp), key);
  luaC_barrierback(L, obj2gco(t), key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

lua哈希表以闭散列的方式实现，每个可能的键值，在哈希表都有一个主要位置，称为mainposition。创建一个新键时，会检查mainposition，若无人使用，则可以直接设置为这个新键。若之前有其他键占据了这个位置，则检查占据此位置的键的主位置是不是这里。若两者位置冲突，则利用Node结构中的next域，以一个单向链表的形式把它们链起来；否则，新键占据这个位置，而老键更换到新位置并根据它的主键找到属于它的链的那条单向链表中上一个结点，重新链入。

无论是哪种冲突情况，都需要在哈希表中找到一个空闲可用的结点。 这里是在 getfreepos 函数中，递减 lastfree 域来实现的。 lua 也不会在设置键位的值为 nil 时而回收空间，而是在预先准备好的哈希空间使用完 后惰性回收。 即在 lastfree 递减到哈希空间头时，做一次 rehash 操作。

static void rehash (lua_State *L, Table *t, const TValue *ek) {
  int nasize, na;
  int nums[MAXBITS+1];  /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */
  int i;
  int totaluse;
  for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */
  nasize = numusearray(t, nums);  /* count keys in array part */
  totaluse = nasize;  /* all those keys are integer keys */
  totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
  /* count extra key */
  nasize += countint(ek, nums);
  totaluse++;
  /* compute new size for array part */
  na = computesizes(nums, &nasize);
  /* resize the table to new computed sizes */
  luaH_resize(L, t, nasize, totaluse - na);
}

rehash 的主要工作是统计当前 table 中到底有多少有效键值对，以及决定数组部分需要开辟多少空间。其原则是最终数组部分的利用率需要超过 50% 。

lua 使用一个 rehash 函数中定义在栈上的 nums 数组来做这个整数键统计工作。 这个数组按 2 的整数幂次来分开统计各个区段间的整数键个数。 统计过程的实现见 numusearray 和 numusehash 函数。

最终，computesizes 函数计算出不低于 50% 利用率下，数组该维持多少空间。同时，还可以得到有多少有效键将被储存在哈希表里。

根据这些统计数据，rehash 函数调用 luaH_resize 这个 api 来重新调整数组部分和哈希部分的大小，并 把不能放在数组里的键值对重新塞入哈希表。

查询操作 luaH_get 的实现要简单的多。当查询键为整数键且在数组范围内时，在数组部分查询；否则，根据键的哈希值去哈希表中查询。 拥有相同哈希值的冲突键值对，在哈希表中由 Node 的 next 域单向链起来，所以遍历这个链表就可以了。

以短字符串为键相当常见，lua 对此做了一点优化。做内部唯一化处理。 相同的短字符串在同一个 State 中只会存在一份。长字符串并不做内部唯一化，且其哈希值也是惰性计算的。在 mainposition 函数 中的 101-106 行可以看到这段惰性计算的代码。

/*
** 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_TLNGSTR: {
      TString *s = rawtsvalue(key);
      if (s->tsv.extra == 0) {  /* no hash? */
        s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash);
        s->tsv.extra = 1;  /* now it has its hash */
      }
      return hashstr(t, rawtsvalue(key));
    }
    case LUA_TSHRSTR:
      return hashstr(t, rawtsvalue(key));
    case LUA_TBOOLEAN:
      return hashboolean(t, bvalue(key));
    case LUA_TLIGHTUSERDATA:
      return hashpointer(t, pvalue(key));
    case LUA_TLCF:
      return hashpointer(t, fvalue(key));
    default:
      return hashpointer(t, gcvalue(key));
  }
}

以上所述就是小编给大家介绍的《Lua Source——Table》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• Lua Source——Table

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。