Coverage Report

Created: 2023-03-26 06:28

/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)