Coverage Report

Created: 2023-03-26 06:28

/src/httpd/srclib/apr/tables/apr_tables.c
Line
Count
Source (jump to first uncovered line)
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
54
static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
55
          int nelts, int elt_size, int clear)
56
6.49k
{
57
    /*
58
     * Assure sanity if someone asks for
59
     * array of zero elts.
60
     */
61
6.49k
    if (nelts < 1) {
62
0
        nelts = 1;
63
0
    }
64
65
6.49k
    if (clear) {
66
796
        res->elts = apr_pcalloc(p, nelts * elt_size);
67
796
    }
68
5.69k
    else {
69
5.69k
        res->elts = apr_palloc(p, nelts * elt_size);
70
5.69k
    }
71
72
6.49k
    res->pool = p;
73
6.49k
    res->elt_size = elt_size;
74
6.49k
    res->nelts = 0;   /* No active elements yet... */
75
6.49k
    res->nalloc = nelts;  /* ...but this many allocated */
76
6.49k
}
77
78
APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
79
0
{
80
0
    return ((a == NULL) || (a->nelts == 0));
81
0
}
82
83
APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
84
            int nelts, int elt_size)
85
796
{
86
796
    apr_array_header_t *res;
87
88
796
    res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
89
796
    make_array_core(res, p, nelts, elt_size, 1);
90
796
    return res;
91
796
}
92
93
APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
94
0
{
95
0
    arr->nelts = 0;
96
0
}
97
98
APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
99
0
{
100
0
    if (apr_is_empty_array(arr)) {
101
0
        return NULL;
102
0
    }
103
104
0
    return arr->elts + (arr->elt_size * (--arr->nelts));
105
0
}
106
107
APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
108
3.51k
{
109
3.51k
    if (arr->nelts == arr->nalloc) {
110
94
        int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
111
94
        char *new_data;
112
113
94
        new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
114
115
94
        memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
116
94
        memset(new_data + arr->nalloc * arr->elt_size, 0,
117
94
               arr->elt_size * (new_size - arr->nalloc));
118
94
        arr->elts = new_data;
119
94
        arr->nalloc = new_size;
120
94
    }
121
122
3.51k
    ++arr->nelts;
123
3.51k
    return arr->elts + (arr->elt_size * (arr->nelts - 1));
124
3.51k
}
125
126
static void *apr_array_push_noclear(apr_array_header_t *arr)
127
2.08k
{
128
2.08k
    if (arr->nelts == arr->nalloc) {
129
33
        int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
130
33
        char *new_data;
131
132
33
        new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
133
134
33
        memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
135
33
        arr->elts = new_data;
136
33
        arr->nalloc = new_size;
137
33
    }
138
139
2.08k
    ++arr->nelts;
140
2.08k
    return arr->elts + (arr->elt_size * (arr->nelts - 1));
141
2.08k
}
142
143
APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
144
             const apr_array_header_t *src)
145
0
{
146
0
    int elt_size = dst->elt_size;
147
148
0
    if (dst->nelts + src->nelts > dst->nalloc) {
149
0
  int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
150
0
  char *new_data;
151
152
0
  while (dst->nelts + src->nelts > new_size) {
153
0
      new_size *= 2;
154
0
  }
155
156
0
  new_data = apr_pcalloc(dst->pool, elt_size * new_size);
157
0
  memcpy(new_data, dst->elts, dst->nalloc * elt_size);
158
159
0
  dst->elts = new_data;
160
0
  dst->nalloc = new_size;
161
0
    }
162
163
0
    memcpy(dst->elts + dst->nelts * elt_size, src->elts,
164
0
     elt_size * src->nelts);
165
0
    dst->nelts += src->nelts;
166
0
}
167
168
APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
169
            const apr_array_header_t *arr)
170
0
{
171
0
    apr_array_header_t *res =
172
0
        (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
173
0
    make_array_core(res, p, arr->nalloc, arr->elt_size, 0);
174
175
0
    memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
176
0
    res->nelts = arr->nelts;
177
0
    memset(res->elts + res->elt_size * res->nelts, 0,
178
0
           res->elt_size * (res->nalloc - res->nelts));
179
0
    return res;
180
0
}
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
189
static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
190
             const apr_array_header_t *arr)
191
0
{
192
0
    res->elts = arr->elts;
193
0
    res->elt_size = arr->elt_size;
194
0
    res->nelts = arr->nelts;
195
0
    res->nalloc = arr->nelts; /* Force overflow on push */
196
0
}
197
198
APR_DECLARE(apr_array_header_t *)
199
    apr_array_copy_hdr(apr_pool_t *p,
200
           const apr_array_header_t *arr)
