咖啡's blog

专心 专注 专业

0%

Lua源码笔记(2)--Table的newkey

发表于 更新于 分类于 ， Valine：

本文从两个操作说明一个新的键值插入到table的哈希表中的过程；插入键值对Lua表的操作相当频繁,其函数的性能也关乎到Lua在宿主语言中的性能；一个操作是newkey函数，通过查找一个新的可用的哈希位置来插入键值，当没有可用位置时，引发另外一个操作就是rehash,这个操作会重新判定Lua表(Table)的数组长度和哈希表的长度，从而腾出新的位置插入当前节点；具体过程参见详细分析。

newkey函数分析

参看一下代码注释前请先参考这篇文章
文章主要解释了Lua的Table表中包含两个部分,一部分是数组部分，一部分是哈希表部分，之所以使用这种存储方式，是考虑到Key的格式不仅仅是数字，若是数字则分情况设置到数组或者哈希表部分，其他类型依情况而定，另外一个情况是哈希到哈希列表部分，如果发生碰撞的情况处理，是先使用getfreepos找到空闲位置，然后主位置的节点链接过去，就像一个链表，这也就导致另外一个问题，就是当真正的节点要插入时，可能有其他节点已经占用了这个位置，这个时候的处理就是将这个节点移动到空闲位置上去，将真正的哈希节点设置进来，基本思路便是如此。

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
39
40
41
42
43
44
45
46
47
48
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
  // 参见后面的mainposition函数的分析
  // 找到key的类型的哈希值所在哈希表中位置的节点mp
  Node *mp = mainposition(t, key);
  // 当mp的值不为nil或者节点mp不为dummynode
  // 注:dummynode是哈希表的初始节点
  if (!ttisnil(gval(mp)) || mp == dummynode) {
    Node *othern;
    // 参见getfreepos
    // 在哈希表中找到一个空闲位置
    Node *n = getfreepos(t);
    if (n == NULL) {  
      // 没有找到空闲位置时重新哈希
      // 注:参见rehash函数保证有一个空闲节点可以设置键值
      rehash(L, t, key);  
      return luaH_set(L, t, key); 
    }
    lua_assert(n != dummynode);
    // 重新计算以mp的键值为哈希值的节点othern
    othern = mainposition(t, key2tval(mp));
    // 注:othern才是这个哈希表中这个位置上的节点
    if (othern != mp) {  
      // 当othern不等于mp时，说明mp只是暂住借用这个节点的空间
      // 这个时候将指向mp的节点指向n
      // 然后将mp迁移到n位置
      while (gnext(othern) != mp) othern = gnext(othern); 
      gnext(othern) = n;  
      *n = *mp; 
      // 迁移到n以后mp就是空闲位置了
      // 要记住一点的是mp是key哈希后得到的哈希表中的位置
      gnext(mp) = NULL;  
      setnilvalue(gval(mp));
    }
    else {  
      // 如果othern和mp相等，那就将n挂到mp下面
      // n是哈希表中的一个空闲位置
      gnext(n) = gnext(mp);  
      gnext(mp) = n;
      mp = n;
    }
  }
  // 这里是这是这个哈希节点的key值
  // 返回的是这个哈希节点的val的指针供后续赋值
  gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
  luaC_barriert(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

mainposition函数分析

这个函数的主要作用就是将根据key的类型得到哈希值生成索引位置，从Table表中哈希列表所在索引位置得到节点。

  • hashnum注释

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // 能使用hashnum的情况说明不能设置到Table的数组中了
    static Node *hashnum (const Table *t, lua_Number n) {
      unsigned int a[numints];
      int i;
      // 如果是数字0就直接返回0位置的节点(特殊处理)
      if (luai_numeq(n, 0))  /* avoid problems with -0 */
        return gnode(t, 0);
      // lua_Number在这里是double类型，做一次拷贝
      memcpy(a, &n, sizeof(a));
      // 逐个数字进行累加到a[0]
      for (i = 1; i < numints; i++) a[0] += a[i];
      // #define hashmod(t,n)	(gnode(t, ((n) % ((sizenode(t)-1)|1))))
      // 将n mod 哈希表长度范围得到的索引,通过gnode得到节点
      // 或1与加1的情况不同,加1是末尾为时加1为0,这里或1是保证索引落在2的倍数索引内
      // 依次展开sizenode宏
      // #define twoto(x)	(1<<(x)) 
      // #define sizenode(t)	(twoto((t)->lsizenode))
      // 以上两句就计算Table的哈希表的长度,lszienode记录的是以2为基的次数
      return hashmod(t, a[0]);
    }

  • hashstr注释

    1
    2
    3
    4
    5
    6
    7
    // 这里使用String的hash值直接根据哈希列表的长度求模得出索引
    // gnode根据索引得到节点
    // 这里需要注意的第一地方是使用了&代替求模，这个可以自行科普一下
    #define lmod(s,size) \
    	(check_exp((size&(size-1))==0, (cast(int, (s) & ((size)-1)))))
    #define hashpow2(t,n)      (gnode(t, lmod((n), sizenode(t))))
    #define hashstr(t,str)  hashpow2(t, (str)->tsv.hash)

  • mainposition注释

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // 这里需要注意的是TValue包含了Lua中表示的所有类型
    // 这里返回的是Node的指针,也就是哈希列表中的节点地址
    static Node *mainposition (const Table *t, const TValue *key) {
      switch (ttype(key)) {
        case LUA_TNUMBER:
          // 参见上面的注释
          // #define nvalue(o)	check_exp(ttisnumber(o), (o)->value.n)
          return hashnum(t, nvalue(key));
        case LUA_TSTRING:
          // 参见上面注释
          // #define rawtsvalue(o)	check_exp(ttisstring(o), &(o)->value.gc->ts)
          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));
      }
    }

newkey的使用

  • 我们以luaH_setnum函数为例来看看newkey函数的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TValue *luaH_setnum (lua_State *L, Table *t, int key) {
  // 先去查询一下这个key的节点是否存在(重点)
  const TValue *p = luaH_getnum(t, key);
  if (p != luaO_nilobject)
    // 存在则直接返回这个节点,cast是去const
    return cast(TValue *, p);
  else {
    // 这里将int的key转换成Lua内部使用TValue
    // #define setnvalue(obj,x) \
    //     { TValue *i_o=(obj); i_o->value.n=(x); i_o->tt=LUA_TNUMBER; }
    TValue k;
    setnvalue(&k, cast_num(key));
    // 进行一次newkey的操作
    // 这里要注意的是有可能引发rehash操作，对数组和哈希列表进行扩容
    return newkey(L, t, &k);
  }
}
  • luaH_getnum函数得到节点(数组部分或者哈希列表部分)
    有人问如何使用Table的数组部分或者哈希部分，主要是通过luaH_getnum函数决定是使用数组部分还是哈希列表部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const TValue *luaH_getnum (Table *t, int key) {
  // 先查找数组部分如果是直接返回数组部分
  // 所以在使用lua时优先使用数组
  if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
    return &t->array[key-1];
  else {
    // 转换成Lua内部内省lua_Number
    lua_Number nk = cast_num(key);
    Node *n = hashnum(t, nk);
    do {  
      // 首先做类型判断然后判断Key的值是否相等
      if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
        return gval(n);
      else n = gnext(n);
    } while (n);
    return luaO_nilobject;
  }
}