Adding upstream version 1.7.2.upstream/1.7.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 2716 insertions, 0 deletions

diff --git a/tables/apr_hash.c b/tables/apr_hash.c
new file mode 100644
index 0000000..0bf4d28
--- /dev/null
+++ b/tables/apr_hash.c
@@ -0,0 +1,552 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "apr_private.h"
+
+#include "apr_general.h"
+#include "apr_pools.h"
+#include "apr_time.h"
+
+#include "apr_hash.h"
+
+#if APR_HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if APR_HAVE_STRING_H
+#include <string.h>
+#endif
+
+#if APR_POOL_DEBUG && APR_HAVE_STDIO_H
+#include <stdio.h>
+#endif
+
+/*
+ * The internal form of a hash table.
+ *
+ * The table is an array indexed by the hash of the key; collisions
+ * are resolved by hanging a linked list of hash entries off each
+ * element of the array. Although this is a really simple design it
+ * isn't too bad given that pools have a low allocation overhead.
+ */
+
+typedef struct apr_hash_entry_t apr_hash_entry_t;
+
+struct apr_hash_entry_t {
+    apr_hash_entry_t *next;
+    unsigned int      hash;
+    const void       *key;
+    apr_ssize_t       klen;
+    const void       *val;
+};
+
+/*
+ * Data structure for iterating through a hash table.
+ *
+ * We keep a pointer to the next hash entry here to allow the current
+ * hash entry to be freed or otherwise mangled between calls to
+ * apr_hash_next().
+ */
+struct apr_hash_index_t {
+    apr_hash_t         *ht;
+    apr_hash_entry_t   *this, *next;
+    unsigned int        index;
+};
+
+/*
+ * The size of the array is always a power of two. We use the maximum
+ * index rather than the size so that we can use bitwise-AND for
+ * modular arithmetic.
+ * The count of hash entries may be greater depending on the chosen
+ * collision rate.
+ */
+struct apr_hash_t {
+    apr_pool_t          *pool;
+    apr_hash_entry_t   **array;
+    apr_hash_index_t     iterator;  /* For apr_hash_first(NULL, ...) */
+    unsigned int         count, max, seed;
+    apr_hashfunc_t       hash_func;
+    apr_hash_entry_t    *free;  /* List of recycled entries */
+};
+
+#define INITIAL_MAX 15 /* tunable == 2^n - 1 */
+
+
+/*
+ * Hash creation functions.
+ */
+
+static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max)
+{
+   return apr_pcalloc(ht->pool, sizeof(*ht->array) * (max + 1));
+}
+
+APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool)
+{
+    apr_hash_t *ht;
+    apr_time_t now = apr_time_now();
+
+    ht = apr_palloc(pool, sizeof(apr_hash_t));
+    ht->pool = pool;
+    ht->free = NULL;
+    ht->count = 0;
+    ht->max = INITIAL_MAX;
+    ht->seed = (unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)pool ^
+                              (apr_uintptr_t)ht ^ (apr_uintptr_t)&now) - 1;
+    ht->array = alloc_array(ht, ht->max);
+    ht->hash_func = NULL;
+
+    return ht;
+}
+
+APR_DECLARE(apr_hash_t *) apr_hash_make_custom(apr_pool_t *pool,
+                                               apr_hashfunc_t hash_func)
+{
+    apr_hash_t *ht = apr_hash_make(pool);
+    ht->hash_func = hash_func;
+    return ht;
+}
+
+
+/*
+ * Hash iteration functions.
+ */
+
+APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)
+{
+    hi->this = hi->next;
+    while (!hi->this) {
+        if (hi->index > hi->ht->max)
+            return NULL;
+
+        hi->this = hi->ht->array[hi->index++];
+    }
+    hi->next = hi->this->next;
+    return hi;
+}
+
+APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_pool_t *p, apr_hash_t *ht)
+{
+    apr_hash_index_t *hi;
+    if (p)
+        hi = apr_palloc(p, sizeof(*hi));
+    else
+        hi = &ht->iterator;
+
+    hi->ht = ht;
+    hi->index = 0;
+    hi->this = NULL;
+    hi->next = NULL;
+    return apr_hash_next(hi);
+}
+
+APR_DECLARE(void) apr_hash_this(apr_hash_index_t *hi,
+                                const void **key,
+                                apr_ssize_t *klen,
+                                void **val)
+{
+    if (key)  *key  = hi->this->key;
+    if (klen) *klen = hi->this->klen;
+    if (val)  *val  = (void *)hi->this->val;
+}
+
+APR_DECLARE(const void *) apr_hash_this_key(apr_hash_index_t *hi)
+{
+    const void *key;
+
+    apr_hash_this(hi, &key, NULL, NULL);
+    return key;
+}
+
+APR_DECLARE(apr_ssize_t) apr_hash_this_key_len(apr_hash_index_t *hi)
+{
+    apr_ssize_t klen;
+
+    apr_hash_this(hi, NULL, &klen, NULL);
+    return klen;
+}
+
+APR_DECLARE(void *) apr_hash_this_val(apr_hash_index_t *hi)
+{
+    void *val;
+
+    apr_hash_this(hi, NULL, NULL, &val);
+    return val;
+}
+
+/*
+ * Expanding a hash table
+ */
+
+static void expand_array(apr_hash_t *ht)
+{
+    apr_hash_index_t *hi;
+    apr_hash_entry_t **new_array;
+    unsigned int new_max;
+
+    new_max = ht->max * 2 + 1;
+    new_array = alloc_array(ht, new_max);
+    for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {
+        unsigned int i = hi->this->hash & new_max;
+        hi->this->next = new_array[i];
+        new_array[i] = hi->this;
+    }
+    ht->array = new_array;
+    ht->max = new_max;
+}
+
+static unsigned int hashfunc_default(const char *char_key, apr_ssize_t *klen,
+                                     unsigned int hash)
+{
+    const unsigned char *key = (const unsigned char *)char_key;
+    const unsigned char *p;
+    apr_ssize_t i;
+    
+    /*
+     * This is the popular `times 33' hash algorithm which is used by
+     * perl and also appears in Berkeley DB. This is one of the best
+     * known hash functions for strings because it is both computed
+     * very fast and distributes very well.
+     *
+     * The originator may be Dan Bernstein but the code in Berkeley DB
+     * cites Chris Torek as the source. The best citation I have found
+     * is "Chris Torek, Hash function for text in C, Usenet message
+     * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
+     * Salz's USENIX 1992 paper about INN which can be found at
+     * <http://citeseer.nj.nec.com/salz92internetnews.html>.
+     *
+     * The magic of number 33, i.e. why it works better than many other
+     * constants, prime or not, has never been adequately explained by
+     * anyone. So I try an explanation: if one experimentally tests all
+     * multipliers between 1 and 256 (as I did while writing a low-level
+     * data structure library some time ago) one detects that even
+     * numbers are not useable at all. The remaining 128 odd numbers
+     * (except for the number 1) work more or less all equally well.
+     * They all distribute in an acceptable way and this way fill a hash
+     * table with an average percent of approx. 86%.
+     *
+     * If one compares the chi^2 values of the variants (see
+     * Bob Jenkins ``Hashing Frequently Asked Questions'' at
+     * http://burtleburtle.net/bob/hash/hashfaq.html for a description
+     * of chi^2), the number 33 not even has the best value. But the
+     * number 33 and a few other equally good numbers like 17, 31, 63,
+     * 127 and 129 have nevertheless a great advantage to the remaining
+     * numbers in the large set of possible multipliers: their multiply
+     * operation can be replaced by a faster operation based on just one
+     * shift plus either a single addition or subtraction operation. And
+     * because a hash function has to both distribute good _and_ has to
+     * be very fast to compute, those few numbers should be preferred.
+     *
+     *                  -- Ralf S. Engelschall <rse@engelschall.com>
+     */
+
+    if (*klen == APR_HASH_KEY_STRING) {
+        for (p = key; *p; p++) {
+            hash = hash * 33 + *p;
+        }
+        *klen = p - key;
+    }
+    else {
+        for (p = key, i = *klen; i; i--, p++) {
+            hash = hash * 33 + *p;
+        }
+    }
+
+    return hash;
+}
+
+APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,
+                                                      apr_ssize_t *klen)
+{
+    return hashfunc_default(char_key, klen, 0);
+}
+
+/*
+ * This is where we keep the details of the hash function and control
+ * the maximum collision rate.
+ *
+ * If val is non-NULL it creates and initializes a new hash entry if
+ * there isn't already one there; it returns an updatable pointer so
+ * that hash entries can be removed.
+ */
+
+static apr_hash_entry_t **find_entry(apr_hash_t *ht,
+                                     const void *key,
+                                     apr_ssize_t klen,
+                                     const void *val)
+{
+    apr_hash_entry_t **hep, *he;
+    unsigned int hash;
+
+    if (ht->hash_func)
+        hash = ht->hash_func(key, &klen);
+    else
+        hash = hashfunc_default(key, &klen, ht->seed);
+
+    /* scan linked list */
+    for (hep = &ht->array[hash & ht->max], he = *hep;
+         he; hep = &he->next, he = *hep) {
+        if (he->hash == hash
+            && he->klen == klen
+            && memcmp(he->key, key, klen) == 0)
+            break;
+    }
+    if (he || !val)
+        return hep;
+
+    /* add a new entry for non-NULL values */
+    if ((he = ht->free) != NULL)
+        ht->free = he->next;
+    else
+        he = apr_palloc(ht->pool, sizeof(*he));
+    he->next = NULL;
+    he->hash = hash;
+    he->key  = key;
+    he->klen = klen;
+    he->val  = val;
+    *hep = he;
+    ht->count++;
+    return hep;
+}
+
+APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
+                                        const apr_hash_t *orig)
+{
+    apr_hash_t *ht;
+    apr_hash_entry_t *new_vals;
+    unsigned int i, j;
+
+    ht = apr_palloc(pool, sizeof(apr_hash_t) +
+                    sizeof(*ht->array) * (orig->max + 1) +
+                    sizeof(apr_hash_entry_t) * orig->count);
+    ht->pool = pool;
+    ht->free = NULL;
+    ht->count = orig->count;
+    ht->max = orig->max;
+    ht->seed = orig->seed;
+    ht->hash_func = orig->hash_func;
+    ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
+
+    new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
+                                    sizeof(*ht->array) * (orig->max + 1));
+    j = 0;
+    for (i = 0; i <= ht->max; i++) {
+        apr_hash_entry_t **new_entry = &(ht->array[i]);
+        apr_hash_entry_t *orig_entry = orig->array[i];
+        while (orig_entry) {
+            *new_entry = &new_vals[j++];
+            (*new_entry)->hash = orig_entry->hash;
+            (*new_entry)->key = orig_entry->key;
+            (*new_entry)->klen = orig_entry->klen;
+            (*new_entry)->val = orig_entry->val;
+            new_entry = &((*new_entry)->next);
+            orig_entry = orig_entry->next;
+        }
+        *new_entry = NULL;
+    }
+    return ht;
+}
+
+APR_DECLARE(void *) apr_hash_get(apr_hash_t *ht,
+                                 const void *key,
+                                 apr_ssize_t klen)
+{
+    apr_hash_entry_t *he;
+    he = *find_entry(ht, key, klen, NULL);
+    if (he)
+        return (void *)he->val;
+    else
+        return NULL;
+}
+
+APR_DECLARE(void) apr_hash_set(apr_hash_t *ht,
+                               const void *key,
+                               apr_ssize_t klen,
+                               const void *val)
+{
+    apr_hash_entry_t **hep;
+    hep = find_entry(ht, key, klen, val);
+    if (*hep) {
+        if (!val) {
+            /* delete entry */
+            apr_hash_entry_t *old = *hep;
+            *hep = (*hep)->next;
+            old->next = ht->free;
+            ht->free = old;
+            --ht->count;
+        }
+        else {
+            /* replace entry */
+            (*hep)->val = val;
+            /* check that the collision rate isn't too high */
+            if (ht->count > ht->max) {
+                expand_array(ht);
+            }
+        }
+    }
+    /* else key not present and val==NULL */
+}
+
+APR_DECLARE(unsigned int) apr_hash_count(apr_hash_t *ht)
+{
+    return ht->count;
+}
+
+APR_DECLARE(void) apr_hash_clear(apr_hash_t *ht)
+{
+    apr_hash_index_t *hi;
+    for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi))
+        apr_hash_set(ht, hi->this->key, hi->this->klen, NULL);
+}
+
+APR_DECLARE(apr_hash_t*) apr_hash_overlay(apr_pool_t *p,
+                                          const apr_hash_t *overlay,
+                                          const apr_hash_t *base)
+{
+    return apr_hash_merge(p, overlay, base, NULL, NULL);
+}
+
+APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
+                                         const apr_hash_t *overlay,
+                                         const apr_hash_t *base,
+                                         void * (*merger)(apr_pool_t *p,
+                                                     const void *key,
+                                                     apr_ssize_t klen,
+                                                     const void *h1_val,
+                                                     const void *h2_val,
+                                                     const void *data),
+                                         const void *data)
+{
+    apr_hash_t *res;
+    apr_hash_entry_t *new_vals = NULL;
+    apr_hash_entry_t *iter;
+    apr_hash_entry_t *ent;
+    unsigned int i, j, k, hash;
+
+#if APR_POOL_DEBUG
+    /* we don't copy keys and values, so it's necessary that
+     * overlay->a.pool and base->a.pool have a life span at least
+     * as long as p
+     */
+    if (!apr_pool_is_ancestor(overlay->pool, p)) {
+        fprintf(stderr,
+                "apr_hash_merge: overlay's pool is not an ancestor of p\n");
+        abort();
+    }
+    if (!apr_pool_is_ancestor(base->pool, p)) {
+        fprintf(stderr,
+                "apr_hash_merge: base's pool is not an ancestor of p\n");
+        abort();
+    }
+#endif
+
+    res = apr_palloc(p, sizeof(apr_hash_t));
+    res->pool = p;
+    res->free = NULL;
+    res->hash_func = base->hash_func;
+    res->count = base->count;
+    res->max = (overlay->max > base->max) ? overlay->max : base->max;
+    if (base->count + overlay->count > res->max) {
+        res->max = res->max * 2 + 1;
+    }
+    res->seed = base->seed;
+    res->array = alloc_array(res, res->max);
+    if (base->count + overlay->count) {
+        new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *
+                              (base->count + overlay->count));
+    }
+    j = 0;
+    for (k = 0; k <= base->max; k++) {
+        for (iter = base->array[k]; iter; iter = iter->next) {
+            i = iter->hash & res->max;
+            new_vals[j].klen = iter->klen;
+            new_vals[j].key = iter->key;
+            new_vals[j].val = iter->val;
+            new_vals[j].hash = iter->hash;
+            new_vals[j].next = res->array[i];
+            res->array[i] = &new_vals[j];
+            j++;
+        }
+    }
+
+    for (k = 0; k <= overlay->max; k++) {
+        for (iter = overlay->array[k]; iter; iter = iter->next) {
+            if (res->hash_func)
+                hash = res->hash_func(iter->key, &iter->klen);
+            else
+                hash = hashfunc_default(iter->key, &iter->klen, res->seed);
+            i = hash & res->max;
+            for (ent = res->array[i]; ent; ent = ent->next) {
+                if ((ent->klen == iter->klen) &&
+                    (memcmp(ent->key, iter->key, iter->klen) == 0)) {
+                    if (merger) {
+                        ent->val = (*merger)(p, iter->key, iter->klen,
+                                             iter->val, ent->val, data);
+                    }
+                    else {
+                        ent->val = iter->val;
+                    }
+                    break;
+                }
+            }
+            if (!ent) {
+                new_vals[j].klen = iter->klen;
+                new_vals[j].key = iter->key;
+                new_vals[j].val = iter->val;
+                new_vals[j].hash = hash;
+                new_vals[j].next = res->array[i];
+                res->array[i] = &new_vals[j];
+                res->count++;
+                j++;
+            }
+        }
+    }
+    return res;
+}
+
+/* This is basically the following...
+ * for every element in hash table {
+ *    comp elemeny.key, element.value
+ * }
+ *
+ * Like with apr_table_do, the comp callback is called for each and every
+ * element of the hash table.
+ */
+APR_DECLARE(int) apr_hash_do(apr_hash_do_callback_fn_t *comp,
+                             void *rec, const apr_hash_t *ht)
+{
+    apr_hash_index_t  hix;
+    apr_hash_index_t *hi;
+    int rv, dorv  = 1;
+
+    hix.ht    = (apr_hash_t *)ht;
+    hix.index = 0;
+    hix.this  = NULL;
+    hix.next  = NULL;
+
+    if ((hi = apr_hash_next(&hix))) {
+        /* Scan the entire table */
+        do {
+            rv = (*comp)(rec, hi->this->key, hi->this->klen, hi->this->val);
+        } while (rv && (hi = apr_hash_next(hi)));
+
+        if (rv == 0) {
+            dorv = 0;
+        }
+    }
+    return dorv;
+}
+
+APR_POOL_IMPLEMENT_ACCESSOR(hash)
diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c
new file mode 100644
index 0000000..8013ed7
--- /dev/null
+++ b/tables/apr_skiplist.c
@@ -0,0 +1,864 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * Modified to use APR and APR pools.
+ *  TODO: Is malloc() better? Will long running skiplists grow too much?
+ *  Keep the skiplist_alloc() and skiplist_free() until we know
+ *  Yeah, if using pools it means some bogus cycles for checks
+ *  (and an useless function call for skiplist_free) which we
+ *  can removed if/when needed.
+ */
+
+#include "apr_skiplist.h"
+
+typedef struct {
+    apr_skiplistnode **data;
+    size_t size, pos;
+    apr_pool_t *p;
+} apr_skiplist_q; 
+
+struct apr_skiplist {
+    apr_skiplist_compare compare;
+    apr_skiplist_compare comparek;
+    int height;
+    int preheight;
+    size_t size;
+    apr_skiplistnode *top;
+    apr_skiplistnode *bottom;
+    /* These two are needed for appending */
+    apr_skiplistnode *topend;
+    apr_skiplistnode *bottomend;
+    apr_skiplist *index;
+    apr_array_header_t *memlist;
+    apr_skiplist_q nodes_q,
+                   stack_q;
+    apr_pool_t *pool;
+};
+
+struct apr_skiplistnode {
+    void *data;
+    apr_skiplistnode *next;
+    apr_skiplistnode *prev;
+    apr_skiplistnode *down;
+    apr_skiplistnode *up;
+    apr_skiplistnode *previndex;
+    apr_skiplistnode *nextindex;
+    apr_skiplist *sl;
+};
+
+static unsigned int get_b_rand(void)
+{
+    static unsigned int ph = 32;         /* More bits than we will ever use */
+    static unsigned int randseq;
+    if (ph > 31) {              /* Num bits in return of rand() */
+        ph = 0;
+        randseq = rand();
+    }
+    return randseq & (1U << ph++);
+}
+
+typedef struct {
+    size_t size;
+    apr_array_header_t *list;
+} memlist_t;
+
+typedef struct {
+    void *ptr;
+    char inuse;
+} chunk_t;
+
+APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size)
+{
+    if (sl->pool) {
+        void *ptr;
+        int found_size = 0;
+        int i;
+        chunk_t *newchunk;
+        memlist_t *memlist = (memlist_t *)sl->memlist->elts;
+        for (i = 0; i < sl->memlist->nelts; i++) {
+            if (memlist->size == size) {
+                int j;
+                chunk_t *chunk = (chunk_t *)memlist->list->elts;
+                found_size = 1;
+                for (j = 0; j < memlist->list->nelts; j++) {
+                    if (!chunk->inuse) {
+                        chunk->inuse = 1;
+                        return chunk->ptr;
+                    }
+                    chunk++;
+                }
+                break; /* no free of this size; punt */
+            }
+            memlist++;
+        }
+        /* no free chunks */
+        ptr = apr_palloc(sl->pool, size);
+        if (!ptr) {
+            return ptr;
+        }
+        /*
+         * is this a new sized chunk? If so, we need to create a new
+         * array of them. Otherwise, re-use what we already have.
+         */
+        if (!found_size) {
+            memlist = apr_array_push(sl->memlist);
+            memlist->size = size;
+            memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t));
+        }
+        newchunk = apr_array_push(memlist->list);
+        newchunk->ptr = ptr;
+        newchunk->inuse = 1;
+        return ptr;
+    }
+    else {
+        return malloc(size);
+    }
+}
+
+APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem)
+{
+    if (!sl->pool) {
+        free(mem);
+    }
+    else {
+        int i;
+        memlist_t *memlist = (memlist_t *)sl->memlist->elts;
+        for (i = 0; i < sl->memlist->nelts; i++) {
+            int j;
+            chunk_t *chunk = (chunk_t *)memlist->list->elts;
+            for (j = 0; j < memlist->list->nelts; j++) {
+                if (chunk->ptr == mem) {
+                    chunk->inuse = 0;
+                    return;
+                }
+                chunk++;
+            }
+            memlist++;
+        }
+    }
+}
+
+static apr_status_t skiplist_qpush(apr_skiplist_q *q, apr_skiplistnode *m)
+{
+    if (q->pos >= q->size) {
+        apr_skiplistnode **data;
+        size_t size = (q->pos) ? q->pos * 2 : 32;
+        if (q->p) {
+            data = apr_palloc(q->p, size * sizeof(*data));
+            if (data && q->data) {
+                memcpy(data, q->data, q->pos * sizeof(*data));
+            }
+        }
+        else {
+            data = realloc(q->data, size * sizeof(*data));
+        }
+        if (!data) {
+            return APR_ENOMEM;
+        }
+        q->data = data;
+        q->size = size;
+    }
+    q->data[q->pos++] = m;
+    return APR_SUCCESS;
+}
+
+static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
+{
+    return (q->pos > 0) ? q->data[--q->pos] : NULL;
+}
+
+static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
+{
+    q->pos = 0;
+}
+
+static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl)
+{
+    apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q);
+    if (!m) {
+        if (sl->pool) {
+            m = apr_palloc(sl->pool, sizeof *m);
+        }
+        else {
+            m = malloc(sizeof *m);
+        }
+    }
+    return m;
+}
+
+static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m)
+{
+    return skiplist_qpush(&sl->nodes_q, m);
+}
+
+static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
+{
+    apr_skiplist *sl;
+    if (p) {
+        sl = apr_pcalloc(p, sizeof(apr_skiplist));
+        sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
+        sl->pool = sl->nodes_q.p = sl->stack_q.p = p;
+    }
+    else {
+        sl = calloc(1, sizeof(apr_skiplist));
+        if (!sl) {
+            return APR_ENOMEM;
+        }
+    }
+    *s = sl;
+    return APR_SUCCESS;
+}
+
+static int indexing_comp(void *a, void *b)
+{
+    void *ac = (void *) (((apr_skiplist *) a)->compare);
+    void *bc = (void *) (((apr_skiplist *) b)->compare);
+    return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
+}
+
+static int indexing_compk(void *ac, void *b)
+{
+    void *bc = (void *) (((apr_skiplist *) b)->compare);
+    return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
+}
+
+APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
+{
+    apr_status_t rv;
+    apr_skiplist *sl;
+    rv = skiplisti_init(&sl, p);
+    if (rv != APR_SUCCESS) {
+        *s = NULL;
+        return rv;
+    }
+    rv = skiplisti_init(&sl->index, p);
+    if (rv != APR_SUCCESS) {
+        *s = NULL;
+        return rv;
+    }
+    apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
+    *s = sl;
+    return APR_SUCCESS;
+}
+
+APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl,
+                          apr_skiplist_compare comp,
+                          apr_skiplist_compare compk)
+{
+    if (sl->compare && sl->comparek) {
+        apr_skiplist_add_index(sl, comp, compk);
+    }
+    else {
+        sl->compare = comp;
+        sl->comparek = compk;
+    }
+}
+
+APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl,
+                        apr_skiplist_compare comp,
+                        apr_skiplist_compare compk)
+{
+    apr_skiplistnode *m;
+    apr_skiplist *ni;
+    int icount = 0;
+    apr_skiplist_find(sl->index, (void *)comp, &m);
+    if (m) {
+        return;                 /* Index already there! */
+    }
+    if (skiplisti_init(&ni, sl->pool) != APR_SUCCESS) {
+        abort();
+        return;
+    }
+    apr_skiplist_set_compare(ni, comp, compk);
+    /* Build the new index... This can be expensive! */
+    m = apr_skiplist_insert(sl->index, ni);
+    while (m->prev) {
+        m = m->prev;
+        icount++;
+    }
+    for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) {
+        int j = icount - 1;
+        apr_skiplistnode *nsln;
+        nsln = apr_skiplist_insert(ni, m->data);
+        /* skip from main index down list */
+        while (j > 0) {
+            m = m->nextindex;
+            j--;
+        }
+        /* insert this node in the indexlist after m */
+        nsln->nextindex = m->nextindex;
+        if (m->nextindex) {
+            m->nextindex->previndex = nsln;
+        }
+        nsln->previndex = m;
+        m->nextindex = nsln;
+    }
+}
+
+static int skiplisti_find_compare(apr_skiplist *sl, void *data,
+                                  apr_skiplistnode **ret,
+                                  apr_skiplist_compare comp,
+                                  int last)
+{
+    int count = 0;
+    apr_skiplistnode *m, *found = NULL;
+    for (m = sl->top; m; count++) {
+        if (m->next) {
+            int compared = comp(data, m->next->data);
+            if (compared == 0) {
+                found = m = m->next;
+                if (!last) {
+                    break;
+                }
+                continue;
+            }
+            if (compared > 0) {
+                m = m->next;
+                continue;
+            }
+        }
+        m = m->down;
+    }
+    if (found) {
+        while (found->down) {
+            found = found->down;
+        }
+        *ret = found;
+    }
+    else {
+        *ret = NULL;
+    }
+    return count;
+}
+
+static void *find_compare(apr_skiplist *sli, void *data,
+                          apr_skiplistnode **iter,
+                          apr_skiplist_compare comp,
+                          int last)
+{
+    apr_skiplistnode *m;
+    apr_skiplist *sl;
+    if (!comp) {
+        if (iter) {
+            *iter = NULL;
+        }
+        return NULL;
+    }
+    if (comp == sli->compare || !sli->index) {
+        sl = sli;
+    }
+    else {
+        apr_skiplist_find(sli->index, (void *)comp, &m);
+        if (!m) {
+            if (iter) {
+                *iter = NULL;
+            }
+            return NULL;
+        }
+        sl = (apr_skiplist *) m->data;
+    }
+    skiplisti_find_compare(sl, data, &m, sl->comparek, last);
+    if (iter) {
+        *iter = m;
+    }
+    return (m) ? m->data : NULL;
+}
+
+APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, void *data,
+                                              apr_skiplistnode **iter,
+                                              apr_skiplist_compare comp)
+{
+    return find_compare(sl, data, iter, comp, 0);
+}
+
+APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
+{
+    return find_compare(sl, data, iter, sl->compare, 0);
+}
+
+APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data,
+                                              apr_skiplistnode **iter,
+                                              apr_skiplist_compare comp)
+{
+    return find_compare(sl, data, iter, comp, 1);
+}
+
+APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data,
+                                      apr_skiplistnode **iter)
+{
+    return find_compare(sl, data, iter, sl->compare, 1);
+}
+
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
+{
+    if (!sl->bottom) {
+        return NULL;
+    }
+    return sl->bottom->next;
+}
+
+APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
+{
+    if (!*iter) {
+        return NULL;
+    }
+    *iter = (*iter)->next;
+    return (*iter) ? ((*iter)->data) : NULL;
+}
+
+APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
+{
+    if (!*iter) {
+        return NULL;
+    }
+    *iter = (*iter)->prev;
+    return (*iter) ? ((*iter)->data) : NULL;
+}
+
+APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter)
+{
+    return (iter) ? iter->data : NULL;
+}
+
+/* forward declared */
+static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
+                            apr_skiplist_freefunc myfree);
+
+static APR_INLINE int skiplist_height(const apr_skiplist *sl)
+{
+    /* Skiplists (even empty) always have a top node, although this
+     * implementation defers its creation until the first insert, or
+     * deletes it with the last remove. We want the real height here.
+     */
+    return sl->height ? sl->height : 1;
+}
+
+static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
+                                        apr_skiplist_compare comp, int add,
+                                        apr_skiplist_freefunc myfree)
+{
+    apr_skiplistnode *m, *p, *tmp, *ret = NULL;
+    int ch, top_nh, nh = 1;
+
+    ch = skiplist_height(sl);
+    if (sl->preheight) {
+        while (nh < sl->preheight && get_b_rand()) {
+            nh++;
+        }
+    }
+    else {
+        while (nh <= ch && get_b_rand()) {
+            nh++;
+        }
+    }
+    top_nh = nh;
+
+    /* Now we have in nh the height at which we wish to insert our new node,
+     * and in ch the current height: don't create skip paths to the inserted
+     * element until the walk down through the tree (which decrements ch)
+     * reaches nh. From there, any walk down pushes the current node on a
+     * stack (the node(s) after which we would insert) to pop back through
+     * for insertion later.
+     */
+    m = sl->top;
+    while (m) {
+        /*
+         * To maintain stability, dups (compared == 0) must be added
+         * AFTER each other.
+         */
+        if (m->next) {
+            int compared = comp(data, m->next->data);
+            if (compared == 0) {
+                if (!add) {
+                    /* Keep the existing element(s) */
+                    skiplist_qclear(&sl->stack_q);
+                    return NULL;
+                }
+                if (add < 0) {
+                    /* Remove this element and continue with the next node
+                     * or the new top if the current one is also removed.
+                     */
+                    apr_skiplistnode *top = sl->top;
+                    skiplisti_remove(sl, m->next, myfree);
+                    if (top != sl->top) {
+                        m = sl->top;
+                        skiplist_qclear(&sl->stack_q);
+                        ch = skiplist_height(sl);
+                        nh = top_nh;
+                    }
+                    continue;
+                }
+            }
+            if (compared >= 0) {
+                m = m->next;
+                continue;
+            }
+        }
+        if (ch <= nh) {
+            /* push on stack */
+            skiplist_qpush(&sl->stack_q, m);
+        }
+        m = m->down;
+        ch--;
+    }
+    /* Pop the stack and insert nodes */
+    p = NULL;
+    while ((m = skiplist_qpop(&sl->stack_q))) {
+        tmp = skiplist_new_node(sl);
+        tmp->next = m->next;
+        if (m->next) {
+            m->next->prev = tmp;
+        }
+        m->next = tmp;
+        tmp->prev = m;
+        tmp->up = NULL;
+        tmp->nextindex = tmp->previndex = NULL;
+        tmp->down = p;
+        if (p) {
+            p->up = tmp;
+        }
+        else {
+            /* This sets ret to the bottom-most node we are inserting */
+            ret = tmp;
+        }
+        tmp->data = data;
+        tmp->sl = sl;
+        p = tmp;
+    }
+
+    /* Now we are sure the node is inserted, grow our tree to 'nh' tall */
+    for (; sl->height < nh; sl->height++) {
+        m = skiplist_new_node(sl);
+        tmp = skiplist_new_node(sl);
+        m->up = m->prev = m->nextindex = m->previndex = NULL;
+        m->next = tmp;
+        m->down = sl->top;
+        m->data = NULL;
+        m->sl = sl;
+        if (sl->top) {
+            sl->top->up = m;
+        }
+        else {
+            sl->bottom = sl->bottomend = m;
+        }
+        sl->top = sl->topend = tmp->prev = m;
+        tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
+        tmp->down = p;
+        tmp->data = data;
+        tmp->sl = sl;
+        if (p) {
+            p->up = tmp;
+        }
+        else {
+            /* This sets ret to the bottom-most node we are inserting */
+            ret = tmp;
+        }
+        p = tmp;
+    }
+    if (sl->index != NULL) {
+        /*
+         * this is a external insertion, we must insert into each index as
+         * well
+         */
+        apr_skiplistnode *ni, *li;
+        li = ret;
+        for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
+            apr_skiplist *sli = (apr_skiplist *)p->data;
+            ni = insert_compare(sli, ret->data, sli->compare, 1, NULL);
+            li->nextindex = ni;
+            ni->previndex = li;
+            li = ni;
+        }
+    }
+    sl->size++;
+    return ret;
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
+                                      apr_skiplist_compare comp)
+{
+    if (!comp) {
+        return NULL;
+    }
+    return insert_compare(sl, data, comp, 0, NULL);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
+{
+    return apr_skiplist_insert_compare(sl, data, sl->compare);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void *data,
+                                      apr_skiplist_compare comp)
+{
+    if (!comp) {
+        return NULL;
+    }
+    return insert_compare(sl, data, comp, 1, NULL);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
+{
+    return apr_skiplist_add_compare(sl, data, sl->compare);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
+                                    void *data, apr_skiplist_freefunc myfree,
+                                    apr_skiplist_compare comp)
+{
+    if (!comp) {
+        return NULL;
+    }
+    return insert_compare(sl, data, comp, -1, myfree);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
+                                    void *data, apr_skiplist_freefunc myfree)
+{
+    return apr_skiplist_replace_compare(sl, data, myfree, sl->compare);
+}
+
+#if 0
+void skiplist_print_struct(apr_skiplist * sl, char *prefix)
+{
+    apr_skiplistnode *p, *q;
+    fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
+    p = sl->bottom;
+    while (p) {
+        q = p;
+        fprintf(stderr, prefix);
+        while (q) {
+            fprintf(stderr, "%p ", q->data);
+            q = q->up;
+        }
+        fprintf(stderr, "\n");
+        p = p->next;
+    }
+}
+#endif
+
+static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
+                            apr_skiplist_freefunc myfree)
+{
+    apr_skiplistnode *p;
+    if (!m) {
+        return 0;
+    }
+    if (m->nextindex) {
+        skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
+    }
+    while (m->up) {
+        m = m->up;
+    }
+    do {
+        p = m;
+        /* take me out of the list */
+        p->prev->next = p->next;
+        if (p->next) {
+            p->next->prev = p->prev;
+        }
+        m = m->down;
+        /* This only frees the actual data in the bottom one */
+        if (!m && myfree && p->data) {
+            myfree(p->data);
+        }
+        skiplist_put_node(sl, p);
+    } while (m);
+    sl->size--;
+    while (sl->top && sl->top->next == NULL) {
+        /* While the row is empty and we are not on the bottom row */
+        p = sl->top;
+        sl->top = sl->top->down;/* Move top down one */
+        if (sl->top) {
+            sl->top->up = NULL; /* Make it think its the top */
+        }
+        skiplist_put_node(sl, p);
+        sl->height--;
+    }
+    if (!sl->top) {
+        sl->bottom = sl->bottomend = NULL;
+        sl->topend = NULL;
+    }
+    return skiplist_height(sl);
+}
+
+APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
+                                          apr_skiplistnode *iter,
+                                          apr_skiplist_freefunc myfree)
+{
+    apr_skiplistnode *m = iter;
+    if (!m) {
+        return 0;
+    }
+    while (m->down) {
+        m = m->down;
+    }
+    while (m->previndex) {
+        m = m->previndex;
+    }
+    return skiplisti_remove(sl, m, myfree);
+}
+
+APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
+                            void *data,
+                            apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
+{
+    apr_skiplistnode *m;
+    apr_skiplist *sl;
+    if (!comp) {
+        return 0;
+    }
+    if (comp == sli->comparek || !sli->index) {
+        sl = sli;
+    }
+    else {
+        apr_skiplist_find(sli->index, (void *)comp, &m);
+        if (!m) {
+            return 0;
+        }
+        sl = (apr_skiplist *) m->data;
+    }
+    skiplisti_find_compare(sl, data, &m, comp, 0);
+    if (!m) {
+        return 0;
+    }
+    while (m->previndex) {
+        m = m->previndex;
+    }
+    return skiplisti_remove(sl, m, myfree);
+}
+
+APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
+{
+    return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
+}
+
+APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
+{
+    /*
+     * This must remove even the place holder nodes (bottom though top)
+     * because we specify in the API that one can free the Skiplist after
+     * making this call without memory leaks
+     */
+    apr_skiplistnode *m, *p, *u;
+    m = sl->bottom;
+    while (m) {
+        p = m->next;
+        if (myfree && p && p->data) {
+            myfree(p->data);
+        }
+        do {
+            u = m->up;
+            skiplist_put_node(sl, m);
+            m = u;
+        } while (m);
+        m = p;
+    }
+    sl->top = sl->bottom = NULL;
+    sl->topend = sl->bottomend = NULL;
+    sl->height = 0;
+    sl->size = 0;
+}
+
+APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
+{
+    apr_skiplistnode *sln;
+    void *data = NULL;
+    sln = apr_skiplist_getlist(a);
+    if (sln) {
+        data = sln->data;
+        skiplisti_remove(a, sln, myfree);
+    }
+    return data;
+}
+
+APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
+{
+    apr_skiplistnode *sln;
+    sln = apr_skiplist_getlist(a);
+    if (sln) {
+        return sln->data;
+    }
+    return NULL;
+}
+
+APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
+{
+    return sl->size;
+}
+
+APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
+{
+    return skiplist_height(sl);
+}
+
+APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
+{
+    return sl->preheight;
+}
+
+APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to)
+{
+    sl->preheight = (to > 0) ? to : 0;
+}
+
+static void skiplisti_destroy(void *vsl)
+{
+    apr_skiplist_destroy(vsl, NULL);
+}
+
+APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
+{
+    while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
+        ;
+    apr_skiplist_remove_all(sl, myfree);
+    if (!sl->pool) {
+        while (sl->nodes_q.pos)
+            free(sl->nodes_q.data[--sl->nodes_q.pos]);
+        free(sl->nodes_q.data);
+        free(sl->stack_q.data);
+        free(sl);
+    }
+}
+
+APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
+{
+    /* Check integrity! */
+    apr_skiplist temp;
+    struct apr_skiplistnode *b2;
+    if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
+        apr_skiplist_remove_all(sl1, NULL);
+        temp = *sl1;
+        *sl1 = *sl2;
+        *sl2 = temp;
+        /* swap them so that sl2 can be freed normally upon return. */
+        return sl1;
+    }
+    if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
+        apr_skiplist_remove_all(sl2, NULL);
+        return sl1;
+    }
+    /* This is what makes it brute force... Just insert :/ */
+    b2 = apr_skiplist_getlist(sl2);
+    while (b2) {
+        apr_skiplist_insert(sl1, b2->data);
+        apr_skiplist_next(sl2, &b2);
+    }
+    apr_skiplist_remove_all(sl2, NULL);
+    return sl1;
+}
diff --git a/tables/apr_tables.c b/tables/apr_tables.c
new file mode 100644
index 0000000..9dc594c
--- /dev/null
+++ b/tables/apr_tables.c
@@ -0,0 +1,1300 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * Resource allocation code... the code here is responsible for making
+ * sure that nothing leaks.
+ *
+ * rst --- 4/95 --- 6/95
+ */
+
+#include "apr_private.h"
+
+#include "apr_general.h"
+#include "apr_pools.h"
+#include "apr_tables.h"
+#include "apr_strings.h"
+#include "apr_lib.h"
+#if APR_HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if APR_HAVE_STRING_H
+#include <string.h>
+#endif
+#if APR_HAVE_STRINGS_H
+#include <strings.h>
+#endif
+
+#if (APR_POOL_DEBUG || defined(MAKE_TABLE_PROFILE)) && APR_HAVE_STDIO_H
+#include <stdio.h>
+#endif
+
+/*****************************************************************
+ * This file contains array and apr_table_t functions only.
+ */
+
+/*****************************************************************
+ *
+ * The 'array' functions...
+ */
+
+static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
+			    int nelts, int elt_size, int clear)
+{
+    /*
+     * Assure sanity if someone asks for
+     * array of zero elts.
+     */
+    if (nelts < 1) {
+        nelts = 1;
+    }
+
+    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;
+    res->nelts = 0;		/* No active elements yet... */
+    res->nalloc = nelts;	/* ...but this many allocated */
+}
+
+APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
+{
+    return ((a == NULL) || (a->nelts == 0));
+}
+
+APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
+						int nelts, int elt_size)
+{
+    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, 1);
+    return res;
+}
+
+APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
+{
+    arr->nelts = 0;
+}
+
+APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
+{
+    if (apr_is_empty_array(arr)) {
+        return NULL;
+    }
+   
+    return arr->elts + (arr->elt_size * (--arr->nelts));
+}
+
+APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
+{
+    if (arr->nelts == arr->nalloc) {
+        int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
+        char *new_data;
+
+        new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
+
+        memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
+        memset(new_data + arr->nalloc * arr->elt_size, 0,
+               arr->elt_size * (new_size - arr->nalloc));
+        arr->elts = new_data;
+        arr->nalloc = new_size;
+    }
+
+    ++arr->nelts;
+    return arr->elts + (arr->elt_size * (arr->nelts - 1));
+}
+
+static void *apr_array_push_noclear(apr_array_header_t *arr)
+{
+    if (arr->nelts == arr->nalloc) {
+        int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
+        char *new_data;
+
+        new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
+
+        memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
+        arr->elts = new_data;
+        arr->nalloc = new_size;
+    }
+
+    ++arr->nelts;
+    return arr->elts + (arr->elt_size * (arr->nelts - 1));
+}
+
+APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
+			       const apr_array_header_t *src)
+{
+    int elt_size = dst->elt_size;
+
+    if (dst->nelts + src->nelts > dst->nalloc) {
+	int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
+	char *new_data;
+
+	while (dst->nelts + src->nelts > new_size) {
+	    new_size *= 2;
+	}
+
+	new_data = apr_pcalloc(dst->pool, elt_size * new_size);
+	memcpy(new_data, dst->elts, dst->nalloc * elt_size);
+
+	dst->elts = new_data;
+	dst->nalloc = new_size;
+    }
+
+    memcpy(dst->elts + dst->nelts * elt_size, src->elts,
+	   elt_size * src->nelts);
+    dst->nelts += src->nelts;
+}
+
+APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
+						const apr_array_header_t *arr)
+{
+    apr_array_header_t *res =
+        (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
+    make_array_core(res, p, arr->nalloc, arr->elt_size, 0);
+
+    memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
+    res->nelts = arr->nelts;
+    memset(res->elts + res->elt_size * res->nelts, 0,
+           res->elt_size * (res->nalloc - res->nelts));
+    return res;
+}
+
+/* This cute function copies the array header *only*, but arranges
+ * for the data section to be copied on the first push or arraycat.
+ * It's useful when the elements of the array being copied are
+ * read only, but new stuff *might* get added on the end; we have the
+ * overhead of the full copy only where it is really needed.
+ */
+
+static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
+					   const apr_array_header_t *arr)
+{
+    res->elts = arr->elts;
+    res->elt_size = arr->elt_size;
+    res->nelts = arr->nelts;
+    res->nalloc = arr->nelts;	/* Force overflow on push */
+}
+
+APR_DECLARE(apr_array_header_t *)
+    apr_array_copy_hdr(apr_pool_t *p,
+		       const apr_array_header_t *arr)
+{
+    apr_array_header_t *res;
+
+    res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
+    res->pool = p;
+    copy_array_hdr_core(res, arr);
+    return res;
+}
+
+/* The above is used here to avoid consing multiple new array bodies... */
+
+APR_DECLARE(apr_array_header_t *)
+    apr_array_append(apr_pool_t *p,
+		      const apr_array_header_t *first,
+		      const apr_array_header_t *second)
+{
+    apr_array_header_t *res = apr_array_copy_hdr(p, first);
+
+    apr_array_cat(res, second);
+    return res;
+}
+
+/* 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,
+ * or if there are no elements in the array.
+ * If sep is non-NUL, it will be inserted between elements as a separator.
+ */
+APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
+				     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;
+}
+
+
+/*****************************************************************
+ *
+ * The "table" functions.
+ */
+
+#if APR_CHARSET_EBCDIC
+#define CASE_MASK 0xbfbfbfbf
+#else
+#define CASE_MASK 0xdfdfdfdf
+#endif
+
+#define TABLE_HASH_SIZE 32
+#define TABLE_INDEX_MASK 0x1f
+#define TABLE_HASH(key)  (TABLE_INDEX_MASK & *(unsigned char *)(key))
+#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1u << (i)))
+#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1u << (i)))
+
+/* 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;                     \
+}
+
+/** The opaque string-content table type */
+struct apr_table_t {
+    /* This has to be first to promote backwards compatibility with
+     * older modules which cast a apr_table_t * to an apr_array_header_t *...
+     * they should use the apr_table_elts() function for most of the
+     * cases they do this for.
+     */
+    /** The underlying array for the table */
+    apr_array_header_t a;
+#ifdef MAKE_TABLE_PROFILE
+    /** Who created the array. */
+    void *creator;
+#endif
+    /* An index to speed up table lookups.  The way this works is:
+     *   - Hash the key into the index:
+     *     - index_first[TABLE_HASH(key)] is the offset within
+     *       the table of the first entry with that key
+     *     - index_last[TABLE_HASH(key)] is the offset within
+     *       the table of the last entry with that key
+     *   - If (and only if) there is no entry in the table whose
+     *     key hashes to index element i, then the i'th bit
+     *     of index_initialized will be zero.  (Check this before
+     *     trying to use index_first[i] or index_last[i]!)
+     */
+    apr_uint32_t index_initialized;
+    int index_first[TABLE_HASH_SIZE];
+    int index_last[TABLE_HASH_SIZE];
+};
+
+/* keep state for apr_table_getm() */
+typedef struct
+{
+    apr_pool_t *p;
+    const char *first;
+    apr_array_header_t *merged;
+} table_getm_t;
+
+/*
+ * NOTICE: if you tweak this you should look at is_empty_table() 
+ * and table_elts() in alloc.h
+ */
+#ifdef MAKE_TABLE_PROFILE
+static apr_table_entry_t *do_table_push(const char *func, apr_table_t *t)
+{
+    if (t->a.nelts == t->a.nalloc) {
+        fprintf(stderr, "%s: table created by %p hit limit of %u\n",
+                func ? func : "table_push", t->creator, t->a.nalloc);
+    }
+    return (apr_table_entry_t *) apr_array_push_noclear(&t->a);
+}
+#if defined(__GNUC__) && __GNUC__ >= 2
+#define table_push(t) do_table_push(__FUNCTION__, t)
+#else
+#define table_push(t) do_table_push(NULL, t)
+#endif
+#else /* MAKE_TABLE_PROFILE */
+#define table_push(t)	((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
+#endif /* MAKE_TABLE_PROFILE */
+
+APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
+{
+    return (const apr_array_header_t *)t;
+}
+
+APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
+{
+    return ((t == NULL) || (t->a.nelts == 0));
+}
+
+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));
+
+    make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);
+#ifdef MAKE_TABLE_PROFILE
+    t->creator = __builtin_return_address(0);
+#endif
+    t->index_initialized = 0;
+    return t;
+}
+
+APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
+{
+    apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));
+
+#if APR_POOL_DEBUG
+    /* we don't copy keys and values, so it's necessary that t->a.pool
+     * have a life span at least as long as p
+     */
+    if (!apr_pool_is_ancestor(t->a.pool, p)) {
+	fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n");
+	abort();
+    }
+#endif
+    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;
+    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_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t)
+{
+    const apr_array_header_t *array = apr_table_elts(t);
+    apr_table_entry_t *elts = (apr_table_entry_t *) array->elts;
+    apr_table_t *new = apr_table_make(p, array->nelts);
+    int i;
+
+    for (i = 0; i < array->nelts; i++) {
+        apr_table_add(new, elts[i].key, elts[i].val);
+    }
+
+    return new;
+}
+
+static void table_reindex(apr_table_t *t)
+{
+    int i;
+    int hash;
+    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
+
+    t->index_initialized = 0;
+    for (i = 0; i < t->a.nelts; i++, next_elt++) {
+        hash = TABLE_HASH(next_elt->key);
+        t->index_last[hash] = i;
+        if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+            t->index_first[hash] = i;
+            TABLE_SET_INDEX_INITIALIZED(t, hash);
+        }
+    }
+}
+
+APR_DECLARE(void) apr_table_clear(apr_table_t *t)
+{
+    t->a.nelts = 0;
+    t->index_initialized = 0;
+}
+
+APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
+{
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
+    apr_uint32_t checksum;
+    int hash;
+
+    if (key == NULL) {
+	return NULL;
+    }
+
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        return NULL;
+    }
+    COMPUTE_KEY_CHECKSUM(key, checksum);
+    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];
+
+    for (; next_elt <= end_elt; next_elt++) {
+	if ((checksum == next_elt->key_checksum) &&
+            !strcasecmp(next_elt->key, key)) {
+	    return next_elt->val;
+	}
+    }
+
+    return NULL;
+}
+
+APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
+                                const char *val)
+{
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
+    apr_table_entry_t *table_end;
+    apr_uint32_t checksum;
+    int hash;
+
+    COMPUTE_KEY_CHECKSUM(key, checksum);
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
+    }
+    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)) {
+
+            /* Found an existing entry with the same key, so overwrite it */
+
+            int must_reindex = 0;
+            apr_table_entry_t *dst_elt = NULL;
+
+            next_elt->val = apr_pstrdup(t->a.pool, 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--;
+                    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);
+            }
+            return;
+        }
+    }
+
+add_new_elt:
+    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->key_checksum = checksum;
+}
+
+APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
+                                 const char *val)
+{
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
+    apr_table_entry_t *table_end;
+    apr_uint32_t checksum;
+    int hash;
+
+    COMPUTE_KEY_CHECKSUM(key, checksum);
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
+    }
+    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)) {
+
+            /* Found an existing entry with the same key, so overwrite it */
+
+            int must_reindex = 0;
+            apr_table_entry_t *dst_elt = NULL;
+
+            next_elt->val = (char *)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--;
+                    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);
+            }
+            return;
+        }
+    }
+
+add_new_elt:
+    t->index_last[hash] = t->a.nelts;
+    next_elt = (apr_table_entry_t *) table_push(t);
+    next_elt->key = (char *)key;
+    next_elt->val = (char *)val;
+    next_elt->key_checksum = checksum;
+}
+
+APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
+{
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
+    apr_table_entry_t *dst_elt;
+    apr_uint32_t checksum;
+    int hash;
+    int must_reindex;
+
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        return;
+    }
+    COMPUTE_KEY_CHECKSUM(key, checksum);
+    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];
+    must_reindex = 0;
+    for (; next_elt <= end_elt; next_elt++) {
+	if ((checksum == next_elt->key_checksum) &&
+            !strcasecmp(next_elt->key, key)) {
+
+            /* Found a match: remove this entry, plus any additional
+             * matches for the same key that might follow
+             */
+            apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
+                t->a.nelts;
+            t->a.nelts--;
+            dst_elt = next_elt;
+            for (next_elt++; next_elt <= end_elt; next_elt++) {
+                if ((checksum == next_elt->key_checksum) &&
+                    !strcasecmp(next_elt->key, key)) {
+                    t->a.nelts--;
+                }
+                else {
+                    *dst_elt++ = *next_elt;
+                }
+            }
+
+            /* 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)
+             */
+            for (; next_elt < table_end; next_elt++) {
+                *dst_elt++ = *next_elt;
+            }
+            must_reindex = 1;
+            break;
+        }
+    }
+    if (must_reindex) {
+        table_reindex(t);
+    }
+}
+
+APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
+				 const char *val)
+{
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
+    apr_uint32_t checksum;
+    int hash;
+
+    COMPUTE_KEY_CHECKSUM(key, checksum);
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
+    }
+    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];
+
+    for (; next_elt <= end_elt; next_elt++) {
+	if ((checksum == next_elt->key_checksum) &&
+            !strcasecmp(next_elt->key, key)) {
+
+            /* 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);
+            return;
+        }
+    }
+
+add_new_elt:
+    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->key_checksum = checksum;
+}
+
+APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
+				  const char *val)
+{
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
+    apr_uint32_t checksum;
+    int hash;
+
+#if APR_POOL_DEBUG
+    {
+	apr_pool_t *pool;
+	pool = apr_pool_find(key);
+	if ((pool != (apr_pool_t *)key)
+            && (!apr_pool_is_ancestor(pool, t->a.pool))) {
+	    fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
+	    abort();
+	}
+	pool = apr_pool_find(val);
+	if ((pool != (apr_pool_t *)val)
+            && (!apr_pool_is_ancestor(pool, t->a.pool))) {
+	    fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n");
+	    abort();
+	}
+    }
+#endif
+
+    COMPUTE_KEY_CHECKSUM(key, checksum);
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
+    }
+    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];
+
+    for (; next_elt <= end_elt; next_elt++) {
+	if ((checksum == next_elt->key_checksum) &&
+            !strcasecmp(next_elt->key, key)) {
+
+            /* 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);
+            return;
+        }
+    }
+
+add_new_elt:
+    t->index_last[hash] = t->a.nelts;
+    next_elt = (apr_table_entry_t *) table_push(t);
+    next_elt->key = (char *)key;
+    next_elt->val = (char *)val;
+    next_elt->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_uint32_t checksum;
+    int hash;
+
+    hash = TABLE_HASH(key);
+    t->index_last[hash] = t->a.nelts;
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+    }
+    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_uint32_t checksum;
+    int hash;
+
+#if APR_POOL_DEBUG
+    {
+	if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
+	    fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
+	    abort();
+	}
+	if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
+	    fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n");
+	    abort();
+	}
+    }
+#endif
+
+    hash = TABLE_HASH(key);
+    t->index_last[hash] = t->a.nelts;
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+    }
+    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,
+					     const apr_table_t *overlay,
+					     const apr_table_t *base)
+{
+    apr_table_t *res;
+
+#if APR_POOL_DEBUG
+    /* we don't copy keys and values, so it's necessary that
+     * overlay->a.pool and base->a.pool have a life span at least
+     * as long as p
+     */
+    if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
+	fprintf(stderr,
+		"apr_table_overlay: overlay's pool is not an ancestor of p\n");
+	abort();
+    }
+    if (!apr_pool_is_ancestor(base->a.pool, p)) {
+	fprintf(stderr,
+		"apr_table_overlay: base's pool is not an ancestor of p\n");
+	abort();
+    }
+#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;
+}
+
+/* And now for something completely abstract ...
+
+ * For each key value given as a vararg:
+ *   run the function pointed to as
+ *     int comp(void *r, char *key, char *value);
+ *   on each valid key-value pair in the apr_table_t t that matches the vararg key,
+ *   or once for every valid key-value pair if the vararg list is empty,
+ *   until the function returns false (0) or we finish the table.
+ *
+ * Note that we restart the traversal for each vararg, which means that
+ * duplicate varargs will result in multiple executions of the function
+ * for each matching key.  Note also that if the vararg list is empty,
+ * only one traversal will be made and will cut short if comp returns 0.
+ *
+ * Note that the table_get and table_merge functions assume that each key in
+ * the apr_table_t is unique (i.e., no multiple entries with the same key).  This
+ * function does not make that assumption, since it (unfortunately) isn't
+ * true for some of Apache's tables.
+ *
+ * Note that rec is simply passed-on to the comp function, so that the
+ * caller can pass additional info for the task.
+ *
+ * ADDENDUM for apr_table_vdo():
+ * 
+ * The caching api will allow a user to walk the header values:
+ *
+ * apr_status_t apr_cache_el_header_walk(apr_cache_el *el, 
+ *    int (*comp)(void *, const char *, const char *), void *rec, ...);
+ *
+ * So it can be ..., however from there I use a  callback that use a va_list:
+ *
+ * apr_status_t (*cache_el_header_walk)(apr_cache_el *el, 
+ *    int (*comp)(void *, const char *, const char *), void *rec, va_list);
+ *
+ * To pass those ...'s on down to the actual module that will handle walking
+ * their headers, in the file case this is actually just an apr_table - and
+ * rather than reimplementing apr_table_do (which IMHO would be bad) I just
+ * called it with the va_list. For mod_shmem_cache I don't need it since I
+ * can't use apr_table's, but mod_file_cache should (though a good hash would
+ * be better, but that's a different issue :). 
+ *
+ * So to make mod_file_cache easier to maintain, it's a good thing
+ */
+APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
+                                     void *rec, const apr_table_t *t, ...)
+{
+    int rv;
+
+    va_list vp;
+    va_start(vp, t);
+    rv = apr_table_vdo(comp, rec, t, vp);
+    va_end(vp);
+
+    return rv;
+} 
+
+/* XXX: do the semantics of this routine make any sense?  Right now,
+ * if the caller passed in a non-empty va_list of keys to search for,
+ * the "early termination" facility only terminates on *that* key; other
+ * keys will continue to process.  Note that this only has any effect
+ * at all if there are multiple entries in the table with the same key,
+ * otherwise the called function can never effectively early-terminate
+ * this function, as the zero return value is effectively ignored.
+ *
+ * Note also that this behavior is at odds with the behavior seen if an
+ * empty va_list is passed in -- in that case, a zero return value terminates
+ * the entire apr_table_vdo (which is what I think should happen in
+ * both cases).
+ *
+ * If nobody objects soon, I'm going to change the order of the nested
+ * loops in this function so that any zero return value from the (*comp)
+ * function will cause a full termination of apr_table_vdo.  I'm hesitant
+ * at the moment because these (funky) semantics have been around for a
+ * very long time, and although Apache doesn't seem to use them at all,
+ * some third-party vendor might.  I can only think of one possible reason
+ * the existing semantics would make any sense, and it's very Apache-centric,
+ * which is this: if (*comp) is looking for matches of a particular
+ * substring in request headers (let's say it's looking for a particular
+ * cookie name in the Set-Cookie headers), then maybe it wants to be
+ * able to stop searching early as soon as it finds that one and move
+ * on to the next key.  That's only an optimization of course, but changing
+ * the behavior of this function would mean that any code that tried
+ * to do that would stop working right.
+ *
+ * Sigh.  --JCW, 06/28/02
+ */
+APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp,
+                               void *rec, const apr_table_t *t, va_list vp)
+{
+    char *argp;
+    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
+    int vdorv = 1;
+
+    argp = va_arg(vp, char *);
+    do {
+        int rv = 1, i;
+        if (argp) {
+            /* Scan for entries that match the next key */
+            int hash = TABLE_HASH(argp);
+            if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+                apr_uint32_t checksum;
+                COMPUTE_KEY_CHECKSUM(argp, checksum);
+                for (i = t->index_first[hash];
+                     rv && (i <= t->index_last[hash]); ++i) {
+                    if (elts[i].key && (checksum == elts[i].key_checksum) &&
+                                        !strcasecmp(elts[i].key, argp)) {
+                        rv = (*comp) (rec, elts[i].key, elts[i].val);
+                    }
+                }
+            }
+        }
+        else {
+            /* Scan the entire table */
+            for (i = 0; rv && (i < t->a.nelts); ++i) {
+                if (elts[i].key) {
+                    rv = (*comp) (rec, elts[i].key, elts[i].val);
+                }
+            }
+        }
+        if (rv == 0) {
+            vdorv = 0;
+        }
+    } while (argp && ((argp = va_arg(vp, char *)) != NULL));
+
+    return vdorv;
+}
+
+static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
+                                           apr_table_entry_t **values, 
+                                           apr_size_t n)
+{
+    /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
+     * in C," chapter 8
+     */
+    apr_table_entry_t **values_tmp =
+        (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
+    apr_size_t i;
+    apr_size_t blocksize;
+
+    /* First pass: sort pairs of elements (blocksize=1) */
+    for (i = 0; i + 1 < n; i += 2) {
+        if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
+            apr_table_entry_t *swap = values[i];
+            values[i] = values[i + 1];
+            values[i + 1] = swap;
+        }
+    }
+
+    /* Merge successively larger blocks */
+    blocksize = 2;
+    while (blocksize < n) {
+        apr_table_entry_t **dst = values_tmp;
+        apr_size_t next_start;
+        apr_table_entry_t **swap;
+
+        /* Merge consecutive pairs blocks of the next blocksize.
+         * Within a block, elements are in sorted order due to
+         * the previous iteration.
+         */
+        for (next_start = 0; next_start + blocksize < n;
+             next_start += (blocksize + blocksize)) {
+
+            apr_size_t block1_start = next_start;
+            apr_size_t block2_start = block1_start + blocksize;
+            apr_size_t block1_end = block2_start;
+            apr_size_t block2_end = block2_start + blocksize;
+            if (block2_end > n) {
+                /* The last block may be smaller than blocksize */
+                block2_end = n;
+            }
+            for (;;) {
+
+                /* Merge the next two blocks:
+                 * Pick the smaller of the next element from
+                 * block 1 and the next element from block 2.
+                 * Once either of the blocks is emptied, copy
+                 * over all the remaining elements from the
+                 * other block
+                 */
+                if (block1_start == block1_end) {
+                    for (; block2_start < block2_end; block2_start++) {
+                        *dst++ = values[block2_start];
+                    }
+                    break;
+                }
+                else if (block2_start == block2_end) {
+                    for (; block1_start < block1_end; block1_start++) {
+                        *dst++ = values[block1_start];
+                    }
+                    break;
+                }
+                if (strcasecmp(values[block1_start]->key,
+                               values[block2_start]->key) > 0) {
+                    *dst++ = values[block2_start++];
+                }
+                else {
+                    *dst++ = values[block1_start++];
+                }
+            }
+        }
+
+        /* If n is not a multiple of 2*blocksize, some elements
+         * will be left over at the end of the array.
+         */
+        for (i = dst - values_tmp; i < n; i++) {
+            values_tmp[i] = values[i];
+        }
+
+        /* The output array of this pass becomes the input
+         * array of the next pass, and vice versa
+         */
+        swap = values_tmp;
+        values_tmp = values;
+        values = swap;
+
+        blocksize += blocksize;
+    }
+
+    return values;
+}
+
+APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
+{
+    apr_table_entry_t **sort_array;
+    apr_table_entry_t **sort_next;
+    apr_table_entry_t **sort_end;
+    apr_table_entry_t *table_next;
+    apr_table_entry_t **last;
+    int i;
+    int dups_found;
+
+    if (flags == APR_OVERLAP_TABLES_ADD) {
+        return;
+    }
+
+    if (t->a.nelts <= 1) {
+        return;
+    }
+
+    /* Copy pointers to all the table elements into an
+     * array and sort to allow for easy detection of
+     * duplicate keys
+     */
+    sort_array = (apr_table_entry_t **)
+        apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
+    sort_next = sort_array;
+    table_next = (apr_table_entry_t *)t->a.elts;
+    i = t->a.nelts;
+    do {
+        *sort_next++ = table_next++;
+    } while (--i);
+
+    /* Note: the merge is done with mergesort instead of quicksort
+     * because mergesort is a stable sort and runs in n*log(n)
+     * time regardless of its inputs (quicksort is quadratic in
+     * the worst case)
+     */
+    sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
+
+    /* Process any duplicate keys */
+    dups_found = 0;
+    sort_next = sort_array;
+    sort_end = sort_array + t->a.nelts;
+    last = sort_next++;
+    while (sort_next < sort_end) {
+        if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
+            !strcasecmp((*sort_next)->key, (*last)->key)) {
+            apr_table_entry_t **dup_last = sort_next + 1;
+            dups_found = 1;
+            while ((dup_last < sort_end) &&
+                   ((*dup_last)->key_checksum == (*last)->key_checksum) &&
+                   !strcasecmp((*dup_last)->key, (*last)->key)) {
+                dup_last++;
+            }
+            dup_last--; /* Elements from last through dup_last, inclusive,
+                         * all have the same key
+                         */
+            if (flags == APR_OVERLAP_TABLES_MERGE) {
+                apr_size_t len = 0;
+                apr_table_entry_t **next = last;
+                char *new_val;
+                char *val_dst;
+                do {
+                    len += strlen((*next)->val);
+                    len += 2; /* for ", " or trailing null */
+                } while (++next <= dup_last);
+                new_val = (char *)apr_palloc(t->a.pool, len);
+                val_dst = new_val;
+                next = last;
+                for (;;) {
+                    strcpy(val_dst, (*next)->val);
+                    val_dst += strlen((*next)->val);
+                    next++;
+                    if (next > dup_last) {
+                        *val_dst = 0;
+                        break;
+                    }
+                    else {
+                        *val_dst++ = ',';
+                        *val_dst++ = ' ';
+                    }
+                }
+                (*last)->val = new_val;
+            }
+            else { /* overwrite */
+                (*last)->val = (*dup_last)->val;
+            }
+            do {
+                (*sort_next)->key = NULL;
+            } while (++sort_next <= dup_last);
+        }
+        else {
+            last = sort_next++;
+        }
+    }
+
+    /* Shift elements to the left to fill holes left by removing duplicates */
+    if (dups_found) {
+        apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
+        apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
+        apr_table_entry_t *last_elt = src + t->a.nelts;
+        do {
+            if (src->key) {
+                *dst++ = *src;
+            }
+        } while (++src < last_elt);
+        t->a.nelts -= (int)(last_elt - dst);
+    }
+
+    table_reindex(t);
+}
+
+static 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(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
+				    unsigned flags)
+{
+    if (a->a.nelts + b->a.nelts == 0) {
+        return;
+    }
+
+#if APR_POOL_DEBUG
+    /* Since the keys and values are not copied, it's required that
+     * b->a.pool has a lifetime at least as long as a->a.pool. */
+    if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
+        fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
+        abort();
+    }
+#endif
+
+    apr_table_cat(a, b);
+
+    apr_table_compress(a, flags);
+}
+
+static int table_getm_do(void *v, const char *key, const char *val)
+{
+    table_getm_t *state = (table_getm_t *) v;
+
+    if (!state->first) {
+        /**
+         * The most common case is a single header, and this is covered by
+         * a fast path that doesn't allocate any memory. On the second and
+         * subsequent header, an array is created and the array concatenated
+         * together to form the final value.
+         */
+        state->first = val;
+    }
+    else {
+        const char **elt;
+        if (!state->merged) {
+            state->merged = apr_array_make(state->p, 10, sizeof(const char *));
+            elt = apr_array_push(state->merged);
+            *elt = state->first;
+        }
+        elt = apr_array_push(state->merged);
+        *elt = val;
+    }
+    return 1;
+}
+
+APR_DECLARE(const char *) apr_table_getm(apr_pool_t *p, const apr_table_t *t,
+        const char *key)
+{
+    table_getm_t state;
+
+    state.p = p;
+    state.first = NULL;
+    state.merged = NULL;
+
+    apr_table_do(table_getm_do, &state, t, key, NULL);
+
+    if (!state.first) {
+        return NULL;
+    }
+    else if (!state.merged) {
+        return state.first;
+    }
+    else {
+        return apr_array_pstrcat(p, state.merged, ',');
+    }
+}