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"
50 #include "main/hash.h"
51 #include "fast_urem_by_const.h"
53 #define XXH_INLINE_ALL
56 static const uint32_t deleted_key_value
;
59 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
60 * p and p-2 are both prime. These tables are sized to have an extra 10%
61 * free to avoid exponential performance degradation as the hash table fills
64 uint32_t max_entries
, size
, rehash
;
65 uint64_t size_magic
, rehash_magic
;
67 #define ENTRY(max_entries, size, rehash) \
68 { max_entries, size, rehash, \
69 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
77 ENTRY(128, 151, 149 ),
78 ENTRY(256, 283, 281 ),
79 ENTRY(512, 571, 569 ),
80 ENTRY(1024, 1153, 1151 ),
81 ENTRY(2048, 2269, 2267 ),
82 ENTRY(4096, 4519, 4517 ),
83 ENTRY(8192, 9013, 9011 ),
84 ENTRY(16384, 18043, 18041 ),
85 ENTRY(32768, 36109, 36107 ),
86 ENTRY(65536, 72091, 72089 ),
87 ENTRY(131072, 144409, 144407 ),
88 ENTRY(262144, 288361, 288359 ),
89 ENTRY(524288, 576883, 576881 ),
90 ENTRY(1048576, 1153459, 1153457 ),
91 ENTRY(2097152, 2307163, 2307161 ),
92 ENTRY(4194304, 4613893, 4613891 ),
93 ENTRY(8388608, 9227641, 9227639 ),
94 ENTRY(16777216, 18455029, 18455027 ),
95 ENTRY(33554432, 36911011, 36911009 ),
96 ENTRY(67108864, 73819861, 73819859 ),
97 ENTRY(134217728, 147639589, 147639587 ),
98 ENTRY(268435456, 295279081, 295279079 ),
99 ENTRY(536870912, 590559793, 590559791 ),
100 ENTRY(1073741824, 1181116273, 1181116271 ),
101 ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
105 key_pointer_is_reserved(const struct hash_table
*ht
, const void *key
)
107 return key
== NULL
|| key
== ht
->deleted_key
;
111 entry_is_free(const struct hash_entry
*entry
)
113 return entry
->key
== NULL
;
117 entry_is_deleted(const struct hash_table
*ht
, struct hash_entry
*entry
)
119 return entry
->key
== ht
->deleted_key
;
123 entry_is_present(const struct hash_table
*ht
, struct hash_entry
*entry
)
125 return entry
->key
!= NULL
&& entry
->key
!= ht
->deleted_key
;
129 _mesa_hash_table_init(struct hash_table
*ht
,
131 uint32_t (*key_hash_function
)(const void *key
),
132 bool (*key_equals_function
)(const void *a
,
136 ht
->size
= hash_sizes
[ht
->size_index
].size
;
137 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
138 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
139 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
140 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
141 ht
->key_hash_function
= key_hash_function
;
142 ht
->key_equals_function
= key_equals_function
;
143 ht
->table
= rzalloc_array(mem_ctx
, struct hash_entry
, ht
->size
);
145 ht
->deleted_entries
= 0;
146 ht
->deleted_key
= &deleted_key_value
;
148 return ht
->table
!= NULL
;
152 _mesa_hash_table_create(void *mem_ctx
,
153 uint32_t (*key_hash_function
)(const void *key
),
154 bool (*key_equals_function
)(const void *a
,
157 struct hash_table
*ht
;
159 /* mem_ctx is used to allocate the hash table, but the hash table is used
160 * to allocate all of the suballocations.
162 ht
= ralloc(mem_ctx
, struct hash_table
);
166 if (!_mesa_hash_table_init(ht
, ht
, key_hash_function
, key_equals_function
)) {
175 _mesa_hash_table_clone(struct hash_table
*src
, void *dst_mem_ctx
)
177 struct hash_table
*ht
;
179 ht
= ralloc(dst_mem_ctx
, struct hash_table
);
183 memcpy(ht
, src
, sizeof(struct hash_table
));
185 ht
->table
= ralloc_array(ht
, struct hash_entry
, ht
->size
);
186 if (ht
->table
== NULL
) {
191 memcpy(ht
->table
, src
->table
, ht
->size
* sizeof(struct hash_entry
));
197 * Frees the given hash table.
199 * If delete_function is passed, it gets called on each entry present before
203 _mesa_hash_table_destroy(struct hash_table
*ht
,
204 void (*delete_function
)(struct hash_entry
*entry
))
209 if (delete_function
) {
210 hash_table_foreach(ht
, entry
) {
211 delete_function(entry
);
218 * Deletes all entries of the given hash table without deleting the table
219 * itself or changing its structure.
221 * If delete_function is passed, it gets called on each entry present.
224 _mesa_hash_table_clear(struct hash_table
*ht
,
225 void (*delete_function
)(struct hash_entry
*entry
))
227 struct hash_entry
*entry
;
229 for (entry
= ht
->table
; entry
!= ht
->table
+ ht
->size
; entry
++) {
230 if (entry
->key
== NULL
)
233 if (delete_function
!= NULL
&& entry
->key
!= ht
->deleted_key
)
234 delete_function(entry
);
240 ht
->deleted_entries
= 0;
243 /** Sets the value of the key pointer used for deleted entries in the table.
245 * The assumption is that usually keys are actual pointers, so we use a
246 * default value of a pointer to an arbitrary piece of storage in the library.
247 * But in some cases a consumer wants to store some other sort of value in the
248 * table, like a uint32_t, in which case that pointer may conflict with one of
249 * their valid keys. This lets that user select a safe value.
251 * This must be called before any keys are actually deleted from the table.
254 _mesa_hash_table_set_deleted_key(struct hash_table
*ht
, const void *deleted_key
)
256 ht
->deleted_key
= deleted_key
;
259 static struct hash_entry
*
260 hash_table_search(struct hash_table
*ht
, uint32_t hash
, const void *key
)
262 assert(!key_pointer_is_reserved(ht
, key
));
264 uint32_t size
= ht
->size
;
265 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
266 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
268 uint32_t hash_address
= start_hash_address
;
271 struct hash_entry
*entry
= ht
->table
+ hash_address
;
273 if (entry_is_free(entry
)) {
275 } else if (entry_is_present(ht
, entry
) && entry
->hash
== hash
) {
276 if (ht
->key_equals_function(key
, entry
->key
)) {
281 hash_address
+= double_hash
;
282 if (hash_address
>= size
)
283 hash_address
-= size
;
284 } while (hash_address
!= start_hash_address
);
290 * Finds a hash table entry with the given key and hash of that key.
292 * Returns NULL if no entry is found. Note that the data pointer may be
293 * modified by the user.
296 _mesa_hash_table_search(struct hash_table
*ht
, const void *key
)
298 assert(ht
->key_hash_function
);
299 return hash_table_search(ht
, ht
->key_hash_function(key
), key
);
303 _mesa_hash_table_search_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
306 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
307 return hash_table_search(ht
, hash
, key
);
310 static struct hash_entry
*
311 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
312 const void *key
, void *data
);
315 hash_table_insert_rehash(struct hash_table
*ht
, uint32_t hash
,
316 const void *key
, void *data
)
318 uint32_t size
= ht
->size
;
319 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
320 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
322 uint32_t hash_address
= start_hash_address
;
324 struct hash_entry
*entry
= ht
->table
+ hash_address
;
326 if (likely(entry
->key
== NULL
)) {
333 hash_address
+= double_hash
;
334 if (hash_address
>= size
)
335 hash_address
-= size
;
340 _mesa_hash_table_rehash(struct hash_table
*ht
, unsigned new_size_index
)
342 struct hash_table old_ht
;
343 struct hash_entry
*table
;
345 if (new_size_index
>= ARRAY_SIZE(hash_sizes
))
348 table
= rzalloc_array(ralloc_parent(ht
->table
), struct hash_entry
,
349 hash_sizes
[new_size_index
].size
);
356 ht
->size_index
= new_size_index
;
357 ht
->size
= hash_sizes
[ht
->size_index
].size
;
358 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
359 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
360 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
361 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
363 ht
->deleted_entries
= 0;
365 hash_table_foreach(&old_ht
, entry
) {
366 hash_table_insert_rehash(ht
, entry
->hash
, entry
->key
, entry
->data
);
369 ht
->entries
= old_ht
.entries
;
371 ralloc_free(old_ht
.table
);
374 static struct hash_entry
*
375 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
376 const void *key
, void *data
)
378 struct hash_entry
*available_entry
= NULL
;
380 assert(!key_pointer_is_reserved(ht
, key
));
382 if (ht
->entries
>= ht
->max_entries
) {
383 _mesa_hash_table_rehash(ht
, ht
->size_index
+ 1);
384 } else if (ht
->deleted_entries
+ ht
->entries
>= ht
->max_entries
) {
385 _mesa_hash_table_rehash(ht
, ht
->size_index
);
388 uint32_t size
= ht
->size
;
389 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
390 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
392 uint32_t hash_address
= start_hash_address
;
394 struct hash_entry
*entry
= ht
->table
+ hash_address
;
396 if (!entry_is_present(ht
, entry
)) {
397 /* Stash the first available entry we find */
398 if (available_entry
== NULL
)
399 available_entry
= entry
;
400 if (entry_is_free(entry
))
404 /* Implement replacement when another insert happens
405 * with a matching key. This is a relatively common
406 * feature of hash tables, with the alternative
407 * generally being "insert the new value as well, and
408 * return it first when the key is searched for".
410 * Note that the hash table doesn't have a delete
411 * callback. If freeing of old data pointers is
412 * required to avoid memory leaks, perform a search
415 if (!entry_is_deleted(ht
, entry
) &&
416 entry
->hash
== hash
&&
417 ht
->key_equals_function(key
, entry
->key
)) {
423 hash_address
+= double_hash
;
424 if (hash_address
>= size
)
425 hash_address
-= size
;
426 } while (hash_address
!= start_hash_address
);
428 if (available_entry
) {
429 if (entry_is_deleted(ht
, available_entry
))
430 ht
->deleted_entries
--;
431 available_entry
->hash
= hash
;
432 available_entry
->key
= key
;
433 available_entry
->data
= data
;
435 return available_entry
;
438 /* We could hit here if a required resize failed. An unchecked-malloc
439 * application could ignore this result.
445 * Inserts the key with the given hash into the table.
447 * Note that insertion may rearrange the table on a resize or rehash,
448 * so previously found hash_entries are no longer valid after this function.
451 _mesa_hash_table_insert(struct hash_table
*ht
, const void *key
, void *data
)
453 assert(ht
->key_hash_function
);
454 return hash_table_insert(ht
, ht
->key_hash_function(key
), key
, data
);
458 _mesa_hash_table_insert_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
459 const void *key
, void *data
)
461 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
462 return hash_table_insert(ht
, hash
, key
, data
);
466 * This function deletes the given hash table entry.
468 * Note that deletion doesn't otherwise modify the table, so an iteration over
469 * the table deleting entries is safe.
472 _mesa_hash_table_remove(struct hash_table
*ht
,
473 struct hash_entry
*entry
)
478 entry
->key
= ht
->deleted_key
;
480 ht
->deleted_entries
++;
484 * Removes the entry with the corresponding key, if exists.
486 void _mesa_hash_table_remove_key(struct hash_table
*ht
,
489 _mesa_hash_table_remove(ht
, _mesa_hash_table_search(ht
, key
));
493 * This function is an iterator over the hash table.
495 * Pass in NULL for the first entry, as in the start of a for loop. Note that
496 * an iteration over the table is O(table_size) not O(entries).
499 _mesa_hash_table_next_entry(struct hash_table
*ht
,
500 struct hash_entry
*entry
)
507 for (; entry
!= ht
->table
+ ht
->size
; entry
++) {
508 if (entry_is_present(ht
, entry
)) {
517 * Returns a random entry from the hash table.
519 * This may be useful in implementing random replacement (as opposed
520 * to just removing everything) in caches based on this hash table
521 * implementation. @predicate may be used to filter entries, or may
522 * be set to NULL for no filtering.
525 _mesa_hash_table_random_entry(struct hash_table
*ht
,
526 bool (*predicate
)(struct hash_entry
*entry
))
528 struct hash_entry
*entry
;
529 uint32_t i
= rand() % ht
->size
;
531 if (ht
->entries
== 0)
534 for (entry
= ht
->table
+ i
; entry
!= ht
->table
+ ht
->size
; entry
++) {
535 if (entry_is_present(ht
, entry
) &&
536 (!predicate
|| predicate(entry
))) {
541 for (entry
= ht
->table
; entry
!= ht
->table
+ i
; entry
++) {
542 if (entry_is_present(ht
, entry
) &&
543 (!predicate
|| predicate(entry
))) {
553 _mesa_hash_data(const void *data
, size_t size
)
555 return XXH32(data
, size
, 0);
559 _mesa_hash_int(const void *key
)
561 return XXH32(key
, sizeof(int), 0);
565 _mesa_hash_uint(const void *key
)
567 return XXH32(key
, sizeof(unsigned), 0);
571 _mesa_hash_u32(const void *key
)
573 return XXH32(key
, 4, 0);
576 /** FNV-1a string hash implementation */
578 _mesa_hash_string(const void *_key
)
580 uint32_t hash
= _mesa_fnv32_1a_offset_bias
;
581 const char *key
= _key
;
584 hash
= _mesa_fnv32_1a_accumulate(hash
, *key
);
592 _mesa_hash_pointer(const void *pointer
)
594 uintptr_t num
= (uintptr_t) pointer
;
595 return (uint32_t) ((num
>> 2) ^ (num
>> 6) ^ (num
>> 10) ^ (num
>> 14));
599 _mesa_key_int_equal(const void *a
, const void *b
)
601 return *((const int *)a
) == *((const int *)b
);
605 _mesa_key_uint_equal(const void *a
, const void *b
)
608 return *((const unsigned *)a
) == *((const unsigned *)b
);
612 _mesa_key_u32_equal(const void *a
, const void *b
)
614 return *((const uint32_t *)a
) == *((const uint32_t *)b
);
618 * String compare function for use as the comparison callback in
619 * _mesa_hash_table_create().
622 _mesa_key_string_equal(const void *a
, const void *b
)
624 return strcmp(a
, b
) == 0;
628 _mesa_key_pointer_equal(const void *a
, const void *b
)
634 * Helper to create a hash table with pointer keys.
637 _mesa_pointer_hash_table_create(void *mem_ctx
)
639 return _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
640 _mesa_key_pointer_equal
);
644 * Hash table wrapper which supports 64-bit keys.
646 * TODO: unify all hash table implementations.
649 struct hash_key_u64
{
654 key_u64_hash(const void *key
)
656 return _mesa_hash_data(key
, sizeof(struct hash_key_u64
));
660 key_u64_equals(const void *a
, const void *b
)
662 const struct hash_key_u64
*aa
= a
;
663 const struct hash_key_u64
*bb
= b
;
665 return aa
->value
== bb
->value
;
668 #define FREED_KEY_VALUE 0
670 struct hash_table_u64
*
671 _mesa_hash_table_u64_create(void *mem_ctx
)
673 STATIC_ASSERT(FREED_KEY_VALUE
!= DELETED_KEY_VALUE
);
674 struct hash_table_u64
*ht
;
676 ht
= CALLOC_STRUCT(hash_table_u64
);
680 if (sizeof(void *) == 8) {
681 ht
->table
= _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
682 _mesa_key_pointer_equal
);
684 ht
->table
= _mesa_hash_table_create(mem_ctx
, key_u64_hash
,
689 _mesa_hash_table_set_deleted_key(ht
->table
, uint_key(DELETED_KEY_VALUE
));
695 _mesa_hash_table_u64_clear(struct hash_table_u64
*ht
,
696 void (*delete_function
)(struct hash_entry
*entry
))
701 if (ht
->deleted_key_data
) {
702 if (delete_function
) {
703 struct hash_table
*table
= ht
->table
;
704 struct hash_entry entry
;
706 /* Create a fake entry for the delete function. */
707 if (sizeof(void *) == 8) {
708 entry
.hash
= table
->key_hash_function(table
->deleted_key
);
710 struct hash_key_u64 _key
= { .value
= (uintptr_t)table
->deleted_key
};
711 entry
.hash
= table
->key_hash_function(&_key
);
713 entry
.key
= table
->deleted_key
;
714 entry
.data
= ht
->deleted_key_data
;
716 delete_function(&entry
);
718 ht
->deleted_key_data
= NULL
;
721 if (ht
->freed_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(uint_key(FREED_KEY_VALUE
));
730 struct hash_key_u64 _key
= { .value
= (uintptr_t)FREED_KEY_VALUE
};
731 entry
.hash
= table
->key_hash_function(&_key
);
733 entry
.key
= uint_key(FREED_KEY_VALUE
);
734 entry
.data
= ht
->freed_key_data
;
736 delete_function(&entry
);
738 ht
->freed_key_data
= NULL
;
741 _mesa_hash_table_clear(ht
->table
, delete_function
);
745 _mesa_hash_table_u64_destroy(struct hash_table_u64
*ht
,
746 void (*delete_function
)(struct hash_entry
*entry
))
751 _mesa_hash_table_u64_clear(ht
, delete_function
);
752 _mesa_hash_table_destroy(ht
->table
, delete_function
);
757 _mesa_hash_table_u64_insert(struct hash_table_u64
*ht
, uint64_t key
,
760 if (key
== FREED_KEY_VALUE
) {
761 ht
->freed_key_data
= data
;
765 if (key
== DELETED_KEY_VALUE
) {
766 ht
->deleted_key_data
= data
;
770 if (sizeof(void *) == 8) {
771 _mesa_hash_table_insert(ht
->table
, (void *)(uintptr_t)key
, data
);
773 struct hash_key_u64
*_key
= CALLOC_STRUCT(hash_key_u64
);
779 _mesa_hash_table_insert(ht
->table
, _key
, data
);
783 static struct hash_entry
*
784 hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
786 if (sizeof(void *) == 8) {
787 return _mesa_hash_table_search(ht
->table
, (void *)(uintptr_t)key
);
789 struct hash_key_u64 _key
= { .value
= key
};
790 return _mesa_hash_table_search(ht
->table
, &_key
);
795 _mesa_hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
797 struct hash_entry
*entry
;
799 if (key
== FREED_KEY_VALUE
)
800 return ht
->freed_key_data
;
802 if (key
== DELETED_KEY_VALUE
)
803 return ht
->deleted_key_data
;
805 entry
= hash_table_u64_search(ht
, key
);
813 _mesa_hash_table_u64_remove(struct hash_table_u64
*ht
, uint64_t key
)
815 struct hash_entry
*entry
;
817 if (key
== FREED_KEY_VALUE
) {
818 ht
->freed_key_data
= NULL
;
822 if (key
== DELETED_KEY_VALUE
) {
823 ht
->deleted_key_data
= NULL
;
827 entry
= hash_table_u64_search(ht
, key
);
831 if (sizeof(void *) == 8) {
832 _mesa_hash_table_remove(ht
->table
, entry
);
834 struct hash_key
*_key
= (struct hash_key
*)entry
->key
;
836 _mesa_hash_table_remove(ht
->table
, entry
);