lua数据结构table的键值存取过程源码分析

一、相关数据结构定义

1、Table结构定义

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
typedef struct  {  
  CommonHeader;  
  lu_byte flags;     
  lu_byte lsizenode;  /* log2 of size of `node' array */  
  struct  *metatable;  
  TValue *array;  /* array part */  
  Node *node;     /* hash part */  
  Node *lastfree;  /* any free position is before this position */  
  GCObject *gclist;  
  int sizearray;  /* size of `array' array */  
} Table;  

—|—

可以看出array和node作为存储数据的两种结构,当table以整型作为key时,会用array来存储,其他数据类型key会用node来存储。sizearray作为数组的长度,2的lsizenode次方作为哈希表的长度。

2、TValue结构定义

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
/*  
** Union of all Lua values  
*/  
typedef union {  
  GCObject *gc;  
  void *p;  
  lua_Number n;  
  int b;  
} Value;  
  
  
  
typedef struct lua_TValue {  
  TValuefields;  
} TValue;  

—|—

TValue是一个结构体,里面是TValuefields,它由一个宏定义完成,包括Value和一个int值。 tt用于表示lua的基本数据类型,Value是一个联合体,可以是lua所支持的数据类型中的任意一种。

3、Node结构定义

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
typedef struct Node {  
  TValue i_val;  
  TKey i_key;  
} Node;  
  
typedef union TKey {  
  struct {  
    TValuefields;  
    struct Node *next;  /* for chaining */  
  } nk;  
  TValue tvk;  
} TKey;  

—|—

Node是key- value对的结构,主要是TKey结构,是一个union,所以TKey的大小就是nk的大小,从TValue的定义可知TValue和TValuefields同一个结构,所以tvk和nk的TValuefields都表示键值。struct Node *next这个指针指向了下一个冲突(哈希碰撞)的node。

二、键值存取过程

1、键值的取值

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
const TValue *luaH_get (Table *t, const TValue *key) {  
  switch (ttype(key)) {  
    case LUA_TNIL: return luaO_nilobject;  
    case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));  
    case LUA_TNUMBER: {  
      int k;  
      lua_Number n = nvalue(key);  
      lua_number2int(k, n);  
      if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */  
        return luaH_getnum(t, k);  /* use specialized version */  
      /* else go through */  
    }  
    default: {  
      Node *n = mainposition(t, key);  
      do {  /* check whether `key' is somewhere in the chain */  
        if (luaO_rawequalObj(key2tval(n), key))  
          return gval(n);  /* that's it */  
        else n = gnext(n);  
      } while (n);  
      return luaO_nilobject;  
    }  
  }  
}  

—|—

首先对key值进行类型判断,如果是空那就返回空,是字符串就调用luaH_getstr(t,k),是数字则根据是否是整形调用luaH_getnum(t, k),否则计算key的存储主位置,然后遍历Node节点寻找key对应的节点。其实luaH_getstr(t,k)和luaH_getnum(t, k)方法内部也是通过遍历寻找节点。
1.若是字符串LUA_TSTRING类型,则调用luaH_getstr(t,k)查找,方法如下

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
/*  
** search function for strings  
*/  
const TValue *luaH_getstr (Table *t, TString *key) {  
  Node *n = hashstr(t, key);  
  do {  /* check whether `key' is somewhere in the chain */  
    if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)  
      return gval(n);  /* that's it */  
    else n = gnext(n);  
  } while (n);  
  return luaO_nilobject;  
}  

—|—

若key为字符串,则根据hashstr(t,key)方法找到该键对应的node位置,遍历链表,返回对应的值。
2.若是LUA_TNUMBER数字类型,则调用luaH_getnum(t, k)查找,方法如下:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
/*  
** search function for integers  
*/  
const TValue *luaH_getnum (Table *t, int key) {  
  /* (1 <= key && key <= t->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 */  
      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;  
  }  
}  

—|—

