util/hash_table: replace fnv1a hash function with xxhash
[mesa.git] / src / util / hash_table.c
1 /*
2 * Copyright © 2009,2012 Intel Corporation
3 * Copyright © 1988-2004 Keith Packard and Bart Massey.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 *
24 * Except as contained in this notice, the names of the authors
25 * or their institutions shall not be used in advertising or
26 * otherwise to promote the sale, use or other dealings in this
27 * Software without prior written authorization from the
28 * authors.
29 *
30 * Authors:
31 * Eric Anholt <eric@anholt.net>
32 * Keith Packard <keithp@keithp.com>
33 */
34
35 /**
36 * Implements an open-addressing, linear-reprobing hash table.
37 *
38 * For more information, see:
39 *
40 * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
41 */
42
43 #include <stdlib.h>
44 #include <string.h>
45 #include <assert.h>
46
47 #include "hash_table.h"
48 #include "ralloc.h"
49 #include "macros.h"
50 #include "u_memory.h"
51 #include "fast_urem_by_const.h"
52 #include "util/u_memory.h"
53
54 #define XXH_INLINE_ALL
55 #include "xxhash.h"
56
57 /**
58 * Magic number that gets stored outside of the struct hash_table.
59 *
60 * The hash table needs a particular pointer to be the marker for a key that
61 * was deleted from the table, along with NULL for the "never allocated in the
62 * table" marker. Legacy GL allows any GLuint to be used as a GL object name,
63 * and we use a 1:1 mapping from GLuints to key pointers, so we need to be
64 * able to track a GLuint that happens to match the deleted key outside of
65 * struct hash_table. We tell the hash table to use "1" as the deleted key
66 * value, so that we test the deleted-key-in-the-table path as best we can.
67 */
68 #define DELETED_KEY_VALUE 1
69
70 static inline void *
71 uint_key(unsigned id)
72 {
73 return (void *)(uintptr_t) id;
74 }
75
76 static const uint32_t deleted_key_value;
77
78 /**
79 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
80 * p and p-2 are both prime. These tables are sized to have an extra 10%
81 * free to avoid exponential performance degradation as the hash table fills
82 */
83 static const struct {
84 uint32_t max_entries, size, rehash;
85 uint64_t size_magic, rehash_magic;
86 } hash_sizes[] = {
87 #define ENTRY(max_entries, size, rehash) \
88 { max_entries, size, rehash, \
89 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
90
91 ENTRY(2, 5, 3 ),
92 ENTRY(4, 7, 5 ),
93 ENTRY(8, 13, 11 ),
94 ENTRY(16, 19, 17 ),
95 ENTRY(32, 43, 41 ),
96 ENTRY(64, 73, 71 ),
97 ENTRY(128, 151, 149 ),
98 ENTRY(256, 283, 281 ),
99 ENTRY(512, 571, 569 ),
100 ENTRY(1024, 1153, 1151 ),
101 ENTRY(2048, 2269, 2267 ),
102 ENTRY(4096, 4519, 4517 ),
103 ENTRY(8192, 9013, 9011 ),
104 ENTRY(16384, 18043, 18041 ),
105 ENTRY(32768, 36109, 36107 ),
106 ENTRY(65536, 72091, 72089 ),
107 ENTRY(131072, 144409, 144407 ),
108 ENTRY(262144, 288361, 288359 ),
109 ENTRY(524288, 576883, 576881 ),
110 ENTRY(1048576, 1153459, 1153457 ),
111 ENTRY(2097152, 2307163, 2307161 ),
112 ENTRY(4194304, 4613893, 4613891 ),
113 ENTRY(8388608, 9227641, 9227639 ),
114 ENTRY(16777216, 18455029, 18455027 ),
115 ENTRY(33554432, 36911011, 36911009 ),
116 ENTRY(67108864, 73819861, 73819859 ),
117 ENTRY(134217728, 147639589, 147639587 ),
118 ENTRY(268435456, 295279081, 295279079 ),
119 ENTRY(536870912, 590559793, 590559791 ),
120 ENTRY(1073741824, 1181116273, 1181116271 ),
121 ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
122 };
123
124 ASSERTED static inline bool
125 key_pointer_is_reserved(const struct hash_table *ht, const void *key)
126 {
127 return key == NULL || key == ht->deleted_key;
128 }
129
130 static int
131 entry_is_free(const struct hash_entry *entry)
132 {
133 return entry->key == NULL;
134 }
135
136 static int
137 entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry)
138 {
139 return entry->key == ht->deleted_key;
140 }
141
142 static int
143 entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
144 {
145 return entry->key != NULL && entry->key != ht->deleted_key;
146 }
147
148 bool
149 _mesa_hash_table_init(struct hash_table *ht,
150 void *mem_ctx,
151 uint32_t (*key_hash_function)(const void *key),
152 bool (*key_equals_function)(const void *a,
153 const void *b))
154 {
155 ht->size_index = 0;
156 ht->size = hash_sizes[ht->size_index].size;
157 ht->rehash = hash_sizes[ht->size_index].rehash;
158 ht->size_magic = hash_sizes[ht->size_index].size_magic;
159 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
160 ht->max_entries = hash_sizes[ht->size_index].max_entries;
161 ht->key_hash_function = key_hash_function;
162 ht->key_equals_function = key_equals_function;
163 ht->table = rzalloc_array(mem_ctx, struct hash_entry, ht->size);
164 ht->entries = 0;
165 ht->deleted_entries = 0;
166 ht->deleted_key = &deleted_key_value;
167
168 return ht->table != NULL;
169 }
170
171 struct hash_table *
172 _mesa_hash_table_create(void *mem_ctx,
173 uint32_t (*key_hash_function)(const void *key),
174 bool (*key_equals_function)(const void *a,
175 const void *b))
176 {
177 struct hash_table *ht;
178
179 /* mem_ctx is used to allocate the hash table, but the hash table is used
180 * to allocate all of the suballocations.
181 */
182 ht = ralloc(mem_ctx, struct hash_table);
183 if (ht == NULL)
184 return NULL;
185
186 if (!_mesa_hash_table_init(ht, ht, key_hash_function, key_equals_function)) {
187 ralloc_free(ht);
188 return NULL;
189 }
190
191 return ht;
192 }
193
194 struct hash_table *
195 _mesa_hash_table_clone(struct hash_table *src, void *dst_mem_ctx)
196 {
197 struct hash_table *ht;
198
199 ht = ralloc(dst_mem_ctx, struct hash_table);
200 if (ht == NULL)
201 return NULL;
202
203 memcpy(ht, src, sizeof(struct hash_table));
204
205 ht->table = ralloc_array(ht, struct hash_entry, ht->size);
206 if (ht->table == NULL) {
207 ralloc_free(ht);
208 return NULL;
209 }
210
211 memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
212
213 return ht;
214 }
215
216 /**
217 * Frees the given hash table.
218 *
219 * If delete_function is passed, it gets called on each entry present before
220 * freeing.
221 */
222 void
223 _mesa_hash_table_destroy(struct hash_table *ht,
224 void (*delete_function)(struct hash_entry *entry))
225 {
226 if (!ht)
227 return;
228
229 if (delete_function) {
230 hash_table_foreach(ht, entry) {
231 delete_function(entry);
232 }
233 }
234 ralloc_free(ht);
235 }
236
237 /**
238 * Deletes all entries of the given hash table without deleting the table
239 * itself or changing its structure.
240 *
241 * If delete_function is passed, it gets called on each entry present.
242 */
243 void
244 _mesa_hash_table_clear(struct hash_table *ht,
245 void (*delete_function)(struct hash_entry *entry))
246 {
247 struct hash_entry *entry;
248
249 for (entry = ht->table; entry != ht->table + ht->size; entry++) {
250 if (entry->key == NULL)
251 continue;
252
253 if (delete_function != NULL && entry->key != ht->deleted_key)
254 delete_function(entry);
255
256 entry->key = NULL;
257 }
258
259 ht->entries = 0;
260 ht->deleted_entries = 0;
261 }
262
263 /** Sets the value of the key pointer used for deleted entries in the table.
264 *
265 * The assumption is that usually keys are actual pointers, so we use a
266 * default value of a pointer to an arbitrary piece of storage in the library.
267 * But in some cases a consumer wants to store some other sort of value in the
268 * table, like a uint32_t, in which case that pointer may conflict with one of
269 * their valid keys. This lets that user select a safe value.
270 *
271 * This must be called before any keys are actually deleted from the table.
272 */
273 void
274 _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
275 {
276 ht->deleted_key = deleted_key;
277 }
278
279 static struct hash_entry *
280 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
281 {
282 assert(!key_pointer_is_reserved(ht, key));
283
284 uint32_t size = ht->size;
285 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
286 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
287 ht->rehash_magic);
288 uint32_t hash_address = start_hash_address;
289
290 do {
291 struct hash_entry *entry = ht->table + hash_address;
292
293 if (entry_is_free(entry)) {
294 return NULL;
295 } else if (entry_is_present(ht, entry) && entry->hash == hash) {
296 if (ht->key_equals_function(key, entry->key)) {
297 return entry;
298 }
299 }
300
301 hash_address += double_hash;
302 if (hash_address >= size)
303 hash_address -= size;
304 } while (hash_address != start_hash_address);
305
306 return NULL;
307 }
308
309 /**
310 * Finds a hash table entry with the given key and hash of that key.
311 *
312 * Returns NULL if no entry is found. Note that the data pointer may be
313 * modified by the user.
314 */
315 struct hash_entry *
316 _mesa_hash_table_search(struct hash_table *ht, const void *key)
317 {
318 assert(ht->key_hash_function);
319 return hash_table_search(ht, ht->key_hash_function(key), key);
320 }
321
322 struct hash_entry *
323 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
324 const void *key)
325 {
326 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
327 return hash_table_search(ht, hash, key);
328 }
329
330 static struct hash_entry *
331 hash_table_insert(struct hash_table *ht, uint32_t hash,
332 const void *key, void *data);
333
334 static void
335 hash_table_insert_rehash(struct hash_table *ht, uint32_t hash,
336 const void *key, void *data)
337 {
338 uint32_t size = ht->size;
339 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
340 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
341 ht->rehash_magic);
342 uint32_t hash_address = start_hash_address;
343 do {
344 struct hash_entry *entry = ht->table + hash_address;
345
346 if (likely(entry->key == NULL)) {
347 entry->hash = hash;
348 entry->key = key;
349 entry->data = data;
350 return;
351 }
352
353 hash_address += double_hash;
354 if (hash_address >= size)
355 hash_address -= size;
356 } while (true);
357 }
358
359 static void
360 _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
361 {
362 struct hash_table old_ht;
363 struct hash_entry *table;
364
365 if (new_size_index >= ARRAY_SIZE(hash_sizes))
366 return;
367
368 table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry,
369 hash_sizes[new_size_index].size);
370 if (table == NULL)
371 return;
372
373 old_ht = *ht;
374
375 ht->table = table;
376 ht->size_index = new_size_index;
377 ht->size = hash_sizes[ht->size_index].size;
378 ht->rehash = hash_sizes[ht->size_index].rehash;
379 ht->size_magic = hash_sizes[ht->size_index].size_magic;
380 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
381 ht->max_entries = hash_sizes[ht->size_index].max_entries;
382 ht->entries = 0;
383 ht->deleted_entries = 0;
384
385 hash_table_foreach(&old_ht, entry) {
386 hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data);
387 }
388
389 ht->entries = old_ht.entries;
390
391 ralloc_free(old_ht.table);
392 }
393
394 static struct hash_entry *
395 hash_table_insert(struct hash_table *ht, uint32_t hash,
396 const void *key, void *data)
397 {
398 struct hash_entry *available_entry = NULL;
399
400 assert(!key_pointer_is_reserved(ht, key));
401
402 if (ht->entries >= ht->max_entries) {
403 _mesa_hash_table_rehash(ht, ht->size_index + 1);
404 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
405 _mesa_hash_table_rehash(ht, ht->size_index);
406 }
407
408 uint32_t size = ht->size;
409 uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
410 uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
411 ht->rehash_magic);
412 uint32_t hash_address = start_hash_address;
413 do {
414 struct hash_entry *entry = ht->table + hash_address;
415
416 if (!entry_is_present(ht, entry)) {
417 /* Stash the first available entry we find */
418 if (available_entry == NULL)
419 available_entry = entry;
420 if (entry_is_free(entry))
421 break;
422 }
423
424 /* Implement replacement when another insert happens
425 * with a matching key. This is a relatively common
426 * feature of hash tables, with the alternative
427 * generally being "insert the new value as well, and
428 * return it first when the key is searched for".
429 *
430 * Note that the hash table doesn't have a delete
431 * callback. If freeing of old data pointers is
432 * required to avoid memory leaks, perform a search
433 * before inserting.
434 */
435 if (!entry_is_deleted(ht, entry) &&
436 entry->hash == hash &&
437 ht->key_equals_function(key, entry->key)) {
438 entry->key = key;
439 entry->data = data;
440 return entry;
441 }
442
443 hash_address += double_hash;
444 if (hash_address >= size)
445 hash_address -= size;
446 } while (hash_address != start_hash_address);
447
448 if (available_entry) {
449 if (entry_is_deleted(ht, available_entry))
450 ht->deleted_entries--;
451 available_entry->hash = hash;
452 available_entry->key = key;
453 available_entry->data = data;
454 ht->entries++;
455 return available_entry;
456 }
457
458 /* We could hit here if a required resize failed. An unchecked-malloc
459 * application could ignore this result.
460 */
461 return NULL;
462 }
463
464 /**
465 * Inserts the key with the given hash into the table.
466 *
467 * Note that insertion may rearrange the table on a resize or rehash,
468 * so previously found hash_entries are no longer valid after this function.
469 */
470 struct hash_entry *
471 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
472 {
473 assert(ht->key_hash_function);
474 return hash_table_insert(ht, ht->key_hash_function(key), key, data);
475 }
476
477 struct hash_entry *
478 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
479 const void *key, void *data)
480 {
481 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
482 return hash_table_insert(ht, hash, key, data);
483 }
484
485 /**
486 * This function deletes the given hash table entry.
487 *
488 * Note that deletion doesn't otherwise modify the table, so an iteration over
489 * the table deleting entries is safe.
490 */
491 void
492 _mesa_hash_table_remove(struct hash_table *ht,
493 struct hash_entry *entry)
494 {
495 if (!entry)
496 return;
497
498 entry->key = ht->deleted_key;
499 ht->entries--;
500 ht->deleted_entries++;
501 }
502
503 /**
504 * Removes the entry with the corresponding key, if exists.
505 */
506 void _mesa_hash_table_remove_key(struct hash_table *ht,
507 const void *key)
508 {
509 _mesa_hash_table_remove(ht, _mesa_hash_table_search(ht, key));
510 }
511
512 /**
513 * This function is an iterator over the hash table.
514 *
515 * Pass in NULL for the first entry, as in the start of a for loop. Note that
516 * an iteration over the table is O(table_size) not O(entries).
517 */
518 struct hash_entry *
519 _mesa_hash_table_next_entry(struct hash_table *ht,
520 struct hash_entry *entry)
521 {
522 if (entry == NULL)
523 entry = ht->table;
524 else
525 entry = entry + 1;
526
527 for (; entry != ht->table + ht->size; entry++) {
528 if (entry_is_present(ht, entry)) {
529 return entry;
530 }
531 }
532
533 return NULL;
534 }
535
536 /**
537 * Returns a random entry from the hash table.
538 *
539 * This may be useful in implementing random replacement (as opposed
540 * to just removing everything) in caches based on this hash table
541 * implementation. @predicate may be used to filter entries, or may
542 * be set to NULL for no filtering.
543 */
544 struct hash_entry *
545 _mesa_hash_table_random_entry(struct hash_table *ht,
546 bool (*predicate)(struct hash_entry *entry))
547 {
548 struct hash_entry *entry;
549 uint32_t i = rand() % ht->size;
550
551 if (ht->entries == 0)
552 return NULL;
553
554 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
555 if (entry_is_present(ht, entry) &&
556 (!predicate || predicate(entry))) {
557 return entry;
558 }
559 }
560
561 for (entry = ht->table; entry != ht->table + i; entry++) {
562 if (entry_is_present(ht, entry) &&
563 (!predicate || predicate(entry))) {
564 return entry;
565 }
566 }
567
568 return NULL;
569 }
570
571
572 uint32_t
573 _mesa_hash_data(const void *data, size_t size)
574 {
575 return XXH32(data, size, 0);
576 }
577
578 uint32_t
579 _mesa_hash_int(const void *key)
580 {
581 return XXH32(key, sizeof(int), 0);
582 }
583
584 uint32_t
585 _mesa_hash_uint(const void *key)
586 {
587 return XXH32(key, sizeof(unsigned), 0);
588 }
589
590 uint32_t
591 _mesa_hash_u32(const void *key)
592 {
593 return XXH32(key, 4, 0);
594 }
595
596 /** FNV-1a string hash implementation */
597 uint32_t
598 _mesa_hash_string(const void *_key)
599 {
600 uint32_t hash = 0;
601 const char *key = _key;
602 size_t len = strlen(key);
603 #if defined(_WIN64) || defined(__x86_64__)
604 hash = (uint32_t)XXH64(key, len, hash);
605 #else
606 hash = XXH32(key, len, hash);
607 #endif
608 return hash;
609 }
610
611 uint32_t
612 _mesa_hash_pointer(const void *pointer)
613 {
614 uintptr_t num = (uintptr_t) pointer;
615 return (uint32_t) ((num >> 2) ^ (num >> 6) ^ (num >> 10) ^ (num >> 14));
616 }
617
618 bool
619 _mesa_key_int_equal(const void *a, const void *b)
620 {
621 return *((const int *)a) == *((const int *)b);
622 }
623
624 bool
625 _mesa_key_uint_equal(const void *a, const void *b)
626 {
627
628 return *((const unsigned *)a) == *((const unsigned *)b);
629 }
630
631 bool
632 _mesa_key_u32_equal(const void *a, const void *b)
633 {
634 return *((const uint32_t *)a) == *((const uint32_t *)b);
635 }
636
637 /**
638 * String compare function for use as the comparison callback in
639 * _mesa_hash_table_create().
640 */
641 bool
642 _mesa_key_string_equal(const void *a, const void *b)
643 {
644 return strcmp(a, b) == 0;
645 }
646
647 bool
648 _mesa_key_pointer_equal(const void *a, const void *b)
649 {
650 return a == b;
651 }
652
653 /**
654 * Helper to create a hash table with pointer keys.
655 */
656 struct hash_table *
657 _mesa_pointer_hash_table_create(void *mem_ctx)
658 {
659 return _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
660 _mesa_key_pointer_equal);
661 }
662
663 /**
664 * Hash table wrapper which supports 64-bit keys.
665 *
666 * TODO: unify all hash table implementations.
667 */
668
669 struct hash_key_u64 {
670 uint64_t value;
671 };
672
673 static uint32_t
674 key_u64_hash(const void *key)
675 {
676 return _mesa_hash_data(key, sizeof(struct hash_key_u64));
677 }
678
679 static bool
680 key_u64_equals(const void *a, const void *b)
681 {
682 const struct hash_key_u64 *aa = a;
683 const struct hash_key_u64 *bb = b;
684
685 return aa->value == bb->value;
686 }
687
688 #define FREED_KEY_VALUE 0
689
690 struct hash_table_u64 *
691 _mesa_hash_table_u64_create(void *mem_ctx)
692 {
693 STATIC_ASSERT(FREED_KEY_VALUE != DELETED_KEY_VALUE);
694 struct hash_table_u64 *ht;
695
696 ht = CALLOC_STRUCT(hash_table_u64);
697 if (!ht)
698 return NULL;
699
700 if (sizeof(void *) == 8) {
701 ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
702 _mesa_key_pointer_equal);
703 } else {
704 ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash,
705 key_u64_equals);
706 }
707
708 if (ht->table)
709 _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE));
710
711 return ht;
712 }
713
714 void
715 _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
716 void (*delete_function)(struct hash_entry *entry))
717 {
718 if (!ht)
719 return;
720
721 if (ht->deleted_key_data) {
722 if (delete_function) {
723 struct hash_table *table = ht->table;
724 struct hash_entry entry;
725
726 /* Create a fake entry for the delete function. */
727 if (sizeof(void *) == 8) {
728 entry.hash = table->key_hash_function(table->deleted_key);
729 } else {
730 struct hash_key_u64 _key = { .value = (uintptr_t)table->deleted_key };
731 entry.hash = table->key_hash_function(&_key);
732 }
733 entry.key = table->deleted_key;
734 entry.data = ht->deleted_key_data;
735
736 delete_function(&entry);
737 }
738 ht->deleted_key_data = NULL;
739 }
740
741 if (ht->freed_key_data) {
742 if (delete_function) {
743 struct hash_table *table = ht->table;
744 struct hash_entry entry;
745
746 /* Create a fake entry for the delete function. */
747 if (sizeof(void *) == 8) {
748 entry.hash = table->key_hash_function(uint_key(FREED_KEY_VALUE));
749 } else {
750 struct hash_key_u64 _key = { .value = (uintptr_t)FREED_KEY_VALUE };
751 entry.hash = table->key_hash_function(&_key);
752 }
753 entry.key = uint_key(FREED_KEY_VALUE);
754 entry.data = ht->freed_key_data;
755
756 delete_function(&entry);
757 }
758 ht->freed_key_data = NULL;
759 }
760
761 _mesa_hash_table_clear(ht->table, delete_function);
762 }
763
764 void
765 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht,
766 void (*delete_function)(struct hash_entry *entry))
767 {
768 if (!ht)
769 return;
770
771 _mesa_hash_table_u64_clear(ht, delete_function);
772 _mesa_hash_table_destroy(ht->table, delete_function);
773 free(ht);
774 }
775
776 void
777 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
778 void *data)
779 {
780 if (key == FREED_KEY_VALUE) {
781 ht->freed_key_data = data;
782 return;
783 }
784
785 if (key == DELETED_KEY_VALUE) {
786 ht->deleted_key_data = data;
787 return;
788 }
789
790 if (sizeof(void *) == 8) {
791 _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
792 } else {
793 struct hash_key_u64 *_key = CALLOC_STRUCT(hash_key_u64);
794
795 if (!_key)
796 return;
797 _key->value = key;
798
799 _mesa_hash_table_insert(ht->table, _key, data);
800 }
801 }
802
803 static struct hash_entry *
804 hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
805 {
806 if (sizeof(void *) == 8) {
807 return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
808 } else {
809 struct hash_key_u64 _key = { .value = key };
810 return _mesa_hash_table_search(ht->table, &_key);
811 }
812 }
813
814 void *
815 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
816 {
817 struct hash_entry *entry;
818
819 if (key == FREED_KEY_VALUE)
820 return ht->freed_key_data;
821
822 if (key == DELETED_KEY_VALUE)
823 return ht->deleted_key_data;
824
825 entry = hash_table_u64_search(ht, key);
826 if (!entry)
827 return NULL;
828
829 return entry->data;
830 }
831
832 void
833 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key)
834 {
835 struct hash_entry *entry;
836
837 if (key == FREED_KEY_VALUE) {
838 ht->freed_key_data = NULL;
839 return;
840 }
841
842 if (key == DELETED_KEY_VALUE) {
843 ht->deleted_key_data = NULL;
844 return;
845 }
846
847 entry = hash_table_u64_search(ht, key);
848 if (!entry)
849 return;
850
851 if (sizeof(void *) == 8) {
852 _mesa_hash_table_remove(ht->table, entry);
853 } else {
854 struct hash_key *_key = (struct hash_key *)entry->key;
855
856 _mesa_hash_table_remove(ht->table, entry);
857 free(_key);
858 }
859 }