目录
Table – 数据结构实现
Table – 初始化luaH_new
Table – 释放操作luaH_free
Table – 设值操作luaH_set&luaH_setint
Table – 扩容操作luaH_resize
Lua语言中，Table结构类型是比较强大的一个存在。和PHP的数组有些类似。比较万能和强大。
Lua语言中Table的具体实现，主要在ltable.c文件中。
Lua语言的Table有两个特性：
- Table使用关联数组，可以用任意类型来作为数组的索引键值
- Table没有固定大小，可以动态扩容。
先看一下Lua中，如何使用Table：
fruits = {"banana","orange","apple"}
a = {x=12,mutou=99,[3]="hello"}
local a = {
{x = 1,y=2},{x = 3,y = 10}}
mt = {}
mt = {a=10,b="123"}
mt.a = 110 //使用.号
mt["c"]=129 //使用索引Table – 数据结构实现
Lua的Table实现，主要由两种类型组成：
- 数组节点形式：TValue *array，通过数组方式，实现值的存储。数组方式，要求table的key必须为数字，并且数字小于数组长度sizearray
- Hash节点形式：Node *node，通过Hash表的方式来存储Node节点，Node节点包含key和value。前面已经说过，key和value可以为任意类型。解决hash冲突，通过TKey结构体中的next链表指针实现。
其中Node *node; 为Hash节点的头部，Node *lastfree为 hash节点，最后一个空闲节点。
key和value最终指向TValue结构，该结构支持多种类型，所以Table可以用任意类型来作为key和value。
/**
* Table数据结构，分两种存储类型：数组节点和hash节点
* 数组节点：sizearray为数字长度，一般存储key值在长度范围内的结果集
* hash节点：k=>v结构，能够存储各类复杂对象结构
*
* LUA语言用法：
* 数组节点：fruits = {"banana","orange","apple"}
* hash节点：a = {x=12,mutou=99,[3]="hello"}
* table中带table结构：local a = {
{x = 1,y=2},{x = 3,y = 10}}
*/
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; //hash节点，node指向hash表的起始位置
Node *lastfree; /* hash节点，最后一个空闲节点 any free position is before this position */
struct Table *metatable; //元表，重载操作需要用
GCObject *gclist;
} Table;
/**
* 节点格式 k=>v
* 节点结构：a = {x=12,mutou=99,[3]="hello"}
*/
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
typedef union TKey {
struct {
TValuefields;
int next; /* 链表 管理Hash Node，用于处理hash 冲突 for chaining (offset for next node) */
} nk;
TValue tvk;
} TKey;
Table – 初始化luaH_new
Table的初始化，主要对数组节点和hash节点两个数据结构进行内存分配和初始化。
一般Table的初始化函数为：luaH_new。该函数是真正意义上的初始化，仅仅对Table数据结构进行了初始化，但是并没有初始化array和node。需要通过luaH_resize函数，针对数组节点和hash节点进行内容分配和初始化。
在lapi.c文件中，有一个函数lua_createtable，封装了Table的整个初始化的全过程。一般完成使用table，调用该函数会更加合理。该函数默认指定了数组节点和Hash节点的长度。
/**
* 创建一个table，固定长度，并将之放在栈顶.
*
* narray是该table数组部分的长度
* nrec是该table hash部分的长度.
*/
LUA_API void lua_createtable (lua_State *L, int narray, int nrec) {
Table *t;
lua_lock(L);
t = luaH_new(L);
sethvalue(L, L->top, t);
api_incr_top(L);
if (narray > 0 || nrec > 0)
luaH_resize(L, t, narray, nrec);
luaC_checkGC(L);
lua_unlock(L);
}
/**
* 创建一个table
* table内容由luaC_newobj创建分配，并且会挂载到global_State->frealloc上统一管理
*
* Table使用方式：
* 数组结构：fruits = {"banana","orange","apple"}
* 节点结构：a = {x=12,mutou=99,[3]="hello"}
* table中带table结构：local a = {
{x = 1,y=2},{x = 3,y = 10}}
*/
Table *luaH_new (lua_State *L) {
GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
Table *t = gco2t(o); //分配一个Table类型的内容，对象在 global_State->frealloc 上管理
t->metatable = NULL;
t->flags = cast_byte(~0);
t->array = NULL;
t->sizearray = 0;
setnodevector(L, t, 0); //设置节点空间
return t;
}Table – 释放操作luaH_free
Table的释放相对比较简单，只要对对应的内存块进行释放即可。
由于Table表的内存分配都是走Lua内部统一的内存管理机制（lmem.c），分配的时候会调用luaM_*方法，所以在释放Table的时候，统一走释放函数即可。Lua的内容都是由全局内存分配器来管理的global_State->frealloc，这里的细节下一章再详解。
/**
* 销毁一个Table
* 1. 先释放node节点
* 2. 再释放array数组
*/
void luaH_free (lua_State *L, Table *t) {
if (!isdummy(t))
luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
luaM_freearray(L, t->array, t->sizearray);
luaM_free(L, t);
}Table – 设值操作luaH_set&luaH_setint
设值操作主要有两个函数：luaH_set和luaH_setint
- luaH_set主要在table上设置一个值，并返回Value对象；
- luaH_setint主要在Table上设置key为数字类型的节点
两者都会优先去判断，key值是否是数字类型，并且数字小于数组的长度，则走数组节点
否则都会调用luaH_newkey，走Hash节点设值。
/*
** beware: when using this function you probably need to check a GC
** barrier and invalidate the TM cache.
** 在Table上设置一个值，然后返回TValue对象
**
** 说明：
** 优先在t->array数组上查询，是否有节点可以存储，如果key小于arraysize，则放置在array上
** 调用luaH_newkey，在table上寻找可以设置key的node节点，设置成功后，返回Node->i_val
** node节点k=v形式
*/
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);
}
/**
* 在Table上设置key为数字类型的节点
* 说明：
* 1. 优先在t->array数组上查询，是否有节点可以存储，如果key小于arraysize，则放置在array上
* 2. 如果数字大于arraysize，则在Node节点上处理
* 3. 如果没有查询到p，则调用luaH_newkey创建一个新的Node节点用于存储value
*/
void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
const TValue *p = luaH_getint(t, key);
TValue *cell;
if (p != luaO_nilobject)
cell = cast(TValue *, p);
else {
TValue k;
setivalue(&k, key);
cell = luaH_newkey(L, t, &k);
}
setobj2t(L, cell, value);
}luaH_newkey相对会复杂一些。需要取检查hash节点，并且判断是否有hash冲突，如果节点数量不够并且要扩容等一系列操作。
/*
** 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.
** 插入一个新key到hash 表中，首先，检查key对应的main position是否是空的，如果不是，
则检查冲突的node是不是main position，如果不是，就应该将冲突的node移到一个新的空位置，
将新key放到main position。如果冲突的点就已经是main position，则将新key放到一个空白点
*/
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"); //检查key值是否为空值
else if (ttisfloat(key)) { //浮点类型，如果可以转int的话，强制转成int
lua_Integer k;
if (luaV_tointeger(key, &k, 0)) { /* does index fit in an integer? */
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); //拿到key 可以存放的的node
/* 如果存在 */
if (!ttisnil(gval(mp)) || isdummy(t)) { /* 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(t));
othern = mainposition(t, gkey(mp));
if (othern != mp) { /* is colliding node out of its main position? 此处需要解决hash冲突*/
/* yes; move colliding node 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 node 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 node is in its own main position */
/* new node 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); //拷贝到node上
luaC_barrierback(L, t, key);
lua_assert(ttisnil(gval(mp)));
return gval(mp); //返回Tvalue方法 Node->i_val
}
Table – 扩容操作luaH_resize
扩容操作主要是luaH_resize函数，该函数可以设定数组节点的大小和Hash节点大小。
具体的扩容操作就不多说了，相对还比较简单。
/**
* 重新设置Table的大小
* 说明：luaH_new方法仅仅是初始化了一个Table，真正Table容器大小，需要调用此方法实现
*
* nasize：数组节点的大小
* nhsize：hash节点的大小
*/
void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
unsigned int nhsize) {
unsigned int i;
int j;
AuxsetnodeT asn;
unsigned int oldasize = t->sizearray;
int oldhsize = allocsizenode(t);
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 */
asn.t = t; asn.nhsize = nhsize;
if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) { /* mem. error? */
setarrayvector(L, t, oldasize); /* array back to its original size */
luaD_throw(L, LUA_ERRMEM); /* rethrow memory error */
}
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 = 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 (oldhsize > 0) /* not the dummy node? */
luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */
}