1 /**************************************************************************
2 *
3 * Copyright 2008 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28 /**
29 * @file
30 * General purpose hash table implementation.
31 *
32 * Just uses the cso_hash for now, but it might be better switch to a linear
33 * probing hash table implementation at some point -- as it is said they have
34 * better lookup and cache performance and it appears to be possible to write
35 * a lock-free implementation of such hash tables .
36 *
37 * @author José Fonseca <jfonseca@vmware.com>
38 */
39
40
41 #include "pipe/p_compiler.h"
42 #include "util/u_debug.h"
43
44 #include "cso_cache/cso_hash.h"
45
46 #include "util/u_memory.h"
47 #include "util/u_hash_table.h"
48
49 #define XXH_INLINE_ALL
50 #include "xxhash.h"
51
52 struct util_hash_table
53 {
54 struct cso_hash *cso;
55
56 /** Hash function */
57 unsigned (*hash)(void *key);
58
59 /** Compare two keys */
60 int (*compare)(void *key1, void *key2);
61
62 /** free value */
63 void (*destroy)(void *value);
64 };
65
66
67 struct util_hash_table_item
68 {
69 void *key;
70 void *value;
71 };
72
73
74 static inline struct util_hash_table_item *
util_hash_table_item(struct cso_hash_iter iter)75 util_hash_table_item(struct cso_hash_iter iter)
76 {
77 return (struct util_hash_table_item *)cso_hash_iter_data(iter);
78 }
79
80
81 struct util_hash_table *
util_hash_table_create(unsigned (* hash)(void * key),int (* compare)(void * key1,void * key2),void (* destroy)(void * value))82 util_hash_table_create(unsigned (*hash)(void *key),
83 int (*compare)(void *key1, void *key2),
84 void (*destroy)(void *value))
85 {
86 struct util_hash_table *ht;
87
88 ht = MALLOC_STRUCT(util_hash_table);
89 if(!ht)
90 return NULL;
91
92 ht->cso = cso_hash_create();
93 if(!ht->cso) {
94 FREE(ht);
95 return NULL;
96 }
97
98 ht->hash = hash;
99 ht->compare = compare;
100 ht->destroy = destroy;
101
102 return ht;
103 }
104
105
106 static inline struct cso_hash_iter
util_hash_table_find_iter(struct util_hash_table * ht,void * key,unsigned key_hash)107 util_hash_table_find_iter(struct util_hash_table *ht,
108 void *key,
109 unsigned key_hash)
110 {
111 struct cso_hash_iter iter;
112 struct util_hash_table_item *item;
113
114 iter = cso_hash_find(ht->cso, key_hash);
115 while (!cso_hash_iter_is_null(iter)) {
116 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
117 if (!ht->compare(item->key, key))
118 break;
119 iter = cso_hash_iter_next(iter);
120 }
121
122 return iter;
123 }
124
125
126 static inline struct util_hash_table_item *
util_hash_table_find_item(struct util_hash_table * ht,void * key,unsigned key_hash)127 util_hash_table_find_item(struct util_hash_table *ht,
128 void *key,
129 unsigned key_hash)
130 {
131 struct cso_hash_iter iter;
132 struct util_hash_table_item *item;
133
134 iter = cso_hash_find(ht->cso, key_hash);
135 while (!cso_hash_iter_is_null(iter)) {
136 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
137 if (!ht->compare(item->key, key))
138 return item;
139 iter = cso_hash_iter_next(iter);
140 }
141
142 return NULL;
143 }
144
145
146 enum pipe_error
util_hash_table_set(struct util_hash_table * ht,void * key,void * value)147 util_hash_table_set(struct util_hash_table *ht,
148 void *key,
149 void *value)
150 {
151 unsigned key_hash;
152 struct util_hash_table_item *item;
153 struct cso_hash_iter iter;
154
155 assert(ht);
156 if (!ht)
157 return PIPE_ERROR_BAD_INPUT;
158
159 key_hash = ht->hash(key);
160
161 item = util_hash_table_find_item(ht, key, key_hash);
162 if(item) {
163 ht->destroy(item->value);
164 item->value = value;
165 return PIPE_OK;
166 }
167
168 item = MALLOC_STRUCT(util_hash_table_item);
169 if(!item)
170 return PIPE_ERROR_OUT_OF_MEMORY;
171
172 item->key = key;
173 item->value = value;
174
175 iter = cso_hash_insert(ht->cso, key_hash, item);
176 if(cso_hash_iter_is_null(iter)) {
177 FREE(item);
178 return PIPE_ERROR_OUT_OF_MEMORY;
179 }
180
181 return PIPE_OK;
182 }
183
184
185 void *
util_hash_table_get(struct util_hash_table * ht,void * key)186 util_hash_table_get(struct util_hash_table *ht,
187 void *key)
188 {
189 unsigned key_hash;
190 struct util_hash_table_item *item;
191
192 assert(ht);
193 if (!ht)
194 return NULL;
195
196 key_hash = ht->hash(key);
197
198 item = util_hash_table_find_item(ht, key, key_hash);
199 if(!item)
200 return NULL;
201
202 return item->value;
203 }
204
205
206 void
util_hash_table_remove(struct util_hash_table * ht,void * key)207 util_hash_table_remove(struct util_hash_table *ht,
208 void *key)
209 {
210 unsigned key_hash;
211 struct cso_hash_iter iter;
212 struct util_hash_table_item *item;
213
214 assert(ht);
215 if (!ht)
216 return;
217
218 key_hash = ht->hash(key);
219
220 iter = util_hash_table_find_iter(ht, key, key_hash);
221 if(cso_hash_iter_is_null(iter))
222 return;
223
224 item = util_hash_table_item(iter);
225 assert(item);
226 ht->destroy(item->value);
227 FREE(item);
228
229 cso_hash_erase(ht->cso, iter);
230 }
231
232
233 void
util_hash_table_clear(struct util_hash_table * ht)234 util_hash_table_clear(struct util_hash_table *ht)
235 {
236 struct cso_hash_iter iter;
237 struct util_hash_table_item *item;
238
239 assert(ht);
240 if (!ht)
241 return;
242
243 iter = cso_hash_first_node(ht->cso);
244 while (!cso_hash_iter_is_null(iter)) {
245 item = (struct util_hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
246 ht->destroy(item->value);
247 FREE(item);
248 iter = cso_hash_first_node(ht->cso);
249 }
250 }
251
252
253 enum pipe_error
util_hash_table_foreach(struct util_hash_table * ht,enum pipe_error (* callback)(void * key,void * value,void * data),void * data)254 util_hash_table_foreach(struct util_hash_table *ht,
255 enum pipe_error (*callback)
256 (void *key, void *value, void *data),
257 void *data)
258 {
259 struct cso_hash_iter iter;
260 struct util_hash_table_item *item;
261 enum pipe_error result;
262
263 assert(ht);
264 if (!ht)
265 return PIPE_ERROR_BAD_INPUT;
266
267 iter = cso_hash_first_node(ht->cso);
268 while (!cso_hash_iter_is_null(iter)) {
269 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
270 result = callback(item->key, item->value, data);
271 if(result != PIPE_OK)
272 return result;
273 iter = cso_hash_iter_next(iter);
274 }
275
276 return PIPE_OK;
277 }
278
279
280 void
util_hash_table_destroy(struct util_hash_table * ht)281 util_hash_table_destroy(struct util_hash_table *ht)
282 {
283 struct cso_hash_iter iter;
284 struct util_hash_table_item *item;
285
286 assert(ht);
287 if (!ht)
288 return;
289
290 iter = cso_hash_first_node(ht->cso);
291 while (!cso_hash_iter_is_null(iter)) {
292 item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
293 ht->destroy(item->value);
294 FREE(item);
295 iter = cso_hash_iter_next(iter);
296 }
297
298 cso_hash_delete(ht->cso);
299
300 FREE(ht);
301 }
302
hash_func_pointer(void * key)303 static unsigned hash_func_pointer(void *key)
304 {
305 return XXH32(&key, sizeof(key), 0);
306 }
307
compare_func_pointer(void * key1,void * key2)308 static int compare_func_pointer(void *key1, void *key2)
309 {
310 return key1 != key2;
311 }
312
hash_func_u64(void * key)313 static unsigned hash_func_u64(void *key)
314 {
315 return XXH32(key, sizeof(uint64_t), 0);
316 }
317
compare_func_u64(void * key1,void * key2)318 static int compare_func_u64(void *key1, void *key2)
319 {
320 return *(const uint64_t *)key1 != *(const uint64_t*)key2;
321 }
322
util_hash_table_u64_uses_pointer(void)323 static bool util_hash_table_u64_uses_pointer(void)
324 {
325 /* return true if we can store a uint64_t in a pointer */
326 return sizeof(void *) >= sizeof(uint64_t);
327 }
328
329 struct util_hash_table_u64 *
util_hash_table_create_u64(void (* destroy)(void * value))330 util_hash_table_create_u64(void (*destroy)(void *value))
331 {
332 if (util_hash_table_u64_uses_pointer()) {
333 return (struct util_hash_table_u64 *)
334 util_hash_table_create(hash_func_pointer,
335 compare_func_pointer,
336 destroy);
337 }
338
339 return (struct util_hash_table_u64 *)
340 util_hash_table_create(hash_func_u64,
341 compare_func_u64,
342 destroy);
343 }
344
345 enum pipe_error
util_hash_table_set_u64(struct util_hash_table_u64 * ht_u64,uint64_t key,void * value)346 util_hash_table_set_u64(struct util_hash_table_u64 *ht_u64,
347 uint64_t key,
348 void *value)
349 {
350 struct util_hash_table *ht = (struct util_hash_table *)ht_u64;
351 uint64_t *real_key;
352 enum pipe_error err;
353
354 if (util_hash_table_u64_uses_pointer())
355 return util_hash_table_set(ht, uintptr_to_pointer(key), value);
356
357 real_key = MALLOC(sizeof(*real_key));
358 if (!real_key)
359 return PIPE_ERROR_OUT_OF_MEMORY;
360 *real_key = key;
361
362 err = util_hash_table_set(ht, real_key, value);
363 if (err != PIPE_OK)
364 FREE(real_key);
365
366 return err;
367 }
368
369 void *
util_hash_table_get_u64(struct util_hash_table_u64 * ht_u64,uint64_t key)370 util_hash_table_get_u64(struct util_hash_table_u64 *ht_u64,
371 uint64_t key)
372 {
373 struct util_hash_table *ht = (struct util_hash_table *)ht_u64;
374
375 if (util_hash_table_u64_uses_pointer())
376 return util_hash_table_get(ht, uintptr_to_pointer(key));
377
378 return util_hash_table_get(ht, &key);
379 }
380
381 void
util_hash_table_remove_u64(struct util_hash_table_u64 * ht_u64,uint64_t key)382 util_hash_table_remove_u64(struct util_hash_table_u64 *ht_u64,
383 uint64_t key)
384 {
385 struct util_hash_table *ht = (struct util_hash_table *)ht_u64;
386 unsigned key_hash;
387 struct cso_hash_iter iter;
388 struct util_hash_table_item *item;
389
390 if (util_hash_table_u64_uses_pointer()) {
391 util_hash_table_remove(ht, uintptr_to_pointer(key));
392 return;
393 }
394
395 key_hash = ht->hash(&key);
396 iter = util_hash_table_find_iter(ht, &key, key_hash);
397
398 if (cso_hash_iter_is_null(iter))
399 return;
400
401 item = util_hash_table_item(iter);
402 ht->destroy(item->value);
403 FREE(item->key);
404 FREE(item);
405
406 cso_hash_erase(ht->cso, iter);
407 }
408
409 void
util_hash_table_destroy_u64(struct util_hash_table_u64 * ht_u64)410 util_hash_table_destroy_u64(struct util_hash_table_u64 *ht_u64)
411 {
412 struct util_hash_table *ht = (struct util_hash_table *)ht_u64;
413 struct cso_hash_iter iter;
414 struct util_hash_table_item *item;
415
416 if (util_hash_table_u64_uses_pointer()) {
417 util_hash_table_destroy(ht);
418 return;
419 }
420
421 iter = cso_hash_first_node(ht->cso);
422 while (!cso_hash_iter_is_null(iter)) {
423 item = util_hash_table_item(iter);
424 ht->destroy(item->value);
425 FREE(item->key);
426 FREE(item);
427 iter = cso_hash_iter_next(iter);
428 }
429
430 cso_hash_delete(ht->cso);
431
432 FREE(ht);
433 }
434