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
40 #define ARRAY_SIZE(a) (sizeof((a)) / sizeof((a)[0]))
41
42 struct x_hash_table_struct {
43 unsigned int bucket_index;
44 unsigned int total_keys;
45 x_list **buckets;
46
47 x_hash_fun *hash_key;
48 x_compare_fun *compare_keys;
49 x_destroy_fun *destroy_key;
50 x_destroy_fun *destroy_value;
51 };
52
53 #define ITEM_NEW(k, v) X_PFX(list_prepend) ((x_list *)(k), v)
54 #define ITEM_FREE(i) X_PFX(list_free_1) (i)
55 #define ITEM_KEY(i) ((void *)(i)->next)
56 #define ITEM_VALUE(i) ((i)->data)
57
58 #define SPLIT_THRESHOLD_FACTOR 2
59
60 /* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */
61 static const unsigned int bucket_sizes[] = {
62 29, 53, 97, 193, 389, 769, 1543,
63 3079, 6151, 12289, 24593, 49157,
64 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
65 12582917,
66 25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
67 1610612741
68 };
69
70 static inline unsigned int
hash_table_total_buckets(x_hash_table * h)71 hash_table_total_buckets(x_hash_table *h)
72 {
73 return bucket_sizes[h->bucket_index];
74 }
75
76 static inline void
hash_table_destroy_item(x_hash_table * h,void * k,void * v)77 hash_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
86 static inline size_t
hash_table_hash_key(x_hash_table * h,void * k)87 hash_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
95 static inline int
hash_table_compare_keys(x_hash_table * h,void * k1,void * k2)96 hash_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
104 static void
hash_table_split(x_hash_table * h)105 hash_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 == ARRAY_SIZE(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
145 X_EXTERN x_hash_table *
X_PFX(hash_table_new)146 X_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
172 X_EXTERN void
X_PFX(hash_table_free)173 X_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
194 X_EXTERN unsigned int
X_PFX(hash_table_size)195 X_PFX(hash_table_size) (x_hash_table * h) {
196 assert(h != NULL);
197
198 return h->total_keys;
199 }
200
201 static void
hash_table_modify(x_hash_table * h,void * k,void * v,int replace)202 hash_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
243 X_EXTERN void
X_PFX(hash_table_insert)244 X_PFX(hash_table_insert) (x_hash_table * h, void *k, void *v) {
245 hash_table_modify(h, k, v, 0);
246 }
247
248 X_EXTERN void
X_PFX(hash_table_replace)249 X_PFX(hash_table_replace) (x_hash_table * h, void *k, void *v) {
250 hash_table_modify(h, k, v, 1);
251 }
252
253 X_EXTERN void
X_PFX(hash_table_remove)254 X_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
278 X_EXTERN void *
X_PFX(hash_table_lookup)279 X_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
305 X_EXTERN void
X_PFX(hash_table_foreach)306 X_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