Lua实现总结

复习lua实现的时候才发现之前写了不少东西，但也许之前看的太快，到最后变成了搬运帖子或书上的内容，没有真正学进去，工作的几年也疏于复习，导致现在基本得重新看，好像一下又回到了刚毕业找工作的那个夏天，感叹时间为什么不能多一些，让面试能更有把握。

悟已往之不谏，知来者之可追。

主要依据构建lua解释器系列文章，尽量以总结的形式，少放代码。

函数调用

通过栈进行，之前一直没理解这个栈是如何构建的，其实是lua_State和global_State初始化的时候预分配了空间，然后储存了那个内存开头的地址作为StkId stack，使用加减就能移动到想去的内存片段中，分配时会多分配20个位置的空间，用来在元素超出时有一个缓冲，不至于崩溃。lua_State内部有一个CallInfo链表，储存函数调用信息，每次有函数调用时会创建一个新节点加进去，调用结束后被释放，然后执行下一个ci节点。

与C的交互

这个内容在另一篇笔记中有详细记录，这里一样只写大概思路。

Lua调C

有两种方法，第一种是在lua的运行环境中直接使用lua_register注册全局一个函数（lua_CFunction），它相当于在全局表_G种添加了这个函数，当在lua按注册的名字调用这个函数时，它就可以从栈中获取lua侧传进来的参数之后处理，把结果push到栈中，并返回要return的数量。

另一种方法是在C定义一个luaopen_mylib的函数，其中使用luaL_newlib注册需要的模块函数，然后调用require("mylib")。 require如果找不到指定的lua文件，它就会搜索对应名称的C标准库，等价于调用

package.loadlib("mylib.so", "luaopen_mylib")

查找前缀为luaopen_xxx的函数是一种约定，这样在栈中就会留下一个拥有这些函数的table，lua便可以进行调用。 luaopen_mylib中可以直接push一个函数在栈上，如此一来lua侧获取的就是一个函数而非一个table。

C调Lua

1. 初始化lua环境
2. 调用luaL_dofile加载lua文件，如果有全局函数便可以拿到
3. 调用lua_getglobal拿到全局函数push进栈
4. 将需要的参数（如果有）push进栈
5. 调用lua_pcall，它会根据需要的参数数量从栈中获取参数，然后调用栈上的函数，并把结果push进栈
6. 从栈上拿到调用结果

Table

Table结构中分别缓存了一个数组一个哈希表，有一个lsizenode变量用来表示哈希表的大小，但真正的大小是2的lsizenode次方，这么做的目的是在取余的时候可以用位运算提高效率，而且哈希表的扩容也是成倍的，虚幻中哈希表在映射的时候也用了同样的方法。哈希表实际上也是一个数组，每个Node中除了有key和value之外，还有下个元素的下标，来达到链接的目的，这点也和虚幻中的很多实现一样。

• 查找：当key为int类型，先看看是否在数组范围内，如果是则直接返回数组对应位置的元素，如果不是则直接将其映射到哈希表中（对size取余），从表头开始依次比较是否找到了对应的key，找到了返回其值，没找到返回luaO_nilobject。如果key的类型不是int，则先计算哈希值然后进行后面的操作。

Table中还有一个lastfree成员，指向哈希表中最后一个空节点的位置，在增加新元素时用来寻找下一个空节点的位置。

• 写入：同样如果key是int类型则先看看在不在数组范围内，如果在就直接写，如果不在就走哈希表。定位到哈希表位置后，如果发生冲突，要先判断一下该位置已有的元素是否是属于这个节点的，因为当冲突发生时会通过lastfree找到一个有效位置将数据放进来，但找到的节点可能对应的是另一个key算出来的哈希值，也就是说它占了一个其他桶的位置，这时就需要先把这个元素移走，然后将新数据放进来。

哈希表会在增加或删除元素的时候进行resize，它的方式是先统计所有int类型的key，看看在每个2^{i - 1}至2ⁱ（i = 0 ~ 32）区间内的数量，然后从i为0的情况开始累加，计算出一个尽可能大的，占用率超过百分之五十的数组大小，为新的数组大小，剩下的不能放进数组中的元素，则是新的哈希表大小（这里有点疑问，如果直接按这个大小那哈希表上来就是满的，下次如果发生哈希冲突又要重新散列？）

userdata

用户自定的类型都会以userdata存储

GC

和虚幻一样，使用的是标记清除法。