apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Greg Stein <gst...@lyra.org>
Subject Re: [PATCH] apr_hash.c -- Make table ordered
Date Thu, 11 Oct 2001 06:46:59 GMT
I'm with Branko here...

-1

Hash tables are unordered entities. Pure and simple. If you want something
else, then introduce something else. But don't mess up hash tables to add a
concept which just doesn't belong.

Cheers,
-g

On Thu, Oct 11, 2001 at 07:58:04AM +0200, Mladen Turk wrote:
> > -----Original Message-----
> > From: Branko Cibej [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.

-- 
Greg Stein, http://www.lyra.org/

Mime
View raw message