apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mladen Turk" <mt...@mappingsoft.com>
Subject [PATCH] apr_hash.c -- Make table ordered
Date Wed, 10 Oct 2001 19:02:21 GMT
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++;
     }



Mime
View raw message