lua table 源码阅读

近日配置了下终端下的 vim 插件,把 c 相关的开发插件都弄的勉强可以用了,为了熟悉下 GDB 的一些基本操作,就拿读 lua 部分源代码来练手了。

这里所有的内容均基于 lua 5.3 版本。

table 的内部操作定义于文件 ltable.h / ltable.c 中,有以下相关的函数构成

  • luaH_new : 构造一个新的 table

初始化

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

首先由 lua gc 模块分配一个被托管的垃圾回收对象 GCObject *o, 然后转为一个指向实际的 table 结构的 Table *t 进行初始化操作。

一个 lua table 被分为两个部分:数组部分和哈希表部分。

数组部分的初始化比较粗暴,直接置零。

t->array = NULL;
t->sizearray = 0;

则哈希表的部分由 setnodevector 函数来初始化,由于传入的特殊表大小 0,哈希表部分被指向一个 所有哈希部分为空的 table 所共享的一个静态变量 dummynode (此处为一个宏)

static void setnodevector (lua_State *L, Table *t, unsigned int size) {
  int lsize;
  if (size == 0) {  /* no elements to hash part? */
    t->node = cast(Node *, dummynode);  /* use hashnode 'dummynode' */
    lsize = 0;
  }
  else {
  ....

struct Table

再回头来看看 Table 的结构:

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

数组部分用到了字段 sizearray, array
哈希表部分用到了字段 node, lastfree, lsizenode

lsizenode 比较特殊,它存储的不是哈希表部分的真实大小,而是存储了真实大小的2的整数次幂 2^lsizenode,也就是说哈希表部分的大小永远是2的整数次幂。

对于一个空的 table 来说,它会是这样的结构:

需要注意的是:为了简便, lastfree 画出的是指向最后一个可用的节点,实际上指针指向的是最后一个可用节点的下一个位置。

数组插入

测试代码

local t = {}; for i=1, 3 do t[i] = 123456 end

其 lua 字节码含义为:

0+ params, 5 slots, 1 upvalue, 5 locals, 3 constants, 0 functions
    1       [2]     NEWTABLE        0 0 0
    2       [2]     LOADK           1 -1    ; 1
    3       [2]     LOADK           2 -2    ; 10
    4       [2]     LOADK           3 -1    ; 1
    5       [2]     FORPREP         1 1     ; to 7
    6       [2]     SETTABLE        0 4 -3  ; - 123456
    7       [2]     FORLOOP         1 -2    ; to 6
    8       [2]     RETURN          0 1

可以在 lvm.c luaV_execute 中的下列分之中打上断点进行观察,对于 GDB 可以使用条件断点 b lvm.c:864 if rc->value_.i == 123456 来调试。

vmcase(OP_SETTABLE) {
    TValue *rb = RKB(i);
    TValue *rc = RKC(i);
    settableProtected(L, ra, rb, rc);
    vmbreak;
}

settable 入口

这里的 settableProtected 是一个宏,luaV_fastset 尝试进行快速赋值,如果失败则执行 luaV_finishset 插入一个新的键:

#define settableProtected(L,t,k,v) { const TValue *slot; \
    if (!luaV_fastset(L,t,k,slot,luaH_get,v)) \
    Protect(luaV_finishset(L,t,k,v,slot)); }

luaV_fastset 中,先尝试使用函数 luaH_get 查找在表 t 中已经存在的键 k, 如果该键已经存在于 table 中,那么只需要简单得取出它并修改其值为 v 即可, 这里的 slot 是一个存放查找结果的中间变量:

// lvm.h
#define luaV_fastset(L,t,k,slot,f,v) \
  (!ttistable(t) \
   ? (slot = NULL, 0) \
   : (slot = f(hvalue(t), k), \
     ttisnil(slot) ? 0 \
     : (luaC_barrierback(L, hvalue(t), v), \
        setobj2t(L, cast(TValue *,slot), v), \
        1)))

// ltable.c
const TValue *luaH_get (Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));
    case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
    case LUA_TNIL: return luaO_nilobject;
    case LUA_TNUMFLT: {
      lua_Integer k;
      if (luaV_tointeger(key, &k, 0)) /* index is int? */
        return luaH_getint(t, k);  /* use specialized version */
      /* else... */
    }  /* FALLTHROUGH */
    default:
      return getgeneric(t, key);
  }
}

