2 * Copyright © 2009,2012 Intel Corporation
3 * Copyright © 1988-2004 Keith Packard and Bart Massey.
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:
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
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
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
31 * Eric Anholt <eric@anholt.net>
32 * Keith Packard <keithp@keithp.com>
36 * Implements an open-addressing, linear-reprobing hash table.
38 * For more information, see:
40 * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
47 #include "hash_table.h"
51 #include "fast_urem_by_const.h"
52 #include "util/u_memory.h"
54 #define XXH_INLINE_ALL
58 * Magic number that gets stored outside of the struct hash_table.
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.
68 #define DELETED_KEY_VALUE 1
73 return (void *)(uintptr_t) id
;
76 static const uint32_t deleted_key_value
;
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
84 uint32_t max_entries
, size
, rehash
;
85 uint64_t size_magic
, rehash_magic
;
87 #define ENTRY(max_entries, size, rehash) \
88 { max_entries, size, rehash, \
89 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
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 )
124 ASSERTED
static inline bool
125 key_pointer_is_reserved(const struct hash_table
*ht
, const void *key
)
127 return key
== NULL
|| key
== ht
->deleted_key
;
131 entry_is_free(const struct hash_entry
*entry
)
133 return entry
->key
== NULL
;
137 entry_is_deleted(const struct hash_table
*ht
, struct hash_entry
*entry
)
139 return entry
->key
== ht
->deleted_key
;
143 entry_is_present(const struct hash_table
*ht
, struct hash_entry
*entry
)
145 return entry
->key
!= NULL
&& entry
->key
!= ht
->deleted_key
;
149 _mesa_hash_table_init(struct hash_table
*ht
,
151 uint32_t (*key_hash_function
)(const void *key
),
152 bool (*key_equals_function
)(const void *a
,
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
);
165 ht
->deleted_entries
= 0;
166 ht
->deleted_key
= &deleted_key_value
;
168 return ht
->table
!= NULL
;
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
,
177 struct hash_table
*ht
;
179 /* mem_ctx is used to allocate the hash table, but the hash table is used
180 * to allocate all of the suballocations.
182 ht
= ralloc(mem_ctx
, struct hash_table
);
186 if (!_mesa_hash_table_init(ht
, ht
, key_hash_function
, key_equals_function
)) {
195 _mesa_hash_table_clone(struct hash_table
*src
, void *dst_mem_ctx
)
197 struct hash_table
*ht
;
199 ht
= ralloc(dst_mem_ctx
, struct hash_table
);
203 memcpy(ht
, src
, sizeof(struct hash_table
));
205 ht
->table
= ralloc_array(ht
, struct hash_entry
, ht
->size
);
206 if (ht
->table
== NULL
) {
211 memcpy(ht
->table
, src
->table
, ht
->size
* sizeof(struct hash_entry
));
217 * Frees the given hash table.
219 * If delete_function is passed, it gets called on each entry present before
223 _mesa_hash_table_destroy(struct hash_table
*ht
,
224 void (*delete_function
)(struct hash_entry
*entry
))
229 if (delete_function
) {
230 hash_table_foreach(ht
, entry
) {
231 delete_function(entry
);
238 * Deletes all entries of the given hash table without deleting the table
239 * itself or changing its structure.
241 * If delete_function is passed, it gets called on each entry present.
244 _mesa_hash_table_clear(struct hash_table
*ht
,
245 void (*delete_function
)(struct hash_entry
*entry
))
247 struct hash_entry
*entry
;
249 for (entry
= ht
->table
; entry
!= ht
->table
+ ht
->size
; entry
++) {
250 if (entry
->key
== NULL
)
253 if (delete_function
!= NULL
&& entry
->key
!= ht
->deleted_key
)
254 delete_function(entry
);
260 ht
->deleted_entries
= 0;
263 /** Sets the value of the key pointer used for deleted entries in the table.
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.
271 * This must be called before any keys are actually deleted from the table.
274 _mesa_hash_table_set_deleted_key(struct hash_table
*ht
, const void *deleted_key
)
276 ht
->deleted_key
= deleted_key
;
279 static struct hash_entry
*
280 hash_table_search(struct hash_table
*ht
, uint32_t hash
, const void *key
)
282 assert(!key_pointer_is_reserved(ht
, key
));
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
,
288 uint32_t hash_address
= start_hash_address
;
291 struct hash_entry
*entry
= ht
->table
+ hash_address
;
293 if (entry_is_free(entry
)) {
295 } else if (entry_is_present(ht
, entry
) && entry
->hash
== hash
) {
296 if (ht
->key_equals_function(key
, entry
->key
)) {
301 hash_address
+= double_hash
;
302 if (hash_address
>= size
)
303 hash_address
-= size
;
304 } while (hash_address
!= start_hash_address
);
310 * Finds a hash table entry with the given key and hash of that key.
312 * Returns NULL if no entry is found. Note that the data pointer may be
313 * modified by the user.
316 _mesa_hash_table_search(struct hash_table
*ht
, const void *key
)
318 assert(ht
->key_hash_function
);
319 return hash_table_search(ht
, ht
->key_hash_function(key
), key
);
323 _mesa_hash_table_search_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
326 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
327 return hash_table_search(ht
, hash
, key
);
330 static struct hash_entry
*
331 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
332 const void *key
, void *data
);
335 hash_table_insert_rehash(struct hash_table
*ht
, uint32_t hash
,
336 const void *key
, void *data
)
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
,
342 uint32_t hash_address
= start_hash_address
;
344 struct hash_entry
*entry
= ht
->table
+ hash_address
;
346 if (likely(entry
->key
== NULL
)) {
353 hash_address
+= double_hash
;
354 if (hash_address
>= size
)
355 hash_address
-= size
;
360 _mesa_hash_table_rehash(struct hash_table
*ht
, unsigned new_size_index
)
362 struct hash_table old_ht
;
363 struct hash_entry
*table
;
365 if (new_size_index
>= ARRAY_SIZE(hash_sizes
))
368 table
= rzalloc_array(ralloc_parent(ht
->table
), struct hash_entry
,
369 hash_sizes
[new_size_index
].size
);
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
;
383 ht
->deleted_entries
= 0;
385 hash_table_foreach(&old_ht
, entry
) {
386 hash_table_insert_rehash(ht
, entry
->hash
, entry
->key
, entry
->data
);
389 ht
->entries
= old_ht
.entries
;
391 ralloc_free(old_ht
.table
);
394 static struct hash_entry
*
395 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
396 const void *key
, void *data
)
398 struct hash_entry
*available_entry
= NULL
;
400 assert(!key_pointer_is_reserved(ht
, key
));
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
);
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
,
412 uint32_t hash_address
= start_hash_address
;
414 struct hash_entry
*entry
= ht
->table
+ hash_address
;
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
))
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".
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
435 if (!entry_is_deleted(ht
, entry
) &&
436 entry
->hash
== hash
&&
437 ht
->key_equals_function(key
, entry
->key
)) {
443 hash_address
+= double_hash
;
444 if (hash_address
>= size
)
445 hash_address
-= size
;
446 } while (hash_address
!= start_hash_address
);
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
;
455 return available_entry
;
458 /* We could hit here if a required resize failed. An unchecked-malloc
459 * application could ignore this result.
465 * Inserts the key with the given hash into the table.
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.
471 _mesa_hash_table_insert(struct hash_table
*ht
, const void *key
, void *data
)
473 assert(ht
->key_hash_function
);
474 return hash_table_insert(ht
, ht
->key_hash_function(key
), key
, data
);
478 _mesa_hash_table_insert_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
479 const void *key
, void *data
)
481 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
482 return hash_table_insert(ht
, hash
, key
, data
);
486 * This function deletes the given hash table entry.
488 * Note that deletion doesn't otherwise modify the table, so an iteration over
489 * the table deleting entries is safe.
492 _mesa_hash_table_remove(struct hash_table
*ht
,
493 struct hash_entry
*entry
)
498 entry
->key
= ht
->deleted_key
;
500 ht
->deleted_entries
++;
504 * Removes the entry with the corresponding key, if exists.
506 void _mesa_hash_table_remove_key(struct hash_table
*ht
,
509 _mesa_hash_table_remove(ht
, _mesa_hash_table_search(ht
, key
));
513 * This function is an iterator over the hash table.
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).
519 _mesa_hash_table_next_entry(struct hash_table
*ht
,
520 struct hash_entry
*entry
)
527 for (; entry
!= ht
->table
+ ht
->size
; entry
++) {
528 if (entry_is_present(ht
, entry
)) {
537 * Returns a random entry from the hash table.
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.
545 _mesa_hash_table_random_entry(struct hash_table
*ht
,
546 bool (*predicate
)(struct hash_entry
*entry
))
548 struct hash_entry
*entry
;
549 uint32_t i
= rand() % ht
->size
;
551 if (ht
->entries
== 0)
554 for (entry
= ht
->table
+ i
; entry
!= ht
->table
+ ht
->size
; entry
++) {
555 if (entry_is_present(ht
, entry
) &&
556 (!predicate
|| predicate(entry
))) {
561 for (entry
= ht
->table
; entry
!= ht
->table
+ i
; entry
++) {
562 if (entry_is_present(ht
, entry
) &&
563 (!predicate
|| predicate(entry
))) {
573 _mesa_hash_data(const void *data
, size_t size
)
575 return XXH32(data
, size
, 0);
579 _mesa_hash_int(const void *key
)
581 return XXH32(key
, sizeof(int), 0);
585 _mesa_hash_uint(const void *key
)
587 return XXH32(key
, sizeof(unsigned), 0);
591 _mesa_hash_u32(const void *key
)
593 return XXH32(key
, 4, 0);
596 /** FNV-1a string hash implementation */
598 _mesa_hash_string(const void *_key
)
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
);
606 hash
= XXH32(key
, len
, hash
);
612 _mesa_hash_pointer(const void *pointer
)
614 uintptr_t num
= (uintptr_t) pointer
;
615 return (uint32_t) ((num
>> 2) ^ (num
>> 6) ^ (num
>> 10) ^ (num
>> 14));
619 _mesa_key_int_equal(const void *a
, const void *b
)
621 return *((const int *)a
) == *((const int *)b
);
625 _mesa_key_uint_equal(const void *a
, const void *b
)
628 return *((const unsigned *)a
) == *((const unsigned *)b
);
632 _mesa_key_u32_equal(const void *a
, const void *b
)
634 return *((const uint32_t *)a
) == *((const uint32_t *)b
);
638 * String compare function for use as the comparison callback in
639 * _mesa_hash_table_create().
642 _mesa_key_string_equal(const void *a
, const void *b
)
644 return strcmp(a
, b
) == 0;
648 _mesa_key_pointer_equal(const void *a
, const void *b
)
654 * Helper to create a hash table with pointer keys.
657 _mesa_pointer_hash_table_create(void *mem_ctx
)
659 return _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
660 _mesa_key_pointer_equal
);
664 * Hash table wrapper which supports 64-bit keys.
666 * TODO: unify all hash table implementations.
669 struct hash_key_u64
{
674 key_u64_hash(const void *key
)
676 return _mesa_hash_data(key
, sizeof(struct hash_key_u64
));
680 key_u64_equals(const void *a
, const void *b
)
682 const struct hash_key_u64
*aa
= a
;
683 const struct hash_key_u64
*bb
= b
;
685 return aa
->value
== bb
->value
;
688 #define FREED_KEY_VALUE 0
690 struct hash_table_u64
*
691 _mesa_hash_table_u64_create(void *mem_ctx
)
693 STATIC_ASSERT(FREED_KEY_VALUE
!= DELETED_KEY_VALUE
);
694 struct hash_table_u64
*ht
;
696 ht
= CALLOC_STRUCT(hash_table_u64
);
700 if (sizeof(void *) == 8) {
701 ht
->table
= _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
702 _mesa_key_pointer_equal
);
704 ht
->table
= _mesa_hash_table_create(mem_ctx
, key_u64_hash
,
709 _mesa_hash_table_set_deleted_key(ht
->table
, uint_key(DELETED_KEY_VALUE
));
715 _mesa_hash_table_u64_clear(struct hash_table_u64
*ht
,
716 void (*delete_function
)(struct hash_entry
*entry
))
721 if (ht
->deleted_key_data
) {
722 if (delete_function
) {
723 struct hash_table
*table
= ht
->table
;
724 struct hash_entry entry
;
726 /* Create a fake entry for the delete function. */
727 if (sizeof(void *) == 8) {
728 entry
.hash
= table
->key_hash_function(table
->deleted_key
);
730 struct hash_key_u64 _key
= { .value
= (uintptr_t)table
->deleted_key
};
731 entry
.hash
= table
->key_hash_function(&_key
);
733 entry
.key
= table
->deleted_key
;
734 entry
.data
= ht
->deleted_key_data
;
736 delete_function(&entry
);
738 ht
->deleted_key_data
= NULL
;
741 if (ht
->freed_key_data
) {
742 if (delete_function
) {
743 struct hash_table
*table
= ht
->table
;
744 struct hash_entry entry
;
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
));
750 struct hash_key_u64 _key
= { .value
= (uintptr_t)FREED_KEY_VALUE
};
751 entry
.hash
= table
->key_hash_function(&_key
);
753 entry
.key
= uint_key(FREED_KEY_VALUE
);
754 entry
.data
= ht
->freed_key_data
;
756 delete_function(&entry
);
758 ht
->freed_key_data
= NULL
;
761 _mesa_hash_table_clear(ht
->table
, delete_function
);
765 _mesa_hash_table_u64_destroy(struct hash_table_u64
*ht
,
766 void (*delete_function
)(struct hash_entry
*entry
))
771 _mesa_hash_table_u64_clear(ht
, delete_function
);
772 _mesa_hash_table_destroy(ht
->table
, delete_function
);
777 _mesa_hash_table_u64_insert(struct hash_table_u64
*ht
, uint64_t key
,
780 if (key
== FREED_KEY_VALUE
) {
781 ht
->freed_key_data
= data
;
785 if (key
== DELETED_KEY_VALUE
) {
786 ht
->deleted_key_data
= data
;
790 if (sizeof(void *) == 8) {
791 _mesa_hash_table_insert(ht
->table
, (void *)(uintptr_t)key
, data
);
793 struct hash_key_u64
*_key
= CALLOC_STRUCT(hash_key_u64
);
799 _mesa_hash_table_insert(ht
->table
, _key
, data
);
803 static struct hash_entry
*
804 hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
806 if (sizeof(void *) == 8) {
807 return _mesa_hash_table_search(ht
->table
, (void *)(uintptr_t)key
);
809 struct hash_key_u64 _key
= { .value
= key
};
810 return _mesa_hash_table_search(ht
->table
, &_key
);
815 _mesa_hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
817 struct hash_entry
*entry
;
819 if (key
== FREED_KEY_VALUE
)
820 return ht
->freed_key_data
;
822 if (key
== DELETED_KEY_VALUE
)
823 return ht
->deleted_key_data
;
825 entry
= hash_table_u64_search(ht
, key
);
833 _mesa_hash_table_u64_remove(struct hash_table_u64
*ht
, uint64_t key
)
835 struct hash_entry
*entry
;
837 if (key
== FREED_KEY_VALUE
) {
838 ht
->freed_key_data
= NULL
;
842 if (key
== DELETED_KEY_VALUE
) {
843 ht
->deleted_key_data
= NULL
;
847 entry
= hash_table_u64_search(ht
, key
);
851 if (sizeof(void *) == 8) {
852 _mesa_hash_table_remove(ht
->table
, entry
);
854 struct hash_key
*_key
= (struct hash_key
*)entry
->key
;
856 _mesa_hash_table_remove(ht
->table
, entry
);