Re: [Patch] Add apr_hash_overlay

Brian Pane 17 Jul 2001 17:33:27 -0000

Ian Holsman wrote:

any comments on this patch?


I just read through it, and I have one major and one minor
issue:

1. Is it just my imagination, or is the overlay logic backwards?
  It looks like you're making a copy of "overlay" and then
  writing elements from "base" on top of it.  Shouldn't it be
  the opposite?

2. IMHO, the function
    APR_DECLARE(apr_hash_index_t *) apr_hash_first(const apr_hash_t *ht);
  is misleading to the caller.  The "ht" argument is declared const,
  but the function returns a non-const iterator that can be used to
  alter the contents of ht.  If ht is going to be const, the result
  value should be const too.

--Brian

I'd really like it in there so I can submit a bigger patch which would convert the 'notes' table to a hash table.
Ian Holsman wrote:
This is the first part of allow notes 'tables' to become hash tables. the patch adds a function to 'merge' two hash tables together, a test program for hash tables, and a small fix to apr_hash_first (make the arg a const)

(I've attached the testhash.c, but am currently on Windows, so I didnt change the makefile.in file for this. ) ..Ian
Index: apr_hash.h
===================================================================
RCS file: /home/cvspublic/apr/include/apr_hash.h,v
retrieving revision 1.25
diff -u -r1.25 apr_hash.h
--- apr_hash.h  2001/05/16 05:30:51     1.25
+++ apr_hash.h  2001/07/16 02:28:43
@@ -150,7 +150,7 @@
 * </PRE>
 * @deffunc apr_hash_index_t *apr_hash_first(apr_hash_t *ht)
 */
-APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_hash_t *ht);
+APR_DECLARE(apr_hash_index_t *) apr_hash_first(const apr_hash_t *ht);
/**
 * Continue iterating over the entries in a hash table.
@@ -179,8 +179,20 @@
 * @return The number of key/value pairs in the hash table.
 * @deffunc int apr_hash_count(apr_hash_t *ht);
 */
-APR_DECLARE(int) apr_hash_count(apr_hash_t *ht);
+APR_DECLARE(int) apr_hash_count(const apr_hash_t *ht);
+/** + * Merge two hash tables into one new hash table. The values of the 'base' tabl e + * override the values of the overlay if both have the same key. + * @param p The pool to use for the new hash table + * @param overlay The first table to put in the new hash table + * @param base The table to add at the end of the new hash table + * @return A new hash table containing all of the data from the two passed in + * @deffunc apr_hash_t *apr_hash_overlay(apr_pool_t *p, const apr_table_t *over lay, const apr_table_t *base); + */ +APR_DECLARE(apr_hash_t *) apr_hash_overlay(apr_pool_t *p, + const apr_hash_t *overlay, + const apr_hash_t *base);
#ifdef __cplusplus
}
Index: apr_hash.c
===================================================================
RCS file: /home/cvspublic/apr/tables/apr_hash.c,v
retrieving revision 1.19
diff -u -r1.19 apr_hash.c
--- apr_hash.c    2001/05/16 05:30:52    1.19
+++ apr_hash.c    2001/07/16 02:19:26
@@ -112,7 +112,7 @@
 * apr_hash_next().
 */
