rubbos/app/httpd-2.0.64/srclib/apr/tables/apr_tables.c

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