This is a repost of my patch to speed up tables, with one change from the previous version: the technique used to compute the checksums was unsafe on SPARCs (doing *(int *)str where 'str' is a char* yields a bus error if the string doesn't start on a word boundary), so I replaced it with a slightly slower--but safe--implementation that builds the checksum a character at a time.
Within Apache, this patch reduces the CPU time spent in table ops by about 40%. In benchmark testing of the httpd, the patch yields a 1-3% increase in throughput to clients (thanks to IanH for the throughput data).
Note: Because the patch increases the size of apr_table_entry_t, it requires a "make clean."
--Brian
Index: modules/arch/win32/mod_isapi.c =================================================================== RCS file: /home/cvs/httpd-2.0/modules/arch/win32/mod_isapi.c,v retrieving revision 1.51 diff -u -r1.51 mod_isapi.c --- modules/arch/win32/mod_isapi.c 2001/11/11 22:31:03 1.51 +++ modules/arch/win32/mod_isapi.c 2001/11/22 00:36:40 @@ -567,13 +567,15 @@ /* lf delimited, colon split, comma seperated and * null terminated list of HTTP_ vars */ - const char * const *env = (const char* const *) apr_table_elts(r->subprocess_env)->elts; - int nelts = 2 * apr_table_elts(r->subprocess_env)->nelts; + const apr_array_header_t *arr = apr_table_elts(r->subprocess_env); + const apr_table_entry_t *elts = (const apr_table_entry_t *)arr->elts; int i; - for (len = 0, i = 0; i < nelts; i += 2) - if (!strncmp(env[i], "HTTP_", 5)) - len += strlen(env[i]) + strlen(env[i + 1]) + 2; + for (len = 0, i = 0; i < arr->nelts; i++) { + if (!strncmp(elts[i].key, "HTTP_", 5)) { + len += strlen(elts[i].key) + strlen(elts[i].val) + 2; + } + } if (*lpdwSizeofBuffer < len + 1) { *lpdwSizeofBuffer = len + 1; @@ -581,15 +583,16 @@ return FALSE; } - for (i = 0; i < nelts; i += 2) - if (!strncmp(env[i], "HTTP_", 5)) { - strcpy(lpvBuffer, env[i]); - ((char*)lpvBuffer) += strlen(env[i]); + for (i = 0; i < arr->nelts; i++) { + if (!strncmp(elts[i].key, "HTTP_", 5)) { + strcpy(lpvBuffer, elts[i].key); + ((char*)lpvBuffer) += strlen(elts[i].key); *(((char*)lpvBuffer)++) = ':'; - strcpy(lpvBuffer, env[i + 1]); - ((char*)lpvBuffer) += strlen(env[i + 1]); + strcpy(lpvBuffer, elts[i].val); + ((char*)lpvBuffer) += strlen(elts[i].val); *(((char*)lpvBuffer)++) = '\n'; } + } *(((char*)lpvBuffer)++) = '\0'; *lpdwSizeofBuffer = len; @@ -601,12 +604,13 @@ /* lf delimited, colon split, comma seperated and * null terminated list of the raw request header */ - const char * const *raw = (const char* const *) apr_table_elts(r->headers_in)->elts; - int nelts = 2 * apr_table_elts(r->headers_in)->nelts; + const apr_array_header_t *arr = apr_table_elts(r->headers_in); + const apr_table_entry_t *elts = (const apr_table_entry_t *)arr->elts; int i; - for (len = 0, i = 0; i < nelts; i += 2) - len += strlen(raw[i]) + strlen(raw[i + 1]) + 2; + for (len = 0, i = 0; i < arr->nelts; i++) { + len += strlen(elts[i].key) + strlen(elts[i].val) + 2; + } if (*lpdwSizeofBuffer < len + 1) { *lpdwSizeofBuffer = len + 1; @@ -614,15 +618,14 @@ return FALSE; } - for (i = 0; i < nelts; i += 2) { - strcpy(lpvBuffer, raw[i]); - ((char*)lpvBuffer) += strlen(raw[i]); + for (i = 0; i < arr->nelts; i++) { + strcpy(lpvBuffer, elts[i].key); + ((char*)lpvBuffer) += strlen(elts[i].key); *(((char*)lpvBuffer)++) = ':'; *(((char*)lpvBuffer)++) = ' '; - strcpy(lpvBuffer, raw[i + 1]); - ((char*)lpvBuffer) += strlen(raw[i + 1]); + strcpy(lpvBuffer, elts[i].val); + ((char*)lpvBuffer) += strlen(elts[i].val); *(((char*)lpvBuffer)++) = '\n'; - i += 2; } *(((char*)lpvBuffer)++) = '\0'; *lpdwSizeofBuffer = len; Index: srclib/apr/include/apr_tables.h =================================================================== RCS file: /home/cvspublic/apr/include/apr_tables.h,v retrieving revision 1.24 diff -u -r1.24 apr_tables.h --- srclib/apr/include/apr_tables.h 2001/11/11 22:31:04 1.24 +++ srclib/apr/include/apr_tables.h 2001/11/22 00:36:41 @@ -130,6 +130,9 @@ */ /** The value for the current table entry */ char *val; + + /** A checksum for the key, for use by the apr_table internals */ + apr_uint32_t key_checksum; }; /** Index: srclib/apr/tables/apr_tables.c =================================================================== RCS file: /home/cvspublic/apr/tables/apr_tables.c,v retrieving revision 1.17 diff -u -r1.17 apr_tables.c --- srclib/apr/tables/apr_tables.c 2001/08/02 03:18:44 1.17 +++ srclib/apr/tables/apr_tables.c 2001/11/22 00:36:41 @@ -89,7 +89,7 @@ */ static void make_array_core(apr_array_header_t *res, apr_pool_t *p, - int nelts, int elt_size) + int nelts, int elt_size, int clear) { /* * Assure sanity if someone asks for @@ -99,7 +99,12 @@ nelts = 1; } - res->elts = apr_pcalloc(p, nelts * elt_size); + if (clear) { + res->elts = apr_pcalloc(p, nelts * elt_size); + } + else { + res->elts = apr_palloc(p, nelts * elt_size); + } res->pool = p; res->elt_size = elt_size; @@ -113,7 +118,7 @@ apr_array_header_t *res; res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t)); - make_array_core(res, p, nelts, elt_size); + make_array_core(res, p, nelts, elt_size, 1); return res; } @@ -277,6 +282,41 @@ * The "table" functions. */ +#if APR_CHARSET_EBCDIC +#define CASE_MASK 0xbfbfbfbf +#else +#define CASE_MASK 0xdfdfdfdf +#endif + +/* Compute the "checksum" for a key, consisting of the first + * 4 bytes, normalized for case-insensitivity and packed into + * an int...this checksum allows us to do a single integer + * comparison as a fast check to determine whether we can + * skip a strcasecmp + */ +#define COMPUTE_KEY_CHECKSUM(key, checksum) \ +{ \ + const char *k = (key); \ + apr_uint32_t c = (apr_uint32_t)*k; \ + (checksum) = c; \ + (checksum) <<= 8; \ + if (c) { \ + c = (apr_uint32_t)*++k; \ + checksum |= c; \ + } \ + (checksum) <<= 8; \ + if (c) { \ + c = (apr_uint32_t)*++k; \ + checksum |= c; \ + } \ + (checksum) <<= 8; \ + if (c) { \ + c = (apr_uint32_t)*++k; \ + checksum |= c; \ + } \ + checksum &= CASE_MASK; \ +} + /* * XXX: if you tweak this you should look at is_empty_table() and table_elts() * in alloc.h @@ -298,7 +338,7 @@ { apr_table_t *t = apr_palloc(p, sizeof(apr_table_t)); - make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t)); + make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0); #ifdef MAKE_TABLE_PROFILE t->creator = __builtin_return_address(0); #endif @@ -318,7 +358,7 @@ abort(); } #endif - make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t)); + 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; return new; @@ -333,13 +373,15 @@ { apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; int i; + apr_uint32_t checksum; if (key == NULL) { return NULL; } + COMPUTE_KEY_CHECKSUM(key, checksum); for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { + if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) { return elts[i].val; } } @@ -353,9 +395,11 @@ register int i, j, k; apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; int done = 0; + apr_uint32_t checksum; + COMPUTE_KEY_CHECKSUM(key, checksum); for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { + if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) { if (!done) { elts[i].val = apr_pstrdup(t->a.pool, val); done = 1; @@ -365,6 +409,7 @@ for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { elts[j].key = elts[k].key; elts[j].val = elts[k].val; + elts[j].key_checksum = elts[k].key_checksum; } --t->a.nelts; } @@ -378,6 +423,7 @@ 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->key_checksum = checksum; } } @@ -387,6 +433,7 @@ register int i, j, k; apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; int done = 0; + apr_uint32_t checksum; #ifdef POOL_DEBUG { @@ -401,8 +448,9 @@ } #endif + COMPUTE_KEY_CHECKSUM(key, checksum); for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { + if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) { if (!done) { elts[i].val = (char *)val; done = 1; @@ -412,6 +460,7 @@ for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { elts[j].key = elts[k].key; elts[j].val = elts[k].val; + elts[j].key_checksum = elts[k].key_checksum; } --t->a.nelts; } @@ -425,6 +474,7 @@ elts = (apr_table_entry_t *) table_push(t); elts->key = (char *)key; elts->val = (char *)val; + elts->key_checksum = checksum; } } @@ -432,9 +482,11 @@ { register int i, j, k; apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; + apr_uint32_t checksum; + COMPUTE_KEY_CHECKSUM(key, checksum); for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { + if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) { /* found an element to skip over * there are any number of ways to remove an element from @@ -444,6 +496,7 @@ for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { elts[j].key = elts[k].key; elts[j].val = elts[k].val; + elts[j].key_checksum = elts[k].key_checksum; } --t->a.nelts; } @@ -458,9 +511,11 @@ { apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; int i; + apr_uint32_t checksum; + COMPUTE_KEY_CHECKSUM(key, checksum); for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { + if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) { elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL); return; } @@ -469,6 +524,7 @@ 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->key_checksum = checksum; } APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key, @@ -476,6 +532,7 @@ { apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; int i; + apr_uint32_t checksum; #ifdef POOL_DEBUG { @@ -490,8 +547,9 @@ } #endif + COMPUTE_KEY_CHECKSUM(key, checksum); for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { + if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) { elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL); return; } @@ -500,22 +558,27 @@ elts = (apr_table_entry_t *) table_push(t); elts->key = (char *)key; elts->val = (char *)val; + elts->key_checksum = checksum; } APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key, const char *val) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; + apr_table_entry_t *elts; + apr_uint32_t checksum; + 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->key_checksum = checksum; } APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key, const char *val) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; + apr_table_entry_t *elts; + apr_uint32_t checksum; #ifdef POOL_DEBUG { @@ -530,9 +593,11 @@ } #endif + COMPUTE_KEY_CHECKSUM(key, checksum); elts = (apr_table_entry_t *) table_push(t); elts->key = (char *)key; elts->val = (char *)val; + elts->key_checksum = checksum; } APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p, @@ -626,171 +691,333 @@ int rv, i; argp = va_arg(vp, char *); do { + apr_uint32_t checksum = 0; + if (argp) { + COMPUTE_KEY_CHECKSUM(argp, checksum); + } for (rv = 1, i = 0; rv && (i < t->a.nelts); ++i) { - if (elts[i].key && (!argp || !strcasecmp(elts[i].key, argp))) { + if (elts[i].key && (!argp || + ((checksum == elts[i].key_checksum) && + !strcasecmp(elts[i].key, argp)))) { rv = (*comp) (rec, elts[i].key, elts[i].val); } } } while (argp && ((argp = va_arg(vp, char *)) != NULL)); } -/* Curse libc and the fact that it doesn't guarantee a stable sort. We - * have to enforce stability ourselves by using the order field. If it - * provided a stable sort then we wouldn't even need temporary storage to - * do the work below. -djg - * - * ("stable sort" means that equal keys retain their original relative - * ordering in the output.) +/* During apr_table_overlap(), we build an overlap key for + * each element in the two tables. */ -typedef struct { - char *key; - char *val; - int order; +#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; -static int sort_overlap(const void *va, const void *vb) -{ - const overlap_key *a = va; - const overlap_key *b = vb; - int r; - - r = strcasecmp(a->key, b->key); - if (r) { - return r; +/* 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; } - return a->order - b->order; + 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; } -/* prefer to use the stack for temp storage for overlaps smaller than this */ -#ifndef APR_OVERLAP_TABLES_ON_STACK -#define APR_OVERLAP_TABLES_ON_STACK (512) -#endif - -APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, - unsigned flags) +static void rotate_clockwise(overlap_key **root, overlap_key *rotate_node) { - overlap_key cat_keys_buf[APR_OVERLAP_TABLES_ON_STACK]; - overlap_key *cat_keys; - int nkeys; - apr_table_entry_t *e; - apr_table_entry_t *last_e; - overlap_key *left; - overlap_key *right; - overlap_key *last; - - nkeys = a->a.nelts + b->a.nelts; - if (nkeys < APR_OVERLAP_TABLES_ON_STACK) { - cat_keys = cat_keys_buf; + 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 { - /* XXX: could use scratch free space in a or b's pool instead... - * which could save an allocation in b's pool. - */ - cat_keys = apr_palloc(b->a.pool, sizeof(overlap_key) * nkeys); + 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; +} - nkeys = 0; - /* Create a list of the entries from a concatenated with the entries - * from b. +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 */ - e = (apr_table_entry_t *)a->a.elts; - last_e = e + a->a.nelts; - while (e < last_e) { - cat_keys[nkeys].key = e->key; - cat_keys[nkeys].val = e->val; - cat_keys[nkeys].order = nkeys; - ++nkeys; - ++e; - } - - e = (apr_table_entry_t *)b->a.elts; - last_e = e + b->a.nelts; - while (e < last_e) { - cat_keys[nkeys].key = e->key; - cat_keys[nkeys].val = e->val; - cat_keys[nkeys].order = nkeys; - ++nkeys; - ++e; + 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, becaue 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; + (*child) = elt; + elt->merge_next = NULL; + elt->merge_last = NULL; + elt->skip = 0; + next->skip = 1; + } + else { + elt->skip = 1; + } + } + return; + } } - - qsort(cat_keys, nkeys, sizeof(overlap_key), sort_overlap); - /* Now iterate over the sorted list and rebuild a. - * Start by making sure it has enough space. + /* 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().) */ - a->a.nelts = 0; - if (a->a.nalloc < nkeys) { - a->a.elts = apr_palloc(a->a.pool, a->a.elt_size * nkeys * 2); - a->a.nalloc = nkeys * 2; + 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; +} - /* - * In both the merge and set cases we retain the invariant: - * - * left->key, (left+1)->key, (left+2)->key, ..., (right-1)->key - * are all equal keys. (i.e. strcasecmp returns 0) - * - * We essentially need to find the maximal - * right for each key, then we can do a quick merge or set as - * appropriate. +/* 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 *b_start; + overlap_key **hash_table; + int nhash; + int i; + apr_table_entry_t *elts; + + max_keys = a->a.nelts + b->a.nelts; + 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) */ - if (flags & APR_OVERLAP_TABLES_MERGE) { - left = cat_keys; - last = left + nkeys; - while (left < last) { - right = left + 1; - if (right == last - || strcasecmp(left->key, right->key)) { - apr_table_addn(a, left->key, left->val); - left = right; - } - else { - char *strp; - char *value; - size_t len; - - /* Have to merge some headers. Let's re-use the order field, - * since it's handy... we'll store the length of val there. - */ - left->order = strlen(left->val); - len = left->order; - do { - right->order = strlen(right->val); - len += 2 + right->order; - ++right; - } while (right < last - && !strcasecmp(left->key, right->key)); - /* right points one past the last header to merge */ - value = apr_palloc(a->a.pool, len + 1); - strp = value; - for (;;) { - memcpy(strp, left->val, left->order); - strp += left->order; - ++left; - if (left == right) { - break; - } - *strp++ = ','; - *strp++ = ' '; - } - *strp = 0; - apr_table_addn(a, (left-1)->key, value); - } - } - } - else { - left = cat_keys; - last = left + nkeys; - while (left < last) { - right = left + 1; - while (right < last && !strcasecmp(left->key, right->key)) { - ++right; - } - apr_table_addn(a, (right-1)->key, (right-1)->val); - left = right; - } + /* 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; + for (i = 0; i < max_keys; i++) { + if (cat_keys[i].skip) { + continue; + } + if (cat_keys[i].merge_next) { + apr_table_entry_t *elt; + 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; + elt = (apr_table_entry_t *)table_push(a); + elt->key = cat_keys[i].elt->key; + elt->val = new_val; + elt->key_checksum = cat_keys[i].elt->key_checksum; + } + else { + apr_table_entry_t *elt = (apr_table_entry_t *)table_push(a); + elt->key = cat_keys[i].elt->key; + elt->val = cat_keys[i].elt->val; + elt->key_checksum = cat_keys[i].elt->key_checksum; + } } }