201
0
{
202
0
    apr_array_header_t *res;
203
204
0
    res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
205
0
    res->pool = p;
206
0
    copy_array_hdr_core(res, arr);
207
0
    return res;
208
0
}
209
210
/* The above is used here to avoid consing multiple new array bodies... */
211
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)
216
0
{
217
0
    apr_array_header_t *res = apr_array_copy_hdr(p, first);
218
219
0
    apr_array_cat(res, second);
220
0
    return res;
221
0
}
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
 */
229
APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
230
             const apr_array_header_t *arr,
231
             const char sep)
232
0
{
233
0
    char *cp, *res, **strpp;
234
0
    apr_size_t len;
235
0
    int i;
236
237
0
    if (arr->nelts <= 0 || arr->elts == NULL) {    /* Empty table? */
238
0
        return (char *) apr_pcalloc(p, 1);
239
0
    }
240
241
    /* Pass one --- find length of required string */
242
243
0
    len = 0;
244
0
    for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
245
0
        if (strpp && *strpp != NULL) {
246
0
            len += strlen(*strpp);
247
0
        }
248
0
        if (++i >= arr->nelts) {
249
0
            break;
250
0
  }
251
0
        if (sep) {
252
0
            ++len;
253
0
  }
254
0
    }
255
256
    /* Allocate the required string */
257
258
0
    res = (char *) apr_palloc(p, len + 1);
259
0
    cp = res;
260
261
    /* Pass two --- copy the argument strings into the result space */
262
263
0
    for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
264
0
        if (strpp && *strpp != NULL) {
265
0
            len = strlen(*strpp);
266
0
            memcpy(cp, *strpp, len);
267
0
            cp += len;
268
0
        }
269
0
        if (++i >= arr->nelts) {
270
0
            break;
271
0
  }
272
0
        if (sep) {
273
0
            *cp++ = sep;
274
0
  }
275
0
    }
276
277
0
    *cp = '\0';
278
279
    /* Return the result string */
280
281
0
    return res;
282
0
}
283
284
285
/*****************************************************************
286
 *
287
 * The "table" functions.
288
 */
289
290
#if APR_CHARSET_EBCDIC
291
#define CASE_MASK 0xbfbfbfbf
292
#else
293
3.68k
#define CASE_MASK 0xdfdfdfdf
294
#endif
295
296
0
#define TABLE_HASH_SIZE 32
297
4.28k
#define TABLE_INDEX_MASK 0x1f
298
4.28k
#define TABLE_HASH(key)  (TABLE_INDEX_MASK & *(unsigned char *)(key))
299
4.28k
#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1u << (i)))
300
1.43k
#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1u << (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
3.68k
#define COMPUTE_KEY_CHECKSUM(key, checksum)    \
309
3.68k
{                                              \
310
3.68k
    const char *k = (key);                     \
311
3.68k
    apr_uint32_t c = (apr_uint32_t)*k;         \
312
3.68k
    (checksum) = c;                            \
313
3.68k
    (checksum) <<= 8;                          \
314
3.68k
    if (c) {                                   \
315
3.49k
        c = (apr_uint32_t)*++k;                \
316
3.49k
        checksum |= c;                         \
317
3.49k
    }                                          \
318
3.68k
    (checksum) <<= 8;                          \
319
3.68k
    if (c) {                                   \
320
2.71k
        c = (apr_uint32_t)*++k;                \
321
2.71k
        checksum |= c;                         \
322
2.71k
    }                                          \
323
3.68k
    (checksum) <<= 8;                          \
324
3.68k
    if (c) {                                   \
325
2.51k
        c = (apr_uint32_t)*++k;                \
326
2.51k
        checksum |= c;                         \
327
2.51k
    }                                          \
328
3.68k
    checksum &= CASE_MASK;                     \
329
3.68k
}
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
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
2.08k
#define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
388
#endif /* MAKE_TABLE_PROFILE */
389
390
APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
391
0
{
392
0
    return (const apr_array_header_t *)t;
393
0
}
394
395
APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
396
0
{
397
0
    return ((t == NULL) || (t->a.nelts == 0));
398
0
}
399
400
APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
401
5.69k
{
402
5.69k
    apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
403
404
5.69k
    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
5.69k
    t->index_initialized = 0;
409
5.69k
    return t;
410
5.69k
}
411
412
APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
413
0
{
414
0
    apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));
415
416
0
#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
0
    if (!apr_pool_is_ancestor(t->a.pool, p)) {
421
0
  fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n");
422
0
  abort();
423
0
    }
