table在里面数据方式比较直观，但是算法很复杂。一些算法的坑会慢慢补上。
先总括下table的数据结构：
1)由一个hash表和一个数组构成,当插入一个小标元素，会根据当前数组的大小决定插入哪儿
2)hash表上会有冲突，通过一个链表的形式组织冲突的元素
3)通过源码，我们还能得到的是一些table的使用技巧方式，尤其是在大数据量上的效率开销
4)我在分析的方法上是这样的：首先分析luaH_getn这个函数，通过获取的方式来对table存储的方式有个大致了解；然后分析tinsert，两者进行迭代阅读
Cpp代码
//ltable.c
int luaH_getn (Table *t)
{
//array数组个数
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1]))
{
/* there is a boundary in the array part: (binary) search for it */
unsigned int i = 0;
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
/* else must find a boundary in hash part */
else if (t->node == dummynode) /* hash part is empty? */
return j; /* that is easy... */
else return unbound_search(t,j);
}
//ltable.c
int luaH_getn (Table *t)
{
//array数组个数
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1]))
{
/* there is a boundary in the array part: (binary) search for it */
unsigned int i = 0;
while (j - i > 1)
{
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
/* else must find a boundary in hash part */
else if (t->node == dummynode) /* hash part is empty? */
return j; /* that is easy... */
else return unbound_search(t,j);
}
可以看出，对个数的统计方式有3种
1.array个数大于0，并且末尾的元素为空。比如{1,2,3,nil},返回值为3
2.array个数大于0，末尾不为空。比如t={1,nil,3},返回为4
3.unbound_search方式的统计.需要2个条件
1)j<=0,t->node!=dummynode
2)j>0,t->array[j - 1]不为空，t->node!=dummynode
并且还可以得到的信息是，
1.array是个数组，并且元素的排列上是紧密的。
2.即使末尾为空，也算是table的空间，但是返回的个数略有不同
3.array的存放上有一定的阀值，如果超出按链表方式存放
4.统计的方式(while)是个二分的查找
Cpp代码
//ltable.c
static int unbound_search (Table *t,unsigned int j)
{
unsigned int i = j; /* i is zero or a present index */
j++;
/* find `i' and `j' such that i is present and j is not */
while (!ttisnil(luaH_getnum(t,j)))
{
i = j;
j *= 2;
if (j > cast(unsigned int,MAX_INT))
{ /* overflow? */
/* table was built with bad purposes: resort to linear search */
i = 1;
while (!ttisnil(luaH_getnum(t,i))) i++;
return i - 1;
}
}
/* now do a binary search between them */
while (j - i > 1)
{
unsigned int m = (i+j)/2;
if (ttisnil(luaH_getnum(t,m))) j = m;
else i = m;
}
return i;
}
//ltable.c
static int unbound_search (Table *t,unsigned int j)
{
unsigned int i = j; /* i is zero or a present index */
j++;
/* find `i' and `j' such that i is present and j is not */
while (!ttisnil(luaH_getnum(t,j)))
{
i = j;
j *= 2;
if (j > cast(unsigned int,MAX_INT))
{ /* overflow? */
/* table was built with bad purposes: resort to linear search */
i = 1;
while (!ttisnil(luaH_getnum(t,i))) i++;
return i - 1;
}
}
/* now do a binary search between them */
while (j - i > 1)
{
unsigned int m = (i+j)/2;
if (ttisnil(luaH_getnum(t,m))) j = m;
else i = m;
}
return i;
}
观察第一个while,有2种情况
1.对j进行判断，i等于j扩大两倍前的值。如果luaH_getnum取到的值为空，则退出循环
2.如果j扩大两倍大于MAX_INT时，则以i从1开始，线性的查找。(是否可以优化为从j/4开始？)
经过第一个while后，取到下面的情况。
有值，有值，有值(i在这)，有值(下一轮while要查找的目标)，空值，空值(j可能在这)
继续二分查找，找到最末尾有值的下标。然后返回。
那么这个函数的功能就可以总结为，先从1-MAX_INT中探测到一个范围，然后从这个范围中查找
末尾的有值节点
继续跟入luaH_getnum
Cpp代码
//ltable.c
/*
** search function for integers
*/
const TValue *luaH_getnum (Table *t,int key)
{
/* (1 <= key && key <= t->sizearray) */
/*
cast很熟悉了，值转换.
从这个判断可以得到信息是sizearray可以存储一定量的数据，
如果超出则用其他方式存储
*/
if (cast(unsigned int,key-1) < cast(unsigned int,t->sizearray))
return &t->array[key-1];
else
{
lua_Number nk = cast_num(key);
Node *n = hashnum(t,nk);
do { /* check whether `key' is somewhere in the chain */
/*
这里也预读到一些信息
1.基本上不是为了出错校验
2.看来是和插入的算法有关。插入的算法可能会导致一些重复
3.能存多少数据，跟nk的类型有关。虽然nk是double,但是小数能否用到
还得继续跟。否则就是一个2^32的总数了
*/
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)),nk))
return gval(n); /* that's it */
else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
//ltable.c
/*
** search function for integers
*/
const TValue *luaH_getnum (Table *t,int key)
{
/* (1 <= key && key <= t->sizearray) */
/*
cast很熟悉了，值转换.
从这个判断可以得到信息是sizearray可以存储一定量的数据，
如果超出则用其他方式存储
*/
if (cast(unsigned int,t->sizearray))
return &t->array[key-1];
else
{
lua_Number nk = cast_num(key);
Node *n = hashnum(t,nk);
do
{ /* check whether `key' is somewhere in the chain */
/*
这里也预读到一些信息
1.基本上不是为了出错校验
2.看来是和插入的算法有关。插入的算法可能会导致一些重复
3.能存多少数据，跟nk的类型有关。虽然nk是double,但是小数能否用到
还得继续跟。否则就是一个2^32的总数了
*/
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)),nk))
return gval(n); /* that's it */
else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
else段里走的流程大概是，根据nk从hashnum里面取到Node,然后进行判断，如果不符合则next个Node.
看来hashnum是个算法。先把gkey,nvalue,luai_numeq几个宏和Node结构体拆开看看
Cpp代码?
//ltable.c
#define gkey(n) (&(n)->i_key.nk)
#define gval(n) (&(n)->i_val)
#define gnext(n) ((n)->i_key.nk.next)
//luaconf.h
#define luai_numeq(a,b) ((a)==(b))
//lobject.h
#define nvalue(o) check_exp(ttisnumber(o),(o)->value.n)
//lobject.h
#define TValuefields Value value; int tt
typedef union TKey {
struct {
TValuefields;
struct Node *next; /* for chaining */
} nk;
TValue tvk;
} TKey;
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
//ltable.c
#define gkey(n) (&(n)->i_key.nk)
#define gval(n) (&(n)->i_val)
#define gnext(n) ((n)->i_key.nk.next)
//luaconf.h
#define luai_numeq(a,b) ((a)==(b))
//lobject.h
#define nvalue(o) check_exp(ttisnumber(o),(o)->value.n)
//lobject.h
#define TValuefields Value value; int tt
typedef union TKey {
struct {
TValuefields;
struct Node *next; /* for chaining */
} nk;
TValue tvk;
} TKey;
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
TValuefields;其实也是个TValue的结构体。用宏扩展开，可以少一层访问的封装。或者可以看成是
TValue多加了个Node *Next,这样可以保证和ttisnumber兼容访问。有了这些，那么可以对这句重新
认识
Cpp代码?
//hashnum表示一种算法，取到目标节点
Node *n = hashnum(t,nk);
do
{
/*
算法导致的节点可能会多个，则根据key里的n来和nk校验
这个就很好理解了，比如1-100算到的因子都是20。20这个node下可能挂了100个节点。然后
依次比较取出正确的。
*/
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)),nk))
}while(n)
//hashnum表示一种算法，取到目标节点
Node *n = hashnum(t,nk);
do
{
/*
算法导致的节点可能会多个，则根据key里的n来和nk校验
这个就很好理解了，比如1-100算到的因子都是20。20这个node下可能挂了100个节点。然后
依次比较取出正确的。
*/
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)),nk))
}while(n)
最后来看下hashnum算法
Cpp代码?
//lobject.h
#define twoto(x) (1<<(x))
#define sizenode(t) (twoto((t)->lsizenode))
//ltable.h
#define gnode(t,i) (&(t)->node[i])
//ltable.c
/*
** for some types,it is better to avoid modulus by power of 2,as
** they tend to have many 2 factors.
*/
/*
算法比想象中的简单。sizenode对table里的lsizenode取一个指数,在源代码也能找到这段注释:
lu_byte lsizenode; log2 of size of `node' array
-1表示0~(1<<(x)-1)范围，|1没弄明白什么意思。防止出现小于0的吗？
hashmod仅仅是为了大下标的处理。
*/
#define hashmod(t,n) (gnode(t,((n) % ((sizenode(t)-1)|1))))
//lobject.h
#define twoto(x) (1<<(x))
#define sizenode(t) (twoto((t)->lsizenode))
//ltable.h
#define gnode(t,i) (&(t)->node[i])
//ltable.c
/*
** for some types,as
** they tend to have many 2 factors.
*/
/*
算法比想象中的简单。sizenode对table里的lsizenode取一个指数,在源代码也能找到这段注释:
lu_byte lsizenode; log2 of size of `node' array
-1表示0~(1<<(x)-1)范围，|1没弄明白什么意思。防止出现小于0的吗？
hashmod仅仅是为了大下标的处理。
*/
#define hashmod(t,n) (gnode(t,((n) % ((sizenode(t)-1)|1))))
Cpp代码?
//跟调do..while里面的hashnum函数
static Node *hashnum (const Table *t,lua_Number n)
{
unsigned int a[numints];
int i;
if (luai_numeq(n,0)) /* avoid problems with -0 */
return gnode(t,0);
/*
lua_Number是个double型，这里是把n的高低4个字节相加，
作为去模的对象
*/
memcpy(a,&n,sizeof(a));
//#define numints cast_int(sizeof(lua_Number)/sizeof(int))
for (i = 1; i < numints; i++) a[0] += a[i];
return hashmod(t,a[0]);
}
//跟调do..while里面的hashnum函数
static Node *hashnum (const Table *t,lua_Number n)
{
unsigned int a[numints];
int i;
if (luai_numeq(n,0)) /* avoid problems with -0 */
return gnode(t,0);
/*
lua_Number是个double型，这里是把n的高低4个字节相加，
作为去模的对象
*/
memcpy(a,sizeof(a));
//#define numints cast_int(sizeof(lua_Number)/sizeof(int))
for (i = 1; i < numints; i++) a[0] += a[i];
return hashmod(t,a[0]);
}
那么luaH_getnum这个函数就很好理解了。首先判断传入的key是否满足当前sizearray,如果满足则返回。
否则可以看成一个大下标的存储，根据hashmod算法取到节点。
再回头总结下调用的源码文件架构
ltablib.c(getn)
ltablib.c(aux_getn)
lauxlib.h(luaL_getn)
lapi.c(lua_objlen)
lobject.h(hvalue)//hvalue很奇怪，从gc中取到table结构
ltable.c(luaH_getn)
另起段
ltable.c(luaH_getn)
lobject.h(ttisnil)
ltable.c(unbound_search)
lobject.h(ttisnil)
ltable.c(luaH_getnum)
limits.h(cast_num,cast)
ltable.h(gkey,gval,gnext)
ltable.c(hashnum)
ltable.c(hashmod)
ltable.h(gnode)
lobject.h(sizenode)
ltable.h(gnode)
luaconf.h(luai_numeq)
总结下第一回分析getn所得到的信息
1.table存储的方式有array,node
2.nil也算是一个元素（如果不是在末尾），并且常用二分法查找
3.node是通过一个取模方式，并且会重复。
接着继续分析tinsert函数
Cpp代码
//ltablib.c
static int tinsert (lua_State *L)
{
//调用的是getn,取回table的元素总数。
imt e = aux_getn(L,1) + 1; /* first empty element */
int pos; /* where to insert new element */
switch (lua_gettop(L))
{
case 2:
{ /* called with only 2 arguments */
pos = e; /* insert new element at the end */
break;
}
/*
如果插入的范围小于当前元素总数，则移出空位
*/
case 3:
{
int i;
pos = luaL_checkint(L,2); /* 2nd argument is the position */
if (pos > e) e = pis; /* `grow' array if necessary */
for (i = e; i > pis; i--)
{ /* move up elements */
lua_rawgeti(L,1,i+1);
lua_rawseti(L,i); /* t[i] = t[i-1] */
}
break;
}
default:
{
return luaL_error(L,"wrong number of arguments to " LUA_QL("insert"));
}
}
luaL_setn(L,e); /* new size */
lua_rawseti(L,pos); /* t[pos] = v */
return 0;
}
//ltablib.c
static int tinsert (lua_State *L)
{
//调用的是getn,取回table的元素总数。
imt e = aux_getn(L,1) + 1; /* first empty element */
int pos; /* where to insert new element */
switch (lua_gettop(L))
{
case 2:
{ /* called with only 2 arguments */
pos = e; /* insert new element at the end */
break;
}
/*
如果插入的范围小于当前元素总数，则移出空位
*/
case 3:
{
int i;
pos = luaL_checkint(L,2); /* 2nd argument is the position */
if (pos > e) e = pis; /* `grow' array if necessary */
for (i = e; i > pis; i--)
{ /* move up elements */
lua_rawgeti(L,i+1);
lua_rawseti(L,i); /* t[i] = t[i-1] */
}
break;
}
default:
{
return luaL_error(L,"wrong number of arguments to " LUA_QL("insert"));
}
}
luaL_setn(L,e); /* new size */
lua_rawseti(L,pos); /* t[pos] = v */
return 0;
}
tinsert函数很简单，重点跟调lua_rawseti
Cpp代码?
//lapi.c??
LUA_API void lua_rawseti (lua_State *L,int idx,int n) {??
StkId o;??
lua_lock(L);??
api_checknelems(L,1);??
o = index2adr(L,idx);??
api_check(L,ttistable(o));??
/*?
L->top上的排列为 table,插入的位置，插入的值.?
L->top-1不知道取的啥值，略过。跟调发现取的是插入的值。?
luaH_setnum的名字比较奇怪，按道理叫luaH_getnum比较合适，不过也间接?
的透露了信息，?
1.首先要确保空间节点的存在?
2.对于空间必然有一个扩展的操作，而不是预先安排?
*/?
setobj2t(L,luaH_setnum(L,hvalue(o),n),L->top-1);??
//这段先不管??
luaC_barriert(L,L->top-1);??
//栈减1??
L->top--;??
lua_unlock(L);??
}?
//lapi.c
LUA_API void lua_rawseti (lua_State *L,int n) {
StkId o;
lua_lock(L);
api_checknelems(L,1);
o = index2adr(L,idx);
api_check(L,ttistable(o));
/*
L->top上的排列为 table,插入的位置，插入的值.
L->top-1不知道取的啥值，略过。跟调发现取的是插入的值。
luaH_setnum的名字比较奇怪，按道理叫luaH_getnum比较合适，不过也间接
的透露了信息，
1.首先要确保空间节点的存在
2.对于空间必然有一个扩展的操作，而不是预先安排
*/
setobj2t(L,L->top-1);
//这段先不管
luaC_barriert(L,L->top-1);
//栈减1
L->top--;
lua_unlock(L);
}
继续走luaH_setnum(L,n)
Cpp代码?
//ltable.c??
//这个函数叫setnum,??
TValue *luaH_setnum (lua_State *L,Table *t,int key) {??
/*?
看到了吧，会先尝试一个获取。取不到则进行扩展key的节点?
luaH_getnum前面分析过了，这里略过?
*/?
const TValue *p = luaH_getnum(t,key);??
if (p != luaO_nilobject)??
return cast(TValue *,p);??
else {??
TValue k;??
setnvalue(&k,cast_num(key));??
return newkey(L,t,&k);??
}??
}?
//ltable.c
//这个函数叫setnum,
TValue *luaH_setnum (lua_State *L,int key) {
/*
看到了吧，会先尝试一个获取。取不到则进行扩展key的节点
luaH_getnum前面分析过了，这里略过
*/
const TValue *p = luaH_getnum(t,key);
if (p != luaO_nilobject)
return cast(TValue *,p);
else {
TValue k;
setnvalue(&k,cast_num(key));
return newkey(L,&k);
}
}
也很简单，继续走newkey
Cpp代码?
//ltable.c??
/*?
** 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.?
*/?
/*?
有点悲剧，这个函数看来比较复杂，否则也不会这么多注释。段首所透露的信息大概如下：?
1.key所对应的hash节点可能存在可能不存在(也就是冲突)?
2.如果存在，那么有2个点需要互斥：main position、an empty place。暂时不知道
这2个所指什么意思?
3.通过几个if not,otherwise可知，main position只能有一个key占着，剩下的要去
an empty place?
4.虽然key所对应的hash节点在，但是main position不一定有key.?
*/?
static TValue *newkey (lua_State *L,const TValue *key) {??
/*?
又冒了一个mainposition出来，跟调一下发现是通过hash算法得到的节点?
上文跟过，不细展开了?
*/?
Node *mp = mainposition(t,key);??
/*?
!ttisnil(gval(mp))表示一个新的节点，?
mp == dummynode同上。?
先解决if之外的。之外的意思很简单，把值给新得到的节点。?
对应Node结构体查看?
typedef struct Node {?
TValue i_val;???
TKey i_key;?? //把key记录在i_key结构里边?
} Node;?
继续刨下面难的那段?
*/?
if (!ttisnil(gval(mp)) || mp == dummynode) {??
Node *othern;??
/*?
getfreepos里面操作的是t->lastfree值，怎么来的不知道。?
只知道也是个指针数组???????
*/?
Node *n = getfreepos(t);? /* get a free place */?
if (n == NULL) {? /* cannot find a free place? */?
/*?
如果为空，那么rehash一个值，这个值相对比较NB，?
不然luaH_set又要执行newkey。我把这段放到了后面，大家?
可以先跳到后面1.1?
*/????
rehash(L,key);? /* grow table */?
return luaH_set(L,key);? /* re-insert key into grown table */?
}??
lua_assert(n != dummynode);??
/*?
第一个if可以反过来分析：?
最终目的是把mp赋给n?
n是作为一个末尾节点。说明这是一个链表结构?
othern节点是通过key2tval宏取得的，该宏扩展开来&(n)->i_key.tvk。可以看成是key
的value值。?
while()语句可以得出一个互斥信息:通过key算出来的mp是同个节点，因此把一样的节点
串起来。?
*/?
othern = mainposition(t,key2tval(mp));??
if (othern != mp) {? /* is colliding node out of its main position? */?
/* yes; move colliding node into free position */?
while (gnext(othern) != mp) othern = gnext(othern);? /* find previous */?
gnext(othern) = n;? /* redo the chain with `n' in place of `mp' */?
*n = *mp;? /* copy colliding node into free pos. (mp->next also goes) */?
gnext(mp) = NULL;? /* now `mp' is free */?
setnilvalue(gval(mp));??
}??
/*?
这段就很简单了，说明当前还没有插入其他的相同算法key，?
则n做为链表头?
*/?
else {? /* colliding node is in its own main position */?
/* new node will go into free position */?
gnext(n) = gnext(mp);? /* chain new position */?
gnext(mp) = n;??
mp = n;??
}??
}??
gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;??
luaC_barriert(L,key);??
lua_assert(ttisnil(gval(mp)));??
return gval(mp);??
}?
//ltable.c
/*
** 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.
*/
/*
有点悲剧，这个函数看来比较复杂，否则也不会这么多注释。段首所透露的信息大概如下：
1.key所对应的hash节点可能存在可能不存在(也就是冲突)
2.如果存在，那么有2个点需要互斥：main position、an empty place。暂时不知道
这2个所指什么意思
3.通过几个if not,otherwise可知，main position只能有一个key占着，剩下的要去
an empty place
4.虽然key所对应的hash节点在，但是main position不一定有key.
*/
static TValue *newkey (lua_State *L,const TValue *key) {
/*
又冒了一个mainposition出来，跟调一下发现是通过hash算法得到的节点
上文跟过，不细展开了
*/
Node *mp = mainposition(t,key);
/*
!ttisnil(gval(mp))表示一个新的节点，
mp == dummynode同上。
先解决if之外的。之外的意思很简单，把值给新得到的节点。
对应Node结构体查看
typedef struct Node {
TValue i_val;?
TKey i_key;?? //把key记录在i_key结构里边
} Node;
继续刨下面难的那段
*/
if (!ttisnil(gval(mp)) || mp == dummynode) {
Node *othern;
/*
getfreepos里面操作的是t->lastfree值，怎么来的不知道。
只知道也是个指针数组??? ?
*/
Node *n = getfreepos(t);? /* get a free place */
if (n == NULL) {? /* cannot find a free place? */
/*
如果为空，那么rehash一个值，这个值相对比较NB，
不然luaH_set又要执行newkey。我把这段放到了后面，大家
可以先跳到后面1.1
*/?
rehash(L,key);? /* grow table */
return luaH_set(L,key);? /* re-insert key into grown table */
}
lua_assert(n != dummynode);
/*
第一个if可以反过来分析：
最终目的是把mp赋给n
n是作为一个末尾节点。说明这是一个链表结构
othern节点是通过key2tval宏取得的，该宏扩展开来&(n)->i_key.tvk。可以看成是key
的value值。
while()语句可以得出一个互斥信息:通过key算出来的mp是同个节点，因此把一样的节点
串起来。
*/
othern = mainposition(t,key2tval(mp));
if (othern != mp) {? /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
while (gnext(othern) != mp) othern = gnext(othern);? /* find previous */
gnext(othern) = n;? /* redo the chain with `n' in place of `mp' */
*n = *mp;? /* copy colliding node into free pos. (mp->next also goes) */
gnext(mp) = NULL;? /* now `mp' is free */
setnilvalue(gval(mp));
}
/*
这段就很简单了，说明当前还没有插入其他的相同算法key，
则n做为链表头
*/
else {? /* colliding node is in its own main position */
/* new node will go into free position */
gnext(n) = gnext(mp);? /* chain new position */
gnext(mp) = n;
mp = n;
}
}
gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
luaC_barriert(L,key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}
Cpp代码?
/*?
这段函数算法可以暂时不分析得非常非常细致。我们可以先用黑盒测试它的一些行为。?
比如用insert插入的两次下标不在同个位置，那么getn得到的是0；如果插入的位置是序列
的，那么rehash会认为是排列紧密的，getn得到是2。可以看出，这个函数主要是个重新?
归纳和分配节点算法的东西。后面留个坑，慢慢补。那么table中插入元素的排列位置如下图:?
*/?
static void rehash (lua_State *L,const TValue *ek) {??
int nasize,na;??
int nums[MAXBITS+1];? /* nums[i] = number of keys between 2^(i-1) and 2^i */?
int i;??
int totaluse;??
//MAXBITS为 26。清零??
for (i=0; i<=MAXBITS; i++) nums[i] = 0;? /* reset counts */?
//小段1.1.1,计算这个数组中已有的元素个数??
nasize = numusearray(t,nums);? /* count keys in array part */?
totaluse = nasize;? /* all those keys are integer keys */?
//小段1.1.2,计算已使用的hash节点个数??
totaluse += numusehash(t,nums,&nasize);? /* count keys in hash part */?
/* count extra key */?
//小段1.1.3,调用的核心算法也是hash的一种??
nasize += countint(ek,nums);??
totaluse++;??
/* compute new size for array part */?
//小段1.1.4,没看太懂，只是做了个黑盒测试。会根据下标重算一个大小??
na = computesizes(nums,&nasize);??
/* resize the table to new computed sizes */?
//小段1.1.5,这个版本留坑。第一次table目的已达到??
resize(L,nasize,totaluse - na);??
}?
/*
这段函数算法可以暂时不分析得非常非常细致。我们可以先用黑盒测试它的一些行为。
比如用insert插入的两次下标不在同个位置，那么getn得到的是0；如果插入的位置是序列
的，那么rehash会认为是排列紧密的，getn得到是2。可以看出，这个函数主要是个重新
归纳和分配节点算法的东西。后面留个坑，慢慢补。那么table中插入元素的排列位置如下图:
*/
static void rehash (lua_State *L,const TValue *ek) {
int nasize,na;
int nums[MAXBITS+1];? /* nums[i] = number of keys between 2^(i-1) and 2^i */
int i;
int totaluse;
//MAXBITS为 26。清零
for (i=0; i<=MAXBITS; i++) nums[i] = 0;? /* reset counts */
//小段1.1.1,计算这个数组中已有的元素个数
nasize = numusearray(t,nums);? /* count keys in array part */
totaluse = nasize;? /* all those keys are integer keys */
//小段1.1.2,计算已使用的hash节点个数
totaluse += numusehash(t,&nasize);? /* count keys in hash part */
/* count extra key */
//小段1.1.3,调用的核心算法也是hash的一种
nasize += countint(ek,nums);
totaluse++;
/* compute new size for array part */
//小段1.1.4,没看太懂，只是做了个黑盒测试。会根据下标重算一个大小
na = computesizes(nums,&nasize);
/* resize the table to new computed sizes */
//小段1.1.5,这个版本留坑。第一次table目的已达到
resize(L,totaluse - na);
}
Cpp代码?
/*?
1.1.1?
先观察退出的条件：i>lim,lim为ttlg,ttlg变化范围是个2^lg,?
i是个ttlg叠加的和,包括空和非空的元素.?
而当i>lim时，lim的值实际上是t->sizearray。这个思路和上文的while?
很像，都是一个预加的试探方法。当ttlg叠加的和大于t->sizearray,说明已经统计完毕。
*/?
static int numusearray (const Table *t,int *nums) {??
int lg;??
int ttlg;? /* 2^lg */?
int ause = 0;? /* summation of `nums' */?
int i = 1;? /* count to traverse all array keys */?
for (lg=0,ttlg=1; lg<=MAXBITS; lg++,ttlg*=2) {? /* for each slice */?
int lc = 0;? /* counter */?
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] */?
for (; i <= lim; i++) {??
if (!ttisnil(&t->array[i-1]))??
lc++;??
}??
//lg,表示对应的下标??
nums[lg] += lc;??
ause += lc;??
}??
return ause;??
}?
/*
1.1.1
先观察退出的条件：i>lim,
i是个ttlg叠加的和,包括空和非空的元素.
而当i>lim时，lim的值实际上是t->sizearray。这个思路和上文的while
很像，都是一个预加的试探方法。当ttlg叠加的和大于t->sizearray,说明已经统计完毕。
*/
static int numusearray (const Table *t,int *nums) {
int lg;
int ttlg;? /* 2^lg */
int ause = 0;? /* summation of `nums' */
int i = 1;? /* count to traverse all array keys */
for (lg=0,ttlg*=2) {? /* for each slice */
int lc = 0;? /* counter */
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] */
for (; i <= lim; i++) {
if (!ttisnil(&t->array[i-1]))
lc++;
}
//lg,表示对应的下标
nums[lg] += lc;
ause += lc;
}
return ause;
}
Cpp代码?
/*?
1.1.2?
返回值totaluse，表示非空的t->node数?
ause,通过countint统计?
*/?
static int numusehash (const Table *t,int *nums,int *pnasize) {??
int totaluse = 0;? /* total number of elements */?
int ause = 0;? /* summation of `nums' */?
//#define sizenode(t) (twoto((t)->lsizenode))?
int i = sizenode(t);??
while (i--) {??
Node *n = &t->node[i];??
if (!ttisnil(gval(n))) {??
//#define key2tval(n)?? (&(n)->i_key.tvk)?
//countint见1.1.2.1??
ause += countint(key2tval(n),nums);??
totaluse++;??
}??
}??
*pnasize += ause;??
return totaluse;??
}?
/*
1.1.2
返回值totaluse，表示非空的t->node数
ause,通过countint统计
*/
static int numusehash (const Table *t,int *pnasize) {
int totaluse = 0;? /* total number of elements */
int ause = 0;? /* summation of `nums' */
//#define sizenode(t)?(twoto((t)->lsizenode))
int i = sizenode(t);
while (i--) {
Node *n = &t->node[i];
if (!ttisnil(gval(n))) {
//#define key2tval(n)?(&(n)->i_key.tvk)
//countint见1.1.2.1
ause += countint(key2tval(n),nums);
totaluse++;
}
}
*pnasize += ause;
return totaluse;
}
Cpp代码?
/*?
1.1.2.1 / 1.1.3?
*/?
static int countint (const TValue *key,int *nums) {??
int k = arrayindex(key);??
if (0 < k && k <= MAXASIZE) {? /* is `key' an appropriate array index? */?
nums[ceillog2(k)]++;? /* count as such */?
return 1;??
}??
else?
return 0;??
}??
/*?
** returns the index for `key' if `key' is an appropriate key to live in
** the array part of the table,-1 otherwise.?
*/?
//没看太懂，为了浮点数偏差比较吗？??
static int arrayindex (const TValue *key) {??
if (ttisnumber(key)) {??
lua_Number n = nvalue(key);??
int k;??
//一条汇编扩展，浮点变整形??
lua_number2int(k,n);??
if (luai_numeq(cast_num(k),n))??
return k;??
}??
return -1;? /* `key' did not match some condition */?
}??
//ceillog2对应??
//没看懂，略过??
#define ceillog2(x) (luaO_log2((x)-1) + 1)?
int luaO_log2 (unsigned int x) {??
static const lu_byte log_2[256] = {??
0,4,5,??
6,6,??
7,7,??
8,8,8??
};??
int l = -1;??
while (x >= 256) { l += 8; x >>= 8; }??
return l + log_2[x];??
}?
/*
1.1.2.1 / 1.1.3
*/
static int countint (const TValue *key,int *nums) {
int k = arrayindex(key);
if (0 < k && k <= MAXASIZE) {? /* is `key' an appropriate array index? */
nums[ceillog2(k)]++;? /* count as such */
return 1;
}
else
return 0;
}
/*
** returns the index for `key' if `key' is an appropriate key to live in
** the array part of the table,-1 otherwise.
*/
//没看太懂，为了浮点数偏差比较吗？
static int arrayindex (const TValue *key) {
if (ttisnumber(key)) {
lua_Number n = nvalue(key);
int k;
//一条汇编扩展，浮点变整形
lua_number2int(k,n);
if (luai_numeq(cast_num(k),n))
return k;
}
return -1;? /* `key' did not match some condition */
}
//ceillog2对应
//没看懂，略过
#define ceillog2(x)?(luaO_log2((x)-1) + 1)
int luaO_log2 (unsigned int x) {
static const lu_byte log_2[256] = {
0,
6,
7,
8,8
};
int l = -1;
while (x >= 256) { l += 8; x >>= 8; }
return l + log_2[x];
}
1.1.3,1.1.4的代码就不贴了。作为第一次分析table,已经满足了。剩下都是算法的坑。首先要做的是去搜索有没有这种算法名，借助外部的资料来学习算法更有效。
http://lin-style.iteye.com/blog/976945