首先进入到了 luaH_get 的分之 case LUA_TNUMIN 中调用 luaH_getint 尝试获取已经存在的索引为正整数值 1 的 TValue 结构用于存放新值。

const TValue *luaH_getint (Table *t, lua_Integer key) {
  /* (1 <= key && key <= t->sizearray) */
  if (l_castS2U(key) - 1 < t->sizearray)
    return &t->array[key - 1];
  else {
    Node *n = hashint(t, key);
    for (;;) {  /* check whether 'key' is somewhere in the chain */
      if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
        return gval(n);  /* that's it */
      else {
        int nx = gnext(n);
        if (nx == 0) break;
        n += nx;
      }
    }
    return luaO_nilobject;
  }
}

先尝试判断这个整数 key 是否在 table 的数组部分,由于 sizearray 为 0,所以并不会在数组部分。继续尝试从哈希表部分查找,由于哈希表部分是指向 dummynode 的,所以依然未查找,整个函数返回空对象 luaO_nilobject(对于如果存在于哈希表部分的键的查找请往下继续看)。

返回 luaV_execute 函数中继续执行, luaV_fastset 结果为 0,查找已存在的 k 失败。 luaV_finishset 执行最终的插入操作,luaV_finishset 有相关的元表操作,暂且在这里忽略掉它们,通过 luaH_newkey 来扩展一个新的位置来存放值。

TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
    Node *mp;
    ...
    mp = mainposition(t, key);
    if (!ttisnil(gval(mp)) || isdummy(mp)) {  /* 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 */
        }
    ...
}

忽略其他条件分之的代码,isdummy(mp) 为 true 进入分之,getfreepos 返回无可用空闲节点,开始执行第一次 rehash 操作。

rehash

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);
}

rehash 函数作用是计算数组部分哈希部分希望调整到的合适的新长度,然后进行扩展空间。

构造一个 nums[MAXABITS + 1] 数组来记录区间 (2^(i - 1), 2^i] 值不为 nil 的正整数键的数量。

变量 na 记录了所有正整数键的数量。

numusearray 遍历了整个数组部分,以区间 (2^(i - 1), 2^i] 为步长来遍历每个区间的非空的值,记录数量到数组 nums 中,同时最终返回数组中非空值的总数:

static unsigned int numusearray (const Table *t, unsigned int *nums) {
  int lg;
  unsigned int ttlg;  /* 2^lg */
  unsigned int ause = 0;  /* summation of 'nums' */
  unsigned int i = 1;  /* count to traverse all array keys */
  /* traverse each slice */
  for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
    unsigned int lc = 0;  /* counter */
    unsigned int lim = ttlg;
    if (lim > t->sizearray) {
      lim = t->sizearray;  /* adjust upper limit */
      if (i > lim)
        break;  /* no more elements to count */
    }
    /* count elements in range (2^(lg - 1), 2^lg] */
    for (; i <= lim; i++) {
      if (!ttisnil(&t->array[i-1]))
        lc++;
    }
    nums[lg] += lc;
    ause += lc;
  }
  return ause;
}

numusehash 遍历了整个哈希表部分来进行计数哈希表部分的使用总数。它也同时统计了哈希部分所有正整数键的数量累加至 na,因为这些键可能会在 rehash 后放入数组部分。

static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
  int totaluse = 0;  /* total number of elements */
  int ause = 0;  /* elements added to 'nums' (can go to array part) */
  int i = sizenode(t);
  while (i--) {
    Node *n = &t->node[i];
    if (!ttisnil(gval(n))) {
      ause += countint(gkey(n), nums);
      totaluse++;
    }
  }
  *pna += ause;
  return totaluse;
}

na += countint(ek, nums) 如果即将插入的新键是一个正整数,那么也把它记录到 nums 数组里,同时否则什么也不做。

computesizes 通过已知所有的(包括即将插入的)正整数键值在 (2^(i - 1), 2^i] 的分布,和正整数键数量的总数,来计算出一个新的数组部分的大小。在数组范围外的正整数键放到哈希表中:

