Return-Path: Delivered-To: apmail-httpd-dev-archive@httpd.apache.org Received: (qmail 20539 invoked by uid 500); 10 Oct 2001 20:11:21 -0000 Mailing-List: contact dev-help@httpd.apache.org; run by ezmlm Precedence: bulk Reply-To: dev@httpd.apache.org list-help: list-unsubscribe: list-post: Delivered-To: mailing list dev@httpd.apache.org Received: (qmail 20487 invoked from network); 10 Oct 2001 20:11:18 -0000 Message-ID: <3BC4AB1F.3030602@xbc.nu> Date: Wed, 10 Oct 2001 22:10:07 +0200 From: Branko =?ISO-8859-2?Q?=C8ibej?= User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.3) Gecko/20010801 X-Accept-Language: sl, en-gb, en MIME-Version: 1.0 To: Mladen Turk CC: APR Dev List , Apache Dev Subject: Re: [PATCH] apr_hash.c -- Make table ordered References: Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N 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 http://www.xbc.nu/brane/