x-hash.c revision 35c4bbdf 
1/* x-hash.c - basic hash tables
2 *
3 * Copyright (c) 2002-2012 Apple Inc. All rights reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation files
7 * (the "Software"), to deal in the Software without restriction,
8 * including without limitation the rights to use, copy, modify, merge,
9 * publish, distribute, sublicense, and/or sell copies of the Software,
10 * and to permit persons to whom the Software is furnished to do so,
11 * subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT.  IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
20 * HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
23 * DEALINGS IN THE SOFTWARE.
24 *
25 * Except as contained in this notice, the name(s) of the above
26 * copyright holders shall not be used in advertising or otherwise to
27 * promote the sale, use or other dealings in this Software without
28 * prior written authorization.
29 */
30
31#ifdef HAVE_DIX_CONFIG_H
32#include <dix-config.h>
33#endif
34
35#include "x-hash.h"
36#include "x-list.h"
37#include <stdlib.h>
38#include <assert.h>
39
40struct x_hash_table_struct {
41    unsigned int bucket_index;
42    unsigned int total_keys;
43    x_list **buckets;
44
45    x_hash_fun *hash_key;
46    x_compare_fun *compare_keys;
47    x_destroy_fun *destroy_key;
48    x_destroy_fun *destroy_value;
49};
50
51#define ITEM_NEW(k, v) X_PFX(list_prepend) ((x_list *)(k), v)
52#define ITEM_FREE(i)   X_PFX(list_free_1) (i)
53#define ITEM_KEY(i)    ((void *)(i)->next)
54#define ITEM_VALUE(i)  ((i)->data)
55
56#define SPLIT_THRESHOLD_FACTOR 2
57
58/* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */
59static const unsigned int bucket_sizes[] = {
60    29,       53,        97,        193,        389,        769,       1543,
61    3079,     6151, 12289, 24593, 49157,
62    98317,    196613,   393241,    786433,    1572869,   3145739,   6291469,
63    12582917,
64    25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
65    1610612741
66};
67
68#define N_BUCKET_SIZES (sizeof(bucket_sizes) / sizeof(bucket_sizes[0]))
69
70static inline unsigned int
71hash_table_total_buckets(x_hash_table *h)
72{
73    return bucket_sizes[h->bucket_index];
74}
75
76static inline void
77hash_table_destroy_item(x_hash_table *h, void *k, void *v)
78{
79    if (h->destroy_key != 0)
80        (*h->destroy_key)(k);
81
82    if (h->destroy_value != 0)
83        (*h->destroy_value)(v);
84}
85
86static inline size_t
87hash_table_hash_key(x_hash_table *h, void *k)
88{
89    if (h->hash_key != 0)
90        return (*h->hash_key)(k);
91    else
92        return (size_t)k;
93}
94
95static inline int
96hash_table_compare_keys(x_hash_table *h, void *k1, void *k2)
97{
98    if (h->compare_keys == 0)
99        return k1 == k2;
100    else
101        return (*h->compare_keys)(k1, k2) == 0;
102}
103
104static void
105hash_table_split(x_hash_table *h)
106{
107    x_list **new, **old;
108    x_list *node, *item, *next;
109    int new_size, old_size;
110    size_t b;
111    int i;
112
113    if (h->bucket_index == N_BUCKET_SIZES - 1)
114        return;
115
116    old_size = hash_table_total_buckets(h);
117    old = h->buckets;
118
119    h->bucket_index++;
120
121    new_size = hash_table_total_buckets(h);
122    new = calloc(new_size, sizeof(x_list *));
123
124    if (new == 0) {
125        h->bucket_index--;
126        return;
127    }
128
129    for (i = 0; i < old_size; i++) {
130        for (node = old[i]; node != 0; node = next) {
131            next = node->next;
132            item = node->data;
133
134            b = hash_table_hash_key(h, ITEM_KEY(item)) % new_size;
135
136            node->next = new[b];
137            new[b] = node;
138        }
139    }
140
141    h->buckets = new;
142    free(old);
143}
144
145X_EXTERN x_hash_table *
146X_PFX(hash_table_new) (x_hash_fun * hash,
147                       x_compare_fun * compare,
148                       x_destroy_fun * key_destroy,
149                       x_destroy_fun * value_destroy) {
150    x_hash_table *h;
151
152    h = calloc(1, sizeof(x_hash_table));
153    if (h == 0)
154        return 0;
155
156    h->bucket_index = 0;
157    h->buckets = calloc(hash_table_total_buckets(h), sizeof(x_list *));
158
159    if (h->buckets == 0) {
160        free(h);
161        return 0;
162    }
163
164    h->hash_key = hash;
165    h->compare_keys = compare;
166    h->destroy_key = key_destroy;
167    h->destroy_value = value_destroy;
168
169    return h;
170}
171
172X_EXTERN void
173X_PFX(hash_table_free) (x_hash_table * h) {
174    int n, i;
175    x_list *node, *item;
176
177    assert(h != NULL);
178
179    n = hash_table_total_buckets(h);
180
181    for (i = 0; i < n; i++) {
182        for (node = h->buckets[i]; node != 0; node = node->next) {
183            item = node->data;
184            hash_table_destroy_item(h, ITEM_KEY(item), ITEM_VALUE(item));
185            ITEM_FREE(item);
186        }
187        X_PFX(list_free) (h->buckets[i]);
188    }
189
190    free(h->buckets);
191    free(h);
192}
193
194X_EXTERN unsigned int
195X_PFX(hash_table_size) (x_hash_table * h) {
196    assert(h != NULL);
197
198    return h->total_keys;
199}
200
201static void
202hash_table_modify(x_hash_table *h, void *k, void *v, int replace)
203{
204    size_t hash_value;
205    x_list *node, *item;
206
207    assert(h != NULL);
208
209    hash_value = hash_table_hash_key(h, k);
210
211    for (node = h->buckets[hash_value % hash_table_total_buckets(h)];
212         node != 0; node = node->next) {
213        item = node->data;
214
215        if (hash_table_compare_keys(h, ITEM_KEY(item), k)) {
216            if (replace) {
217                hash_table_destroy_item(h, ITEM_KEY(item),
218                                        ITEM_VALUE(item));
219                item->next = k;
220                ITEM_VALUE(item) = v;
221            }
222            else {
223                hash_table_destroy_item(h, k, ITEM_VALUE(item));
224                ITEM_VALUE(item) = v;
225            }
226            return;
227        }
228    }
229
230    /* Key isn't already in the table. Insert it. */
231
232    if (h->total_keys + 1
233        > hash_table_total_buckets(h) * SPLIT_THRESHOLD_FACTOR) {
234        hash_table_split(h);
235    }
236
237    hash_value = hash_value % hash_table_total_buckets(h);
238    h->buckets[hash_value] = X_PFX(list_prepend) (h->buckets[hash_value],
239                                                  ITEM_NEW(k, v));
240    h->total_keys++;
241}
242
243X_EXTERN void
244X_PFX(hash_table_insert) (x_hash_table * h, void *k, void *v) {
245    hash_table_modify(h, k, v, 0);
246}
247
248X_EXTERN void
249X_PFX(hash_table_replace) (x_hash_table * h, void *k, void *v) {
250    hash_table_modify(h, k, v, 1);
251}
252
253X_EXTERN void
254X_PFX(hash_table_remove) (x_hash_table * h, void *k) {
255    size_t hash_value;
256    x_list **ptr, *item;
257
258    assert(h != NULL);
259
260    hash_value = hash_table_hash_key(h, k);
261
262    for (ptr = &h->buckets[hash_value % hash_table_total_buckets(h)];
263         *ptr != 0; ptr = &((*ptr)->next)) {
264        item = (*ptr)->data;
265
266        if (hash_table_compare_keys(h, ITEM_KEY(item), k)) {
267            hash_table_destroy_item(h, ITEM_KEY(item), ITEM_VALUE(item));
268            ITEM_FREE(item);
269            item = *ptr;
270            *ptr = item->next;
271            X_PFX(list_free_1) (item);
272            h->total_keys--;
273            return;
274        }
275    }
276}
277
278X_EXTERN void *
279X_PFX(hash_table_lookup) (x_hash_table * h, void *k, void **k_ret) {
280    size_t hash_value;
281    x_list *node, *item;
282
283    assert(h != NULL);
284
285    hash_value = hash_table_hash_key(h, k);
286
287    for (node = h->buckets[hash_value % hash_table_total_buckets(h)];
288         node != 0; node = node->next) {
289        item = node->data;
290
291        if (hash_table_compare_keys(h, ITEM_KEY(item), k)) {
292            if (k_ret != 0)
293                *k_ret = ITEM_KEY(item);
294
295            return ITEM_VALUE(item);
296        }
297    }
298
299    if (k_ret != 0)
300        *k_ret = 0;
301
302    return 0;
303}
304
305X_EXTERN void
306X_PFX(hash_table_foreach) (x_hash_table * h,
307                           x_hash_foreach_fun * fun, void *data) {
308    int i, n;
309    x_list *node, *item;
310
311    assert(h != NULL);
312
313    n = hash_table_total_buckets(h);
314
315    for (i = 0; i < n; i++) {
316        for (node = h->buckets[i]; node != 0; node = node->next) {
317            item = node->data;
318            (*fun)(ITEM_KEY(item), ITEM_VALUE(item), data);
319        }
320    }
321}
322