static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
  int i;
  unsigned int twotoi;  /* 2^i (candidate for optimal size) */
  unsigned int a = 0;  /* number of elements smaller than 2^i */
  unsigned int na = 0;  /* number of elements to go to array part */
  unsigned int optimal = 0;  /* optimal size for array part */
  /* loop while keys can fill more than half of total size */
  for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) {
    if (nums[i] > 0) {
      a += nums[i];
      if (a > twotoi/2) {  /* more than half elements present? */
        optimal = twotoi;  /* optimal size (till now) */
        na = a;  /* all elements up to 'optimal' will go to array part */
      }
    }
  }
  lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
  *pna = na;
  return optimal;
}

注意: 可以跳过下面这里的说明,后面有另一个角度的解释)

以有 16 个连续的已存在的正整数键 1 至 16 为例,如果插入正整数键 17, 那么 rehash 时计算计算出的 nums 如下:

nums[MAXABITS + 1] = {1, 1, 2, 4, 8, 0 ...} 
区间 (0.5, 1], (1, 2], (2, 4], (4, 8], (8, 16] 满

算上插入的新键,则所有的正整数键为 17 个。那么会遍历且累加正整数键的合,同时判断累加和是否大于当前右闭区间一半的大小 twotoi (也就是左区间),如果成立,则记录数组到此大小。

累加到区间 i=4, (8, 16] 时, a = 16, twotoi = 16 时。数组总数为 pna = 17,循环还未终止。

累加到区间 i=5, (16, 32] 时,a = 17, twotoi = 32 时,a > twotoi / 2 成立,且循环终止,数组部分取 32。

如果后面的区间还有正整数键存在,则继续用上面的规则来计算。

但是循环会在正整数键总数 pna 小于等于当前右区间的一半 (twotoi/2) 时停下。因为后面的区间已经不可能成立 累加的正整数键大于当前区间右区间的一半 (twotoi/2)了。

假设这里的 17 个正整数键不是连续的,最后迭代到 (16, 32] 已经够了,因为 17 个正整数键值对已经不可能在 (32, 64] 范围内成立 17 > 64 / 2 。

!!! 上面确实很难理解(我自己写的时候已经要混乱了),让我们换一个逆向的方向来理解它

[1, 2^(MAXABITS + 1)] 范围内有没有一半以上的正整数键?(第一次是不可能的,整数键最大数量为 2^MAXABITS, 至少得 2^MAXABITS + 1 个整数键才算一半以上)
没有,分配这个长度的数组太浪费了,砍一半看看。
[1, 2^MAXABITS] 范围内有没有一半以上的正整数键?
没有,砍一半。
...
[1, 64] 范围内有没有一半以上的正整数键?
没有,砍一半。
[1, 32] 范围内有没有一半以上的正整数键?
有,17 大于 32 / 2,就它了。

computesizes 则是上面说明的顺序遍历版本,所以会比较难理解。

可用下列代码进行测试:

GDB 断点: b rehash if ek->value_.i >= 16 && ek->value_.i < 999

local t = {}; for i=1, 16 do t[i] = 0 end; t[32] = 0

可以看见最终的数组长度 asize 被计算为32,如果最后一次的正整数键赋值改成 t[33] = 0,则键 33 会被放到哈希表部分。

让我们回到首次插入正整数键 1 的时刻,此刻传给 luaH_resize 的分配数组长度 nasize 为 1,哈希表长度 nhsize 为 0。

void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
                                          unsigned int nhsize) {
  unsigned int i;
  int j;
  unsigned int oldasize = t->sizearray;
  int oldhsize = t->lsizenode;
  Node *nold = t->node;  /* save old hash ... */
  if (nasize > oldasize)  /* array part must grow? */
    setarrayvector(L, t, nasize);
  /* create new hash part with appropriate size */
  setnodevector(L, t, nhsize);
  if (nasize < oldasize) {  /* array part must shrink? */
    t->sizearray = nasize;
    /* re-insert elements from vanishing slice */
    for (i=nasize; i<oldasize; i++) {
      if (!ttisnil(&t->array[i]))
        luaH_setint(L, t, i + 1, &t->array[i]);
    }
    /* shrink array */
    luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  }
  /* re-insert elements from hash part */
  for (j = twoto(oldhsize) - 1; j >= 0; j--) {
    Node *old = nold + j;
    if (!ttisnil(gval(old))) {
      /* doesn't need barrier/invalidate cache, as entry was
         already present in the table */
      setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
    }
  }
  if (!isdummy(nold))
    luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old hash */
}

