表格在整个Lua语言的数据结构中占有重要地位，正如Lua的作者所说： Tables are the main — in fact, the only — data-structuring mechanism in Lua.Table是Lua的主要(事实上，也是唯一的)数据结构。

数组变量的初始化有三种形式：最为常见的就是使用逗号分开的值；第二种是[index] = value形式的初始化，这种形式下中括号内为一个数值；第三种是键值(或者可以认为是结构的成员变量)形式的初始化。第一种最为平铺直叙，或者说trivial实现。不过后两种形式的初始化事实上离我们也并不是那么遥远，因为gcc也支持通过这种方式对数组和结构的特定成员进行初始化：

tsecer@harry: cat gcc_init_ext.c 

#include <stdio.h>

typedef struct

{

int x;

int y;

} Base;

 

int main()

{

int i;

int arr[5] = {[2] = 1111, [3] = 2222,};

Base b = {.y = 3333};

for (i = 0; i < 5 ; i++)

{

printf("%d %d\n", i, arr[i]);

}

printf("x %d y %d\n", b.x, b.y);

}

 

tsecer@harry: gcc gcc_init_ext.c

tsecer@harry: ./a.out 

0 0

1 0

2 1111

3 2222

4 0

x 0 y 3333

下面脚本对表格数据通过for循环加pairs进行遍历。

tsecer@harry: cat ./lua-table.lua

arr =

{

  tsecer = "TSECER",

  harry = "HARRY",

   "STRAY",

   [1] = "11111",

   [2] = "22222",

   [4] = "11111",

}

local i , j

for k, v in pairs(arr) do

  print(k, v)

end

 

print("arr len", #arr)

 

tsecer@harry:   /home/tsecer/Download/lua-5.3.4/src/lua ./lua-table.lua 

1 STRAY

2 22222

tsecer TSECER

harry HARRY

4 11111

arr len 4

tsecer@harry:   /home/tsecer/Download/lua-5.3.4/src/luac -o lua-table.i ./lua-table.lua 

tsecer@harry:   /home/tsecer/Download/lua-5.3.4/src/luac -l -l  lua-table.i 

 

main <./lua-table.lua:0,0> (26 instructions at 0x84b7f38)

0+ params, 10 slots, 1 upvalue, 7 locals, 14 constants, 0 functions

1 [1] NEWTABLE  0 1 5

2 [3] SETTABLE  0 -2 -3 ; "tsecer" "TSECER"

3 [4] SETTABLE  0 -4 -5 ; "harry" "HARRY"

4 [5] LOADK     1 -6 ; "STRAY"

5 [6] SETTABLE  0 -7 -8 ; 1 "11111"

6 [7] SETTABLE  0 -9 -10 ; 2 "22222"

7 [8] SETTABLE  0 -11 -8 ; 4 "11111"

8 [9] SETLIST   0 1 1 ; 1

9 [9] SETTABUP  0 -1 0 ; _ENV "arr"

10 [10] LOADNIL   0 1

11 [11] GETTABUP  2 0 -12 ; _ENV "pairs"

12 [11] GETTABUP  3 0 -1 ; _ENV "arr"

13 [11] CALL      2 2 4

14 [11] JMP       0 4 ; to 19

15 [12] GETTABUP  7 0 -13 ; _ENV "print"

16 [12] MOVE      8 5

17 [12] MOVE      9 6

18 [12] CALL      7 3 1

19 [11] TFORCALL  2 2

20 [11] TFORLOOP  4 -6 ; to 15

21 [15] GETTABUP  2 0 -13 ; _ENV "print"

22 [15] LOADK     3 -14 ; "arr len"

23 [15] GETTABUP  4 0 -1 ; _ENV "arr"

24 [15] LEN       4 4

25 [15] CALL      2 3 1

26 [15] RETURN    0 1

constants (14) for 0x84b7f38:

1 "arr"

2 "tsecer"

3 "TSECER"

4 "harry"

5 "HARRY"

6 "STRAY"

7 1

8 "11111"

9 2

10 "22222"

11 4

12 "pairs"

13 "print"

14 "arr len"

locals (7) for 0x84b7f38:

0 i 11 27

1 j 11 27

2 (for generator) 14 21

3 (for state) 14 21

4 (for control) 14 21

5 k 15 19

6 v 15 19

upvalues (1) for 0x84b7f38:

0 _ENV 1 0

tsecer@harry: 

下面是Lua手册中对于for语句语义的说明：

A for statement like

 

     for var_1, ···, var_n in explist do block end

is equivalent to the code:

 

     do

       local f, s, var = explist

       while true do

         local var_1, ···, var_n = f(s, var)

         if var_1 == nil then break end

         var = var_1

         block

       end

     end

这里有三个隐藏变量f、s、var(这个“隐藏”可以认为是编译器瞒着用户创建的，而不是由于用户声明而触发)，f是一个函数，s和var是该函数的回调参数。对于函数使用的变量state和var来说，state在每次迭代的时候保持静止(或许state可以理解为“静止”的意思，当然理解为“状态”也行)，而var是在每次函数结束之后都会更新的一个变化变量。对于table的pairs遍历来说，这个地方的state存储的就是当前遍历的table，而其中的var用来保存迭代的当前位置，从而可以在下次迭代的时候从该位置继续。

这里的luaB_next就是和f对应的迭代器。

static int luaB_pairs (lua_State *L) {

  return pairsmeta(L, "__pairs", 0, luaB_next);

}

在函数pairsmeta中，lua_pushvalue(L, 1)将当前栈帧1位置上的变量(也就是arr表格的地址)压入堆栈。这里由于调用的是pairs(arr)表达式，所在在执行到pairsmeta的时候，虚拟机堆栈上0位置保存的是pairsmeta函数的Closure，1位置保存的就是参数arr的值。

static int pairsmeta (lua_State *L, const char *method, int iszero,

                      lua_CFunction iter) {

  luaL_checkany(L, 1);

  if (luaL_getmetafield(L, 1, method) == LUA_TNIL) {  /* no metamethod? */

    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); // 在堆栈上放入变量var的值，也就是nil。

  }

  else {

    lua_pushvalue(L, 1);  /* argument 'self' to metamethod */

    lua_call(L, 1, 3);  /* get 3 values from metamethod */

  }

  return 3;//返回值为3，表示在返回堆栈上压入了3个参数，分别对应iter、arr和nil

}