struct apr_hash_index_t {
-    apr_hash_t           *ht;
+    const apr_hash_t           *ht;
    apr_hash_entry_t   *this, *next;
    int                 index;
};
@@ -155,7 +155,7 @@
    return hi;
}
-APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_hash_t *ht)
+APR_DECLARE(apr_hash_index_t *) apr_hash_first(const apr_hash_t *ht)
{
    apr_hash_index_t *hi;
    hi = apr_palloc(ht->pool, sizeof(*hi));
@@ -321,7 +321,67 @@
    /* else key not present and val==NULL */
}
-APR_DECLARE(int) apr_hash_count(apr_hash_t *ht) +APR_DECLARE(int) apr_hash_count(const apr_hash_t *ht) { return ht->count; +} + +APR_DECLARE(apr_hash_t*) apr_hash_overlay(apr_pool_t*p, const apr_hash_t *overlay, const apr_hash_t*base) +{ + apr_hash_t *res; + apr_hash_index_t *hi; + apr_hash_entry_t *new_vals; + int i,j; + +#ifdef POOL_DEBUG + /* we don't copy keys and values, so it's necessary that + * overlay->a.pool and base->a.pool have a life span at least + * as long as p + */ + if (!apr_pool_is_ancestor(overlay->a.pool, p)) { + fprintf(stderr, "apr_hash_overlay: overlay's pool is not an ancestor of p\n"); + abort(); + } + if (!apr_pool_is_ancestor(base->a.pool, p)) { + fprintf(stderr, "apr_hash_overlay: base's pool is not an ancestor of p\n"); + abort(); + } +#endif + + res = apr_palloc(p, sizeof(apr_hash_t)); + res->pool = p; + res->count=overlay->count; + res->max= (overlay->max > base->max)? overlay->max: base->max; + res->array = alloc_array(res, res->max); + new_vals = apr_palloc(p, sizeof( apr_hash_entry_t)*res->count); + j=0; + for (hi = apr_hash_first(overlay); hi; hi = apr_hash_next(hi)) { + i = hi->this->hash & res->max; + + new_vals[j].klen = hi->this->klen; + new_vals[j].key = hi->this->key; + new_vals[j].val = hi->this->val; + new_vals[j].hash = hi->this->hash; + new_vals[j].next = res->array[i]; + res->array[i] = &new_vals[j]; + j++; + } + /* can't simply copy the stuff over, need to set each one so as to + increment the counts/array properly + */ + for (hi = apr_hash_first(base); hi; hi = apr_hash_next(hi)) { + apr_hash_set(res,hi->this->key,hi->this->klen, hi->this->val); + } + return res; }
------------------------------------------------------------------------
/*
*/
#include "apr.h"
#include "apr_strings.h"
#include "apr_general.h"
#include "apr_pools.h"
#include "apr_hash.h"
#if APR_HAVE_STDIO_H
#include <stdio.h>
#endif
#if APR_HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if APR_HAVE_STRING_H
#include <string.h>
#endif
static void dump_hash( const apr_hash_t *h) {
    apr_hash_index_t *hi;
    char* val;
    char* key;
    int len;
    int i=0;
for (hi = apr_hash_first(h); hi; hi = apr_hash_next(hi)) { apr_hash_this(hi,(void*) &key, &len,(void*) &val); fprintf(stdout, "Key %s (%d) Value %s\n",key,len,val); i++; } if ( i != apr_hash_count(h)) { fprintf(stderr, "ERROR: #entries (%d) does not match count (%d)\n",i,apr_hash_count(h)); } else { fprintf( stdout, "#entries %d \n",i); }
}
static void sum_hash( const apr_hash_t *h, int*pcount,int*keySum, int*valSum) { apr_hash_index_t *hi; void*val; void*key; int count=0;
    *keySum=0;
    *valSum=0;
    *pcount=0;
    for (hi = apr_hash_first(h); hi; hi = apr_hash_next(hi)) {
        apr_hash_this(hi, &key, NULL, &val);
        *valSum += *(int *)val;
        *keySum += *(int *)key;
        count++;
    }
    *pcount=count;
}
int main(int argc, const char *const argv[])
{
    apr_pool_t*cntxt;
    apr_hash_t *h;
    apr_hash_t *h2;
    apr_hash_t *h3;
    apr_hash_t *h4;
    int i;
    int j;
    int *val;
    int *key;
    char*result;
    int sumKeys,sumVal;
    int trySumKey,trySumVal;
   /* table defaults  */
   apr_initialize();
   atexit(apr_terminate);
   apr_pool_create(&cntxt, NULL);
    h =apr_hash_make(cntxt);
   if ( h == NULL )  {
       fprintf(stderr, "ERROR: can not allocate HASH!\n");
       exit(-1);
   }
apr_hash_set(h,"OVERWRITE",APR_HASH_KEY_STRING, "should not see this"); apr_hash_set(h,"FOO3",APR_HASH_KEY_STRING, "bar3"); apr_hash_set(h,"FOO3",APR_HASH_KEY_STRING, "bar3"); apr_hash_set(h,"FOO1",APR_HASH_KEY_STRING, "bar1"); apr_hash_set(h,"FOO2",APR_HASH_KEY_STRING, "bar2"); apr_hash_set(h,"FOO4",APR_HASH_KEY_STRING, "bar4"); apr_hash_set(h,"SAME1",APR_HASH_KEY_STRING, "same"); apr_hash_set(h,"SAME2",APR_HASH_KEY_STRING, "same"); apr_hash_set(h,"OVERWRITE",APR_HASH_KEY_STRING, "Overwrite key");

result=apr_hash_get(h,"FOO2", APR_HASH_KEY_STRING); if (strcmp(result,"bar2")) fprintf(stderr,"ERROR:apr_hash_get FOO2 = %s (should be bar2)\n",result);

result= apr_hash_get(h,"SAME2", APR_HASH_KEY_STRING); if (strcmp(result,"same")) fprintf(stderr,"ERROR:apr_hash_get SAME2 = %s (should be same)\n",result);

result=apr_hash_get(h,"OVERWRITE", APR_HASH_KEY_STRING); if ( strcmp(result,"Overwrite key")) fprintf(stderr,"ERROR:apr_hash_get OVERWRITE = %s (should be 'Overwrite key')\n",result);

result=apr_hash_get(h,"NOTTHERE", APR_HASH_KEY_STRING); if (result) fprintf(stderr,"ERROR:apr_hash_get NOTTHERE = %s (should be NULL)\n",result); result=apr_hash_get(h,"FOO3", APR_HASH_KEY_STRING); if ( strcmp(result,"bar3")) fprintf(stderr,"ERROR:apr_hash_get FOO3 = %s (should be bar3)\n",result);
    dump_hash(h);
    h2 =apr_hash_make(cntxt);
    if ( h2 == NULL )  {
        fprintf(stderr, "ERROR: can not allocate HASH!\n");
        exit(-1);
    }
    sumKeys=0;
    sumVal=0;
    trySumKey=0;
    trySumVal=0;
    for (i=0;i<100;i++) {
        j=i*10+1;
        sumKeys+=j;
        sumVal+=i;
        key=apr_palloc(cntxt,sizeof(int));
        *key=j;
        val = apr_palloc(cntxt,sizeof(int));
        *val=i;
        apr_hash_set(h2,key,sizeof(int), val);
    }
sum_hash( h2, &i, &trySumKey,&trySumVal ); if (i==100) { fprintf(stdout,"All keys accounted for\n"); } else { fprintf(stderr,"ERROR: Only got %d (out of 100)\n",i); } if ( trySumVal != sumVal ) { fprintf(stderr,"ERROR:Values don't add up Got %d expected %d\n",trySumVal ,sumVal); } if ( trySumKey != sumKeys ) { fprintf(stderr,"ERROR:Keys don't add up Got %d expected %d\n",trySumKey,sumKeys); }

j=891; apr_hash_set(h2, &j,sizeof(int),NULL); if (apr_hash_get(h2,&j,sizeof(int))) { fprintf(stderr,"ERRROR: Delete not working\n"); } else { fprintf(stdout,"Delete working\n"); } sum_hash( h2, &i, &trySumKey,&trySumVal );
    sumKeys -=891;
    sumVal -=89;
if ( i==99) { fprintf(stdout,"All keys accounted for.. Delete OK\n"); } else { fprintf(stderr,"Only got %d (out of 99) Delete Not OK\n",i); } if ( trySumVal != sumVal ) { fprintf(stderr,"ERROR:Values don't add up Got %d expected %d\n",trySumVal ,sumVal); } if ( trySumKey != sumKeys ) { fprintf(stderr,"ERROR:Keys don't add up Got %d expected %d\n",trySumKey,sumKeys); }

/* test overlay */ h3 = apr_hash_make(cntxt); /* test with blank hash tables */ h4 = apr_hash_overlay(cntxt, h3,h); if ( apr_hash_count(h4) != apr_hash_count(h)) { fprintf(stderr,"ERROR: overlay not working with blank overlay as overlay\n"); dump_hash(h4); }

h4 = apr_hash_overlay(cntxt, h,h3); if ( apr_hash_count(h4) != apr_hash_count(h)) { fprintf(stderr,"ERROR: overlay not working with blank overlay as base\n"); dump_hash(h4); }

h4 = apr_hash_overlay(cntxt, h,h2); if ( apr_hash_count(h4) != ( apr_hash_count(h) + apr_hash_count(h2)) ) fprintf(stderr,"ERROR: overlay not working when overlaying 2 unique hashs\n");

h4 = apr_hash_overlay(cntxt, h,h); if ( apr_hash_count(h4) != apr_hash_count(h) ) { fprintf(stderr,"ERROR: overlay not working when overlaying same hash\n"); dump_hash(h4); } result=apr_hash_get(h4,"FOO2", APR_HASH_KEY_STRING); if (strcmp(result,"bar2")) fprintf(stderr,"ERROR:apr_hash_get FOO2 = %s (should be bar2)\n",result);

result= apr_hash_get(h4,"SAME2", APR_HASH_KEY_STRING); if (strcmp(result,"same")) fprintf(stderr,"ERROR:apr_hash_get SAME2 = %s (should be same)\n",result); result=apr_hash_get(h4,"OVERWRITE", APR_HASH_KEY_STRING); if ( strcmp(result,"Overwrite key")) fprintf(stderr,"ERROR:apr_hash_get OVERWRITE = %s (should be 'Overwrite key')\n",result);

result=apr_hash_get(h4,"NOTTHERE", APR_HASH_KEY_STRING); if (result) fprintf(stderr,"ERROR:apr_hash_get NOTTHERE = %s (should be NULL)\n",result); result=apr_hash_get(h4,"FOO3", APR_HASH_KEY_STRING); if ( strcmp(result,"bar3")) fprintf(stderr,"ERROR:apr_hash_get FOO3 = %s (should be bar3)\n",result);

apr_hash_set(h4, "FOO3",sizeof(int),NULL); result=apr_hash_get(h4,"FOO3", APR_HASH_KEY_STRING); if ( result ) fprintf(stderr,"ERROR:apr_hash_get FOO3 = %s (should be NULL, we just deleted it!)\n",result);
    return 0;
}
testhash.c
Content-Type:
text/plain
Content-Encoding:
7bit

Re: [Patch] Add apr_hash_overlay

Reply via email to