1
/* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
4
* Licensed under the Apache License, Version 2.0 (the "License");
5
* you may not use this file except in compliance with the License.
6
* 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 && 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_pop(apr_array_header_t *arr)
95
if (apr_is_empty_array(arr)) {
99
return arr->elts + (arr->elt_size * (--arr->nelts));
102
APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
104
if (arr->nelts == arr->nalloc) {
105
int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
108
new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
110
memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
111
memset(new_data + arr->nalloc * arr->elt_size, 0,
112
arr->elt_size * (new_size - arr->nalloc));
113
arr->elts = new_data;
114
arr->nalloc = new_size;
118
return arr->elts + (arr->elt_size * (arr->nelts - 1));
121
static void *apr_array_push_noclear(apr_array_header_t *arr)
123
if (arr->nelts == arr->nalloc) {
124
int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
127
new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
129
memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
130
arr->elts = new_data;
131
arr->nalloc = new_size;
135
return arr->elts + (arr->elt_size * (arr->nelts - 1));
138
APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
139
const apr_array_header_t *src)
141
int elt_size = dst->elt_size;
143
if (dst->nelts + src->nelts > dst->nalloc) {
144
int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
147
while (dst->nelts + src->nelts > new_size) {
151
new_data = apr_pcalloc(dst->pool, elt_size * new_size);
152
memcpy(new_data, dst->elts, dst->nalloc * elt_size);
154
dst->elts = new_data;
155
dst->nalloc = new_size;
158
memcpy(dst->elts + dst->nelts * elt_size, src->elts,
159
elt_size * src->nelts);
160
dst->nelts += src->nelts;
163
APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
164
const apr_array_header_t *arr)
166
apr_array_header_t *res =
167
(apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
168
make_array_core(res, p, arr->nalloc, arr->elt_size, 0);
170
memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
171
res->nelts = arr->nelts;
172
memset(res->elts + res->elt_size * res->nelts, 0,
173
res->elt_size * (res->nalloc - res->nelts));
177
/* This cute function copies the array header *only*, but arranges
178
* for the data section to be copied on the first push or arraycat.
179
* It's useful when the elements of the array being copied are
180
* read only, but new stuff *might* get added on the end; we have the
181
* overhead of the full copy only where it is really needed.
184
static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
185
const apr_array_header_t *arr)
187
res->elts = arr->elts;
188
res->elt_size = arr->elt_size;
189
res->nelts = arr->nelts;
190
res->nalloc = arr->nelts; /* Force overflow on push */
193
APR_DECLARE(apr_array_header_t *)
194
apr_array_copy_hdr(apr_pool_t *p,
195
const apr_array_header_t *arr)
197
apr_array_header_t *res;
199
res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
201
copy_array_hdr_core(res, arr);
205
/* The above is used here to avoid consing multiple new array bodies... */
207
APR_DECLARE(apr_array_header_t *)
208
apr_array_append(apr_pool_t *p,
209
const apr_array_header_t *first,
210
const apr_array_header_t *second)
212
apr_array_header_t *res = apr_array_copy_hdr(p, first);
214
apr_array_cat(res, second);
218
/* apr_array_pstrcat generates a new string from the apr_pool_t containing
219
* the concatenated sequence of substrings referenced as elements within
220
* the array. The string will be empty if all substrings are empty or null,
221
* or if there are no elements in the array.
222
* If sep is non-NUL, it will be inserted between elements as a separator.
224
APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
225
const apr_array_header_t *arr,
228
char *cp, *res, **strpp;
232
if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */
233
return (char *) apr_pcalloc(p, 1);
236
/* Pass one --- find length of required string */
239
for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
240
if (strpp && *strpp != NULL) {
241
len += strlen(*strpp);
243
if (++i >= arr->nelts) {
251
/* Allocate the required string */
253
res = (char *) apr_palloc(p, len + 1);
256
/* Pass two --- copy the argument strings into the result space */
258
for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
259
if (strpp && *strpp != NULL) {
260
len = strlen(*strpp);
261
memcpy(cp, *strpp, len);
264
if (++i >= arr->nelts) {
274
/* Return the result string */
280
/*****************************************************************
282
* The "table" functions.
285
#if APR_CHARSET_EBCDIC
286
#define CASE_MASK 0xbfbfbfbf
288
#define CASE_MASK 0xdfdfdfdf
291
#define TABLE_HASH_SIZE 32
292
#define TABLE_INDEX_MASK 0x1f
293
#define TABLE_HASH(key) (TABLE_INDEX_MASK & *(unsigned char *)(key))
294
#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))
295
#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i)))
297
/* Compute the "checksum" for a key, consisting of the first
298
* 4 bytes, normalized for case-insensitivity and packed into
299
* an int...this checksum allows us to do a single integer
300
* comparison as a fast check to determine whether we can
303
#define COMPUTE_KEY_CHECKSUM(key, checksum) \
305
const char *k = (key); \
306
apr_uint32_t c = (apr_uint32_t)*k; \
310
c = (apr_uint32_t)*++k; \
315
c = (apr_uint32_t)*++k; \
320
c = (apr_uint32_t)*++k; \
323
checksum &= CASE_MASK; \
326
/** The opaque string-content table type */
328
/* This has to be first to promote backwards compatibility with
329
* older modules which cast a apr_table_t * to an apr_array_header_t *...
330
* they should use the apr_table_elts() function for most of the
331
* cases they do this for.
333
/** The underlying array for the table */
334
apr_array_header_t a;
335
#ifdef MAKE_TABLE_PROFILE
336
/** Who created the array. */
339
/* An index to speed up table lookups. The way this works is:
340
* - Hash the key into the index:
341
* - index_first[TABLE_HASH(key)] is the offset within
342
* the table of the first entry with that key
343
* - index_last[TABLE_HASH(key)] is the offset within
344
* the table of the last entry with that key
345
* - If (and only if) there is no entry in the table whose
346
* key hashes to index element i, then the i'th bit
347
* of index_initialized will be zero. (Check this before
348
* trying to use index_first[i] or index_last[i]!)
350
apr_uint32_t index_initialized;
351
int index_first[TABLE_HASH_SIZE];
352
int index_last[TABLE_HASH_SIZE];
356
* NOTICE: if you tweak this you should look at is_empty_table()
357
* and table_elts() in alloc.h
359
#ifdef MAKE_TABLE_PROFILE
360
static apr_table_entry_t *table_push(apr_table_t *t)
362
if (t->a.nelts == t->a.nalloc) {
365
return (apr_table_entry_t *) apr_array_push_noclear(&t->a);
367
#else /* MAKE_TABLE_PROFILE */
368
#define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
369
#endif /* MAKE_TABLE_PROFILE */
371
APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
373
return (const apr_array_header_t *)t;
376
APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
378
return ((t == NULL) || (t->a.nelts == 0));
381
APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
383
apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
385
make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);
386
#ifdef MAKE_TABLE_PROFILE
387
t->creator = __builtin_return_address(0);
389
t->index_initialized = 0;
393
APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
395
apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));
398
/* we don't copy keys and values, so it's necessary that t->a.pool
399
* have a life span at least as long as p
401
if (!apr_pool_is_ancestor(t->a.pool, p)) {
402
fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n");
406
make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
407
memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
408
new->a.nelts = t->a.nelts;
409
memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
410
memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
411
new->index_initialized = t->index_initialized;
415
static void table_reindex(apr_table_t *t)
419
apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
421
t->index_initialized = 0;
422
for (i = 0; i < t->a.nelts; i++, next_elt++) {
423
hash = TABLE_HASH(next_elt->key);
424
t->index_last[hash] = i;
425
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
426
t->index_first[hash] = i;
427
TABLE_SET_INDEX_INITIALIZED(t, hash);
432
APR_DECLARE(void) apr_table_clear(apr_table_t *t)
435
t->index_initialized = 0;
438
APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
440
apr_table_entry_t *next_elt;
441
apr_table_entry_t *end_elt;
442
apr_uint32_t checksum;
449
hash = TABLE_HASH(key);
450
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
453
COMPUTE_KEY_CHECKSUM(key, checksum);
454
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
455
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
457
for (; next_elt <= end_elt; next_elt++) {
458
if ((checksum == next_elt->key_checksum) &&
459
!strcasecmp(next_elt->key, key)) {
460
return next_elt->val;
467
APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
470
apr_table_entry_t *next_elt;
471
apr_table_entry_t *end_elt;
472
apr_table_entry_t *table_end;
473
apr_uint32_t checksum;
476
COMPUTE_KEY_CHECKSUM(key, checksum);
477
hash = TABLE_HASH(key);
478
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
479
t->index_first[hash] = t->a.nelts;
480
TABLE_SET_INDEX_INITIALIZED(t, hash);
483
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
484
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
485
table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
487
for (; next_elt <= end_elt; next_elt++) {
488
if ((checksum == next_elt->key_checksum) &&
489
!strcasecmp(next_elt->key, key)) {
491
/* Found an existing entry with the same key, so overwrite it */
493
int must_reindex = 0;
494
apr_table_entry_t *dst_elt = NULL;
496
next_elt->val = apr_pstrdup(t->a.pool, val);
498
/* Remove any other instances of this key */
499
for (next_elt++; next_elt <= end_elt; next_elt++) {
500
if ((checksum == next_elt->key_checksum) &&
501
!strcasecmp(next_elt->key, key)) {
508
*dst_elt++ = *next_elt;
513
/* If we've removed anything, shift over the remainder
514
* of the table (note that the previous loop didn't
515
* run to the end of the table, just to the last match
519
for (; next_elt < table_end; next_elt++) {
520
*dst_elt++ = *next_elt;
532
t->index_last[hash] = t->a.nelts;
533
next_elt = (apr_table_entry_t *) table_push(t);
534
next_elt->key = apr_pstrdup(t->a.pool, key);
535
next_elt->val = apr_pstrdup(t->a.pool, val);
536
next_elt->key_checksum = checksum;
539
APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
542
apr_table_entry_t *next_elt;
543
apr_table_entry_t *end_elt;
544
apr_table_entry_t *table_end;
545
apr_uint32_t checksum;
548
COMPUTE_KEY_CHECKSUM(key, checksum);
549
hash = TABLE_HASH(key);
550
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
551
t->index_first[hash] = t->a.nelts;
552
TABLE_SET_INDEX_INITIALIZED(t, hash);
555
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
556
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
557
table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
559
for (; next_elt <= end_elt; next_elt++) {
560
if ((checksum == next_elt->key_checksum) &&
561
!strcasecmp(next_elt->key, key)) {
563
/* Found an existing entry with the same key, so overwrite it */
565
int must_reindex = 0;
566
apr_table_entry_t *dst_elt = NULL;
568
next_elt->val = (char *)val;
570
/* Remove any other instances of this key */
571
for (next_elt++; next_elt <= end_elt; next_elt++) {
572
if ((checksum == next_elt->key_checksum) &&
573
!strcasecmp(next_elt->key, key)) {
580
*dst_elt++ = *next_elt;
585
/* If we've removed anything, shift over the remainder
586
* of the table (note that the previous loop didn't
587
* run to the end of the table, just to the last match
591
for (; next_elt < table_end; next_elt++) {
592
*dst_elt++ = *next_elt;
604
t->index_last[hash] = t->a.nelts;
605
next_elt = (apr_table_entry_t *) table_push(t);
606
next_elt->key = (char *)key;
607
next_elt->val = (char *)val;
608
next_elt->key_checksum = checksum;
611
APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
613
apr_table_entry_t *next_elt;
614
apr_table_entry_t *end_elt;
615
apr_table_entry_t *dst_elt;
616
apr_uint32_t checksum;
620
hash = TABLE_HASH(key);
621
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
624
COMPUTE_KEY_CHECKSUM(key, checksum);
625
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
626
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
628
for (; next_elt <= end_elt; next_elt++) {
629
if ((checksum == next_elt->key_checksum) &&
630
!strcasecmp(next_elt->key, key)) {
632
/* Found a match: remove this entry, plus any additional
633
* matches for the same key that might follow
635
apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
639
for (next_elt++; next_elt <= end_elt; next_elt++) {
640
if ((checksum == next_elt->key_checksum) &&
641
!strcasecmp(next_elt->key, key)) {
645
*dst_elt++ = *next_elt;
649
/* Shift over the remainder of the table (note that
650
* the previous loop didn't run to the end of the table,
651
* just to the last match for the index)
653
for (; next_elt < table_end; next_elt++) {
654
*dst_elt++ = *next_elt;
665
APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
668
apr_table_entry_t *next_elt;
669
apr_table_entry_t *end_elt;
670
apr_uint32_t checksum;
673
COMPUTE_KEY_CHECKSUM(key, checksum);
674
hash = TABLE_HASH(key);
675
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
676
t->index_first[hash] = t->a.nelts;
677
TABLE_SET_INDEX_INITIALIZED(t, hash);
680
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
681
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
683
for (; next_elt <= end_elt; next_elt++) {
684
if ((checksum == next_elt->key_checksum) &&
685
!strcasecmp(next_elt->key, key)) {
687
/* Found an existing entry with the same key, so merge with it */
688
next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
695
t->index_last[hash] = t->a.nelts;
696
next_elt = (apr_table_entry_t *) table_push(t);
697
next_elt->key = apr_pstrdup(t->a.pool, key);
698
next_elt->val = apr_pstrdup(t->a.pool, val);
699
next_elt->key_checksum = checksum;
702
APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
705
apr_table_entry_t *next_elt;
706
apr_table_entry_t *end_elt;
707
apr_uint32_t checksum;
712
if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
713
fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
716
if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
717
fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
723
COMPUTE_KEY_CHECKSUM(key, checksum);
724
hash = TABLE_HASH(key);
725
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
726
t->index_first[hash] = t->a.nelts;
727
TABLE_SET_INDEX_INITIALIZED(t, hash);
730
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
731
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
733
for (; next_elt <= end_elt; next_elt++) {
734
if ((checksum == next_elt->key_checksum) &&
735
!strcasecmp(next_elt->key, key)) {
737
/* Found an existing entry with the same key, so merge with it */
738
next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
745
t->index_last[hash] = t->a.nelts;
746
next_elt = (apr_table_entry_t *) table_push(t);
747
next_elt->key = (char *)key;
748
next_elt->val = (char *)val;
749
next_elt->key_checksum = checksum;
752
APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
755
apr_table_entry_t *elts;
756
apr_uint32_t checksum;
759
hash = TABLE_HASH(key);
760
t->index_last[hash] = t->a.nelts;
761
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
762
t->index_first[hash] = t->a.nelts;
763
TABLE_SET_INDEX_INITIALIZED(t, hash);
765
COMPUTE_KEY_CHECKSUM(key, checksum);
766
elts = (apr_table_entry_t *) table_push(t);
767
elts->key = apr_pstrdup(t->a.pool, key);
768
elts->val = apr_pstrdup(t->a.pool, val);
769
elts->key_checksum = checksum;
772
APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
775
apr_table_entry_t *elts;
776
apr_uint32_t checksum;
781
if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
782
fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
785
if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
786
fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
792
hash = TABLE_HASH(key);
793
t->index_last[hash] = t->a.nelts;
794
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
795
t->index_first[hash] = t->a.nelts;
796
TABLE_SET_INDEX_INITIALIZED(t, hash);
798
COMPUTE_KEY_CHECKSUM(key, checksum);
799
elts = (apr_table_entry_t *) table_push(t);
800
elts->key = (char *)key;
801
elts->val = (char *)val;
802
elts->key_checksum = checksum;
805
APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
806
const apr_table_t *overlay,
807
const apr_table_t *base)
812
/* we don't copy keys and values, so it's necessary that
813
* overlay->a.pool and base->a.pool have a life span at least
816
if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
818
"apr_table_overlay: overlay's pool is not an ancestor of p\n");
821
if (!apr_pool_is_ancestor(base->a.pool, p)) {
823
"apr_table_overlay: base's pool is not an ancestor of p\n");
828
res = apr_palloc(p, sizeof(apr_table_t));
829
/* behave like append_arrays */
831
copy_array_hdr_core(&res->a, &overlay->a);
832
apr_array_cat(&res->a, &base->a);
837
/* And now for something completely abstract ...
839
* For each key value given as a vararg:
840
* run the function pointed to as
841
* int comp(void *r, char *key, char *value);
842
* on each valid key-value pair in the apr_table_t t that matches the vararg key,
843
* or once for every valid key-value pair if the vararg list is empty,
844
* until the function returns false (0) or we finish the table.
846
* Note that we restart the traversal for each vararg, which means that
847
* duplicate varargs will result in multiple executions of the function
848
* for each matching key. Note also that if the vararg list is empty,
849
* only one traversal will be made and will cut short if comp returns 0.
851
* Note that the table_get and table_merge functions assume that each key in
852
* the apr_table_t is unique (i.e., no multiple entries with the same key). This
853
* function does not make that assumption, since it (unfortunately) isn't
854
* true for some of Apache's tables.
856
* Note that rec is simply passed-on to the comp function, so that the
857
* caller can pass additional info for the task.
859
* ADDENDUM for apr_table_vdo():
861
* The caching api will allow a user to walk the header values:
863
* apr_status_t apr_cache_el_header_walk(apr_cache_el *el,
864
* int (*comp)(void *, const char *, const char *), void *rec, ...);
866
* So it can be ..., however from there I use a callback that use a va_list:
868
* apr_status_t (*cache_el_header_walk)(apr_cache_el *el,
869
* int (*comp)(void *, const char *, const char *), void *rec, va_list);
871
* To pass those ...'s on down to the actual module that will handle walking
872
* their headers, in the file case this is actually just an apr_table - and
873
* rather than reimplementing apr_table_do (which IMHO would be bad) I just
874
* called it with the va_list. For mod_shmem_cache I don't need it since I
875
* can't use apr_table's, but mod_file_cache should (though a good hash would
876
* be better, but that's a different issue :).
878
* So to make mod_file_cache easier to maintain, it's a good thing
880
APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
881
void *rec, const apr_table_t *t, ...)
887
rv = apr_table_vdo(comp, rec, t, vp);
893
/* XXX: do the semantics of this routine make any sense? Right now,
894
* if the caller passed in a non-empty va_list of keys to search for,
895
* the "early termination" facility only terminates on *that* key; other
896
* keys will continue to process. Note that this only has any effect
897
* at all if there are multiple entries in the table with the same key,
898
* otherwise the called function can never effectively early-terminate
899
* this function, as the zero return value is effectively ignored.
901
* Note also that this behavior is at odds with the behavior seen if an
902
* empty va_list is passed in -- in that case, a zero return value terminates
903
* the entire apr_table_vdo (which is what I think should happen in
906
* If nobody objects soon, I'm going to change the order of the nested
907
* loops in this function so that any zero return value from the (*comp)
908
* function will cause a full termination of apr_table_vdo. I'm hesitant
909
* at the moment because these (funky) semantics have been around for a
910
* very long time, and although Apache doesn't seem to use them at all,
911
* some third-party vendor might. I can only think of one possible reason
912
* the existing semantics would make any sense, and it's very Apache-centric,
913
* which is this: if (*comp) is looking for matches of a particular
914
* substring in request headers (let's say it's looking for a particular
915
* cookie name in the Set-Cookie headers), then maybe it wants to be
916
* able to stop searching early as soon as it finds that one and move
917
* on to the next key. That's only an optimization of course, but changing
918
* the behavior of this function would mean that any code that tried
919
* to do that would stop working right.
921
* Sigh. --JCW, 06/28/02
923
APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp,
924
void *rec, const apr_table_t *t, va_list vp)
927
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
930
argp = va_arg(vp, char *);
934
/* Scan for entries that match the next key */
935
int hash = TABLE_HASH(argp);
936
if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
937
apr_uint32_t checksum;
938
COMPUTE_KEY_CHECKSUM(argp, checksum);
939
for (i = t->index_first[hash];
940
rv && (i <= t->index_last[hash]); ++i) {
941
if (elts[i].key && (checksum == elts[i].key_checksum) &&
942
!strcasecmp(elts[i].key, argp)) {
943
rv = (*comp) (rec, elts[i].key, elts[i].val);
949
/* Scan the entire table */
950
for (i = 0; rv && (i < t->a.nelts); ++i) {
952
rv = (*comp) (rec, elts[i].key, elts[i].val);
959
} while (argp && ((argp = va_arg(vp, char *)) != NULL));
964
static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
965
apr_table_entry_t **values,
968
/* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
971
apr_table_entry_t **values_tmp =
972
(apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
974
apr_size_t blocksize;
976
/* First pass: sort pairs of elements (blocksize=1) */
977
for (i = 0; i + 1 < n; i += 2) {
978
if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
979
apr_table_entry_t *swap = values[i];
980
values[i] = values[i + 1];
981
values[i + 1] = swap;
985
/* Merge successively larger blocks */
987
while (blocksize < n) {
988
apr_table_entry_t **dst = values_tmp;
989
apr_size_t next_start;
990
apr_table_entry_t **swap;
992
/* Merge consecutive pairs blocks of the next blocksize.
993
* Within a block, elements are in sorted order due to
994
* the previous iteration.
996
for (next_start = 0; next_start + blocksize < n;
997
next_start += (blocksize + blocksize)) {
999
apr_size_t block1_start = next_start;
1000
apr_size_t block2_start = block1_start + blocksize;
1001
apr_size_t block1_end = block2_start;
1002
apr_size_t block2_end = block2_start + blocksize;
1003
if (block2_end > n) {
1004
/* The last block may be smaller than blocksize */
1009
/* Merge the next two blocks:
1010
* Pick the smaller of the next element from
1011
* block 1 and the next element from block 2.
1012
* Once either of the blocks is emptied, copy
1013
* over all the remaining elements from the
1016
if (block1_start == block1_end) {
1017
for (; block2_start < block2_end; block2_start++) {
1018
*dst++ = values[block2_start];
1022
else if (block2_start == block2_end) {
1023
for (; block1_start < block1_end; block1_start++) {
1024
*dst++ = values[block1_start];
1028
if (strcasecmp(values[block1_start]->key,
1029
values[block2_start]->key) > 0) {
1030
*dst++ = values[block2_start++];
1033
*dst++ = values[block1_start++];
1038
/* If n is not a multiple of 2*blocksize, some elements
1039
* will be left over at the end of the array.
1041
for (i = dst - values_tmp; i < n; i++) {
1042
values_tmp[i] = values[i];
1045
/* The output array of this pass becomes the input
1046
* array of the next pass, and vice versa
1049
values_tmp = values;
1052
blocksize += blocksize;
1058
APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
1060
apr_table_entry_t **sort_array;
1061
apr_table_entry_t **sort_next;
1062
apr_table_entry_t **sort_end;
1063
apr_table_entry_t *table_next;
1064
apr_table_entry_t **last;
1068
if (t->a.nelts <= 1) {
1072
/* Copy pointers to all the table elements into an
1073
* array and sort to allow for easy detection of
1076
sort_array = (apr_table_entry_t **)
1077
apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
1078
sort_next = sort_array;
1079
table_next = (apr_table_entry_t *)t->a.elts;
1082
*sort_next++ = table_next++;
1085
/* Note: the merge is done with mergesort instead of quicksort
1086
* because mergesort is a stable sort and runs in n*log(n)
1087
* time regardless of its inputs (quicksort is quadratic in
1090
sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
1092
/* Process any duplicate keys */
1094
sort_next = sort_array;
1095
sort_end = sort_array + t->a.nelts;
1097
while (sort_next < sort_end) {
1098
if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
1099
!strcasecmp((*sort_next)->key, (*last)->key)) {
1100
apr_table_entry_t **dup_last = sort_next + 1;
1102
while ((dup_last < sort_end) &&
1103
((*dup_last)->key_checksum == (*last)->key_checksum) &&
1104
!strcasecmp((*dup_last)->key, (*last)->key)) {
1107
dup_last--; /* Elements from last through dup_last, inclusive,
1108
* all have the same key
1110
if (flags == APR_OVERLAP_TABLES_MERGE) {
1112
apr_table_entry_t **next = last;
1116
len += strlen((*next)->val);
1117
len += 2; /* for ", " or trailing null */
1118
} while (++next <= dup_last);
1119
new_val = (char *)apr_palloc(t->a.pool, len);
1123
strcpy(val_dst, (*next)->val);
1124
val_dst += strlen((*next)->val);
1126
if (next > dup_last) {
1135
(*last)->val = new_val;
1137
else { /* overwrite */
1138
(*last)->val = (*dup_last)->val;
1141
(*sort_next)->key = NULL;
1142
} while (++sort_next <= dup_last);
1149
/* Shift elements to the left to fill holes left by removing duplicates */
1151
apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
1152
apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
1153
apr_table_entry_t *last_elt = src + t->a.nelts;
1158
} while (++src < last_elt);
1159
t->a.nelts -= (int)(last_elt - dst);
1165
static void apr_table_cat(apr_table_t *t, const apr_table_t *s)
1167
const int n = t->a.nelts;
1170
apr_array_cat(&t->a,&s->a);
1173
memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
1174
memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
1175
t->index_initialized = s->index_initialized;
1179
for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
1180
if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
1181
t->index_last[idx] = s->index_last[idx] + n;
1182
if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
1183
t->index_first[idx] = s->index_first[idx] + n;
1188
t->index_initialized |= s->index_initialized;
1191
APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
1194
if (a->a.nelts + b->a.nelts == 0) {
1199
/* Since the keys and values are not copied, it's required that
1200
* b->a.pool has a lifetime at least as long as a->a.pool. */
1201
if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
1202
fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
1207
apr_table_cat(a, b);
1209
apr_table_compress(a, flags);
added
removed
srclib/apr/tables/apr_tables.c
