Joe Schaefer <[EMAIL PROTECTED]> writes:
[...]
> BRIAN'S-PATCH
>
> 0000c1e8 559 1.24604 apr_table_get ...
> 0000c4f8 253 0.563952 apr_table_setn ...
> 0000ce94 203 0.452499 table_mergesort ...
> 0000c06c 187 0.416834 apr_table_make ...
> 0000cbd8 179 0.399001 apr_table_addn ...
> 0000d048 138 0.30761 apr_table_compress ...
> 0000ccec 86 0.191699 apr_table_vdo ...
> 0000c9e4 84 0.187241 apr_table_mergen ...
> 0000c160 82 0.182783 table_reindex ...
> 0000c048 71 0.158263 apr_table_elts ...
> 0000c050 62 0.138202 apr_is_empty_table ...
> 0000ccc4 57 0.127056 apr_table_do ...
> 0000c700 54 0.120369 apr_table_unset ...
>
> TOTAL: 2015 4.491549 %
I added back the callbacks apreq needs,
and moved the table_reindex call inside
the dups_found test. Here's the corresponding
oprofile data:
0000c748 561 1.25878 apr_table_get ...
0000ca54 256 0.574416 apr_table_setn ...
0000c2e4 232 0.520565 table_mergesort ...
0000d490 194 0.4353 apr_table_addn ...
0000c134 178 0.399399 apr_table_make ...
0000c4b8 117 0.262526 apr_table_compress ...
0000d0f4 116 0.260282 apr_table_mergen ...
0000d704 85 0.190724 apr_table_vdo ...
0000cc5c 66 0.148092 apr_table_unset ...
0000c0e4 63 0.14136 apr_table_elts ...
0000c0ec 59 0.132385 apr_is_empty_table ...
0000d6dc 53 0.118922 apr_table_do ...
TOTAL: 1980 4.442751 %
apr patch is attached below; the same patch Brian wrote for
httpd-2.0 applies.
Index: include/apr_tables.h
===================================================================
RCS file: /home/cvspublic/apr/include/apr_tables.h,v
retrieving revision 1.37
diff -u -r1.37 apr_tables.h
--- include/apr_tables.h 5 Mar 2003 21:22:26 -0000 1.37
+++ include/apr_tables.h 18 Jun 2003 14:50:39 -0000
@@ -224,6 +224,16 @@
const char sep);
/**
+ * Same as apr_array_pstrcat, but takes a (char *) as third argument.
+ * This allows the array elements to be joined on a string instead of
+ * a single character.
+ */
+
+APR_DECLARE(char *)apr_array_pstrjoin(apr_pool_t *p,
+ const apr_array_header_t *arr,
+ const char *sep);
+
+/**
* Make a new table
* @param p The pool to allocate the pool out of
* @param nelts The number of elements in the initial table.
@@ -242,6 +252,31 @@
const apr_table_t *t);
/**
+ * Get/set method for the table's value copier.
+ * @param t Table.
+ * @param c The new t->copy callback. c = NULL is ignored;
+ * a non-NULL value replaces the table's internal copier.
+ * @return The original t->copy callback (prior to any assignment).
+ */
+typedef char *(apr_table_copier_t)(apr_pool_t *p, const char *val);
+
+APR_DECLARE(apr_table_copier_t *) apr_table_copier(apr_table_t *t,
+ apr_table_copier_t *c);
+
+/**
+ * Get/set method for the table's merger callback.
+ * @param t Table.
+ * @param m The new t->merge callback. m = NULL is ignored;
+ * a non-NULL value replaces the table's internal merger.
+ * @return The original t->merge callback (prior to any assignment).
+ */
+typedef char *(apr_table_merger_t)(apr_pool_t *p,
+ const apr_array_header_t *a);
+
+APR_DECLARE(apr_table_merger_t *) apr_table_merger(apr_table_t *t,
+ apr_table_merger_t *m);
+
+/**
* Delete all of the elements from a table
* @param t The table to clear
*/
@@ -334,6 +369,27 @@
*/
APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
const char *val);
+
+/**
+ * Eliminates redunandant entries with the apr_table_merger_t
+ * callback associated to t. Use apr_table_merger() to access
+ * and alter this callback.
+ *
+ * @param t Table.
+ * @param flags ::APR_OVERLAP_TABLES_MERGE or ::APR_OVERLAP_TABLES_SET
+ * see apr_overlap_tables for details on this parameter.
+ */
+APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned int flags);
+
+/**
+ * Append one table to the end of another.
+ * @param t The table to be modified.
+ * @param s The entries from this table are added to "t".
+ * @remark This function overlays the internal indices from "s"
+ * onto "t", so it shoul be faster than iterating over s with apr_table_addn.
+ * In any case, the result should be identical.
+ */
+APR_DECLARE(void) apr_table_cat(apr_table_t *t, const apr_table_t *s);
/**
* Merge two tables into one new table
Index: tables/apr_tables.c
===================================================================
RCS file: /home/cvspublic/apr/tables/apr_tables.c,v
retrieving revision 1.47
diff -u -r1.47 apr_tables.c
--- tables/apr_tables.c 4 Apr 2003 12:05:53 -0000 1.47
+++ tables/apr_tables.c 18 Jun 2003 14:50:40 -0000
@@ -249,6 +249,40 @@
return res;
}
+APR_DECLARE(char *)apr_array_pstrjoin(apr_pool_t *p,
+ const apr_array_header_t *arr,
+ const char *sep)
+{
+ apr_size_t len;
+ const char *src, **a = (const char **)arr->elts;
+ char *dest, *rv;
+ const int n = arr->nelts;
+ int j;
+
+ if (n == 0)
+ return apr_pcalloc(p, 1);
+
+ for (j=0, len=0; j<n; ++j)
+ if (a[j] != NULL)
+ len += strlen(a[j]);
+
+ rv = apr_palloc(p, len + 1 + strlen(sep)*(n-1));
+
+ /* ~ strcpy: this leaves "dest" & "src" pointing at nul-characters */
+ for (dest = rv, src = a[0]; (*dest = *src); ++src, ++dest)
+ ;
+
+ for (j=1; j<n; ++j) {
+ for (src = sep; (*dest = *src); ++src, ++dest)
+ ;
+ if (a[j] != NULL)
+ for (src = a[j]; (*dest = *src); ++src, ++dest)
+ ;
+ }
+
+ return rv;
+}
+
/* apr_array_pstrcat generates a new string from the apr_pool_t containing
* the concatenated sequence of substrings referenced as elements within
* the array. The string will be empty if all substrings are empty or null,
@@ -259,55 +293,8 @@
const apr_array_header_t *arr,
const char sep)
{
- char *cp, *res, **strpp;
- apr_size_t len;
- int i;
-
- if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */
- return (char *) apr_pcalloc(p, 1);
- }
-
- /* Pass one --- find length of required string */
-
- len = 0;
- for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
- if (strpp && *strpp != NULL) {
- len += strlen(*strpp);
- }
- if (++i >= arr->nelts) {
- break;
- }
- if (sep) {
- ++len;
- }
- }
-
- /* Allocate the required string */
-
- res = (char *) apr_palloc(p, len + 1);
- cp = res;
-
- /* Pass two --- copy the argument strings into the result space */
-
- for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
- if (strpp && *strpp != NULL) {
- len = strlen(*strpp);
- memcpy(cp, *strpp, len);
- cp += len;
- }
- if (++i >= arr->nelts) {
- break;
- }
- if (sep) {
- *cp++ = sep;
- }
- }
-
- *cp = '\0';
-
- /* Return the result string */
-
- return res;
+ char s[2] = {sep,0};
+ return apr_array_pstrjoin(p, arr, s);
}
@@ -382,9 +369,12 @@
* of index_initialized will be zero. (Check this before
* trying to use index_first[i] or index_last[i]!)
*/
+ apr_table_copier_t *copy;
+ apr_table_merger_t *merge;
apr_uint32_t index_initialized;
int index_first[TABLE_HASH_SIZE];
int index_last[TABLE_HASH_SIZE];
+
};
/*
@@ -413,6 +403,12 @@
return ((t == NULL) || (t->a.nelts == 0));
}
+static char *merge_values(apr_pool_t *p, const apr_array_header_t *a)
+{
+
+ return apr_array_pstrjoin(p, a, ", ");
+}
+
APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
{
apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
@@ -421,6 +417,8 @@
#ifdef MAKE_TABLE_PROFILE
t->creator = __builtin_return_address(0);
#endif
+ t->copy = apr_pstrdup;
+ t->merge = merge_values;
t->index_initialized = 0;
return t;
}
@@ -441,12 +439,36 @@
make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
new->a.nelts = t->a.nelts;
+ new->copy = t->copy;
+ new->merge = t->merge;
memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
new->index_initialized = t->index_initialized;
return new;
}
+APR_DECLARE(apr_table_copier_t *)apr_table_copier(apr_table_t *t,
+ apr_table_copier_t *c)
+{
+ apr_table_copier_t *original = t->copy;
+
+ if (c != NULL)
+ t->copy = c;
+ return original;
+}
+
+
+APR_DECLARE(apr_table_merger_t *)apr_table_merger(apr_table_t *t,
+ apr_table_merger_t *m)
+{
+ apr_table_merger_t *original = t->merge;
+
+ if (m != NULL)
+ t->merge = m;
+ return original;
+}
+
+
static void table_reindex(apr_table_t *t)
{
int i;
@@ -464,6 +486,194 @@
}
}
+static void table_mergesort(apr_pool_t *pool,
+ apr_table_entry_t **values,
+ int n)
+{
+ /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
+ * in C," chapter 8
+ */
+ apr_table_entry_t **values_tmp = apr_palloc(pool, n * sizeof *values_tmp);
+ int i;
+ int blocksize;
+
+ /* First pass: sort pairs of elements (blocksize=1) */
+ for (i = 0; i + 1 < n; i += 2) {
+ if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
+ apr_table_entry_t *swap = values[i];
+ values[i] = values[i + 1];
+ values[i + 1] = swap;
+ }
+ }
+ /* Merge successively larger blocks */
+ blocksize = 2;
+ while (blocksize < n) {
+ apr_table_entry_t **dst = values_tmp;
+ int next_start;
+ apr_table_entry_t **swap;
+
+ /* Merge consecutive pairs blocks of the next blocksize.
+ * Within a block, elements are in sorted order due to
+ * the previous iteration.
+ */
+ for (next_start = 0; next_start + blocksize < n;
+ next_start += (blocksize + blocksize)) {
+ int block1_start = next_start;
+ int block2_start = block1_start + blocksize;
+ int block1_end = block2_start;
+ int block2_end = block2_start + blocksize;
+ if (block2_end > n) {
+ /* The last block may be smaller than blocksize */
+ block2_end = n;
+ }
+
+ for (;;) {
+
+ /* Merge the next two blocks:
+ * Pick the smaller of the next element from
+ * block 1 and the next element from block 2.
+ * Once either of the blocks is emptied, copy
+ * over all the remaining elements from the
+ * other block
+ */
+ if (block1_start == block1_end) {
+ for (; block2_start < block2_end; block2_start++) {
+ *dst++ = values[block2_start];
+ }
+ break;
+ }
+ else if (block2_start == block2_end) {
+ for (; block1_start < block1_end; block1_start++) {
+ *dst++ = values[block1_start];
+ }
+
+ break;
+ }
+ if (strcasecmp(values[block1_start]->key,
+ values[block2_start]->key) > 0) {
+ *dst++ = values[block2_start++];
+ }
+ else {
+ *dst++ = values[block1_start++];
+ }
+ }
+ }
+ /* If n is not a multiple of 2*blocksize, some elements
+ * will be left over at the end of the array.
+ */
+ for (i = dst - values_tmp; i < n; i++) {
+ values_tmp[i] = values[i];
+ }
+
+ /* The output array of this pass becomes the input
+ * array of the next pass, and vice versa
+ */
+ swap = values_tmp;
+ values_tmp = values;
+ values = swap;
+
+ blocksize += blocksize;
+ }
+}
+
+#define DEFAULT_NELTS 8
+
+APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
+{
+
+ apr_table_entry_t **sort_array;
+ apr_table_entry_t **sort_next;
+ apr_table_entry_t **sort_end;
+ apr_table_entry_t *table_next;
+ apr_table_entry_t **last;
+ int i;
+ int dups_found;
+ char *a[DEFAULT_NELTS];
+ apr_array_header_t arr = {t->a.pool, sizeof(char *), 0,
+ DEFAULT_NELTS, (char *)a};
+
+ if (t->a.nelts <= 1) {
+ return;
+ }
+
+ /* Copy pointers to all the table elements into an
+ * array and sort to allow for easy detection of
+ * duplicate keys
+ */
+ sort_array = (apr_table_entry_t **)
+ apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
+ sort_next = sort_array;
+ table_next = (apr_table_entry_t *)t->a.elts;
+ i = t->a.nelts;
+ do {
+ *sort_next++ = table_next++;
+ } while (--i);
+
+ /* Note: the merge is done with mergesort instead of quicksort
+ * because mergesort is a stable sort and runs in n*log(n)
+ * time regardless of its inputs (quicksort is quadratic in
+ * the worst case)
+ */
+ table_mergesort(t->a.pool, sort_array, t->a.nelts);
+
+ /* Process any duplicate keys */
+ dups_found = 0;
+ sort_next = sort_array;
+ sort_end = sort_array + t->a.nelts;
+ last = sort_next;
+ while (++sort_next < sort_end) {
+ if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
+ !strcasecmp((*sort_next)->key, (*last)->key)) {
+
+ apr_table_entry_t **dup_last = sort_next + 1;
+
+ dups_found = 1;
+ while ((dup_last < sort_end) &&
+ ((*dup_last)->key_checksum == (*last)->key_checksum) &&
+ !strcasecmp((*dup_last)->key, (*last)->key)) {
+ dup_last++;
+ }
+ dup_last--;
+ /* Elements from last through dup_last, inclusive,
+ * all have the same key
+ */
+ if (flags == APR_OVERLAP_TABLES_MERGE) {
+ apr_table_entry_t **next = last;
+ arr.nelts = 0;
+ do {
+ *(char **)apr_array_push(&arr) = (*next)->val;
+ } while (++next <= dup_last);
+
+ (*last)->val = t->merge(t->a.pool, &arr);
+ }
+ else { /* overwrite */
+ (*last)->val = (*dup_last)->val;
+ }
+ do {
+ (*sort_next)->key = NULL;
+ } while (++sort_next <= dup_last);
+ }
+
+ last = sort_next;
+ }
+
+ /* Shift elements to the left to fill holes left by removing duplicates */
+ if (dups_found) {
+ apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
+ apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
+ apr_table_entry_t *last_elt = src + t->a.nelts;
+ do {
+ if (src->key) {
+ *dst++ = *src;
+ }
+ } while (++src < last_elt);
+ t->a.nelts -= (last_elt - dst);
+
+ table_reindex(t);
+ }
+}
+
+
APR_DECLARE(void) apr_table_clear(apr_table_t *t)
{
t->a.nelts = 0;
@@ -528,7 +738,7 @@
int must_reindex = 0;
apr_table_entry_t *dst_elt = NULL;
- next_elt->val = apr_pstrdup(t->a.pool, val);
+ next_elt->val = t->copy(t->a.pool, val);
/* Remove any other instances of this key */
for (next_elt++; next_elt <= end_elt; next_elt++) {
@@ -567,7 +777,7 @@
t->index_last[hash] = t->a.nelts;
next_elt = (apr_table_entry_t *) table_push(t);
next_elt->key = apr_pstrdup(t->a.pool, key);
- next_elt->val = apr_pstrdup(t->a.pool, val);
+ next_elt->val = t->copy(t->a.pool, val);
next_elt->key_checksum = checksum;
}
@@ -702,8 +912,12 @@
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
+ apr_table_entry_t *table_end;
apr_uint32_t checksum;
int hash;
+ int a[DEFAULT_NELTS];
+ apr_array_header_t arr = { t->a.pool, sizeof(int), 0,
+ DEFAULT_NELTS, (char *)a };
COMPUTE_KEY_CHECKSUM(key, checksum);
hash = TABLE_HASH(key);
@@ -714,14 +928,52 @@
}
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
+ table_end = ((apr_table_entry_t *) t->a.elts) + t->a.nelts;
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
+ int must_reindex = 0;
+ apr_table_entry_t *dst_elt = NULL;
+ apr_table_entry_t *match_elt = next_elt;
+
+ *(char **)apr_array_push(&arr) = next_elt->val;
+
+ /* Remove any other instances of this key */
+ for (next_elt++; next_elt <= end_elt; next_elt++) {
+ if ((checksum == next_elt->key_checksum) &&
+ !strcasecmp(next_elt->key, key)) {
+ t->a.nelts--;
+ *(const char **)apr_array_push(&arr) = next_elt->val;
+ if (!dst_elt) {
+ dst_elt = next_elt;
+ }
+ }
+ else if (dst_elt) {
+ *dst_elt++ = *next_elt;
+ must_reindex = 1;
+ }
+ }
+
+
+ /* If we've removed anything, shift over the remainder
+ * of the table (note that the previous loop didn't
+ * run to the end of the table, just to the last match
+ * for the index)
+ */
+ if (dst_elt) {
+ for (; next_elt < table_end; next_elt++) {
+ *dst_elt++ = *next_elt;
+ }
+ must_reindex = 1;
+ }
+ if (must_reindex) {
+ table_reindex(t);
+ }
/* Found an existing entry with the same key, so merge with it */
- next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
- val, NULL);
+ *(const char **)apr_array_push(&arr) = t->copy(t->a.pool, val);
+ match_elt->val = t->merge(t->a.pool, &arr);
return;
}
}
@@ -730,7 +982,7 @@
t->index_last[hash] = t->a.nelts;
next_elt = (apr_table_entry_t *) table_push(t);
next_elt->key = apr_pstrdup(t->a.pool, key);
- next_elt->val = apr_pstrdup(t->a.pool, val);
+ next_elt->val = t->copy(t->a.pool, val);
next_elt->key_checksum = checksum;
}
@@ -739,8 +991,12 @@
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
+ apr_table_entry_t *table_end;
apr_uint32_t checksum;
int hash;
+ int a[DEFAULT_NELTS];
+ apr_array_header_t arr = { t->a.pool, sizeof(int), 0,
+ DEFAULT_NELTS, (char *)a };
#ifdef POOL_DEBUG
{
@@ -764,14 +1020,51 @@
}
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
-
+ table_end = ((apr_table_entry_t *) t->a.elts) + t->a.nelts;
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
+ int must_reindex = 0;
+ apr_table_entry_t *dst_elt = NULL;
+ apr_table_entry_t *match_elt = next_elt;
+
+ *(const char **)apr_array_push(&arr) = next_elt->val;
+
+ /* Remove any other instances of this key */
+ for (next_elt++; next_elt <= end_elt; next_elt++) {
+ if ((checksum == next_elt->key_checksum) &&
+ !strcasecmp(next_elt->key, key)) {
+ t->a.nelts--;
+ *(const char **)apr_array_push(&arr) = next_elt->val;
+ if (!dst_elt) {
+ dst_elt = next_elt;
+ }
+ }
+ else if (dst_elt) {
+ *dst_elt++ = *next_elt;
+ must_reindex = 1;
+ }
+ }
+
+
+ /* If we've removed anything, shift over the remainder
+ * of the table (note that the previous loop didn't
+ * run to the end of the table, just to the last match
+ * for the index)
+ */
+ if (dst_elt) {
+ for (; next_elt < table_end; next_elt++) {
+ *dst_elt++ = *next_elt;
+ }
+ must_reindex = 1;
+ }
+ if (must_reindex) {
+ table_reindex(t);
+ }
/* Found an existing entry with the same key, so merge with it */
- next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
- val, NULL);
+ *(const char **)apr_array_push(&arr) = val;
+ match_elt->val = t->merge(t->a.pool, &arr);
return;
}
}
@@ -800,7 +1093,7 @@
COMPUTE_KEY_CHECKSUM(key, checksum);
elts = (apr_table_entry_t *) table_push(t);
elts->key = apr_pstrdup(t->a.pool, key);
- elts->val = apr_pstrdup(t->a.pool, val);
+ elts->val = t->copy(t->a.pool, val);
elts->key_checksum = checksum;
}
@@ -835,13 +1128,41 @@
elts->key = (char *)key;
elts->val = (char *)val;
elts->key_checksum = checksum;
+ }
+
+
+APR_DECLARE(void) apr_table_cat(apr_table_t *t, const apr_table_t *s)
+{
+ const int n = t->a.nelts;
+ register int idx;
+
+ apr_array_cat(&t->a,&s->a);
+
+ if (n == 0) {
+ memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
+ memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
+ t->index_initialized = s->index_initialized;
+ return;
+ }
+
+ for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
+ if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
+ t->index_last[idx] = s->index_last[idx] + n;
+ if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
+ t->index_first[idx] = s->index_first[idx] + n;
+ }
+ }
+ }
+
+ t->index_initialized |= s->index_initialized;
}
+
APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
const apr_table_t *overlay,
const apr_table_t *base)
-{
- apr_table_t *res;
+{
+ apr_table_t *t = apr_palloc(p, sizeof *t);
#ifdef POOL_DEBUG
/* we don't copy keys and values, so it's necessary that
@@ -860,13 +1181,27 @@
}
#endif
- res = apr_palloc(p, sizeof(apr_table_t));
- /* behave like append_arrays */
- res->a.pool = p;
- copy_array_hdr_core(&res->a, &overlay->a);
- apr_array_cat(&res->a, &base->a);
- table_reindex(res);
- return res;
+ t->a.pool = p;
+ t->a.elt_size = sizeof(apr_table_entry_t);
+ t->copy = overlay->copy;
+ t->merge = overlay->merge;
+ t->index_initialized = overlay->index_initialized;
+
+ memcpy(t->index_first,overlay->index_first,TABLE_HASH_SIZE * sizeof(int));
+ memcpy(t->index_last, overlay->index_last, TABLE_HASH_SIZE * sizeof(int));
+
+ t->a.elts = apr_palloc(p, t->a.elt_size *
+ (overlay->a.nalloc + base->a.nalloc));
+
+ memcpy(t->a.elts, overlay->a.elts, overlay->a.elt_size *
+ overlay->a.nelts);
+
+ t->a.nelts = overlay->a.nelts;
+ t->a.nalloc = overlay->a.nalloc + base->a.nalloc;
+
+ if (base->a.nelts)
+ apr_table_cat(t, base);
+ return t;
}
/* And now for something completely abstract ...
@@ -996,334 +1331,24 @@
return vdorv;
}
-/* During apr_table_overlap(), we build an overlap key for
- * each element in the two tables.
- */
-#define RED 0
-#define BLACK 1
-typedef struct overlap_key {
- /* The table element */
- apr_table_entry_t *elt;
-
- /* 0 if from table 'a', 1 if from table 'b' */
- int level;
-
- /* Whether to omit this element when building the result table */
- int skip;
-
- /* overlap_keys can be assembled into a red-black tree */
- int black;
- struct overlap_key *tree_parent;
- struct overlap_key *tree_left;
- struct overlap_key *tree_right;
- int color;
-
- /* List of multiple values for this key */
- struct overlap_key *merge_next;
- struct overlap_key *merge_last;
-} overlap_key;
-
-/* Rotate a subtree of a red-black tree */
-static void rotate_counterclockwise(overlap_key **root,
- overlap_key *rotate_node)
-{
- overlap_key *child = rotate_node->tree_right;
- rotate_node->tree_right = child->tree_left;
- if (rotate_node->tree_right) {
- rotate_node->tree_right->tree_parent = rotate_node;
- }
- child->tree_parent = rotate_node->tree_parent;
- if (child->tree_parent == NULL) {
- *root = child;
- }
- else {
- if (rotate_node == rotate_node->tree_parent->tree_left) {
- rotate_node->tree_parent->tree_left = child;
- }
- else {
- rotate_node->tree_parent->tree_right = child;
- }
- }
- child->tree_left = rotate_node;
- rotate_node->tree_parent = child;
-}
-static void rotate_clockwise(overlap_key **root, overlap_key *rotate_node)
+APR_DECLARE(void) apr_table_overlap(apr_table_t *a,
+ const apr_table_t *b,
+ const unsigned flags)
{
- overlap_key *child = rotate_node->tree_left;
- rotate_node->tree_left = child->tree_right;
- if (rotate_node->tree_left) {
- rotate_node->tree_left->tree_parent = rotate_node;
- }
- child->tree_parent = rotate_node->tree_parent;
- if (child->tree_parent == NULL) {
- *root = child;
- }
- else {
- if (rotate_node == rotate_node->tree_parent->tree_left) {
- rotate_node->tree_parent->tree_left = child;
- }
- else {
- rotate_node->tree_parent->tree_right = child;
- }
- }
- child->tree_right = rotate_node;
- rotate_node->tree_parent = child;
-}
+ const int m = a->a.nelts;
+ const int n = b->a.nelts;
+ apr_pool_t *p = b->a.pool;
-static void overlap_hash(overlap_key *elt,
- overlap_key **hash_table, int nhash,
- unsigned flags)
-{
- /* Each bucket in the hash table holds a red-black tree
- * containing the overlap_keys that hash into that bucket
- */
- overlap_key **child = &(hash_table[elt->elt->key_checksum & (nhash - 1)]);
- overlap_key **root = child;
- overlap_key *parent = NULL;
- overlap_key *next;
-
- /* Look for the element in the tree */
- while ((next = *child) != NULL) {
- int direction = strcasecmp(elt->elt->key, next->elt->key);
- if (direction < 0) {
- parent = next;
- child = &(next->tree_left);
- }
- else if (direction > 0) {
- parent = next;
- child = &(next->tree_right);
- }
- else {
- /* This is the key we're looking for */
- if (flags == APR_OVERLAP_TABLES_MERGE) {
- /* Just link this node at the end of the list
- * of values for the key. It doesn't need to
- * be linked into the tree, because the node at
- * the head of this key's value list is in the
- * tree already.
- */
- elt->skip = 1;
- elt->merge_next = NULL;
- if (next->merge_last) {
- next->merge_last->merge_next = elt;
- }
- else {
- next->merge_next = elt;
- }
- next->merge_last = elt;
- }
- else {
- /* In the "set" case, don't bother storing
- * this value in the tree if it's already
- * there, except if the previous value was
- * from table 'a' (level==0) and this value
- * is from table 'b' (level==1)
- */
- if (elt->level > next->level) {
- elt->tree_left = next->tree_left;
- if (next->tree_left) {
- next->tree_left->tree_parent = elt;
- }
- elt->tree_right = next->tree_right;
- if (next->tree_right) {
- next->tree_right->tree_parent = elt;
- }
- elt->tree_parent = next->tree_parent;
- elt->color = next->color;
- (*child) = elt;
- elt->merge_next = NULL;
- elt->merge_last = NULL;
- elt->skip = 0;
- next->skip = 1;
- }
- else {
- elt->skip = 1;
- }
- }
- return;
- }
- }
-
- /* The element wasn't in the tree, so add it */
- elt->tree_left = NULL;
- elt->tree_right = NULL;
- elt->tree_parent = parent;
- (*child) = elt;
- elt->merge_next = NULL;
- elt->merge_last = NULL;
- elt->skip = 0;
- elt->color = RED;
-
- /* Shuffle the nodes to maintain the red-black tree's balanced
- * shape property. (This is what guarantees O(n*log(n)) worst-case
- * performance for apr_table_overlap().)
- */
- next = elt;
- while ((next->tree_parent) && (next->tree_parent->color == RED)) {
- /* Note: Root is always black, and red and black nodes
- * alternate on any path down the tree. So if we're inside
- * this block, the grandparent node is non-NULL.
- */
- overlap_key *grandparent = next->tree_parent->tree_parent;
- if (next->tree_parent == grandparent->tree_left) {
- overlap_key *parent_sibling = grandparent->tree_right;
- if (parent_sibling && (parent_sibling->color == RED)) {
- next->tree_parent->color = BLACK;
- parent_sibling->color = BLACK;
- grandparent->color = RED;
- next = grandparent;
- }
- else {
- if (next == next->tree_parent->tree_right) {
- next = next->tree_parent;
- rotate_counterclockwise(root, next);
- }
- next->tree_parent->color = BLACK;
- next->tree_parent->tree_parent->color = RED;
- rotate_clockwise(root, next->tree_parent->tree_parent);
- }
- }
- else {
- overlap_key *parent_sibling = grandparent->tree_left;
- if (parent_sibling && (parent_sibling->color == RED)) {
- next->tree_parent->color = BLACK;
- parent_sibling->color = BLACK;
- grandparent->color = RED;
- next = grandparent;
- }
- else {
- if (next == next->tree_parent->tree_left) {
- next = next->tree_parent;
- rotate_clockwise(root, next);
- }
- next->tree_parent->color = BLACK;
- next->tree_parent->tree_parent->color = RED;
- rotate_counterclockwise(root, next->tree_parent->tree_parent);
- }
- }
- }
- (*root)->color = BLACK;
-}
-
-/* Must be a power of 2 */
-#define DEFAULT_HASH_SIZE 16
-
-APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
- unsigned flags)
-{
- int max_keys;
- int nkeys;
- overlap_key *cat_keys; /* concatenation of the keys of a and b */
- overlap_key **hash_table;
- int nhash;
- int i;
- apr_table_entry_t *elts;
- apr_table_entry_t *dst_elt;
-
- max_keys = a->a.nelts + b->a.nelts;
- if (!max_keys) {
- /* The following logic won't do anything harmful if we keep
- * going in this situation, but
- *
- * 1) certain memory debuggers don't like an alloc size of 0
- * so we'd like to avoid that...
- * 2) this isn't all that rare a call anyway, so it is useful
- * to skip the storage allocation and other checks in the
- * following logic
- */
+ if (m + n == 0)
return;
- }
- cat_keys = apr_palloc(b->a.pool, sizeof(overlap_key) * max_keys);
- nhash = DEFAULT_HASH_SIZE;
- while (nhash < max_keys) {
- nhash <<= 1;
- }
- hash_table = (overlap_key **)apr_pcalloc(b->a.pool,
- sizeof(overlap_key *) * nhash);
-
- /* The cat_keys array contains an element for each entry in a,
- * followed by one for each in b. While populating this array,
- * we also use it as:
- * 1) a hash table, to detect matching keys, and
- * 2) a linked list of multiple values for a given key (in the
- * APR_OVERLAP_TABLES_MERGE case)
- */
- /* First, the elements of a */
- nkeys = 0;
- elts = (apr_table_entry_t *)a->a.elts;
- for (i = 0; i < a->a.nelts; i++, nkeys++) {
- cat_keys[nkeys].elt = &(elts[i]);
- cat_keys[nkeys].level = 0;
- overlap_hash(&(cat_keys[nkeys]), hash_table, nhash, flags);
- }
-
- /* Then the elements of b */
- elts = (apr_table_entry_t *)b->a.elts;
- for (i = 0; i < b->a.nelts; i++, nkeys++) {
- cat_keys[nkeys].elt = &(elts[i]);
- cat_keys[nkeys].level = 1;
- overlap_hash(&(cat_keys[nkeys]), hash_table, nhash, flags);
- }
-
- /* Copy concatenated list of elements into table a to
- * form the new table contents, but:
- * 1) omit the ones marked "skip," and
- * 2) merge values for the same key if needed
- */
- make_array_core(&a->a, b->a.pool, max_keys, sizeof(apr_table_entry_t), 0);
- nkeys = 0;
- dst_elt = (apr_table_entry_t *)a->a.elts;
- for (i = 0; i < max_keys; i++) {
- if (cat_keys[i].skip) {
- continue;
- }
- if (cat_keys[i].merge_next) {
- char *new_val;
- char *val_next;
- overlap_key *next = cat_keys[i].merge_next;
- int len = (cat_keys[i].elt->val ?
- strlen(cat_keys[i].elt->val) : 0);
- do {
- len += 2;
- if (next->elt->val) {
- len += strlen(next->elt->val);
- }
- next = next->merge_next;
- } while (next);
- len++;
- new_val = (char *)apr_palloc(b->a.pool, len);
- val_next = new_val;
- if (cat_keys[i].elt->val) {
- strcpy(val_next, cat_keys[i].elt->val);
- val_next += strlen(cat_keys[i].elt->val);
- }
- next = cat_keys[i].merge_next;
- do {
- *val_next++ = ',';
- *val_next++ = ' ';
- if (next->elt->val) {
- strcpy(val_next, next->elt->val);
- val_next += strlen(next->elt->val);
- }
- next = next->merge_next;
- } while (next);
- *val_next = 0;
- dst_elt->key = cat_keys[i].elt->key;
- dst_elt->val = new_val;
- dst_elt->key_checksum = cat_keys[i].elt->key_checksum;
- dst_elt++;
- }
- else {
- dst_elt->key = cat_keys[i].elt->key;
- dst_elt->val = cat_keys[i].elt->val;
- dst_elt->key_checksum = cat_keys[i].elt->key_checksum;
- dst_elt++;
- }
+ /* copy (extend) a using b's pool */
+ if (a->a.pool != p) {
+ make_array_core(&a->a, p, m+n, sizeof(apr_table_entry_t), 0);
}
- a->a.nelts = dst_elt - (apr_table_entry_t *)a->a.elts;
- table_reindex(a);
-}
+ apr_table_cat(a, b);
+ apr_table_compress(a, flags);
+}
--
Joe Schaefer