424
0
#endif
425
0
    make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
426
0
    memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
427
0
    new->a.nelts = t->a.nelts;
428
0
    memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
429
0
    memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
430
0
    new->index_initialized = t->index_initialized;
431
0
    return new;
432
0
}
433
434
APR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t)
435
0
{
436
0
    const apr_array_header_t *array = apr_table_elts(t);
437
0
    apr_table_entry_t *elts = (apr_table_entry_t *) array->elts;
438
0
    apr_table_t *new = apr_table_make(p, array->nelts);
439
0
    int i;
440
441
0
    for (i = 0; i < array->nelts; i++) {
442
0
        apr_table_add(new, elts[i].key, elts[i].val);
443
0
    }
444
445
0
    return new;
446
0
}
447
448
static void table_reindex(apr_table_t *t)
449
0
{
450
0
    int i;
451
0
    int hash;
452
0
    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
453
454
0
    t->index_initialized = 0;
455
0
    for (i = 0; i < t->a.nelts; i++, next_elt++) {
456
0
        hash = TABLE_HASH(next_elt->key);
457
0
        t->index_last[hash] = i;
458
0
        if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
459
0
            t->index_first[hash] = i;
460
0
            TABLE_SET_INDEX_INITIALIZED(t, hash);
461
0
        }
462
0
    }
463
0
}
464
465
APR_DECLARE(void) apr_table_clear(apr_table_t *t)
466
0
{
467
0
    t->a.nelts = 0;
468
0
    t->index_initialized = 0;
469
0
}
470
471
APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
472
2.20k
{
473
2.20k
    apr_table_entry_t *next_elt;
474
2.20k
    apr_table_entry_t *end_elt;
475
2.20k
    apr_uint32_t checksum;
476
2.20k
    int hash;
477
478
2.20k
    if (key == NULL) {
479
0
  return NULL;
480
0
    }
481
482
2.20k
    hash = TABLE_HASH(key);
483
2.20k
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
484
603
        return NULL;
485
603
    }
486
1.59k
    COMPUTE_KEY_CHECKSUM(key, checksum);
487
1.59k
    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
488
1.59k
    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
489
490
3.39k
    for (; next_elt <= end_elt; next_elt++) {
491
2.20k
  if ((checksum == next_elt->key_checksum) &&
492
2.20k
            !strcasecmp(next_elt->key, key)) {
493
408
      return next_elt->val;
494
408
  }
495
2.20k
    }
496
497
1.18k
    return NULL;
498
1.59k
}
499
500
APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
501
                                const char *val)
502
0
{
503
0
    apr_table_entry_t *next_elt;
504
0
    apr_table_entry_t *end_elt;
505
0
    apr_table_entry_t *table_end;
506
0
    apr_uint32_t checksum;
507
0
    int hash;
508
509
0
    COMPUTE_KEY_CHECKSUM(key, checksum);
510
0
    hash = TABLE_HASH(key);
511
0
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
512
0
        t->index_first[hash] = t->a.nelts;
513
0
        TABLE_SET_INDEX_INITIALIZED(t, hash);
514
0
        goto add_new_elt;
515
0
    }
516
0
    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
517
0
    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
518
0
    table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
519
520
0
    for (; next_elt <= end_elt; next_elt++) {
521
0
  if ((checksum == next_elt->key_checksum) &&
522
0
            !strcasecmp(next_elt->key, key)) {
523
524
            /* Found an existing entry with the same key, so overwrite it */
525
526
0
            int must_reindex = 0;
527
0
            apr_table_entry_t *dst_elt = NULL;
528
529
0
            next_elt->val = apr_pstrdup(t->a.pool, val);
530
531
            /* Remove any other instances of this key */
532
0
            for (next_elt++; next_elt <= end_elt; next_elt++) {
533
0
                if ((checksum == next_elt->key_checksum) &&
534
0
                    !strcasecmp(next_elt->key, key)) {
535
0
                    t->a.nelts--;
536
0
                    if (!dst_elt) {
537
0
                        dst_elt = next_elt;
538
0
                    }
539
0
                }
540
0
                else if (dst_elt) {
541
0
                    *dst_elt++ = *next_elt;
542
0
                    must_reindex = 1;
543
0
                }
544
0
            }
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
0
            if (dst_elt) {
552
0
                for (; next_elt < table_end; next_elt++) {
553
0
                    *dst_elt++ = *next_elt;
554
0
                }
555
0
                must_reindex = 1;
556
0
            }
557
0
            if (must_reindex) {
558
0
                table_reindex(t);
559
0
            }
560
0
            return;
561
0
        }
562
0
    }
