（2025.2）四年之后翻出来之前的笔记发现根本不记得写过。要是当初多花点时间再研究研究，偶尔复习一下，现在能省不少时间。真是生于忧患，死于安乐。
这里的主要依据为codedump写的《Lua设计与实现》和lua5.4源码。
通用数据结构
lua定义了一个CommonHeader，每种数据类型都会包含它，TValue用来表示lua中所有类型，其中tt记录类型种类，声明为union的Value储存具体数据：
// tt为数据类型，marked为GC相关标记位
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked
typedef struct GCheader{
CommonHeader;
} GCheader;
// 在lua5.4中GCOject被简化为GCheader的形式，只包含一个CommonHeader
// 这部分在新版本中叫GCUnion，不再有GCHeader的定义
typedef struct GCObject {
CommonHeader;
} GCObject;
// 5.4整型为long long，且加入了函数指针
typedef union Value {
struct GCObject *gc; /* collectable objects */
void *p; /* light userdata */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
} Value;
// tt为数据的类型
#define TValuefields Value value; int tt
// TValue可以表示lua中任何数据
typedef struct lua_TValue {
TValuefields;
} TValue;
// 5.4中的GCUnion
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; /* thread */
struct UpVal upv;
};
字符串实现（2021.3.7）
新老版本lua中对于字符串的定义有所不同，但大体思路是一致的，都有gc要用的CommonHeader，保留字符串的标记，字符串长度、hash值等，贴一个lua5.4中的TString定义：
/*
** Header for a string value.
*/
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;
char contents[1];
} TString;
字符串在lua中是不可被改变的数据，多份相同的字符串只有一个副本，称为内化，lua虚拟机中有一个全局的数据，用来存放当前系统中所有的字符串，即global_State的stringtable类型成员strt中，用一个hash值来索引，如果哈希值相同，则使用链表连接。
typedef struct stringtable {
TString **hash;
int nuse; /* number of elements */
int size;
} stringtable;
创建新字符串时先会根据长度判断是否为短字符串：
- 如果是，计算要创建str的hash，在
strt中查找，如果找到则阻止其被gc（如果正在gc），然后返回，如果没找到则创建新的 - 如果不是，则不去计算哈希值，创建TString时直接用global_State中的seed作为其hash，与此同时使用lnglen来存长度，而不是保存哈希链表的指针hnext（原来这里的union是这样用的！）
在老版本中，长短都要进行哈希计算，但会根据字符串长度得到一个步长，如果字符串过长，则不对每个字符哈希，而是间隔相应步长再哈希，短字符串步长就是1。
下面是lua5.4创建新字符串的实现：
TString *luaS_createlngstrobj (lua_State *L, size_t l) {
TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed);
ts->u.lnglen = l;
return ts;
}
static TString *internshrstr (lua_State *L, const char *str, size_t l) {
TString *ts;
global_State *g = G(L);
stringtable *tb = &g->strt;
unsigned int h = luaS_hash(str, l, g->seed);
TString **list = &tb->hash[lmod(h, tb->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 */
return ts;
}
}
/* else must create a new string */
if (tb->nuse >= tb->size) { /* need to grow string table? */
growstrtab(L, tb);
list = &tb->hash[lmod(h, tb->size)]; /* rehash with new size */
}
ts = createstrobj(L, l, LUA_VSHRSTR, h);
memcpy(getstr(ts), str, l * sizeof(char));
ts->shrlen = cast_byte(l);
ts->u.hnext = *list;
*list = ts;
tb->nuse++;
return ts;
}
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 (unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char)))
luaM_toobig(L);
ts = luaS_createlngstrobj(L, l);
memcpy(getstr(ts), str, l * sizeof(char));
return ts;
}
}
创建新字符串时还要检查哈希表当前元素数量是否已经达到上限，如果达到则需要扩容，并rehash，简单来说就是遍历strt的哈希链表数组，把每个链表元素都用新的哈希值索引到相应的新链表，插入表头。在createstrobj的实现中是用短字符串的类型作为tag创建了一个gco，然后将其转成了GCUnion，最后取其中的TString类型成员返回。最后将新的ts放到哈希值索引的链表表头，并增加strt元素计数。
一些保留字符串如and、or会在初始化时创建并被标记为不被gc，实现函数是luaX_init，其中标记不被gc的函数是luaC_fix，原理是global_State中有两个GCObject链表，一个allgc储存所有需要gc的obj，一个fixedgc储存不会被gc的obj，它接收传入的gco后，首先判断它是不是allgc的第一个元素，如果是，则把它加进fidxedgc的链表头，并把后面的元素接入allgc：
void luaC_fix (lua_State *L, GCObject *o) {
global_State *g = G(L);
lua_assert(g->allgc == o); /* object must be 1st in 'allgc' list! */
set2gray(o); /* they will be gray forever */
setage(o, G_OLD); /* and old forever */
g->allgc = o->next; /* remove object from 'allgc' list */
o->next = g->fixedgc; /* link it to 'fixedgc' list */
g->fixedgc = o;
}
如果一个字符串没有在任何地方引用，将在GC阶段被回收。具体的gc流程是另一章的内容。传统的字符串比较算法根据字符串的长度逐位进行对比，其时间复杂度与字符串的长度线性相关，内化之后就只需要计算字符串的散列值了。变量存放的仅是字符串的引用。因此为了提高效率，应该尽量少的使用..来连接字符串，如果需要大量连接的操作，可以先将要连接的字符缓存在一个表中，然后用table.cancat()方法连接。
表实现（2021.3.14）
lua中表分为数组和散列表两个部分，任何数组不能储存的数据都会储存在散列表中，只要键值不为nil。
// 老版本定义
typedef union TKey {
struct {
TValuefields;
struct Node *next;
} nk;
TValue tvk;
} TKey;
// 5.4定义
/*
** Nodes for Hash tables: A pack of two TValue's (key-value pairs)
** plus a 'next' field to link colliding entries. The distribution
** of the key's fields ('key_tt' and 'key_val') not forming a proper
** 'TValue' allows for a smaller size for 'Node' both in 4-byte
** and 8-byte alignments.
*/
typedef union Node {
struct NodeKey {
TValuefields; /* fields for value */
lu_byte key_tt; /* key type */
int next; /* for chaining */
Value key_val; /* key value */
} u;
TValue i_val; /* direct access to node's value as a proper 'TValue' */
} 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; /* array part */
Node *node; // 散列桶起始位置
Node *lastfree; // any free position is before this position 散列通数组的最后位置
struct Table *metatable;
GCObject *gclist;
} Table;
Node是散列桶的节点类型，其中的值是前面定义的通用数据类型TValue，键会根据需要决定是否使用链表。在查找时，如果输入的key是一个正整数且小于数组的大小，那么会尝试在数组部分查找，否则尝试在散列表部分查找。
散列表用链表解决冲突，将hash相同的元素储存在一个链表中，查找时先计算元素的hash，然后在遍历对应链表的所有元素。为了以最大效率储存数据，lua用一个数组nums的第i个元素记录key在2^(i - 1)到2^i之间的元素数量，如果数组在每一个2次方位置容纳的元素数量都超过该范围的50%，我们就认为这个数组范围发挥了最大的效率。只有三个元素的表在依次添加时会执行三次重新散列的操作，而100万个元素的表只需要20次，因此如果我们需要很多长度很小的表，可以在创建时预先填充元素避免重新散列。
新建key
/*
** 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.
*/
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
TValue aux;
if (unlikely(ttisnil(key)))
luaG_runerror(L, "table index is nil");
else if (ttisfloat(key)) {
lua_Number f = fltvalue(key);
lua_Integer k;
if (luaV_flttointeger(f, &k, F2Ieq)) { /* does key fit in an integer? */
setivalue(&aux, k);
key = &aux; /* insert it as an integer */
}
else if (unlikely(luai_numisnan(f)))
luaG_runerror(L, "table index is NaN");
}
mp = mainpositionTV(t, key);
if (!isempty(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, keytt(mp), &keyval(mp));
if (othern != mp) { /* is colliding node out of its main position? */
/* 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 */
}
setempty(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, key);
luaC_barrierback(L, obj2gco(t), key);
lua_assert(isempty(gval(mp)));
return gval(mp);
}
迭代
表的迭代实现是luaH_next函数
取长度操作符“#”
在对表使用#时，会返回一个整数下标n，它满足t[n] ~= nil且t[n + 1] == nil，使用简单的二分法查找，因此如果表内存在空洞时它可能返回任何一个nil之前位置的下标。
其实现是函数luaH_getn，里面调用了一个luaH_realasize拿数组的真实size，返回的值其实是比当前alimit大的最小二次幂数，换言之如果以二进制表示alimit，那么返回的是它最高位往左一位为1其余位为0的数。
/*
** Returns the real size of the 'array' array
*/
LUAI_FUNC unsigned int luaH_realasize (const Table *t) {
if (limitequalsasize(t))
return t->alimit; /* this is the size */
else {
unsigned int size = t->alimit;
/* compute the smallest power of 2 not smaller than 'n' */
size |= (size >> 1);
size |= (size >> 2);
size |= (size >> 4);
size |= (size >> 8);
size |= (size >> 16); // 注意这里是迭代运算
#if (UINT_MAX >> 30) > 3
size |= (size >> 32); /* unsigned int has more than 32 bits */
#endif
size++;
lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size);
return size;
}
}