Commit | Line | Data |
---|---|---|
a09e091a JB |
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 | struct 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 */ | |
59 | static 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 | ||
70 | static inline unsigned int | |
71 | hash_table_total_buckets(x_hash_table *h) | |
72 | { | |
73 | return bucket_sizes[h->bucket_index]; | |
74 | } | |
75 | ||
76 | static inline void | |
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 | |
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 | |
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 | |
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 == 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 | ||
145 | X_EXTERN x_hash_table * | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 * | |
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 | |
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 | } |