563
564
0
add_new_elt:
565
0
    t->index_last[hash] = t->a.nelts;
566
0
    next_elt = (apr_table_entry_t *) table_push(t);
567
0
    next_elt->key = apr_pstrdup(t->a.pool, key);
568
0
    next_elt->val = apr_pstrdup(t->a.pool, val);
569
0
    next_elt->key_checksum = checksum;
570
0
}
571
572
APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
573
                                 const char *val)
574
0
{
575
0
    apr_table_entry_t *next_elt;
576
0
    apr_table_entry_t *end_elt;
577
0
    apr_table_entry_t *table_end;
578
0
    apr_uint32_t checksum;
579
0
    int hash;
580
581
0
    COMPUTE_KEY_CHECKSUM(key, checksum);
582
0
    hash = TABLE_HASH(key);
583
0
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
584
0
        t->index_first[hash] = t->a.nelts;
585
0
        TABLE_SET_INDEX_INITIALIZED(t, hash);
586
0
        goto add_new_elt;
587
0
    }
588
0
    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
589
0
    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
590
0
    table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
591
592
0
    for (; next_elt <= end_elt; next_elt++) {
593
0
  if ((checksum == next_elt->key_checksum) &&
594
0
            !strcasecmp(next_elt->key, key)) {
595
596
            /* Found an existing entry with the same key, so overwrite it */
597
598
0
            int must_reindex = 0;
599
0
            apr_table_entry_t *dst_elt = NULL;
600
601
0
            next_elt->val = (char *)val;
602
603
            /* Remove any other instances of this key */
604
0
            for (next_elt++; next_elt <= end_elt; next_elt++) {
605
0
                if ((checksum == next_elt->key_checksum) &&
606
0
                    !strcasecmp(next_elt->key, key)) {
607
0
                    t->a.nelts--;
608
0
                    if (!dst_elt) {
609
0
                        dst_elt = next_elt;
610
0
                    }
611
0
                }
612
0
                else if (dst_elt) {
613
0
                    *dst_elt++ = *next_elt;
614
0
                    must_reindex = 1;
615
0
                }
616
0
            }
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
0
            if (dst_elt) {
624
0
                for (; next_elt < table_end; next_elt++) {
625
0
                    *dst_elt++ = *next_elt;
626
0
                }
627
0
                must_reindex = 1;
628
0
            }
629
0
            if (must_reindex) {
630
0
                table_reindex(t);
631
0
            }
632
0
            return;
633
0
        }
634
0
    }
635
636
0
add_new_elt:
637
0
    t->index_last[hash] = t->a.nelts;
638
0
    next_elt = (apr_table_entry_t *) table_push(t);
639
0
    next_elt->key = (char *)key;
640
0
    next_elt->val = (char *)val;
641
0
    next_elt->key_checksum = checksum;
642
0
}
643
644
APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
645
0
{
646
0
    apr_table_entry_t *next_elt;
647
0
    apr_table_entry_t *end_elt;
648
0
    apr_table_entry_t *dst_elt;
649
0
    apr_uint32_t checksum;
650
0
    int hash;
651
0
    int must_reindex;
652
653
0
    hash = TABLE_HASH(key);
654
0
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
655
0
        return;
656
0
    }
657
0
    COMPUTE_KEY_CHECKSUM(key, checksum);
658
0
    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
659
0
    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
660
0
    must_reindex = 0;
661
0
    for (; next_elt <= end_elt; next_elt++) {
662
0
  if ((checksum == next_elt->key_checksum) &&
663
0
            !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
0
            apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
669
0
                t->a.nelts;
670
0
            t->a.nelts--;
671
0
            dst_elt = next_elt;
672
0
            for (next_elt++; next_elt <= end_elt; next_elt++) {
673
0
                if ((checksum == next_elt->key_checksum) &&
674
0
                    !strcasecmp(next_elt->key, key)) {
675
0
                    t->a.nelts--;
676
0
                }
677
0
                else {
678
0
                    *dst_elt++ = *next_elt;
679
0
                }
680
0
            }
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
0
            for (; next_elt < table_end; next_elt++) {
687
0
                *dst_elt++ = *next_elt;
688
0
            }
689
0
            must_reindex = 1;
690
0
            break;
691
0
        }
692
0
    }
693
0
    if (must_reindex) {
694
0
        table_reindex(t);
695
0
    }
696
0
}
697
698
APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
699
         const char *val)
