Re: SV: Progress Update

[Pierre Phaneuf <pp@ludusdesign.com>]

Bjarke Hammersholt Roune wrote:

> >>Thus, to edit a HashTable, one needs to call ConvertToDynTable(), edit the
> >>returned DynHashTable, and then call CreateFromDynTable(), passing the
> >>DynHashTable as its parameter. The DynHashTable can then be deleted.
> >>
> >How costly is the HashTable->DynHashTable conversion?
> >
> Well, to get data from a HashTable into a DynHashTable is almost free. All
> that is done in ConvertToDynTable() is the allocation of the DynHashTable,
> and a few assignments to properly empty the HashTable and move ownersip over
> to DynHashTable.
> 
> The other way around is a little more costly. DynHashTable maintains an
> array of data, which contains the data it was originally given by the
> creating HashTable, plus a linked list to handle new additions.
> 
> Now, to make a HashTable out of a DynHashTable, the array and the linked
> list of the DynHashTable has to be copied into one, new array. With that
> done, the job of the DynHashTable is finished. Then the HashTable needs to
> sort the array (it now uses qsort()), and then index it (ie, create a hash
> look-up table).

Why the heck isn't this a normal hash table? No need to sort, no need
for linked lists. For the (once in a while) table resizing, you need a
costly realloc and only binary logical operations (masking the
significant parts of the key (they are already hashed, since they're in
the hash table), giving you the straight index).

-- 
Pierre Phaneuf
http://ludusdesign.com/