lua源码之TString和Table数据结构分析 -

616050468

浏览: 9851 次
性别:
来自: 广州

最近访客更多访客>>

vpone

鱿鱼须

q278541473

icson.zhou

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

lua源码之TString和Table数据结构分析

博客分类：

TString Table lua数据结构 lua源码分析

最近游戏项目改用c++/lua开发，于是开始学习lua，lua是一种轻量小巧的脚本语言，据说lua是最快的脚本语言也不无道理。这篇文章从lua的数据结构入手，把lua的实现描述出来，加深自己的理解。(lua源码版本为5.2.3)

所谓lua虚拟机其实就是一个c的struct结构体(lua_State)，所有lua代码都通过解析器加载到lua_State结构中保存。lua中的基础数据类型分为8种：nil, boolean, lightuserdata, number, string, table, function(包括c函数cfunction和lua函数lfunction), userdata, thread，其中最重要的就是table，因为所有的数据其实都是保存在table中的。程序就是数据结构和算法，那么在lua中是怎么表示这些数据类型呢。

图 1-1

如图1-1所示，lua中对基础数据类型使用统一的数据结构TValue表示，value_表示值，tt_表示数据类型。由此可知Value是一个union结构，结合源码(lobject.h 184行开始/* Macros to set values */)可知，对于nil,boolean,lightuserdata,number,cfunction这些数据类型的值都是直接存放在TValue中，其他类型的数据都用GCObject来表示，TValue中只是保存GCObject结构的指针。下面重点讲一下Table和TString两种类型，后面深入其他东西的时候会继续讲到。

1. TString

/*
** creates a new string object
*/
static TString *createstrobj (lua_State *L, const char *str, size_t l,
                              int tag, unsigned int h, GCObject **list) {
  TString *ts;
  size_t totalsize;  /* total size of TString object */
  totalsize = sizeof(TString) + ((l + 1) * sizeof(char));
  ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts;
  ts->tsv.len = l;
  ts->tsv.hash = h;
  ts->tsv.extra = 0;
  memcpy(ts+1, str, l*sizeof(char));
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  return ts;
}

图1-2

从代码可以看出，字符串在lua的内存分配结构，如图1-2所示。lua字符串都自动加上结束符。

/*
** new string (with explicit length)
*/
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  if (l <= LUAI_MAXSHORTLEN)  /* short string? */
    return internshrstr(L, str, l);
  else {
    if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
      luaM_toobig(L);
    return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL);
  }
}

在实际中对字符串的使用大部分都是很短的，所以lua保存字符串分为短字符串和长字符串，短字符串都保存在全局的字符串hash表中，长字符串则放在全局的可gc对象列表中。

/*
** checks whether short string exists and reuses it or creates a new one
*/
static TString *internshrstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  global_State *g = G(L);
  unsigned int h = luaS_hash(str, l, g->seed);
  for (o = g->strt.hash[lmod(h, g->strt.size)];
       o != NULL;
       o = gch(o)->next) {
    TString *ts = rawgco2ts(o);
    if (h == ts->tsv.hash &&
        l == ts->tsv.len &&
        (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
      if (isdead(G(L), o))  /* string is dead (but was not collected yet)? */
        changewhite(o);  /* resurrect it */
      return ts;
    }
  }
  return newshrstr(L, str, l, h);  /* not found; create a new string */
}

短字符串的hash表采用开放寻址hash算法，在处理一个短字符串的时候对首先判断字符串在hash表中是否已存在，存在则直接返回其地址；不存在则创建该字符串，并求出其hash值。长字符串则都重新分配内存保存。因此在对比两个字符串是否相等时，短字符串只要比较地址是否相等就行了，而对于长字符串则需要对比所有字符。由此可见lua中对于短字符串的处理很高效，一般用于字符串的比较，或者用作table的key。

2. Table

图1-3

CommonHeader先忽略，lu_byte 是typedef unsigned char lu_byte，然后结合源码来讲解Table的实现(ltable.c, ltable.h)，对lua中对table的操作函数接口都定义在ltable.h中。lua中的table是key-value的形式来存放数据的，table分为两部分：数组部分array和hash部分。array和sizearray为数组部分，node，lastfree，lsizenode为hash部分。

Table *luaH_new (lua_State *L) {
  Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h;
  t->metatable = NULL;
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0);
  return t;
}

创建一个空的table时，数组部分和hash部分都为0。

返回表的一个key的值，以指针的形式返回：

/*
** main search function
*/
const TValue *luaH_get (Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key));
    case LUA_TNIL: return luaO_nilobject;
    case LUA_TNUMBER: {
      int k;
      lua_Number n = nvalue(key);
      lua_number2int(k, n);
      if (luai_numeq(cast_num(k), n)) /* index is int? */
        return luaH_getint(t, k);  /* use specialized version */
      /* else go through */
    }
    default: {
      Node *n = mainposition(t, key);
      do {  /* check whether `key' is somewhere in the chain */
        if (luaV_rawequalobj(gkey(n), key))
          return gval(n);  /* that's it */
        else n = gnext(n);
      } while (n);
      return luaO_nilobject;
    }
  }
}

当key为LUA_TNUMBER时，调用luaH_getint

