Lua設計與實現–讀書筆記
lua簡介
C++底層核心模組，暴露核心介面給lua腳本層，網路的收發都在c++層完成，本書簡述lua解釋器的實現原理，工業級腳本語言
特性：簡潔高效可移植可嵌入可擴展
純C編寫
Lua的數據結構、Lua虛擬機、Lua的其他內容
我缺少的知識：詞法分析、語法分析、遞歸下降分析、BNF規則
Lua程式碼是解釋成lua虛擬機能識別的位元組碼而運行的
- 翻譯成位元組碼
- 位元組碼裝載到虛擬機執行
Lua是有宿主系統的
Lua採用一種通用的數據類型來表示所有的類型，Lua只有字元串和表兩種基本的數據結構
一種通用的數據類型：lua_TValue
- 一個欄位存儲數據類型
- 存儲不同的數據類型的數據（聯合體）
commonHeader+union，lua還要標出處理GC的對象
配圖：
字元串
每當創建字元串時，會先查找記憶體中是否有一份相同的字元串數據，如果存在就直接復用，將引用直接指向字元串數據，否則就重新創建一份數據，這樣在進行字元串數據比較和查找時性能會提升不少，系統內部維護了一個全局的字元串的表用來存放字元串（LUA虛擬機使用一個散列桶來管理，global_state的strt），比較時可以直接比較字元串散列值，這樣也是有空間優化，相同字元串只有一份數據
應當盡量少的使用字元串連接符，每次使用都會創建一個新的字元串，大量重複的相同字元連接可以用一個table緩衝區一個字元一個字元的快取起來，然後再調用table.concat將其全部連接
Table
有數組和散列表部分，唯一的要求就鍵值不能為nil
數組從1開始索引，內涵散列桶數組起點和終點的指針還有元表，意思0和負數的索引都是哈希表裡的內容，如果數字的很大，超過了數組長度則是在散列表裡面存
存的數據有可能在數組或者在散列表部分
查找數據：使用key來查找。我們看這個key是否為正整數且他是否大於0且小於等於數組長度，在則在數組中查找，不在則跑到散列表去查
設置數據：set setnum setstr三個set數據的函數先找對應的key，找不到則內部是調用一個newkey函數分配一個新key，大小不夠會重新散列
個人實踐規律：取長度符號#
取長度，只對錶的序列部分進行，序列指的是表的一個子集，
當既有數組部分又有散列表部分，優先取數組部分長度，
當只有數組部分時候取數組的長度
（#{1,2,3，nil，4,5,6,} == 6）
當散列表的key和數組的Index一致的時候，遇到[num] = nil的時候便停止計數
(#{[1] = 10,[2]=20,[3]=nil,[4]=60} ==2)
(#{[1] = 10,[2]=20,[3]=32,[5]=60} ==3) 缺少4
當只有散列表部分時，取key從1開始的最大正整數
(#{["asd"] = 10,["sd1"]=20,["aasd"]=nil,[45]=60} == 0)
(#{["asd"] = 10,["sd1"]=20,["aasd"]=nil,[1]=60,[2]=899} == 0)
一般要規避重新散列操作，一般通過只使用數組部分、預分配等方式來避免重新散列
盡量不要混用數組和散列表部分，一個table最好只放一類數據
lua實現一個隊列
網上的版本，用起來，pushright存數據會往數組裡的填很多東西，pushleft突破了0，會往哈希表裡填東西，如果一直popleft多了則數組部分的頭部會被回收嗎？推測不會，數組部分的指針指向的數組整體，前面幾個元素回收了頭部會改變，如果是popright回收數組部分是可以理解的，如果pop的是哈希的部分應該是可以回收的
List = {}
function List.new ()
return {first = 0, last = -1}
end
function List.pushleft (list, value)
local first = list.first - 1
list.first = first
list[first] = value
end
function List.pushright (list, value)
local last = list.last + 1
list.last = last
list[last] = value
end
function List.popleft (list)
local first = list.first
if first > list.last then error("list is empty") end
local value = list[first]
list[first] = nil -- to allow garbage collection
list.first = first + 1
return value
end
function List.popright (list)
local last = list.last
if list.first > last then error("list is empty") end
local value = list[last]
list[last] = nil -- to allow garbage collection
list.last = last - 1
return value
end
插入、刪除時間複雜度 O（1），空間複雜度可能會隨著消息變大而變大，O（n）
使用Insert和Remove的版本，空間複雜度是O（1）的，時間複雜度是（n）
關於清空lua table
a = {1,2,3,4,5}
function upDate(t)
print("====")
print(t)
t = {}
print(t)
end
upDate(a)
print(a)
print(a[1])
這裡設置t = {} 或者 t = nil都不會真的清空table對象 a
只是處理了變數和值之間的關係，t的地址是值傳遞的，嘗試用一個新表的地址給它賦值會出現函數參數值傳遞，對地址t引用的實際值並不會有影響，但是通過t改動引用table里的實際值是會對a有影響的比如t[1]=999，這裡就是通過地址改動到了實際值的區域
我的方法是使用——table套table，其實就是相當於指針的指針
local a = {1,2,3,4,5}
local b = {9,99,999,9999}
function upDate(t)
print("====")
print(t.a)
t.a = nil
--a = nil
print(t.a)
end
local ta ={}
ta.a = a
upDate(ta)
print(ta.a)
print(a)
這樣子ta.a可以便可以正確的賦值為nil了
我實現的一份LuaQueue程式碼
local LuaQueue = {}
-- pure array table, if you want to iterate use lua "ipairs"
function LuaQueue.New()
return {_length = 0,_maxLength=10,_queue={}}
end
function LuaQueue.SetMaxLength(queue,length)
if(queue==nil) then
error("Queue is nil")
end
queue._maxLength = length
end
function LuaQueue.GetLength(queue)
if(queue==nil) then
error("Queue is nil")
end
return queue._length
end
--push in array last pos O(1)
function LuaQueue.Push(queue,val)
if(queue==nil) then
error("Queue is nil")
end
if(queue._length<queue._maxLength) then
table.insert(queue._queue,val)
queue._length = queue._length+1
else
error("Already reach last pos")
end
end
--O(n)
function LuaQueue.Pop(queue)
if(queue==nil) then
error("Queue is nil")
end
if(queue._length>0) then
table.remove(queue._queue,1)
queue._length = queue._length-1
else
error("Queue is Empty")
end
end
function LuaQueue.GetData(queue)
if(queue==nil) then
error("Queue is nil")
end
local data={}
if(queue._length>0) then
for _,v in ipairs(queue._queue) do
table.insert(data,v)
end
return data
else
print("Queue is Empty")
end
end
function LuaQueue.ClearData(queue)
if queue == nil then
error("Queue is nil")
end
queue._queue = {}
queue._length = 0
end
--[[Example:
local testQueue = LuaQueue.New()
LuaQueue.Push(testQueue,10)
LuaQueue.Push(testQueue,20)
LuaQueue.Push(testQueue,30)
LuaQueue.Push(testQueue,40)
local data = LuaQueue.GetData(testQueue)
for _,v in pairs(data) do
print(v)
end
print("-------------------------------------")
LuaQueue.Pop(testQueue)
local data = LuaQueue.GetData(testQueue)
for _,v in pairs(data) do
print(v)
end
print("-------------------------------------")
LuaQueue.Pop(testQueue)
LuaQueue.Push(testQueue,909)
local data = LuaQueue.GetData(testQueue)
for _,v in pairs(data) do
print(v)
end
LuaQueue.ClearData(testQueue)
--]]
