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/* 361 * NOTICE: if you tweak this you should look at is_empty_table() 362 * and table_elts() in alloc.h 363 */ 364#ifdef MAKE_TABLE_PROFILE 365static apr_table_entry_t *do_table_push(const char *func, apr_table_t *t) 366{ 367 if (t->a.nelts == t->a.nalloc) { 368 fprintf(stderr, "%s: table created by %p hit limit of %u\n", 369 func ? func : "table_push", t->creator, t->a.nalloc); 370 } 371 return (apr_table_entry_t *) apr_array_push_noclear(&t->a); 372} 373#if defined(__GNUC__) && __GNUC__ >= 2 374#define table_push(t) do_table_push(__FUNCTION__, t) 375#else 376#define table_push(t) do_table_push(NULL, t) 377#endif 378#else /* MAKE_TABLE_PROFILE */ 379#define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a)) 380#endif /* MAKE_TABLE_PROFILE */ 381 382APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t) 383{ 384 return (const apr_array_header_t *)t; 385} 386 387APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t) 388{ 389 return ((t == NULL) || (t->a.nelts == 0)); 390} 391 392APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts) 393{ 394 apr_table_t *t = apr_palloc(p, sizeof(apr_table_t)); 395 396 make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0); 397#ifdef MAKE_TABLE_PROFILE 398 t->creator = __builtin_return_address(0); 399#endif 400 t->index_initialized = 0; 401 return t; 402} 403 404APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t) 405{ 406 apr_table_t *new = apr_palloc(p, sizeof(apr_table_t)); 407 408#if APR_POOL_DEBUG 409 /* we don't copy keys and values, so it's necessary that t->a.pool 410 * have a life span at least as long as p 411 */ 412 if (!apr_pool_is_ancestor(t->a.pool, p)) { 413 fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n"); 414 abort(); 415 } 416#endif 417 make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0); 418 memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t)); 419 new->a.nelts = t->a.nelts; 420 memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE); 421 memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE); 422 new->index_initialized = t->index_initialized; 423 return new; 424} 425 426APR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t) 427{ 428 const apr_array_header_t *array = apr_table_elts(t); 429 apr_table_entry_t *elts = (apr_table_entry_t *) array->elts; 430 apr_table_t *new = apr_table_make(p, array->nelts); 431 int i; 432 433 for (i = 0; i < array->nelts; i++) { 434 apr_table_add(new, elts[i].key, elts[i].val); 435 } 436 437 return new; 438} 439 440static void table_reindex(apr_table_t *t) 441{ 442 int i; 443 int hash; 444 apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts; 445 446 t->index_initialized = 0; 447 for (i = 0; i < t->a.nelts; i++, next_elt++) { 448 hash = TABLE_HASH(next_elt->key); 449 t->index_last[hash] = i; 450 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 451 t->index_first[hash] = i; 452 TABLE_SET_INDEX_INITIALIZED(t, hash); 453 } 454 } 455} 456 457APR_DECLARE(void) apr_table_clear(apr_table_t *t) 458{ 459 t->a.nelts = 0; 460 t->index_initialized = 0; 461} 462 463APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key) 464{ 465 apr_table_entry_t *next_elt; 466 apr_table_entry_t *end_elt; 467 apr_uint32_t checksum; 468 int hash; 469 470 if (key == NULL) { 471 return NULL; 472 } 473 474 hash = TABLE_HASH(key); 475 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 476 return NULL; 477 } 478 COMPUTE_KEY_CHECKSUM(key, checksum); 479 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 480 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 481 482 for (; next_elt <= end_elt; next_elt++) { 483 if ((checksum == next_elt->key_checksum) && 484 !strcasecmp(next_elt->key, key)) { 485 return next_elt->val; 486 } 487 } 488 489 return NULL; 490} 491 492APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key, 493 const char *val) 494{ 495 apr_table_entry_t *next_elt; 496 apr_table_entry_t *end_elt; 497 apr_table_entry_t *table_end; 498 apr_uint32_t checksum; 499 int hash; 500 501 COMPUTE_KEY_CHECKSUM(key, checksum); 502 hash = TABLE_HASH(key); 503 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 504 t->index_first[hash] = t->a.nelts; 505 TABLE_SET_INDEX_INITIALIZED(t, hash); 506 goto add_new_elt; 507 } 508 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 509 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 510 table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts; 511 512 for (; next_elt <= end_elt; next_elt++) { 513 if ((checksum == next_elt->key_checksum) && 514 !strcasecmp(next_elt->key, key)) { 515 516 /* Found an existing entry with the same key, so overwrite it */ 517 518 int must_reindex = 0; 519 apr_table_entry_t *dst_elt = NULL; 520 521 next_elt->val = apr_pstrdup(t->a.pool, val); 522 523 /* Remove any other instances of this key */ 524 for (next_elt++; next_elt <= end_elt; next_elt++) { 525 if ((checksum == next_elt->key_checksum) && 526 !strcasecmp(next_elt->key, key)) { 527 t->a.nelts--; 528 if (!dst_elt) { 529 dst_elt = next_elt; 530 } 531 } 532 else if (dst_elt) { 533 *dst_elt++ = *next_elt; 534 must_reindex = 1; 535 } 536 } 537 538 /* If we've removed anything, shift over the remainder 539 * of the table (note that the previous loop didn't 540 * run to the end of the table, just to the last match 541 * for the index) 542 */ 543 if (dst_elt) { 544 for (; next_elt < table_end; next_elt++) { 545 *dst_elt++ = *next_elt; 546 } 547 must_reindex = 1; 548 } 549 if (must_reindex) { 550 table_reindex(t); 551 } 552 return; 553 } 554 } 555 556add_new_elt: 557 t->index_last[hash] = t->a.nelts; 558 next_elt = (apr_table_entry_t *) table_push(t); 559 next_elt->key = apr_pstrdup(t->a.pool, key); 560 next_elt->val = apr_pstrdup(t->a.pool, val); 561 next_elt->key_checksum = checksum; 562} 563 564APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key, 565 const char *val) 566{ 567 apr_table_entry_t *next_elt; 568 apr_table_entry_t *end_elt; 569 apr_table_entry_t *table_end; 570 apr_uint32_t checksum; 571 int hash; 572 573 COMPUTE_KEY_CHECKSUM(key, checksum); 574 hash = TABLE_HASH(key); 575 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 576 t->index_first[hash] = t->a.nelts; 577 TABLE_SET_INDEX_INITIALIZED(t, hash); 578 goto add_new_elt; 579 } 580 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 581 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 582 table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts; 583 584 for (; next_elt <= end_elt; next_elt++) { 585 if ((checksum == next_elt->key_checksum) && 586 !strcasecmp(next_elt->key, key)) { 587 588 /* Found an existing entry with the same key, so overwrite it */ 589 590 int must_reindex = 0; 591 apr_table_entry_t *dst_elt = NULL; 592 593 next_elt->val = (char *)val; 594 595 /* Remove any other instances of this key */ 596 for (next_elt++; next_elt <= end_elt; next_elt++) { 597 if ((checksum == next_elt->key_checksum) && 598 !strcasecmp(next_elt->key, key)) { 599 t->a.nelts--; 600 if (!dst_elt) { 601 dst_elt = next_elt; 602 } 603 } 604 else if (dst_elt) { 605 *dst_elt++ = *next_elt; 606 must_reindex = 1; 607 } 608 } 609 610 /* If we've removed anything, shift over the remainder 611 * of the table (note that the previous loop didn't 612 * run to the end of the table, just to the last match 613 * for the index) 614 */ 615 if (dst_elt) { 616 for (; next_elt < table_end; next_elt++) { 617 *dst_elt++ = *next_elt; 618 } 619 must_reindex = 1; 620 } 621 if (must_reindex) { 622 table_reindex(t); 623 } 624 return; 625 } 626 } 627 628add_new_elt: 629 t->index_last[hash] = t->a.nelts; 630 next_elt = (apr_table_entry_t *) table_push(t); 631 next_elt->key = (char *)key; 632 next_elt->val = (char *)val; 633 next_elt->key_checksum = checksum; 634} 635 636APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key) 637{ 638 apr_table_entry_t *next_elt; 639 apr_table_entry_t *end_elt; 640 apr_table_entry_t *dst_elt; 641 apr_uint32_t checksum; 642 int hash; 643 int must_reindex; 644 645 hash = TABLE_HASH(key); 646 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 647 return; 648 } 649 COMPUTE_KEY_CHECKSUM(key, checksum); 650 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash]; 651 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 652 must_reindex = 0; 653 for (; next_elt <= end_elt; next_elt++) { 654 if ((checksum == next_elt->key_checksum) && 655 !strcasecmp(next_elt->key, key)) { 656 657 /* Found a match: remove this entry, plus any additional 658 * matches for the same key that might follow 659 */ 660 apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) + 661 t->a.nelts; 662 t->a.nelts--; 663 dst_elt = next_elt; 664 for (next_elt++; next_elt <= end_elt; next_elt++) { 665 if ((checksum == next_elt->key_checksum) && 666 !strcasecmp(next_elt->key, key)) { 667 t->a.nelts--; 668 } 669 else { 670 *dst_elt++ = *next_elt; 671 } 672 } 673 674 /* Shift over the remainder of the table (note that 675 * the previous loop didn't run to the end of the table, 676 * just to the last match for the index) 677 */ 678 for (; next_elt < table_end; next_elt++) { 679 *dst_elt++ = *next_elt; 680 } 681 must_reindex = 1; 682 break; 683 } 684 } 685 if (must_reindex) { 686 table_reindex(t); 687 } 688} 689 690APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key, 691 const char *val) 692{ 693 apr_table_entry_t *next_elt; 694 apr_table_entry_t *end_elt; 695 apr_uint32_t checksum; 696 int hash; 697 698 COMPUTE_KEY_CHECKSUM(key, checksum); 699 hash = TABLE_HASH(key); 700 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 701 t->index_first[hash] = t->a.nelts; 702 TABLE_SET_INDEX_INITIALIZED(t, hash); 703 goto add_new_elt; 704 } 705 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash]; 706 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 707 708 for (; next_elt <= end_elt; next_elt++) { 709 if ((checksum == next_elt->key_checksum) && 710 !strcasecmp(next_elt->key, key)) { 711 712 /* Found an existing entry with the same key, so merge with it */ 713 next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ", 714 val, NULL); 715 return; 716 } 717 } 718 719add_new_elt: 720 t->index_last[hash] = t->a.nelts; 721 next_elt = (apr_table_entry_t *) table_push(t); 722 next_elt->key = apr_pstrdup(t->a.pool, key); 723 next_elt->val = apr_pstrdup(t->a.pool, val); 724 next_elt->key_checksum = checksum; 725} 726 727APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key, 728 const char *val) 729{ 730 apr_table_entry_t *next_elt; 731 apr_table_entry_t *end_elt; 732 apr_uint32_t checksum; 733 int hash; 734 735#if APR_POOL_DEBUG 736 { 737 apr_pool_t *pool; 738 pool = apr_pool_find(key); 739 if ((pool != key) && (!apr_pool_is_ancestor(pool, t->a.pool))) { 740 fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n"); 741 abort(); 742 } 743 pool = apr_pool_find(val); 744 if ((pool != val) && (!apr_pool_is_ancestor(pool, t->a.pool))) { 745 fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n"); 746 abort(); 747 } 748 } 749#endif 750 751 COMPUTE_KEY_CHECKSUM(key, checksum); 752 hash = TABLE_HASH(key); 753 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 754 t->index_first[hash] = t->a.nelts; 755 TABLE_SET_INDEX_INITIALIZED(t, hash); 756 goto add_new_elt; 757 } 758 next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 759 end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 760 761 for (; next_elt <= end_elt; next_elt++) { 762 if ((checksum == next_elt->key_checksum) && 763 !strcasecmp(next_elt->key, key)) { 764 765 /* Found an existing entry with the same key, so merge with it */ 766 next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ", 767 val, NULL); 768 return; 769 } 770 } 771 772add_new_elt: 773 t->index_last[hash] = t->a.nelts; 774 next_elt = (apr_table_entry_t *) table_push(t); 775 next_elt->key = (char *)key; 776 next_elt->val = (char *)val; 777 next_elt->key_checksum = checksum; 778} 779 780APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key, 781 const char *val) 782{ 783 apr_table_entry_t *elts; 784 apr_uint32_t checksum; 785 int hash; 786 787 hash = TABLE_HASH(key); 788 t->index_last[hash] = t->a.nelts; 789 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 790 t->index_first[hash] = t->a.nelts; 791 TABLE_SET_INDEX_INITIALIZED(t, hash); 792 } 793 COMPUTE_KEY_CHECKSUM(key, checksum); 794 elts = (apr_table_entry_t *) table_push(t); 795 elts->key = apr_pstrdup(t->a.pool, key); 796 elts->val = apr_pstrdup(t->a.pool, val); 797 elts->key_checksum = checksum; 798} 799 800APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key, 801 const char *val) 802{ 803 apr_table_entry_t *elts; 804 apr_uint32_t checksum; 805 int hash; 806 807#if APR_POOL_DEBUG 808 { 809 if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) { 810 fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n"); 811 abort(); 812 } 813 if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) { 814 fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n"); 815 abort(); 816 } 817 } 818#endif 819 820 hash = TABLE_HASH(key); 821 t->index_last[hash] = t->a.nelts; 822 if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 823 t->index_first[hash] = t->a.nelts; 824 TABLE_SET_INDEX_INITIALIZED(t, hash); 825 } 826 COMPUTE_KEY_CHECKSUM(key, checksum); 827 elts = (apr_table_entry_t *) table_push(t); 828 elts->key = (char *)key; 829 elts->val = (char *)val; 830 elts->key_checksum = checksum; 831} 832 833APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p, 834 const apr_table_t *overlay, 835 const apr_table_t *base) 836{ 837 apr_table_t *res; 838 839#if APR_POOL_DEBUG 840 /* we don't copy keys and values, so it's necessary that 841 * overlay->a.pool and base->a.pool have a life span at least 842 * as long as p 843 */ 844 if (!apr_pool_is_ancestor(overlay->a.pool, p)) { 845 fprintf(stderr, 846 "apr_table_overlay: overlay's pool is not an ancestor of p\n"); 847 abort(); 848 } 849 if (!apr_pool_is_ancestor(base->a.pool, p)) { 850 fprintf(stderr, 851 "apr_table_overlay: base's pool is not an ancestor of p\n"); 852 abort(); 853 } 854#endif 855 856 res = apr_palloc(p, sizeof(apr_table_t)); 857 /* behave like append_arrays */ 858 res->a.pool = p; 859 copy_array_hdr_core(&res->a, &overlay->a); 860 apr_array_cat(&res->a, &base->a); 861 table_reindex(res); 862 return res; 863} 864 865/* And now for something completely abstract ... 866 867 * For each key value given as a vararg: 868 * run the function pointed to as 869 * int comp(void *r, char *key, char *value); 870 * on each valid key-value pair in the apr_table_t t that matches the vararg key, 871 * or once for every valid key-value pair if the vararg list is empty, 872 * until the function returns false (0) or we finish the table. 873 * 874 * Note that we restart the traversal for each vararg, which means that 875 * duplicate varargs will result in multiple executions of the function 876 * for each matching key. Note also that if the vararg list is empty, 877 * only one traversal will be made and will cut short if comp returns 0. 878 * 879 * Note that the table_get and table_merge functions assume that each key in 880 * the apr_table_t is unique (i.e., no multiple entries with the same key). This 881 * function does not make that assumption, since it (unfortunately) isn't 882 * true for some of Apache's tables. 883 * 884 * Note that rec is simply passed-on to the comp function, so that the 885 * caller can pass additional info for the task. 886 * 887 * ADDENDUM for apr_table_vdo(): 888 * 889 * The caching api will allow a user to walk the header values: 890 * 891 * apr_status_t apr_cache_el_header_walk(apr_cache_el *el, 892 * int (*comp)(void *, const char *, const char *), void *rec, ...); 893 * 894 * So it can be ..., however from there I use a callback that use a va_list: 895 * 896 * apr_status_t (*cache_el_header_walk)(apr_cache_el *el, 897 * int (*comp)(void *, const char *, const char *), void *rec, va_list); 898 * 899 * To pass those ...'s on down to the actual module that will handle walking 900 * their headers, in the file case this is actually just an apr_table - and 901 * rather than reimplementing apr_table_do (which IMHO would be bad) I just 902 * called it with the va_list. For mod_shmem_cache I don't need it since I 903 * can't use apr_table's, but mod_file_cache should (though a good hash would 904 * be better, but that's a different issue :). 905 * 906 * So to make mod_file_cache easier to maintain, it's a good thing 907 */ 908APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp, 909 void *rec, const apr_table_t *t, ...) 910{ 911 int rv; 912 913 va_list vp; 914 va_start(vp, t); 915 rv = apr_table_vdo(comp, rec, t, vp); 916 va_end(vp); 917 918 return rv; 919} 920 921/* XXX: do the semantics of this routine make any sense? Right now, 922 * if the caller passed in a non-empty va_list of keys to search for, 923 * the "early termination" facility only terminates on *that* key; other 924 * keys will continue to process. Note that this only has any effect 925 * at all if there are multiple entries in the table with the same key, 926 * otherwise the called function can never effectively early-terminate 927 * this function, as the zero return value is effectively ignored. 928 * 929 * Note also that this behavior is at odds with the behavior seen if an 930 * empty va_list is passed in -- in that case, a zero return value terminates 931 * the entire apr_table_vdo (which is what I think should happen in 932 * both cases). 933 * 934 * If nobody objects soon, I'm going to change the order of the nested 935 * loops in this function so that any zero return value from the (*comp) 936 * function will cause a full termination of apr_table_vdo. I'm hesitant 937 * at the moment because these (funky) semantics have been around for a 938 * very long time, and although Apache doesn't seem to use them at all, 939 * some third-party vendor might. I can only think of one possible reason 940 * the existing semantics would make any sense, and it's very Apache-centric, 941 * which is this: if (*comp) is looking for matches of a particular 942 * substring in request headers (let's say it's looking for a particular 943 * cookie name in the Set-Cookie headers), then maybe it wants to be 944 * able to stop searching early as soon as it finds that one and move 945 * on to the next key. That's only an optimization of course, but changing 946 * the behavior of this function would mean that any code that tried 947 * to do that would stop working right. 948 * 949 * Sigh. --JCW, 06/28/02 950 */ 951APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp, 952 void *rec, const apr_table_t *t, va_list vp) 953{ 954 char *argp; 955 apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; 956 int vdorv = 1; 957 958 argp = va_arg(vp, char *); 959 do { 960 int rv = 1, i; 961 if (argp) { 962 /* Scan for entries that match the next key */ 963 int hash = TABLE_HASH(argp); 964 if (TABLE_INDEX_IS_INITIALIZED(t, hash)) { 965 apr_uint32_t checksum; 966 COMPUTE_KEY_CHECKSUM(argp, checksum); 967 for (i = t->index_first[hash]; 968 rv && (i <= t->index_last[hash]); ++i) { 969 if (elts[i].key && (checksum == elts[i].key_checksum) && 970 !strcasecmp(elts[i].key, argp)) { 971 rv = (*comp) (rec, elts[i].key, elts[i].val); 972 } 973 } 974 } 975 } 976 else { 977 /* Scan the entire table */ 978 for (i = 0; rv && (i < t->a.nelts); ++i) { 979 if (elts[i].key) { 980 rv = (*comp) (rec, elts[i].key, elts[i].val); 981 } 982 } 983 } 984 if (rv == 0) { 985 vdorv = 0; 986 } 987 } while (argp && ((argp = va_arg(vp, char *)) != NULL)); 988 989 return vdorv; 990} 991 992static apr_table_entry_t **table_mergesort(apr_pool_t *pool, 993 apr_table_entry_t **values, 994 apr_size_t n) 995{ 996 /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms 997 * in C," chapter 8 998 */ 999 apr_table_entry_t **values_tmp = 1000 (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*)); 1001 apr_size_t i; 1002 apr_size_t blocksize; 1003 1004 /* First pass: sort pairs of elements (blocksize=1) */ 1005 for (i = 0; i + 1 < n; i += 2) { 1006 if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) { 1007 apr_table_entry_t *swap = values[i]; 1008 values[i] = values[i + 1]; 1009 values[i + 1] = swap; 1010 } 1011 } 1012 1013 /* Merge successively larger blocks */ 1014 blocksize = 2; 1015 while (blocksize < n) { 1016 apr_table_entry_t **dst = values_tmp; 1017 apr_size_t next_start; 1018 apr_table_entry_t **swap; 1019 1020 /* Merge consecutive pairs blocks of the next blocksize. 1021 * Within a block, elements are in sorted order due to 1022 * the previous iteration. 1023 */ 1024 for (next_start = 0; next_start + blocksize < n; 1025 next_start += (blocksize + blocksize)) { 1026 1027 apr_size_t block1_start = next_start; 1028 apr_size_t block2_start = block1_start + blocksize; 1029 apr_size_t block1_end = block2_start; 1030 apr_size_t block2_end = block2_start + blocksize; 1031 if (block2_end > n) { 1032 /* The last block may be smaller than blocksize */ 1033 block2_end = n; 1034 } 1035 for (;;) { 1036 1037 /* Merge the next two blocks: 1038 * Pick the smaller of the next element from 1039 * block 1 and the next element from block 2. 1040 * Once either of the blocks is emptied, copy 1041 * over all the remaining elements from the 1042 * other block 1043 */ 1044 if (block1_start == block1_end) { 1045 for (; block2_start < block2_end; block2_start++) { 1046 *dst++ = values[block2_start]; 1047 } 1048 break; 1049 } 1050 else if (block2_start == block2_end) { 1051 for (; block1_start < block1_end; block1_start++) { 1052 *dst++ = values[block1_start]; 1053 } 1054 break; 1055 } 1056 if (strcasecmp(values[block1_start]->key, 1057 values[block2_start]->key) > 0) { 1058 *dst++ = values[block2_start++]; 1059 } 1060 else { 1061 *dst++ = values[block1_start++]; 1062 } 1063 } 1064 } 1065 1066 /* If n is not a multiple of 2*blocksize, some elements 1067 * will be left over at the end of the array. 1068 */ 1069 for (i = dst - values_tmp; i < n; i++) { 1070 values_tmp[i] = values[i]; 1071 } 1072 1073 /* The output array of this pass becomes the input 1074 * array of the next pass, and vice versa 1075 */ 1076 swap = values_tmp; 1077 values_tmp = values; 1078 values = swap; 1079 1080 blocksize += blocksize; 1081 } 1082 1083 return values; 1084} 1085 1086APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags) 1087{ 1088 apr_table_entry_t **sort_array; 1089 apr_table_entry_t **sort_next; 1090 apr_table_entry_t **sort_end; 1091 apr_table_entry_t *table_next; 1092 apr_table_entry_t **last; 1093 int i; 1094 int dups_found; 1095 1096 if (t->a.nelts <= 1) { 1097 return; 1098 } 1099 1100 /* Copy pointers to all the table elements into an 1101 * array and sort to allow for easy detection of 1102 * duplicate keys 1103 */ 1104 sort_array = (apr_table_entry_t **) 1105 apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*)); 1106 sort_next = sort_array; 1107 table_next = (apr_table_entry_t *)t->a.elts; 1108 i = t->a.nelts; 1109 do { 1110 *sort_next++ = table_next++; 1111 } while (--i); 1112 1113 /* Note: the merge is done with mergesort instead of quicksort 1114 * because mergesort is a stable sort and runs in n*log(n) 1115 * time regardless of its inputs (quicksort is quadratic in 1116 * the worst case) 1117 */ 1118 sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts); 1119 1120 /* Process any duplicate keys */ 1121 dups_found = 0; 1122 sort_next = sort_array; 1123 sort_end = sort_array + t->a.nelts; 1124 last = sort_next++; 1125 while (sort_next < sort_end) { 1126 if (((*sort_next)->key_checksum == (*last)->key_checksum) && 1127 !strcasecmp((*sort_next)->key, (*last)->key)) { 1128 apr_table_entry_t **dup_last = sort_next + 1; 1129 dups_found = 1; 1130 while ((dup_last < sort_end) && 1131 ((*dup_last)->key_checksum == (*last)->key_checksum) && 1132 !strcasecmp((*dup_last)->key, (*last)->key)) { 1133 dup_last++; 1134 } 1135 dup_last--; /* Elements from last through dup_last, inclusive, 1136 * all have the same key 1137 */ 1138 if (flags == APR_OVERLAP_TABLES_MERGE) { 1139 apr_size_t len = 0; 1140 apr_table_entry_t **next = last; 1141 char *new_val; 1142 char *val_dst; 1143 do { 1144 len += strlen((*next)->val); 1145 len += 2; /* for ", " or trailing null */ 1146 } while (++next <= dup_last); 1147 new_val = (char *)apr_palloc(t->a.pool, len); 1148 val_dst = new_val; 1149 next = last; 1150 for (;;) { 1151 strcpy(val_dst, (*next)->val); 1152 val_dst += strlen((*next)->val); 1153 next++; 1154 if (next > dup_last) { 1155 *val_dst = 0; 1156 break; 1157 } 1158 else { 1159 *val_dst++ = ','; 1160 *val_dst++ = ' '; 1161 } 1162 } 1163 (*last)->val = new_val; 1164 } 1165 else { /* overwrite */ 1166 (*last)->val = (*dup_last)->val; 1167 } 1168 do { 1169 (*sort_next)->key = NULL; 1170 } while (++sort_next <= dup_last); 1171 } 1172 else { 1173 last = sort_next++; 1174 } 1175 } 1176 1177 /* Shift elements to the left to fill holes left by removing duplicates */ 1178 if (dups_found) { 1179 apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts; 1180 apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts; 1181 apr_table_entry_t *last_elt = src + t->a.nelts; 1182 do { 1183 if (src->key) { 1184 *dst++ = *src; 1185 } 1186 } while (++src < last_elt); 1187 t->a.nelts -= (int)(last_elt - dst); 1188 } 1189 1190 table_reindex(t); 1191} 1192 1193static void apr_table_cat(apr_table_t *t, const apr_table_t *s) 1194{ 1195 const int n = t->a.nelts; 1196 register int idx; 1197 1198 apr_array_cat(&t->a,&s->a); 1199 1200 if (n == 0) { 1201 memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE); 1202 memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE); 1203 t->index_initialized = s->index_initialized; 1204 return; 1205 } 1206 1207 for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) { 1208 if (TABLE_INDEX_IS_INITIALIZED(s, idx)) { 1209 t->index_last[idx] = s->index_last[idx] + n; 1210 if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) { 1211 t->index_first[idx] = s->index_first[idx] + n; 1212 } 1213 } 1214 } 1215 1216 t->index_initialized |= s->index_initialized; 1217} 1218 1219APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, 1220 unsigned flags) 1221{ 1222 if (a->a.nelts + b->a.nelts == 0) { 1223 return; 1224 } 1225 1226#if APR_POOL_DEBUG 1227 /* Since the keys and values are not copied, it's required that 1228 * b->a.pool has a lifetime at least as long as a->a.pool. */ 1229 if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) { 1230 fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n"); 1231 abort(); 1232 } 1233#endif 1234 1235 apr_table_cat(a, b); 1236 1237 apr_table_compress(a, flags); 1238} 1239