从源码剖析Lua数据类型

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

lua类型	lua示例	C类型（宏）	C子类型（variant tags宏）及详细说明	C数据结构
nil（空）	type(nil) -->nil	#define LUA_TNIL 0 //空类型	// 判断TValue* o是否为一个nil 即：o->_tt是否为0 #define ttisnil(o) checktag((o), LUA_TNIL)	无
boolean（布尔）	type(true) -->boolean	#define LUA_TBOOLEAN 1	不被GC管理 // 判断TValue* o是否为一个bool值即：o->_tt是否为1 #define ttisboolean(o) checktag((o), LUA_TBOOLEAN)	int
number（数值）	type(3.14) -->number type(100) -->number // 若想知道number具体类型，可使用函数math.type来获取 math.type(3.14) -->float math.type(100) -->integer 注：对于其他非number类型，math.type会返回nil	#define LUA_TNUMBER 3 // 判断TValue* o是否为一个number 即：(o->_tt & 0xF)是否为3 #define ttisnumber(o) checktype((o), LUA_TNUMBER)	#define LUA_TNUMFLT (LUA_TNUMBER \| (0 << 4)) /* float numbers / 3 不被GC管理 // 判断TValue o是否为一个浮点值即：o->_tt是否为3 #define ttisfloat(o) checktag((o), LUA_TNUMFLT)	lua_Number //即double
number（数值）			#define LUA_TNUMINT (LUA_TNUMBER \| (1 << 4)) /* integer numbers / 19 不被GC管理 // 判断TValue o是否为一个整型值即：o->_tt是否为19（0x13） #define ttisinteger(o) checktag((o), LUA_TNUMINT)	lua_Integer //即__int64
string（字符串）	type("Hello World") -->string type('good') -->string	#define LUA_TSTRING 4 // 判断TValue* o是否为一个string 即：(o->_tt & 0xF)是否为4 #define ttisstring(o) checktype((o), LUA_TSTRING)	#define LUA_TSHRSTR (LUA_TSTRING \| (0 << 4)) /* short strings / 4 被GC管理 // 判断TValue o是否为短串即：o->_tt是否为68（0x44） #define ttisshrstring(o) checktag((o), ctb(LUA_TSHRSTR))	TString
string（字符串）	type("Hello World") -->string type('good') -->string		#define LUA_TLNGSTR (LUA_TSTRING \| (1 << 4)) /* long strings / 20 被GC管理 // 判断TValue o是否为长串即：o->_tt是否为84（0x54） #define ttislngstring(o) checktag((o), ctb(LUA_TLNGSTR))	TString
function（函数）	type(print) -->function	#define LUA_TFUNCTION 6 // 判断TValue* o是否为一个function #define ttisclosure(o) ((rttype(o) & 0x1F) == LUA_TFUNCTION)	#define LUA_TLCL (LUA_TFUNCTION \| (0 << 4)) /* Lua closure / 6 被GC管理 // 判断TValue o是否为LClosure 即：o->_tt是否为70（0x46） #define ttisLclosure(o) checktag((o), ctb(LUA_TLCL)) 注：Lua closure即Lua function LClosure 由 Proto 和 UpVal 组成 Proto描述了lua函数的函数原型记录着函数原型的字节码、函数引用的常量表、调试信息、参数、栈大小等信息 UpVal保存了对upvalue的引用。它直接用一个TValue 指针引用一个upvalue值变量当被引用的变量还在数据栈上时，这个指针直接指向栈上的TValue，那么这个upvalue被称为开放的	LClosure
			#define LUA_TLCF (LUA_TFUNCTION \| (1 << 4)) /* light C function / 22 不被GC管理 // 判断TValue o是否为lua_CFunction 即：o->_tt是否为22（0x16） #define ttislcf(o) checktag((o), LUA_TLCF) LUA_TLCF即：当LUA_TCCL不包含 upvalue时，直接用lua_CFunction函数指针，不必构造Closure对象注：typedef int (lua_CFunction) (lua_State L)	lua_CFunction
			#define LUA_TCCL (LUA_TFUNCTION \| (2 << 4)) /* C closure / 38 被GC管理 // 判断TValue o是否为CClosure 即：o->_tt是否为102（0x66） #define ttisCclosure(o) checktag((o), ctb(LUA_TCCL)) 注：C closure即regular C function CClosure 由 lua_CFunction 和 TValue 组成 C 函数可以用闭包的方式嵌入 lua，与LClosure 相比，CClosure天生就是关闭的因此，直接使用TValue来保存upvalue	CClosure
