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