LUA的table实现

数据结构

下面的结构体是lua中用于表示一个table，主要关注里面的array和node。

typedef struct Table {

    CommonHeader;

    lu_byte flags;  /* 1<<p means tagmethod(p) is not present */

    lu_byte lsizenode;  /* log2 of size of 'node' array */

    unsigned int alimit;  /* "limit" of 'array' array */

    TValue *array;    //数组

    Node *node;    // 哈希表

    Node *lastfree;    // 辅助寻找冲突节点的指针

    struct Table *metatable;

    GCObject *gclist;

} Table;

设计原理

table可以当数组也可以当哈希表，这得益于其Table结构的设计与实现。array作数组，node作哈希表。数组部分只能存放value，所以key必须是整数，其他的都放在哈希表部分。仅当哈希表没空间的时候才会触发resize，这个时候会重新调整array和node大小，数组满了并不会触发resize。

具体操作

查找

主要关注整型是怎么查到的。

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

        // 如果double转int再转double还能相等，则认为是整数

        if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */

            return luaH_getnum(t, k); // 指向value的指针

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

    }

    }

}

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);  // 哈希部分

            else n = gnext(n);

        } while (n);

        return luaO_nilobject;

    }

}

插入

同样是关注整数。

TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {

    const TValue *p = luaH_get(t, key);   // 这里get到的是指向value的指针，有可能是数组部分

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

    }

}

void luaV_settable (lua_State *L, const TValue *t, TValue *key, StkId val) {

    int loop;

    for (loop = 0; loop < MAXTAGLOOP; loop++) {

        const TValue *tm;

        if (ttistable(t)) {  /* `t' is a table? */

            Table *h = hvalue(t);

            TValue *oldval = luaH_set(L, h, key); // 这里取到value

            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;

            }

            /* else will try the tag method */

        }

        else if (ttisnil(tm = luaT_gettmbyobj(L, t, TM_NEWINDEX)))

            luaG_typeerror(L, t, "index");

        if (ttisfunction(tm)) {

            callTM(L, tm, t, key, val);

            return;

        }

        t = tm;  /* else repeat with `tm' */

    }

    luaG_runerror(L, "loop in settable");

}

rehash:

0. t->array数组，t->node是哈希表的桶。

只有正整数才允许放到array中，其他key必然都放到哈希表。
新t->array使用率必须超过50%总table元素个数，能放多少就放多少。
新t->node使用率必须超过50%，装下非array的部分。

解读:

如果旧table当做数组来用，那么rehash之后所有元素都放在新t->array部分，新t->node指向dummynode。
如果旧table的key都是正整数，但是比较零散，有可能新t->array极小。
如果旧table的key都是正整数，但是删除了部分key，有可能新t->array比原来还小。
如果旧table的key大部分都是非正整数，有可能所有key都被存哈希表了，t->array为NULL。
如果旧table的key都是非正整数，则t->array必然是NULL。
t->array和t->node的长度都只可能是2的幂次。

哈希表部分解决冲突：

1. 通过将key1哈希到t->node上的某个位置，称为main position(简称mp)。

2. 如果mp1空闲，则直接存在mp1。若已被key2占用，计算key2的为mp2。

3. 若mp2不等于mp1，则将key1放在mp1位置上，再为key2找个其他空闲位置。

4. 若mp2等于mp1，则再为key1重新找个位置。

方案：桶+挂链。

大致的思想：为了节省内存，链表上的节点也是桶节点。即冲突的时候，在桶里面随便找一个空节点存放，再链接起来即可。

插入：如果通过哈希算出的桶节点空闲，直接使用。

若不空闲，分两种情况：

1)这个位置上的节点和新节点具有同样的哈希值。那这个节点肯定是桶头，随便找个空节点存放新节点，挂到桶头的后面。

2)这个位置上的节点和新节点具有不同的哈希值。那这个节点肯定是属于其他链表的，帮它随便找个位置放。新节点就是这个位置的桶头。

找空闲位置：有个空闲指针，从后往前移动，空节点就是可用的。若找不到空节点，持续到t->node头，就会触发rehash。

巴特西

LUA的table实现

数据结构

设计原理

具体操作

最新文章

热门文章