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 <[EMAIL PROTECTED]>
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 <[EMAIL PROTECTED]
+
*) 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 <[EMAIL PROTECTED]
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;
}