findindex根据上次迭代的返回位置对table表格内部的array列表和hash列表进行遍历，而在luaH_next函数会从当前位置开始依次遍历array或hash，如果遇到非空元素则返回该元素。注意对于hash表的遍历也是按照下标来依次遍历。

luaB_next===>>>lua_next===>>>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 */

}

manual中对于for的解释中有这么一个语义动作

local var_1, ···, var_n = f(s, var)

这个赋值是一个连续赋值，会对for中自定义的变量组使用迭代函数初始化，结合生成的虚拟机指令，这个动作只是通过一条虚拟机指令来实现

19 [11] TFORCALL  2 2

下面是Lua虚拟机对于该指令的解释lua-5.3.4\src\lvm.c:luaV_execute (lua_State *L)

      vmcase(OP_TFORCALL) {

        StkId cb = ra + 3;  /* call base */

        setobjs2s(L, cb+2, ra+2);

        setobjs2s(L, cb+1, ra+1);

        setobjs2s(L, cb, ra);

        L->top = cb + 3;  /* func. + 2 args (state and index) */

        Protect(luaD_call(L, cb, GETARG_C(i)));

        L->top = ci->top;

        i = *(ci->u.l.savedpc++);  /* go to next instruction */

        ra = RA(i);

        lua_assert(GET_OPCODE(i) == OP_TFORLOOP);

        goto l_tforloop;

      }

这里使用到了TFORCALL指令的两个操作数，第一个操作数for循环变量组(这个变量组中包含了不可见的f，state，var,和可见的var1,……,varn，这些变量占用的寄存器编号从f开始连续分配)中第一个变量(f变量的寄存器编号)的起始地址，第二个参数GETARG_C(i)表示了函数调用者需要的返回变量数目。

虚拟机执行逻辑中

        setobjs2s(L, cb+2, ra+2);

        setobjs2s(L, cb+1, ra+1);

        setobjs2s(L, cb, ra);

