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

Re: SV: Progress Update

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