apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Branko ─îibej <br...@xbc.nu>
Subject Re: [PATCH] apr_hash.c -- Make table ordered
Date Wed, 10 Oct 2001 20:10:07 GMT
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   <brane@xbc.nu>            http://www.xbc.nu/brane/




Mime
View raw message