如果数组部分需要的长度大于原有的长度: 则通过 setarrayvector 分配新的数组长度 1,并且把新增的部分赋值为 nil。如果旧的数组含有数据,分配函数 luaM_reallocvector 会复制这部分数据到新数组中。

static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
  unsigned int i;
  luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
  for (i=t->sizearray; i<size; i++)
     setnilvalue(&t->array[i]);
  t->sizearray = size;
}

若数组部分被截断: 则遍历被截断部分的正整数键通过 luaH_setint 插入至哈希表(数组长度先已经被标记为较短的新长度 nasize,此时新哈希表空间已被分配),然后再缩小数组部分。

对于哈希部分,则进行一次完整的插入操作。

栈帧最终回退到 luaH_newkey 中,进行 luaH_set 赋值操作,至此对于一个空表的首次数组部分赋值完成, 此时 table 的结构如下:

哈希插入

对于哈希的插入使用下列的示例代码:

local t = {}; t["s"] = 123456

再回到函数 luaH_get 中,它返回一个查找到的键的对应的 TValue 结构:

对于短字符串键,使用 luaH_getshortstr 来查找。

对于正整数键,或者可以转换成整数形式的浮点数键,使用 luaH_getint 来查找。

nil 类型返回静态变量 luaO_nilobject (这并不意味着你能插入 nil 键)。

对于其他类型,使用标准查找 getgeneric

除了正整数键查找 luaH_getint 会先查找数组部分以外,其它查找函数都做的是类似的事情,以 getgeneric 为例:

static const TValue *getgeneric (Table *t, const TValue *key) {
  Node *n = mainposition(t, key);
  for (;;) {  /* check whether 'key' is somewhere in the chain */
    if (luaV_rawequalobj(gkey(n), key))
      return gval(n);  /* that's it */
    else {
      int nx = gnext(n);
      if (nx == 0)
        return luaO_nilobject;  /* not found */
      n += nx;
    }
  }
}

通过 mainposition 获得 主位置节点(键哈希值与哈希表长度取模),然后判断哈希节点的键是否与所查找的键相等,如果相等则返回节点的 TValue。否则通过存储的偏移值查找下一个节点,如果没有,则表明键不在哈希表中。

一种可能的情况:

对于哈希部分是指向 dummynode 的 table 来说,getgeneric 肯定是找不到对应的键的节点的,最终 luaH_get 返回 luaO_nilobject

接下来的大部分流程与数组插入无异,对于空表来说 getfreepos 返回 NULL, 执行第一次 rehash

最终传递给 luaH_resize 中的 setnodevector 函数来调整哈希部分大小,对于传入的新的哈希大小,分配的实际尺寸为 2^ceil(log2(size)),所以哈希表部分也是以2的整数次幂增长的。

新的哈希表空间分配完成后,通过 luaH_set 插入被移出数组部分的内容和原哈希表的内容。

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

由于 rehash 是重新排列,在新表中不可能找到一个已经存在的空键 key,所有逻辑均会执行到调用 luaH_newkey 来分配一个新的哈希节点。

