diff options
Diffstat (limited to 'tables')
-rw-r--r-- | tables/.cvsignore | 1 | ||||
-rw-r--r-- | tables/Makefile.in | 61 | ||||
-rw-r--r-- | tables/apr_hash.c | 314 | ||||
-rw-r--r-- | tables/apr_tables.c | 796 |
4 files changed, 1172 insertions, 0 deletions
diff --git a/tables/.cvsignore b/tables/.cvsignore new file mode 100644 index 000000000..f3c7a7c5d --- /dev/null +++ b/tables/.cvsignore @@ -0,0 +1 @@ +Makefile diff --git a/tables/Makefile.in b/tables/Makefile.in new file mode 100644 index 000000000..53d47af9f --- /dev/null +++ b/tables/Makefile.in @@ -0,0 +1,61 @@ +#CFLAGS=$(OPTIM) $(CFLAGS1) $(EXTRA_CFLAGS) +#LIBS=$(EXTRA_LIBS) $(LIBS1) +#INCLUDES=$(INCLUDES1) $(INCLUDES0) $(EXTRA_INCLUDES) +#LDFLAGS=$(LDFLAGS1) $(EXTRA_LDFLAGS) + +CC=@CC@ +RANLIB=@RANLIB@ +AR=@AR@ +RM=@RM@ +CFLAGS=@CFLAGS@ @OPTIM@ +LIBS=@LIBS@ +LDFLAGS=@LDFLAGS@ $(LIBS) +INCDIR=../include +INCDIR1=../misc/@OSDIR@ +INCLUDES=-I$(INCDIR) -I$(INCDIR1) -I../misc/unix + +OBJS=apr_tables.o \ + apr_hash.o + +.c.o: + $(CC) $(CFLAGS) -c $(INCLUDES) $< + +all: $(OBJS) + +clean: + $(RM) -f *.o *.a *.so + +distclean: clean + -$(RM) -f Makefile + + +#$(LIB): $(OBJS) +# $(RM) -f $@ +# $(AR) cr $@ $(OBJS) +# $(RANLIB) $@ + +# +# We really don't expect end users to use this rule. It works only with +# gcc, and rebuilds Makefile.in. You have to re-run configure after +# using it. +# +depend: + cp Makefile.in Makefile.in.bak \ + && sed -ne '1,/^# DO NOT REMOVE/p' Makefile.in > Makefile.new \ + && gcc -MM $(INCLUDES) $(CFLAGS) *.c >> Makefile.new \ + && sed -e '1,$$s: $(INCDIR)/: $$(INCDIR)/:g' \ + -e '1,$$s: $(OSDIR)/: $$(OSDIR)/:g' Makefile.new \ + > Makefile.in \ + && rm Makefile.new + +# DO NOT REMOVE +apr_hash.o: apr_hash.c $(INCDIR)/apr_private.h \ + $(INCDIR)/apr_general.h $(INCDIR)/apr.h $(INCDIR)/apr_errno.h \ + $(INCDIR)/apr_pools.h $(INCDIR)/apr_thread_proc.h \ + $(INCDIR)/apr_file_io.h $(INCDIR)/apr_time.h $(INCDIR)/apr_hash.h +apr_tables.o: apr_tables.c $(INCDIR)/apr_private.h \ + $(INCDIR)/apr_general.h $(INCDIR)/apr.h $(INCDIR)/apr_errno.h \ + $(INCDIR)/apr_pools.h $(INCDIR)/apr_thread_proc.h \ + $(INCDIR)/apr_file_io.h $(INCDIR)/apr_time.h \ + $(INCDIR)/apr_tables.h $(INCDIR)/apr_strings.h $(INCDIR)/apr_lib.h \ + ../misc/unix/misc.h $(INCDIR)/apr_getopt.h diff --git a/tables/apr_hash.c b/tables/apr_hash.c new file mode 100644 index 000000000..f486a2698 --- /dev/null +++ b/tables/apr_hash.c @@ -0,0 +1,314 @@ +/* ==================================================================== + * The Apache Software License, Version 1.1 + * + * Copyright (c) 2000 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/>. + * + * Portions of this software are based upon public domain software + * originally written at the National Center for Supercomputing Applications, + * University of Illinois, Urbana-Champaign. + */ + +#include "apr_private.h" + +#include "apr_general.h" +#include "apr_pools.h" + +#include "apr_hash.h" + +#ifdef HAVE_STDLIB_H +#include <stdlib.h> +#endif +#ifdef HAVE_STDLIB_H +#include <string.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 ap_hash_entry_t ap_hash_entry_t; + +struct ap_hash_entry_t { + ap_hash_entry_t *next; + int hash; + const void *key; + size_t klen; + const void *val; +}; + +/* + * 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 ap_hash_t { + ap_pool_t *pool; + ap_hash_entry_t **array; + size_t count, max; +}; +#define INITIAL_MAX 15 /* tunable == 2^n - 1 */ + +/* + * 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 + * ap_hash_next(). + */ +struct ap_hash_index_t { + ap_hash_t *ht; + ap_hash_entry_t *this, *next; + int index; +}; + + +/* + * Hash creation functions. + */ + +static ap_hash_entry_t **alloc_array(ap_hash_t *ht) +{ + return ap_pcalloc(ht->pool, sizeof(*ht->array) * (ht->max + 1)); +} + +APR_EXPORT(ap_hash_t *) ap_make_hash(ap_pool_t *pool) +{ + ap_hash_t *ht; + ht = ap_palloc(pool, sizeof(ap_hash_t)); + ht->pool = pool; + ht->count = 0; + ht->max = INITIAL_MAX; + ht->array = alloc_array(ht); + return ht; +} + + +/* + * Hash iteration functions. + */ + +APR_EXPORT(ap_hash_index_t *) ap_hash_next(ap_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_EXPORT(ap_hash_index_t *) ap_hash_first(ap_hash_t *ht) +{ + ap_hash_index_t *hi; + hi = ap_palloc(ht->pool, sizeof(*hi)); + hi->ht = ht; + hi->index = 0; + hi->this = NULL; + hi->next = NULL; + return ap_hash_next(hi); +} + +APR_EXPORT(void) ap_hash_this(ap_hash_index_t *hi, + const void **key, + size_t *klen, + void **val) +{ + if (key) *key = hi->this->key; + if (klen) *klen = hi->this->klen; + if (val) *val = (void *)hi->this->val; +} + + +/* + * Resizing a hash table + */ + +static void resize_array(ap_hash_t *ht) +{ + ap_hash_index_t *hi; + ap_hash_entry_t **new_array; + int i; + + new_array = alloc_array(ht); + for (hi = ap_hash_first(ht); hi; hi = ap_hash_next(hi)) { + i = hi->this->hash & ht->max; + hi->this->next = new_array[i]; + new_array[i] = hi->this; + } + ht->array = new_array; +} + +/* + * 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 ap_hash_entry_t **find_entry(ap_hash_t *ht, + const void *key, + size_t klen, + const void *val) +{ + ap_hash_entry_t **hep, *he; + const unsigned char *p; + int hash; + int i; + + if (klen == 0) + klen = strlen(key) + 1; + + /* + * This is Daniel J. Bernstein's popular `times 33' hash function + * as posted by him years ago on comp.lang.c and used by perl. + * This is one of the best known hash functions for strings + * because it is both computed very fast and distributes very + * well. + * + * 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 + * and seems to be the reason why Daniel J. Bernstein also preferred + * it. + * -- Ralf S. Engelschall <rse@engelschall.com> + */ + hash = 0; + for (p = key, i = klen; i; i--, p++) + hash = hash * 33 + *p; + + /* 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 */ + he = ap_pcalloc(ht->pool, sizeof(*he)); + he->hash = hash; + he->key = key; + he->klen = klen; + he->val = val; + *hep = he; + /* check that the collision rate isn't too high */ + if (++ht->count > ht->max) { + ht->max = ht->max * 2 + 1; + resize_array(ht); + } + return hep; +} + +APR_EXPORT(void *) ap_hash_get(ap_hash_t *ht, + const void *key, + size_t klen) +{ + ap_hash_entry_t *he; + he = *find_entry(ht, key, klen, NULL); + if (he) + return (void *)he->val; + else + return NULL; +} + +APR_EXPORT(void) ap_hash_set(ap_hash_t *ht, + const void *key, + size_t klen, + const void *val) +{ + ap_hash_entry_t **hep; + hep = find_entry(ht, key, klen, val); + if (*hep) { + if (!val) { + /* delete entry */ + *hep = (*hep)->next; + --ht->count; + } + else { + /* replace entry */ + (*hep)->val = val; + } + } + /* else key not present and val==NULL */ +} diff --git a/tables/apr_tables.c b/tables/apr_tables.c new file mode 100644 index 000000000..8c417b2eb --- /dev/null +++ b/tables/apr_tables.c @@ -0,0 +1,796 @@ +/* ==================================================================== + * The Apache Software License, Version 1.1 + * + * Copyright (c) 2000 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" +#include "misc.h" +#ifdef HAVE_STDLIB_H +#include <stdlib.h> +#endif +#ifdef HAVE_MALLOC_H +#include <malloc.h> +#endif +#ifdef HAVE_STRING_H +#include <string.h> +#endif +#ifdef HAVE_STRINGS_H +#include <strings.h> +#endif + +/***************************************************************** + * This file contains array and ap_table_t functions only. + */ + +/***************************************************************** + * + * The 'array' functions... + */ + +static void make_array_core(ap_array_header_t *res, ap_pool_t *c, + int nelts, int elt_size) +{ + /* + * Assure sanity if someone asks for + * array of zero elts. + */ + if (nelts < 1) { + nelts = 1; + } + + res->elts = ap_pcalloc(c, nelts * elt_size); + + res->cont = c; + res->elt_size = elt_size; + res->nelts = 0; /* No active elements yet... */ + res->nalloc = nelts; /* ...but this many allocated */ +} + +APR_EXPORT(ap_array_header_t *) ap_make_array(ap_pool_t *p, + int nelts, int elt_size) +{ + ap_array_header_t *res; + + res = (ap_array_header_t *) ap_palloc(p, sizeof(ap_array_header_t)); + make_array_core(res, p, nelts, elt_size); + return res; +} + +APR_EXPORT(void *) ap_push_array(ap_array_header_t *arr) +{ + if (arr->nelts == arr->nalloc) { + int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2; + char *new_data; + + new_data = ap_pcalloc(arr->cont, 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_EXPORT(void) ap_array_cat(ap_array_header_t *dst, + const ap_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 = ap_pcalloc(dst->cont, 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_EXPORT(ap_array_header_t *) ap_copy_array(ap_pool_t *p, + const ap_array_header_t *arr) +{ + ap_array_header_t *res = ap_make_array(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(ap_array_header_t *res, + const ap_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_EXPORT(ap_array_header_t *) + ap_copy_array_hdr(ap_pool_t *p, + const ap_array_header_t *arr) +{ + ap_array_header_t *res; + + res = (ap_array_header_t *) ap_palloc(p, sizeof(ap_array_header_t)); + res->cont = p; + copy_array_hdr_core(res, arr); + return res; +} + +/* The above is used here to avoid consing multiple new array bodies... */ + +APR_EXPORT(ap_array_header_t *) + ap_append_arrays(ap_pool_t *p, + const ap_array_header_t *first, + const ap_array_header_t *second) +{ + ap_array_header_t *res = ap_copy_array_hdr(p, first); + + ap_array_cat(res, second); + return res; +} + +/* ap_array_pstrcat generates a new string from the ap_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_EXPORT(char *) ap_array_pstrcat(ap_pool_t *p, + const ap_array_header_t *arr, + const char sep) +{ + char *cp, *res, **strpp; + int i, len; + + if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */ + return (char *) ap_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 *) ap_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. + */ + +/* + * XXX: if you tweak this you should look at is_empty_table() and table_elts() + * in alloc.h + */ +#ifdef MAKE_TABLE_PROFILE +static ap_table_entry_t *table_push(ap_table_t *t) +{ + if (t->a.nelts == t->a.nalloc) { + return NULL; + } + return (ap_table_entry_t *) ap_push_array(&t->a); +} +#else /* MAKE_TABLE_PROFILE */ +#define table_push(t) ((ap_table_entry_t *) ap_push_array(&(t)->a)) +#endif /* MAKE_TABLE_PROFILE */ + + +APR_EXPORT(ap_table_t *) ap_make_table(ap_pool_t *p, int nelts) +{ + ap_table_t *t = ap_palloc(p, sizeof(ap_table_t)); + + make_array_core(&t->a, p, nelts, sizeof(ap_table_entry_t)); +#ifdef MAKE_TABLE_PROFILE + t->creator = __builtin_return_address(0); +#endif + return t; +} + +APR_EXPORT(ap_table_t *) ap_copy_table(ap_pool_t *p, const ap_table_t *t) +{ + ap_table_t *new = ap_palloc(p, sizeof(ap_table_t)); + +#ifdef 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 (!ap_pool_is_ancestor(t->a.cont, p)) { + fprintf(stderr, "copy_table: t's pool is not an ancestor of p\n"); + abort(); + } +#endif + make_array_core(&new->a, p, t->a.nalloc, sizeof(ap_table_entry_t)); + memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(ap_table_entry_t)); + new->a.nelts = t->a.nelts; + return new; +} + +APR_EXPORT(void) ap_clear_table(ap_table_t *t) +{ + t->a.nelts = 0; +} + +APR_EXPORT(const char *) ap_table_get(const ap_table_t *t, const char *key) +{ + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + int i; + + if (key == NULL) { + return NULL; + } + + for (i = 0; i < t->a.nelts; ++i) { + if (!strcasecmp(elts[i].key, key)) { + return elts[i].val; + } + } + + return NULL; +} + +APR_EXPORT(void) ap_table_set(ap_table_t *t, const char *key, + const char *val) +{ + register int i, j, k; + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + int done = 0; + + for (i = 0; i < t->a.nelts; ) { + if (!strcasecmp(elts[i].key, key)) { + if (!done) { + elts[i].val = ap_pstrdup(t->a.cont, val); + done = 1; + ++i; + } + else { /* delete an extraneous element */ + for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { + elts[j].key = elts[k].key; + elts[j].val = elts[k].val; + } + --t->a.nelts; + } + } + else { + ++i; + } + } + + if (!done) { + elts = (ap_table_entry_t *) table_push(t); + elts->key = ap_pstrdup(t->a.cont, key); + elts->val = ap_pstrdup(t->a.cont, val); + } +} + +APR_EXPORT(void) ap_table_setn(ap_table_t *t, const char *key, + const char *val) +{ + register int i, j, k; + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + int done = 0; + +#ifdef POOL_DEBUG + { + if (!ap_pool_is_ancestor(ap_find_pool(key, NULL), t->a.cont)) { + fprintf(stderr, "table_set: key not in ancestor pool of t\n"); + abort(); + } + if (!ap_pool_is_ancestor(ap_find_pool(val, NULL), t->a.cont)) { + fprintf(stderr, "table_set: val not in ancestor pool of t\n"); + abort(); + } + } +#endif + + for (i = 0; i < t->a.nelts; ) { + if (!strcasecmp(elts[i].key, key)) { + if (!done) { + elts[i].val = (char *)val; + done = 1; + ++i; + } + else { /* delete an extraneous element */ + for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { + elts[j].key = elts[k].key; + elts[j].val = elts[k].val; + } + --t->a.nelts; + } + } + else { + ++i; + } + } + + if (!done) { + elts = (ap_table_entry_t *) table_push(t); + elts->key = (char *)key; + elts->val = (char *)val; + } +} + +APR_EXPORT(void) ap_table_unset(ap_table_t *t, const char *key) +{ + register int i, j, k; + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + + for (i = 0; i < t->a.nelts; ) { + if (!strcasecmp(elts[i].key, key)) { + + /* found an element to skip over + * there are any number of ways to remove an element from + * a contiguous block of memory. I've chosen one that + * doesn't do a memcpy/bcopy/array_delete, *shrug*... + */ + for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { + elts[j].key = elts[k].key; + elts[j].val = elts[k].val; + } + --t->a.nelts; + } + else { + ++i; + } + } +} + +APR_EXPORT(void) ap_table_merge(ap_table_t *t, const char *key, + const char *val) +{ + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + int i; + + for (i = 0; i < t->a.nelts; ++i) { + if (!strcasecmp(elts[i].key, key)) { + elts[i].val = ap_pstrcat(t->a.cont, elts[i].val, ", ", val, NULL); + return; + } + } + + elts = (ap_table_entry_t *) table_push(t); + elts->key = ap_pstrdup(t->a.cont, key); + elts->val = ap_pstrdup(t->a.cont, val); +} + +APR_EXPORT(void) ap_table_mergen(ap_table_t *t, const char *key, + const char *val) +{ + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + int i; + +#ifdef POOL_DEBUG + { + if (!ap_pool_is_ancestor(ap_find_pool(key, NULL), t->a.cont)) { + fprintf(stderr, "table_set: key not in ancestor pool of t\n"); + abort(); + } + if (!ap_pool_is_ancestor(ap_find_pool(val, NULL), t->a.cont)) { + fprintf(stderr, "table_set: key not in ancestor pool of t\n"); + abort(); + } + } +#endif + + for (i = 0; i < t->a.nelts; ++i) { + if (!strcasecmp(elts[i].key, key)) { + elts[i].val = ap_pstrcat(t->a.cont, elts[i].val, ", ", val, NULL); + return; + } + } + + elts = (ap_table_entry_t *) table_push(t); + elts->key = (char *)key; + elts->val = (char *)val; +} + +APR_EXPORT(void) ap_table_add(ap_table_t *t, const char *key, + const char *val) +{ + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + + elts = (ap_table_entry_t *) table_push(t); + elts->key = ap_pstrdup(t->a.cont, key); + elts->val = ap_pstrdup(t->a.cont, val); +} + +APR_EXPORT(void) ap_table_addn(ap_table_t *t, const char *key, + const char *val) +{ + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + +#ifdef POOL_DEBUG + { + if (!ap_pool_is_ancestor(ap_find_pool(key, NULL), t->a.cont)) { + fprintf(stderr, "table_set: key not in ancestor pool of t\n"); + abort(); + } + if (!ap_pool_is_ancestor(ap_find_pool(val, NULL), t->a.cont)) { + fprintf(stderr, "table_set: key not in ancestor pool of t\n"); + abort(); + } + } +#endif + + elts = (ap_table_entry_t *) table_push(t); + elts->key = (char *)key; + elts->val = (char *)val; +} + +APR_EXPORT(ap_table_t *) ap_overlay_tables(ap_pool_t *p, + const ap_table_t *overlay, + const ap_table_t *base) +{ + ap_table_t *res; + +#ifdef 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 (!ap_pool_is_ancestor(overlay->a.cont, p)) { + fprintf(stderr, + "overlay_tables: overlay's pool is not an ancestor of p\n"); + abort(); + } + if (!ap_pool_is_ancestor(base->a.cont, p)) { + fprintf(stderr, + "overlay_tables: base's pool is not an ancestor of p\n"); + abort(); + } +#endif + + res = ap_palloc(p, sizeof(ap_table_t)); + /* behave like append_arrays */ + res->a.cont = p; + copy_array_hdr_core(&res->a, &overlay->a); + ap_array_cat(&res->a, &base->a); + + 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 ap_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 ap_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 ap_table_vdo(): + * + * The caching api will allow a user to walk the header values: + * + * ap_status_t ap_cache_el_header_walk(ap_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: + * + * ap_status_t (*cache_el_header_walk)(ap_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 ap_table - and + * rather than reimplementing ap_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 ap_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_EXPORT(void) ap_table_do(int (*comp) (void *, const char *, const char *), + void *rec, const ap_table_t *t, ...) +{ + va_list vp; + va_start(vp, t); + ap_table_vdo(comp, rec, t, vp); + va_end(vp); +} +APR_EXPORT(void) ap_table_vdo(int (*comp) (void *, const char *, const char *), + void *rec, const ap_table_t *t, va_list vp) +{ + char *argp; + ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; + int rv, i; + argp = va_arg(vp, char *); + do { + for (rv = 1, i = 0; rv && (i < t->a.nelts); ++i) { + if (elts[i].key && (!argp || !strcasecmp(elts[i].key, argp))) { + rv = (*comp) (rec, elts[i].key, elts[i].val); + } + } + } while (argp && ((argp = va_arg(vp, char *)) != NULL)); +} + +/* Curse libc and the fact that it doesn't guarantee a stable sort. We + * have to enforce stability ourselves by using the order field. If it + * provided a stable sort then we wouldn't even need temporary storage to + * do the work below. -djg + * + * ("stable sort" means that equal keys retain their original relative + * ordering in the output.) + */ +typedef struct { + char *key; + char *val; + int order; +} overlap_key; + +static int sort_overlap(const void *va, const void *vb) +{ + const overlap_key *a = va; + const overlap_key *b = vb; + int r; + + r = strcasecmp(a->key, b->key); + if (r) { + return r; + } + return a->order - b->order; +} + +/* prefer to use the stack for temp storage for overlaps smaller than this */ +#ifndef ap_OVERLAP_TABLES_ON_STACK +#define ap_OVERLAP_TABLES_ON_STACK (512) +#endif + +APR_EXPORT(void) ap_overlap_tables(ap_table_t *a, const ap_table_t *b, + unsigned flags) +{ + overlap_key cat_keys_buf[ap_OVERLAP_TABLES_ON_STACK]; + overlap_key *cat_keys; + int nkeys; + ap_table_entry_t *e; + ap_table_entry_t *last_e; + overlap_key *left; + overlap_key *right; + overlap_key *last; + + nkeys = a->a.nelts + b->a.nelts; + if (nkeys < ap_OVERLAP_TABLES_ON_STACK) { + cat_keys = cat_keys_buf; + } + else { + /* XXX: could use scratch free space in a or b's pool instead... + * which could save an allocation in b's pool. + */ + cat_keys = ap_palloc(b->a.cont, sizeof(overlap_key) * nkeys); + } + + nkeys = 0; + + /* Create a list of the entries from a concatenated with the entries + * from b. + */ + e = (ap_table_entry_t *)a->a.elts; + last_e = e + a->a.nelts; + while (e < last_e) { + cat_keys[nkeys].key = e->key; + cat_keys[nkeys].val = e->val; + cat_keys[nkeys].order = nkeys; + ++nkeys; + ++e; + } + + e = (ap_table_entry_t *)b->a.elts; + last_e = e + b->a.nelts; + while (e < last_e) { + cat_keys[nkeys].key = e->key; + cat_keys[nkeys].val = e->val; + cat_keys[nkeys].order = nkeys; + ++nkeys; + ++e; + } + + qsort(cat_keys, nkeys, sizeof(overlap_key), sort_overlap); + + /* Now iterate over the sorted list and rebuild a. + * Start by making sure it has enough space. + */ + a->a.nelts = 0; + if (a->a.nalloc < nkeys) { + a->a.elts = ap_palloc(a->a.cont, a->a.elt_size * nkeys * 2); + a->a.nalloc = nkeys * 2; + } + + /* + * In both the merge and set cases we retain the invariant: + * + * left->key, (left+1)->key, (left+2)->key, ..., (right-1)->key + * are all equal keys. (i.e. strcasecmp returns 0) + * + * We essentially need to find the maximal + * right for each key, then we can do a quick merge or set as + * appropriate. + */ + + if (flags & AP_OVERLAP_TABLES_MERGE) { + left = cat_keys; + last = left + nkeys; + while (left < last) { + right = left + 1; + if (right == last + || strcasecmp(left->key, right->key)) { + ap_table_addn(a, left->key, left->val); + left = right; + } + else { + char *strp; + char *value; + size_t len; + + /* Have to merge some headers. Let's re-use the order field, + * since it's handy... we'll store the length of val there. + */ + left->order = strlen(left->val); + len = left->order; + do { + right->order = strlen(right->val); + len += 2 + right->order; + ++right; + } while (right < last + && !strcasecmp(left->key, right->key)); + /* right points one past the last header to merge */ + value = ap_palloc(a->a.cont, len + 1); + strp = value; + for (;;) { + memcpy(strp, left->val, left->order); + strp += left->order; + ++left; + if (left == right) { + break; + } + *strp++ = ','; + *strp++ = ' '; + } + *strp = 0; + ap_table_addn(a, (left-1)->key, value); + } + } + } + else { + left = cat_keys; + last = left + nkeys; + while (left < last) { + right = left + 1; + while (right < last && !strcasecmp(left->key, right->key)) { + ++right; + } + ap_table_addn(a, (right-1)->key, (right-1)->val); + left = right; + } + } +} + |