Ich weiĂ nichts ĂŒber dich, aber ich stöbere gerne in den Eingeweiden verschiedener Systeme herum. Und in diesem Artikel möchte ich ĂŒber die interne Struktur von Lua-Tabellen und ihre Funktionen sprechen. Lua ist meine primĂ€re Programmiersprache fĂŒr den Dienst, und um guten Code zu schreiben, muss man zumindest ein wenig verstehen, was hinter den Kulissen passiert. Neugierig frage ich nach mir.
Lua hat mehrere Implementierungen und mehrere Versionen. Dieser Artikel konzentriert sich hauptsÀchlich auf LuaJIT 2.1.0, das in Tarantool verwendet wird. Unsere Version ist im Vergleich zu authentischem LuaJIT leicht gepatcht, aber diese Unterschiede betreffen keine Tabellen.
Zu den Tabellen in der Implementierung von PUC-Rio gibt es eine weitere gute PrÀsentation [1] , wenn Sie interessiert sind.
Bildungsprogramm
Lua â , . ( ), key-value . ( nil). , â [2].
local t1 = {}
local t2 = { 'Sunday', 'Monday', 'Im tired' }
local t3 = {
cat = 'meow',
dog = 'woof',
cow = 'moo',
}
local t4 = {
'k1', 'k2', 'k3'
['k1'] = 'v1',
['k2'] = 'v2',
['k3'] = 'v3',
}
LuaJIT [3] ( , , ):
typedef struct GCtab {
/* GC stuff */
MRef array; /* Array part. */
MRef node; /* Hash part. */
uint32_t asize; /* Size of array part (keys [0, asize-1]). */
uint32_t hmask; /* Hash part mask (size of hash part - 1). */
} GCtab;
: -. . , LuaJIT , . , , Lua, , . : , . , .
LuaJIT tostring(), stdout printf().
, , [4]. :
diff --git a/src/lj_strfmt.c b/src/lj_strfmt.c
index d7893ce..45df53c 100644
@@ -392,6 +392,51 @@ GCstr * LJ_FASTCALL lj_strfmt_obj(lua_State *L, cTValue *o)
if (tvisfunc(o) && isffunc(funcV(o))) {
p = lj_buf_wmem(p, "builtin#", 8);
p = lj_strfmt_wint(p, funcV(o)->c.ffid);
+ } else if (tvistab(o)) {
+ GCtab *t = tabV(o);
+ /* print array part */
+ printf("-- a[%d]: ", asize);
+ for (i = 0; i < asize; i++) {
+ // printf(...);
+ }
+
+ /* print hashmap part */
+ printf("-- h[%d]: ", hmask+1);
+ for (i = 0; i <= hmask; i++) {
+ // printf(...);
+ }
} else {
p = lj_strfmt_wptr(p, lj_obj_ptr(o));
}
, :
t = {}
tostring(t)
, LuaJIT 0 1 -, nil nil (.. ). :
t["a"] = "A"
t["b"] = "B"
t["c"] = "C"
tostring(t)
, , -. , â . LuaJIT [5] [5] ( ).
, , . traverse(), for .
traverse- [4]. .
function traverse(fn, t)
local str = ''
for k, v, n in fn(t) do
str = str .. string.format('%s=%s ', k, v)
end
print(str)
end
t1 = {a = 1, b = 2, c = 3}
tostring(t1)
t2 = {c = 3, b = 2, a = 1}
tostring(t2)
traverse(pairs, t1)
traverse(pairs, t2)
: . -, .
t2["c"] = nil
traverse(pairs, t2)
tostring(t2)
print(next(t2, "c"))
, . â , .
: , lookup' . . main node , predecessor main ( ). O(n), . dead node . . [5].
, , . â :
t = {1, 2}
tostring(t)
Lua , . , LuaJIT . / .
, , ( ) â :
t = {[2] = 2, 1}
tostring(t)
, , -. , : , .
: ?: LuaJIT, Lua, .
, .
$ luac -l - <<< "t1 = {1, 2}"
1 [1] NEWTABLE 0 2 0 -- 2 , 0 -
...
â 1 -.
$ luac -l - <<< "t2 = {[2] = 2, 1}"
1 [1] NEWTABLE 0 1 1 -- 1 , 1 -
...
, , , . LuaJIT -, . , . .
pairs()
pairs() . . . LuaJIT pairs() , -. - -, :
t = table.new(4, 4)
for i = 1, 8 do t[i] = i end
tostring(t)
traverse(pairs, t)
: ?: table.new(narr, nrec) â lua_createtable(L, a, h) Lua C API. (, ), .
. ( ) :
t[9] = 9
tostring(t)
. 99.9 % "" Lua , .
table.getn()
- . , â Lua [6].
3.4.6 â The Length Operator
The length of a table t is only defined if the table is a sequence, that is,
the set of its positive numeric keys is equal to {1..n} for some non-negative
integer n. In that case, n is its length. Note that a table like
{10, 20, nil, 40}
is not a sequence, because it has the key 4 but does not have the key 3. (So,
there is no n such that the set {1..n} is equal to the set of positive numeric
keys of that table.) Note, however, that non-numeric keys do not interfere with
whether a table is a sequence.
, . â Lua undefined behavior. "" . LuaJIT lj_tab_len [7] :
/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
MSize LJ_FASTCALL lj_tab_len(GCtab *t);
LuaJIT "". , , LuaJIT , :
print(#{nil, 2})
print(#{[2] = 2})
: ?: .
tostring({nil, 2})
tostring({[2] = 2})
LuaJIT , . , -, .
, . , undefined behavior . , .
table.sort()
1 #t, . , , :
local function is_array(t)
if type(t) ~= 'table' then
return false
end
local i = 0
for _, _ in pairs(t) do
i = i + 1
if type(t[i]) == 'nil' then
return false
end
end
return true
end
Lua, , , , .
Pack / unpack
? , - . , :
local function vararg(...)
local args = {...}
end
â , .
- vararg(nil, "err"), . unpack(t), ( , , UB).
Lua [8] :
6.5 â Table Manipulation
unpack (list [, i [, j]])
Returns the elements from the given table. This function is equivalent to
return list[i], list[i+1], ···, list[j]
except that the above code can be written only for a fixed number of elements.
By default, i is 1 and j is the length of the list, as defined by the length
operator #list.
, unpack(t, 1, #t) unpack(t, 1, n), n? , . varargs, table.pack(), :
t = table.pack(nil, 2)
tostring(t)
traverse(pairs, t)
print(unpack(t, 1, t.n))
LuaJIT ( Tarantool) table.pack - , -DLUAJIT_ENABLE_LUA52COMPAT. :
function table.pack(...)
return {..., n = select('#', ...)}
end
select('#', ...) [9], . , Lua [10] â , Lua C (Lua C API). .
ipairs()
â . . ipairs , while:
local i = 1
while type(t[i]) ~= 'nil' do
i = i + 1
end
, "" undefined behavior â .
t = {1, 2, nil, 4}
print(#t)
traverse(ipairs, t)
FFI
, type(x) ~= 'nil'. x == nil? , LuaJIT, PUC-Rio Lua, cdata:
ffi = require('ffi')
NULL = ffi.new('void*', nil)
print(type(NULL))
print(type(nil))
print(NULL == nil)
if NULL then print('NULL is not nil') end
Tarantool, box.NULL. â if NULL ( if nil), NULL == nil.
LuaJIT â FFI . Lua, FFI Lua . LuaJIT . , [11]:
Lua tables may be indexed by cdata objects, but this doesn't provide any useful
semantics â cdata objects are unsuitable as table keys!
A cdata object is treated like any other garbage-collected object and is hashed
and compared by its address for table indexing. Since there's no interning for
cdata value types, the same value may be boxed in different cdata objects with
different addresses. Thus t[1LL+1LL] and t[2LL] usually do not point to the
same hash slot and they certainly do not point to the same hash slot as t[2].
, cdata- ( void*), , . Tarantool:
tarantool> t = {1}; t[1ULL] = 2; t[1ULL] = 3;
---
...
tarantool> t
---
- 1: 1
1: 3
1: 2
...
tarantool> t[1ULL]
---
- null
...
, , cdata , . uuid [12] clock.time64() Tarantool. , unsigned .
, FFI, :
tarantool> t = {'normal one'}
t[1.0 + 2^-52] = '1.0 + 2^-52'
t[0.1 + 0.3*3] = '0.1 + 0.3*3'
---
...
tarantool> t
---
- 1: normal one
1: 1.0 + 2^-52
1: 0.1 + 0.3*3
...
#t . â Undefined behavior.ipairs() while type(t[i]) ~= 'nil' â , , .pairs() , .unpack, table.sort, table.insert, table.remove, -, undefined behavior #t.- "" (ffi) . .
[1] The basics and design of Lua table ( slideshare.net).
[2] Programming in Lua â Tables
[3] GitHub â LuaJIT/LuaJIT â lj_obj.h
[4] GitHub â rosik/luajit:habr-luajit-tables
[5] â - â
[5a] GitHub â LuaJIT/LuaJIT â Issue #494.
[6] Lua 5.2 Reference manual â The Length Operator
[7] GitHub â LuaJIT/LuaJIT lj_tab.c
[8] Lua 5.1 Reference manual â Basic Functions â unpack
[9] Lua 5.1 Reference manual â Basic Functions â select
[10] Lua 5.1 Reference manual â The Stack
[11] GitHub â LuaJIT/LuaJIT â ext_ffi_semantics.html
[12] Tarantool » 2.2 » Reference » Built-in modules reference » Module uuid
[Bonus] Learn X in Y Minutes, where X=Lua
[Bonus] â Lua.