这次让我们来看完整的 luaH_newkey 函数:

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)) {  /* index is int? */
      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);
  if (!ttisnil(gval(mp)) || isdummy(mp)) {  /* 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(f));
    othern = mainposition(t, gkey(mp));
    if (othern != mp) {  /* is colliding hashnode out of its main position? */
      /* yes; move colliding hashnode 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 hashnode 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 hashnode is in its own main position */
      /* new hashnode 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);
      mp = f;
    }
  }
  setnodekey(L, &mp->i_key, key);
  luaC_barrierback(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

在首次 mainposition 之后,获得的节点 mp 如果是一个空节点且不指向 dummynode 时,则表明该节点可用。否则判断是否需要 rehash (表指向 dummynodegetfreepos 一定会返回 NULL),由于当前的是 rehash 过程中的重排列,所以不可能再次发生 rehash。

当查找的 mp 由于冲突被其它键所占用时,会通过 getfreepos 尝试获取一个可用的节点来存储新的键。

static Node *getfreepos (Table *t) {
  while (t->lastfree > t->node) {
    t->lastfree--;
    if (ttisnil(gkey(t->lastfree)))
      return t->lastfree;
  }
  return NULL;  /* could not find a free place */
}

lastfree 初始指向哈希表的最后一个节点的下一个位置,向前迭代直到找到一个空节点,如果迭代到哈希表头则表明无可用节点,返回 NULL。

当返回一个可用的节点时,会判断:

1) 如果属于同一主位置节点链下 (现有的 mp 位置的键的主位置节点和新插入的 key 的主位置节点确实指向的同一个节点),那么把空节点插入到主位置节点之后(每个节点的 TKey 结构中存储着指向下一个节点的偏移值)。

2) 如果不属于同一主位置节点链下,则意味着原本通过 mainposition(newkey) 直接定位的节点被其它节点链中的某个节点占用:

othern (起始位置 上图 key1 位置) 节点开始遍历链表直到 mp 的前一个位置 (指向上图 key2 位置的节点,在这里就是 key1 自己), 然后将 mp 的数据移动到空节点上,othern 指向新的节点,旧的节点用来放入新插入的键:

luaH_newkey 返回新键的 TValue 结构,rehash 中的哈希部分的重新插入全部完成。

最终: 示例代码中的 table 新哈希部分长度为 1,且不会有哈希部分的重新插入,所以执行完毕后直接对插入的新键进行 luaH_newkey 操作,最终得到了一个可用的键位插入新值 123456,至此哈希插入完成。

索引

索引函数 luaH_get 上述内容已经描述

序列长度

lua文档 中,取长操作符的定义是当 table 是一个序列时才有定义。序列意味着正整数键的部分必须是连续的(非正整数键会忽略)。否则是一个 未定义行为,例如:

