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 <[EMAIL PROTECTED]> http://www.xbc.nu/brane/
