关于LUA（上）
Lua是一种轻量小巧的脚本语言，C语言编写，并提供了易于使用的扩展接口和机制，易于嵌入到应用中，在游戏开发中经常被用来进行外层业务系统的开发。
Lua的table
Lua的基本数据类型有八种，分别是：nil、boolean、number、string、userdata、function、thread 和 table；其中Lua中的table是一个关联数组，他的KV的值的类型十分的灵活：key可以是出nil以外的任何数据类型，甚至可以是一个function，而val则更加丰富。
table的数据存储
Lua中table的源码实现如下：
typedef struct Table {
CommonHeader;
lu_byte flags;
lu_byte lsizenode;
unsigned int sizearray;
TValue* array;
Node* node;
Node* lastfree;
struct Table* metatable;
GCObject* gclist;
} Table;需要关注以下几点：
1.在Lua的table这个数据结构中，array和node都是用来存数据的，且存放的数据不重叠；实际在运行过程中会先尝试把key转成一个整数，若是可转成功，并且能存入到数组中（即下标值能在数组下标范围内）则优先存数组；否则就插入到哈希表中；查询过程也是，优先查数组，数组找不到就查哈希表，代码段如下：
/*
*1、先根据key的类型判断是不是能转成整数下标，如LUA_TNUMINT、LUA_TNUMFLT
*2、luaH_getint接口里面会根据转出来的值，判断是否能放在当前数组中，即下标小于sizearray，小于的话就丢数组，否则放到哈希表里面
*/
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 */
} /* FALLTHROUGH */
default:
return getgeneric(t, key);
}
}
/*
** search function for integers
*/
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]; // if key == 1 then the value store in t->array[0]
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;
}
}2.从接口luaH_getint的实现可以看出，sizearray用于存放array数组的容量
3.此外从luaH_getint还可以看到，可能存在一些能转成数字下标的key，但是由于当时不在数组空间内，即对应下标大小大于sizearray的key会存在哈希表中，并且还有当寻找的key值不等于哈希出来的这里的哈希表采取的是寻找下一个可用哈希节点的方式（n = gnext(n) + nx），这一点可以通过后面的在插入哈希节点前寻找空闲节点的接口getfreepos得到验证
4.在Lua中，当有新的key值需要插入到哈希表中时，是通过接口mainposition在计算key并获取对应key在哈希表的位置，若是对应位置已经被占了，则通过接口getfreepos寻找下一个可用的节点，从getfreepos的注释可以看出，table的哈希表也是一个数组结构，且大小是2的lsizenode的幂次（这一点可以从后面rehash过程可以印证），lastfree记录的是哈希表可用的节点位置；再进入到实现，若是对应key被占了，则解决哈希冲突的方法是向前找，找到第一个可用的节点为止，并且key的next成员变量是将这些节点串成一个链，也就是Lua table的哈希是通过开放寻址法做的：
// At First: t->lastfree ==> t->node[2^t->lsizenode]
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 */
}5.开放寻址法有一个弊端，就是随着节点越来越多，冲突会越来越多，且冲突会导致后面节点因为冲突占用到原先本不属于他的节点上，从而导致查询成本变高（举例来说，假设节点A本应该插入到node1的位置，但是因为node1被占用，导致必须插入到node2上，后面节点B被哈希到node2上因为这个占用导致节点B必须得寻找下一个节点，从而随着链节点和冲突增多，导致哈希表的访问丧失了最初的设计优势），针对此类问题，Lua采取的策略是，当后续节点哈希当被占用节点时，若是当前占用节点是因为碰撞移动到这个位置，本不属于这个链的，则将当前这个节点移动到下一个位置，通过这种方式维持后续访问通过哈希计算出来的node始终是一个冲突链的头，以提升查询效率，这个实现在luaH_newkey里面有体现，省略到不相干的代码，有如下代码段：
TValue* luaH_newkey(lua_State* L, Table* t, const TValue* key) {
//1)首先根据key值计算出来当前key应该在的主位置mp
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(t)) { /* main position is taken? */
//2)若这个位置被占用了!ttisnil(gval(mp)) ，那就找下一个可用位置getfreepos
//ps：isdummy为表判空逻辑
Node* f = getfreepos(t); /* get a free place */
//3)当前发生冲突的位置存放的节点是map，我们算一下这个mp的主位置在哪，得到othern
othern = mainposition(t, gkey(mp));
//4-1)若是othern和mp不相等，说明当前mp的主位置不是这个节点，则重新为mp这个节点选择位置
//具体做法是先通过while循环找到冲突链到mp前一个的位置
if (othern != mp) { /* is colliding node out of its main position? */
while (othern + gnext(othern) != mp) /* find previous */
othern += gnext(othern);
//前一个位置的next指向新分配的位置
gnext(othern) = cast_int(f - othern); /* rechain to point to 'f' */
//把当前位置mp的内容赋值到对应位置f上
*f = *mp; /* copy colliding node into free pos. (mp->next also goes) */
//如果mp后面有节点，则f的next指向mp的next，并将mp的next重置
if (gnext(mp) != 0) {
gnext(f) += cast_int(mp - f); /* correct 'next' */
gnext(mp) = 0; /* now 'mp' is free */
}
//重置mp
setnilvalue(gval(mp));
}
//4-2）若othern和mp相等，就表示这个本来就是当前节点主位置，则头插法插入进来：新插入节点的next存自己到f的插值，mp的next存f和mp的差值
else { /* colliding node is in its own main position */
if (gnext(mp) != 0)
gnext(f) = cast_int((mp + gnext(mp)) - f); /* chain new position */
gnext(mp) = cast_int(f - mp);
mp = f;
}
}
return gval(mp);
}6.继续说到rehash过程，再空闲节点被用完，会走到rehash的过程，rehash分为两步，一个是处理数组array部分，一个是处理哈希表部分，其中
(1) 数组部分由numusearray接口处理，从这个接口可以看到
①array数组扩容是翻倍扩容的，且上限为2的63次方
②array数组，被按照2的幂次划分为若干段，每段使用量记录在数组nums中，ause记录array总共的使用量
(2) 哈希表部分是numusehash处理的，其中：
①哈希表里面的key落在哪个幂次段是统计在nums数组的，实际nums里面累加了两次池子幂次段的用量
②totaluse记录哈希表的总节点数木，而ause累加的是适合放在数组的节点数
(3) 通过接口computesizes计算当前这个table中array数组的最优大小，其中asize返回的是估算后数组的大小，na获取的是放在数组里面元素的个数。computesizes计算的思路即数组能容纳一半数组元素就行，找到能容纳一半元素且最小的数组大小
(4) 实际迁移数据是在luaH_resize里面做的
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 */
//1)记录表中每个幂次段元素的用量，存在nums数组中
na = numusearray(t, nums); /* count keys in array part */
totaluse = na; /* all those keys are integer keys */
//2)遍历哈希表，每个幂次段元素个数累加到nums数组中，适合放在数组中的节点用na统计，array+node中元素总个数存入totaluse中
totaluse += numusehash(t, nums, &na); /* count keys in hash part */
//3）当前新插入的元素ek也得加上
na += countint(ek, nums);
totaluse++;
asize = computesizes(nums, &na);
luaH_resize(L, t, asize, totaluse - na);
}
static unsigned int numusearray(const Table* t, unsigned int* nums) {
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] */
//分段统计元素的个数，nums[1-63]分别存放的2的n-1次方到2的n次方元素个数
for (; i <= lim; i++) {
if (!ttisnil(&t->array[i - 1]))
lc++;
}
nums[lg] += lc;
ause += lc;
}
return ause;
}
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))) {
//numusehash核心思路一样，不同分段的都放在nums数组里面，区别在于countint会判断一下是否适合放在数组里面，不适合就不算进去
ause += countint(gkey(n), nums);
totaluse++;
}
}
*pna += ause;
return totaluse;
}table的metatable
前面一段介绍了数据在table里面是怎么存储和查询的，table的结构体里面还有一个成员变量metatable是做什么的&怎么用的呢？
typedef struct Table {
CommonHeader;
lu_byte flags;
lu_byte lsizenode;
unsigned int sizearray;
TValue* array;
Node* node;
Node* lastfree;
struct Table* metatable;
GCObject* gclist;
} Table;元表（metatable）在Lua的官方文档里面是这么解释的:
Usually, tables in Lua have a quite predictable set of operations. We can add key-value pairs, we can check the value associated with a key, we can traverse all key-value pairs, and that is all. We cannot add tables, we cannot compare tables, and we cannot call a table.
Metatables allow us to change the behavior of a table. For instance, using metatables, we can define how Lua computes the expression a+b, where a and b are tables. Whenever Lua tries to add two tables, it checks whether either of them has a metatable and whether that metatable has an __add field. If Lua finds this field, it calls the corresponding value (the so-called metamethod, which should be a function) to compute the sum.
Each table in Lua may have its own metatable. (As we will see later, userdata also can have metatables.) Lua always create new tables without metatables:
t = {}
print(getmetatable(t)) --> nil
We can use setmetatable to set or change the metatable of any table:
t1 = {}
setmetatable(t, t1)
assert(getmetatable(t) == t1)
Any table can be the metatable of any other table; a group of related tables may share a common metatable (which describes their common behavior); a table can be its own metatable (so that it describes its own individual behavior). Any configuration is valid.翻译过来就是，Lua的table不支持表之间的操作，如表之间的比较、表之间的相加、调用一个表，而Lua的metatable给我们提供了一种修改表行为的方式，如，我们可以进行表的加操作（如果他们元表的__add field元方法被定义了），对于元表来说任何表可以拿任何表作为自己的元表，甚至一个表可以定义自己为元表（即table和metatable的关系十分的松散），那么实际元表和元方法的结构、实际用的时候流程是怎样的呢，我们通过代码来看:
第一步，我们需要了解Lua里面的操作码极其含义，以OP_GETTABLE和OP_CALL为例
/*
** R(x) - register
** Kst(x) - constant (in constant table)
** RK(x) == if ISK(x) then Kst(INDEXK(x)) else R(x)
*/
typedef enum {
/*----------------------------------------------------------------------
name args description
------------------------------------------------------------------------*/
OP_GETTABLE, /* A B C R(A) := R(B)[RK(C)] */
} OpCode;
void luaV_execute(lua_State* L) {
CallInfo* ci = L->ci;
ci->callstatus |= CIST_FRESH; /* fresh invocation of 'luaV_execute" */
newframe: /* reentry point when frame changes (call/return) */
lua_assert(ci == L->ci);
cl = clLvalue(ci->func); /* local reference to function's closure */
k = cl->p->k; /* local reference to function's constant table */
base = ci->u.l.base; /* local copy of function's base */
/* main loop of interpreter */
for (;;) {
Instruction i;
StkId ra;
vmfetch();
vmdispatch(GET_OPCODE(i)) {
vmcase(OP_GETTABLE) {
StkId rb = RB(i);
TValue* rc = RKC(i);
gettableProtected(L, rb, rc, ra);
vmbreak;
}
}
}
}
/*
** Finish the table access 'val = t[key]'.
** if 'slot' is NULL, 't' is not a table; otherwise, 'slot' points to
** t[k] entry (which must be nil).
*/
void luaV_finishget(lua_State* L, const TValue* t, TValue* key, StkId val, const TValue* slot) {
for (loop = 0; loop < MAXTAGLOOP; loop++) {
if (slot == NULL) { /* 't' is not a table? */
lua_assert(!ttistable(t));
tm = luaT_gettmbyobj(L, t, TM_INDEX);
if (ttisnil(tm))
luaG_typeerror(L, t, "index"); /* no metamethod */
/* else will try the metamethod */
} else { /* 't' is a table */
lua_assert(ttisnil(slot));
tm = fasttm(L, hvalue(t)->metatable, TM_INDEX); /* table's metamethod */
if (tm == NULL) { /* no metamethod? */
setnilvalue(val); /* result is nil */
return;
}
/* else will try the metamethod */
}
if (ttisfunction(tm)) { /* is metamethod a function? */
luaT_callTM(L, tm, t, key, val, 1); /* call it */
return;
}
t = tm; /* else try to access 'tm[key]' */
if (luaV_fastget(L, t, key, slot, luaH_get)) { /* fast track? */
setobj2s(L, val, slot); /* done */
return;
}
/* else repeat (tail call 'luaV_finishget') */
}
luaG_runerror(L, "'__index' chain too long; possible loop");
}1）枚举OpCode定义了Lua规定的各种操作码，其中OP_GETTABLE表示表的访问，也是我们对表最常用的操作之一;
2）luaV_execute，对于Lua来说，最终脚本的操作会被封装为并进入到luaV_execute接口通过GET_OPCODE的返回值进行分发;
3）以OP_GETTABLE为例，注释部分说明了其格式为，根据key从表中获取数据存入到寄存器中，最终会走到接口luaV_finishget;
4）从接口可以看到先通过luaH_get从自己的表里面取，若是取到则直接返回，否则走下一步;
5）若是原来表里面没有即slot为null，则看下metable是否为空且定义了__index元方法（TM_INDEX），若定义了，从里面找到对应的项，找出来看是不是方法（ttisfunction）是的话，就执行调用操作并把结果赋值给val，否则从表里面取出对应的数据（luaV_fastset）;
从上面流程，我们可以总结如下流程（还是以__index元方法为例）：
对于任意一个Lua的table，我们可以通过接口setmetatable为其设置一个metatable；当我们尝试在table里面取一个key1的值时，会被封装为OP_GETTABLE事件分发到对应的处理接口，处理接口分两步进行操作一个是本table有的值，则直接访问，否则访问metatable的__index表项（调用的时候参数设置为TM_INDEX），可以是一个表，也可以是一个方法（也就是说在Lua的table里面，和我们在setmetatable里面__index设置上的metatable之间，实际是中间隔了一个Table数据结构metatable指针指向的表，这个表里面含有index、newindex、call等一系列已经定义好的key）。
未完待续。
参考资料
