Mailing-List: contact cvs-help@apr.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@apr.apache.org
Date: 9 Nov 2001 22:59:00 -0000
Message-ID: <20011109225900.622.qmail@icarus.apache.org>
From: ianh@apache.org
To: apr-cvs@apache.org
Subject: cvs commit: apr/tables apr_hash.c

ianh        01/11/09 14:59:00

  Modified:    .        CHANGES
               include  apr_hash.h
               tables   apr_hash.c
  Log:
  Add 2 new hash functions.
  apr_hash_copy & apr_hash_merge.
  the merge function allows for a callback if both hash's have the same value
  this changes the overlay function so that it calls the 'merge'
  
  Submitted by:	 Brian Pane <bpane@pacbell.net>
  Reviewed by:	Ian Holsman
  
  Revision  Changes    Path
  1.177     +4 -0      apr/CHANGES
  
  Index: CHANGES
  ===================================================================
  RCS file: /home/cvs/apr/CHANGES,v
  retrieving revision 1.176
  retrieving revision 1.177
  diff -u -r1.176 -r1.177
  --- CHANGES	2001/10/29 14:54:19	1.176
  +++ CHANGES	2001/11/09 22:59:00	1.177
  @@ -1,5 +1,9 @@
   Changes with APR b1  
   
  +  *) New functions apr_hash_[merge|copy], change to overlay fn
  +     so that it calls merge, which does a inline iteration instead
  +     of calling the iterator function. [Brian Pan <bpane@pacbell.net]
  +
     *) Introduce the apr_pool_userdata_setn() variant that doesn't 
        strdup the key.  Allows both the _setn() and _set() variant to 
        accept NULL for the cleanup.  [Brian Pane <bpane@pacbell.net]
  
  
  
  1.32      +34 -0     apr/include/apr_hash.h
  
  Index: apr_hash.h
  ===================================================================
  RCS file: /home/cvs/apr/include/apr_hash.h,v
  retrieving revision 1.31
  retrieving revision 1.32
  diff -u -r1.31 -r1.32
  --- apr_hash.h	2001/11/09 17:50:48	1.31
  +++ apr_hash.h	2001/11/09 22:59:00	1.32
  @@ -105,6 +105,16 @@
   APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool);
   
   /**
  + * Make a copy of a hash table
  + * @param pool The pool from which to allocate the new hash table
  + * @param h The hash table to clone
  + * @return The hash table just created
  + * @remark Makes a shallow copy
  + */
  +APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
  +                                        const apr_hash_t *h);
  +
  +/**
    * Associate a value with a key in a hash table.
    * @param ht The hash table
    * @param key Pointer to the key
  @@ -192,6 +202,30 @@
   APR_DECLARE(apr_hash_t *) apr_hash_overlay(apr_pool_t *p,
                                              const apr_hash_t *overlay, 
                                              const apr_hash_t *base);
  +
  +/**
  + * Merge two hash tables into one new hash table. If the same key
  + * is present in both tables, call the supplied merge function to
  + * produce a merged value for the key in the new table.
  + * @param p The pool to use for the new hash table
  + * @param h1 The first of the tables to merge
  + * @param h2 The second of the tables to merge
  + * @param merger A callback function to merge values, or NULL to
  + *  make values from h1 override values from h2 (same semantics as
  + *  apr_hash_overlay())
  + * @param data Client data to pass to the merger function
  + * @return A new hash table containing all of the data from the two passed in
  + */
  +APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
  +                                         const apr_hash_t *h1,
  +                                         const apr_hash_t *h2,
  +                                         void * (*merger)(apr_pool_t *p,
  +                                                     const void *key,
  +                                                     apr_ssize_t klen,
  +                                                     const void *h1_val,
  +                                                     const void *h2_val,
  +                                                     const void *data),
  +                                         const void *data);
   
   /**
    * Get a pointer to the pool which the hash table 
  
  
  
  1.26      +97 -19    apr/tables/apr_hash.c
  
  Index: apr_hash.c
  ===================================================================
  RCS file: /home/cvs/apr/tables/apr_hash.c,v
  retrieving revision 1.25
  retrieving revision 1.26
  diff -u -r1.25 -r1.26
  --- apr_hash.c	2001/09/06 06:34:59	1.25
  +++ apr_hash.c	2001/11/09 22:59:00	1.26
  @@ -289,6 +289,41 @@
       return hep;
   }
   
  +APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
  +                                        const apr_hash_t *orig)
  +{
  +    apr_hash_t *ht;
  +    apr_hash_entry_t *new_vals;
  +    int i, j;
  +
  +    ht = apr_palloc(pool, sizeof(apr_hash_t) +
  +                    sizeof(*ht->array) * (orig->max + 1) +
  +                    sizeof(apr_hash_entry_t) * orig->count);
  +    ht->pool = pool;
  +    ht->count = orig->count;
  +    ht->max = orig->max;
  +    ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
  +
  +    new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
  +                                    sizeof(*ht->array) * (orig->max + 1));
  +    j = 0;
  +    for (i = 0; i <= ht->max; i++) {
  +        apr_hash_entry_t **new_entry = &(ht->array[i]);
  +        apr_hash_entry_t *orig_entry = orig->array[i];
  +        while (orig_entry) {
  +            *new_entry = &new_vals[j++];
  +            (*new_entry)->hash = orig_entry->hash;
  +            (*new_entry)->key = orig_entry->key;
  +            (*new_entry)->klen = orig_entry->klen;
  +            (*new_entry)->val = orig_entry->val;
  +            new_entry = &((*new_entry)->next);
  +            orig_entry = orig_entry->next;
  +        }
  +        *new_entry = NULL;
  +    }
  +    return ht;
  +}
  +
   APR_DECLARE(void *) apr_hash_get(apr_hash_t *ht,
   			       const void *key,
   			       apr_ssize_t klen)
  @@ -335,10 +370,25 @@
                                             const apr_hash_t *overlay, 
                                             const apr_hash_t *base)
   {
  +    return apr_hash_merge(p, overlay, base, NULL, NULL);
  +}
  +
  +APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
  +                                         const apr_hash_t *overlay, 
  +                                         const apr_hash_t *base,
  +                                         void * (*merger)(apr_pool_t *p,
  +                                                     const void *key,
  +                                                     apr_ssize_t klen,
  +                                                     const void *h1_val,
  +                                                     const void *h2_val,
  +                                                     const void *data),
  +                                         const void *data)
  +{
       apr_hash_t *res;
  -    apr_hash_index_t *hi;
       apr_hash_entry_t *new_vals;
  -    int i,j;
  +    apr_hash_entry_t *iter;
  +    apr_hash_entry_t *ent;
  +    int i,j,k;
   
   #ifdef POOL_DEBUG
       /* we don't copy keys and values, so it's necessary that
  @@ -361,27 +411,55 @@
       res->pool = p;
       res->count = base->count;
       res->max = (overlay->max > base->max) ? overlay->max : base->max;
  +    if (base->count + overlay->count > res->max) {
  +        res->max = res->max * 2 + 1;
  +    }
       res->array = alloc_array(res, res->max);
  -    new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * res->count);
  +    if (base->count + overlay->count) {
  +        new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *
  +                              (base->count + overlay->count));
  +    }
       j = 0;
  -    for (hi = apr_hash_first(NULL, (apr_hash_t*)base); 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++;
  +    for (k = 0; k <= base->max; k++) {
  +        for (iter = base->array[k]; iter; iter = iter->next) {
  +            i = iter->hash & res->max;
  +            new_vals[j].klen = iter->klen;
  +            new_vals[j].key = iter->key;
  +            new_vals[j].val = iter->val;
  +            new_vals[j].hash = iter->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(NULL, (apr_hash_t*)overlay); hi; 
  -         hi = apr_hash_next(hi)) {
  -        apr_hash_set(res, hi->this->key, hi->this->klen, hi->this->val);
  +    for (k = 0; k < overlay->max; k++) {
  +        for (iter = overlay->array[k]; iter; iter = iter->next) {
  +            i = iter->hash & res->max;
  +            for (ent = res->array[i]; ent; ent = ent->next) {
  +                if ((ent->klen == iter->klen) &&
  +                    (memcmp(ent->key, iter->key, iter->klen) == 0)) {
  +                    if (merger) {
  +                        ent->val = (*merger)(p, iter->key, iter->klen,
  +                                             iter->val, ent->val, data);
  +                    }
  +                    else {
  +                        ent->val = iter->val;
  +                    }
  +                    break;
  +                }
  +            }
  +            if (!ent) {
  +                new_vals[j].klen = iter->klen;
  +                new_vals[j].key = iter->key;
  +                new_vals[j].val = iter->val;
  +                new_vals[j].hash = iter->hash;
  +                new_vals[j].next = res->array[i];
  +                res->array[i] = &new_vals[j];
  +                res->count++;
  +                j++;
  +            }
  +        }
       }
       return res;
   }