若key大于等于1,且小于等于数组长度,则从数组中取出对应的键值。否则通过hashnum(t, nk)函数找到key对应的Node位置,然后遍历寻找对应的值。
3.若是其他类型,即不是空,数字,字符串类型,都是通过hash函数计算出节点存储主位置,然后遍历链表找查找(因为存在hash冲突的键值,冲突的键值在hash表中有Node *next指针链接起来)。
mainposition函数实现如下:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
/*  
** returns the `main' position of an element in a table (that is, the index  
** of its hash value)  
*/  
static Node *mainposition (const Table *t, const TValue *key) {  
  switch (ttype(key)) {  
    case LUA_TNUMBER:  
      return hashnum(t, nvalue(key));  
    case LUA_TSTRING:  
      return hashstr(t, rawtsvalue(key));  
    case LUA_TBOOLEAN:  
      return hashboolean(t, bvalue(key));  
    case LUA_TLIGHTUSERDATA:  
      return hashpointer(t, pvalue(key));  
    default:  
      return hashpointer(t, gcvalue(key));  
  }  
}  

—|—

可以看出,此函数根据key值的类型选择不同的hash函数进行计算节点存储主位置

2、键值的存值

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {  
  const TValue *p = luaH_get(t, key);  
  t->flags = 0;  
  if (p != luaO_nilobject)  
    return cast(TValue *, p);  
  else {  
    if (ttisnil(key)) luaG_runerror(L, "table index is nil");  
    else if (ttisnumber(key) && luai_numisnan(nvalue(key)))  
      luaG_runerror(L, "table index is NaN");  
    return newkey(L, t, key);  
  }  
}  

—|—

首先判断key是否在table中,如果在就替换,否则调用newkey(L, t, key)插入新的key-value结构。
函数newkey代码如下:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
/*  
** 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.   
*/  
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {  
  Node *mp = mainposition(t, key);  
  if (!ttisnil(gval(mp)) || mp == dummynode) {  
    Node *othern;  
    Node *n = getfreepos(t);  /* get a free place */  
    if (n == NULL) {  /* cannot find a free place? */  
      rehash(L, t, key);  /* grow table */  
      return luaH_set(L, t, key);  /* re-insert key into grown table */  
    }  
    lua_assert(n != dummynode);  
    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));  
    }  
    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);  
}  

—|—

从注释可以看出插入表的过程是,检查主位置(mainposition)是否为空,如果不为空则检查冲突Node是否在这个主位置。如果不在,移冲突Node到一个空位置,存放新Key在这个主位置,否则新Key存放到一个空位置。
在插入Key过程中,如果hash表空间已经满了,需要调用rehash函数增加表存储空间。
rehash函数实现如下:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
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;  
  for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */  
  nasize = numusearray(t, nums);  /* count keys in array part */  
  totaluse = nasize;  /* all those keys are integer keys */  
  totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */  
  /* count extra key */  
  nasize += countint(ek, nums);  
  totaluse++;  
  /* compute new size for array part */  
  na = computesizes(nums, &nasize);  
  /* resize the table to new computed sizes */  
  resize(L, t, nasize, totaluse - na);  
}  

—|—

rehash首先统计当前table中到底有value值不是nil的键值对的个数,然后根据这个数值确定table中数组部分的大小(其大小保证数组部分的空间利用率必须50%),最后调用luaH_resize函数来重建table。
具体过程是首先调用函数numusearray计算table中数组部分非nil的数值的个数,然后调用numusehash函数计算table中哈希部分的非nil的键值对的个数。调用countint函数来确定将要插入的(key,value)是否可以放在数组部分,接着调用computesizes来计算新的table数组部分的大小,最后调用luaH_resize函数根据原来table中数据构建新的table。

原文参考链接 https://blog.csdn.net/zr339361504/article/details/52432163

小知识:位运算的求余公式(该方法只对2的N次方数系有效) X & (2^N - 1)

糖果

糖果
LUA教程

如果不小心安装错 SQL Server 为 Evaluation 的版本,要小心当超过 180 天之后,系统就会无法正常使用了 这几天遇到一个蛮特别的案例,原本收到的问题是 “维护计划” 忽然无法使用,即便是里面没有任何的Task,都无法顺利地执行。但从对方所提供的错误消...… Continue reading

PLUM NIZ静电容键盘怎么样?

Published on September 25, 2020

程序员如何选择合适的机械键盘

Published on September 18, 2020