1 /* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 * Resource allocation code... the code here is responsible for making
19 * sure that nothing leaks.
21 * rst --- 4/95 --- 6/95
24 #include "apr_private.h"
26 #include "apr_general.h"
27 #include "apr_pools.h"
28 #include "apr_tables.h"
29 #include "apr_strings.h"
37 #if APR_HAVE_STRINGS_H
41 #if (APR_POOL_DEBUG || defined(MAKE_TABLE_PROFILE)) && APR_HAVE_STDIO_H
45 /*****************************************************************
46 * This file contains array and apr_table_t functions only.
49 /*****************************************************************
51 * The 'array' functions...
54 static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
55 int nelts, int elt_size, int clear)
58 * Assure sanity if someone asks for
66 res->elts = apr_pcalloc(p, nelts * elt_size);
69 res->elts = apr_palloc(p, nelts * elt_size);
73 res->elt_size = elt_size;
74 res->nelts = 0; /* No active elements yet... */
75 res->nalloc = nelts; /* ...but this many allocated */
78 APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
80 return ((a == NULL) || (a->nelts == 0));
83 APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
84 int nelts, int elt_size)
86 apr_array_header_t *res;
88 res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
89 make_array_core(res, p, nelts, elt_size, 1);
93 APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
98 APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
100 if (apr_is_empty_array(arr)) {
104 return arr->elts + (arr->elt_size * (--arr->nelts));
107 APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
109 if (arr->nelts == arr->nalloc) {
110 int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
113 new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
115 memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
116 memset(new_data + arr->nalloc * arr->elt_size, 0,
117 arr->elt_size * (new_size - arr->nalloc));
118 arr->elts = new_data;
119 arr->nalloc = new_size;
123 return arr->elts + (arr->elt_size * (arr->nelts - 1));
126 static void *apr_array_push_noclear(apr_array_header_t *arr)
128 if (arr->nelts == arr->nalloc) {
129 int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
132 new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
134 memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
135 arr->elts = new_data;
136 arr->nalloc = new_size;
140 return arr->elts + (arr->elt_size * (arr->nelts - 1));
143 APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
144 const apr_array_header_t *src)
146 int elt_size = dst->elt_size;
148 if (dst->nelts + src->nelts > dst->nalloc) {
149 int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
152 while (dst->nelts + src->nelts > new_size) {
156 new_data = apr_pcalloc(dst->pool, elt_size * new_size);
157 memcpy(new_data, dst->elts, dst->nalloc * elt_size);
159 dst->elts = new_data;
160 dst->nalloc = new_size;
163 memcpy(dst->elts + dst->nelts * elt_size, src->elts,
164 elt_size * src->nelts);
165 dst->nelts += src->nelts;
168 APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
169 const apr_array_header_t *arr)
171 apr_array_header_t *res =
172 (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
173 make_array_core(res, p, arr->nalloc, arr->elt_size, 0);
175 memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
176 res->nelts = arr->nelts;
177 memset(res->elts + res->elt_size * res->nelts, 0,
178 res->elt_size * (res->nalloc - res->nelts));
182 /* This cute function copies the array header *only*, but arranges
183 * for the data section to be copied on the first push or arraycat.
184 * It's useful when the elements of the array being copied are
185 * read only, but new stuff *might* get added on the end; we have the
186 * overhead of the full copy only where it is really needed.
189 static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
190 const apr_array_header_t *arr)
192 res->elts = arr->elts;
193 res->elt_size = arr->elt_size;
194 res->nelts = arr->nelts;
195 res->nalloc = arr->nelts; /* Force overflow on push */
198 APR_DECLARE(apr_array_header_t *)
199 apr_array_copy_hdr(apr_pool_t *p,
200 const apr_array_header_t *arr)
202 apr_array_header_t *res;
204 res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
206 copy_array_hdr_core(res, arr);
210 /* The above is used here to avoid consing multiple new array bodies... */
212 APR_DECLARE(apr_array_header_t *)
213 apr_array_append(apr_pool_t *p,
214 const apr_array_header_t *first,
215 const apr_array_header_t *second)
217 apr_array_header_t *res = apr_array_copy_hdr(p, first);
219 apr_array_cat(res, second);
223 /* apr_array_pstrcat generates a new string from the apr_pool_t containing
224 * the concatenated sequence of substrings referenced as elements within
225 * the array. The string will be empty if all substrings are empty or null,
226 * or if there are no elements in the array.
227 * If sep is non-NUL, it will be inserted between elements as a separator.
229 APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
230 const apr_array_header_t *arr,
233 char *cp, *res, **strpp;
237 if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */
238 return (char *) apr_pcalloc(p, 1);
241 /* Pass one --- find length of required string */
244 for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
245 if (strpp && *strpp != NULL) {
246 len += strlen(*strpp);
248 if (++i >= arr->nelts) {
256 /* Allocate the required string */
258 res = (char *) apr_palloc(p, len + 1);
261 /* Pass two --- copy the argument strings into the result space */
263 for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
264 if (strpp && *strpp != NULL) {
265 len = strlen(*strpp);
266 memcpy(cp, *strpp, len);
269 if (++i >= arr->nelts) {
279 /* Return the result string */
285 /*****************************************************************
287 * The "table" functions.
290 #if APR_CHARSET_EBCDIC
291 #define CASE_MASK 0xbfbfbfbf
293 #define CASE_MASK 0xdfdfdfdf
296 #define TABLE_HASH_SIZE 32
297 #define TABLE_INDEX_MASK 0x1f
298 #define TABLE_HASH(key) (TABLE_INDEX_MASK & *(unsigned char *)(key))
299 #define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))
300 #define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i)))
302 /* Compute the "checksum" for a key, consisting of the first
303 * 4 bytes, normalized for case-insensitivity and packed into
304 * an int...this checksum allows us to do a single integer
305 * comparison as a fast check to determine whether we can
308 #define COMPUTE_KEY_CHECKSUM(key, checksum) \
310 const char *k = (key); \
311 apr_uint32_t c = (apr_uint32_t)*k; \
315 c = (apr_uint32_t)*++k; \
320 c = (apr_uint32_t)*++k; \
325 c = (apr_uint32_t)*++k; \
328 checksum &= CASE_MASK; \
331 /** The opaque string-content table type */
333 /* This has to be first to promote backwards compatibility with
334 * older modules which cast a apr_table_t * to an apr_array_header_t *...
335 * they should use the apr_table_elts() function for most of the
336 * cases they do this for.
338 /** The underlying array for the table */
339 apr_array_header_t a;
340 #ifdef MAKE_TABLE_PROFILE
341 /** Who created the array. */
344 /* An index to speed up table lookups. The way this works is:
345 * - Hash the key into the index:
346 * - index_first[TABLE_HASH(key)] is the offset within
347 * the table of the first entry with that key
348 * - index_last[TABLE_HASH(key)] is the offset within
349 * the table of the last entry with that key
350 * - If (and only if) there is no entry in the table whose
351 * key hashes to index element i, then the i'th bit
352 * of index_initialized will be zero. (Check this before
353 * trying to use index_first[i] or index_last[i]!)
355 apr_uint32_t index_initialized;
356 int index_first[TABLE_HASH_SIZE];
357 int index_last[TABLE_HASH_SIZE];
361 * NOTICE: if you tweak this you should look at is_empty_table()
362 * and table_elts() in alloc.h
364 #ifdef MAKE_TABLE_PROFILE
365 static apr_table_entry_t *do_table_push(const char *func, apr_table_t *t)
367 if (t->a.nelts == t->a.nalloc) {
368 fprintf(stderr, "%s: table created by %p hit limit of %u\n",
369 func ? func : "table_push", t->creator, t->a.nalloc);
371 return (apr_table_entry_t *) apr_array_push_noclear(&t->a);
373 #if defined(__GNUC__) && __GNUC__ >= 2
374 #define table_push(t) do_table_push(__FUNCTION__, t)
376 #define table_push(t) do_table_push(NULL, t)
378 #else /* MAKE_TABLE_PROFILE */
379 #define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
380 #endif /* MAKE_TABLE_PROFILE */
382 APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
384 return (const apr_array_header_t *)t;
387 APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
389 return ((t == NULL) || (t->a.nelts == 0));
392 APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
394 apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
396 make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);
397 #ifdef MAKE_TABLE_PROFILE
398 t->creator = __builtin_return_address(0);
400 t->index_initialized = 0;
404 APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
406 apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));
409 /* we don't copy keys and values, so it's necessary that t->a.pool
410 * have a life span at least as long as p
412 if (!apr_pool_is_ancestor(t->a.pool, p)) {
413 fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n");
417 make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
418 memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
419 new->a.nelts = t->a.nelts;
420 memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
421 memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
422 new->index_initialized = t->index_initialized;
426 APR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t)
428 const apr_array_header_t *array = apr_table_elts(t);
429 apr_table_entry_t *elts = (apr_table_entry_t *) array->elts;
430 apr_table_t *new = apr_table_make(p, array->nelts);
433 for (i = 0; i < array->nelts; i++) {
434 apr_table_add(new, elts[i].key, elts[i].val);
440 static void table_reindex(apr_table_t *t)
444 apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
446 t->index_initialized = 0;
447 for (i = 0; i < t->a.nelts; i++, next_elt++) {
448 hash = TABLE_HASH(next_elt->key);
449 t->index_last[hash] = i;
450 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
451 t->index_first[hash] = i;
452 TABLE_SET_INDEX_INITIALIZED(t, hash);
457 APR_DECLARE(void) apr_table_clear(apr_table_t *t)
460 t->index_initialized = 0;
463 APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
465 apr_table_entry_t *next_elt;
466 apr_table_entry_t *end_elt;
467 apr_uint32_t checksum;
474 hash = TABLE_HASH(key);
475 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
478 COMPUTE_KEY_CHECKSUM(key, checksum);
479 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
480 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
482 for (; next_elt <= end_elt; next_elt++) {
483 if ((checksum == next_elt->key_checksum) &&
484 !strcasecmp(next_elt->key, key)) {
485 return next_elt->val;
492 APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
495 apr_table_entry_t *next_elt;
496 apr_table_entry_t *end_elt;
497 apr_table_entry_t *table_end;
498 apr_uint32_t checksum;
501 COMPUTE_KEY_CHECKSUM(key, checksum);
502 hash = TABLE_HASH(key);
503 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
504 t->index_first[hash] = t->a.nelts;
505 TABLE_SET_INDEX_INITIALIZED(t, hash);
508 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
509 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
510 table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
512 for (; next_elt <= end_elt; next_elt++) {
513 if ((checksum == next_elt->key_checksum) &&
514 !strcasecmp(next_elt->key, key)) {
516 /* Found an existing entry with the same key, so overwrite it */
518 int must_reindex = 0;
519 apr_table_entry_t *dst_elt = NULL;
521 next_elt->val = apr_pstrdup(t->a.pool, val);
523 /* Remove any other instances of this key */
524 for (next_elt++; next_elt <= end_elt; next_elt++) {
525 if ((checksum == next_elt->key_checksum) &&
526 !strcasecmp(next_elt->key, key)) {
533 *dst_elt++ = *next_elt;
538 /* If we've removed anything, shift over the remainder
539 * of the table (note that the previous loop didn't
540 * run to the end of the table, just to the last match
544 for (; next_elt < table_end; next_elt++) {
545 *dst_elt++ = *next_elt;
557 t->index_last[hash] = t->a.nelts;
558 next_elt = (apr_table_entry_t *) table_push(t);
559 next_elt->key = apr_pstrdup(t->a.pool, key);
560 next_elt->val = apr_pstrdup(t->a.pool, val);
561 next_elt->key_checksum = checksum;
564 APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
567 apr_table_entry_t *next_elt;
568 apr_table_entry_t *end_elt;
569 apr_table_entry_t *table_end;
570 apr_uint32_t checksum;
573 COMPUTE_KEY_CHECKSUM(key, checksum);
574 hash = TABLE_HASH(key);
575 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
576 t->index_first[hash] = t->a.nelts;
577 TABLE_SET_INDEX_INITIALIZED(t, hash);
580 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
581 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
582 table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
584 for (; next_elt <= end_elt; next_elt++) {
585 if ((checksum == next_elt->key_checksum) &&
586 !strcasecmp(next_elt->key, key)) {
588 /* Found an existing entry with the same key, so overwrite it */
590 int must_reindex = 0;
591 apr_table_entry_t *dst_elt = NULL;
593 next_elt->val = (char *)val;
595 /* Remove any other instances of this key */
596 for (next_elt++; next_elt <= end_elt; next_elt++) {
597 if ((checksum == next_elt->key_checksum) &&
598 !strcasecmp(next_elt->key, key)) {
605 *dst_elt++ = *next_elt;
610 /* If we've removed anything, shift over the remainder
611 * of the table (note that the previous loop didn't
612 * run to the end of the table, just to the last match
616 for (; next_elt < table_end; next_elt++) {
617 *dst_elt++ = *next_elt;
629 t->index_last[hash] = t->a.nelts;
630 next_elt = (apr_table_entry_t *) table_push(t);
631 next_elt->key = (char *)key;
632 next_elt->val = (char *)val;
633 next_elt->key_checksum = checksum;
636 APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
638 apr_table_entry_t *next_elt;
639 apr_table_entry_t *end_elt;
640 apr_table_entry_t *dst_elt;
641 apr_uint32_t checksum;
645 hash = TABLE_HASH(key);
646 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
649 COMPUTE_KEY_CHECKSUM(key, checksum);
650 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
651 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
653 for (; next_elt <= end_elt; next_elt++) {
654 if ((checksum == next_elt->key_checksum) &&
655 !strcasecmp(next_elt->key, key)) {
657 /* Found a match: remove this entry, plus any additional
658 * matches for the same key that might follow
660 apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
664 for (next_elt++; next_elt <= end_elt; next_elt++) {
665 if ((checksum == next_elt->key_checksum) &&
666 !strcasecmp(next_elt->key, key)) {
670 *dst_elt++ = *next_elt;
674 /* Shift over the remainder of the table (note that
675 * the previous loop didn't run to the end of the table,
676 * just to the last match for the index)
678 for (; next_elt < table_end; next_elt++) {
679 *dst_elt++ = *next_elt;
690 APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
693 apr_table_entry_t *next_elt;
694 apr_table_entry_t *end_elt;
695 apr_uint32_t checksum;
698 COMPUTE_KEY_CHECKSUM(key, checksum);
699 hash = TABLE_HASH(key);
700 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
701 t->index_first[hash] = t->a.nelts;
702 TABLE_SET_INDEX_INITIALIZED(t, hash);
705 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
706 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
708 for (; next_elt <= end_elt; next_elt++) {
709 if ((checksum == next_elt->key_checksum) &&
710 !strcasecmp(next_elt->key, key)) {
712 /* Found an existing entry with the same key, so merge with it */
713 next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
720 t->index_last[hash] = t->a.nelts;
721 next_elt = (apr_table_entry_t *) table_push(t);
722 next_elt->key = apr_pstrdup(t->a.pool, key);
723 next_elt->val = apr_pstrdup(t->a.pool, val);
724 next_elt->key_checksum = checksum;
727 APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
730 apr_table_entry_t *next_elt;
731 apr_table_entry_t *end_elt;
732 apr_uint32_t checksum;
738 pool = apr_pool_find(key);
739 if ((pool != key) && (!apr_pool_is_ancestor(pool, t->a.pool))) {
740 fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
743 pool = apr_pool_find(val);
744 if ((pool != val) && (!apr_pool_is_ancestor(pool, t->a.pool))) {
745 fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n");
751 COMPUTE_KEY_CHECKSUM(key, checksum);
752 hash = TABLE_HASH(key);
753 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
754 t->index_first[hash] = t->a.nelts;
755 TABLE_SET_INDEX_INITIALIZED(t, hash);
758 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
759 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
761 for (; next_elt <= end_elt; next_elt++) {
762 if ((checksum == next_elt->key_checksum) &&
763 !strcasecmp(next_elt->key, key)) {
765 /* Found an existing entry with the same key, so merge with it */
766 next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
773 t->index_last[hash] = t->a.nelts;
774 next_elt = (apr_table_entry_t *) table_push(t);
775 next_elt->key = (char *)key;
776 next_elt->val = (char *)val;
777 next_elt->key_checksum = checksum;
780 APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
783 apr_table_entry_t *elts;
784 apr_uint32_t checksum;
787 hash = TABLE_HASH(key);
788 t->index_last[hash] = t->a.nelts;
789 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
790 t->index_first[hash] = t->a.nelts;
791 TABLE_SET_INDEX_INITIALIZED(t, hash);
793 COMPUTE_KEY_CHECKSUM(key, checksum);
794 elts = (apr_table_entry_t *) table_push(t);
795 elts->key = apr_pstrdup(t->a.pool, key);
796 elts->val = apr_pstrdup(t->a.pool, val);
797 elts->key_checksum = checksum;
800 APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
803 apr_table_entry_t *elts;
804 apr_uint32_t checksum;
809 if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
810 fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
813 if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
814 fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n");
820 hash = TABLE_HASH(key);
821 t->index_last[hash] = t->a.nelts;
822 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
823 t->index_first[hash] = t->a.nelts;
824 TABLE_SET_INDEX_INITIALIZED(t, hash);
826 COMPUTE_KEY_CHECKSUM(key, checksum);
827 elts = (apr_table_entry_t *) table_push(t);
828 elts->key = (char *)key;
829 elts->val = (char *)val;
830 elts->key_checksum = checksum;
833 APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
834 const apr_table_t *overlay,
835 const apr_table_t *base)
840 /* we don't copy keys and values, so it's necessary that
841 * overlay->a.pool and base->a.pool have a life span at least
844 if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
846 "apr_table_overlay: overlay's pool is not an ancestor of p\n");
849 if (!apr_pool_is_ancestor(base->a.pool, p)) {
851 "apr_table_overlay: base's pool is not an ancestor of p\n");
856 res = apr_palloc(p, sizeof(apr_table_t));
857 /* behave like append_arrays */
859 copy_array_hdr_core(&res->a, &overlay->a);
860 apr_array_cat(&res->a, &base->a);
865 /* And now for something completely abstract ...
867 * For each key value given as a vararg:
868 * run the function pointed to as
869 * int comp(void *r, char *key, char *value);
870 * on each valid key-value pair in the apr_table_t t that matches the vararg key,
871 * or once for every valid key-value pair if the vararg list is empty,
872 * until the function returns false (0) or we finish the table.
874 * Note that we restart the traversal for each vararg, which means that
875 * duplicate varargs will result in multiple executions of the function
876 * for each matching key. Note also that if the vararg list is empty,
877 * only one traversal will be made and will cut short if comp returns 0.
879 * Note that the table_get and table_merge functions assume that each key in
880 * the apr_table_t is unique (i.e., no multiple entries with the same key). This
881 * function does not make that assumption, since it (unfortunately) isn't
882 * true for some of Apache's tables.
884 * Note that rec is simply passed-on to the comp function, so that the
885 * caller can pass additional info for the task.
887 * ADDENDUM for apr_table_vdo():
889 * The caching api will allow a user to walk the header values:
891 * apr_status_t apr_cache_el_header_walk(apr_cache_el *el,
892 * int (*comp)(void *, const char *, const char *), void *rec, ...);
894 * So it can be ..., however from there I use a callback that use a va_list:
896 * apr_status_t (*cache_el_header_walk)(apr_cache_el *el,
897 * int (*comp)(void *, const char *, const char *), void *rec, va_list);
899 * To pass those ...'s on down to the actual module that will handle walking
900 * their headers, in the file case this is actually just an apr_table - and
901 * rather than reimplementing apr_table_do (which IMHO would be bad) I just
902 * called it with the va_list. For mod_shmem_cache I don't need it since I
903 * can't use apr_table's, but mod_file_cache should (though a good hash would
904 * be better, but that's a different issue :).
906 * So to make mod_file_cache easier to maintain, it's a good thing
908 APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
909 void *rec, const apr_table_t *t, ...)
915 rv = apr_table_vdo(comp, rec, t, vp);
921 /* XXX: do the semantics of this routine make any sense? Right now,
922 * if the caller passed in a non-empty va_list of keys to search for,
923 * the "early termination" facility only terminates on *that* key; other
924 * keys will continue to process. Note that this only has any effect
925 * at all if there are multiple entries in the table with the same key,
926 * otherwise the called function can never effectively early-terminate
927 * this function, as the zero return value is effectively ignored.
929 * Note also that this behavior is at odds with the behavior seen if an
930 * empty va_list is passed in -- in that case, a zero return value terminates
931 * the entire apr_table_vdo (which is what I think should happen in
934 * If nobody objects soon, I'm going to change the order of the nested
935 * loops in this function so that any zero return value from the (*comp)
936 * function will cause a full termination of apr_table_vdo. I'm hesitant
937 * at the moment because these (funky) semantics have been around for a
938 * very long time, and although Apache doesn't seem to use them at all,
939 * some third-party vendor might. I can only think of one possible reason
940 * the existing semantics would make any sense, and it's very Apache-centric,
941 * which is this: if (*comp) is looking for matches of a particular
942 * substring in request headers (let's say it's looking for a particular
943 * cookie name in the Set-Cookie headers), then maybe it wants to be
944 * able to stop searching early as soon as it finds that one and move
945 * on to the next key. That's only an optimization of course, but changing
946 * the behavior of this function would mean that any code that tried
947 * to do that would stop working right.
949 * Sigh. --JCW, 06/28/02
951 APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp,
952 void *rec, const apr_table_t *t, va_list vp)
955 apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
958 argp = va_arg(vp, char *);
962 /* Scan for entries that match the next key */
963 int hash = TABLE_HASH(argp);
964 if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
965 apr_uint32_t checksum;
966 COMPUTE_KEY_CHECKSUM(argp, checksum);
967 for (i = t->index_first[hash];
968 rv && (i <= t->index_last[hash]); ++i) {
969 if (elts[i].key && (checksum == elts[i].key_checksum) &&
970 !strcasecmp(elts[i].key, argp)) {
971 rv = (*comp) (rec, elts[i].key, elts[i].val);
977 /* Scan the entire table */
978 for (i = 0; rv && (i < t->a.nelts); ++i) {
980 rv = (*comp) (rec, elts[i].key, elts[i].val);
987 } while (argp && ((argp = va_arg(vp, char *)) != NULL));
992 static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
993 apr_table_entry_t **values,
996 /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
999 apr_table_entry_t **values_tmp =
1000 (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
1002 apr_size_t blocksize;
1004 /* First pass: sort pairs of elements (blocksize=1) */
1005 for (i = 0; i + 1 < n; i += 2) {
1006 if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
1007 apr_table_entry_t *swap = values[i];
1008 values[i] = values[i + 1];
1009 values[i + 1] = swap;
1013 /* Merge successively larger blocks */
1015 while (blocksize < n) {
1016 apr_table_entry_t **dst = values_tmp;
1017 apr_size_t next_start;
1018 apr_table_entry_t **swap;
1020 /* Merge consecutive pairs blocks of the next blocksize.
1021 * Within a block, elements are in sorted order due to
1022 * the previous iteration.
1024 for (next_start = 0; next_start + blocksize < n;
1025 next_start += (blocksize + blocksize)) {
1027 apr_size_t block1_start = next_start;
1028 apr_size_t block2_start = block1_start + blocksize;
1029 apr_size_t block1_end = block2_start;
1030 apr_size_t block2_end = block2_start + blocksize;
1031 if (block2_end > n) {
1032 /* The last block may be smaller than blocksize */
1037 /* Merge the next two blocks:
1038 * Pick the smaller of the next element from
1039 * block 1 and the next element from block 2.
1040 * Once either of the blocks is emptied, copy
1041 * over all the remaining elements from the
1044 if (block1_start == block1_end) {
1045 for (; block2_start < block2_end; block2_start++) {
1046 *dst++ = values[block2_start];
1050 else if (block2_start == block2_end) {
1051 for (; block1_start < block1_end; block1_start++) {
1052 *dst++ = values[block1_start];
1056 if (strcasecmp(values[block1_start]->key,
1057 values[block2_start]->key) > 0) {
1058 *dst++ = values[block2_start++];
1061 *dst++ = values[block1_start++];
1066 /* If n is not a multiple of 2*blocksize, some elements
1067 * will be left over at the end of the array.
1069 for (i = dst - values_tmp; i < n; i++) {
1070 values_tmp[i] = values[i];
1073 /* The output array of this pass becomes the input
1074 * array of the next pass, and vice versa
1077 values_tmp = values;
1080 blocksize += blocksize;
1086 APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
1088 apr_table_entry_t **sort_array;
1089 apr_table_entry_t **sort_next;
1090 apr_table_entry_t **sort_end;
1091 apr_table_entry_t *table_next;
1092 apr_table_entry_t **last;
1096 if (t->a.nelts <= 1) {
1100 /* Copy pointers to all the table elements into an
1101 * array and sort to allow for easy detection of
1104 sort_array = (apr_table_entry_t **)
1105 apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
1106 sort_next = sort_array;
1107 table_next = (apr_table_entry_t *)t->a.elts;
1110 *sort_next++ = table_next++;
1113 /* Note: the merge is done with mergesort instead of quicksort
1114 * because mergesort is a stable sort and runs in n*log(n)
1115 * time regardless of its inputs (quicksort is quadratic in
1118 sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
1120 /* Process any duplicate keys */
1122 sort_next = sort_array;
1123 sort_end = sort_array + t->a.nelts;
1125 while (sort_next < sort_end) {
1126 if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
1127 !strcasecmp((*sort_next)->key, (*last)->key)) {
1128 apr_table_entry_t **dup_last = sort_next + 1;
1130 while ((dup_last < sort_end) &&
1131 ((*dup_last)->key_checksum == (*last)->key_checksum) &&
1132 !strcasecmp((*dup_last)->key, (*last)->key)) {
1135 dup_last--; /* Elements from last through dup_last, inclusive,
1136 * all have the same key
1138 if (flags == APR_OVERLAP_TABLES_MERGE) {
1140 apr_table_entry_t **next = last;
1144 len += strlen((*next)->val);
1145 len += 2; /* for ", " or trailing null */
1146 } while (++next <= dup_last);
1147 new_val = (char *)apr_palloc(t->a.pool, len);
1151 strcpy(val_dst, (*next)->val);
1152 val_dst += strlen((*next)->val);
1154 if (next > dup_last) {
1163 (*last)->val = new_val;
1165 else { /* overwrite */
1166 (*last)->val = (*dup_last)->val;
1169 (*sort_next)->key = NULL;
1170 } while (++sort_next <= dup_last);
1177 /* Shift elements to the left to fill holes left by removing duplicates */
1179 apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
1180 apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
1181 apr_table_entry_t *last_elt = src + t->a.nelts;
1186 } while (++src < last_elt);
1187 t->a.nelts -= (int)(last_elt - dst);
1193 static void apr_table_cat(apr_table_t *t, const apr_table_t *s)
1195 const int n = t->a.nelts;
1198 apr_array_cat(&t->a,&s->a);
1201 memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
1202 memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
1203 t->index_initialized = s->index_initialized;
1207 for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
1208 if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
1209 t->index_last[idx] = s->index_last[idx] + n;
1210 if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
1211 t->index_first[idx] = s->index_first[idx] + n;
1216 t->index_initialized |= s->index_initialized;
1219 APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
1222 if (a->a.nelts + b->a.nelts == 0) {
1227 /* Since the keys and values are not copied, it's required that
1228 * b->a.pool has a lifetime at least as long as a->a.pool. */
1229 if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
1230 fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
1235 apr_table_cat(a, b);
1237 apr_table_compress(a, flags);