print(#{nil,nil,0}) => 3
local t = {1,2,3}; t[2] = nil; print(#t) => 3
local t = {1,2,3}; t[2] = nil; t["x"] = nil; print(#t) => 1
local t = {1,2,3,4,5,6,7,8}; t[16] = 0; print(#t) => 16
local t = {1,2,3,4,5,6,7,8}; t[15] = 0; print(#t) => 8

luaH_getn 获取了一个 table 序列的长度 (假定它是一个序列为前提):

int luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  if (j > 0 && ttisnil(&t->array[j - 1])) {
    /* there is a boundary in the array part: (binary) search for it */
    unsigned int i = 0;
    while (j - i > 1) {
      unsigned int m = (i+j)/2;
      if (ttisnil(&t->array[m - 1])) j = m;
      else i = m;
    }
    return i;
  }
  /* else must find a boundary in hash part */
  else if (isdummy(t->node))  /* hash part is empty? */
    return j;  /* that is easy... */
  else return unbound_search(t, j);
}

有三种情况:

1) 数组部分刚好被占满,且没有哈希表部分,则直接返回 sizearray

2) 数组部分没有被占满,则通过二分查找检索到数组最后的非空位置。最终返回序列长度。

3) 数组部分被占满,且有哈希表部分,执行 unbound_search 传入数组长度,开始搜索在哈希部分的正整数键。

使用下列测试代码可以触发哈希部分的搜索:

local t= {};
for i=1, 8 do 
    t[i] = 0 
end
for i=1, 16 do 
    t[''..i] = 0 
end
for i=1, 16 do 
    t[''..i] = nil 
end
for i=1, 16 do 
    t[i + 8] = 0 
end 
print(#t)

数组部分先占用8个长度,再占用16个长度的哈希部分,再清空它们,全部插入整数键,table 的序列长度最终为24,数组长度为8,哈希表长度为 16。

再来看 unbound_search 的实现:

static int unbound_search (Table *t, unsigned int j) {
  unsigned int i = j;  /* i is zero or a present index */
  j++;
  /* find 'i' and 'j' such that i is present and j is not */
  while (!ttisnil(luaH_getint(t, j))) {
    i = j;
    if (j > cast(unsigned int, MAX_INT)/2) {  /* overflow? */
      /* table was built with bad purposes: resort to linear search */
      i = 1;
      while (!ttisnil(luaH_getint(t, i))) i++;
      return i - 1;
    }
    j *= 2;
  }
  /* now do a binary search between them */
  while (j - i > 1) {
    unsigned int m = (i+j)/2;
    if (ttisnil(luaH_getint(t, m))) j = m;
    else i = m;
  }
  return i;
}

以每次2倍的增幅向后搜索可能的二分查找用的区间,以 j = 8 为例,则搜索 [9,18], [18,36],当 j 等于 36 时,哈希部分的键 36 为 nil,则说明序列的末尾在 18 到 36 范围内,然后进行二分查找最终返回序列长度。

如果搜索到正整数即将溢出的范围都还没有到条件 (则说明你构造了一个很糟糕的 table),则使用线性搜索。

迭代器

ipairs

注意:5.2 中的元方法 __ipairs 在 5.3 中已被标记为 deprecated,可以定义宏 LUA_COMPAT_5_2 来开启它。

// lbaselib.c
static int luaB_ipairs (lua_State *L) {
#if defined(LUA_COMPAT_IPAIRS)
  return pairsmeta(L, "__ipairs", 1, ipairsaux);
#else
  luaL_checkany(L, 1);
  lua_pushcfunction(L, ipairsaux);  /* iteration function */
  lua_pushvalue(L, 1);  /* state */
  lua_pushinteger(L, 0);  /* initial value */
  return 3;
#endif
}

ipairs 返回了三个值给 for 循环来进行迭代: 迭代函数, 迭代对象 (函数的第一个参数), 以及迭代初始值 0。迭代函数 ipairsaux 如下:

static int ipairsaux (lua_State *L) {
  lua_Integer i = luaL_checkinteger(L, 2) + 1;
  lua_pushinteger(L, i);
  return (lua_geti(L, 1, i) == LUA_TNIL) ? 1 : 2;
}

它只是简单的每次把传入的迭代值增加 1 再去尝试从 table 中索引,如果没有值返回 nil 停止迭代。

pairs

pairs 迭代器会先尝试取元方法 __pairs,如果成功则调用元方法来获得值用于迭代。否则通过传入的迭代函数 luaB_next,迭代对象,迭代初始值 nil 来进行迭代:

static int pairsmeta (lua_State *L, const char *method, int iszero,
                  lua_CFunction iter) {
  if (luaL_getmetafield(L, 1, method) == LUA_TNIL) {  /* no metamethod? */
    luaL_checktype(L, 1, LUA_TTABLE);  /* argument must be a table */
    lua_pushcfunction(L, iter);  /* will return generator, */
    lua_pushvalue(L, 1);  /* state, */
    if (iszero) lua_pushinteger(L, 0);  /* and initial value */
    else lua_pushnil(L);
  }
  else {
    lua_pushvalue(L, 1);  /* argument 'self' to metamethod */
    lua_call(L, 1, 3);  /* get 3 values from metamethod */
  }
  return 3;
}

static int luaB_pairs (lua_State *L) {
  return pairsmeta(L, "__pairs", 0, luaB_next);
}

luaB_next 会压入两个参数给 API 函数 lua_next,被遍历的 table,以及即迭代值,如果没有传入迭代值则压入一个 nil 值作为初始值:

static int luaB_next (lua_State *L) {
  luaL_checktype(L, 1, LUA_TTABLE);
  lua_settop(L, 2);  /* create a 2nd argument if there isn't one */
  if (lua_next(L, 1))
    return 2;
  else {
    lua_pushnil(L);
    return 1;
  }
}

lua_next 会从栈中从指定的 idx 取出被迭代的 table 对象,栈顶被用作迭代值来迭代下一个对象,迭代的核心实现在 table 模块中的 luaH_next。关于 lua_next 的用法可以参考 官方文档

// lapi.c
LUA_API int lua_next (lua_State *L, int idx) {
  StkId t;
  int more;
  lua_lock(L);
  t = index2addr(L, idx);
  api_check(L, ttistable(t), "table expected");
  more = luaH_next(L, hvalue(t), L->top - 1);
  if (more) {
    api_incr_top(L);
  }
  else  /* no more elements */
    L->top -= 1;  /* remove key */
  lua_unlock(L);
  return more;
}

最终的迭代实现在 luaH_next 中:

int luaH_next (lua_State *L, Table *t, StkId key) {
  unsigned int i = findindex(L, t, key);  /* find original element */
  for (; i < t->sizearray; i++) {  /* try first array part */
    if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
      setivalue(key, i + 1);
      setobj2s(L, key+1, &t->array[i]);
      return 1;
    }
  }
  for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) {  /* hash part */
    if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
      setobj2s(L, key, gkey(gnode(t, i)));
      setobj2s(L, key+1, gval(gnode(t, i)));
      return 1;
    }
  }
  return 0;  /* no more elements */
}

