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 54static 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 78APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a) 79{ 80 return ((a == NULL) || (a->nelts == 0)); 81} 82 83APR_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 93APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr) 94{ 95 arr->nelts = 0; 96} 97 98APR_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 107APR_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 126static 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 143APR_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 168APR_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 189static 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 198APR_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 212APR_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 */ 229APR_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 */ 332struct 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() */ 361typedef 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 373static 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 390APR_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 395APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t) 396{ 397 return ((t == NULL) || (t->a.nelts == 0)); 398} 399 400APR_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 412APR_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 434APR_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 448static 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 465APR_DECLARE(void) apr_table_clear(apr_table_t *t) 466{ 467 t->a.nelts = 0; 468 t->index_initialized = 0; 469} 470 471APR_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 500APR_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 564add_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 572APR_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 636add_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 644APR_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 698APR_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 727add_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 735APR_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 782add_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 790APR_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 810APR_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 843APR_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 */ 918APR_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 */ 961APR_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 1002static 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 1096APR_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 (flags == APR_OVERLAP_TABLES_ADD) { 1107 return; 1108 } 1109 1110 if (t->a.nelts <= 1) { 1111 return; 1112 } 1113 1114 /* Copy pointers to all the table elements into an 1115 * array and sort to allow for easy detection of 1116 * duplicate keys 1117 */ 1118 sort_array = (apr_table_entry_t **) 1119 apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*)); 1120 sort_next = sort_array; 1121 table_next = (apr_table_entry_t *)t->a.elts; 1122 i = t->a.nelts; 1123 do { 1124 *sort_next++ = table_next++; 1125 } while (--i); 1126 1127 /* Note: the merge is done with mergesort instead of quicksort 1128 * because mergesort is a stable sort and runs in n*log(n) 1129 * time regardless of its inputs (quicksort is quadratic in 1130 * the worst case) 1131 */ 1132 sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts); 1133 1134 /* Process any duplicate keys */ 1135 dups_found = 0; 1136 sort_next = sort_array; 1137 sort_end = sort_array + t->a.nelts; 1138 last = sort_next++; 1139 while (sort_next < sort_end) { 1140 if (((*sort_next)->key_checksum == (*last)->key_checksum) && 1141 !strcasecmp((*sort_next)->key, (*last)->key)) { 1142 apr_table_entry_t **dup_last = sort_next + 1; 1143 dups_found = 1; 1144 while ((dup_last < sort_end) && 1145 ((*dup_last)->key_checksum == (*last)->key_checksum) && 1146 !strcasecmp((*dup_last)->key, (*last)->key)) { 1147 dup_last++; 1148 } 1149 dup_last--; /* Elements from last through dup_last, inclusive, 1150 * all have the same key 1151 */ 1152 if (flags == APR_OVERLAP_TABLES_MERGE) { 1153 apr_size_t len = 0; 1154 apr_table_entry_t **next = last; 1155 char *new_val; 1156 char *val_dst; 1157 do { 1158 len += strlen((*next)->val); 1159 len += 2; /* for ", " or trailing null */ 1160 } while (++next <= dup_last); 1161 new_val = (char *)apr_palloc(t->a.pool, len); 1162 val_dst = new_val; 1163 next = last; 1164 for (;;) { 1165 strcpy(val_dst, (*next)->val); 1166 val_dst += strlen((*next)->val); 1167 next++; 1168 if (next > dup_last) { 1169 *val_dst = 0; 1170 break; 1171 } 1172 else { 1173 *val_dst++ = ','; 1174 *val_dst++ = ' '; 1175 } 1176 } 1177 (*last)->val = new_val; 1178 } 1179 else { /* overwrite */ 1180 (*last)->val = (*dup_last)->val; 1181 } 1182 do { 1183 (*sort_next)->key = NULL; 1184 } while (++sort_next <= dup_last); 1185 } 1186 else { 1187 last = sort_next++; 1188 } 1189 } 1190 1191 /* Shift elements to the left to fill holes left by removing duplicates */ 1192 if (dups_found) { 1193 apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts; 1194 apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts; 1195 apr_table_entry_t *last_elt = src + t->a.nelts; 1196 do { 1197 if (src->key) { 1198 *dst++ = *src; 1199 } 1200 } while (++src < last_elt); 1201 t->a.nelts -= (int)(last_elt - dst); 1202 } 1203 1204 table_reindex(t); 1205} 1206 1207static void apr_table_cat(apr_table_t *t, const apr_table_t *s) 1208{ 1209 const int n = t->a.nelts; 1210 register int idx; 1211 1212 apr_array_cat(&t->a,&s->a); 1213 1214 if (n == 0) { 1215 memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE); 1216 memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE); 1217 t->index_initialized = s->index_initialized; 1218 return; 1219 } 1220 1221 for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) { 1222 if (TABLE_INDEX_IS_INITIALIZED(s, idx)) { 1223 t->index_last[idx] = s->index_last[idx] + n; 1224 if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) { 1225 t->index_first[idx] = s->index_first[idx] + n; 1226 } 1227 } 1228 } 1229 1230 t->index_initialized |= s->index_initialized; 1231} 1232 1233APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, 1234 unsigned flags) 1235{ 1236 if (a->a.nelts + b->a.nelts == 0) { 1237 return; 1238 } 1239 1240#if APR_POOL_DEBUG 1241 /* Since the keys and values are not copied, it's required that 1242 * b->a.pool has a lifetime at least as long as a->a.pool. */ 1243 if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) { 1244 fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n"); 1245 abort(); 1246 } 1247#endif 1248 1249 apr_table_cat(a, b); 1250 1251 apr_table_compress(a, flags); 1252} 1253 1254static int table_getm_do(void *v, const char *key, const char *val) 1255{ 1256 table_getm_t *state = (table_getm_t *) v; 1257 1258 if (!state->first) { 1259 /** 1260 * The most common case is a single header, and this is covered by 1261 * a fast path that doesn't allocate any memory. On the second and 1262 * subsequent header, an array is created and the array concatenated 1263 * together to form the final value. 1264 */ 1265 state->first = val; 1266 } 1267 else { 1268 const char **elt; 1269 if (!state->merged) { 1270 state->merged = apr_array_make(state->p, 10, sizeof(const char *)); 1271 elt = apr_array_push(state->merged); 1272 *elt = state->first; 1273 } 1274 elt = apr_array_push(state->merged); 1275 *elt = val; 1276 } 1277 return 1; 1278} 1279 1280APR_DECLARE(const char *) apr_table_getm(apr_pool_t *p, const apr_table_t *t, 1281 const char *key) 1282{ 1283 table_getm_t state; 1284 1285 state.p = p; 1286 state.first = NULL; 1287 state.merged = NULL; 1288 1289 apr_table_do(table_getm_do, &state, t, key, NULL); 1290 1291 if (!state.first) { 1292 return NULL; 1293 } 1294 else if (!state.merged) { 1295 return state.first; 1296 } 1297 else { 1298 return apr_array_pstrcat(p, state.merged, ','); 1299 } 1300} 1301