700
0
{
701
0
    apr_table_entry_t *next_elt;
702
0
    apr_table_entry_t *end_elt;
703
0
    apr_uint32_t checksum;
704
0
    int hash;
705
706
0
    COMPUTE_KEY_CHECKSUM(key, checksum);
707
0
    hash = TABLE_HASH(key);
708
0
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
709
0
        t->index_first[hash] = t->a.nelts;
710
0
        TABLE_SET_INDEX_INITIALIZED(t, hash);
711
0
        goto add_new_elt;
712
0
    }
713
0
    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
714
0
    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
715
716
0
    for (; next_elt <= end_elt; next_elt++) {
717
0
  if ((checksum == next_elt->key_checksum) &&
718
0
            !strcasecmp(next_elt->key, key)) {
719
720
            /* Found an existing entry with the same key, so merge with it */
721
0
      next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
722
0
                                        val, NULL);
723
0
            return;
724
0
        }
725
0
    }
726
727
0
add_new_elt:
728
0
    t->index_last[hash] = t->a.nelts;
729
0
    next_elt = (apr_table_entry_t *) table_push(t);
730
0
    next_elt->key = apr_pstrdup(t->a.pool, key);
731
0
    next_elt->val = apr_pstrdup(t->a.pool, val);
732
0
    next_elt->key_checksum = checksum;
733
0
}
734
735
APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
736
          const char *val)
737
0
{
738
0
    apr_table_entry_t *next_elt;
739
0
    apr_table_entry_t *end_elt;
740
0
    apr_uint32_t checksum;
741
0
    int hash;
742
743
0
#if APR_POOL_DEBUG
744
0
    {
745
0
  apr_pool_t *pool;
746
0
  pool = apr_pool_find(key);
747
0
  if ((pool != (apr_pool_t *)key)
748
0
            && (!apr_pool_is_ancestor(pool, t->a.pool))) {
749
0
      fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
750
0
      abort();
751
0
  }
752
0
  pool = apr_pool_find(val);
753
0
  if ((pool != (apr_pool_t *)val)
754
0
            && (!apr_pool_is_ancestor(pool, t->a.pool))) {
755
0
      fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n");
756
0
      abort();
757
0
  }
758
0
    }
759
0
#endif
760
761
0
    COMPUTE_KEY_CHECKSUM(key, checksum);
762
0
    hash = TABLE_HASH(key);
763
0
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
764
0
        t->index_first[hash] = t->a.nelts;
765
0
        TABLE_SET_INDEX_INITIALIZED(t, hash);
766
0
        goto add_new_elt;
767
0
    }
768
0
    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
769
0
    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
770
771
0
    for (; next_elt <= end_elt; next_elt++) {
772
0
  if ((checksum == next_elt->key_checksum) &&
773
0
            !strcasecmp(next_elt->key, key)) {
774
775
            /* Found an existing entry with the same key, so merge with it */
776
0
      next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
777
0
                                        val, NULL);
778
0
            return;
779
0
        }
780
0
    }
781
782
0
add_new_elt:
783
0
    t->index_last[hash] = t->a.nelts;
784
0
    next_elt = (apr_table_entry_t *) table_push(t);
785
0
    next_elt->key = (char *)key;
786
0
    next_elt->val = (char *)val;
787
0
    next_elt->key_checksum = checksum;
788
0
}
789
790
APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
791
             const char *val)
792
0
{
793
0
    apr_table_entry_t *elts;
794
0
    apr_uint32_t checksum;
795
0
    int hash;
796
797
0
    hash = TABLE_HASH(key);
798
0
    t->index_last[hash] = t->a.nelts;
799
0
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
800
0
        t->index_first[hash] = t->a.nelts;
801
0
        TABLE_SET_INDEX_INITIALIZED(t, hash);
802
0
    }
803
0
    COMPUTE_KEY_CHECKSUM(key, checksum);
804
0
    elts = (apr_table_entry_t *) table_push(t);
805
0
    elts->key = apr_pstrdup(t->a.pool, key);
806
0
    elts->val = apr_pstrdup(t->a.pool, val);
807
0
    elts->key_checksum = checksum;
808
0
}
809
810
APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
811
        const char *val)
812
2.08k
{
813
2.08k
    apr_table_entry_t *elts;
814
2.08k
    apr_uint32_t checksum;
815
2.08k
    int hash;
816
817
2.08k
#if APR_POOL_DEBUG
818
2.08k
    {
819
2.08k
  if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
820
0
      fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
821
0
      abort();
822
0
  }
823
2.08k
  if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
824
0
      fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n");
825
0
      abort();
826
0
  }