table（表）	type({}) -->table	#define LUA_TTABLE 5	// 判断TValue* o是否为Table 即：o->_tt是否为69（0x45） #define ttistable(o) checktag((o), ctb(LUA_TTABLE)) 可以有元表和元方法	Table
userdata（用户数据）	type(io.stdin) -->userdata 注：stdin,stdout,stderr是lua提供三种预定义文件描述	#define LUA_TLIGHTUSERDATA 2	// 判断TValue* o是否为一个light userdata数即：o->_tt是否为2 #define ttislightuserdata(o) checktag((o), LUA_TLIGHTUSERDATA) 即轻量级用户数据（light userdata）只是一个指针（在c中，调用lua_pushlightuserdata将一个指针压入栈来给lua使用）没有元表，且无法得知其类型与数值类型一样，不被GC管理	void*
userdata（用户数据）		#define LUA_TUSERDATA 7	// 判断TValue* o是否为一个full userdata数即：o->_tt是否为71（0x47） #define ttisfulluserdata(o) checktag((o), ctb(LUA_TUSERDATA)) 即完全用户数据（full userdata）通常用来表示C中的结构体，可以有元表和元方法在c中调用lua_newuserdata创建指定大小的内存区域，被GC管理	void*
thread（线程）	type(coroutine.create(function() end)) -->thread	#define LUA_TTHREAD 8	// 判断TValue* o是否为一个thread 即：o->_tt是否为72（0x48） #define ttisthread(o) checktag((o), ctb(LUA_TTHREAD)) lua不支持真正的多线程，实际是一个协程在c中调用lua_newstate来创建lua_State 在c中调用lua_newthread创建一个线程被GC管理	lua_State
		#define LUA_TNONE (-1) //无类型		无

基础结构

Value与TValue

lua为了方便对所有的类型进行统一管理，把它们都抽象成了一个叫做Value的union结构中注：sizeof(Value)=8

/*
** Union of all Lua values
*/
typedef union Value {
  GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  int b;           /* booleans */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;

从定义可以看出，主要把这些类型划分为了需要GC的类型和不需要GC的类型

由于Value是union的结构，所以每个Value实例里同时只会有一个字段是有效的

而为了知道具体哪个字段是有效的，也就是具体该Value是什么类型，从而有了TValue这个struct结构，主要在Value基础上wrap了一个_tt字段来标识Value的具体类型注：sizeof(TValue)=16

#define TValuefields    Value value_; int tt_


typedef struct lua_TValue {
  TValuefields;
} TValue;

GCUnion、GCObject、CommonHeader

lua把所有值按是否需要被GC，划分为了一般类型和被GC管理的类型。所有需要被GC的类型，被定义在了GCUnion里

/*
** Union of all collectable objects (only for conversions)
*/
union GCUnion {
  GCObject gc;  /* common header */
  struct TString ts;  /* 字符串 */
  struct Udata u;  /* 用户数据 */
  union Closure cl;  /* 函数 */
  struct Table h;  /* 表 */
  struct Proto p;  /* 函数原型：存放函数字节码等信息 */
  struct lua_State th;  /* 线程 */
};

可以发现String、UserData、Closure、Table、Proto、luaState等类型都是需要被GC的，GCUnion结构和Value类似，也是同时只有一个字段是有效的

所以我们自然而然会想到，是不是类似TValue一样，在外面给包一层type呢，但是lua实现这边并没有这样做

而是让TString、UData这些"子类"都在各自开头定义了一个叫做CommonHeader的宏，这个宏里包含了type和一些其他字

而每个GC类型都需要在在其struct头部定义该宏，从而可以造成一种所有GC类型都继承自一个带有CommonHeader宏的基类的假象

/*
** Common type for all collectable objects
*/
typedef struct GCObject GCObject;


/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/
#define CommonHeader    GCObject *next; lu_byte tt; lu_byte marked
// 注：tt，即该GC对象的具体类型
// 注：next，指向GCObject的指针，用于GC算法内部实现链表
// 注：marked，用于GC算法内部实现


/*
** Common type has only the common header
*/
struct GCObject {
  CommonHeader;
};

这样组织的好处在于lua可以把所有的GC类型的对象都视作是一个GCObject。

再比如，lua里创建单个gcobject的函数如下

/*
** create a new collectable object (with given type and size) and link
** it to 'allgc' list.
*/
GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
  global_State *g = G(L);
  GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
  o->marked = luaC_white(g);
  o->tt = tt;
  o->next = g->allgc;
  g->allgc = o;
  return o;
}

