/* ====================================================================
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2000-2001 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */

/*
 * 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
#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif
#if APR_HAVE_STRING_H
#include <string.h>
#endif
#if APR_HAVE_STRINGS_H
#include <strings.h>
#endif

#define INITIAL_MIN 31

struct apr_table_bucket_t {
    /** The next bucket in bucket list*/
    apr_table_bucket_t *next;  
    /** The previous bucket in bucket list */
    apr_table_bucket_t *prev;
    /** The current table entry pointer */
    apr_table_entry_t *elt;
    /** The hash bucket value */
    int     hash;
};


/** The opaque string-content table type */
struct apr_table_index_t {
    /** The table of hash buckets */
    apr_table_bucket_t **buckets;
    /** The number of hash buckets */    
    int     size;
    /** The allocated number of hash buckets */    
    int     count;
};


/*****************************************************************
 * 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)
{
    /*
     * Assure sanity if someone asks for
     * array of zero elts.
     */
    if (nelts < 1) {
        nelts = 1;
    }

    res->elts = apr_pcalloc(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(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);
    return res;
}

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_pcalloc(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_make(p, arr->nalloc, arr->elt_size);

    memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
    res->nelts = arr->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;
}


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));
    if (nelts < 1)
        nelts = 1;
    t->a.elts = apr_pcalloc(p, nelts * sizeof(apr_table_entry_t));
    t->a.pool = p;
    t->a.elt_size = sizeof(apr_table_entry_t);
    t->a.nelts = 0;
    t->a.nalloc = nelts;
    t->i = apr_pcalloc(p, sizeof(apr_table_index_t));
    if (nelts < INITIAL_MIN)
        nelts = INITIAL_MIN;
    t->i->buckets = apr_pcalloc(p, (nelts + 1) * sizeof(apr_table_bucket_t *));
    t->i->size = nelts;
    t->i->count = 0;
    return t;
}

APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p,
                                          const apr_table_t *t)
{
    apr_table_t *n_t = apr_palloc(p, sizeof(apr_table_t));
    apr_table_bucket_t *b;
    apr_table_entry_t *e, *n;
    int i, hash;

    n_t->a.elts = apr_pcalloc(p, t->a.nalloc * sizeof(apr_table_entry_t));
    n_t->a.pool = p;
    n_t->a.elt_size = sizeof(apr_table_entry_t);
    n_t->a.nelts = t->a.nelts;
    n_t->a.nalloc = t->a.nalloc;
    n_t->i = apr_pcalloc(p, sizeof(apr_table_index_t));
    n_t->i->buckets = apr_pcalloc(p, (t->i->size + 1) * sizeof(apr_table_bucket_t *));
    n_t->i->size = t->i->size;
    n_t->i->count = t->i->count;

    memcpy(n_t->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));

    e = (apr_table_entry_t *) t->a.elts;
    n = (apr_table_entry_t *) n_t->a.elts;
    
    for (i = 0; i < t->a.nelts; i++) {
        hash = e[i].idx->hash;
        
        b = apr_palloc(t->a.pool, sizeof(apr_table_bucket_t));        
        b->next = n_t->i->buckets[hash & n_t->i->size];
        b->prev = NULL;
        b->hash = hash;
        b->elt = &n[i];
        if (n_t->i->buckets[hash & n_t->i->size])
            n_t->i->buckets[hash & n_t->i->size]->prev = b;
        n_t->i->buckets[hash & n_t->i->size] = b;
        n[i].idx = b;
    }
    return n_t;
}

APR_DECLARE(void) apr_table_clear(apr_table_t *t)
{
    memset(*t->i->buckets, 0, t->i->size * sizeof(apr_table_bucket_t *));
    t->a.nelts = 0;
}
/*
APR_DECLARE(apr_table_entry_t *) apr_table_elts(apr_table_t *t)
{
    return (apr_table_entry_t *)t->a.elts;
}
*/
APR_DECLARE(int) apr_table_count(apr_table_t *t)
{
    return t->a.nelts;
}

static int hash2(const char *key)
{
    int hash;
    for (hash = 0; *key; key++)
        hash = hash * 33 + toupper(*key);
    return hash;
}

