diff options
Diffstat (limited to 'rubbos/app/httpd-2.0.64/srclib/apr/tables')
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_hash.o | bin | 19424 -> 0 bytes | |||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_tables.o | bin | 68512 -> 0 bytes | |||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile | 13 | ||||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile.in | 13 | ||||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.c | 443 | ||||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.lo | 12 | ||||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.o | bin | 19368 -> 0 bytes | |||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.c | 1207 | ||||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.lo | 12 | ||||
| -rw-r--r-- | rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.o | bin | 68320 -> 0 bytes |
10 files changed, 0 insertions, 1700 deletions
diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_hash.o b/rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_hash.o Binary files differdeleted file mode 100644 index c7bf7e51..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_hash.o +++ /dev/null diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_tables.o b/rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_tables.o Binary files differdeleted file mode 100644 index e6d0baf4..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/.libs/apr_tables.o +++ /dev/null diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile b/rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile deleted file mode 100644 index 18c9d1a0..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile +++ /dev/null @@ -1,13 +0,0 @@ -srcdir = . - - -TARGETS = apr_tables.lo apr_hash.lo - -# bring in rules.mk for standard functionality -include /bottlenecks/rubbos/app/httpd-2.0.64/srclib/apr/build/apr_rules.mk - -DEFOSDIR=$(INCDIR)/arch/unix -INCDIR=../include -INCLUDES=-I$(INCDIR) -I$(DEFOSDIR) - -# DO NOT REMOVE diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile.in b/rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile.in deleted file mode 100644 index 9a97a30f..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/Makefile.in +++ /dev/null @@ -1,13 +0,0 @@ -srcdir = @srcdir@ -VPATH = @srcdir@ - -TARGETS = apr_tables.lo apr_hash.lo - -# bring in rules.mk for standard functionality -@INCLUDE_RULES@ - -DEFOSDIR=$(INCDIR)/arch/@DEFAULT_OSDIR@ -INCDIR=../include -INCLUDES=-I$(INCDIR) -I$(DEFOSDIR) - -# DO NOT REMOVE diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.c b/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.c deleted file mode 100644 index abc5008c..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.c +++ /dev/null @@ -1,443 +0,0 @@ -/* 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_hash.h" - -#if APR_HAVE_STDLIB_H -#include <stdlib.h> -#endif -#if APR_HAVE_STRING_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 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; - 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; - ht = apr_palloc(pool, sizeof(apr_hash_t)); - ht->pool = pool; - ht->free = NULL; - ht->count = 0; - ht->max = INITIAL_MAX; - ht->array = alloc_array(ht, ht->max); - 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; -} - - -/* - * 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; -} - -/* - * 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; - const unsigned char *p; - unsigned int hash; - 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> - */ - hash = 0; - if (klen == APR_HASH_KEY_STRING) { - for (p = key; *p; p++) { - hash = hash * 33 + *p; - } - klen = p - (const unsigned char *)key; - } - else { - 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 */ - 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->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(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; - -#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 (!apr_pool_is_ancestor(overlay->pool, p)) { - fprintf(stderr, - "apr_hash_overlay: overlay's pool is not an ancestor of p\n"); - abort(); - } - if (!apr_pool_is_ancestor(base->pool, p)) { - fprintf(stderr, - "apr_hash_overlay: 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->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->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) { - i = iter->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 = iter->hash; - new_vals[j].next = res->array[i]; - res->array[i] = &new_vals[j]; - res->count++; - j++; - } - } - } - return res; -} - -APR_POOL_IMPLEMENT_ACCESSOR(hash) diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.lo b/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.lo deleted file mode 100644 index 94e4a9c1..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.lo +++ /dev/null @@ -1,12 +0,0 @@ -# apr_hash.lo - a libtool object file -# Generated by ltmain.sh - GNU libtool 1.5.26 (1.1220.2.493 2008/02/01 16:58:18) -# -# Please DO NOT delete this file! -# It is necessary for linking the library. - -# Name of the PIC object. -pic_object='.libs/apr_hash.o' - -# Name of the non-PIC object. -non_pic_object='apr_hash.o' - diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.o b/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.o Binary files differdeleted file mode 100644 index 04bd1950..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_hash.o +++ /dev/null diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.c b/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.c deleted file mode 100644 index 3f1f2edd..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.c +++ /dev/null @@ -1,1207 +0,0 @@ -#include <stdio.h> -/* 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 - -/***************************************************************** - * 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_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 & (1 << (i))) -#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (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: - * - Take the requested key and compute its checksum - * - Hash the checksum into the index: - * - index_first[TABLE_HASH(checksum)] is the offset within - * the table of the first entry with that key checksum - * - index_last[TABLE_HASH(checksum)] is the offset within - * the table of the first entry with that key checksum - * - If (and only if) there is no entry in the table whose - * checksum 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]; -}; - -/* - * 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 *table_push(apr_table_t *t) -{ - if (t->a.nelts == t->a.nalloc) { - return NULL; - } - return (apr_table_entry_t *) apr_array_push_noclear(&t->a); -} -#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)); - -#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 (!apr_pool_is_ancestor(t->a.pool, 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(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; -} - -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; - -#ifdef POOL_DEBUG - { - if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) { - fprintf(stderr, "table_set: key not in ancestor pool of t\n"); - abort(); - } - if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) { - fprintf(stderr, "table_set: 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; - -#ifdef POOL_DEBUG - { - if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) { - fprintf(stderr, "table_set: key not in ancestor pool of t\n"); - abort(); - } - if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) { - fprintf(stderr, "table_set: 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; - -#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 (!apr_pool_is_ancestor(overlay->a.pool, p)) { - fprintf(stderr, - "overlay_tables: overlay's pool is not an ancestor of p\n"); - abort(); - } - if (!apr_pool_is_ancestor(base->a.pool, p)) { - fprintf(stderr, - "overlay_tables: 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, int 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*)); - int i; - int 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; - int 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)) { - - int block1_start = next_start; - int block2_start = block1_start + blocksize; - int block1_end = block2_start; - int 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 (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 -= (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) -{ - const int m = a->a.nelts; - const int n = b->a.nelts; - apr_pool_t *p = b->a.pool; - - if (m + n == 0) { - return; - } - - /* copy (extend) a using b's pool */ - if (a->a.pool != p) { - make_array_core(&a->a, p, m+n, sizeof(apr_table_entry_t), 0); - } - - apr_table_cat(a, b); - - apr_table_compress(a, flags); -} diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.lo b/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.lo deleted file mode 100644 index a74bcd28..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.lo +++ /dev/null @@ -1,12 +0,0 @@ -# apr_tables.lo - a libtool object file -# Generated by ltmain.sh - GNU libtool 1.5.26 (1.1220.2.493 2008/02/01 16:58:18) -# -# Please DO NOT delete this file! -# It is necessary for linking the library. - -# Name of the PIC object. -pic_object='.libs/apr_tables.o' - -# Name of the non-PIC object. -non_pic_object='apr_tables.o' - diff --git a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.o b/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.o Binary files differdeleted file mode 100644 index 21b95695..00000000 --- a/rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.o +++ /dev/null |