You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Mladen Turk <mt...@mappingsoft.com> on 2001/10/10 21:02:21 UTC
[PATCH] apr_hash.c -- Make table ordered
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.
MT.
cvs server: Diffing .
Index: apr_hash.c
===================================================================
RCS file: /home/cvspublic/apr/tables/apr_hash.c,v
retrieving revision 1.25
diff -u -r1.25 apr_hash.c
--- apr_hash.c 2001/09/06 06:34:59 1.25
+++ apr_hash.c 2001/10/10 18:40:55
@@ -114,7 +114,8 @@
apr_pool_t *pool;
apr_hash_entry_t **array;
apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
- int count, max;
+ apr_hash_entry_t **list;
+ int count, max;
};
#define INITIAL_MAX 15 /* tunable == 2^n - 1 */
@@ -136,6 +137,7 @@
ht->count = 0;
ht->max = INITIAL_MAX;
ht->array = alloc_array(ht, ht->max);
+ ht->list = alloc_array(ht, ht->max);
return ht;
}
@@ -146,13 +148,14 @@
APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)
{
- hi->this = hi->next;
- while (!hi->this) {
+
if (hi->index > hi->ht->max)
return NULL;
- hi->this = hi->ht->array[hi->index++];
- }
+ hi->this = hi->ht->list[hi->index++];
+ if (!hi->this)
+ return NULL;
hi->next = hi->this->next;
+
return hi;
}
@@ -189,18 +192,23 @@
{
apr_hash_index_t *hi;
apr_hash_entry_t **new_array;
+ apr_hash_entry_t **new_list;
int new_max;
- int i;
+ int i, j;
new_max = ht->max * 2 + 1;
new_array = alloc_array(ht, new_max);
+ new_list = alloc_array(ht, new_max);
+ j = 0;
for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {
i = hi->this->hash & new_max;
hi->this->next = new_array[i];
new_array[i] = hi->this;
+ new_list[j++] = new_array[i];
}
ht->array = new_array;
ht->max = new_max;
+ ht->list = new_list;
}
/*
@@ -285,6 +293,7 @@
he->klen = klen;
he->val = val;
*hep = he;
+ ht->list[ht->count] = he;
ht->count++;
return hep;
}
@@ -307,10 +316,19 @@
const void *val)
{
apr_hash_entry_t **hep;
+ int i, j;
hep = find_entry(ht, key, klen, val);
if (*hep) {
if (!val) {
- /* delete entry */
+ /* delete entry */
+ for (i = 0; i < ht->count; i++) {
+ if (ht->list[i] == *hep) {
+ for (j = i; j < ht->count - 1; j++)
+ ht->list[j] = ht->list[j+1];
+ ht->list[j] = NULL;
+ break;
+ }
+ }
*hep = (*hep)->next;
--ht->count;
}
@@ -362,6 +380,7 @@
res->count = base->count;
res->max = (overlay->max > base->max) ? overlay->max : base->max;
res->array = alloc_array(res, res->max);
+ res->list = alloc_array(res, res->max);
new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * res->count);
j = 0;
for (hi = apr_hash_first(NULL, (apr_hash_t*)base); hi; hi =
apr_hash_next(hi)) {
@@ -373,6 +392,7 @@
new_vals[j].hash = hi->this->hash;
new_vals[j].next = res->array[i];
res->array[i] = &new_vals[j];
+ res->list[j] = res->array[i];
j++;
}
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Branko Čibej <br...@xbc.nu>.
Sterling Hughes wrote:
>On Thu, 11 Oct 2001, Branko [ISO-8859-2] E`ibej wrote:
>
>>Mladen Turk wrote:
>>
>>>OK!
>>>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 <br...@xbc.nu> http://www.xbc.nu/brane/
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Sterling Hughes <st...@designmultimedia.com>.
On Thu, 11 Oct 2001, Branko [ISO-8859-2] Èibej wrote:
> Mladen Turk wrote:
>
> >OK!
> >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)..
> >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.
which begs the question, why would you want to use a hash in place of a
dlist ;)
-Sterling
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Branko Čibej <br...@xbc.nu>.
Mladen Turk wrote:
>OK!
>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.)
>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.
>How that sounds?
>
All of this should go into apr-util, not apr.
--
Brane Čibej <br...@xbc.nu> http://www.xbc.nu/brane/
RE: [PATCH] apr_hash.c -- Make table ordered
Posted by Mladen Turk <mt...@mappingsoft.com>.
> -----Original Message-----
> From: Greg Stein [mailto:gstein@lyra.org]
> Sent: 10. listopad 2001 23:47
> To: Mladen Turk
> Cc: brane@xbc.nu; APR Dev List
> Subject: Re: [PATCH] apr_hash.c -- Make table ordered
>
> 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.
OK!
I'll propose the two things:
1. apr_btree to be able to do the range-based searches
2. apr_shash to be able to sort the hash table.
How that sounds?
MT.
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Greg Stein <gs...@lyra.org>.
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/
RE: [PATCH] apr_hash.c -- Make table ordered
Posted by Mladen Turk <mt...@mappingsoft.com>.
> -----Original Message-----
> From: Justin Erenkrantz [mailto:jerenkrantz@ebuilt.com]
> Sent: 10. listopad 2001 23:10
> To: Mladen Turk
> Cc: APR Dev List
> Subject: Re: [PATCH] apr_hash.c -- Make table ordered
>
> On Thu, Oct 11, 2001 at 07:58:04AM +0200, Mladen Turk wrote:
> > 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.
>
> That can't be realistically answered by the APR library.
>
> In point of fact, mod_mbox uses the hash table to store all of the
> message IDs when computing threads. (It uses DBMs to store the
> complicated information, but it uses the hash when doing the threading
> calculation because of the insanely fast in-memory lookups keyed off
> of the Message-IDs.)
>
> We have at least one mbox file with about 2,000 messages. -- Justin
It was just a figure of speech :)
An excellent example!
What is the real table size (containing messages) compared to 2000
pointers?
What is the overhead of converting hash tables to a SLL (MBOX_LIST) you
are using now, compared to simply sorting pointers?
The patch does not interfere with the in-memory lookups at all.
MT.
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Justin Erenkrantz <je...@ebuilt.com>.
On Thu, Oct 11, 2001 at 07:58:04AM +0200, Mladen Turk wrote:
> 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.
That can't be realistically answered by the APR library.
In point of fact, mod_mbox uses the hash table to store all of the
message IDs when computing threads. (It uses DBMs to store the
complicated information, but it uses the hash when doing the threading
calculation because of the insanely fast in-memory lookups keyed off
of the Message-IDs.)
We have at least one mbox file with about 2,000 messages. -- justin
RE: [PATCH] apr_hash.c -- Make table ordered
Posted by Mladen Turk <mt...@mappingsoft.com>.
> -----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.
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Branko Čibej <br...@xbc.nu>.
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.
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. But it makes no
sense to do this / within/ the hash table implementation.
>
>
>
>MT.
>
>cvs server: Diffing .
>Index: apr_hash.c
>===================================================================
>RCS file: /home/cvspublic/apr/tables/apr_hash.c,v
>retrieving revision 1.25
>diff -u -r1.25 apr_hash.c
>--- apr_hash.c 2001/09/06 06:34:59 1.25
>+++ apr_hash.c 2001/10/10 18:40:55
>@@ -114,7 +114,8 @@
> apr_pool_t *pool;
> apr_hash_entry_t **array;
> apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
>- int count, max;
>+ apr_hash_entry_t **list;
>+ int count, max;
> };
> #define INITIAL_MAX 15 /* tunable == 2^n - 1 */
>
>@@ -136,6 +137,7 @@
> ht->count = 0;
> ht->max = INITIAL_MAX;
> ht->array = alloc_array(ht, ht->max);
>+ ht->list = alloc_array(ht, ht->max);
> return ht;
> }
>
>@@ -146,13 +148,14 @@
>
> APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)
> {
>- hi->this = hi->next;
>- while (!hi->this) {
>+
> if (hi->index > hi->ht->max)
> return NULL;
>- hi->this = hi->ht->array[hi->index++];
>- }
>+ hi->this = hi->ht->list[hi->index++];
>+ if (!hi->this)
>+ return NULL;
> hi->next = hi->this->next;
>+
> return hi;
> }
>
>@@ -189,18 +192,23 @@
> {
> apr_hash_index_t *hi;
> apr_hash_entry_t **new_array;
>+ apr_hash_entry_t **new_list;
> int new_max;
>- int i;
>+ int i, j;
>
> new_max = ht->max * 2 + 1;
> new_array = alloc_array(ht, new_max);
>+ new_list = alloc_array(ht, new_max);
>+ j = 0;
> for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {
> i = hi->this->hash & new_max;
> hi->this->next = new_array[i];
> new_array[i] = hi->this;
>+ new_list[j++] = new_array[i];
> }
> ht->array = new_array;
> ht->max = new_max;
>+ ht->list = new_list;
> }
>
> /*
>@@ -285,6 +293,7 @@
> he->klen = klen;
> he->val = val;
> *hep = he;
>+ ht->list[ht->count] = he;
> ht->count++;
> return hep;
> }
>@@ -307,10 +316,19 @@
> const void *val)
> {
> apr_hash_entry_t **hep;
>+ int i, j;
> hep = find_entry(ht, key, klen, val);
> if (*hep) {
> if (!val) {
>- /* delete entry */
>+ /* delete entry */
>+ for (i = 0; i < ht->count; i++) {
>+ if (ht->list[i] == *hep) {
>+ for (j = i; j < ht->count - 1; j++)
>+ ht->list[j] = ht->list[j+1];
>+ ht->list[j] = NULL;
>+ break;
>+ }
>+ }
> *hep = (*hep)->next;
> --ht->count;
> }
>@@ -362,6 +380,7 @@
> res->count = base->count;
> res->max = (overlay->max > base->max) ? overlay->max : base->max;
> res->array = alloc_array(res, res->max);
>+ res->list = alloc_array(res, res->max);
> new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * res->count);
> j = 0;
> for (hi = apr_hash_first(NULL, (apr_hash_t*)base); hi; hi =
>apr_hash_next(hi)) {
>@@ -373,6 +392,7 @@
> new_vals[j].hash = hi->this->hash;
> new_vals[j].next = res->array[i];
> res->array[i] = &new_vals[j];
>+ res->list[j] = res->array[i];
> j++;
> }
>
>
--
Brane Čibej <br...@xbc.nu> http://www.xbc.nu/brane/
Re: [PATCH] apr_hash.c -- Make table ordered
Posted by Branko Čibej <br...@xbc.nu>.
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.
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. But it makes no
sense to do this / within/ the hash table implementation.
>
>
>
>MT.
>
>cvs server: Diffing .
>Index: apr_hash.c
>===================================================================
>RCS file: /home/cvspublic/apr/tables/apr_hash.c,v
>retrieving revision 1.25
>diff -u -r1.25 apr_hash.c
>--- apr_hash.c 2001/09/06 06:34:59 1.25
>+++ apr_hash.c 2001/10/10 18:40:55
>@@ -114,7 +114,8 @@
> apr_pool_t *pool;
> apr_hash_entry_t **array;
> apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
>- int count, max;
>+ apr_hash_entry_t **list;
>+ int count, max;
> };
> #define INITIAL_MAX 15 /* tunable == 2^n - 1 */
>
>@@ -136,6 +137,7 @@
> ht->count = 0;
> ht->max = INITIAL_MAX;
> ht->array = alloc_array(ht, ht->max);
>+ ht->list = alloc_array(ht, ht->max);
> return ht;
> }
>
>@@ -146,13 +148,14 @@
>
> APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)
> {
>- hi->this = hi->next;
>- while (!hi->this) {
>+
> if (hi->index > hi->ht->max)
> return NULL;
>- hi->this = hi->ht->array[hi->index++];
>- }
>+ hi->this = hi->ht->list[hi->index++];
>+ if (!hi->this)
>+ return NULL;
> hi->next = hi->this->next;
>+
> return hi;
> }
>
>@@ -189,18 +192,23 @@
> {
> apr_hash_index_t *hi;
> apr_hash_entry_t **new_array;
>+ apr_hash_entry_t **new_list;
> int new_max;
>- int i;
>+ int i, j;
>
> new_max = ht->max * 2 + 1;
> new_array = alloc_array(ht, new_max);
>+ new_list = alloc_array(ht, new_max);
>+ j = 0;
> for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {
> i = hi->this->hash & new_max;
> hi->this->next = new_array[i];
> new_array[i] = hi->this;
>+ new_list[j++] = new_array[i];
> }
> ht->array = new_array;
> ht->max = new_max;
>+ ht->list = new_list;
> }
>
> /*
>@@ -285,6 +293,7 @@
> he->klen = klen;
> he->val = val;
> *hep = he;
>+ ht->list[ht->count] = he;
> ht->count++;
> return hep;
> }
>@@ -307,10 +316,19 @@
> const void *val)
> {
> apr_hash_entry_t **hep;
>+ int i, j;
> hep = find_entry(ht, key, klen, val);
> if (*hep) {
> if (!val) {
>- /* delete entry */
>+ /* delete entry */
>+ for (i = 0; i < ht->count; i++) {
>+ if (ht->list[i] == *hep) {
>+ for (j = i; j < ht->count - 1; j++)
>+ ht->list[j] = ht->list[j+1];
>+ ht->list[j] = NULL;
>+ break;
>+ }
>+ }
> *hep = (*hep)->next;
> --ht->count;
> }
>@@ -362,6 +380,7 @@
> res->count = base->count;
> res->max = (overlay->max > base->max) ? overlay->max : base->max;
> res->array = alloc_array(res, res->max);
>+ res->list = alloc_array(res, res->max);
> new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * res->count);
> j = 0;
> for (hi = apr_hash_first(NULL, (apr_hash_t*)base); hi; hi =
>apr_hash_next(hi)) {
>@@ -373,6 +392,7 @@
> new_vals[j].hash = hi->this->hash;
> new_vals[j].next = res->array[i];
> res->array[i] = &new_vals[j];
>+ res->list[j] = res->array[i];
> j++;
> }
>
>
--
Brane Čibej <br...@xbc.nu> http://www.xbc.nu/brane/