static void expand_index(apr_table_t *t)
{
    apr_table_bucket_t **n_b;
    apr_table_bucket_t *b;
    apr_table_entry_t *e = (apr_table_entry_t *) t->a.elts;
    int n_nalloc;
    int i, h;

    n_nalloc = t->i->size << 2 + 3;

    n_b = apr_pcalloc(t->a.pool, sizeof(apr_table_bucket_t *) * n_nalloc);
    for (i = 0; i < t->a.nelts; i++) {
        h = e[i].idx->hash & n_nalloc;
        b = apr_palloc(t->a.pool, sizeof(apr_table_bucket_t));    
        b->next = n_b[h];
        b->prev = NULL;
        b->elt = &e[i];
        b->hash = e[i].idx->hash;
        b->elt = NULL;
        e[i].idx = b;
        if (n_b[h])
            n_b[h]->prev = b;
        n_b[h] = b;
    }
    t->i->size = n_nalloc;
    t->i->buckets = n_b;
}

static void expand_table(apr_table_t *t)
{
    int n_nalloc = (t->a.nalloc <= 0) ? 1 : t->a.nalloc * 2;
    char *new_data;
    apr_table_entry_t  *e;
    int i;

    new_data = apr_pcalloc(t->a.pool, sizeof(apr_table_entry_t) * n_nalloc);
    memcpy(new_data, t->a.elts, t->a.nalloc * sizeof(apr_table_entry_t));
    e = (apr_table_entry_t  *) new_data;
    /* fix the index pointers */
    for (i = 0; i < t->a.nelts; i++)
        e[i].idx->elt = &e[i];
    t->a.elts = new_data;
    t->a.nalloc = n_nalloc;
}

static apr_table_entry_t *stable_push(apr_table_t *t)
{
    apr_table_entry_t *e;
    if (t->a.nalloc == t->a.nelts)
        expand_table(t);
    e = (apr_table_entry_t *)(t->a.elts + t->a.nelts * sizeof(apr_table_entry_t));
    ++t->a.nelts;
    return e;
}

static apr_table_bucket_t *lookup_bucket(const apr_table_t *t, const char *key)
{
    apr_table_bucket_t *b;
    int hash = hash2(key);
     
    for (b = t->i->buckets[hash & t->i->size]; b; b = b->next) {
        if (hash == b->hash && b->elt && !strcasecmp(b->elt->key, key))
            return b;
    }    
    return NULL;
}

APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
{

    apr_table_bucket_t *b = lookup_bucket(t, key);
    return b ? b->elt->val : NULL;

}

static apr_table_bucket_t *create_bucket(apr_table_t *t, apr_table_entry_t *e)
{
    apr_table_bucket_t *b;
    int hash = hash2(e->key);
    
    b = apr_palloc(t->a.pool, sizeof(apr_table_bucket_t));
    
    b->next = t->i->buckets[hash & t->i->size];
    b->prev = NULL;
    b->hash = hash;
    b->elt = e;
    if (t->i->buckets[hash & t->i->size])
        t->i->buckets[hash & t->i->size]->prev = b;
    t->i->buckets[hash & t->i->size] = b;
    ++t->i->count;
    return b;
}

APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
                                const char *val)
{
    apr_table_entry_t  *e;
    
    e = stable_push(t);
    e->key = apr_pstrdup(t->a.pool, key);
    e->val = apr_pstrdup(t->a.pool, val);
    e->idx = create_bucket(t, e);
    if (t->a.nelts > t->i->size * 4)
        expand_index(t);        
}

APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
                                const char *val)
{
    apr_table_entry_t  *e;
    
    e = stable_push(t);
    e->key = (char *) key;
    e->val = (char *) val;
    e->idx = create_bucket(t, e);
    if (t->a.nelts > t->i->size * 4)
        expand_index(t);        
}

static apr_table_bucket_t *lookup_dups(apr_table_t *t, const char *key, int *dups)
{

    apr_table_bucket_t *b, *f = NULL;
    int hash = hash2(key);
     
    for (b = t->i->buckets[hash & t->i->size]; b; b = b->next) {
        if (hash == b->hash && b->elt && !strcasecmp(b->elt->key, key)) {
            if (!f)
                f = b;
            else {
                b->elt->key = NULL;
                ++*dups;
            }
        }
    }    
    return f;

}

static int lookup_del(apr_table_t *t, const char *key)
{
    apr_table_bucket_t *b;
    int hash = hash2(key);
    int count = 0;

    for (b = t->i->buckets[hash & t->i->size]; b; b = b->next) {
        b->elt->key = NULL;
        ++count;
    }
        
    return count;
}

APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
                                const char *val)
{
    apr_table_bucket_t *b;
    apr_table_entry_t  *e;
    int dups = 0;

    b = lookup_dups(t, key, &dups);
    if (!b) {
        e = stable_push(t);
        e->key = apr_pstrdup(t->a.pool, key);
        e->val = apr_pstrdup(t->a.pool, val);
        e->idx = create_bucket(t, e);
        if (t->a.nelts > t->i->size * 4)
            expand_index(t);
    }
    else {
        if (dups) {
            register int i, j, k;
            int done;
            e = (apr_table_entry_t *) t->a.elts;

            for (i = 0; i < t->a.nelts; ) {
                done = 0;
                if (e[i].key == NULL) {
                    if (!done) {
                        if (e[i].idx->prev)
                            e[i].idx->prev->next = e[i].idx->next;
                        else
                            t->i->buckets[e[i].idx->hash & t->i->size] = e[i].idx->next;
                        if (e[i].idx->next)
                            e[i].idx->next->prev = e[i].idx->prev;                    
                        --t->i->count;
                        done = 1;
                    }
                    for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
                        e[j].key = e[k].key;
                        e[j].val = e[k].val;
                        e[j].idx = e[k].idx;
                        e[k].idx->elt = &e[j];
                    }
                    --t->a.nelts;
                }
                else
                    ++i;

            }
        }
        b->elt->val = apr_pstrdup(t->a.pool, val);
    }
}

APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
                                const char *val)
{
    apr_table_bucket_t *b;
    apr_table_entry_t  *e;
    int dups = 0;

    b = lookup_dups(t, key, &dups);
    if (!b) {
        e = stable_push(t);
        e->key = (char *) key;
        e->val = (char *) val;
        e->idx = create_bucket(t, e);
        if (t->a.nelts > t->i->size * 4)
            expand_index(t);
    }
    else {
        if (dups) {
            register int i, j, k;
            int done;
            e = (apr_table_entry_t *) t->a.elts;

            for (i = 0; i < t->a.nelts; ) {
                done = 0;
                if (e[i].key == NULL) {
                    if (!done) {
                        if (e[i].idx->prev)
                            e[i].idx->prev->next = e[i].idx->next;
                        else
                            t->i->buckets[e[i].idx->hash & t->i->size] = e[i].idx->next;
                        if (e[i].idx->next)
                            e[i].idx->next->prev = e[i].idx->prev;                    
                        --t->i->count;
                        done = 1;
                    }
                    for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
                        e[j].key = e[k].key;
                        e[j].val = e[k].val;
                        e[j].idx = e[k].idx;
                        e[k].idx->elt = &e[j];
                    }
                    --t->a.nelts;
                }
                else
                    ++i;

            }
        }
        b->elt->val = (char *) val;
    }
}

APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
{
    apr_table_bucket_t *b;
    apr_table_entry_t  *e;

    int hash = hash2(key);
    int found = 0;

    for (b = t->i->buckets[hash & t->i->size]; b; b = b->next) {
        b->elt->key = NULL;
        ++found;
    }

    if (found) {
        register int i, j, k;
        int done;
        e = (apr_table_entry_t *) t->a.elts;

        for (i = 0; i < t->a.nelts; ) {
            done = 0;
            if (e[i].key == NULL) {
                if (!done) {
                    if (e[i].idx->prev)
                        e[i].idx->prev->next = e[i].idx->next;
                    else
                        t->i->buckets[e[i].idx->hash & t->i->size] = e[i].idx->next;
                    if (e[i].idx->next)
                        e[i].idx->next->prev = e[i].idx->prev;                    
                    --t->i->count;
                    done = 1;
                }
                for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
                    e[j].key = e[k].key;
                    e[j].val = e[k].val;
                    e[j].idx = e[k].idx;
                    e[k].idx->elt = &e[j];
                }
                --t->a.nelts;
            }
            else
               ++i;
        }
    }
}

APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
                                  const char *val)
{
    apr_table_bucket_t *b;
    apr_table_entry_t  *e;
    int hash = hash2(key);
    int found = 0;

    b = lookup_bucket(t, key);
    if (b)
        b->elt->val = apr_pstrcat(t->a.pool, b->elt->val, ", ", val, NULL);
    else {
        e = stable_push(t);
        e->key = apr_pstrdup(t->a.pool, key);
        e->val = apr_pstrdup(t->a.pool, val);
        e->idx = create_bucket(t, e);
        if (t->a.nelts > t->i->size * 4)
            expand_index(t);
    }
}

APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
                                  const char *val)
{
    apr_table_bucket_t *b;
    apr_table_entry_t  *e;
    int hash = hash2(key);
    int found = 0;

    b = lookup_bucket(t, key);
    if (b)
        b->elt->val = apr_pstrcat(t->a.pool, b->elt->val, ", ", val, NULL);
    else {
        e = stable_push(t);
        e->key = (char *) key;
        e->val = (char *) val;
        e->idx = create_bucket(t, e);
        if (t->a.nelts > t->i->size * 4)
            expand_index(t);
    }
}

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 *n_t = apr_palloc(p, sizeof(apr_table_t));
    apr_table_bucket_t *b;
    apr_table_entry_t *e, *n;
    int i, hash, n_nalloc, n_nelts, n_size;

    n_nalloc = overlay->a.nalloc + base->a.nalloc;
    n_nelts = overlay->a.nelts + base->a.nelts;
    n_size = overlay->i->size + base->i->size;

    n_t->a.elts = apr_pcalloc(p, n_nalloc * sizeof(apr_table_entry_t));
    n_t->a.pool = p;
    n_t->a.elt_size = sizeof(apr_table_entry_t);
    n_t->a.nelts = n_nelts ;
    n_t->a.nalloc = n_nalloc;
    n_t->i = apr_pcalloc(p, sizeof(apr_table_index_t));
    n_t->i->buckets = apr_pcalloc(p, (n_size + 1) * sizeof(apr_table_bucket_t *));
    n_t->i->size = n_size;
    n_t->i->count = overlay->i->count + base->i->count;

    memcpy(n_t->a.elts, overlay->a.elts, overlay->a.nelts * sizeof(apr_table_entry_t));
    memcpy(n_t->a.elts + overlay->a.nelts * sizeof(apr_table_entry_t),
            base->a.elts, base->a.nelts * sizeof(apr_table_entry_t));

    e = (apr_table_entry_t *) overlay->a.elts;
    n = (apr_table_entry_t *) n_t->a.elts;
    
    for (i = 0; i < overlay->a.nelts; i++) {
        hash = e[i].idx->hash;
        
        b = apr_palloc(p, sizeof(apr_table_bucket_t));        
        b->next = n_t->i->buckets[hash & n_size];
        b->prev = NULL;
        b->hash = hash;
        b->elt = &n[i];
        if (n_t->i->buckets[hash & n_size])
            n_t->i->buckets[hash & n_size]->prev = b;
        n_t->i->buckets[hash & n_size] = b;
        n[i].idx = b;
    }
    e = (apr_table_entry_t *) base->a.elts;
    
    for (i = 0; i < base->a.nelts; i++) {
        hash = e[i].idx->hash;
        
        b = apr_palloc(p, sizeof(apr_table_bucket_t));        
        b->next = n_t->i->buckets[hash & n_size];
        b->prev = NULL;
        b->hash = hash;
        b->elt = &n[i];
        if (n_t->i->buckets[hash & n_size])
            n_t->i->buckets[hash & n_size]->prev = b;
        n_t->i->buckets[hash & n_size] = b;
        n[i].idx = b;
    }

    return n_t;
}

APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
                                     unsigned flags)
{
    apr_table_entry_t *e = (apr_table_entry_t *)b->a.elts;
    int i;
  
    for (i = 0; i < b->a.nelts; ++i) {
        if (flags & APR_OVERLAP_TABLES_MERGE) {
           apr_table_mergen(a, e[i].key, e[i].val);
        }
        else {
            apr_table_setn(a, e[i].key, e[i].val);
        }
    }
}

/* 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(void) apr_table_do(int (*comp) (void *, const char *, const char *),
                  void *rec, const apr_table_t *t, ...)
{
    va_list vp;
    va_start(vp, t);
    apr_table_vdo(comp, rec, t, vp);
    va_end(vp);  
} 

APR_DECLARE(void) apr_table_vdo(int (*comp) (void *, const char *, const char *),
                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 rv, h;
    apr_table_bucket_t *b;

    argp = va_arg(vp, char *);
    do {
        if (argp) {
        h = hash2(argp);
        for (rv = 1, b = t->i->buckets[h & t->i->size]; b && rv; b = b->next) {
            if (h == b->hash && b->elt && b->elt->key && !strcasecmp(b->elt->key, argp)) {
                rv = (*comp) (rec, b->elt->key, b->elt->val);
            }
        }
        }
    } while (argp && ((argp = va_arg(vp, char *)) != NULL));
}