所有的gc类型就都会调用luaC_newobj函数来创建一个GCObject实例，区别只是在于传入的type和内存size不一样而已

该函数会根据实际传入的内存大小来开辟空间，然后填充CommonHeader部分的数据

最后，它还会把该obj挂接到global_state结构里定义的GC列表GCObject* allgc（保存所有gc类型对象的指针）的头部，以供GC模块使用

每个类型只用把创建出来的实例剩余内存部分的数据设置好即可，比如下面的String类型

#define sizelstring(l)  (sizeof(union UTString) + ((l) + 1) * sizeof(char))

/*
** Get the actual string (array of bytes) from a 'TString'.
** (Access to 'extra' ensures that value is really a 'TString'.)
*/
#define getstr(ts)  \
  check_exp(sizeof((ts)->extra), cast(char *, (ts)) + sizeof(UTString))
  
#define gco2ts(o)  \
    check_exp(novariant((o)->tt) == LUA_TSTRING, &((cast_u(o))->ts))
  
/*
** creates a new string object
*/
static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
  TString *ts;
  GCObject *o;
  size_t totalsize;  /* total size of TString object */
  // 计算一个string实例实际内存占用大小：其实是UTString结构占用，再加上(charlength+1)个char大小
  totalsize = sizelstring(l);
  // 创建GCObject
  o = luaC_newobj(L, tag, totalsize);
  ts = gco2ts(o);
  // 填充string实例特有字段
  ts->hash = h;
  ts->extra = 0;
  // 取TString关联的char数组
  getstr(ts)[l] = '\0';  /* ending 0 */
  return ts;
}

string在创建完成以后，调用了内部的gco2ts函数，把本来指向GCObject指针强转成了指向TString的指针，然后对TString的额外元数据进行了赋值

字符串

考虑到性能和内存等方面，lua把String分成短字符串和长字符串两类来分开处理（注：长度大于40的为长串，反之则为短串；#define LUAI_MAXSHORTLEN 40）

如：短串会先在全局stringtable的hashmap结构表中查询，若查询不到才会创建；而长串不查询，直接创建；两个相同的长串将会是两个副本，占用两份内存。

主要原因是：

① 短串复用度会比长串要高。比如obj["id"] = 12, obj["type"] = 0，类似"id"、"type"这种短串可能会在程序很多处地方使用到，如果开辟多份就有点浪费了；而长串则很少会有重复的

② 长串计算哈希耗时长

TString结构体

/*
** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
*/
typedef struct TString {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
  lu_byte shrlen;  /* length for short strings */
  unsigned int hash;
  union {
    size_t lnglen;  /* length for long strings */
    struct TString *hnext;  /* linked list for hash table */
  } u;
} TString;

字段含义：

