LUA源码分析三:table分析(1)

版本整理日期：2011/3/27

分析函数:getn,tinsert

 

 

table在里面数据方式比较直观，但是算法很复杂。一些算法的坑会慢慢补上。

先总括下table的数据结构：

1)由一个hash表和一个数组构成,当插入一个小标元素，会根据当前数组的大小决定插入哪儿

2)hash表上会有冲突，通过一个链表的形式组织冲突的元素

3)通过源码，我们还能得到的是一些table的使用技巧方式，尤其是在大数据量上的效率开销

4)我在分析的方法上是这样的：首先分析luaH_getn这个函数，通过获取的方式来对table存储的方式有个大致了解；然后分析tinsert，两者进行迭代阅读

 

 

 

//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,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)是个二分的查找

 

 

//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

 

 

//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;
  }
}

 

 

 

else段里走的流程大概是，根据nk从hashnum里面取到Node,然后进行判断，如果不符合则next个Node.

看来hashnum是个算法。先把gkey,nvalue,luai_numeq几个宏和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兼容访问。有了这些，那么可以对这句重新

认识

 

//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算法

 

//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))))

 

 

 

//跟调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]);
}

 

 

那么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函数

//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, 1, i);  /* t[i] = t[i-1] */
      }
      break;
    }
    default: {
      return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
    }
  }
  luaL_setn(L, 1, e);  /* new size */
  lua_rawseti(L, 1, pos);  /* t[pos] = v */
  return 0;
}

 tinsert函数很简单，重点跟调lua_rawseti

//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, hvalue(o), L->top-1);
  //栈减1
  L->top--;
  lua_unlock(L);
}

 

继续走luaH_setnum(L, hvalue(o), n)

//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);
  }
}

 也很简单，继续走newkey

//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, Table *t, 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, t, key);  /* grow table */
      return luaH_set(L, t, 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, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

 

/*
	这段函数算法可以暂时不分析得非常非常细致。我们可以先用黑盒测试它的一些行为。
	比如用insert插入的两次下标不在同个位置，那么getn得到的是0；如果插入的位置是序列
	的，那么rehash会认为是排列紧密的，getn得到是2。可以看出，这个函数主要是个重新
	归纳和分配节点算法的东西。后面留个坑，慢慢补。那么table中插入元素的排列位置如下图:
*/
static void rehash (lua_State *L, Table *t, 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, t, nasize, totaluse - na);
}

 

/*
	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.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.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,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
  };
  int l = -1;
  while (x >= 256) { l += 8; x >>= 8; }
  return l + log_2[x];

}

 

1.1.3,1.1.4的代码就不贴了。作为第一次分析table,已经满足了。剩下都是算法的坑。首先要做的是去搜索有没有这种算法名，借助外部的资料来学习算法更有效。

评论

3 楼 jw72jw 2015-09-22  

最后这个是打表求值

2 楼 jvmlover 2011-12-07  

被踩10次了，什么思想感情啊。

1 楼 lin_style 2011-03-28  

来访2人，被踩十几次，NB