← Back to branch summary

~ubuntu-branches/ubuntu/feisty/apache2/feisty

« back to all changes in this revision

Viewing changes to srclib/apr/tables/apr_hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Andreas Barth
  • Date: 2006-12-09 21:05:45 UTC
  • mfrom: (0.6.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20061209210545-h70s0xaqc2v8vqr2
Tags: 2.2.3-3.2
http://bugs.debian.org/396265
* Non-maintainer upload.
* 043_ajp_connection_reuse: Patch from upstream Bugzilla, fixing a critical
  issue with regard to connection reuse in mod_proxy_ajp.
  Closes: #396265

Show diffs side-by-side

added added

removed removed

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