apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mladen Turk" <mt...@mappingsoft.com>
Subject RE: [PATCH] apr_hash.c -- Make table ordered
Date Thu, 11 Oct 2001 05:58:04 GMT
> -----Original Message-----
> From: Branko ─îibej [mailto:brane@xbc.nu]
> Sent: Wednesday, October 10, 2001 10:10 PM
> To: Mladen Turk
> Cc: APR Dev List; Apache Dev
> Subject: Re: [PATCH] apr_hash.c -- Make table ordered
>
>
> Mladen Turk wrote:
>
> >Hi,
> >
> >Here is the patch that makes the apr_hash table ordered in the
> way that the
> >apr_hash_first/apr_hash_next returns the values in order they
> were stored in
> >the table using apr_hash_set.
> >The patch could be IMO very usefull to solve the httpd release
> showstopper
> >Set...Filter Add...Filter, because one can retrive the entries ordered in
> >the way they are entered.
> >
>
> -1. This would add memory (and time) overhead to all hash tables
> everywhere.

The memory overhead is < 2% in real table (only one extra pointer per slot).
Time overhead happens only when deleting items from table (solvable by using
an extra int), but the walking through table works faster.

>
> A hash table is an unordered associative container. If you need
> ordering, there are other ways to do this. You could, for instance, put
> your objects into an array and use the hash table as an index over the
> array slots, or join them with a doubly-linked list.

That would be overhead indeed.

> But it makes no sense to do this / within/ the hash table implementation.

It's discussable what makes/makes-no sense :)
The question is where the hash table is used and for what purpose, not for
the sake of the theory itself.
How many entries are in the table itself? It is not used to store couple of
thousand records, not even couple of hundreds.

I see couple of usages of apr_array (just because they need ordered entries)
that would gain the performance benefit.

If the hash table implementation _must_ remain as such, then how about
introducing something like apr_shash?

MT.


Mime
View raw message