Lua源码剖析（四）数值结构体的操作

一. 前言

  前文中我们详细讲解了Lua数值结构的设计和实现思路，本文则完善配套于数值结构的各种操作处理函数。

二. 字符串操作

  Lua的字符串设计为每次添加时先去总表取哈希看看是否有同样的哈希值，有同样的则不会新加，否则创建新字符串从而节约内存。因此主要操作就是新建以及新建附带的总表扩容，删除相对简单这里略过不提，因为每个不同的都会新建，所以不存在字符串的修改逻辑，从而提高了运算效率。

  新建字符串时，会调用luaS_new()/luaS_newlstr()函数，这里主要逻辑为

• 计算哈希值
• 根据哈希值去总表中找是否存在
  • 如果存在则返回该对应哈希值的字符串
  • 如果不存在则调用newlstr()新建

#define luaS_new(L, s)	(luaS_newlstr(L, s, strlen(s)))

TString* luaS_newlstr(lua_State* L, const char* str, size_t l) 
{
    GCObject* o;
    unsigned int h = cast(unsigned int, l);  /* seed */
    size_t step = (l >> 5) + 1;  /* if string is too long, don't hash all its chars */
    size_t l1;
    
    for (l1 = l; l1 >= step; l1 -= step)  /* compute hash */
        h = h ^ ((h << 5) + (h >> 2) + cast(unsigned char, str[l1 - 1]));
    
    for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
        o != NULL;
        o = o->gch.next) 
    {
        TString* ts = rawgco2ts(o);
        if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) 
        {
            /* string may be dead */
            if (isdead(G(L), o)) changewhite(o);
            return ts;
        }
    }
    return newlstr(L, str, l, h);  /* not found */
}

  newlstr()的新建逻辑比较简单，很常规的三步走

• 建立TString并赋值
• 加入对应的哈希表链中
• 检测哈希表是否需要扩容

static TString* newlstr(lua_State* L, const char* str, size_t l,
    unsigned int h) 
{
    TString* ts;
    stringtable* tb;
    
    if (l + 1 > (MAX_SIZET - sizeof(TString)) / sizeof(char))
        luaM_toobig(L);
    ts = cast(TString*, luaM_malloc(L, (l + 1) * sizeof(char) + sizeof(TString)));
    ts->tsv.len = l;
    ts->tsv.hash = h;
    ts->tsv.marked = luaC_white(G(L));
    ts->tsv.tt = LUA_TSTRING;
    ts->tsv.reserved = 0;
    memcpy(ts + 1, str, l * sizeof(char));
    ((char*)(ts + 1))[l] = '\0';  /* ending 0 */
    
    tb = &G(L)->strt;
    h = lmod(h, tb->size);
    ts->tsv.next = tb->hash[h];  /* chain new entry */
    tb->hash[h] = obj2gco(ts);
    tb->nuse++;
    
    if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT / 2)
        luaS_resize(L, tb->size * 2);  /* too crowded */
    return ts;
}

  重新分配新的总字符串表的逻辑也很清晰

• 申请新空间并初始化
• 遍历旧表并挨个赋值给新表
• 释放旧表空间

void luaS_resize(lua_State* L, int newsize) 
{
    GCObject** newhash;
    stringtable* tb;
    int i;
    
    if (G(L)->gcstate == GCSsweepstring)
        return;  /* cannot resize during GC traverse */
    newhash = luaM_newvector(L, newsize, GCObject*);
    tb = &G(L)->strt;
    for (i = 0; i < newsize; i++) newhash[i] = NULL;
    
    /* rehash */
    for (i = 0; i < tb->size; i++) 
    {
        GCObject* p = tb->hash[i];
        while (p) {  /* for each node in the list */
            GCObject* next = p->gch.next;  /* save next */
            unsigned int h = gco2ts(p)->hash;
            int h1 = lmod(h, newsize);  /* new position */
            lua_assert(cast_int(h % newsize) == lmod(h, newsize));
            p->gch.next = newhash[h1];  /* chain it */
            newhash[h1] = p;
            p = next;
        }
    }
    
    luaM_freearray(L, tb->hash, tb->size, TString*);
    tb->size = newsize;
    tb->hash = newhash;
}

三. 表操作

  表的操作相对来说会复杂一些，创建还好说，插入元素时，因为涉及了索引为数字的数组和键值型数组，所以需要考虑以下问题

• 插入数字索引的数组还是键值数组
• 插入键值数组的话，是否会导致单链过长复杂度退化以及空间浪费
• 扩容问题

  首先看看最简单的创建表，其实就是申请内存然后赋初始值，这里一开始的时候，两个数组都是空的