827
2.08k
    }
828
2.08k
#endif
829
830
2.08k
    hash = TABLE_HASH(key);
831
2.08k
    t->index_last[hash] = t->a.nelts;
832
2.08k
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
833
1.43k
        t->index_first[hash] = t->a.nelts;
834
1.43k
        TABLE_SET_INDEX_INITIALIZED(t, hash);
835
1.43k
    }
836
2.08k
    COMPUTE_KEY_CHECKSUM(key, checksum);
837
2.08k
    elts = (apr_table_entry_t *) table_push(t);
838
2.08k
    elts->key = (char *)key;
839
2.08k
    elts->val = (char *)val;
840
2.08k
    elts->key_checksum = checksum;
841
2.08k
}
842
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
0
{
847
0
    apr_table_t *res;
848
849
0
#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
0
    if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
855
0
  fprintf(stderr,
856
0
    "apr_table_overlay: overlay's pool is not an ancestor of p\n");
857
0
  abort();
858
0
    }
859
0
    if (!apr_pool_is_ancestor(base->a.pool, p)) {
860
0
  fprintf(stderr,
861
0
    "apr_table_overlay: base's pool is not an ancestor of p\n");
862
0
  abort();
863
0
    }
864
0
#endif
865
866
0
    res = apr_palloc(p, sizeof(apr_table_t));
867
    /* behave like append_arrays */
868
0
    res->a.pool = p;
869
0
    copy_array_hdr_core(&res->a, &overlay->a);
870
0
    apr_array_cat(&res->a, &base->a);
871
0
    table_reindex(res);
872
0
    return res;
873
0
}
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
 */
918
APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
919
                                     void *rec, const apr_table_t *t, ...)
920
0
{
921
0
    int rv;
922
923
0
    va_list vp;
924
0
    va_start(vp, t);
925
0
    rv = apr_table_vdo(comp, rec, t, vp);
926
0
    va_end(vp);
927
928
0
    return rv;
929
0
}
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
 */
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
0
{
964
0
    char *argp;
965
0
    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
966
0
    int vdorv = 1;
967
968
0
    argp = va_arg(vp, char *);
969
0
    do {
970
0
        int rv = 1, i;
971
0
        if (argp) {
972
            /* Scan for entries that match the next key */
973
0
            int hash = TABLE_HASH(argp);
974
0
            if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
975
0
                apr_uint32_t checksum;
976
0
                COMPUTE_KEY_CHECKSUM(argp, checksum);
977
0
                for (i = t->index_first[hash];
978
0
                     rv && (i <= t->index_last[hash]); ++i) {
979
0
                    if (elts[i].key && (checksum == elts[i].key_checksum) &&
980
0
                                        !strcasecmp(elts[i].key, argp)) {
981
0
                        rv = (*comp) (rec, elts[i].key, elts[i].val);
982
0
                    }
983
0
                }
984
0
            }
985
0
        }
986
0
        else {
987
            /* Scan the entire table */
988
0
            for (i = 0; rv && (i < t->a.nelts); ++i) {
989
0
                if (elts[i].key) {
990
0
                    rv = (*comp) (rec, elts[i].key, elts[i].val);
991
0
                }
992
0
            }
993
0
        }
994
0
        if (rv == 0) {
995
0
            vdorv = 0;
996
0
        }
997
0
    } while (argp && ((argp = va_arg(vp, char *)) != NULL));
998
999
0
    return vdorv;
1000
0
}
1001
1002
static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
1003
                                           apr_table_entry_t **values,
1004
                                           apr_size_t n)
