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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17 /*
18 * Resource allocation code... the code here is responsible for making
19 * sure that nothing leaks.
20 *
21 * rst --- 4/95 --- 6/95
22 */
23
24 #include "apr_private.h"
25
26 #include "apr_general.h"
27 #include "apr_pools.h"
28 #include "apr_tables.h"
29 #include "apr_strings.h"
30 #include "apr_lib.h"
31 #if APR_HAVE_STDLIB_H
32 #include <stdlib.h>
33 #endif
34 #if APR_HAVE_STRING_H
35 #include <string.h>
36 #endif
37 #if APR_HAVE_STRINGS_H
38 #include <strings.h>
39 #endif
40
41 #if (APR_POOL_DEBUG || defined(MAKE_TABLE_PROFILE)) && APR_HAVE_STDIO_H
42 #include <stdio.h>
43 #endif
44
45 /*****************************************************************
46 * This file contains array and apr_table_t functions only.
47 */
48
49 /*****************************************************************
50 *
51 * The 'array' functions...
52 */
53
make_array_core(apr_array_header_t * res,apr_pool_t * p,int nelts,int elt_size,int clear)54 static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
55 int nelts, int elt_size, int clear)
56 {
57 /*
58 * Assure sanity if someone asks for
59 * array of zero elts.
60 */
61 if (nelts < 1) {
62 nelts = 1;
63 }
64
65 if (clear) {
66 res->elts = apr_pcalloc(p, nelts * elt_size);
67 }
68 else {
69 res->elts = apr_palloc(p, nelts * elt_size);
70 }
71
72 res->pool = p;
73 res->elt_size = elt_size;
74 res->nelts = 0; /* No active elements yet... */
75 res->nalloc = nelts; /* ...but this many allocated */
76 }
77
apr_is_empty_array(const apr_array_header_t * a)78 APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
79 {
80 return ((a == NULL) || (a->nelts == 0));
81 }
82
apr_array_make(apr_pool_t * p,int nelts,int elt_size)83 APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
84 int nelts, int elt_size)
85 {
86 apr_array_header_t *res;
87
88 res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
89 make_array_core(res, p, nelts, elt_size, 1);
90 return res;
91 }
92
apr_array_clear(apr_array_header_t * arr)93 APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
94 {
95 arr->nelts = 0;
96 }
97
apr_array_pop(apr_array_header_t * arr)98 APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
99 {
100 if (apr_is_empty_array(arr)) {
101 return NULL;
102 }
103
104 return arr->elts + (arr->elt_size * (--arr->nelts));
105 }
106
apr_array_push(apr_array_header_t * arr)107 APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
108 {
109 if (arr->nelts == arr->nalloc) {
110 int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
111 char *new_data;
112
113 new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
114
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;
120 }
121
122 ++arr->nelts;
123 return arr->elts + (arr->elt_size * (arr->nelts - 1));
124 }
125
apr_array_push_noclear(apr_array_header_t * arr)126 static void *apr_array_push_noclear(apr_array_header_t *arr)
127 {
128 if (arr->nelts == arr->nalloc) {
129 int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
130 char *new_data;
131
132 new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
133
134 memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
135 arr->elts = new_data;
136 arr->nalloc = new_size;
137 }
138
139 ++arr->nelts;
140 return arr->elts + (arr->elt_size * (arr->nelts - 1));
141 }
142
apr_array_cat(apr_array_header_t * dst,const apr_array_header_t * src)143 APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
144 const apr_array_header_t *src)
145 {
146 int elt_size = dst->elt_size;
147
148 if (dst->nelts + src->nelts > dst->nalloc) {
149 int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
150 char *new_data;
151
152 while (dst->nelts + src->nelts > new_size) {
153 new_size *= 2;
154 }
155
156 new_data = apr_pcalloc(dst->pool, elt_size * new_size);
157 memcpy(new_data, dst->elts, dst->nalloc * elt_size);
158
159 dst->elts = new_data;
160 dst->nalloc = new_size;
161 }
162
163 memcpy(dst->elts + dst->nelts * elt_size, src->elts,
164 elt_size * src->nelts);
165 dst->nelts += src->nelts;
166 }
167
apr_array_copy(apr_pool_t * p,const apr_array_header_t * arr)168 APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
169 const apr_array_header_t *arr)
170 {
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);
174
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));
179 return res;
180 }
181
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.
187 */
188
copy_array_hdr_core(apr_array_header_t * res,const apr_array_header_t * arr)189 static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
190 const apr_array_header_t *arr)
191 {
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 */
196 }
197
198 APR_DECLARE(apr_array_header_t *)
apr_array_copy_hdr(apr_pool_t * p,const apr_array_header_t * arr)199 apr_array_copy_hdr(apr_pool_t *p,
200 const apr_array_header_t *arr)
201 {
202 apr_array_header_t *res;
203
204 res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
205 res->pool = p;
206 copy_array_hdr_core(res, arr);
207 return res;
208 }
209
210 /* The above is used here to avoid consing multiple new array bodies... */
211
212 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)213 apr_array_append(apr_pool_t *p,
214 const apr_array_header_t *first,
215 const apr_array_header_t *second)
216 {
217 apr_array_header_t *res = apr_array_copy_hdr(p, first);
218
219 apr_array_cat(res, second);
220 return res;
221 }
222
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.
228 */
apr_array_pstrcat(apr_pool_t * p,const apr_array_header_t * arr,const char sep)229 APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
230 const apr_array_header_t *arr,
231 const char sep)
232 {
233 char *cp, *res, **strpp;
234 apr_size_t len;
235 int i;
236
237 if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */
238 return (char *) apr_pcalloc(p, 1);
239 }
240
241 /* Pass one --- find length of required string */
242
243 len = 0;
244 for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
245 if (strpp && *strpp != NULL) {
246 len += strlen(*strpp);
247 }
248 if (++i >= arr->nelts) {
249 break;
250 }
251 if (sep) {
252 ++len;
253 }
254 }
255
256 /* Allocate the required string */
257
258 res = (char *) apr_palloc(p, len + 1);
259 cp = res;
260
261 /* Pass two --- copy the argument strings into the result space */
262
263 for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
264 if (strpp && *strpp != NULL) {
265 len = strlen(*strpp);
266 memcpy(cp, *strpp, len);
267 cp += len;
268 }
269 if (++i >= arr->nelts) {
270 break;
271 }
272 if (sep) {
273 *cp++ = sep;
274 }
275 }
276
277 *cp = '\0';
278
279 /* Return the result string */
280
281 return res;
282 }
283
284
285 /*****************************************************************
286 *
287 * The "table" functions.
288 */
289
290 #if APR_CHARSET_EBCDIC
291 #define CASE_MASK 0xbfbfbfbf
292 #else
293 #define CASE_MASK 0xdfdfdfdf
294 #endif
295
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)))
301
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
306 * skip a strcasecmp
307 */
308 #define COMPUTE_KEY_CHECKSUM(key, checksum) \
309 { \
310 const char *k = (key); \
311 apr_uint32_t c = (apr_uint32_t)*k; \
312 (checksum) = c; \
313 (checksum) <<= 8; \
314 if (c) { \
315 c = (apr_uint32_t)*++k; \
316 checksum |= c; \
317 } \
318 (checksum) <<= 8; \
319 if (c) { \
320 c = (apr_uint32_t)*++k; \
321 checksum |= c; \
322 } \
323 (checksum) <<= 8; \
324 if (c) { \
325 c = (apr_uint32_t)*++k; \
326 checksum |= c; \
327 } \
328 checksum &= CASE_MASK; \
329 }
330
331 /** The opaque string-content table type */
332 struct apr_table_t {
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.
337 */
338 /** The underlying array for the table */
339 apr_array_header_t a;
340 #ifdef MAKE_TABLE_PROFILE
341 /** Who created the array. */
342 void *creator;
343 #endif
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]!)
354 */
355 apr_uint32_t index_initialized;
356 int index_first[TABLE_HASH_SIZE];
357 int index_last[TABLE_HASH_SIZE];
358 };
359
360 /* keep state for apr_table_getm() */
361 typedef struct
362 {
363 apr_pool_t *p;
364 const char *first;
365 apr_array_header_t *merged;
366 } table_getm_t;
367
368 /*
369 * NOTICE: if you tweak this you should look at is_empty_table()
370 * and table_elts() in alloc.h
371 */
372 #ifdef MAKE_TABLE_PROFILE
do_table_push(const char * func,apr_table_t * t)373 static apr_table_entry_t *do_table_push(const char *func, apr_table_t *t)
374 {
375 if (t->a.nelts == t->a.nalloc) {
376 fprintf(stderr, "%s: table created by %p hit limit of %u\n",
377 func ? func : "table_push", t->creator, t->a.nalloc);
378 }
379 return (apr_table_entry_t *) apr_array_push_noclear(&t->a);
380 }
381 #if defined(__GNUC__) && __GNUC__ >= 2
382 #define table_push(t) do_table_push(__FUNCTION__, t)
383 #else
384 #define table_push(t) do_table_push(NULL, t)
385 #endif
386 #else /* MAKE_TABLE_PROFILE */
387 #define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
388 #endif /* MAKE_TABLE_PROFILE */
389
apr_table_elts(const apr_table_t * t)390 APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
391 {
392 return (const apr_array_header_t *)t;
393 }
394
apr_is_empty_table(const apr_table_t * t)395 APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
396 {
397 return ((t == NULL) || (t->a.nelts == 0));
398 }
399
apr_table_make(apr_pool_t * p,int nelts)400 APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
401 {
402 apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
403
404 make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);
405 #ifdef MAKE_TABLE_PROFILE
406 t->creator = __builtin_return_address(0);
407 #endif
408 t->index_initialized = 0;
409 return t;
410 }
411
apr_table_copy(apr_pool_t * p,const apr_table_t * t)412 APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
413 {
414 apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));
415
416 #if APR_POOL_DEBUG
417 /* we don't copy keys and values, so it's necessary that t->a.pool
418 * have a life span at least as long as p
419 */
420 if (!apr_pool_is_ancestor(t->a.pool, p)) {
421 fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n");
422 abort();
423 }
424 #endif
425 make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
426 memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
427 new->a.nelts = t->a.nelts;
428 memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
429 memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
430 new->index_initialized = t->index_initialized;
431 return new;
432 }
433
apr_table_clone(apr_pool_t * p,const apr_table_t * t)434 APR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t)
435 {
436 const apr_array_header_t *array = apr_table_elts(t);
437 apr_table_entry_t *elts = (apr_table_entry_t *) array->elts;
438 apr_table_t *new = apr_table_make(p, array->nelts);
439 int i;
440
441 for (i = 0; i < array->nelts; i++) {
442 apr_table_add(new, elts[i].key, elts[i].val);
443 }
444
445 return new;
446 }
447
table_reindex(apr_table_t * t)448 static void table_reindex(apr_table_t *t)
449 {
450 int i;
451 int hash;
452 apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
453
454 t->index_initialized = 0;
455 for (i = 0; i < t->a.nelts; i++, next_elt++) {
456 hash = TABLE_HASH(next_elt->key);
457 t->index_last[hash] = i;
458 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
459 t->index_first[hash] = i;
460 TABLE_SET_INDEX_INITIALIZED(t, hash);
461 }
462 }
463 }
464
apr_table_clear(apr_table_t * t)465 APR_DECLARE(void) apr_table_clear(apr_table_t *t)
466 {
467 t->a.nelts = 0;
468 t->index_initialized = 0;
469 }
470
apr_table_get(const apr_table_t * t,const char * key)471 APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
472 {
473 apr_table_entry_t *next_elt;
474 apr_table_entry_t *end_elt;
475 apr_uint32_t checksum;
476 int hash;
477
478 if (key == NULL) {
479 return NULL;
480 }
481
482 hash = TABLE_HASH(key);
483 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
484 return NULL;
485 }
486 COMPUTE_KEY_CHECKSUM(key, checksum);
487 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
488 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
489
490 for (; next_elt <= end_elt; next_elt++) {
491 if ((checksum == next_elt->key_checksum) &&
492 !strcasecmp(next_elt->key, key)) {
493 return next_elt->val;
494 }
495 }
496
497 return NULL;
498 }
499
apr_table_set(apr_table_t * t,const char * key,const char * val)500 APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
501 const char *val)
502 {
503 apr_table_entry_t *next_elt;
504 apr_table_entry_t *end_elt;
505 apr_table_entry_t *table_end;
506 apr_uint32_t checksum;
507 int hash;
508
509 COMPUTE_KEY_CHECKSUM(key, checksum);
510 hash = TABLE_HASH(key);
511 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
512 t->index_first[hash] = t->a.nelts;
513 TABLE_SET_INDEX_INITIALIZED(t, hash);
514 goto add_new_elt;
515 }
516 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
517 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
518 table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
519
520 for (; next_elt <= end_elt; next_elt++) {
521 if ((checksum == next_elt->key_checksum) &&
522 !strcasecmp(next_elt->key, key)) {
523
524 /* Found an existing entry with the same key, so overwrite it */
525
526 int must_reindex = 0;
527 apr_table_entry_t *dst_elt = NULL;
528
529 next_elt->val = apr_pstrdup(t->a.pool, val);
530
531 /* Remove any other instances of this key */
532 for (next_elt++; next_elt <= end_elt; next_elt++) {
533 if ((checksum == next_elt->key_checksum) &&
534 !strcasecmp(next_elt->key, key)) {
535 t->a.nelts--;
536 if (!dst_elt) {
537 dst_elt = next_elt;
538 }
539 }
540 else if (dst_elt) {
541 *dst_elt++ = *next_elt;
542 must_reindex = 1;
543 }
544 }
545
546 /* If we've removed anything, shift over the remainder
547 * of the table (note that the previous loop didn't
548 * run to the end of the table, just to the last match
549 * for the index)
550 */
551 if (dst_elt) {
552 for (; next_elt < table_end; next_elt++) {
553 *dst_elt++ = *next_elt;
554 }
555 must_reindex = 1;
556 }
557 if (must_reindex) {
558 table_reindex(t);
559 }
560 return;
561 }
562 }
563
564 add_new_elt:
565 t->index_last[hash] = t->a.nelts;
566 next_elt = (apr_table_entry_t *) table_push(t);
567 next_elt->key = apr_pstrdup(t->a.pool, key);
568 next_elt->val = apr_pstrdup(t->a.pool, val);
569 next_elt->key_checksum = checksum;
570 }
571
apr_table_setn(apr_table_t * t,const char * key,const char * val)572 APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
573 const char *val)
574 {
575 apr_table_entry_t *next_elt;
576 apr_table_entry_t *end_elt;
577 apr_table_entry_t *table_end;
578 apr_uint32_t checksum;
579 int hash;
580
581 COMPUTE_KEY_CHECKSUM(key, checksum);
582 hash = TABLE_HASH(key);
583 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
584 t->index_first[hash] = t->a.nelts;
585 TABLE_SET_INDEX_INITIALIZED(t, hash);
586 goto add_new_elt;
587 }
588 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
589 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
590 table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
591
592 for (; next_elt <= end_elt; next_elt++) {
593 if ((checksum == next_elt->key_checksum) &&
594 !strcasecmp(next_elt->key, key)) {
595
596 /* Found an existing entry with the same key, so overwrite it */
597
598 int must_reindex = 0;
599 apr_table_entry_t *dst_elt = NULL;
600
601 next_elt->val = (char *)val;
602
603 /* Remove any other instances of this key */
604 for (next_elt++; next_elt <= end_elt; next_elt++) {
605 if ((checksum == next_elt->key_checksum) &&
606 !strcasecmp(next_elt->key, key)) {
607 t->a.nelts--;
608 if (!dst_elt) {
609 dst_elt = next_elt;
610 }
611 }
612 else if (dst_elt) {
613 *dst_elt++ = *next_elt;
614 must_reindex = 1;
615 }
616 }
617
618 /* If we've removed anything, shift over the remainder
619 * of the table (note that the previous loop didn't
620 * run to the end of the table, just to the last match
621 * for the index)
622 */
623 if (dst_elt) {
624 for (; next_elt < table_end; next_elt++) {
625 *dst_elt++ = *next_elt;
626 }
627 must_reindex = 1;
628 }
629 if (must_reindex) {
630 table_reindex(t);
631 }
632 return;
633 }
634 }
635
636 add_new_elt:
637 t->index_last[hash] = t->a.nelts;
638 next_elt = (apr_table_entry_t *) table_push(t);
639 next_elt->key = (char *)key;
640 next_elt->val = (char *)val;
641 next_elt->key_checksum = checksum;
642 }
643
apr_table_unset(apr_table_t * t,const char * key)644 APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
645 {
646 apr_table_entry_t *next_elt;
647 apr_table_entry_t *end_elt;
648 apr_table_entry_t *dst_elt;
649 apr_uint32_t checksum;
650 int hash;
651 int must_reindex;
652
653 hash = TABLE_HASH(key);
654 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
655 return;
656 }
657 COMPUTE_KEY_CHECKSUM(key, checksum);
658 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
659 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
660 must_reindex = 0;
661 for (; next_elt <= end_elt; next_elt++) {
662 if ((checksum == next_elt->key_checksum) &&
663 !strcasecmp(next_elt->key, key)) {
664
665 /* Found a match: remove this entry, plus any additional
666 * matches for the same key that might follow
667 */
668 apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
669 t->a.nelts;
670 t->a.nelts--;
671 dst_elt = next_elt;
672 for (next_elt++; next_elt <= end_elt; next_elt++) {
673 if ((checksum == next_elt->key_checksum) &&
674 !strcasecmp(next_elt->key, key)) {
675 t->a.nelts--;
676 }
677 else {
678 *dst_elt++ = *next_elt;
679 }
680 }
681
682 /* Shift over the remainder of the table (note that
683 * the previous loop didn't run to the end of the table,
684 * just to the last match for the index)
685 */
686 for (; next_elt < table_end; next_elt++) {
687 *dst_elt++ = *next_elt;
688 }
689 must_reindex = 1;
690 break;
691 }
692 }
693 if (must_reindex) {
694 table_reindex(t);
695 }
696 }
697
apr_table_merge(apr_table_t * t,const char * key,const char * val)698 APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
699 const char *val)
700 {
701 apr_table_entry_t *next_elt;
702 apr_table_entry_t *end_elt;
703 apr_uint32_t checksum;
704 int hash;
705
706 COMPUTE_KEY_CHECKSUM(key, checksum);
707 hash = TABLE_HASH(key);
708 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
709 t->index_first[hash] = t->a.nelts;
710 TABLE_SET_INDEX_INITIALIZED(t, hash);
711 goto add_new_elt;
712 }
713 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
714 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
715
716 for (; next_elt <= end_elt; next_elt++) {
717 if ((checksum == next_elt->key_checksum) &&
718 !strcasecmp(next_elt->key, key)) {
719
720 /* Found an existing entry with the same key, so merge with it */
721 next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
722 val, NULL);
723 return;
724 }
725 }
726
727 add_new_elt:
728 t->index_last[hash] = t->a.nelts;
729 next_elt = (apr_table_entry_t *) table_push(t);
730 next_elt->key = apr_pstrdup(t->a.pool, key);
731 next_elt->val = apr_pstrdup(t->a.pool, val);
732 next_elt->key_checksum = checksum;
733 }
734
apr_table_mergen(apr_table_t * t,const char * key,const char * val)735 APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
736 const char *val)
737 {
738 apr_table_entry_t *next_elt;
739 apr_table_entry_t *end_elt;
740 apr_uint32_t checksum;
741 int hash;
742
743 #if APR_POOL_DEBUG
744 {
745 apr_pool_t *pool;
746 pool = apr_pool_find(key);
747 if ((pool != (apr_pool_t *)key)
748 && (!apr_pool_is_ancestor(pool, t->a.pool))) {
749 fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
750 abort();
751 }
752 pool = apr_pool_find(val);
753 if ((pool != (apr_pool_t *)val)
754 && (!apr_pool_is_ancestor(pool, t->a.pool))) {
755 fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n");
756 abort();
757 }
758 }
759 #endif
760
761 COMPUTE_KEY_CHECKSUM(key, checksum);
762 hash = TABLE_HASH(key);
763 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
764 t->index_first[hash] = t->a.nelts;
765 TABLE_SET_INDEX_INITIALIZED(t, hash);
766 goto add_new_elt;
767 }
768 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
769 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
770
771 for (; next_elt <= end_elt; next_elt++) {
772 if ((checksum == next_elt->key_checksum) &&
773 !strcasecmp(next_elt->key, key)) {
774
775 /* Found an existing entry with the same key, so merge with it */
776 next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
777 val, NULL);
778 return;
779 }
780 }
781
782 add_new_elt:
783 t->index_last[hash] = t->a.nelts;
784 next_elt = (apr_table_entry_t *) table_push(t);
785 next_elt->key = (char *)key;
786 next_elt->val = (char *)val;
787 next_elt->key_checksum = checksum;
788 }
789
apr_table_add(apr_table_t * t,const char * key,const char * val)790 APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
791 const char *val)
792 {
793 apr_table_entry_t *elts;
794 apr_uint32_t checksum;
795 int hash;
796
797 hash = TABLE_HASH(key);
798 t->index_last[hash] = t->a.nelts;
799 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
800 t->index_first[hash] = t->a.nelts;
801 TABLE_SET_INDEX_INITIALIZED(t, hash);
802 }
803 COMPUTE_KEY_CHECKSUM(key, checksum);
804 elts = (apr_table_entry_t *) table_push(t);
805 elts->key = apr_pstrdup(t->a.pool, key);
806 elts->val = apr_pstrdup(t->a.pool, val);
807 elts->key_checksum = checksum;
808 }
809
apr_table_addn(apr_table_t * t,const char * key,const char * val)810 APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
811 const char *val)
812 {
813 apr_table_entry_t *elts;
814 apr_uint32_t checksum;
815 int hash;
816
817 #if APR_POOL_DEBUG
818 {
819 if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
820 fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
821 abort();
822 }
823 if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
824 fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n");
825 abort();
826 }
827 }
828 #endif
829
830 hash = TABLE_HASH(key);
831 t->index_last[hash] = t->a.nelts;
832 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
833 t->index_first[hash] = t->a.nelts;
834 TABLE_SET_INDEX_INITIALIZED(t, hash);
835 }
836 COMPUTE_KEY_CHECKSUM(key, checksum);
837 elts = (apr_table_entry_t *) table_push(t);
838 elts->key = (char *)key;
839 elts->val = (char *)val;
840 elts->key_checksum = checksum;
841 }
842
apr_table_overlay(apr_pool_t * p,const apr_table_t * overlay,const apr_table_t * base)843 APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
844 const apr_table_t *overlay,
845 const apr_table_t *base)
846 {
847 apr_table_t *res;
848
849 #if APR_POOL_DEBUG
850 /* we don't copy keys and values, so it's necessary that
851 * overlay->a.pool and base->a.pool have a life span at least
852 * as long as p
853 */
854 if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
855 fprintf(stderr,
856 "apr_table_overlay: overlay's pool is not an ancestor of p\n");
857 abort();
858 }
859 if (!apr_pool_is_ancestor(base->a.pool, p)) {
860 fprintf(stderr,
861 "apr_table_overlay: base's pool is not an ancestor of p\n");
862 abort();
863 }
864 #endif
865
866 res = apr_palloc(p, sizeof(apr_table_t));
867 /* behave like append_arrays */
868 res->a.pool = p;
869 copy_array_hdr_core(&res->a, &overlay->a);
870 apr_array_cat(&res->a, &base->a);
871 table_reindex(res);
872 return res;
873 }
874
875 /* And now for something completely abstract ...
876
877 * For each key value given as a vararg:
878 * run the function pointed to as
879 * int comp(void *r, char *key, char *value);
880 * on each valid key-value pair in the apr_table_t t that matches the vararg key,
881 * or once for every valid key-value pair if the vararg list is empty,
882 * until the function returns false (0) or we finish the table.
883 *
884 * Note that we restart the traversal for each vararg, which means that
885 * duplicate varargs will result in multiple executions of the function
886 * for each matching key. Note also that if the vararg list is empty,
887 * only one traversal will be made and will cut short if comp returns 0.
888 *
889 * Note that the table_get and table_merge functions assume that each key in
890 * the apr_table_t is unique (i.e., no multiple entries with the same key). This
891 * function does not make that assumption, since it (unfortunately) isn't
892 * true for some of Apache's tables.
893 *
894 * Note that rec is simply passed-on to the comp function, so that the
895 * caller can pass additional info for the task.
896 *
897 * ADDENDUM for apr_table_vdo():
898 *
899 * The caching api will allow a user to walk the header values:
900 *
901 * apr_status_t apr_cache_el_header_walk(apr_cache_el *el,
902 * int (*comp)(void *, const char *, const char *), void *rec, ...);
903 *
904 * So it can be ..., however from there I use a callback that use a va_list:
905 *
906 * apr_status_t (*cache_el_header_walk)(apr_cache_el *el,
907 * int (*comp)(void *, const char *, const char *), void *rec, va_list);
908 *
909 * To pass those ...'s on down to the actual module that will handle walking
910 * their headers, in the file case this is actually just an apr_table - and
911 * rather than reimplementing apr_table_do (which IMHO would be bad) I just
912 * called it with the va_list. For mod_shmem_cache I don't need it since I
913 * can't use apr_table's, but mod_file_cache should (though a good hash would
914 * be better, but that's a different issue :).
915 *
916 * So to make mod_file_cache easier to maintain, it's a good thing
917 */
apr_table_do(apr_table_do_callback_fn_t * comp,void * rec,const apr_table_t * t,...)918 APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
919 void *rec, const apr_table_t *t, ...)
920 {
921 int rv;
922
923 va_list vp;
924 va_start(vp, t);
925 rv = apr_table_vdo(comp, rec, t, vp);
926 va_end(vp);
927
928 return rv;
929 }
930
931 /* XXX: do the semantics of this routine make any sense? Right now,
932 * if the caller passed in a non-empty va_list of keys to search for,
933 * the "early termination" facility only terminates on *that* key; other
934 * keys will continue to process. Note that this only has any effect
935 * at all if there are multiple entries in the table with the same key,
936 * otherwise the called function can never effectively early-terminate
937 * this function, as the zero return value is effectively ignored.
938 *
939 * Note also that this behavior is at odds with the behavior seen if an
940 * empty va_list is passed in -- in that case, a zero return value terminates
941 * the entire apr_table_vdo (which is what I think should happen in
942 * both cases).
943 *
944 * If nobody objects soon, I'm going to change the order of the nested
945 * loops in this function so that any zero return value from the (*comp)
946 * function will cause a full termination of apr_table_vdo. I'm hesitant
947 * at the moment because these (funky) semantics have been around for a
948 * very long time, and although Apache doesn't seem to use them at all,
949 * some third-party vendor might. I can only think of one possible reason
950 * the existing semantics would make any sense, and it's very Apache-centric,
951 * which is this: if (*comp) is looking for matches of a particular
952 * substring in request headers (let's say it's looking for a particular
953 * cookie name in the Set-Cookie headers), then maybe it wants to be
954 * able to stop searching early as soon as it finds that one and move
955 * on to the next key. That's only an optimization of course, but changing
956 * the behavior of this function would mean that any code that tried
957 * to do that would stop working right.
958 *
959 * Sigh. --JCW, 06/28/02
960 */
apr_table_vdo(apr_table_do_callback_fn_t * comp,void * rec,const apr_table_t * t,va_list vp)961 APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp,
962 void *rec, const apr_table_t *t, va_list vp)
963 {
964 char *argp;
965 apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
966 int vdorv = 1;
967
968 argp = va_arg(vp, char *);
969 do {
970 int rv = 1, i;
971 if (argp) {
972 /* Scan for entries that match the next key */
973 int hash = TABLE_HASH(argp);
974 if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
975 apr_uint32_t checksum;
976 COMPUTE_KEY_CHECKSUM(argp, checksum);
977 for (i = t->index_first[hash];
978 rv && (i <= t->index_last[hash]); ++i) {
979 if (elts[i].key && (checksum == elts[i].key_checksum) &&
980 !strcasecmp(elts[i].key, argp)) {
981 rv = (*comp) (rec, elts[i].key, elts[i].val);
982 }
983 }
984 }
985 }
986 else {
987 /* Scan the entire table */
988 for (i = 0; rv && (i < t->a.nelts); ++i) {
989 if (elts[i].key) {
990 rv = (*comp) (rec, elts[i].key, elts[i].val);
991 }
992 }
993 }
994 if (rv == 0) {
995 vdorv = 0;
996 }
997 } while (argp && ((argp = va_arg(vp, char *)) != NULL));
998
999 return vdorv;
1000 }
1001
table_mergesort(apr_pool_t * pool,apr_table_entry_t ** values,apr_size_t n)1002 static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
1003 apr_table_entry_t **values,
1004 apr_size_t n)
1005 {
1006 /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
1007 * in C," chapter 8
1008 */
1009 apr_table_entry_t **values_tmp =
1010 (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
1011 apr_size_t i;
1012 apr_size_t blocksize;
1013
1014 /* First pass: sort pairs of elements (blocksize=1) */
1015 for (i = 0; i + 1 < n; i += 2) {
1016 if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
1017 apr_table_entry_t *swap = values[i];
1018 values[i] = values[i + 1];
1019 values[i + 1] = swap;
1020 }
1021 }
1022
1023 /* Merge successively larger blocks */
1024 blocksize = 2;
1025 while (blocksize < n) {
1026 apr_table_entry_t **dst = values_tmp;
1027 apr_size_t next_start;
1028 apr_table_entry_t **swap;
1029
1030 /* Merge consecutive pairs blocks of the next blocksize.
1031 * Within a block, elements are in sorted order due to
1032 * the previous iteration.
1033 */
1034 for (next_start = 0; next_start + blocksize < n;
1035 next_start += (blocksize + blocksize)) {
1036
1037 apr_size_t block1_start = next_start;
1038 apr_size_t block2_start = block1_start + blocksize;
1039 apr_size_t block1_end = block2_start;
1040 apr_size_t block2_end = block2_start + blocksize;
1041 if (block2_end > n) {
1042 /* The last block may be smaller than blocksize */
1043 block2_end = n;
1044 }
1045 for (;;) {
1046
1047 /* Merge the next two blocks:
1048 * Pick the smaller of the next element from
1049 * block 1 and the next element from block 2.
1050 * Once either of the blocks is emptied, copy
1051 * over all the remaining elements from the
1052 * other block
1053 */
1054 if (block1_start == block1_end) {
1055 for (; block2_start < block2_end; block2_start++) {
1056 *dst++ = values[block2_start];
1057 }
1058 break;
1059 }
1060 else if (block2_start == block2_end) {
1061 for (; block1_start < block1_end; block1_start++) {
1062 *dst++ = values[block1_start];
1063 }
1064 break;
1065 }
1066 if (strcasecmp(values[block1_start]->key,
1067 values[block2_start]->key) > 0) {
1068 *dst++ = values[block2_start++];
1069 }
1070 else {
1071 *dst++ = values[block1_start++];
1072 }
1073 }
1074 }
1075
1076 /* If n is not a multiple of 2*blocksize, some elements
1077 * will be left over at the end of the array.
1078 */
1079 for (i = dst - values_tmp; i < n; i++) {
1080 values_tmp[i] = values[i];
1081 }
1082
1083 /* The output array of this pass becomes the input
1084 * array of the next pass, and vice versa
1085 */
1086 swap = values_tmp;
1087 values_tmp = values;
1088 values = swap;
1089
1090 blocksize += blocksize;
1091 }
1092
1093 return values;
1094 }
1095
apr_table_compress(apr_table_t * t,unsigned flags)1096 APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
1097 {
1098 apr_table_entry_t **sort_array;
1099 apr_table_entry_t **sort_next;
1100 apr_table_entry_t **sort_end;
1101 apr_table_entry_t *table_next;
1102 apr_table_entry_t **last;
1103 int i;
1104 int dups_found;
1105
1106 if (t->a.nelts <= 1) {
1107 return;
1108 }
1109
1110 /* Copy pointers to all the table elements into an
1111 * array and sort to allow for easy detection of
1112 * duplicate keys
1113 */
1114 sort_array = (apr_table_entry_t **)
1115 apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
1116 sort_next = sort_array;
1117 table_next = (apr_table_entry_t *)t->a.elts;
1118 i = t->a.nelts;
1119 do {
1120 *sort_next++ = table_next++;
1121 } while (--i);
1122
1123 /* Note: the merge is done with mergesort instead of quicksort
1124 * because mergesort is a stable sort and runs in n*log(n)
1125 * time regardless of its inputs (quicksort is quadratic in
1126 * the worst case)
1127 */
1128 sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
1129
1130 /* Process any duplicate keys */
1131 dups_found = 0;
1132 sort_next = sort_array;
1133 sort_end = sort_array + t->a.nelts;
1134 last = sort_next++;
1135 while (sort_next < sort_end) {
1136 if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
1137 !strcasecmp((*sort_next)->key, (*last)->key)) {
1138 apr_table_entry_t **dup_last = sort_next + 1;
1139 dups_found = 1;
1140 while ((dup_last < sort_end) &&
1141 ((*dup_last)->key_checksum == (*last)->key_checksum) &&
1142 !strcasecmp((*dup_last)->key, (*last)->key)) {
1143 dup_last++;
1144 }
1145 dup_last--; /* Elements from last through dup_last, inclusive,
1146 * all have the same key
1147 */
1148 if (flags == APR_OVERLAP_TABLES_MERGE) {
1149 apr_size_t len = 0;
1150 apr_table_entry_t **next = last;
1151 char *new_val;
1152 char *val_dst;
1153 do {
1154 len += strlen((*next)->val);
1155 len += 2; /* for ", " or trailing null */
1156 } while (++next <= dup_last);
1157 new_val = (char *)apr_palloc(t->a.pool, len);
1158 val_dst = new_val;
1159 next = last;
1160 for (;;) {
1161 strcpy(val_dst, (*next)->val);
1162 val_dst += strlen((*next)->val);
1163 next++;
1164 if (next > dup_last) {
1165 *val_dst = 0;
1166 break;
1167 }
1168 else {
1169 *val_dst++ = ',';
1170 *val_dst++ = ' ';
1171 }
1172 }
1173 (*last)->val = new_val;
1174 }
1175 else { /* overwrite */
1176 (*last)->val = (*dup_last)->val;
1177 }
1178 do {
1179 (*sort_next)->key = NULL;
1180 } while (++sort_next <= dup_last);
1181 }
1182 else {
1183 last = sort_next++;
1184 }
1185 }
1186
1187 /* Shift elements to the left to fill holes left by removing duplicates */
1188 if (dups_found) {
1189 apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
1190 apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
1191 apr_table_entry_t *last_elt = src + t->a.nelts;
1192 do {
1193 if (src->key) {
1194 *dst++ = *src;
1195 }
1196 } while (++src < last_elt);
1197 t->a.nelts -= (int)(last_elt - dst);
1198 }
1199
1200 table_reindex(t);
1201 }
1202
apr_table_cat(apr_table_t * t,const apr_table_t * s)1203 static void apr_table_cat(apr_table_t *t, const apr_table_t *s)
1204 {
1205 const int n = t->a.nelts;
1206 register int idx;
1207
1208 apr_array_cat(&t->a,&s->a);
1209
1210 if (n == 0) {
1211 memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
1212 memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
1213 t->index_initialized = s->index_initialized;
1214 return;
1215 }
1216
1217 for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
1218 if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
1219 t->index_last[idx] = s->index_last[idx] + n;
1220 if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
1221 t->index_first[idx] = s->index_first[idx] + n;
1222 }
1223 }
1224 }
1225
1226 t->index_initialized |= s->index_initialized;
1227 }
1228
apr_table_overlap(apr_table_t * a,const apr_table_t * b,unsigned flags)1229 APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
1230 unsigned flags)
1231 {
1232 if (a->a.nelts + b->a.nelts == 0) {
1233 return;
1234 }
1235
1236 #if APR_POOL_DEBUG
1237 /* Since the keys and values are not copied, it's required that
1238 * b->a.pool has a lifetime at least as long as a->a.pool. */
1239 if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
1240 fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
1241 abort();
1242 }
1243 #endif
1244
1245 apr_table_cat(a, b);
1246
1247 apr_table_compress(a, flags);
1248 }
1249
table_getm_do(void * v,const char * key,const char * val)1250 static int table_getm_do(void *v, const char *key, const char *val)
1251 {
1252 table_getm_t *state = (table_getm_t *) v;
1253
1254 if (!state->first) {
1255 /**
1256 * The most common case is a single header, and this is covered by
1257 * a fast path that doesn't allocate any memory. On the second and
1258 * subsequent header, an array is created and the array concatenated
1259 * together to form the final value.
1260 */
1261 state->first = val;
1262 }
1263 else {
1264 const char **elt;
1265 if (!state->merged) {
1266 state->merged = apr_array_make(state->p, 10, sizeof(const char *));
1267 elt = apr_array_push(state->merged);
1268 *elt = state->first;
1269 }
1270 elt = apr_array_push(state->merged);
1271 *elt = val;
1272 }
1273 return 1;
1274 }
1275
apr_table_getm(apr_pool_t * p,const apr_table_t * t,const char * key)1276 APR_DECLARE(const char *) apr_table_getm(apr_pool_t *p, const apr_table_t *t,
1277 const char *key)
1278 {
1279 table_getm_t state;
1280
1281 state.p = p;
1282 state.first = NULL;
1283 state.merged = NULL;
1284
1285 apr_table_do(table_getm_do, &state, t, key, NULL);
1286
1287 if (!state.first) {
1288 return NULL;
1289 }
1290 else if (!state.merged) {
1291 return state.first;
1292 }
1293 else {
1294 return apr_array_pstrcat(p, state.merged, ',');
1295 }
1296 }
1297