依次将var、state、f从高到低放入堆栈，并且f位置为ra + 3，这里的3表示不可见的三个控制寄存器，因为ra指向的是不可见寄存器的起始地址，ra + 3指向的是用户变量寄存器的起始位置。被调用函数return的时候，会将返回数值列表放在从cb开始的位置，也就是用户定义变量列表var1……这些变量中，所以OP_TFORCALL指令执行之后，用户变量均已被赋值为迭代函数返回值。

static void forlist (LexState *ls, TString *indexname) {

……

  int nvars = 4;  /* gen, state, control, plus at least one declared var */

……

  int base = fs->freereg;

  /* create control variables */

  new_localvarliteral(ls, "(for generator)");

  new_localvarliteral(ls, "(for state)");

  new_localvarliteral(ls, "(for control)");

  /* create declared variables */

  new_localvar(ls, indexname);

  while (testnext(ls, ',')) {

    new_localvar(ls, str_checkname(ls));

    nvars++;

  }

……

  forbody(ls, base, line, nvars - 3, 0);

}

在forlist函数中，base值为fs->freereg，也就是当前第一个空闲寄存器，它们也就是这些连续变量寄存器的起始位置。以我们前面代码为例，由于local i , j占用了0、1连个寄存器，所以这个地方的fs->freereg值为2，也就是虚拟机指令OP_TFORLOOP中第一个操作数2的由来(指令第二个操作数2表示迭代变量的数量：k、v)。

static void forbody (LexState *ls, int base, int line, int nvars, int isnum) {

……

  if (isnum)  /* numeric for? */

    endfor = luaK_codeAsBx(fs, OP_FORLOOP, base, NO_JUMP);

  else {  /* generic for */

    luaK_codeABC(fs, OP_TFORCALL, base, 0, nvars); 这个地方记录的是不包括之前变量的起始位置，对于之前的代码，这里的base值为2，也就是i和j占用的连个临时变量。

    luaK_fixline(fs, line);

    endfor = luaK_codeAsBx(fs, OP_TFORLOOP, base + 2, NO_JUMP);

  }

 

从前面的例子可以看到，可以通过数组类型和关联类型来定义一个数组，所以对应地在每个table的定义中就包涵了两种类型的数据结构：

lua-5.3.4\src\lobject.h

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;

可以看到，数组类型的定义只有“值”，所以访问的时候只能通过数值作为数组下标来访问。而对于hash类型定义，其中的每个节点Node包含了key和value两个部分，也就是在hash冲突的时候可以通过key值来“确认”精确匹配。

typedef struct Node {

  TValue i_val;

  TKey i_key;

} Node;

不过值得注意的是，这两个结构指向的都是数组结构，数组不用说，但是对于hash来说，这意味着没有一个单独的桶结构来保存冲突的head，而是需要在内部解决冲突，从而将所有的元素放在一个连续空间中。

在hash的键值定义中，除了简直本身之外还定义了一个额外的链表成员next，用来指向同一个hash值出现冲突的时候下一个冲突元素的存放位置。

typedef union TKey {

  struct {

    TValuefields;

    int next;  /* for chaining (offset for next node) */

  } nk;

  TValue tvk;

} TKey;

在这个冲突解决的过程中，实现的思路是每个键值必须放在自己的“主位置”，除非该位置也是当前元素的主位置。这里的主位置就是该元素hash值对应的第一首选位置。

举个栗子，数组长度为10，hash算法是 value % 10，考虑数组为空的情况下插入序列10、20、19：

10插入数组下标为0的位置，

20发现自己的主位置0已经被占用，并且当前占用元素为10，所以这个位置是当前占用元素的主位置，大家占用该位置的优先级相同，本着先来后到的原则，自己需要从当前空闲位置中选择一个(假设空闲位置从最后一个元素lastfree开始，也就是下标为9元素)，所以放在9下标处，在位置确定之后，要把该元素位置放在主位置引导的next链表中，从而可以在查找时可以遍历到该元素。

9发现自己的位置也被占用了，存放元素为20，检查下发现，20的主位置并不在这里(它是因为自己的主位置被10占用了才寄人篱下在这里的)，所以此时9可以名正言顺的让20离开而自己占据该位置。至于20离开之后存放在什么位置并不重要(当然还是lastfree位置了)，因为反正已不在主位置，再次转移依然不是。这里打个不恰当的必要，就相当于你拿着火车票上车，发现自己位置上坐的是一个拿站票的人，你是可以请他离开的。