Re: Lua table implementation

[Dave Dodge <dododge@...>]

On Tue, Oct 03, 2006 at 08:11:49PM +0200, Wim Couwenberg wrote:
> I too have written a generic hash table implementation that I use in my 
> C projects.  It differs from Lua's hash table in one respect, with some 
> nice consequences.  To explain, here is the structure of an entry (in 
> pseudo speak):
> 
> struct hash_entry
> {
>   struct hash_entry *root; /* points to the root of the chain */
>   struct hash_entry *next; /* chains hash identical items */
>   data_type data; /* entry data */
> };

I don't understand what the relationship is between the root and next
pointers in a particular hash_entry instance.  From your description
it doesn't sound like there really is any relationship, which would
suggest that it could be implemented about as simply but more flexibly
by splitting them out into two separate arrays:

  struct hash_entry
  {
    struct hash_entry *next; /* chains hash identical items */
    data_type data; /* entry data */
  };

  struct table_slot
  {
    struct hash_entry *root; /* points to the root of the chain */
  };

Then you can set the sizes of the table_slot and hash_entry arrays
independently based on whether you want long or short chains on
average.  For example if you consider chains of 2-3 entries to be
acceptable then you can set the size of the hash_entry array 2-3 times
as large as the table_slot array -- without paying the overhead of
having a root pointer for every entry.  You can also independently
change the sizes of the arrays when rehashing.  For example if you
change the size of one of the arrays, the other can be rehashed
in-place.

Or maybe I'm just missing something?

                                                  -Dave Dodge