CommonHeader -- GC对象通用的CommonHeader
extra -- 短串：用于实现保留字符串长串：是否进行过hash的标识，为0时，表示该长串的hash还没计算过，否则表示已经计算过了
shrlen -- 短串：长度长串：未使用
hash -- 字符串的hash值。短串：该hash值是在创建时就计算出来的长串：只有真正需要它的hash值时，才会手动调用luaS_hashlongstr函数生成该值，lua内部现在只有在把长串作为table的key时，才会去计算它。
union{lnglen, hnext} -- 短串：由于创建时会被加入到全局stringtable的链表中，所以在该结构中保存了指向下一个TString的指针；长串：表示该长串的长度。
注：长串和短串没有共用一个字段来表示它们的长度，主要是长串的长度可以很长，而短串最长就为40，一个byte就够用了，这边也体现了lua实现是很抠细节的，反倒是把这两个不相关的字段打包到一个union里来节约内存了。

UTString Union

/*
** Ensures that address after this type is always fully aligned.
*/
typedef union UTString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  TString tsv;
} UTString;

为了实现TString结构的内存对齐，lua又在其上wrap了一层UTString结构

sizeof(L_Umaxalign)为8，保证UTString对象本身会按照8字节进行对齐

使用luaS_newlstr创建字符串

/*
** 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 {
    TString *ts;
    if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char))  // MAX_SIZE=0x7FFFFFFFFFFFFFFF
      luaM_toobig(L); // 长度太大了，直接报错
    ts = luaS_createlngstrobj(L, l);  // 创建长串
    memcpy(getstr(ts), str, l * sizeof(char)); // 将str的内容拷贝到ts的内存中
    return ts;
  }
}


/*************************************创建短串***************************************/
/*
** 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) {
  TString *ts;
  global_State *g = G(L);
  unsigned int h = luaS_hash(str, l, g->seed);  // 计算Hash  为了对长度较长的字符串不逐位hash，luaS_hash函数内部也是根据长度的2次幂计算出了一个步长step，来加速hash的过程
  
  // 查找该Hash是否在全局stringtable对象g->strt中
  TString **list = &g->strt.hash[lmod(h, g->strt.size)];
  lua_assert(str != NULL);  /* otherwise 'memcmp'/'memcpy' are undefined */
  for (ts = *list; ts != NULL; ts = ts->u.hnext) {
    if (l == ts->shrlen &&
        (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
      /* found! */
      if (isdead(g, ts))  /* dead (but not collected yet)? */
        changewhite(ts);  /* resurrect it */
      // 如果在stringtable中，直接返回
      return ts;
    }
  }
  // stringtable的元素数量已经大于桶数，那么以两倍的尺寸对stringtable进行resize
  if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) {
    // luaS_resize是实际改变stringtable桶数量的函数，只会在2个地方被调用
    // 一个是这里：桶数量小于了元素数量，说明散列比较拥挤了，会对桶进行两倍的扩容
    // 即：newsize>oldsize。这个时候会先进行扩容，然后进行rehash。扩容跟到里面去调用的就是realloc函数。而rehash的代码也很简洁，就是简单的遍历每个桶，把每个桶里的元素再哈希到正确的桶里去
    // 另一个是在gc时，如果发现桶数量大于4倍的元素数量，说明散列太稀疏了，会对桶数量进行减半操作
    // 即：newsize < oldsize，顺序是倒过来的，需要先根据newsize进行rehash，然后在保证所有元素已经收缩到newsize个数的桶里以后，才能进行shrink操作，这里也是调用的realloc函数来实现
    luaS_resize(L, g->strt.size * 2);
    list = &g->strt.hash[lmod(h, g->strt.size)];  /* recompute with new size */
  }
  // 调用createstrobj函数创建TString。其中包括了内存的分配，CommonHeader的填充，TString特化字段的填充等
  ts = createstrobj(L, l, LUA_TSHRSTR, h);
  memcpy(getstr(ts), str, l * sizeof(char));
  ts->shrlen = cast_byte(l);
  ts->u.hnext = *list;
  // 更新stringtable的链表，以及对stringtable的元素数量加1
  *list = ts;
  g->strt.nuse++;
  return ts;
}


// 短串实现的hashmap结构体
typedef struct stringtable {
  TString **hash; // 基于TString的hashmap，也叫做散列桶。基本结构是一个数组，每个数组里存的是相同hash值的TString的链表
  int nuse;  /* number of elements */  // 当前实际的元素数
  int size;  // 当前的桶大小
} stringtable;


