lua-users home
lua-l archive

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

I did some more thinking on the tree/graph problem I posted some days ago and
specifically about a mixed C/Lua implementation. The tree will internally be
implemented using linked lists, that is every node will have a linked list of
its children, but there will also be a Lua interface to it, a table hierarchy
with the needed __index and __newindex metamethods to manipulate the C linked
lists. This way I can have the nice Lua interface to manipulate the tree (like = {...}) and still traverse the it pretty much as fast as
possible from within C.That's nice. Only problem is implementing this thing
ins't that simple. The best scheme I came up with is this:

Let's assume there's a global root wich is an empty table with appropriate (see
below) __index and __newindex metamethods. Let's also assume that the registry
contatins two tables children and userdata and that children[root] is an empty
table and userdata[root] is a pointer to the root C node (all this is set-up in
some initialization C code).

As you might have guessed the children table will be used to hold a table of
children for each node and the userdata table to hold a pointer to it's C
counterpart. The metamethods would look like this (although this might resemble
Lua code it is in fact (Lua-like) pseudocode):

__newindex(t, k, v)
        udata = conmpute_c_node_from_lua_table(v)

        -- this table must always remain empty to ensure that
        -- its metamethods will trigger

        table = {}
        table.metatable.__newindex = __newindex
        table.metatable.__index = __index

        -- update the parent's children list
        children[t][k] = table

        -- create the new node's children and userdata entries
        children[table] = {}
        userdata[table] = udata

        parent_udata = userdata[t]
        link_c_nodes(parent_udata, udata)

__index(t, k)
        -- this should be an empty table with appropriate metamethods
        return children[t][k]

Well I'm off to sleep now (its 4:30am over here) so if any of you Lua gurus
can think of a better (simpler) way to implement this you'd better have it
posted before I wake up.