lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

for k,v in pairs(tbl) do end -->
1 local tbl = {}
2 local iter_func, tbl, init = pairs(tbl)
3 local k, v = iter_func(tbl, init) --iter_func is next(luaB_next)
4 while k do
5     k, v = iter_func(tbl, k)
6 end

tbl = {A1=1, A2=1, A3=1, B1=1, B2=1}
struct Table Node[]: |... |A1|...|B1| ...|B2|...|A3|...|A2|...|
                                             i        j        k
Suppose hash(Ai)、hash(Bi) are equal.
Link: A1->A2->A3, B1->B2

luaB_next is a normal C function, it is stateless and doesn't hold
information about iteration,
so pairs(tbl) needs to find out all key's position in Node[].
Take next(tbl, "B2") as an example:
1. find the mainpostion of B2: i
2. Node[i] is B1, B1 != B2, try Node[i]->next: j;
3. Node[j] == B2, look for the first not null value from j+1,
    which is A3,so next(tbl, "B2") returns "A3".
The overhead of next(tbl, "B2") equals to tbl["B2"] (retrieve "B2").
table.len() is widely used in our project:
function table.len(t)
    local cnt = 0
    for k,v in pairs(t) do
        cnt = cnt + 1
    return cnt
and the overhead of table.len() equals to retrieving all keys from table.
why pairs doesn't return a C closure with an integer upvalue to hold
the last key's position in Node[] ?
I think this can be improved.

Python2.7 dict(hashmap) also stores all key,value in an array
(Include/dictobject.h PyDictEntry ma_table[]).
dict.iteritems() returns a dict iter object, which use an integer to
represent the last key's position in ma_table[]. (Objects/dictobject.c
struct dictiterobject Py_ssize_t di_pos)