contrib/apr/tables/apr_tables.c

   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 {
  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
  78 APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
  79 {
  80     return ((a == NULL) || (a->nelts == 0));
  81 }
  82
  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
  93 APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
  94 {
  95     arr->nelts = 0;
  96 }
  97
  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
 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
 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
 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
 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
 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 *)
 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 *)
 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  */
 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
 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
 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
 395 APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
 396 {
 397     return ((t == NULL) || (t->a.nelts == 0));
 398 }
 399
 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
 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
 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
 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
 465 APR_DECLARE(void) apr_table_clear(apr_table_t *t)
 466 {
 467     t->a.nelts = 0;
 468     t->index_initialized = 0;
 469 }
 470
 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
 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
 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
 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
 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
 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
 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
 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
 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  */
 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  */
 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
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
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
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
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
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
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 }