httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mladen Turk" <mt...@mappingsoft.com>
Subject RE: What to do about tables?
Date Wed, 07 Nov 2001 19:22:37 GMT
> -----Original Message-----
> From: Martin Kraemer [mailto:Martin.Kraemer@Fujitsu-Siemens.com]
> Sent: 7. studeni 2001 2:00
> To: dev@httpd.apache.org
> Subject: Re: What to do about tables?
> 
> > On Sun, Nov 04, 2001 at 03:00:43PM -0800, Brian Pane wrote:
> > >...
> > > 2. Change the performance-sensitive fields in the httpd's
request_rec
> > >    from apr_table_t (like r->headers_in) to some different data
type
> > >    (e.g., "ap_http_headers_t") that supports O(log(n)) or O(1)
get/set
> > >    operations
> On Sun, Nov 04, 2001 at 07:05:17PM -0800, Greg Stein wrote:
> > I think this custom type would be a wrapper around an apr_hash_t.
> 
> Isn't there the problem that some headers are order-sensitive?
> Say, if there are several cookies, or several authentication protocol
> alternatives (Basic/Digest/Negotiate), then order might matter.
> 
> OTOH, each header class per se could be hashed, and multiple
occurrences
> would be iterated for the located hash node.
> 

I've proposed last month the apr_hlist which is exactly the needed
one... You have the ordered list with overlaid hash table. That way you
have ordered list with the option to have multiple keys and almost
constant access time.

Since the apr_hlist is a general key/data container (in fact it's
extended apr_hash) and the needed one here is the string one, there are
some overloads in that.

I'm currently working to extend the apr_table in such way (apr_htable).
Iterating through table elements will preserve the element index
approach, but getting and setting elements to table will have almost
constant times regardless of table size.

MT. 



Mime
View raw message