Lua源码分析 - 数据结构篇 - Table实现（06）

joe

目录

一、Table - 数据结构实现

二、Table - 初始化luaH_new

三、Table - 释放操作luaH_free

四、Table - 设值操作luaH_set&luaH_setint

五、Table - 扩容操作luaH_resize

Lua语言中，Table结构类型是比较强大的一个存在。和PHP的数组有些类似。比较万能和强大。

Lua语言中Table的具体实现，主要在ltable.c文件中。

Lua语言的Table有两个特性：

Table使用关联数组，可以用任意类型来作为数组的索引键值
Table没有固定大小，可以动态扩容。
先看一下Lua中，如何使用Table：

fruits = {"banana","orange","apple"}
a = {x=12,mutou=99,[3]="hello"}
local a = {{x = 1,y=2},{x = 3,y = 10}}

mt = {}
mt = {a=10,b="123"}
mt.a = 110  //使用.号
mt["c"]=129 //使用索引
一、Table - 数据结构实现
Lua的Table实现，主要由两种类型组成：

数组节点形式：TValue *array，通过数组方式，实现值的存储。数组方式，要求table的key必须为数字，并且数字小于数组长度sizearray
Hash节点形式：Node *node，通过Hash表的方式来存储Node节点，Node节点包含key和value。前面已经说过，key和value可以为任意类型。解决hash冲突，通过TKey结构体中的next链表指针实现。
其中Node *node; 为Hash节点的头部，Node *lastfree为 hash节点，最后一个空闲节点。

key和value最终指向TValue结构，该结构支持多种类型，所以Table可以用任意类型来作为key和value。



/**
* Table数据结构，分两种存储类型：数组节点和hash节点
* 数组节点：sizearray为数字长度，一般存储key值在长度范围内的结果集
* hash节点：k=>v结构，能够存储各类复杂对象结构
*
* LUA语言用法：
* 数组节点：fruits = {"banana","orange","apple"}
* hash节点：a = {x=12,mutou=99,[3]="hello"}
* table中带table结构：local a = {{x = 1,y=2},{x = 3,y = 10}}
*/
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 sizearray;  /* size of 'array' array */
  TValue *array;  /* 数组方式 array part */
  Node *node;  //hash节点，node指向hash表的起始位置
  Node *lastfree;  /* hash节点，最后一个空闲节点 any free position is before this position */
  struct Table *metatable; //元表，重载操作需要用
  GCObject *gclist;
} Table;

/**
* 节点格式 k=>v
* 节点结构：a = {x=12,mutou=99,[3]="hello"}
*/
typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;


typedef union TKey {
  struct {
    TValuefields;
    int next;  /* 链表 管理Hash Node，用于处理hash 冲突 for chaining (offset for next node) */
  } nk;
  TValue tvk;
} TKey;
二、Table - 初始化luaH_new
Table的初始化，主要对数组节点和hash节点两个数据结构进行内存分配和初始化。

一般Table的初始化函数为：luaH_new。该函数是真正意义上的初始化，仅仅对Table数据结构进行了初始化，但是并没有初始化array和node。需要通过luaH_resize函数，针对数组节点和hash节点进行内容分配和初始化。

在lapi.c文件中，有一个函数lua_createtable，封装了Table的整个初始化的全过程。一般完成使用table，调用该函数会更加合理。该函数默认指定了数组节点和Hash节点的长度。

/**
* 创建一个table，固定长度，并将之放在栈顶.
*
* narray是该table数组部分的长度
* nrec是该table hash部分的长度.
*/
LUA_API void lua_createtable (lua_State *L, int narray, int nrec) {
  Table *t;
  lua_lock(L);
  t = luaH_new(L);
  sethvalue(L, L->top, t);
  api_incr_top(L);
  if (narray > 0 || nrec > 0)
    luaH_resize(L, t, narray, nrec);
  luaC_checkGC(L);
  lua_unlock(L);
}

/**
* 创建一个table
* table内容由luaC_newobj创建分配，并且会挂载到global_State->frealloc上统一管理
*
* Table使用方式：
* 数组结构：fruits = {"banana","orange","apple"}
* 节点结构：a = {x=12,mutou=99,[3]="hello"}
* table中带table结构：local a = {{x = 1,y=2},{x = 3,y = 10}}
*/
Table *luaH_new (lua_State *L) {
  GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
  Table *t = gco2t(o); //分配一个Table类型的内容，对象在 global_State->frealloc 上管理
  t->metatable = NULL;
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0); //设置节点空间
  return t;
}
三、Table - 释放操作luaH_free
Table的释放相对比较简单，只要对对应的内存块进行释放即可。

由于Table表的内存分配都是走Lua内部统一的内存管理机制（lmem.c），分配的时候会调用luaM_*方法，所以在释放Table的时候，统一走释放函数即可。Lua的内容都是由全局内存分配器来管理的global_State->frealloc，这里的细节下一章再详解。

/**
* 销毁一个Table
* 1. 先释放node节点
* 2. 再释放array数组
*/
void luaH_free (lua_State *L, Table *t) {
  if (!isdummy(t))
    luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
  luaM_freearray(L, t->array, t->sizearray);
  luaM_free(L, t);
}
四、Table - 设值操作luaH_set&luaH_setint
设值操作主要有两个函数：luaH_set和luaH_setint

luaH_set主要在table上设置一个值，并返回Value对象；
luaH_setint主要在Table上设置key为数字类型的节点
两者都会优先去判断，key值是否是数字类型，并且数字小于数组的长度，则走数组节点

否则都会调用luaH_newkey，走Hash节点设值。

