apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joe Schaefer <joe+gm...@sunstarsys.com>
Subject [PATCH] Re: Frankentables
Date Sat, 17 May 2003 01:19:07 GMT
Joe Schaefer <joe+gmane@sunstarsys.com> writes:

[...]

> There's a crude set of table tests in httpd-apreq-2/t/performance.c,
> but basically what they tell me is that
> 
>   1) Getting rid of the temporary table in ap_get_mime_headers_core
>      is a big win.
> 
>   2) For tables whose entries can be distinguished by first letter
>      alone, the current implementation is faster. I haven't benchmarked
>      the addn difference yet, but the penalty on the new code
>      is certainly more substantial there.

I haven't out a figured a way to make my tree implementation faster
(overall) than the current table implementation wrt httpd, but the 
following patch incorporates the above ideas into the current code.

oprofile tells me this version wins by ~10 - 25% when measuring the
time httpd spends in table ops.  To get the full benefit, 
ap_get_mime_headers_core in httpd-2.0/server/protocol.c also 
needs a patch.

The first patch is for httpd-2.0, the other two are for apr_tables.

-- Joe Schaefer

Index: server/protocol.c
===================================================================
RCS file: /home/cvspublic/httpd-2.0/server/protocol.c,v
retrieving revision 1.131
diff -u -r1.131 protocol.c
--- server/protocol.c   15 Apr 2003 22:47:57 -0000      1.131
+++ server/protocol.c   16 May 2003 23:47:33 -0000
@@ -705,10 +705,6 @@
     char *value;
     apr_size_t len;
     int fields_read = 0;
-    apr_table_t *tmp_headers;
-
-    /* We'll use apr_table_overlap later to merge these into r->headers_in. */
-    tmp_headers = apr_table_make(r->pool, 50);

     /*
      * Read header lines until we get the empty separator line, a read error,
@@ -796,7 +792,7 @@
                     ++value;            /* Skip to start of value   */
                 }

-                apr_table_addn(tmp_headers, last_field, value);
+                apr_table_addn(r->headers_in, last_field, value);

                 /* reset the alloc_len so that we'll allocate a new
                  * buffer if we have to do any more folding: we can't
@@ -822,8 +818,7 @@
             last_len = len;
         }
     }
-
-    apr_table_overlap(r->headers_in, tmp_headers, APR_OVERLAP_TABLES_MERGE);
+    apr_table_compress(r->headers_in);
 }

 AP_DECLARE(void) ap_get_mime_headers(request_rec *r)
 



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	17 May 2003 01:02:19 -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,25 @@
  */
 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.
+ */
+APR_DECLARE(void) apr_table_compress(apr_table_t *t);
+
+/**
+ * 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	17 May 2003 01:02:22 -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,81 @@
     }
 }
 
+static void bury_table_entries(apr_table_t *t, apr_array_header_t *q)
+{
+    apr_table_entry_t *const o = (apr_table_entry_t *)t->a.elts;
+    int j, m, n, *p;
+
+    /* add sentinel */
+    *(int *)apr_array_push(q) = t->a.nelts; 
+    q->nelts--;
+    p = (int *)q->elts;
+
+    /* remove entries O(t->nelts - p[o]) */
+    for (j=1, n=0; n < q->nelts; ++j, ++n)
+        for (m = p[n]+1; m < p[n+1]; ++m)
+            m[o-j] = m[o];
+
+    t->a.nelts -= q->nelts;
+    table_reindex(t);
+}
+
+#define DEFAULT_NELTS 8
+
+APR_DECLARE(void)apr_table_compress(apr_table_t *t)
+{
+    int g[DEFAULT_NELTS];
+    apr_array_header_t ghosts = { t->a.pool, sizeof(int), 0,
+                                  DEFAULT_NELTS, (char *)g };
+    char *a[DEFAULT_NELTS];
+    apr_array_header_t arr = {t->a.pool, sizeof(char *), 0,
+                              DEFAULT_NELTS, (char *)a};
+
+    apr_table_entry_t *const table_start = (apr_table_entry_t *)t->a.elts;
+    apr_table_entry_t *const table_end   = table_start + t->a.nelts;
+    apr_table_entry_t *next_elt;
+
+    /* mark & sweep:
+     * Iterate through the table, marking duplicates by setting their
+     * checksum to -1 (-1 is "greater" than CASE_MASK as unsigned integer 
+     * types).  The process is quadratic in time, but linear in space.
+     * Once the duplicates are marked, the original value is replaced
+     * by merging it with the rest.
+     */
+
+    for (next_elt = table_start; next_elt < table_end; ++next_elt) {
+        const apr_uint32_t checksum = next_elt->key_checksum;
+        const char *const key = next_elt->key;
+
+        apr_table_entry_t *e = next_elt;
+        const apr_table_entry_t *const end = table_start + 
+            t->index_last[TABLE_HASH(next_elt->key)];
+
+        if (checksum == -1) {
+            *(int *)apr_array_push(&ghosts) = next_elt - table_start;
+            continue;
+        }
+
+        arr.nelts = 0;
+        *(const char **)apr_array_push(&arr) = e->val;
+
+        while (++e <= end) {
+            if ((checksum == e->key_checksum) &&
+                !strcasecmp(e->key, key)) {
+                e->key_checksum = -1;
+                *(const char **)apr_array_push(&arr) = e->val;
+            }
+        }
+
+        if (arr.nelts > 1) {
+            next_elt->val = t->merge(t->a.pool, &arr);
+        }
+    }
+
+    if (ghosts.nelts)
+        bury_table_entries(t, &ghosts);
+}
+
 APR_DECLARE(void) apr_table_clear(apr_table_t *t)
 {
     t->a.nelts = 0;
@@ -528,7 +625,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 +664,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 +799,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 +815,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 +869,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 +878,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 +907,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;
         }
     }
@@ -835,13 +1015,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 +1068,26 @@
     }
 #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;
+
+    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 +1217,39 @@
     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)
+static char *collapse(apr_pool_t *p, 
+                               const apr_array_header_t *arr)
 {
-    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;
+    char **a = (char **)arr->elts;
+    return (arr->nelts == 0) ? NULL : a[arr->nelts - 1];
 }
 
 
-static void overlap_hash(overlap_key *elt,
-                         overlap_key **hash_table, int nhash,
-                         unsigned flags)
+APR_DECLARE(void) apr_table_overlap(apr_table_t *a, 
+                                    const apr_table_t *b,
+                                    const 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;
+    const int m = a->a.nelts;
+    const int n = b->a.nelts;
+    apr_pool_t *p = b->a.pool;
 
-    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;
+
+    /* 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);
     }
-    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++;
-        }
+    apr_table_cat(a, b);
+
+    if (flags == APR_OVERLAP_TABLES_SET) {
+        apr_table_merger_t *f = a->merge;
+        a->merge = collapse;
+        apr_table_compress(a);
+        a->merge = f;
     }
-    a->a.nelts = dst_elt - (apr_table_entry_t *)a->a.elts;
-    table_reindex(a);
+    else
+        apr_table_compress(a);
 }
-


Mime
View raw message