httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ian Holsman <i...@cnet.com>
Subject Re: [PATCH 3] speedup for apr_table_t
Date Mon, 26 Nov 2001 16:43:53 GMT
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          IanH@cnet.com
Performance Measurement & Analysis
CNET Networks   -   (415) 344-2608


Mime
View raw message