Table *luaH_new (lua_State *L, int narray, int nhash) {
  Table *t = luaM_new(L, Table);
  luaC_link(L, obj2gco(t), LUA_TTABLE);
  t->metatable = NULL;
  t->flags = cast_byte(~0);
  /* temporary values (kept only if some malloc fails) */
  t->array = NULL;
  t->sizearray = 0;
  t->lsizenode = 0;
  t->node = cast(Node *, dummynode);
  setarrayvector(L, t, narray);
  setnodevector(L, t, nhash);
  return t;
}

  然后我们来考虑插入的事情，先回顾以下表的两个存储结构。对于array来说其实就是一系列的TValue，索引为数字。而Node则为k/v键值对，其中k考虑到哈希冲突的问题所以涉及了链表结构，对于同哈希的则存于链表之中。

struct Table
{
    TValue *array;  /* array part */
    Node *node;
}

typedef union TKey {
  struct {
    TValuefields;
    struct Node *next;  /* for chaining */
  } nk;
  TValue tvk;
} TKey;


typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

  如果仅使用拉链法解决哈希冲突，当然是可行的，但是会带来一个问题：存在大量的空间浪费，因为必然有些哈希字段是未被模到的，所以如何合理使用这些没有哈希到的空桶就可以节约内存。其实节约空间的方法一般也很固定了：开放寻址法，也就是使用当前还空着的哈希槽，如果后续加入了该槽元素，再挪位即可。表中插入元素/替换元素的代码位置在luaV_settable()，主要逻辑是

• 调用luaH_set()，根据key获取一个table的值指针oldval
• 将val的值写在在位置oldval上

void luaV_settable(lua_State* L, const TValue* t, TValue* key, StkId val) 
{
...
    Table* h = hvalue(t);
    TValue* oldval = luaH_set(L, h, key); /* do a primitive set */
    
    if (!ttisnil(oldval) ||  /* result is no nil? */
         (tm = fasttm(L, h->metatable, TM_NEWINDEX)) == NULL
       )
    { /* or no TM? */      
        setobj2t(L, oldval, val);
        luaC_barriert(L, h, val);
        return;
    }
...
}

  所以根据key取找val指针逻辑其实来自于luaH_set()，该函数主要逻辑为

• 根据key调用luaH_get()尝试取val指针
  • 取到不为空则返回
  • 为空则调用newkey()新建key并返回val指针

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

  luaH_get()实际会根据key的类型不同，调用luaH_getstr()或者luaH_getnum()或者直接default循环查找，其中luaH_getnum()尝试在数组上寻找值并返回，如果找不到，则逻辑上和其他两个函数是统一的：

• 调用mainposition()取去哈希槽位置
• while循环去遍历链表找key值相同的位置输出

  newkey()会在表中创建key-val位置，这里也是上文提到的拉链法+开放寻址法的关键实现位置

  该函数代码逻辑主要为

• 调用mainposition()获取key对应的哈希槽位置mp
• mp位置如果有值，则存在两种可能：有相同哈希需要加入链表，或者开放寻址法被其他节点占用了，需要挪开
  • 先试图取一个空位置n（如果相同哈希的情况，则需要放key；如果是被占用了，需要把占用的节点挪开），取不到的话需要rehash()扩容
  • 看看mp节点的key是否就是该哈希槽
    • 确实是该槽的节点，那就将n插在mp链表中，新的key要插入n位置
    • 不是该槽的节点，则挪到n中，将mp空出来
• 根据上面找到的位置，安放key，并返回其val指针

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

  至此，剩下的问题rehash()了。重新分配大小的逻辑其实说起来很简单，先计算当前需要多少，然后按需分配。但是由于这里存在整数数组和k/v数组，所以如何取舍二者间的关系就是很重要的事了。对于Lua来说，有这么一个判定：希望在调整过后，数组在每一个2次方位置，其容纳的元素数量都超过了该范围的50%。不难想到想做到这个效果可以先按次方统计到一个数组，然后计算前缀和去比较即可。所以rehash()实现逻辑为

• 调用numusearray()统计整数数组部分
• 调用numusehash()统计k/v部分
• 调用computesizes()去计算分配多大的整数数组合适
• 调用resize()完成实际分配

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

每个函数的实现其实都相对简单，这里就不展开讨论了。

四. 总结

本篇文章详细介绍了数值结构体相关操作的实现和思路，希望能有所启发。

参考文献

1. Lua-Source-Internal

2. 《A No Frills Introduction to Lua 5.1 VM Instructions》

3. http://lua-users.org/wiki/LuaSource

4. 《The Implementation of Lua 5.0》