注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

lua表格  

2017-04-08 21:56:26|  分类: Lua |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、表格
表格在整个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: 
三、manual中对于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用来保存迭代的当前位置,从而可以在下次迭代的时候从该位置继续。
四、table的pairs遍历
1、初始化
这里的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
}
2、table的迭代
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 */
}
五、for语句中变量寄存器的连续分配
1、如何将迭代函数结果赋值给迭代变量
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指令执行之后,用户变量均已被赋值为迭代函数返回值。
2、连续寄存器的编译时分配
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);
  }

六、Lua中table使用的数据结构
1、数组型和关联性并存
从前面的例子可以看到,可以通过数组类型和关联类型来定义一个数组,所以对应地在每个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,而是需要在内部解决冲突,从而将所有的元素放在一个连续空间中。
2、hash冲突的处理
在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位置了),因为反正已不在主位置,再次转移依然不是。这里打个不恰当的必要,就相当于你拿着火车票上车,发现自己位置上坐的是一个拿站票的人,你是可以请他离开的。

  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017