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"
53 #define XXH_INLINE_ALL
57 * Magic number that gets stored outside of the struct hash_table.
59 * The hash table needs a particular pointer to be the marker for a key that
60 * was deleted from the table, along with NULL for the "never allocated in the
61 * table" marker. Legacy GL allows any GLuint to be used as a GL object name,
62 * and we use a 1:1 mapping from GLuints to key pointers, so we need to be
63 * able to track a GLuint that happens to match the deleted key outside of
64 * struct hash_table. We tell the hash table to use "1" as the deleted key
65 * value, so that we test the deleted-key-in-the-table path as best we can.
67 #define DELETED_KEY_VALUE 1
72 return (void *)(uintptr_t) id
;
75 static const uint32_t deleted_key_value
;
78 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
79 * p and p-2 are both prime. These tables are sized to have an extra 10%
80 * free to avoid exponential performance degradation as the hash table fills
83 uint32_t max_entries
, size
, rehash
;
84 uint64_t size_magic
, rehash_magic
;
86 #define ENTRY(max_entries, size, rehash) \
87 { max_entries, size, rehash, \
88 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
96 ENTRY(128, 151, 149 ),
97 ENTRY(256, 283, 281 ),
98 ENTRY(512, 571, 569 ),
99 ENTRY(1024, 1153, 1151 ),
100 ENTRY(2048, 2269, 2267 ),
101 ENTRY(4096, 4519, 4517 ),
102 ENTRY(8192, 9013, 9011 ),
103 ENTRY(16384, 18043, 18041 ),
104 ENTRY(32768, 36109, 36107 ),
105 ENTRY(65536, 72091, 72089 ),
106 ENTRY(131072, 144409, 144407 ),
107 ENTRY(262144, 288361, 288359 ),
108 ENTRY(524288, 576883, 576881 ),
109 ENTRY(1048576, 1153459, 1153457 ),
110 ENTRY(2097152, 2307163, 2307161 ),
111 ENTRY(4194304, 4613893, 4613891 ),
112 ENTRY(8388608, 9227641, 9227639 ),
113 ENTRY(16777216, 18455029, 18455027 ),
114 ENTRY(33554432, 36911011, 36911009 ),
115 ENTRY(67108864, 73819861, 73819859 ),
116 ENTRY(134217728, 147639589, 147639587 ),
117 ENTRY(268435456, 295279081, 295279079 ),
118 ENTRY(536870912, 590559793, 590559791 ),
119 ENTRY(1073741824, 1181116273, 1181116271 ),
120 ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
123 ASSERTED
static inline bool
124 key_pointer_is_reserved(const struct hash_table
*ht
, const void *key
)
126 return key
== NULL
|| key
== ht
->deleted_key
;
130 entry_is_free(const struct hash_entry
*entry
)
132 return entry
->key
== NULL
;
136 entry_is_deleted(const struct hash_table
*ht
, struct hash_entry
*entry
)
138 return entry
->key
== ht
->deleted_key
;
142 entry_is_present(const struct hash_table
*ht
, struct hash_entry
*entry
)
144 return entry
->key
!= NULL
&& entry
->key
!= ht
->deleted_key
;
148 _mesa_hash_table_init(struct hash_table
*ht
,
150 uint32_t (*key_hash_function
)(const void *key
),
151 bool (*key_equals_function
)(const void *a
,
155 ht
->size
= hash_sizes
[ht
->size_index
].size
;
156 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
157 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
158 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
159 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
160 ht
->key_hash_function
= key_hash_function
;
161 ht
->key_equals_function
= key_equals_function
;
162 ht
->table
= rzalloc_array(mem_ctx
, struct hash_entry
, ht
->size
);
164 ht
->deleted_entries
= 0;
165 ht
->deleted_key
= &deleted_key_value
;
167 return ht
->table
!= NULL
;
171 _mesa_hash_table_create(void *mem_ctx
,
172 uint32_t (*key_hash_function
)(const void *key
),
173 bool (*key_equals_function
)(const void *a
,
176 struct hash_table
*ht
;
178 /* mem_ctx is used to allocate the hash table, but the hash table is used
179 * to allocate all of the suballocations.
181 ht
= ralloc(mem_ctx
, struct hash_table
);
185 if (!_mesa_hash_table_init(ht
, ht
, key_hash_function
, key_equals_function
)) {
194 _mesa_hash_table_clone(struct hash_table
*src
, void *dst_mem_ctx
)
196 struct hash_table
*ht
;
198 ht
= ralloc(dst_mem_ctx
, struct hash_table
);
202 memcpy(ht
, src
, sizeof(struct hash_table
));
204 ht
->table
= ralloc_array(ht
, struct hash_entry
, ht
->size
);
205 if (ht
->table
== NULL
) {
210 memcpy(ht
->table
, src
->table
, ht
->size
* sizeof(struct hash_entry
));
216 * Frees the given hash table.
218 * If delete_function is passed, it gets called on each entry present before
222 _mesa_hash_table_destroy(struct hash_table
*ht
,
223 void (*delete_function
)(struct hash_entry
*entry
))
228 if (delete_function
) {
229 hash_table_foreach(ht
, entry
) {
230 delete_function(entry
);
237 * Deletes all entries of the given hash table without deleting the table
238 * itself or changing its structure.
240 * If delete_function is passed, it gets called on each entry present.
243 _mesa_hash_table_clear(struct hash_table
*ht
,
244 void (*delete_function
)(struct hash_entry
*entry
))
246 struct hash_entry
*entry
;
248 for (entry
= ht
->table
; entry
!= ht
->table
+ ht
->size
; entry
++) {
249 if (entry
->key
== NULL
)
252 if (delete_function
!= NULL
&& entry
->key
!= ht
->deleted_key
)
253 delete_function(entry
);
259 ht
->deleted_entries
= 0;
262 /** Sets the value of the key pointer used for deleted entries in the table.
264 * The assumption is that usually keys are actual pointers, so we use a
265 * default value of a pointer to an arbitrary piece of storage in the library.
266 * But in some cases a consumer wants to store some other sort of value in the
267 * table, like a uint32_t, in which case that pointer may conflict with one of
268 * their valid keys. This lets that user select a safe value.
270 * This must be called before any keys are actually deleted from the table.
273 _mesa_hash_table_set_deleted_key(struct hash_table
*ht
, const void *deleted_key
)
275 ht
->deleted_key
= deleted_key
;
278 static struct hash_entry
*
279 hash_table_search(struct hash_table
*ht
, uint32_t hash
, const void *key
)
281 assert(!key_pointer_is_reserved(ht
, key
));
283 uint32_t size
= ht
->size
;
284 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
285 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
287 uint32_t hash_address
= start_hash_address
;
290 struct hash_entry
*entry
= ht
->table
+ hash_address
;
292 if (entry_is_free(entry
)) {
294 } else if (entry_is_present(ht
, entry
) && entry
->hash
== hash
) {
295 if (ht
->key_equals_function(key
, entry
->key
)) {
300 hash_address
+= double_hash
;
301 if (hash_address
>= size
)
302 hash_address
-= size
;
303 } while (hash_address
!= start_hash_address
);
309 * Finds a hash table entry with the given key and hash of that key.
311 * Returns NULL if no entry is found. Note that the data pointer may be
312 * modified by the user.
315 _mesa_hash_table_search(struct hash_table
*ht
, const void *key
)
317 assert(ht
->key_hash_function
);
318 return hash_table_search(ht
, ht
->key_hash_function(key
), key
);
322 _mesa_hash_table_search_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
325 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
326 return hash_table_search(ht
, hash
, key
);
329 static struct hash_entry
*
330 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
331 const void *key
, void *data
);
334 hash_table_insert_rehash(struct hash_table
*ht
, uint32_t hash
,
335 const void *key
, void *data
)
337 uint32_t size
= ht
->size
;
338 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
339 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
341 uint32_t hash_address
= start_hash_address
;
343 struct hash_entry
*entry
= ht
->table
+ hash_address
;
345 if (likely(entry
->key
== NULL
)) {
352 hash_address
+= double_hash
;
353 if (hash_address
>= size
)
354 hash_address
-= size
;
359 _mesa_hash_table_rehash(struct hash_table
*ht
, unsigned new_size_index
)
361 struct hash_table old_ht
;
362 struct hash_entry
*table
;
364 if (new_size_index
>= ARRAY_SIZE(hash_sizes
))
367 table
= rzalloc_array(ralloc_parent(ht
->table
), struct hash_entry
,
368 hash_sizes
[new_size_index
].size
);
375 ht
->size_index
= new_size_index
;
376 ht
->size
= hash_sizes
[ht
->size_index
].size
;
377 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
378 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
379 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
380 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
382 ht
->deleted_entries
= 0;
384 hash_table_foreach(&old_ht
, entry
) {
385 hash_table_insert_rehash(ht
, entry
->hash
, entry
->key
, entry
->data
);
388 ht
->entries
= old_ht
.entries
;
390 ralloc_free(old_ht
.table
);
393 static struct hash_entry
*
394 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
395 const void *key
, void *data
)
397 struct hash_entry
*available_entry
= NULL
;
399 assert(!key_pointer_is_reserved(ht
, key
));
401 if (ht
->entries
>= ht
->max_entries
) {
402 _mesa_hash_table_rehash(ht
, ht
->size_index
+ 1);
403 } else if (ht
->deleted_entries
+ ht
->entries
>= ht
->max_entries
) {
404 _mesa_hash_table_rehash(ht
, ht
->size_index
);
407 uint32_t size
= ht
->size
;
408 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
409 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
411 uint32_t hash_address
= start_hash_address
;
413 struct hash_entry
*entry
= ht
->table
+ hash_address
;
415 if (!entry_is_present(ht
, entry
)) {
416 /* Stash the first available entry we find */
417 if (available_entry
== NULL
)
418 available_entry
= entry
;
419 if (entry_is_free(entry
))
423 /* Implement replacement when another insert happens
424 * with a matching key. This is a relatively common
425 * feature of hash tables, with the alternative
426 * generally being "insert the new value as well, and
427 * return it first when the key is searched for".
429 * Note that the hash table doesn't have a delete
430 * callback. If freeing of old data pointers is
431 * required to avoid memory leaks, perform a search
434 if (!entry_is_deleted(ht
, entry
) &&
435 entry
->hash
== hash
&&
436 ht
->key_equals_function(key
, entry
->key
)) {
442 hash_address
+= double_hash
;
443 if (hash_address
>= size
)
444 hash_address
-= size
;
445 } while (hash_address
!= start_hash_address
);
447 if (available_entry
) {
448 if (entry_is_deleted(ht
, available_entry
))
449 ht
->deleted_entries
--;
450 available_entry
->hash
= hash
;
451 available_entry
->key
= key
;
452 available_entry
->data
= data
;
454 return available_entry
;
457 /* We could hit here if a required resize failed. An unchecked-malloc
458 * application could ignore this result.
464 * Inserts the key with the given hash into the table.
466 * Note that insertion may rearrange the table on a resize or rehash,
467 * so previously found hash_entries are no longer valid after this function.
470 _mesa_hash_table_insert(struct hash_table
*ht
, const void *key
, void *data
)
472 assert(ht
->key_hash_function
);
473 return hash_table_insert(ht
, ht
->key_hash_function(key
), key
, data
);
477 _mesa_hash_table_insert_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
478 const void *key
, void *data
)
480 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
481 return hash_table_insert(ht
, hash
, key
, data
);
485 * This function deletes the given hash table entry.
487 * Note that deletion doesn't otherwise modify the table, so an iteration over
488 * the table deleting entries is safe.
491 _mesa_hash_table_remove(struct hash_table
*ht
,
492 struct hash_entry
*entry
)
497 entry
->key
= ht
->deleted_key
;
499 ht
->deleted_entries
++;
503 * Removes the entry with the corresponding key, if exists.
505 void _mesa_hash_table_remove_key(struct hash_table
*ht
,
508 _mesa_hash_table_remove(ht
, _mesa_hash_table_search(ht
, key
));
512 * This function is an iterator over the hash table.
514 * Pass in NULL for the first entry, as in the start of a for loop. Note that
515 * an iteration over the table is O(table_size) not O(entries).
518 _mesa_hash_table_next_entry(struct hash_table
*ht
,
519 struct hash_entry
*entry
)
526 for (; entry
!= ht
->table
+ ht
->size
; entry
++) {
527 if (entry_is_present(ht
, entry
)) {
536 * Returns a random entry from the hash table.
538 * This may be useful in implementing random replacement (as opposed
539 * to just removing everything) in caches based on this hash table
540 * implementation. @predicate may be used to filter entries, or may
541 * be set to NULL for no filtering.
544 _mesa_hash_table_random_entry(struct hash_table
*ht
,
545 bool (*predicate
)(struct hash_entry
*entry
))
547 struct hash_entry
*entry
;
548 uint32_t i
= rand() % ht
->size
;
550 if (ht
->entries
== 0)
553 for (entry
= ht
->table
+ i
; entry
!= ht
->table
+ ht
->size
; entry
++) {
554 if (entry_is_present(ht
, entry
) &&
555 (!predicate
|| predicate(entry
))) {
560 for (entry
= ht
->table
; entry
!= ht
->table
+ i
; entry
++) {
561 if (entry_is_present(ht
, entry
) &&
562 (!predicate
|| predicate(entry
))) {
572 _mesa_hash_data(const void *data
, size_t size
)
574 return XXH32(data
, size
, 0);
578 _mesa_hash_int(const void *key
)
580 return XXH32(key
, sizeof(int), 0);
584 _mesa_hash_uint(const void *key
)
586 return XXH32(key
, sizeof(unsigned), 0);
590 _mesa_hash_u32(const void *key
)
592 return XXH32(key
, 4, 0);
595 /** FNV-1a string hash implementation */
597 _mesa_hash_string(const void *_key
)
599 uint32_t hash
= _mesa_fnv32_1a_offset_bias
;
600 const char *key
= _key
;
603 hash
= _mesa_fnv32_1a_accumulate(hash
, *key
);
611 _mesa_hash_pointer(const void *pointer
)
613 uintptr_t num
= (uintptr_t) pointer
;
614 return (uint32_t) ((num
>> 2) ^ (num
>> 6) ^ (num
>> 10) ^ (num
>> 14));
618 _mesa_key_int_equal(const void *a
, const void *b
)
620 return *((const int *)a
) == *((const int *)b
);
624 _mesa_key_uint_equal(const void *a
, const void *b
)
627 return *((const unsigned *)a
) == *((const unsigned *)b
);
631 _mesa_key_u32_equal(const void *a
, const void *b
)
633 return *((const uint32_t *)a
) == *((const uint32_t *)b
);
637 * String compare function for use as the comparison callback in
638 * _mesa_hash_table_create().
641 _mesa_key_string_equal(const void *a
, const void *b
)
643 return strcmp(a
, b
) == 0;
647 _mesa_key_pointer_equal(const void *a
, const void *b
)
653 * Helper to create a hash table with pointer keys.
656 _mesa_pointer_hash_table_create(void *mem_ctx
)
658 return _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
659 _mesa_key_pointer_equal
);
663 * Hash table wrapper which supports 64-bit keys.
665 * TODO: unify all hash table implementations.
668 struct hash_key_u64
{
673 key_u64_hash(const void *key
)
675 return _mesa_hash_data(key
, sizeof(struct hash_key_u64
));
679 key_u64_equals(const void *a
, const void *b
)
681 const struct hash_key_u64
*aa
= a
;
682 const struct hash_key_u64
*bb
= b
;
684 return aa
->value
== bb
->value
;
687 #define FREED_KEY_VALUE 0
689 struct hash_table_u64
*
690 _mesa_hash_table_u64_create(void *mem_ctx
)
692 STATIC_ASSERT(FREED_KEY_VALUE
!= DELETED_KEY_VALUE
);
693 struct hash_table_u64
*ht
;
695 ht
= CALLOC_STRUCT(hash_table_u64
);
699 if (sizeof(void *) == 8) {
700 ht
->table
= _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
701 _mesa_key_pointer_equal
);
703 ht
->table
= _mesa_hash_table_create(mem_ctx
, key_u64_hash
,
708 _mesa_hash_table_set_deleted_key(ht
->table
, uint_key(DELETED_KEY_VALUE
));
714 _mesa_hash_table_u64_clear(struct hash_table_u64
*ht
,
715 void (*delete_function
)(struct hash_entry
*entry
))
720 if (ht
->deleted_key_data
) {
721 if (delete_function
) {
722 struct hash_table
*table
= ht
->table
;
723 struct hash_entry entry
;
725 /* Create a fake entry for the delete function. */
726 if (sizeof(void *) == 8) {
727 entry
.hash
= table
->key_hash_function(table
->deleted_key
);
729 struct hash_key_u64 _key
= { .value
= (uintptr_t)table
->deleted_key
};
730 entry
.hash
= table
->key_hash_function(&_key
);
732 entry
.key
= table
->deleted_key
;
733 entry
.data
= ht
->deleted_key_data
;
735 delete_function(&entry
);
737 ht
->deleted_key_data
= NULL
;
740 if (ht
->freed_key_data
) {
741 if (delete_function
) {
742 struct hash_table
*table
= ht
->table
;
743 struct hash_entry entry
;
745 /* Create a fake entry for the delete function. */
746 if (sizeof(void *) == 8) {
747 entry
.hash
= table
->key_hash_function(uint_key(FREED_KEY_VALUE
));
749 struct hash_key_u64 _key
= { .value
= (uintptr_t)FREED_KEY_VALUE
};
750 entry
.hash
= table
->key_hash_function(&_key
);
752 entry
.key
= uint_key(FREED_KEY_VALUE
);
753 entry
.data
= ht
->freed_key_data
;
755 delete_function(&entry
);
757 ht
->freed_key_data
= NULL
;
760 _mesa_hash_table_clear(ht
->table
, delete_function
);
764 _mesa_hash_table_u64_destroy(struct hash_table_u64
*ht
,
765 void (*delete_function
)(struct hash_entry
*entry
))
770 _mesa_hash_table_u64_clear(ht
, delete_function
);
771 _mesa_hash_table_destroy(ht
->table
, delete_function
);
776 _mesa_hash_table_u64_insert(struct hash_table_u64
*ht
, uint64_t key
,
779 if (key
== FREED_KEY_VALUE
) {
780 ht
->freed_key_data
= data
;
784 if (key
== DELETED_KEY_VALUE
) {
785 ht
->deleted_key_data
= data
;
789 if (sizeof(void *) == 8) {
790 _mesa_hash_table_insert(ht
->table
, (void *)(uintptr_t)key
, data
);
792 struct hash_key_u64
*_key
= CALLOC_STRUCT(hash_key_u64
);
798 _mesa_hash_table_insert(ht
->table
, _key
, data
);
802 static struct hash_entry
*
803 hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
805 if (sizeof(void *) == 8) {
806 return _mesa_hash_table_search(ht
->table
, (void *)(uintptr_t)key
);
808 struct hash_key_u64 _key
= { .value
= key
};
809 return _mesa_hash_table_search(ht
->table
, &_key
);
814 _mesa_hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
816 struct hash_entry
*entry
;
818 if (key
== FREED_KEY_VALUE
)
819 return ht
->freed_key_data
;
821 if (key
== DELETED_KEY_VALUE
)
822 return ht
->deleted_key_data
;
824 entry
= hash_table_u64_search(ht
, key
);
832 _mesa_hash_table_u64_remove(struct hash_table_u64
*ht
, uint64_t key
)
834 struct hash_entry
*entry
;
836 if (key
== FREED_KEY_VALUE
) {
837 ht
->freed_key_data
= NULL
;
841 if (key
== DELETED_KEY_VALUE
) {
842 ht
->deleted_key_data
= NULL
;
846 entry
= hash_table_u64_search(ht
, key
);
850 if (sizeof(void *) == 8) {
851 _mesa_hash_table_remove(ht
->table
, entry
);
853 struct hash_key
*_key
= (struct hash_key
*)entry
->key
;
855 _mesa_hash_table_remove(ht
->table
, entry
);