Lua学习笔记：浅谈table的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了Lua学习笔记：浅谈table的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

本篇在讲什么

Lua中的table的实现

本篇适合什么

适合初学Lua的小白

本篇需要什么

对Lua语法有简单认知
依赖Sublime Text编辑器

本篇的特色

具有全流程的图文教学
重实践，轻理论，快速上手
提供全流程的源码内容

★提高阅读体验★

👉 ♠ 一级标题 👈

👉 ♥ 二级标题 👈

👉 ♣ 三级标题 👈

👉 ♦ 四级标题 👈

♠ table的定义

摘自Lua5.1源码文件lobject.h

/*
** Tables
*/

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


typedef struct Node {
  TValue i_val;
  TKey i_key;
} 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 */
  struct Table *metatable;
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  GCObject *gclist;
  int sizearray;  /* size of `array' array */
} Table;

flags：元方法的标记，用于查询table是否包含某个类别的元方法
lsizenode：表示table的hash部分大小，2的幂数
metatable：该表的元表
array：table的数组部分
node：hash表的起始位置指针
lastfree：hash表最后位置的指针
gclist：gc相关链表
sizearray：数组的大小，不一定是2的幂数

每个table，最多会由三块连续内存构成

一个 table 结构
一块存放了连续整数索引的数组
和一块大小为 2 的整数次幂的哈希表。

♠ table的创建

在之前C/C++操作Lua的表中就了解过，创建Lua的表可以通过通过函数lua_createtable，源码如下所示

LUA_API void lua_createtable (lua_State *L, int narray, int nrec) {
  lua_lock(L);
  luaC_checkGC(L);
  sethvalue(L, L->top, luaH_new(L, narray, nrec));
  api_incr_top(L);
  lua_unlock(L);
}

Lua学习笔记：浅谈table的实现,lua学习笔记,lua,学习,笔记

其中创建函数调用的事luaH_new函数，其定义在ltabel.c脚本内

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

可根据传入的narray和nhash，初始化数组和hash表的大小

♠ table的销毁

void luaH_free (lua_State *L, Table *t) {
  if (t->node != dummynode)
    luaM_freearray(L, t->node, sizenode(t), Node);
  luaM_freearray(L, t->array, t->sizearray, TValue);
  luaM_free(L, t);
}

释放数组
释放hash表
释放table结构

♠ table的操作

针对table有多种这里我们挑一些看看源码，了解一下大致原理

♥ 读

源码摘自ltable.c，主要的查询入口是luaH_get函数

/*
** main search function
*/
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的类型，去调用对应类型的查询方法
如果key的类型是nil，则直接返回nil，table的key不能为nil
整数会根据大小，如果不超过数组长度，优先从数组内去查询
超过数组长度的key或者其他类型的key，直接从hash表内查询对应的值

♠ 写

同样的在之前操作表的学习中我们知道了可以通过以下几个函数来修改或添加表的键值

lua_settable
lua_setfield
lua_rawset
lua_rawseti

查看源码，这几个接口最终都是调用了函数luaH_set，代码如下所示

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

♠ 获取长度

获取table的长度通过函数luaH_getn，源码如下，这里需要注意，如果表不是从1开始的连续整数为key，长度获取可能会错乱

/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
int luaH_getn (Table *t) {
  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);
}