/*************************************创建长串***************************************/
TString *luaS_createlngstrobj (lua_State *L, size_t l) {
  TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed);
  ts->u.lnglen = l;  // 设置长串的长度变量
  return ts;
}

内存结构如下：

注1：将value_.gc指针强制转换为TString*类型，即可读取TString中数据

注2：(char*)(value_.gc) + sizeof(TString)即为字符串的内容

函数

lua函数及C函数，都是一个函数闭包。函数闭包存储了函数本身以及外围作用域的局部变量（upvalue）注：env环境也是upvalue的一种

#define ClosureHeader \
    CommonHeader; lu_byte nupvalues; GCObject *gclist
//包含了CommonHeader的宏，表明Closure是gc类型
//nupvalues为upvalue的个数
//GCObject* gclist：与gc有关，将table加入到gray表中时gclist指向gray表中的下一个元素或者为空


/*
** Upvalues for Lua closures  // Lua函数闭包的Upvalues
*/
struct UpVal {
  TValue *v;  /* points to stack or to its own value */
  lu_mem refcount;  /* reference counter */  // 引用计数
  union {
    struct {  /* (when open) */
      UpVal *next;  /* linked list */
      int touched;  /* mark to avoid cycles with dead threads */
    } open;
    TValue value;  /* the value (when closed) */  // 关闭状态时的value值
  } u;
};

// C函数闭包
typedef struct CClosure {
  ClosureHeader;
  lua_CFunction f;  // 函数指针
  TValue upvalue[1];  /* list of upvalues */  //C函数的闭包天生是关闭的，直接使用TValue来保存upvalue
} CClosure;

// Lua函数闭包
typedef struct LClosure {
  ClosureHeader;
  struct Proto *p;  // 函数原型（Prototype）的结构
  UpVal *upvals[1];  /* list of upvalues */ //函数的upvalue指针列表，记录了该函数引用的所有upvals
} LClosure;


typedef union Closure {
  CClosure c;
  LClosure l;
} Closure;

Proto结构体

每个函数会被编译成一个称之为原型（Proto）的结构

原型主要包含6部分内容：函数基本信息（basic info：含参数数量、局部变量数量等信息）、字节码（bytecodes）、常量（constants）表、upvalue（闭包捕获的非局部变量）表、调试信息（debug info）、子函数原型列表（sub functions）

// Lua虚拟机的指令集为定长（Fixed-width）指令集，每条指令占4个字节（32bits），其中操作码（OpCode）占6bits，操作数（Operand）使用剩余的26bits
/*
** type for virtual-machine instructions;
** must be an unsigned with (at least) 4 bytes (see details in lopcodes.h)
*/
#if LUAI_BITSINT >= 32
typedef unsigned int Instruction;
#else
typedef unsigned long Instruction;
#endif

// 描述函数原型上的一个upvalue
/*
** Description of an upvalue for function prototypes
*/
typedef struct Upvaldesc {
  TString *name;  /* upvalue name (for debug information) */  // upvalue的名称（debug版字节码才有该信息）
  lu_byte instack;  /* whether it is in stack (register) */   // 是否在寄存器中
  lu_byte idx;  /* index of upvalue (in stack or in outer function's list) */  // upvalue在栈或外部函数列表中index
} Upvaldesc;

// 描述函数原型上的一个局部变量（debug版字节码才有该信息）
/*
** Description of a local variable for function prototypes
** (used for debug information)
*/
typedef struct LocVar {
  TString *varname;  // 变量名
  int startpc;  /* first point where variable is active */ // 起始指令索引
  int endpc;    /* first point where variable is dead */  // 终止指令索引
} LocVar;

