[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: stringtable and Table Hashing
- From: Wim Couwenberg <debosberg@...>
- Date: Tue, 1 Jun 2004 13:53:38 -0700 (PDT)
Although Knuth gives this reference for "Brent's
variation" (in Sorting and Searching) it is not so
relevant for Lua's implementation, I think. But
ltable.c is an excellent reference! ;-)
About the special string hash table: Lua uses a string
object (TString) to represent strings and maps equal C
strings to the *same* TString. To do this it uses the
special string hash table with ordinary C strings
(i.e. const char* + length) as keys and TString* as
values. The "usual" hash table can not be used
because a C string is not a Lua type that can occur as
a key (or value) in such a table.
Testing two TStrings for equality now takes just a
simple pointer comparison and not a full memcmp call.
This is a huge gain because strings are very common as
table keys (almost all identifiers in a Lua program
end up as keys in a table.)
Do you Yahoo!?
Friends. Fun. Try the all-new Yahoo! Messenger.