1/* x-hash.c - basic hash tables
2
3   Copyright (c) 2002 Apple Computer, 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#ifdef HAVE_DIX_CONFIG_H
31#include <dix-config.h>
32#endif
33
34#include "x-hash.h"
35#include "x-list.h"
36#include <stdlib.h>
37#include <assert.h>
38
39struct x_hash_table_struct {
40    unsigned int bucket_index;
41    unsigned int total_keys;
42    x_list **buckets;
43
44    x_hash_fun *hash_key;
45    x_compare_fun *compare_keys;
46    x_destroy_fun *destroy_key;
47    x_destroy_fun *destroy_value;
48};
49
50#define ITEM_NEW(k, v) X_PFX (list_prepend) ((x_list *) (k), v)
51#define ITEM_FREE(i) X_PFX (list_free_1) (i)
52#define ITEM_KEY(i) ((void *) (i)->next)
53#define ITEM_VALUE(i) ((i)->data)
54
55#define SPLIT_THRESHOLD_FACTOR 2
56
57/* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */
58static const unsigned int bucket_sizes[] = {
59    29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157,
60    98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
61    25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
62    1610612741
63};
64
65#define N_BUCKET_SIZES (sizeof (bucket_sizes) / sizeof (bucket_sizes[0]))
66
67static inline unsigned int
68hash_table_total_buckets (x_hash_table *h)
69{
70    return bucket_sizes[h->bucket_index];
71}
72
73static inline void
74hash_table_destroy_item (x_hash_table *h, void *k, void *v)
75{
76    if (h->destroy_key != 0)
77        (*h->destroy_key) (k);
78
79    if (h->destroy_value != 0)
80        (*h->destroy_value) (v);
81}
82
83static inline size_t
84hash_table_hash_key (x_hash_table *h, void *k)
85{
86    if (h->hash_key != 0)
87        return (*h->hash_key) (k);
88    else
89        return (size_t) k;
90}
91
92static inline int
93hash_table_compare_keys (x_hash_table *h, void *k1, void *k2)
94{
95    if (h->compare_keys == 0)
96        return k1 == k2;
97    else
98        return (*h->compare_keys) (k1, k2) == 0;
99}
100
101static void
102hash_table_split (x_hash_table *h)
103{
104    x_list **new, **old;
105    x_list *node, *item, *next;
106    int new_size, old_size;
107    size_t b;
108    int i;
109
110    if (h->bucket_index == N_BUCKET_SIZES - 1)
111        return;
112
113    old_size = hash_table_total_buckets (h);
114    old = h->buckets;
115
116    h->bucket_index++;
117
118    new_size = hash_table_total_buckets (h);
119    new = calloc (new_size, sizeof (x_list *));
120
121    if (new == 0)
122    {
123        h->bucket_index--;
124        return;
125    }
126
127    for (i = 0; i < old_size; i++)
128    {
129        for (node = old[i]; node != 0; node = next)
130        {
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{
151    x_hash_table *h;
152
153    h = calloc (1, sizeof (x_hash_table));
154    if (h == 0)
155        return 0;
156
157    h->bucket_index = 0;
158    h->buckets = calloc (hash_table_total_buckets (h), sizeof (x_list *));
159
160    if (h->buckets == 0)
161    {
162        free (h);
163        return 0;
164    }
165
166    h->hash_key = hash;
167    h->compare_keys = compare;
168    h->destroy_key = key_destroy;
169    h->destroy_value = value_destroy;
170
171    return h;
172}
173
174X_EXTERN void
175X_PFX (hash_table_free) (x_hash_table *h)
176{
177    int n, i;
178    x_list *node, *item;
179
180    assert (h != NULL);
181
182    n = hash_table_total_buckets (h);
183
184    for (i = 0; i < n; i++)
185    {
186        for (node = h->buckets[i]; node != 0; node = node->next)
187        {
188            item = node->data;
189            hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
190            ITEM_FREE (item);
191        }
192        X_PFX (list_free) (h->buckets[i]);
193    }
194
195    free (h->buckets);
196    free (h);
197}
198
199X_EXTERN unsigned int
200X_PFX (hash_table_size) (x_hash_table *h)
201{
202    assert (h != NULL);
203
204    return h->total_keys;
205}
206
207static void
208hash_table_modify (x_hash_table *h, void *k, void *v, int replace)
209{
210    size_t hash_value;
211    x_list *node, *item;
212
213    assert (h != NULL);
214
215    hash_value = hash_table_hash_key (h, k);
216
217    for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
218         node != 0; node = node->next)
219    {
220        item = node->data;
221
222        if (hash_table_compare_keys (h, ITEM_KEY (item), k))
223        {
224            if (replace)
225            {
226                hash_table_destroy_item (h, ITEM_KEY (item),
227                                         ITEM_VALUE (item));
228                item->next = k;
229                ITEM_VALUE (item) = v;
230            }
231            else
232            {
233                hash_table_destroy_item (h, k, ITEM_VALUE (item));
234                ITEM_VALUE (item) = v;
235            }
236            return;
237        }
238    }
239
240    /* Key isn't already in the table. Insert it. */
241
242    if (h->total_keys + 1
243        > hash_table_total_buckets (h) * SPLIT_THRESHOLD_FACTOR)
244    {
245        hash_table_split (h);
246    }
247
248    hash_value = hash_value % hash_table_total_buckets (h);
249    h->buckets[hash_value] = X_PFX (list_prepend) (h->buckets[hash_value],
250                                                   ITEM_NEW (k, v));
251    h->total_keys++;
252}
253
254X_EXTERN void
255X_PFX (hash_table_insert) (x_hash_table *h, void *k, void *v)
256{
257    hash_table_modify (h, k, v, 0);
258}
259
260X_EXTERN void
261X_PFX (hash_table_replace) (x_hash_table *h, void *k, void *v)
262{
263    hash_table_modify (h, k, v, 1);
264}
265
266X_EXTERN void
267X_PFX (hash_table_remove) (x_hash_table *h, void *k)
268{
269    size_t hash_value;
270    x_list **ptr, *item;
271
272    assert (h != NULL);
273
274    hash_value = hash_table_hash_key (h, k);
275
276    for (ptr = &h->buckets[hash_value % hash_table_total_buckets (h)];
277         *ptr != 0; ptr = &((*ptr)->next))
278    {
279        item = (*ptr)->data;
280
281        if (hash_table_compare_keys (h, ITEM_KEY (item), k))
282        {
283            hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
284            ITEM_FREE (item);
285            item = *ptr;
286            *ptr = item->next;
287            X_PFX (list_free_1) (item);
288            h->total_keys--;
289            return;
290        }
291    }
292}
293
294X_EXTERN void *
295X_PFX (hash_table_lookup) (x_hash_table *h, void *k, void **k_ret)
296{
297    size_t hash_value;
298    x_list *node, *item;
299
300    assert (h != NULL);
301
302    hash_value = hash_table_hash_key (h, k);
303
304    for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
305         node != 0; node = node->next)
306    {
307        item = node->data;
308
309        if (hash_table_compare_keys (h, ITEM_KEY (item), k))
310        {
311            if (k_ret != 0)
312            *k_ret = ITEM_KEY (item);
313
314            return ITEM_VALUE (item);
315        }
316    }
317
318    if (k_ret != 0)
319        *k_ret = 0;
320
321    return 0;
322}
323
324X_EXTERN void
325X_PFX (hash_table_foreach) (x_hash_table *h,
326                            x_hash_foreach_fun *fun, void *data)
327{
328    int i, n;
329    x_list *node, *item;
330
331    assert (h != NULL);
332
333    n = hash_table_total_buckets (h);
334
335    for (i = 0; i < n; i++)
336    {
337        for (node = h->buckets[i]; node != 0; node = node->next)
338        {
339            item = node->data;
340            (*fun) (ITEM_KEY (item), ITEM_VALUE (item), data);
341        }
342    }
343}
344