apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ian Holsman <i...@cnet.com>
Subject Re: [Patch] Add apr_hash_overlay
Date Tue, 17 Jul 2001 14:34:24 GMT
any comments on this  patch?

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
>
>




Mime
View raw message