1005
0
{
1006
    /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
1007
     * in C," chapter 8
1008
     */
1009
0
    apr_table_entry_t **values_tmp =
1010
0
        (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
1011
0
    apr_size_t i;
1012
0
    apr_size_t blocksize;
1013
1014
    /* First pass: sort pairs of elements (blocksize=1) */
1015
0
    for (i = 0; i + 1 < n; i += 2) {
1016
0
        if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
1017
0
            apr_table_entry_t *swap = values[i];
1018
0
            values[i] = values[i + 1];
1019
0
            values[i + 1] = swap;
1020
0
        }
1021
0
    }
1022
1023
    /* Merge successively larger blocks */
1024
0
    blocksize = 2;
1025
0
    while (blocksize < n) {
1026
0
        apr_table_entry_t **dst = values_tmp;
1027
0
        apr_size_t next_start;
1028
0
        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
0
        for (next_start = 0; next_start + blocksize < n;
1035
0
             next_start += (blocksize + blocksize)) {
1036
1037
0
            apr_size_t block1_start = next_start;
1038
0
            apr_size_t block2_start = block1_start + blocksize;
1039
0
            apr_size_t block1_end = block2_start;
1040
0
            apr_size_t block2_end = block2_start + blocksize;
1041
0
            if (block2_end > n) {
1042
                /* The last block may be smaller than blocksize */
1043
0
                block2_end = n;
1044
0
            }
1045
0
            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
0
                if (block1_start == block1_end) {
1055
0
                    for (; block2_start < block2_end; block2_start++) {
1056
0
                        *dst++ = values[block2_start];
1057
0
                    }
1058
0
                    break;
1059
0
                }
1060
0
                else if (block2_start == block2_end) {
1061
0
                    for (; block1_start < block1_end; block1_start++) {
1062
0
                        *dst++ = values[block1_start];
1063
0
                    }
1064
0
                    break;
1065
0
                }
1066
0
                if (strcasecmp(values[block1_start]->key,
1067
0
                               values[block2_start]->key) > 0) {
1068
0
                    *dst++ = values[block2_start++];
1069
0
                }
1070
0
                else {
1071
0
                    *dst++ = values[block1_start++];
1072
0
                }
1073
0
            }
1074
0
        }
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
0
        for (i = dst - values_tmp; i < n; i++) {
1080
0
            values_tmp[i] = values[i];
1081
0
        }
1082
1083
        /* The output array of this pass becomes the input
1084
         * array of the next pass, and vice versa
1085
         */
1086
0
        swap = values_tmp;
1087
0
        values_tmp = values;
1088
0
        values = swap;
1089
1090
0
        blocksize += blocksize;
1091
0
    }
1092
1093
0
    return values;
1094
0
}
1095
1096
APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
1097
0
{
1098
0
    apr_table_entry_t **sort_array;
1099
0
    apr_table_entry_t **sort_next;
1100
0
    apr_table_entry_t **sort_end;
1101
0
    apr_table_entry_t *table_next;
1102
0
    apr_table_entry_t **last;
1103
0
    int i;
1104
0
    int dups_found;
1105
1106
0
    if (flags == APR_OVERLAP_TABLES_ADD) {
1107
0
        return;
1108
0
    }
1109
1110
0
    if (t->a.nelts <= 1) {
1111
0
        return;
1112
0
    }
1113
1114
    /* Copy pointers to all the table elements into an
1115
     * array and sort to allow for easy detection of
1116
     * duplicate keys
1117
     */
1118
0
    sort_array = (apr_table_entry_t **)
1119
0
        apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
1120
0
    sort_next = sort_array;
1121
0
    table_next = (apr_table_entry_t *)t->a.elts;
1122
0
    i = t->a.nelts;
1123
0
    do {
1124
0
        *sort_next++ = table_next++;
1125
0
    } while (--i);
1126
1127
    /* Note: the merge is done with mergesort instead of quicksort
1128
     * because mergesort is a stable sort and runs in n*log(n)
1129
     * time regardless of its inputs (quicksort is quadratic in
1130
     * the worst case)
1131
     */
1132
0
    sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
1133
1134
    /* Process any duplicate keys */
1135
0
    dups_found = 0;
1136
0
    sort_next = sort_array;
1137
0
    sort_end = sort_array + t->a.nelts;
1138
0
    last = sort_next++;
1139
0
    while (sort_next < sort_end) {
1140
0
        if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
1141
0
            !strcasecmp((*sort_next)->key, (*last)->key)) {
1142
0
            apr_table_entry_t **dup_last = sort_next + 1;
1143
0
            dups_found = 1;
1144
0
            while ((dup_last < sort_end) &&
1145
0
                   ((*dup_last)->key_checksum == (*last)->key_checksum) &&
1146
0
                   !strcasecmp((*dup_last)->key, (*last)->key)) {
1147
0
                dup_last++;
1148
0
            }
1149
0
            dup_last--; /* Elements from last through dup_last, inclusive,
1150
                         * all have the same key
1151
                         */
1152
0
            if (flags == APR_OVERLAP_TABLES_MERGE) {
1153
0
                apr_size_t len = 0;
1154
0
                apr_table_entry_t **next = last;
1155
0
                char *new_val;
1156
0
                char *val_dst;
1157
0
                do {
1158
0
                    len += strlen((*next)->val);
1159
0
                    len += 2; /* for ", " or trailing null */
1160
0
                } while (++next <= dup_last);
1161
0
                new_val = (char *)apr_palloc(t->a.pool, len);
1162
0
                val_dst = new_val;
1163
0
                next = last;
1164
0
                for (;;) {
1165
0
                    strcpy(val_dst, (*next)->val);
1166
0
                    val_dst += strlen((*next)->val);
1167
0
                    next++;
1168
0
                    if (next > dup_last) {
1169
0
                        *val_dst = 0;
1170
0
                        break;
1171
0
                    }
1172
0
                    else {
1173
0
                        *val_dst++ = ',';
1174
0
                        *val_dst++ = ' ';
1175
0
                    }
1176
0
                }
1177
0
                (*last)->val = new_val;
1178
0
            }
1179
0
            else { /* overwrite */
1180
0
                (*last)->val = (*dup_last)->val;
1181
0
            }
1182
0
            do {
1183
0
                (*sort_next)->key = NULL;
1184
0
            } while (++sort_next <= dup_last);
1185
0
        }
1186
0
        else {
1187
0
            last = sort_next++;
1188
0
        }
1189
0
    }