通过 findindex 获得 key 的一个整数表示的搜索位置:

1) 如果位于数组部分,则由搜索位置开始向后索引数组部分的值,查找到一个非 nil 的值则向 lua 栈中压入当前位置的键值对。

2) 如果位于哈希表部分,那么也是类似的,直接按照哈希表的节点顺序遍历每个哈希节点,直到找到一个非 nil 的节点。

一种可能的迭代顺序(这里并不是 i 的值):

实质上 findindex 是将数组部分和哈希表部分当作一个整体,来获得指定的 key 的索引:

/*
** returns the index of a 'key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signaled by 0.
*/
static unsigned int findindex (lua_State *L, Table *t, StkId key) {
  unsigned int i;
  if (ttisnil(key)) return 0;  /* first iteration */
  i = arrayindex(key);
  if (i != 0 && i <= t->sizearray)  /* is 'key' inside array part? */
    return i;  /* yes; that's the index */
  else {
    int nx;
    Node *n = mainposition(t, key);
    for (;;) {  /* check whether 'key' is somewhere in the chain */
      /* key may be dead already, but it is ok to use it in 'next' */
      if (luaV_rawequalobj(gkey(n), key) ||
            (ttisdeadkey(gkey(n)) && iscollectable(key) &&
             deadvalue(gkey(n)) == gcvalue(key))) {
        i = cast_int(n - gnode(t, 0));  /* key index in hash table */
        /* hash elements are numbered after array ones */
        return (i + 1) + t->sizearray;
      }
      nx = gnext(n);
      if (nx == 0)
        luaG_runerror(L, "invalid key to 'next'");  /* key not found */
      else n += nx;
    }
  }
}

可以看成数组部分在前,哈希表部分在后的形式:

总结

1) 构造 table 时尽量使用构造语句以预分配空间:

local t = {1,2,3,4,5,6 ... }

但是对于会有大量的键的 table 来说只是为了避免几次小范围的 rehash 去这么做,有点不值得,特别是会提升代码维护成本。

2) 尽量避免连续的正整数键和其它键混用,考虑下列两种情况:

local t = {}

for i=1, 1024 do
    t[i] = 0
end

for i=1, 1024 do
    t[i] = nil
end

t["s"] = 0

将数组部分扩充至 1024 长度之后再全部置为 nil 后进行一次哈希插入,此时 rehash 会将数组部分全部回收。可使用断点 b ltable.c:346 if nasize < oldasize 观察。

但下列情况:

local t = {}

for i=1,1024 do
    t[""..i] = 0
end

for i=1,1024 do
    t[""..i] = nil
end

t[1] = 0

正整数键 1 会放入哈希部分 (luaH_get 检查到数组部分没有可用的空间,luaH_newkey 会放入哈希部分)。

结论数组部分哈希部分有空间不足的情况时会触发 rehash,但是如果其中有空闲空间比较多的情况,则会减少该部分的使用空间。如果数组空间不够时会先尝试放入哈希部分,如果哈希部分空间不够则才进行 rehash

3) etc … 待补..