首页 > 代码库 > lua.5.2.3源码阅读(04)：Table结构基本操作
lua.5.2.3源码阅读(04)：Table结构基本操作
table(lobject.h)的结构定义：
1 // TKey结构是一个链表结构，用来存储hash相同 2 // 的所有key，value对结构。 3 typedef union TKey { 4 struct { 5 TValuefields; // key值 6 struct Node *next; // 指向像一个相同hash值的key值； 7 } nk; 8 TValue tvk; //尾部的key值； 9 } TKey;10 11 // (key，value）对结构，通过key计算获得的相同hash的Node保存在一个链表中；12 typedef struct Node {13 TValue i_val;14 TKey i_key;15 } Node;16 17 18 typedef struct Table {19 CommonHeader;20 lu_byte flags; 21 lu_byte lsizenode; // Node数量 = 2^lsizenode 个Node结构22 struct Table *metatable;23 TValue *array; // 数组方式存储的Node结构24 Node *node; // Node数组，数组的索引通过Key计算hash获取25 Node *lastfree; // 指向Node数组中的最后一个空闲Node，初始化为Node数组的最后一个值26 GCObject *gclist;27 int sizearray; // 数组方式储存的Node结构数量，即数组大小28 } Table;
通过上述结构：
a、Table作为数组使用是，获取较好的性能；
b、避免采用数组时，太多的空间浪费；
c、不过，通过后续的分析，还是将Table采用单一结构来使用（数组或者Map）可以获取更好的访问性能；
接下来分析Table的一些函数：
1、Table的创建和销毁；
2、Table的读取和写入；
3、Table的内存数组和Hash表的动态管理；
Table的创建和销毁；
Table *luaH_new (lua_State *L) { Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h; t->metatable = NULL; t->flags = cast_byte(~0); t->array = NULL; t->sizearray = 0; setnodevector(L, t, 0); return t;}void luaH_free (lua_State *L, Table *t) { if (!isdummy(t->node)) luaM_freearray(L, t->node, cast(size_t, sizenode(t))); luaM_freearray(L, t->array, t->sizearray); luaM_free(L, t);}
a、luaC_newobj函数生成一个大小为Table的内存块，同TString的方式一样，在申请内存的过程中，构造GCObject结构，
并且把Table挂在到lua_State中的全局gc object列表中，用于垃圾回收；
b、Table的删除也很简单：首先释放Hash表（实际上也是连续内存）、然后释放数组、最后释放Table结构指针指向的内存；
c、luaH_free函数本身不负责从gc链表中删除；
Table的读取和写入：
LUAI_FUNC const TValue *luaH_getint (Table *t, int key);
LUAI_FUNC void luaH_setint (lua_State *L, Table *t, int key, TValue *value);
LUAI_FUNC const TValue *luaH_getstr (Table *t, TString *key);
LUAI_FUNC const TValue *luaH_get (Table *t, const TValue *key);
LUAI_FUNC TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key);
LUAI_FUNC TValue *luaH_set (lua_State *L, Table *t, const TValue *key);
首先看int的读取和写入：
1 /* 2 ** search function for integers 3 */ 4 const TValue *luaH_getint (Table *t, int key) { 5 /* (1 <= key && key <= t->sizearray) */ 6 if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) 7 return &t->array[key-1]; 8 else { 9 lua_Number nk = cast_num(key);10 Node *n = hashnum(t, nk);11 do { /* check whether `key‘ is somewhere in the chain */12 if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))13 return gval(n); /* that‘s it */14 else n = gnext(n);15 } while (n);16 return luaO_nilobject;17 }18 }19 20 void luaH_setint (lua_State *L, Table *t, int key, TValue *value) {21 const TValue *p = luaH_getint(t, key);22 TValue *cell;23 if (p != luaO_nilobject)24 cell = cast(TValue *, p);25 else {26 TValue k;27 setnvalue(&k, cast_num(key));28 cell = luaH_newkey(L, t, &k);29 }30 setobj2t(L, cell, value);31 }
读取过程：
a、判断key的值是否小于Table中sizearray数组大小；
b、如果小于数组大小，直接返回数组key所在的数组值；
c、如果大于数组大小，通过整型hashnum函数计算索引，并获取Node结构；
d、如果Node为空，则为没有该key对应的TValue；
e、如果Node非空，则从Node链表中遍历，查找和Key相同的Node，并返回TValue；
写入过程：
a、首先查找Table中是否包含key的元素，通过读取函数获取；
b、如果包括，则直接返回key对应的value，并设置int；
c、如果不包括，则新生成key，并把TValue返回，设置int值；
d、实际上在生成key的过程中，可能会内部调整内存结构，后续分析；
通过Table的读取或写入：
1 const TValue *luaH_get (Table *t, const TValue *key) { 2 switch (ttype(key)) { 3 case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key)); 4 case LUA_TNIL: return luaO_nilobject; 5 case LUA_TNUMBER: { 6 int k; 7 lua_Number n = nvalue(key); 8 lua_number2int(k, n); 9 if (luai_numeq(cast_num(k), n)) /* index is int? */10 return luaH_getint(t, k); /* use specialized version */11 /* else go through */12 }13 default: {14 Node *n = mainposition(t, key);15 do { /* check whether `key‘ is somewhere in the chain */16 if (luaV_rawequalobj(gkey(n), key))17 return gval(n); /* that‘s it */18 else n = gnext(n);19 } while (n);20 return luaO_nilobject;21 }22 }23 }24 25 TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {26 const TValue *p = luaH_get(t, key);27 if (p != luaO_nilobject)28 return cast(TValue *, p);29 else return luaH_newkey(L, t, key);30 }31 32 static Node *mainposition (const Table *t, const TValue *key) {33 switch (ttype(key)) {34 case LUA_TNUMBER:35 return hashnum(t, nvalue(key));36 case LUA_TLNGSTR: {37 TString *s = rawtsvalue(key);38 if (s->tsv.extra == 0) { /* no hash? */39 s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash);40 s->tsv.extra = 1; /* now it has its hash */41 }42 return hashstr(t, rawtsvalue(key));43 }44 case LUA_TSHRSTR:45 return hashstr(t, rawtsvalue(key));46 case LUA_TBOOLEAN:47 return hashboolean(t, bvalue(key));48 case LUA_TLIGHTUSERDATA:49 return hashpointer(t, pvalue(key));50 case LUA_TLCF:51 return hashpointer(t, fvalue(key));52 default:53 return hashpointer(t, gcvalue(key));54 }55 }
a、读取函数和上述的int的主要区别就是区分不同的类型采用不同的hash的方式（注意mainposition函数）；
b、指针直接将地址采用int方式hash；
c、字符串的访问直接采用hash查找，实际上只有计算hash的时候较耗时，后续访问比c\c++中更快；
d、写入函数基本上和int一模一样；
下一篇详细说明一下Table结构内存增长时的管理方式。
lua.5.2.3源码阅读(04)：Table结构基本操作