// 函数原型
/*
** Function Prototypes
*/
typedef struct Proto {
  CommonHeader; // GC类型
  lu_byte numparams;  /* number of fixed parameters */ // 固定参数个数
  lu_byte is_vararg; // 是否为不定参数
  lu_byte maxstacksize;  /* number of registers needed by this function */  // 函数所需的寄存器数目
  int sizeupvalues;  /* size of 'upvalues' */  // Upvaldesc *upvalues个数
  int sizek;  /* size of 'k' */  // 常量TValue *k个数
  int sizecode;  // 指令Instruction *code个数
  int sizelineinfo; // 指令int *lineinfo行号个数 （debug版字节码才有该信息）
  int sizep;  /* size of 'p' */  // 子函数原型个数
  int sizelocvars;  // 局部变量个数
  int linedefined;  /* debug information  */  // 函数起始代码行（debug版字节码才有该信息）
  int lastlinedefined;  /* debug information  */  // 函数结束代码行（debug版字节码才有该信息）
  TValue *k;  /* constants used by the function */  // 常量表
  Instruction *code;  /* opcodes */  // 指令表
  struct Proto **p;  /* functions defined inside the function */  // 子函数原型表
  int *lineinfo;  /* map from opcodes to source lines (debug information) */  // 指令行号表（debug版字节码才有该信息）
  LocVar *locvars;  /* information about local variables (debug information) */  // 局部变量表（debug版字节码才有该信息）
  Upvaldesc *upvalues;  /* upvalue information */  // upvalue表
  struct LClosure *cache;  /* last-created closure with this prototype */  // 最近一次使用该原型创建的closure
  TString  *source;  /* used for debug information */  // 源代码文件名（debug版字节码才有该信息）
  GCObject *gclist;  // 与gc有关，将table加入到gray表中时gclist指向gray表中的下一个元素或者为空
} Proto;

这里的localvars和upvalues是函数原型中包含局部变量和upvalue的原始信息。在运行时，局部变量是存储在Lua栈上，upvalue索引是存储在LClosure的upvals字段中的

CClosure结构体

CClosure其实是lua在C侧对闭包的一个模拟。可以通过lua_pushcclosure函数来往栈上加入一个C闭包

// 该函数会先创建一个CClosure结构，然后把提前push到栈顶的n个元素作为upvalue，将其引用存储在CClosure的upvalue数组中
LUA_API void lua_pushcclosure (lua_State *L, lua_CFunction fn, int n) {
  lua_lock(L);
  if (n == 0) {
    setfvalue(L->top, fn);
  }
  else {
    CClosure *cl;
    api_checknelems(L, n);
    api_check(L, n <= MAXUPVAL, "upvalue index too large");
    cl = luaF_newCclosure(L, n);
    cl->f = fn;
    L->top -= n;
    while (n--) {
      setobj2n(L, &cl->upvalue[n], L->top + n);
      /* does not need barrier because closure is white */
    }
    setclCvalue(L, L->top, cl);
  }
  api_incr_top(L);
  luaC_checkGC(L);
  lua_unlock(L);
}

CClosure和LClosure最大区别，在于LClosure是需要去解析lua代码来得到upvalue以及字节码等信息，在执行时需要去根据opcode来执行；

而CClosure是一个直接的C函数，可直接执行，并且upvalue也是在创建前调用者手动push到栈上去的。

表（table）

table应该算是lua最灵魂的一个结构了，它有以下特点：

容器功能：与其他语言相似，lua也内置了容器功能，也就是table。而与其他语言不同的是，lua内置容器只有table。

table的内部结构又分为了数组和哈希表（字典）两个部分，根据不同情况来决定使用哪个部分。

面向对象功能：与其他语言不同的时，lua并没有把面向对象的功能以语法的形式包装给开发者。

而是保留了这样一种能力，待开发者去实现自己的面向对象，而这一保留的能力，也是封装在table里的。

table里可以组合一个metatable，这个metatable本身也是一个table，它的字段用来描述原table的行为。

#define TValuefields    Value value_; int tt_


typedef union TKey {
  struct {
    TValuefields; // 主要是为了方便对value_、tt_变量的访问，不用写成tvk.value_、tvk.tt_
    int next;  /* for chaining (offset for next node) */  // 相当于当前Node的下一个Node的索引Offset（在当前Node后面，next值为正；在当前Node前面，next值为负）
  } nk;
  TValue tvk;
} TKey;

typedef struct Node {
  TValue i_val;