apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Branko ─îibej <br...@xbc.nu>
Subject Re: [PATCH] apr_hash.c -- Make table ordered
Date Thu, 11 Oct 2001 22:12:02 GMT
Sterling Hughes wrote:

>On Thu, 11 Oct 2001, Branko [ISO-8859-2] E`ibej wrote:
>>Mladen Turk wrote:
>>>I'll propose the two things:
>>>1. apr_btree to be able to do the range-based searches
>>Sounds useful. (I'd suggest implementing red-black trees, not AVL.)
>    why? avl is, too my knowledge, a faster algorithm for all intensive
>    purposes (faster insertion, equivalent lookup)..
Really? I thought it was just the opposite, at least in the amortized 
case. Well, never mind.

>>>2. apr_shash to be able to sort the hash table.
>>Do you mean actually sort elements in the table by some key, or just
>>make sure traversal is in the order of insertions? If the first, it's
>>probably better to use a tree. If the second, then there should be a way
>>to insert an element in a specific place in the traversal.
>    a hash is a random access data structure, i don't see any reason
>    that in-place insertions and deletions should be allowed, unless of course
>    you want to use it in place of a dlist.

What hw's proposing is *not* a hash table. He wants a structure with 
near-constant-time key-based lookup, and a well-defned traversal order.

>    which begs the question, why would you want to use a hash in place of a
>    dlist ;)
Whenever you want fast access to anything but the head or tail.

Brane ─îibej <brane@xbc.nu> http://www.xbc.nu/brane/

View raw message