/*
** search function for integers
*/
const TValue *luaH_getint (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);  /* that's it */
      else n = gnext(n);
    } while (n);
    return luaO_nilobject;
  }
}

当key小于数组长度时，则直接返回数组中的值，否则计算key的hash值，从表的hash部分查找key的值。

当key为LUA_TSHRSTR时，调用luaH_getstr：

/*
** search function for short strings
*/
const TValue *luaH_getstr (Table *t, TString *key) {
  Node *n = hashstr(t, key);
  lua_assert(key->tsv.tt == LUA_TSHRSTR);
  do {  /* check whether `key' is somewhere in the chain */
    if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key))
      return gval(n);  /* that's it */
    else n = gnext(n);
  } while (n);
  return luaO_nilobject;
}
#define hashpow2(t,n)		(gnode(t, lmod((n), sizenode(t))))
#define hashstr(t,str)		hashpow2(t, (str)->tsv.hash)

当key为其他类型时，则统一调用mainposition获取其hash值对应的散列地址。我们来看看mainposition支持哪些类型。

static Node *mainposition (const Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TNUMBER:
      return hashnum(t, nvalue(key));
    case LUA_TLNGSTR: {
      TString *s = rawtsvalue(key);
      if (s->tsv.extra == 0) {  /* no hash? */
        s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash);
        s->tsv.extra = 1;  /* now it has its hash */
      }
      return hashstr(t, rawtsvalue(key));
    }
    case LUA_TSHRSTR:
      return hashstr(t, rawtsvalue(key));
    case LUA_TBOOLEAN:
      return hashboolean(t, bvalue(key));
    case LUA_TLIGHTUSERDATA:
      return hashpointer(t, pvalue(key));
    case LUA_TLCF:
      return hashpointer(t, fvalue(key));
    default:
      return hashpointer(t, gcvalue(key));
  }
}

表的key可以是lua中能表示的任意类型。

当给table的key赋值的时候，会先查找key是否存在，如果存在则对value重新赋值，如果不存在则表示key也不存在，会调用luaH_newkey创建key，然后再对value赋值。在创建key的时候如果table的大小不够会触发rehash对表进行扩大。

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);
      // 先判断key值是否存在
      TValue *oldval = cast(TValue *, luaH_get(h, key));
      /* if previous value is not nil, there must be a previous entry
         in the table; moreover, a metamethod has no relevance */
      if (!ttisnil(oldval) ||
         /* previous value is nil; must check the metamethod */
         ((tm = fasttm(L, h->metatable, TM_NEWINDEX)) == NULL &&
         /* no metamethod; is there a previous entry in the table? */
         (oldval != luaO_nilobject ||
         /* no previous entry; must create one. (The next test is
            always true; we only need the assignment.) */
         // key值不存在则创建key，如果table不够大了，就会扩大table，扩大table的时候需要对所有的key,value键对重新挪动位置
         (oldval = luaH_newkey(L, h, key), 1)))) {
........

看下luaH_get调用的重新分配table大小的函数rehash

static void rehash (lua_State *L, Table *t, const TValue *ek) {
  int nasize, na;
  int nums[MAXBITS+1];  /* nums[i] = number of keys with 2^(i-1) < k <= 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 */
  //对hash部分进行遍历，计算hash部分中key为number的大小和不是number的大小
  totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
  /* count extra key */
  //加上要创建的key，如果key为number，则nasize加1
  nasize += countint(ek, nums);
  totaluse++;
  /* compute new size for array part */
  //根据当前key的统计，重新计算数组部分的大小，结果保存到na中
  na = computesizes(nums, &nasize);
  /* resize the table to new computed sizes */
  luaH_resize(L, t, nasize, totaluse - na);
}

来看看怎样重新计算数组部分大小的：

static int computesizes (int nums[], int *narray) {
  int i;
  int twotoi;  /* 2^i */
  int a = 0;  /* number of elements smaller than 2^i */
  int na = 0;  /* number of elements to go to array part */
  int n = 0;  /* optimal size for array part */
  for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
    if (nums[i] > 0) {
      a += nums[i];
      if (a > twotoi/2) {  /* more than half elements present? */
        n = twotoi;  /* optimal size (till now) */
        na = a;  /* all elements smaller than n will go to array part */
      }
    }
    if (a == *narray) break;  /* all elements already counted */
  }
  *narray = n;
  lua_assert(*narray/2 <= na && na <= *narray);
  return na;
}

数组nums是按块保存个数的，2^(i-1) < k <= 2^i (i=1,2,3,..., 31)的属于同一块，比如key=1，则key放在nums[0]的块，key=2则放在nums[1]的块，key=3，4则存放在nums[2]的块，k=5, 8存放在nums[3]的块，如此类推。分配数组大小的规则是：遍历nums的所有块，所有块的已被使用的key的总和（对应a）大于当前块所能存放的key的上限的一半（对应twotoi/2），则数组大小取当前key的上限（对应twotoi）。可以认为a是key的密集程度，如果所有key都使用了，则密集程度为1，如果没有key被使用，则密集程度为0，computessizes就是求出key的密集程度大于0.5小于1的情况。

以上就是对lua中TString和Table数据结构的分析。记录下来供自己查看。其他的结构以后继续分析