1190
1191
    /* Shift elements to the left to fill holes left by removing duplicates */
1192
0
    if (dups_found) {
1193
0
        apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
1194
0
        apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
1195
0
        apr_table_entry_t *last_elt = src + t->a.nelts;
1196
0
        do {
1197
0
            if (src->key) {
1198
0
                *dst++ = *src;
1199
0
            }
1200
0
        } while (++src < last_elt);
1201
0
        t->a.nelts -= (int)(last_elt - dst);
1202
0
    }
1203
1204
0
    table_reindex(t);
1205
0
}
1206
1207
static void apr_table_cat(apr_table_t *t, const apr_table_t *s)
1208
0
{
1209
0
    const int n = t->a.nelts;
1210
0
    register int idx;
1211
1212
0
    apr_array_cat(&t->a,&s->a);
1213
1214
0
    if (n == 0) {
1215
0
        memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
1216
0
        memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
1217
0
        t->index_initialized = s->index_initialized;
1218
0
        return;
1219
0
    }
1220
1221
0
    for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
1222
0
        if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
1223
0
            t->index_last[idx] = s->index_last[idx] + n;
1224
0
            if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
1225
0
                t->index_first[idx] = s->index_first[idx] + n;
1226
0
            }
1227
0
        }
1228
0
    }
1229
1230
0
    t->index_initialized |= s->index_initialized;
1231
0
}
1232
1233
APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
1234
            unsigned flags)
1235
0
{
1236
0
    if (a->a.nelts + b->a.nelts == 0) {
1237
0
        return;
1238
0
    }
1239
1240
0
#if APR_POOL_DEBUG
1241
    /* Since the keys and values are not copied, it's required that
1242
     * b->a.pool has a lifetime at least as long as a->a.pool. */
1243
0
    if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
1244
0
        fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
1245
0
        abort();
1246
0
    }
1247
0
#endif
1248
1249
0
    apr_table_cat(a, b);
1250
1251
0
    apr_table_compress(a, flags);
1252
0
}
1253
1254
static int table_getm_do(void *v, const char *key, const char *val)
1255
0
{
1256
0
    table_getm_t *state = (table_getm_t *) v;
1257
1258
0
    if (!state->first) {
1259
        /**
1260
         * The most common case is a single header, and this is covered by
1261
         * a fast path that doesn't allocate any memory. On the second and
1262
         * subsequent header, an array is created and the array concatenated
1263
         * together to form the final value.
1264
         */
1265
0
        state->first = val;
1266
0
    }
1267
0
    else {
1268
0
        const char **elt;
1269
0
        if (!state->merged) {
1270
0
            state->merged = apr_array_make(state->p, 10, sizeof(const char *));
1271
0
            elt = apr_array_push(state->merged);
1272
0
            *elt = state->first;
1273
0
        }
1274
0
        elt = apr_array_push(state->merged);
1275
0
        *elt = val;
1276
0
    }
1277
0
    return 1;
1278
0
}
1279
1280
APR_DECLARE(const char *) apr_table_getm(apr_pool_t *p, const apr_table_t *t,
1281
        const char *key)
1282
0
{
1283
0
    table_getm_t state;
1284
1285
0
    state.p = p;
1286
0
    state.first = NULL;
1287
0
    state.merged = NULL;
1288
1289
0
    apr_table_do(table_getm_do, &state, t, key, NULL);
1290
1291
0
    if (!state.first) {
1292
0
        return NULL;
1293
0
    }
1294
0
    else if (!state.merged) {
1295
0
        return state.first;
1296
0
    }
1297
0
    else {
1298
0
        return apr_array_pstrcat(p, state.merged, ',');
1299
0
    }
1300
0
}