/*
** beware: when using this function you probably need to check a GC
** barrier and invalidate the TM cache.
** 在Table上设置一个值，然后返回TValue对象
**
** 说明：
** 优先在t->array数组上查询，是否有节点可以存储，如果key小于arraysize，则放置在array上
** 调用luaH_newkey，在table上寻找可以设置key的node节点，设置成功后，返回Node->i_val
** node节点k=v形式
*/
TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  const TValue *p = luaH_get(t, key);
  if (p != luaO_nilobject)
    return cast(TValue *, p);
  else return luaH_newkey(L, t, key);
}

/**
* 在Table上设置key为数字类型的节点
* 说明：
* 1. 优先在t->array数组上查询，是否有节点可以存储，如果key小于arraysize，则放置在array上
* 2. 如果数字大于arraysize，则在Node节点上处理
* 3. 如果没有查询到p，则调用luaH_newkey创建一个新的Node节点用于存储value
*/
void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
  const TValue *p = luaH_getint(t, key);
  TValue *cell;
  if (p != luaO_nilobject)
    cell = cast(TValue *, p);
  else {
    TValue k;
    setivalue(&k, key);
    cell = luaH_newkey(L, t, &k);
  }
  setobj2t(L, cell, value);
}
luaH_newkey相对会复杂一些。需要取检查hash节点，并且判断是否有hash冲突，如果节点数量不够并且要扩容等一系列操作。

/*
** 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.
** 插入一个新key到hash 表中，首先，检查key对应的main position是否是空的，如果不是，
则检查冲突的node是不是main position，如果不是，就应该将冲突的node移到一个新的空位置，
将新key放到main position。如果冲突的点就已经是main position，则将新key放到一个空白点
*/
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
  Node *mp;
  TValue aux;
  if (ttisnil(key)) luaG_runerror(L, "table index is nil"); //检查key值是否为空值
  else if (ttisfloat(key)) { //浮点类型，如果可以转int的话，强制转成int
    lua_Integer k;
    if (luaV_tointeger(key, &k, 0)) {  /* does index fit in an integer? */
      setivalue(&aux, k);
      key = &aux;  /* insert it as an integer */
    }
    else if (luai_numisnan(fltvalue(key)))
      luaG_runerror(L, "table index is NaN");
  }
  mp = mainposition(t, key); //拿到key 可以存放的的node
  /* 如果存在 */
  if (!ttisnil(gval(mp)) || isdummy(t)) {  /* main position is taken? */
    Node *othern;
    Node *f = getfreepos(t);  /* 扩容 get a free place */
    if (f == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /*  扩容 grow table  */
      /* whatever called 'newkey' takes care of TM cache */
      return luaH_set(L, t, key);  /* insert key into grown table */
    }
    lua_assert(!isdummy(t));
    othern = mainposition(t, gkey(mp));
    if (othern != mp) {  /* is colliding node out of its main position?    此处需要解决hash冲突*/
      /* yes; move colliding node into free position */
      while (othern + gnext(othern) != mp)  /* find previous */
        othern += gnext(othern);
      gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */
      *f = *mp;  /* copy colliding node into free pos. (mp->next also goes)  */
      if (gnext(mp) != 0) {
        gnext(f) += cast_int(mp - f);  /* correct 'next' */
        gnext(mp) = 0;  /* now 'mp' is free */
      }
      setnilvalue(gval(mp));
    }
    else {  /* colliding node is in its own main position */
      /* new node will go into free position */
      if (gnext(mp) != 0)
        gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */
      else lua_assert(gnext(f) == 0);
      gnext(mp) = cast_int(f - mp);
      mp = f;
    }
  }
  setnodekey(L, &mp->i_key, key); //拷贝到node上
  luaC_barrierback(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp); //返回Tvalue方法 Node->i_val
}
五、Table - 扩容操作luaH_resize
扩容操作主要是luaH_resize函数，该函数可以设定数组节点的大小和Hash节点大小。

具体的扩容操作就不多说了，相对还比较简单。

/**
* 重新设置Table的大小
* 说明：luaH_new方法仅仅是初始化了一个Table，真正Table容器大小，需要调用此方法实现
*
* nasize：数组节点的大小
* nhsize：hash节点的大小
*/
void luaH_resize (lua_State *L, Table *t, unsigned int nasize,
                                          unsigned int nhsize) {
  unsigned int i;
  int j;
  AuxsetnodeT asn;
  unsigned int oldasize = t->sizearray;
  int oldhsize = allocsizenode(t);
  Node *nold = t->node;  /* save old hash ... */
  if (nasize > oldasize)  /* array part must grow? */
    setarrayvector(L, t, nasize);
  /* create new hash part with appropriate size */
  asn.t = t; asn.nhsize = nhsize;
  if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) {  /* mem. error? */
    setarrayvector(L, t, oldasize);  /* array back to its original size */
    luaD_throw(L, LUA_ERRMEM);  /* rethrow memory error */
  }
  if (nasize < oldasize) {  /* array part must shrink? */
    t->sizearray = nasize;
    /* re-insert elements from vanishing slice */
    for (i=nasize; i<oldasize; i++) {
      if (!ttisnil(&t->array))
        luaH_setint(L, t, i + 1, &t->array);
    }
    /* shrink array */
    luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  }
  /* re-insert elements from hash part */
  for (j = oldhsize - 1; j >= 0; j--) {
    Node *old = nold + j;
    if (!ttisnil(gval(old))) {
      /* doesn't need barrier/invalidate cache, as entry was
         already present in the table */
      setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
    }
  }
  if (oldhsize > 0)  /* not the dummy node? */
    luaM_freearray(L, nold, cast(size_t, oldhsize)); /* free old hash */
}

————————————————
版权声明：本文为CSDN博主「老码农zhuli」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/initphp/article/details/104135304