/src/httpd/srclib/apr/tables/apr_hash.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 | | #include "apr_private.h" |
18 | | |
19 | | #include "apr_general.h" |
20 | | #include "apr_pools.h" |
21 | | #include "apr_time.h" |
22 | | |
23 | | #include "apr_hash.h" |
24 | | |
25 | | #if APR_HAVE_STDLIB_H |
26 | | #include <stdlib.h> |
27 | | #endif |
28 | | #if APR_HAVE_STRING_H |
29 | | #include <string.h> |
30 | | #endif |
31 | | |
32 | | #if APR_POOL_DEBUG && APR_HAVE_STDIO_H |
33 | | #include <stdio.h> |
34 | | #endif |
35 | | |
36 | | /* |
37 | | * The internal form of a hash table. |
38 | | * |
39 | | * The table is an array indexed by the hash of the key; collisions |
40 | | * are resolved by hanging a linked list of hash entries off each |
41 | | * element of the array. Although this is a really simple design it |
42 | | * isn't too bad given that pools have a low allocation overhead. |
43 | | */ |
44 | | |
45 | | typedef struct apr_hash_entry_t apr_hash_entry_t; |
46 | | |
47 | | struct apr_hash_entry_t { |
48 | | apr_hash_entry_t *next; |
49 | | unsigned int hash; |
50 | | const void *key; |
51 | | apr_ssize_t klen; |
52 | | const void *val; |
53 | | }; |
54 | | |
55 | | /* |
56 | | * Data structure for iterating through a hash table. |
57 | | * |
58 | | * We keep a pointer to the next hash entry here to allow the current |
59 | | * hash entry to be freed or otherwise mangled between calls to |
60 | | * apr_hash_next(). |
61 | | */ |
62 | | struct apr_hash_index_t { |
63 | | apr_hash_t *ht; |
64 | | apr_hash_entry_t *this, *next; |
65 | | unsigned int index; |
66 | | }; |
67 | | |
68 | | /* |
69 | | * The size of the array is always a power of two. We use the maximum |
70 | | * index rather than the size so that we can use bitwise-AND for |
71 | | * modular arithmetic. |
72 | | * The count of hash entries may be greater depending on the chosen |
73 | | * collision rate. |
74 | | */ |
75 | | struct apr_hash_t { |
76 | | apr_pool_t *pool; |
77 | | apr_hash_entry_t **array; |
78 | | apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */ |
79 | | unsigned int count, max, seed; |
80 | | apr_hashfunc_t hash_func; |
81 | | apr_hash_entry_t *free; /* List of recycled entries */ |
82 | | }; |
83 | | |
84 | 531 | #define INITIAL_MAX 15 /* tunable == 2^n - 1 */ |
85 | | |
86 | | |
87 | | /* |
88 | | * Hash creation functions. |
89 | | */ |
90 | | |
91 | | static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max) |
92 | 1.06k | { |
93 | 1.06k | return apr_pcalloc(ht->pool, sizeof(*ht->array) * (max + 1)); |
94 | 1.06k | } |
95 | | |
96 | | APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool) |
97 | 531 | { |
98 | 531 | apr_hash_t *ht; |
99 | 531 | apr_time_t now = apr_time_now(); |
100 | | |
101 | 531 | ht = apr_palloc(pool, sizeof(apr_hash_t)); |
102 | 531 | ht->pool = pool; |
103 | 531 | ht->free = NULL; |
104 | 531 | ht->count = 0; |
105 | 531 | ht->max = INITIAL_MAX; |
106 | 531 | ht->seed = (unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)pool ^ |
107 | 531 | (apr_uintptr_t)ht ^ (apr_uintptr_t)&now) - 1; |
108 | 531 | ht->array = alloc_array(ht, ht->max); |
109 | 531 | ht->hash_func = NULL; |
110 | | |
111 | 531 | return ht; |
112 | 531 | } |
113 | | |
114 | | APR_DECLARE(apr_hash_t *) apr_hash_make_custom(apr_pool_t *pool, |
115 | | apr_hashfunc_t hash_func) |
116 | 0 | { |
117 | 0 | apr_hash_t *ht = apr_hash_make(pool); |
118 | 0 | ht->hash_func = hash_func; |
119 | 0 | return ht; |
120 | 0 | } |
121 | | |
122 | | |
123 | | /* |
124 | | * Hash iteration functions. |
125 | | */ |
126 | | |
127 | | APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi) |
128 | 9.02k | { |
129 | 9.02k | hi->this = hi->next; |
130 | 17.5k | while (!hi->this) { |
131 | 9.02k | if (hi->index > hi->ht->max) |
132 | 531 | return NULL; |
133 | | |
134 | 8.49k | hi->this = hi->ht->array[hi->index++]; |
135 | 8.49k | } |
136 | 8.49k | hi->next = hi->this->next; |
137 | 8.49k | return hi; |
138 | 9.02k | } |
139 | | |
140 | | APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_pool_t *p, apr_hash_t *ht) |
141 | 531 | { |
142 | 531 | apr_hash_index_t *hi; |
143 | 531 | if (p) |
144 | 0 | hi = apr_palloc(p, sizeof(*hi)); |
145 | 531 | else |
146 | 531 | hi = &ht->iterator; |
147 | | |
148 | 531 | hi->ht = ht; |
149 | 531 | hi->index = 0; |
150 | 531 | hi->this = NULL; |
151 | 531 | hi->next = NULL; |
152 | 531 | return apr_hash_next(hi); |
153 | 531 | } |
154 | | |
155 | | APR_DECLARE(void) apr_hash_this(apr_hash_index_t *hi, |
156 | | const void **key, |
157 | | apr_ssize_t *klen, |
158 | | void **val) |
159 | 0 | { |
160 | 0 | if (key) *key = hi->this->key; |
161 | 0 | if (klen) *klen = hi->this->klen; |
162 | 0 | if (val) *val = (void *)hi->this->val; |
163 | 0 | } |
164 | | |
165 | | APR_DECLARE(const void *) apr_hash_this_key(apr_hash_index_t *hi) |
166 | 0 | { |
167 | 0 | const void *key; |
168 | |
|
169 | 0 | apr_hash_this(hi, &key, NULL, NULL); |
170 | 0 | return key; |
171 | 0 | } |
172 | | |
173 | | APR_DECLARE(apr_ssize_t) apr_hash_this_key_len(apr_hash_index_t *hi) |
174 | 0 | { |
175 | 0 | apr_ssize_t klen; |
176 | |
|
177 | 0 | apr_hash_this(hi, NULL, &klen, NULL); |
178 | 0 | return klen; |
179 | 0 | } |
180 | | |
181 | | APR_DECLARE(void *) apr_hash_this_val(apr_hash_index_t *hi) |
182 | 0 | { |
183 | 0 | void *val; |
184 | |
|
185 | 0 | apr_hash_this(hi, NULL, NULL, &val); |
186 | 0 | return val; |
187 | 0 | } |
188 | | |
189 | | /* |
190 | | * Expanding a hash table |
191 | | */ |
192 | | |
193 | | static void expand_array(apr_hash_t *ht) |
194 | 531 | { |
195 | 531 | apr_hash_index_t *hi; |
196 | 531 | apr_hash_entry_t **new_array; |
197 | 531 | unsigned int new_max; |
198 | | |
199 | 531 | new_max = ht->max * 2 + 1; |
200 | 531 | new_array = alloc_array(ht, new_max); |
201 | 9.02k | for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) { |
202 | 8.49k | unsigned int i = hi->this->hash & new_max; |
203 | 8.49k | hi->this->next = new_array[i]; |
204 | 8.49k | new_array[i] = hi->this; |
205 | 8.49k | } |
206 | 531 | ht->array = new_array; |
207 | 531 | ht->max = new_max; |
208 | 531 | } |
209 | | |
210 | | static unsigned int hashfunc_default(const char *char_key, apr_ssize_t *klen, |
211 | | unsigned int hash) |
212 | 14.7k | { |
213 | 14.7k | const unsigned char *key = (const unsigned char *)char_key; |
214 | 14.7k | const unsigned char *p; |
215 | 14.7k | apr_ssize_t i; |
216 | | |
217 | | /* |
218 | | * This is the popular `times 33' hash algorithm which is used by |
219 | | * perl and also appears in Berkeley DB. This is one of the best |
220 | | * known hash functions for strings because it is both computed |
221 | | * very fast and distributes very well. |
222 | | * |
223 | | * The originator may be Dan Bernstein but the code in Berkeley DB |
224 | | * cites Chris Torek as the source. The best citation I have found |
225 | | * is "Chris Torek, Hash function for text in C, Usenet message |
226 | | * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich |
227 | | * Salz's USENIX 1992 paper about INN which can be found at |
228 | | * <http://citeseer.nj.nec.com/salz92internetnews.html>. |
229 | | * |
230 | | * The magic of number 33, i.e. why it works better than many other |
231 | | * constants, prime or not, has never been adequately explained by |
232 | | * anyone. So I try an explanation: if one experimentally tests all |
233 | | * multipliers between 1 and 256 (as I did while writing a low-level |
234 | | * data structure library some time ago) one detects that even |
235 | | * numbers are not useable at all. The remaining 128 odd numbers |
236 | | * (except for the number 1) work more or less all equally well. |
237 | | * They all distribute in an acceptable way and this way fill a hash |
238 | | * table with an average percent of approx. 86%. |
239 | | * |
240 | | * If one compares the chi^2 values of the variants (see |
241 | | * Bob Jenkins ``Hashing Frequently Asked Questions'' at |
242 | | * http://burtleburtle.net/bob/hash/hashfaq.html for a description |
243 | | * of chi^2), the number 33 not even has the best value. But the |
244 | | * number 33 and a few other equally good numbers like 17, 31, 63, |
245 | | * 127 and 129 have nevertheless a great advantage to the remaining |
246 | | * numbers in the large set of possible multipliers: their multiply |
247 | | * operation can be replaced by a faster operation based on just one |
248 | | * shift plus either a single addition or subtraction operation. And |
249 | | * because a hash function has to both distribute good _and_ has to |
250 | | * be very fast to compute, those few numbers should be preferred. |
251 | | * |
252 | | * -- Ralf S. Engelschall <rse@engelschall.com> |
253 | | */ |
254 | | |
255 | 14.7k | if (*klen == APR_HASH_KEY_STRING) { |
256 | 111k | for (p = key; *p; p++) { |
257 | 97.1k | hash = hash * 33 + *p; |
258 | 97.1k | } |
259 | 14.3k | *klen = p - key; |
260 | 14.3k | } |
261 | 373 | else { |
262 | 2.28k | for (p = key, i = *klen; i; i--, p++) { |
263 | 1.91k | hash = hash * 33 + *p; |
264 | 1.91k | } |
265 | 373 | } |
266 | | |
267 | 14.7k | return hash; |
268 | 14.7k | } |
269 | | |
270 | | APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, |
271 | | apr_ssize_t *klen) |
272 | 0 | { |
273 | 0 | return hashfunc_default(char_key, klen, 0); |
274 | 0 | } |
275 | | |
276 | | /* |
277 | | * This is where we keep the details of the hash function and control |
278 | | * the maximum collision rate. |
279 | | * |
280 | | * If val is non-NULL it creates and initializes a new hash entry if |
281 | | * there isn't already one there; it returns an updatable pointer so |
282 | | * that hash entries can be removed. |
283 | | */ |
284 | | |
285 | | static apr_hash_entry_t **find_entry(apr_hash_t *ht, |
286 | | const void *key, |
287 | | apr_ssize_t klen, |
288 | | const void *val) |
289 | 14.7k | { |
290 | 14.7k | apr_hash_entry_t **hep, *he; |
291 | 14.7k | unsigned int hash; |
292 | | |
293 | 14.7k | if (ht->hash_func) |
294 | 0 | hash = ht->hash_func(key, &klen); |
295 | 14.7k | else |
296 | 14.7k | hash = hashfunc_default(key, &klen, ht->seed); |
297 | | |
298 | | /* scan linked list */ |
299 | 14.7k | for (hep = &ht->array[hash & ht->max], he = *hep; |
300 | 20.3k | he; hep = &he->next, he = *hep) { |
301 | 5.73k | if (he->hash == hash |
302 | 5.73k | && he->klen == klen |
303 | 5.73k | && memcmp(he->key, key, klen) == 0) |
304 | 64 | break; |
305 | 5.73k | } |
306 | 14.7k | if (he || !val) |
307 | 373 | return hep; |
308 | | |
309 | | /* add a new entry for non-NULL values */ |
310 | 14.3k | if ((he = ht->free) != NULL) |
311 | 0 | ht->free = he->next; |
312 | 14.3k | else |
313 | 14.3k | he = apr_palloc(ht->pool, sizeof(*he)); |
314 | 14.3k | he->next = NULL; |
315 | 14.3k | he->hash = hash; |
316 | 14.3k | he->key = key; |
317 | 14.3k | he->klen = klen; |
318 | 14.3k | he->val = val; |
319 | 14.3k | *hep = he; |
320 | 14.3k | ht->count++; |
321 | 14.3k | return hep; |
322 | 14.7k | } |
323 | | |
324 | | APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool, |
325 | | const apr_hash_t *orig) |
326 | 0 | { |
327 | 0 | apr_hash_t *ht; |
328 | 0 | apr_hash_entry_t *new_vals; |
329 | 0 | unsigned int i, j; |
330 | |
|
331 | 0 | ht = apr_palloc(pool, sizeof(apr_hash_t) + |
332 | 0 | sizeof(*ht->array) * (orig->max + 1) + |
333 | 0 | sizeof(apr_hash_entry_t) * orig->count); |
334 | 0 | ht->pool = pool; |
335 | 0 | ht->free = NULL; |
336 | 0 | ht->count = orig->count; |
337 | 0 | ht->max = orig->max; |
338 | 0 | ht->seed = orig->seed; |
339 | 0 | ht->hash_func = orig->hash_func; |
340 | 0 | ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t)); |
341 | |
|
342 | 0 | new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) + |
343 | 0 | sizeof(*ht->array) * (orig->max + 1)); |
344 | 0 | j = 0; |
345 | 0 | for (i = 0; i <= ht->max; i++) { |
346 | 0 | apr_hash_entry_t **new_entry = &(ht->array[i]); |
347 | 0 | apr_hash_entry_t *orig_entry = orig->array[i]; |
348 | 0 | while (orig_entry) { |
349 | 0 | *new_entry = &new_vals[j++]; |
350 | 0 | (*new_entry)->hash = orig_entry->hash; |
351 | 0 | (*new_entry)->key = orig_entry->key; |
352 | 0 | (*new_entry)->klen = orig_entry->klen; |
353 | 0 | (*new_entry)->val = orig_entry->val; |
354 | 0 | new_entry = &((*new_entry)->next); |
355 | 0 | orig_entry = orig_entry->next; |
356 | 0 | } |
357 | 0 | *new_entry = NULL; |
358 | 0 | } |
359 | 0 | return ht; |
360 | 0 | } |
361 | | |
362 | | APR_DECLARE(void *) apr_hash_get(apr_hash_t *ht, |
363 | | const void *key, |
364 | | apr_ssize_t klen) |
365 | 373 | { |
366 | 373 | apr_hash_entry_t *he; |
367 | 373 | he = *find_entry(ht, key, klen, NULL); |
368 | 373 | if (he) |
369 | 64 | return (void *)he->val; |
370 | 309 | else |
371 | 309 | return NULL; |
372 | 373 | } |
373 | | |
374 | | APR_DECLARE(void) apr_hash_set(apr_hash_t *ht, |
375 | | const void *key, |
376 | | apr_ssize_t klen, |
377 | | const void *val) |
378 | 14.3k | { |
379 | 14.3k | apr_hash_entry_t **hep; |
380 | 14.3k | hep = find_entry(ht, key, klen, val); |
381 | 14.3k | if (*hep) { |
382 | 14.3k | if (!val) { |
383 | | /* delete entry */ |
384 | 0 | apr_hash_entry_t *old = *hep; |
385 | 0 | *hep = (*hep)->next; |
386 | 0 | old->next = ht->free; |
387 | 0 | ht->free = old; |
388 | 0 | --ht->count; |
389 | 0 | } |
390 | 14.3k | else { |
391 | | /* replace entry */ |
392 | 14.3k | (*hep)->val = val; |
393 | | /* check that the collision rate isn't too high */ |
394 | 14.3k | if (ht->count > ht->max) { |
395 | 531 | expand_array(ht); |
396 | 531 | } |
397 | 14.3k | } |
398 | 14.3k | } |
399 | | /* else key not present and val==NULL */ |
400 | 14.3k | } |
401 | | |
402 | | APR_DECLARE(void *) apr_hash_get_or_set(apr_hash_t *ht, |
403 | | const void *key, |
404 | | apr_ssize_t klen, |
405 | | const void *val) |
406 | 0 | { |
407 | 0 | apr_hash_entry_t **hep; |
408 | 0 | hep = find_entry(ht, key, klen, val); |
409 | 0 | if (*hep) { |
410 | 0 | val = (*hep)->val; |
411 | | /* check that the collision rate isn't too high */ |
412 | 0 | if (ht->count > ht->max) { |
413 | 0 | expand_array(ht); |
414 | 0 | } |
415 | 0 | return (void *)val; |
416 | 0 | } |
417 | | /* else key not present and val==NULL */ |
418 | 0 | return NULL; |
419 | 0 | } |
420 | | |
421 | | APR_DECLARE(unsigned int) apr_hash_count(apr_hash_t *ht) |
422 | 0 | { |
423 | 0 | return ht->count; |
424 | 0 | } |
425 | | |
426 | | APR_DECLARE(void) apr_hash_clear(apr_hash_t *ht) |
427 | 0 | { |
428 | 0 | apr_hash_index_t *hi; |
429 | 0 | for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) |
430 | 0 | apr_hash_set(ht, hi->this->key, hi->this->klen, NULL); |
431 | 0 | } |
432 | | |
433 | | APR_DECLARE(apr_hash_t*) apr_hash_overlay(apr_pool_t *p, |
434 | | const apr_hash_t *overlay, |
435 | | const apr_hash_t *base) |
436 | 0 | { |
437 | 0 | return apr_hash_merge(p, overlay, base, NULL, NULL); |
438 | 0 | } |
439 | | |
440 | | APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, |
441 | | const apr_hash_t *overlay, |
442 | | const apr_hash_t *base, |
443 | | void * (*merger)(apr_pool_t *p, |
444 | | const void *key, |
445 | | apr_ssize_t klen, |
446 | | const void *h1_val, |
447 | | const void *h2_val, |
448 | | const void *data), |
449 | | const void *data) |
450 | 0 | { |
451 | 0 | apr_hash_t *res; |
452 | 0 | apr_hash_entry_t *new_vals = NULL; |
453 | 0 | apr_hash_entry_t *iter; |
454 | 0 | apr_hash_entry_t *ent; |
455 | 0 | unsigned int i, j, k, hash; |
456 | |
|
457 | 0 | #if APR_POOL_DEBUG |
458 | | /* we don't copy keys and values, so it's necessary that |
459 | | * overlay->a.pool and base->a.pool have a life span at least |
460 | | * as long as p |
461 | | */ |
462 | 0 | if (!apr_pool_is_ancestor(overlay->pool, p)) { |
463 | 0 | fprintf(stderr, |
464 | 0 | "apr_hash_merge: overlay's pool is not an ancestor of p\n"); |
465 | 0 | abort(); |
466 | 0 | } |
467 | 0 | if (!apr_pool_is_ancestor(base->pool, p)) { |
468 | 0 | fprintf(stderr, |
469 | 0 | "apr_hash_merge: base's pool is not an ancestor of p\n"); |
470 | 0 | abort(); |
471 | 0 | } |
472 | 0 | #endif |
473 | | |
474 | 0 | res = apr_palloc(p, sizeof(apr_hash_t)); |
475 | 0 | res->pool = p; |
476 | 0 | res->free = NULL; |
477 | 0 | res->hash_func = base->hash_func; |
478 | 0 | res->count = base->count; |
479 | 0 | res->max = (overlay->max > base->max) ? overlay->max : base->max; |
480 | 0 | if (base->count + overlay->count > res->max) { |
481 | 0 | res->max = res->max * 2 + 1; |
482 | 0 | } |
483 | 0 | res->seed = base->seed; |
484 | 0 | res->array = alloc_array(res, res->max); |
485 | 0 | if (base->count + overlay->count) { |
486 | 0 | new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * |
487 | 0 | (base->count + overlay->count)); |
488 | 0 | } |
489 | 0 | j = 0; |
490 | 0 | for (k = 0; k <= base->max; k++) { |
491 | 0 | for (iter = base->array[k]; iter; iter = iter->next) { |
492 | 0 | i = iter->hash & res->max; |
493 | 0 | new_vals[j].klen = iter->klen; |
494 | 0 | new_vals[j].key = iter->key; |
495 | 0 | new_vals[j].val = iter->val; |
496 | 0 | new_vals[j].hash = iter->hash; |
497 | 0 | new_vals[j].next = res->array[i]; |
498 | 0 | res->array[i] = &new_vals[j]; |
499 | 0 | j++; |
500 | 0 | } |
501 | 0 | } |
502 | |
|
503 | 0 | for (k = 0; k <= overlay->max; k++) { |
504 | 0 | for (iter = overlay->array[k]; iter; iter = iter->next) { |
505 | 0 | if (res->hash_func) |
506 | 0 | hash = res->hash_func(iter->key, &iter->klen); |
507 | 0 | else |
508 | 0 | hash = hashfunc_default(iter->key, &iter->klen, res->seed); |
509 | 0 | i = hash & res->max; |
510 | 0 | for (ent = res->array[i]; ent; ent = ent->next) { |
511 | 0 | if ((ent->klen == iter->klen) && |
512 | 0 | (memcmp(ent->key, iter->key, iter->klen) == 0)) { |
513 | 0 | if (merger) { |
514 | 0 | ent->val = (*merger)(p, iter->key, iter->klen, |
515 | 0 | iter->val, ent->val, data); |
516 | 0 | } |
517 | 0 | else { |
518 | 0 | ent->val = iter->val; |
519 | 0 | } |
520 | 0 | break; |
521 | 0 | } |
522 | 0 | } |
523 | 0 | if (!ent) { |
524 | 0 | new_vals[j].klen = iter->klen; |
525 | 0 | new_vals[j].key = iter->key; |
526 | 0 | new_vals[j].val = iter->val; |
527 | 0 | new_vals[j].hash = hash; |
528 | 0 | new_vals[j].next = res->array[i]; |
529 | 0 | res->array[i] = &new_vals[j]; |
530 | 0 | res->count++; |
531 | 0 | j++; |
532 | 0 | } |
533 | 0 | } |
534 | 0 | } |
535 | 0 | return res; |
536 | 0 | } |
537 | | |
538 | | /* This is basically the following... |
539 | | * for every element in hash table { |
540 | | * comp elemeny.key, element.value |
541 | | * } |
542 | | * |
543 | | * Like with apr_table_do, the comp callback is called for each and every |
544 | | * element of the hash table. |
545 | | */ |
546 | | APR_DECLARE(int) apr_hash_do(apr_hash_do_callback_fn_t *comp, |
547 | | void *rec, const apr_hash_t *ht) |
548 | 0 | { |
549 | 0 | apr_hash_index_t hix; |
550 | 0 | apr_hash_index_t *hi; |
551 | 0 | int rv, dorv = 1; |
552 | |
|
553 | 0 | hix.ht = (apr_hash_t *)ht; |
554 | 0 | hix.index = 0; |
555 | 0 | hix.this = NULL; |
556 | 0 | hix.next = NULL; |
557 | |
|
558 | 0 | if ((hi = apr_hash_next(&hix))) { |
559 | | /* Scan the entire table */ |
560 | 0 | do { |
561 | 0 | rv = (*comp)(rec, hi->this->key, hi->this->klen, hi->this->val); |
562 | 0 | } while (rv && (hi = apr_hash_next(hi))); |
563 | |
|
564 | 0 | if (rv == 0) { |
565 | 0 | dorv = 0; |
566 | 0 | } |
567 | 0 | } |
568 | 0 | return dorv; |
569 | 0 | } |
570 | | |
571 | | APR_POOL_IMPLEMENT_ACCESSOR(hash) |