1251875Speter/* Licensed to the Apache Software Foundation (ASF) under one or more 2251875Speter * contributor license agreements. See the NOTICE file distributed with 3251875Speter * this work for additional information regarding copyright ownership. 4251875Speter * The ASF licenses this file to You under the Apache License, Version 2.0 5251875Speter * (the "License"); you may not use this file except in compliance with 6251875Speter * the License. You may obtain a copy of the License at 7251875Speter * 8251875Speter * http://www.apache.org/licenses/LICENSE-2.0 9251875Speter * 10251875Speter * Unless required by applicable law or agreed to in writing, software 11251875Speter * distributed under the License is distributed on an "AS IS" BASIS, 12251875Speter * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13251875Speter * See the License for the specific language governing permissions and 14251875Speter * limitations under the License. 15251875Speter */ 16251875Speter 17251875Speter/* 18251875Speter * Resource allocation code... the code here is responsible for making 19251875Speter * sure that nothing leaks. 20251875Speter * 21251875Speter * rst --- 4/95 --- 6/95 22251875Speter */ 23251875Speter 24251875Speter#include "apr_private.h" 25251875Speter 26251875Speter#include "apr_general.h" 27251875Speter#include "apr_pools.h" 28251875Speter#include "apr_tables.h" 29251875Speter#include "apr_strings.h" 30251875Speter#include "apr_lib.h" 31251875Speter#if APR_HAVE_STDLIB_H 32251875Speter#include <stdlib.h> 33251875Speter#endif 34251875Speter#if APR_HAVE_STRING_H 35251875Speter#include <string.h> 36251875Speter#endif 37251875Speter#if APR_HAVE_STRINGS_H 38251875Speter#include <strings.h> 39251875Speter#endif 40251875Speter 41251875Speter#if (APR_POOL_DEBUG || defined(MAKE_TABLE_PROFILE)) && APR_HAVE_STDIO_H 42251875Speter#include <stdio.h> 43251875Speter#endif 44251875Speter 45251875Speter/***************************************************************** 46251875Speter * This file contains array and apr_table_t functions only. 47251875Speter */ 48251875Speter 49251875Speter/***************************************************************** 50251875Speter * 51251875Speter * The 'array' functions... 52251875Speter */ 53251875Speter 54251875Speterstatic void make_array_core(apr_array_header_t *res, apr_pool_t *p, 55251875Speter int nelts, int elt_size, int clear) 56251875Speter{ 57251875Speter /* 58251875Speter * Assure sanity if someone asks for 59251875Speter * array of zero elts. 60251875Speter */ 61251875Speter if (nelts < 1) { 62251875Speter nelts = 1; 63251875Speter } 64251875Speter 65251875Speter if (clear) { 66251875Speter res->elts = apr_pcalloc(p, nelts * elt_size); 67251875Speter } 68251875Speter else { 69251875Speter res->elts = apr_palloc(p, nelts * elt_size); 70251875Speter } 71251875Speter 72251875Speter res->pool = p; 73251875Speter res->elt_size = elt_size; 74251875Speter res->nelts = 0; /* No active elements yet... */ 75251875Speter res->nalloc = nelts; /* ...but this many allocated */ 76251875Speter} 77251875Speter 78251875SpeterAPR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a) 79251875Speter{ 80251875Speter return ((a == NULL) || (a->nelts == 0)); 81251875Speter} 82251875Speter 83251875SpeterAPR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p, 84251875Speter int nelts, int elt_size) 85251875Speter{ 86251875Speter apr_array_header_t *res; 87251875Speter 88251875Speter res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t)); 89251875Speter make_array_core(res, p, nelts, elt_size, 1); 90251875Speter return res; 91251875Speter} 92251875Speter 93251875SpeterAPR_DECLARE(void) apr_array_clear(apr_array_header_t *arr) 94251875Speter{ 95251875Speter arr->nelts = 0; 96251875Speter} 97251875Speter 98251875SpeterAPR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr) 99251875Speter{ 100251875Speter if (apr_is_empty_array(arr)) { 101251875Speter return NULL; 102251875Speter } 103251875Speter 104251875Speter return arr->elts + (arr->elt_size * (--arr->nelts)); 105251875Speter} 106251875Speter 107251875SpeterAPR_DECLARE(void *) apr_array_push(apr_array_header_t *arr) 108251875Speter{ 109251875Speter if (arr->nelts == arr->nalloc) { 110251875Speter int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2; 111251875Speter char *new_data; 112251875Speter 113251875Speter new_data = apr_palloc(arr->pool, arr->elt_size * new_size); 114251875Speter 115251875Speter memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size); 116251875Speter memset(new_data + arr->nalloc * arr->elt_size, 0, 117251875Speter arr->elt_size * (new_size - arr->nalloc)); 118251875Speter arr->elts = new_data; 119251875Speter arr->nalloc = new_size; 120251875Speter } 121251875Speter 122251875Speter ++arr->nelts; 123251875Speter return arr->elts + (arr->elt_size * (arr->nelts - 1)); 124251875Speter} 125251875Speter 126251875Speterstatic void *apr_array_push_noclear(apr_array_header_t *arr) 127251875Speter{ 128251875Speter if (arr->nelts == arr->nalloc) { 129251875Speter int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2; 130251875Speter char *new_data; 131251875Speter 132251875Speter new_data = apr_palloc(arr->pool, arr->elt_size * new_size); 133251875Speter 134251875Speter memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size); 135251875Speter arr->elts = new_data; 136251875Speter arr->nalloc = new_size; 137251875Speter } 138251875Speter 139251875Speter ++arr->nelts; 140251875Speter return arr->elts + (arr->elt_size * (arr->nelts - 1)); 141251875Speter} 142251875Speter 143251875SpeterAPR_DECLARE(void) apr_array_cat(apr_array_header_t *dst, 144251875Speter const apr_array_header_t *src) 145251875Speter{ 146251875Speter int elt_size = dst->elt_size; 147251875Speter 148251875Speter if (dst->nelts + src->nelts > dst->nalloc) { 149251875Speter int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2; 150251875Speter char *new_data; 151251875Speter 152251875Speter while (dst->nelts + src->nelts > new_size) { 153251875Speter new_size *= 2; 154251875Speter } 155251875Speter 156251875Speter new_data = apr_pcalloc(dst->pool, elt_size * new_size); 157251875Speter memcpy(new_data, dst->elts, dst->nalloc * elt_size); 158251875Speter 159251875Speter dst->elts = new_data; 160251875Speter dst->nalloc = new_size; 161251875Speter } 162251875Speter 163251875Speter memcpy(dst->elts + dst->nelts * elt_size, src->elts, 164251875Speter elt_size * src->nelts); 165251875Speter dst->nelts += src->nelts; 166251875Speter} 167251875Speter 168251875SpeterAPR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p, 169251875Speter const apr_array_header_t *arr) 170251875Speter{ 171251875Speter apr_array_header_t *res = 172251875Speter (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t)); 173251875Speter make_array_core(res, p, arr->nalloc, arr->elt_size, 0); 174251875Speter 175251875Speter memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts); 176251875Speter res->nelts = arr->nelts; 177251875Speter memset(res->elts + res->elt_size * res->nelts, 0, 178251875Speter res->elt_size * (res->nalloc - res->nelts)); 179251875Speter return res; 180251875Speter} 181251875Speter 182251875Speter/* This cute function copies the array header *only*, but arranges 183251875Speter * for the data section to be copied on the first push or arraycat. 184251875Speter * It's useful when the elements of the array being copied are 185251875Speter * read only, but new stuff *might* get added on the end; we have the 186251875Speter * overhead of the full copy only where it is really needed. 187251875Speter */ 188251875Speter 189251875Speterstatic APR_INLINE void copy_array_hdr_core(apr_array_header_t *res, 190251875Speter const apr_array_header_t *arr) 191251875Speter{ 192251875Speter res->elts = arr->elts; 193251875Speter res->elt_size = arr->elt_size; 194251875Speter res->nelts = arr->nelts; 195251875Speter res->nalloc = arr->nelts; /* Force overflow on push */ 196251875Speter} 197251875Speter 198251875SpeterAPR_DECLARE(apr_array_header_t *) 199251875Speter apr_array_copy_hdr(apr_pool_t *p, 200251875Speter const apr_array_header_t *arr) 201251875Speter{ 202251875Speter apr_array_header_t *res; 203251875Speter 204251875Speter res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t)); 205251875Speter res->pool = p; 206251875Speter copy_array_hdr_core(res, arr); 207251875Speter return res; 208251875Speter} 209251875Speter 210251875Speter/* The above is used here to avoid consing multiple new array bodies... */ 211251875Speter 212251875SpeterAPR_DECLARE(apr_array_header_t *) 213251875Speter apr_array_append(apr_pool_t *p, 214251875Speter const apr_array_header_t *first, 215251875Speter const apr_array_header_t *second) 216251875Speter{ 217251875Speter apr_array_header_t *res = apr_array_copy_hdr(p, first); 218251875Speter 219251875Speter apr_array_cat(res, second); 220251875Speter return res; 221251875Speter} 222251875Speter 223251875Speter/* apr_array_pstrcat generates a new string from the apr_pool_t containing 224251875Speter * the concatenated sequence of substrings referenced as elements within 225251875Speter * the array. The string will be empty if all substrings are empty or null, 226251875Speter * or if there are no elements in the array. 227251875Speter * If sep is non-NUL, it will be inserted between elements as a separator. 228251875Speter */ 229251875SpeterAPR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p, 230251875Speter const apr_array_header_t *arr, 231251875Speter const char sep) 232251875Speter{ 233251875Speter char *cp, *res, **strpp; 234251875Speter apr_size_t len; 235251875Speter int i; 236251875Speter 237251875Speter if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */ 238251875Speter return (char *) apr_pcalloc(p, 1); 239251875Speter } 240251875Speter 241251875Speter /* Pass one --- find length of required string */ 242251875Speter 243251875Speter len = 0; 244251875Speter for (i = 0, strpp = (char **) arr->elts; ; ++strpp) { 245251875Speter if (strpp && *strpp != NULL) { 246251875Speter len += strlen(*strpp); 247251875Speter } 248251875Speter if (++i >= arr->nelts) { 249251875Speter break; 250251875Speter } 251251875Speter if (sep) { 252251875Speter ++len; 253251875Speter } 254251875Speter } 255251875Speter 256251875Speter /* Allocate the required string */ 257251875Speter 258251875Speter res = (char *) apr_palloc(p, len + 1); 259251875Speter cp = res; 260251875Speter 261251875Speter /* Pass two --- copy the argument strings into the result space */ 262251875Speter 263251875Speter for (i = 0, strpp = (char **) arr->elts; ; ++strpp) { 264251875Speter if (strpp && *strpp != NULL) { 265251875Speter len = strlen(*strpp); 266251875Speter memcpy(cp, *strpp, len); 267251875Speter cp += len; 268251875Speter } 269251875Speter if (++i >= arr->nelts) { 270251875Speter break; 271251875Speter } 272251875Speter if (sep) { 273251875Speter *cp++ = sep; 274251875Speter } 275251875Speter } 276251875Speter 277251875Speter *cp = '\0'; 278251875Speter 279251875Speter /* Return the result string */ 280251875Speter 281251875Speter return res; 282251875Speter} 283251875Speter 284251875Speter 285251875Speter/***************************************************************** 286251875Speter * 287251875Speter * The "table" functions. 288251875Speter */ 289251875Speter 290251875Speter#if APR_CHARSET_EBCDIC 291251875Speter#define CASE_MASK 0xbfbfbfbf 292251875Speter#else 293251875Speter#define CASE_MASK 0xdfdfdfdf 294251875Speter#endif 295251875Speter 296251875Speter#define TABLE_HASH_SIZE 32 297251875Speter#define TABLE_INDEX_MASK 0x1f 298251875Speter#define TABLE_HASH(key) (TABLE_INDEX_MASK & *(unsigned char *)(key)) 299251875Speter#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i))) 300251875Speter#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i))) 301251875Speter 302251875Speter/* Compute the "checksum" for a key, consisting of the first 303251875Speter * 4 bytes, normalized for case-insensitivity and packed into 304251875Speter * an int...this checksum allows us to do a single integer 305251875Speter * comparison as a fast check to determine whether we can 306251875Speter * skip a strcasecmp 307251875Speter */ 308251875Speter#define COMPUTE_KEY_CHECKSUM(key, checksum) \ 309251875Speter{ \ 310251875Speter const char *k = (key); \ 311251875Speter apr_uint32_t c = (apr_uint32_t)*k; \ 312251875Speter (checksum) = c; \ 313251875Speter (checksum) <<= 8; \ 314251875Speter if (c) { \ 315251875Speter c = (apr_uint32_t)*++k; \ 316251875Speter checksum |= c; \ 317251875Speter } \ 318251875Speter (checksum) <<= 8; \ 319251875Speter if (c) { \ 320251875Speter c = (apr_uint32_t)*++k; \ 321251875Speter checksum |= c; \ 322251875Speter } \ 323251875Speter (checksum) <<= 8; \ 324251875Speter if (c) { \ 325251875Speter c = (apr_uint32_t)*++k; \ 326251875Speter checksum |= c; \ 327251875Speter } \ 328251875Speter checksum &= CASE_MASK; \ 329251875Speter} 330251875Speter 331251875Speter/** The opaque string-content table type */ 332251875Speterstruct apr_table_t { 333251875Speter /* This has to be first to promote backwards compatibility with 334251875Speter * older modules which cast a apr_table_t * to an apr_array_header_t *... 335251875Speter * they should use the apr_table_elts() function for most of the 336251875Speter * cases they do this for. 337251875Speter */ 338251875Speter /** The underlying array for the table */ 339251875Speter apr_array_header_t a; 340251875Speter#ifdef MAKE_TABLE_PROFILE 341251875Speter /** Who created the array. */ 342251875Speter void *creator; 343251875Speter#endif 344251875Speter /* An index to speed up table lookups. The way this works is: 345251875Speter * - Hash the key into the index: 346251875Speter * - index_first[TABLE_HASH(key)] is the offset within 347251875Speter * the table of the first entry with that key 348251875Speter * - index_last[TABLE_HASH(key)] is the offset within 349251875Speter * the table of the last entry with that key 350251875Speter * - If (and only if) there is no entry in the table whose 351251875Speter * key hashes to index element i, then the i'th bit 352251875Speter * of index_initialized will be zero. (Check this before 353251875Speter * trying to use index_first[i] or index_last[i]!) 354251875Speter */ 355251875Speter apr_uint32_t index_initialized; 356251875Speter int index_first[TABLE_HASH_SIZE]; 357251875Speter int index_last[TABLE_HASH_SIZE]; 358251875Speter}; 359251875Speter 360251875Speter/* 361251875Speter * NOTICE: if you tweak this you should look at is_empty_table() 362251875Speter * and table_elts() in alloc.h 363251875Speter */ 364251875Speter#ifdef MAKE_TABLE_PROFILE 365251875Speterstatic apr_table_entry_t *do_table_push(const char *func, apr_table_t *t) 366251875Speter{ 367251875Speter if (t->a.nelts == t->a.nalloc) { 368251875Speter fprintf(stderr, "%s: table created by %p hit limit of %u\n", 369251875Speter func ? func : "table_push", t->creator, t->a.nalloc); 370251875Speter } 371251875Speter return (apr_table_entry_t *) apr_array_push_noclear(&t->a); 372251875Speter} 373251875Speter#if defined(__GNUC__) && __GNUC__ >= 2 374251875Speter#define table_push(t) do_table_push(__FUNCTION__, t) 375251875Speter#else 376251875Speter#define table_push(t) do_table_push(NULL, t) 377251875Speter#endif 378251875Speter#else /* MAKE_TABLE_PROFILE */ 379251875Speter#define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a)) 380251875Speter#endif /* MAKE_TABLE_PROFILE */ 381251875Speter 382251875SpeterAPR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t) 383251875Speter{ 384251875Speter return (const apr_array_header_t *)t; 385251875Speter} 386251875Speter 387251875SpeterAPR_DECLARE(int) apr_is_empty_table(const apr_table_t *t) 388251875Speter{ 389251875Speter return ((t == NULL) || (t->a.nelts == 0)); 390251875Speter} 391251875Speter 392251875SpeterAPR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts) 393251875Speter{ 394251875Speter apr_table_t *t = apr_palloc(p, sizeof(apr_table_t)); 395251875Speter 396251875Speter make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0); 397251875Speter#ifdef MAKE_TABLE_PROFILE 398251875Speter t->creator = __builtin_return_address(0); 399251875Speter#endif 400251875Speter t->index_initialized = 0; 401251875Speter return t; 402251875Speter} 403251875Speter 404251875SpeterAPR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t) 405251875Speter{ 406251875Speter apr_table_t *new = apr_palloc(p, sizeof(apr_table_t)); 407251875Speter 408251875Speter#if APR_POOL_DEBUG 409251875Speter /* we don't copy keys and values, so it's necessary that t->a.pool 410251875Speter * have a life span at least as long as p 411251875Speter */ 412251875Speter if (!apr_pool_is_ancestor(t->a.pool, p)) { 413251875Speter fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n"); 414251875Speter abort(); 415251875Speter } 416251875Speter#endif 417251875Speter make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0); 418251875Speter memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t)); 419251875Speter new->a.nelts = t->a.nelts; 420251875Speter memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE); 421251875Speter memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE); 422251875Speter new->index_initialized = t->index_initialized; 423251875Speter return new; 424251875Speter} 425251875Speter 426251875SpeterAPR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t) 427251875Speter{ 428251875Speter const apr_array_header_t *array = apr_table_elts(t); 429251875Speter apr_table_entry_t *elts = (apr_table_entry_t *) array->elts; 430251875Speter apr_table_t *new = apr_table_make(p, array->nelts); 431251875Speter int i; 432251875Speter 433251875Speter for (i = 0; i < array->nelts; i++) { 434251875Speter apr_table_add(new, elts[i].key, elts[i].val); 435251875Speter } 436251875Speter 437251875Speter return new; 438251875Speter} 439251875Speter 440251875Speterstatic void table_reindex(apr_table_t *t) 441251875Speter{ 442251875Speter int i; 443251875Speter int hash; 444251875Speter apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts; 445251875Speter 446251875Speter t->index_initialized = 0; 447251875Speter for (i = 0; i < t->a.nelts; i++, next_elt++) { 448251875Speter hash = TABLE_HASH(next_elt->key); 449251875Speter t->index_last[hash] = i; 450251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 451251875Speter t->index_first[hash] = i; 452251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 453251875Speter } 454251875Speter } 455251875Speter} 456251875Speter 457251875SpeterAPR_DECLARE(void) apr_table_clear(apr_table_t *t) 458251875Speter{ 459251875Speter t->a.nelts = 0; 460251875Speter t->index_initialized = 0; 461251875Speter} 462251875Speter 463251875SpeterAPR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key) 464251875Speter{ 465251875Speter apr_table_entry_t *next_elt; 466251875Speter apr_table_entry_t *end_elt; 467251875Speter apr_uint32_t checksum; 468251875Speter int hash; 469251875Speter 470251875Speter if (key == NULL) { 471251875Speter return NULL; 472251875Speter } 473251875Speter 474251875Speter hash = TABLE_HASH(key); 475251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 476251875Speter return NULL; 477251875Speter } 478251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 479251875Speter next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 480251875Speter end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 481251875Speter 482251875Speter for (; next_elt <= end_elt; next_elt++) { 483251875Speter if ((checksum == next_elt->key_checksum) && 484251875Speter !strcasecmp(next_elt->key, key)) { 485251875Speter return next_elt->val; 486251875Speter } 487251875Speter } 488251875Speter 489251875Speter return NULL; 490251875Speter} 491251875Speter 492251875SpeterAPR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key, 493251875Speter const char *val) 494251875Speter{ 495251875Speter apr_table_entry_t *next_elt; 496251875Speter apr_table_entry_t *end_elt; 497251875Speter apr_table_entry_t *table_end; 498251875Speter apr_uint32_t checksum; 499251875Speter int hash; 500251875Speter 501251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 502251875Speter hash = TABLE_HASH(key); 503251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 504251875Speter t->index_first[hash] = t->a.nelts; 505251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 506251875Speter goto add_new_elt; 507251875Speter } 508251875Speter next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 509251875Speter end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 510251875Speter table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts; 511251875Speter 512251875Speter for (; next_elt <= end_elt; next_elt++) { 513251875Speter if ((checksum == next_elt->key_checksum) && 514251875Speter !strcasecmp(next_elt->key, key)) { 515251875Speter 516251875Speter /* Found an existing entry with the same key, so overwrite it */ 517251875Speter 518251875Speter int must_reindex = 0; 519251875Speter apr_table_entry_t *dst_elt = NULL; 520251875Speter 521251875Speter next_elt->val = apr_pstrdup(t->a.pool, val); 522251875Speter 523251875Speter /* Remove any other instances of this key */ 524251875Speter for (next_elt++; next_elt <= end_elt; next_elt++) { 525251875Speter if ((checksum == next_elt->key_checksum) && 526251875Speter !strcasecmp(next_elt->key, key)) { 527251875Speter t->a.nelts--; 528251875Speter if (!dst_elt) { 529251875Speter dst_elt = next_elt; 530251875Speter } 531251875Speter } 532251875Speter else if (dst_elt) { 533251875Speter *dst_elt++ = *next_elt; 534251875Speter must_reindex = 1; 535251875Speter } 536251875Speter } 537251875Speter 538251875Speter /* If we've removed anything, shift over the remainder 539251875Speter * of the table (note that the previous loop didn't 540251875Speter * run to the end of the table, just to the last match 541251875Speter * for the index) 542251875Speter */ 543251875Speter if (dst_elt) { 544251875Speter for (; next_elt < table_end; next_elt++) { 545251875Speter *dst_elt++ = *next_elt; 546251875Speter } 547251875Speter must_reindex = 1; 548251875Speter } 549251875Speter if (must_reindex) { 550251875Speter table_reindex(t); 551251875Speter } 552251875Speter return; 553251875Speter } 554251875Speter } 555251875Speter 556251875Speteradd_new_elt: 557251875Speter t->index_last[hash] = t->a.nelts; 558251875Speter next_elt = (apr_table_entry_t *) table_push(t); 559251875Speter next_elt->key = apr_pstrdup(t->a.pool, key); 560251875Speter next_elt->val = apr_pstrdup(t->a.pool, val); 561251875Speter next_elt->key_checksum = checksum; 562251875Speter} 563251875Speter 564251875SpeterAPR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key, 565251875Speter const char *val) 566251875Speter{ 567251875Speter apr_table_entry_t *next_elt; 568251875Speter apr_table_entry_t *end_elt; 569251875Speter apr_table_entry_t *table_end; 570251875Speter apr_uint32_t checksum; 571251875Speter int hash; 572251875Speter 573251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 574251875Speter hash = TABLE_HASH(key); 575251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 576251875Speter t->index_first[hash] = t->a.nelts; 577251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 578251875Speter goto add_new_elt; 579251875Speter } 580251875Speter next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 581251875Speter end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 582251875Speter table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts; 583251875Speter 584251875Speter for (; next_elt <= end_elt; next_elt++) { 585251875Speter if ((checksum == next_elt->key_checksum) && 586251875Speter !strcasecmp(next_elt->key, key)) { 587251875Speter 588251875Speter /* Found an existing entry with the same key, so overwrite it */ 589251875Speter 590251875Speter int must_reindex = 0; 591251875Speter apr_table_entry_t *dst_elt = NULL; 592251875Speter 593251875Speter next_elt->val = (char *)val; 594251875Speter 595251875Speter /* Remove any other instances of this key */ 596251875Speter for (next_elt++; next_elt <= end_elt; next_elt++) { 597251875Speter if ((checksum == next_elt->key_checksum) && 598251875Speter !strcasecmp(next_elt->key, key)) { 599251875Speter t->a.nelts--; 600251875Speter if (!dst_elt) { 601251875Speter dst_elt = next_elt; 602251875Speter } 603251875Speter } 604251875Speter else if (dst_elt) { 605251875Speter *dst_elt++ = *next_elt; 606251875Speter must_reindex = 1; 607251875Speter } 608251875Speter } 609251875Speter 610251875Speter /* If we've removed anything, shift over the remainder 611251875Speter * of the table (note that the previous loop didn't 612251875Speter * run to the end of the table, just to the last match 613251875Speter * for the index) 614251875Speter */ 615251875Speter if (dst_elt) { 616251875Speter for (; next_elt < table_end; next_elt++) { 617251875Speter *dst_elt++ = *next_elt; 618251875Speter } 619251875Speter must_reindex = 1; 620251875Speter } 621251875Speter if (must_reindex) { 622251875Speter table_reindex(t); 623251875Speter } 624251875Speter return; 625251875Speter } 626251875Speter } 627251875Speter 628251875Speteradd_new_elt: 629251875Speter t->index_last[hash] = t->a.nelts; 630251875Speter next_elt = (apr_table_entry_t *) table_push(t); 631251875Speter next_elt->key = (char *)key; 632251875Speter next_elt->val = (char *)val; 633251875Speter next_elt->key_checksum = checksum; 634251875Speter} 635251875Speter 636251875SpeterAPR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key) 637251875Speter{ 638251875Speter apr_table_entry_t *next_elt; 639251875Speter apr_table_entry_t *end_elt; 640251875Speter apr_table_entry_t *dst_elt; 641251875Speter apr_uint32_t checksum; 642251875Speter int hash; 643251875Speter int must_reindex; 644251875Speter 645251875Speter hash = TABLE_HASH(key); 646251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 647251875Speter return; 648251875Speter } 649251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 650251875Speter next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash]; 651251875Speter end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 652251875Speter must_reindex = 0; 653251875Speter for (; next_elt <= end_elt; next_elt++) { 654251875Speter if ((checksum == next_elt->key_checksum) && 655251875Speter !strcasecmp(next_elt->key, key)) { 656251875Speter 657251875Speter /* Found a match: remove this entry, plus any additional 658251875Speter * matches for the same key that might follow 659251875Speter */ 660251875Speter apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) + 661251875Speter t->a.nelts; 662251875Speter t->a.nelts--; 663251875Speter dst_elt = next_elt; 664251875Speter for (next_elt++; next_elt <= end_elt; next_elt++) { 665251875Speter if ((checksum == next_elt->key_checksum) && 666251875Speter !strcasecmp(next_elt->key, key)) { 667251875Speter t->a.nelts--; 668251875Speter } 669251875Speter else { 670251875Speter *dst_elt++ = *next_elt; 671251875Speter } 672251875Speter } 673251875Speter 674251875Speter /* Shift over the remainder of the table (note that 675251875Speter * the previous loop didn't run to the end of the table, 676251875Speter * just to the last match for the index) 677251875Speter */ 678251875Speter for (; next_elt < table_end; next_elt++) { 679251875Speter *dst_elt++ = *next_elt; 680251875Speter } 681251875Speter must_reindex = 1; 682251875Speter break; 683251875Speter } 684251875Speter } 685251875Speter if (must_reindex) { 686251875Speter table_reindex(t); 687251875Speter } 688251875Speter} 689251875Speter 690251875SpeterAPR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key, 691251875Speter const char *val) 692251875Speter{ 693251875Speter apr_table_entry_t *next_elt; 694251875Speter apr_table_entry_t *end_elt; 695251875Speter apr_uint32_t checksum; 696251875Speter int hash; 697251875Speter 698251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 699251875Speter hash = TABLE_HASH(key); 700251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 701251875Speter t->index_first[hash] = t->a.nelts; 702251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 703251875Speter goto add_new_elt; 704251875Speter } 705251875Speter next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash]; 706251875Speter end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 707251875Speter 708251875Speter for (; next_elt <= end_elt; next_elt++) { 709251875Speter if ((checksum == next_elt->key_checksum) && 710251875Speter !strcasecmp(next_elt->key, key)) { 711251875Speter 712251875Speter /* Found an existing entry with the same key, so merge with it */ 713251875Speter next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ", 714251875Speter val, NULL); 715251875Speter return; 716251875Speter } 717251875Speter } 718251875Speter 719251875Speteradd_new_elt: 720251875Speter t->index_last[hash] = t->a.nelts; 721251875Speter next_elt = (apr_table_entry_t *) table_push(t); 722251875Speter next_elt->key = apr_pstrdup(t->a.pool, key); 723251875Speter next_elt->val = apr_pstrdup(t->a.pool, val); 724251875Speter next_elt->key_checksum = checksum; 725251875Speter} 726251875Speter 727251875SpeterAPR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key, 728251875Speter const char *val) 729251875Speter{ 730251875Speter apr_table_entry_t *next_elt; 731251875Speter apr_table_entry_t *end_elt; 732251875Speter apr_uint32_t checksum; 733251875Speter int hash; 734251875Speter 735251875Speter#if APR_POOL_DEBUG 736251875Speter { 737253734Speter apr_pool_t *pool; 738253734Speter pool = apr_pool_find(key); 739253734Speter if ((pool != key) && (!apr_pool_is_ancestor(pool, t->a.pool))) { 740251875Speter fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n"); 741251875Speter abort(); 742251875Speter } 743253734Speter pool = apr_pool_find(val); 744253734Speter if ((pool != val) && (!apr_pool_is_ancestor(pool, t->a.pool))) { 745251875Speter fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n"); 746251875Speter abort(); 747251875Speter } 748251875Speter } 749251875Speter#endif 750251875Speter 751251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 752251875Speter hash = TABLE_HASH(key); 753251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 754251875Speter t->index_first[hash] = t->a.nelts; 755251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 756251875Speter goto add_new_elt; 757251875Speter } 758251875Speter next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];; 759251875Speter end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash]; 760251875Speter 761251875Speter for (; next_elt <= end_elt; next_elt++) { 762251875Speter if ((checksum == next_elt->key_checksum) && 763251875Speter !strcasecmp(next_elt->key, key)) { 764251875Speter 765251875Speter /* Found an existing entry with the same key, so merge with it */ 766251875Speter next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ", 767251875Speter val, NULL); 768251875Speter return; 769251875Speter } 770251875Speter } 771251875Speter 772251875Speteradd_new_elt: 773251875Speter t->index_last[hash] = t->a.nelts; 774251875Speter next_elt = (apr_table_entry_t *) table_push(t); 775251875Speter next_elt->key = (char *)key; 776251875Speter next_elt->val = (char *)val; 777251875Speter next_elt->key_checksum = checksum; 778251875Speter} 779251875Speter 780251875SpeterAPR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key, 781251875Speter const char *val) 782251875Speter{ 783251875Speter apr_table_entry_t *elts; 784251875Speter apr_uint32_t checksum; 785251875Speter int hash; 786251875Speter 787251875Speter hash = TABLE_HASH(key); 788251875Speter t->index_last[hash] = t->a.nelts; 789251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 790251875Speter t->index_first[hash] = t->a.nelts; 791251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 792251875Speter } 793251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 794251875Speter elts = (apr_table_entry_t *) table_push(t); 795251875Speter elts->key = apr_pstrdup(t->a.pool, key); 796251875Speter elts->val = apr_pstrdup(t->a.pool, val); 797251875Speter elts->key_checksum = checksum; 798251875Speter} 799251875Speter 800251875SpeterAPR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key, 801251875Speter const char *val) 802251875Speter{ 803251875Speter apr_table_entry_t *elts; 804251875Speter apr_uint32_t checksum; 805251875Speter int hash; 806251875Speter 807251875Speter#if APR_POOL_DEBUG 808251875Speter { 809251875Speter if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) { 810251875Speter fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n"); 811251875Speter abort(); 812251875Speter } 813251875Speter if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) { 814251875Speter fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n"); 815251875Speter abort(); 816251875Speter } 817251875Speter } 818251875Speter#endif 819251875Speter 820251875Speter hash = TABLE_HASH(key); 821251875Speter t->index_last[hash] = t->a.nelts; 822251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) { 823251875Speter t->index_first[hash] = t->a.nelts; 824251875Speter TABLE_SET_INDEX_INITIALIZED(t, hash); 825251875Speter } 826251875Speter COMPUTE_KEY_CHECKSUM(key, checksum); 827251875Speter elts = (apr_table_entry_t *) table_push(t); 828251875Speter elts->key = (char *)key; 829251875Speter elts->val = (char *)val; 830251875Speter elts->key_checksum = checksum; 831251875Speter} 832251875Speter 833251875SpeterAPR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p, 834251875Speter const apr_table_t *overlay, 835251875Speter const apr_table_t *base) 836251875Speter{ 837251875Speter apr_table_t *res; 838251875Speter 839251875Speter#if APR_POOL_DEBUG 840251875Speter /* we don't copy keys and values, so it's necessary that 841251875Speter * overlay->a.pool and base->a.pool have a life span at least 842251875Speter * as long as p 843251875Speter */ 844251875Speter if (!apr_pool_is_ancestor(overlay->a.pool, p)) { 845251875Speter fprintf(stderr, 846251875Speter "apr_table_overlay: overlay's pool is not an ancestor of p\n"); 847251875Speter abort(); 848251875Speter } 849251875Speter if (!apr_pool_is_ancestor(base->a.pool, p)) { 850251875Speter fprintf(stderr, 851251875Speter "apr_table_overlay: base's pool is not an ancestor of p\n"); 852251875Speter abort(); 853251875Speter } 854251875Speter#endif 855251875Speter 856251875Speter res = apr_palloc(p, sizeof(apr_table_t)); 857251875Speter /* behave like append_arrays */ 858251875Speter res->a.pool = p; 859251875Speter copy_array_hdr_core(&res->a, &overlay->a); 860251875Speter apr_array_cat(&res->a, &base->a); 861251875Speter table_reindex(res); 862251875Speter return res; 863251875Speter} 864251875Speter 865251875Speter/* And now for something completely abstract ... 866251875Speter 867251875Speter * For each key value given as a vararg: 868251875Speter * run the function pointed to as 869251875Speter * int comp(void *r, char *key, char *value); 870251875Speter * on each valid key-value pair in the apr_table_t t that matches the vararg key, 871251875Speter * or once for every valid key-value pair if the vararg list is empty, 872251875Speter * until the function returns false (0) or we finish the table. 873251875Speter * 874251875Speter * Note that we restart the traversal for each vararg, which means that 875251875Speter * duplicate varargs will result in multiple executions of the function 876251875Speter * for each matching key. Note also that if the vararg list is empty, 877251875Speter * only one traversal will be made and will cut short if comp returns 0. 878251875Speter * 879251875Speter * Note that the table_get and table_merge functions assume that each key in 880251875Speter * the apr_table_t is unique (i.e., no multiple entries with the same key). This 881251875Speter * function does not make that assumption, since it (unfortunately) isn't 882251875Speter * true for some of Apache's tables. 883251875Speter * 884251875Speter * Note that rec is simply passed-on to the comp function, so that the 885251875Speter * caller can pass additional info for the task. 886251875Speter * 887251875Speter * ADDENDUM for apr_table_vdo(): 888251875Speter * 889251875Speter * The caching api will allow a user to walk the header values: 890251875Speter * 891251875Speter * apr_status_t apr_cache_el_header_walk(apr_cache_el *el, 892251875Speter * int (*comp)(void *, const char *, const char *), void *rec, ...); 893251875Speter * 894251875Speter * So it can be ..., however from there I use a callback that use a va_list: 895251875Speter * 896251875Speter * apr_status_t (*cache_el_header_walk)(apr_cache_el *el, 897251875Speter * int (*comp)(void *, const char *, const char *), void *rec, va_list); 898251875Speter * 899251875Speter * To pass those ...'s on down to the actual module that will handle walking 900251875Speter * their headers, in the file case this is actually just an apr_table - and 901251875Speter * rather than reimplementing apr_table_do (which IMHO would be bad) I just 902251875Speter * called it with the va_list. For mod_shmem_cache I don't need it since I 903251875Speter * can't use apr_table's, but mod_file_cache should (though a good hash would 904251875Speter * be better, but that's a different issue :). 905251875Speter * 906251875Speter * So to make mod_file_cache easier to maintain, it's a good thing 907251875Speter */ 908251875SpeterAPR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp, 909251875Speter void *rec, const apr_table_t *t, ...) 910251875Speter{ 911251875Speter int rv; 912251875Speter 913251875Speter va_list vp; 914251875Speter va_start(vp, t); 915251875Speter rv = apr_table_vdo(comp, rec, t, vp); 916251875Speter va_end(vp); 917251875Speter 918251875Speter return rv; 919251875Speter} 920251875Speter 921251875Speter/* XXX: do the semantics of this routine make any sense? Right now, 922251875Speter * if the caller passed in a non-empty va_list of keys to search for, 923251875Speter * the "early termination" facility only terminates on *that* key; other 924251875Speter * keys will continue to process. Note that this only has any effect 925251875Speter * at all if there are multiple entries in the table with the same key, 926251875Speter * otherwise the called function can never effectively early-terminate 927251875Speter * this function, as the zero return value is effectively ignored. 928251875Speter * 929251875Speter * Note also that this behavior is at odds with the behavior seen if an 930251875Speter * empty va_list is passed in -- in that case, a zero return value terminates 931251875Speter * the entire apr_table_vdo (which is what I think should happen in 932251875Speter * both cases). 933251875Speter * 934251875Speter * If nobody objects soon, I'm going to change the order of the nested 935251875Speter * loops in this function so that any zero return value from the (*comp) 936251875Speter * function will cause a full termination of apr_table_vdo. I'm hesitant 937251875Speter * at the moment because these (funky) semantics have been around for a 938251875Speter * very long time, and although Apache doesn't seem to use them at all, 939251875Speter * some third-party vendor might. I can only think of one possible reason 940251875Speter * the existing semantics would make any sense, and it's very Apache-centric, 941251875Speter * which is this: if (*comp) is looking for matches of a particular 942251875Speter * substring in request headers (let's say it's looking for a particular 943251875Speter * cookie name in the Set-Cookie headers), then maybe it wants to be 944251875Speter * able to stop searching early as soon as it finds that one and move 945251875Speter * on to the next key. That's only an optimization of course, but changing 946251875Speter * the behavior of this function would mean that any code that tried 947251875Speter * to do that would stop working right. 948251875Speter * 949251875Speter * Sigh. --JCW, 06/28/02 950251875Speter */ 951251875SpeterAPR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp, 952251875Speter void *rec, const apr_table_t *t, va_list vp) 953251875Speter{ 954251875Speter char *argp; 955251875Speter apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; 956251875Speter int vdorv = 1; 957251875Speter 958251875Speter argp = va_arg(vp, char *); 959251875Speter do { 960251875Speter int rv = 1, i; 961251875Speter if (argp) { 962251875Speter /* Scan for entries that match the next key */ 963251875Speter int hash = TABLE_HASH(argp); 964251875Speter if (TABLE_INDEX_IS_INITIALIZED(t, hash)) { 965251875Speter apr_uint32_t checksum; 966251875Speter COMPUTE_KEY_CHECKSUM(argp, checksum); 967251875Speter for (i = t->index_first[hash]; 968251875Speter rv && (i <= t->index_last[hash]); ++i) { 969251875Speter if (elts[i].key && (checksum == elts[i].key_checksum) && 970251875Speter !strcasecmp(elts[i].key, argp)) { 971251875Speter rv = (*comp) (rec, elts[i].key, elts[i].val); 972251875Speter } 973251875Speter } 974251875Speter } 975251875Speter } 976251875Speter else { 977251875Speter /* Scan the entire table */ 978251875Speter for (i = 0; rv && (i < t->a.nelts); ++i) { 979251875Speter if (elts[i].key) { 980251875Speter rv = (*comp) (rec, elts[i].key, elts[i].val); 981251875Speter } 982251875Speter } 983251875Speter } 984251875Speter if (rv == 0) { 985251875Speter vdorv = 0; 986251875Speter } 987251875Speter } while (argp && ((argp = va_arg(vp, char *)) != NULL)); 988251875Speter 989251875Speter return vdorv; 990251875Speter} 991251875Speter 992251875Speterstatic apr_table_entry_t **table_mergesort(apr_pool_t *pool, 993251875Speter apr_table_entry_t **values, 994251875Speter apr_size_t n) 995251875Speter{ 996251875Speter /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms 997251875Speter * in C," chapter 8 998251875Speter */ 999251875Speter apr_table_entry_t **values_tmp = 1000251875Speter (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*)); 1001251875Speter apr_size_t i; 1002251875Speter apr_size_t blocksize; 1003251875Speter 1004251875Speter /* First pass: sort pairs of elements (blocksize=1) */ 1005251875Speter for (i = 0; i + 1 < n; i += 2) { 1006251875Speter if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) { 1007251875Speter apr_table_entry_t *swap = values[i]; 1008251875Speter values[i] = values[i + 1]; 1009251875Speter values[i + 1] = swap; 1010251875Speter } 1011251875Speter } 1012251875Speter 1013251875Speter /* Merge successively larger blocks */ 1014251875Speter blocksize = 2; 1015251875Speter while (blocksize < n) { 1016251875Speter apr_table_entry_t **dst = values_tmp; 1017251875Speter apr_size_t next_start; 1018251875Speter apr_table_entry_t **swap; 1019251875Speter 1020251875Speter /* Merge consecutive pairs blocks of the next blocksize. 1021251875Speter * Within a block, elements are in sorted order due to 1022251875Speter * the previous iteration. 1023251875Speter */ 1024251875Speter for (next_start = 0; next_start + blocksize < n; 1025251875Speter next_start += (blocksize + blocksize)) { 1026251875Speter 1027251875Speter apr_size_t block1_start = next_start; 1028251875Speter apr_size_t block2_start = block1_start + blocksize; 1029251875Speter apr_size_t block1_end = block2_start; 1030251875Speter apr_size_t block2_end = block2_start + blocksize; 1031251875Speter if (block2_end > n) { 1032251875Speter /* The last block may be smaller than blocksize */ 1033251875Speter block2_end = n; 1034251875Speter } 1035251875Speter for (;;) { 1036251875Speter 1037251875Speter /* Merge the next two blocks: 1038251875Speter * Pick the smaller of the next element from 1039251875Speter * block 1 and the next element from block 2. 1040251875Speter * Once either of the blocks is emptied, copy 1041251875Speter * over all the remaining elements from the 1042251875Speter * other block 1043251875Speter */ 1044251875Speter if (block1_start == block1_end) { 1045251875Speter for (; block2_start < block2_end; block2_start++) { 1046251875Speter *dst++ = values[block2_start]; 1047251875Speter } 1048251875Speter break; 1049251875Speter } 1050251875Speter else if (block2_start == block2_end) { 1051251875Speter for (; block1_start < block1_end; block1_start++) { 1052251875Speter *dst++ = values[block1_start]; 1053251875Speter } 1054251875Speter break; 1055251875Speter } 1056251875Speter if (strcasecmp(values[block1_start]->key, 1057251875Speter values[block2_start]->key) > 0) { 1058251875Speter *dst++ = values[block2_start++]; 1059251875Speter } 1060251875Speter else { 1061251875Speter *dst++ = values[block1_start++]; 1062251875Speter } 1063251875Speter } 1064251875Speter } 1065251875Speter 1066251875Speter /* If n is not a multiple of 2*blocksize, some elements 1067251875Speter * will be left over at the end of the array. 1068251875Speter */ 1069251875Speter for (i = dst - values_tmp; i < n; i++) { 1070251875Speter values_tmp[i] = values[i]; 1071251875Speter } 1072251875Speter 1073251875Speter /* The output array of this pass becomes the input 1074251875Speter * array of the next pass, and vice versa 1075251875Speter */ 1076251875Speter swap = values_tmp; 1077251875Speter values_tmp = values; 1078251875Speter values = swap; 1079251875Speter 1080251875Speter blocksize += blocksize; 1081251875Speter } 1082251875Speter 1083251875Speter return values; 1084251875Speter} 1085251875Speter 1086251875SpeterAPR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags) 1087251875Speter{ 1088251875Speter apr_table_entry_t **sort_array; 1089251875Speter apr_table_entry_t **sort_next; 1090251875Speter apr_table_entry_t **sort_end; 1091251875Speter apr_table_entry_t *table_next; 1092251875Speter apr_table_entry_t **last; 1093251875Speter int i; 1094251875Speter int dups_found; 1095251875Speter 1096251875Speter if (t->a.nelts <= 1) { 1097251875Speter return; 1098251875Speter } 1099251875Speter 1100251875Speter /* Copy pointers to all the table elements into an 1101251875Speter * array and sort to allow for easy detection of 1102251875Speter * duplicate keys 1103251875Speter */ 1104251875Speter sort_array = (apr_table_entry_t **) 1105251875Speter apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*)); 1106251875Speter sort_next = sort_array; 1107251875Speter table_next = (apr_table_entry_t *)t->a.elts; 1108251875Speter i = t->a.nelts; 1109251875Speter do { 1110251875Speter *sort_next++ = table_next++; 1111251875Speter } while (--i); 1112251875Speter 1113251875Speter /* Note: the merge is done with mergesort instead of quicksort 1114251875Speter * because mergesort is a stable sort and runs in n*log(n) 1115251875Speter * time regardless of its inputs (quicksort is quadratic in 1116251875Speter * the worst case) 1117251875Speter */ 1118251875Speter sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts); 1119251875Speter 1120251875Speter /* Process any duplicate keys */ 1121251875Speter dups_found = 0; 1122251875Speter sort_next = sort_array; 1123251875Speter sort_end = sort_array + t->a.nelts; 1124251875Speter last = sort_next++; 1125251875Speter while (sort_next < sort_end) { 1126251875Speter if (((*sort_next)->key_checksum == (*last)->key_checksum) && 1127251875Speter !strcasecmp((*sort_next)->key, (*last)->key)) { 1128251875Speter apr_table_entry_t **dup_last = sort_next + 1; 1129251875Speter dups_found = 1; 1130251875Speter while ((dup_last < sort_end) && 1131251875Speter ((*dup_last)->key_checksum == (*last)->key_checksum) && 1132251875Speter !strcasecmp((*dup_last)->key, (*last)->key)) { 1133251875Speter dup_last++; 1134251875Speter } 1135251875Speter dup_last--; /* Elements from last through dup_last, inclusive, 1136251875Speter * all have the same key 1137251875Speter */ 1138251875Speter if (flags == APR_OVERLAP_TABLES_MERGE) { 1139251875Speter apr_size_t len = 0; 1140251875Speter apr_table_entry_t **next = last; 1141251875Speter char *new_val; 1142251875Speter char *val_dst; 1143251875Speter do { 1144251875Speter len += strlen((*next)->val); 1145251875Speter len += 2; /* for ", " or trailing null */ 1146251875Speter } while (++next <= dup_last); 1147251875Speter new_val = (char *)apr_palloc(t->a.pool, len); 1148251875Speter val_dst = new_val; 1149251875Speter next = last; 1150251875Speter for (;;) { 1151251875Speter strcpy(val_dst, (*next)->val); 1152251875Speter val_dst += strlen((*next)->val); 1153251875Speter next++; 1154251875Speter if (next > dup_last) { 1155251875Speter *val_dst = 0; 1156251875Speter break; 1157251875Speter } 1158251875Speter else { 1159251875Speter *val_dst++ = ','; 1160251875Speter *val_dst++ = ' '; 1161251875Speter } 1162251875Speter } 1163251875Speter (*last)->val = new_val; 1164251875Speter } 1165251875Speter else { /* overwrite */ 1166251875Speter (*last)->val = (*dup_last)->val; 1167251875Speter } 1168251875Speter do { 1169251875Speter (*sort_next)->key = NULL; 1170251875Speter } while (++sort_next <= dup_last); 1171251875Speter } 1172251875Speter else { 1173251875Speter last = sort_next++; 1174251875Speter } 1175251875Speter } 1176251875Speter 1177251875Speter /* Shift elements to the left to fill holes left by removing duplicates */ 1178251875Speter if (dups_found) { 1179251875Speter apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts; 1180251875Speter apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts; 1181251875Speter apr_table_entry_t *last_elt = src + t->a.nelts; 1182251875Speter do { 1183251875Speter if (src->key) { 1184251875Speter *dst++ = *src; 1185251875Speter } 1186251875Speter } while (++src < last_elt); 1187251875Speter t->a.nelts -= (int)(last_elt - dst); 1188251875Speter } 1189251875Speter 1190251875Speter table_reindex(t); 1191251875Speter} 1192251875Speter 1193251875Speterstatic void apr_table_cat(apr_table_t *t, const apr_table_t *s) 1194251875Speter{ 1195251875Speter const int n = t->a.nelts; 1196251875Speter register int idx; 1197251875Speter 1198251875Speter apr_array_cat(&t->a,&s->a); 1199251875Speter 1200251875Speter if (n == 0) { 1201251875Speter memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE); 1202251875Speter memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE); 1203251875Speter t->index_initialized = s->index_initialized; 1204251875Speter return; 1205251875Speter } 1206251875Speter 1207251875Speter for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) { 1208251875Speter if (TABLE_INDEX_IS_INITIALIZED(s, idx)) { 1209251875Speter t->index_last[idx] = s->index_last[idx] + n; 1210251875Speter if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) { 1211251875Speter t->index_first[idx] = s->index_first[idx] + n; 1212251875Speter } 1213251875Speter } 1214251875Speter } 1215251875Speter 1216251875Speter t->index_initialized |= s->index_initialized; 1217251875Speter} 1218251875Speter 1219251875SpeterAPR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, 1220251875Speter unsigned flags) 1221251875Speter{ 1222251875Speter if (a->a.nelts + b->a.nelts == 0) { 1223251875Speter return; 1224251875Speter } 1225251875Speter 1226251875Speter#if APR_POOL_DEBUG 1227251875Speter /* Since the keys and values are not copied, it's required that 1228251875Speter * b->a.pool has a lifetime at least as long as a->a.pool. */ 1229251875Speter if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) { 1230251875Speter fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n"); 1231251875Speter abort(); 1232251875Speter } 1233251875Speter#endif 1234251875Speter 1235251875Speter apr_table_cat(a, b); 1236251875Speter 1237251875Speter apr_table_compress(a, flags); 1238251875Speter} 1239