On Mon, 2001-11-19 at 22:38, Brian Pane wrote:
> Here's the latest revision of my apr_table_t optimizations.
> It's the same as the last one, except that the hash table in
> apr_table_overlap() now uses a red-black tree rather than
> a linear list to hold multiple entries per hash bucket, so
> that the worst-case run time of apr_table_overlap() is
> O(n*log(n)) instead of O(n^2).
>
> --Brian
Committed.
Thanks 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/20 06:19:11
> @@ -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/20 06:19:11
> @@ -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/20 06:19:12
> @@ -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,28 @@
> * 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) \
> +{ \
> + if ((key)[0] && (key)[1] && (key)[2] && (key)[3]) { \
> + checksum = (*((apr_uint32_t *)(key))) & CASE_MASK; \
> + } \
> + else { \
> + checksum = 0; \
> + } \
> +}
> +
> /*
> * XXX: if you tweak this you should look at is_empty_table() and
> table_elts()
> * in alloc.h
> @@ -298,7 +325,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 +345,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 +360,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 +382,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 +396,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 +410,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 +420,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 +435,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 +447,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 +461,7 @@
> elts = (apr_table_entry_t *) table_push(t);
> elts->key = (char *)key;
> elts->val = (char *)val;
> + elts->key_checksum = checksum;
> }
> }
>
> @@ -432,9 +469,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 +483,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 +498,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 +511,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 +519,7 @@
> {
> apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
> int i;
> + apr_uint32_t checksum;
>
> #ifdef POOL_DEBUG
> {
> @@ -490,8 +534,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 +545,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 +580,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 +678,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;
> + }
> }
> }
>
--
Ian Holsman [EMAIL PROTECTED]
Performance Measurement & Analysis
CNET Networks - (415) 344-2608
