lua-users home
lua-l archive

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

Leo Razoumov wrote:
Alternatively, as I suggested in an earlier post to this thread, you
can use self-balancing trees like RB-tree to resolve collisions
instead of lists when lists get larger. Most of the time current Lua
hash-table implementation is in effect but it switches to RB-tree
buckets when list performance gets in trouble (e.g. when under
attack). RB-tree give you O(log(N)) performance which is sufficient to
defeat the attack.

I started writing an RB-tree patch where I use one tree for every bucket in the global string table. It defeats my test attack quite well, but it still seems to have its own bugs...

I only changed the implementation of the global string table. For other tables I just #define'd hashstr to hashpointer. Since strings are internalized, this should work just as well and is quite simple.

I hope that I can find the time to get the bugs out of my patch. (Has somebody else already written such a patch?)

-- David