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 static const uint32_t deleted_key_value
;
56 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
57 * p and p-2 are both prime. These tables are sized to have an extra 10%
58 * free to avoid exponential performance degradation as the hash table fills
61 uint32_t max_entries
, size
, rehash
;
62 uint64_t size_magic
, rehash_magic
;
64 #define ENTRY(max_entries, size, rehash) \
65 { max_entries, size, rehash, \
66 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
74 ENTRY(128, 151, 149 ),
75 ENTRY(256, 283, 281 ),
76 ENTRY(512, 571, 569 ),
77 ENTRY(1024, 1153, 1151 ),
78 ENTRY(2048, 2269, 2267 ),
79 ENTRY(4096, 4519, 4517 ),
80 ENTRY(8192, 9013, 9011 ),
81 ENTRY(16384, 18043, 18041 ),
82 ENTRY(32768, 36109, 36107 ),
83 ENTRY(65536, 72091, 72089 ),
84 ENTRY(131072, 144409, 144407 ),
85 ENTRY(262144, 288361, 288359 ),
86 ENTRY(524288, 576883, 576881 ),
87 ENTRY(1048576, 1153459, 1153457 ),
88 ENTRY(2097152, 2307163, 2307161 ),
89 ENTRY(4194304, 4613893, 4613891 ),
90 ENTRY(8388608, 9227641, 9227639 ),
91 ENTRY(16777216, 18455029, 18455027 ),
92 ENTRY(33554432, 36911011, 36911009 ),
93 ENTRY(67108864, 73819861, 73819859 ),
94 ENTRY(134217728, 147639589, 147639587 ),
95 ENTRY(268435456, 295279081, 295279079 ),
96 ENTRY(536870912, 590559793, 590559791 ),
97 ENTRY(1073741824, 1181116273, 1181116271 ),
98 ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
102 key_pointer_is_reserved(const struct hash_table
*ht
, const void *key
)
104 return key
== NULL
|| key
== ht
->deleted_key
;
108 entry_is_free(const struct hash_entry
*entry
)
110 return entry
->key
== NULL
;
114 entry_is_deleted(const struct hash_table
*ht
, struct hash_entry
*entry
)
116 return entry
->key
== ht
->deleted_key
;
120 entry_is_present(const struct hash_table
*ht
, struct hash_entry
*entry
)
122 return entry
->key
!= NULL
&& entry
->key
!= ht
->deleted_key
;
126 _mesa_hash_table_init(struct hash_table
*ht
,
128 uint32_t (*key_hash_function
)(const void *key
),
129 bool (*key_equals_function
)(const void *a
,
133 ht
->size
= hash_sizes
[ht
->size_index
].size
;
134 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
135 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
136 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
137 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
138 ht
->key_hash_function
= key_hash_function
;
139 ht
->key_equals_function
= key_equals_function
;
140 ht
->table
= rzalloc_array(mem_ctx
, struct hash_entry
, ht
->size
);
142 ht
->deleted_entries
= 0;
143 ht
->deleted_key
= &deleted_key_value
;
145 return ht
->table
!= NULL
;
149 _mesa_hash_table_create(void *mem_ctx
,
150 uint32_t (*key_hash_function
)(const void *key
),
151 bool (*key_equals_function
)(const void *a
,
154 struct hash_table
*ht
;
156 /* mem_ctx is used to allocate the hash table, but the hash table is used
157 * to allocate all of the suballocations.
159 ht
= ralloc(mem_ctx
, struct hash_table
);
163 if (!_mesa_hash_table_init(ht
, ht
, key_hash_function
, key_equals_function
)) {
172 _mesa_hash_table_clone(struct hash_table
*src
, void *dst_mem_ctx
)
174 struct hash_table
*ht
;
176 ht
= ralloc(dst_mem_ctx
, struct hash_table
);
180 memcpy(ht
, src
, sizeof(struct hash_table
));
182 ht
->table
= ralloc_array(ht
, struct hash_entry
, ht
->size
);
183 if (ht
->table
== NULL
) {
188 memcpy(ht
->table
, src
->table
, ht
->size
* sizeof(struct hash_entry
));
194 * Frees the given hash table.
196 * If delete_function is passed, it gets called on each entry present before
200 _mesa_hash_table_destroy(struct hash_table
*ht
,
201 void (*delete_function
)(struct hash_entry
*entry
))
206 if (delete_function
) {
207 hash_table_foreach(ht
, entry
) {
208 delete_function(entry
);
215 * Deletes all entries of the given hash table without deleting the table
216 * itself or changing its structure.
218 * If delete_function is passed, it gets called on each entry present.
221 _mesa_hash_table_clear(struct hash_table
*ht
,
222 void (*delete_function
)(struct hash_entry
*entry
))
224 struct hash_entry
*entry
;
226 for (entry
= ht
->table
; entry
!= ht
->table
+ ht
->size
; entry
++) {
227 if (entry
->key
== NULL
)
230 if (delete_function
!= NULL
&& entry
->key
!= ht
->deleted_key
)
231 delete_function(entry
);
237 ht
->deleted_entries
= 0;
240 /** Sets the value of the key pointer used for deleted entries in the table.
242 * The assumption is that usually keys are actual pointers, so we use a
243 * default value of a pointer to an arbitrary piece of storage in the library.
244 * But in some cases a consumer wants to store some other sort of value in the
245 * table, like a uint32_t, in which case that pointer may conflict with one of
246 * their valid keys. This lets that user select a safe value.
248 * This must be called before any keys are actually deleted from the table.
251 _mesa_hash_table_set_deleted_key(struct hash_table
*ht
, const void *deleted_key
)
253 ht
->deleted_key
= deleted_key
;
256 static struct hash_entry
*
257 hash_table_search(struct hash_table
*ht
, uint32_t hash
, const void *key
)
259 assert(!key_pointer_is_reserved(ht
, key
));
261 uint32_t size
= ht
->size
;
262 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
263 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
265 uint32_t hash_address
= start_hash_address
;
268 struct hash_entry
*entry
= ht
->table
+ hash_address
;
270 if (entry_is_free(entry
)) {
272 } else if (entry_is_present(ht
, entry
) && entry
->hash
== hash
) {
273 if (ht
->key_equals_function(key
, entry
->key
)) {
278 hash_address
+= double_hash
;
279 if (hash_address
>= size
)
280 hash_address
-= size
;
281 } while (hash_address
!= start_hash_address
);
287 * Finds a hash table entry with the given key and hash of that key.
289 * Returns NULL if no entry is found. Note that the data pointer may be
290 * modified by the user.
293 _mesa_hash_table_search(struct hash_table
*ht
, const void *key
)
295 assert(ht
->key_hash_function
);
296 return hash_table_search(ht
, ht
->key_hash_function(key
), key
);
300 _mesa_hash_table_search_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
303 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
304 return hash_table_search(ht
, hash
, key
);
307 static struct hash_entry
*
308 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
309 const void *key
, void *data
);
312 hash_table_insert_rehash(struct hash_table
*ht
, uint32_t hash
,
313 const void *key
, void *data
)
315 uint32_t size
= ht
->size
;
316 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
317 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
319 uint32_t hash_address
= start_hash_address
;
321 struct hash_entry
*entry
= ht
->table
+ hash_address
;
323 if (likely(entry
->key
== NULL
)) {
330 hash_address
+= double_hash
;
331 if (hash_address
>= size
)
332 hash_address
-= size
;
337 _mesa_hash_table_rehash(struct hash_table
*ht
, unsigned new_size_index
)
339 struct hash_table old_ht
;
340 struct hash_entry
*table
;
342 if (new_size_index
>= ARRAY_SIZE(hash_sizes
))
345 table
= rzalloc_array(ralloc_parent(ht
->table
), struct hash_entry
,
346 hash_sizes
[new_size_index
].size
);
353 ht
->size_index
= new_size_index
;
354 ht
->size
= hash_sizes
[ht
->size_index
].size
;
355 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
356 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
357 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
358 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
360 ht
->deleted_entries
= 0;
362 hash_table_foreach(&old_ht
, entry
) {
363 hash_table_insert_rehash(ht
, entry
->hash
, entry
->key
, entry
->data
);
366 ht
->entries
= old_ht
.entries
;
368 ralloc_free(old_ht
.table
);
371 static struct hash_entry
*
372 hash_table_insert(struct hash_table
*ht
, uint32_t hash
,
373 const void *key
, void *data
)
375 struct hash_entry
*available_entry
= NULL
;
377 assert(!key_pointer_is_reserved(ht
, key
));
379 if (ht
->entries
>= ht
->max_entries
) {
380 _mesa_hash_table_rehash(ht
, ht
->size_index
+ 1);
381 } else if (ht
->deleted_entries
+ ht
->entries
>= ht
->max_entries
) {
382 _mesa_hash_table_rehash(ht
, ht
->size_index
);
385 uint32_t size
= ht
->size
;
386 uint32_t start_hash_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
387 uint32_t double_hash
= 1 + util_fast_urem32(hash
, ht
->rehash
,
389 uint32_t hash_address
= start_hash_address
;
391 struct hash_entry
*entry
= ht
->table
+ hash_address
;
393 if (!entry_is_present(ht
, entry
)) {
394 /* Stash the first available entry we find */
395 if (available_entry
== NULL
)
396 available_entry
= entry
;
397 if (entry_is_free(entry
))
401 /* Implement replacement when another insert happens
402 * with a matching key. This is a relatively common
403 * feature of hash tables, with the alternative
404 * generally being "insert the new value as well, and
405 * return it first when the key is searched for".
407 * Note that the hash table doesn't have a delete
408 * callback. If freeing of old data pointers is
409 * required to avoid memory leaks, perform a search
412 if (!entry_is_deleted(ht
, entry
) &&
413 entry
->hash
== hash
&&
414 ht
->key_equals_function(key
, entry
->key
)) {
420 hash_address
+= double_hash
;
421 if (hash_address
>= size
)
422 hash_address
-= size
;
423 } while (hash_address
!= start_hash_address
);
425 if (available_entry
) {
426 if (entry_is_deleted(ht
, available_entry
))
427 ht
->deleted_entries
--;
428 available_entry
->hash
= hash
;
429 available_entry
->key
= key
;
430 available_entry
->data
= data
;
432 return available_entry
;
435 /* We could hit here if a required resize failed. An unchecked-malloc
436 * application could ignore this result.
442 * Inserts the key with the given hash into the table.
444 * Note that insertion may rearrange the table on a resize or rehash,
445 * so previously found hash_entries are no longer valid after this function.
448 _mesa_hash_table_insert(struct hash_table
*ht
, const void *key
, void *data
)
450 assert(ht
->key_hash_function
);
451 return hash_table_insert(ht
, ht
->key_hash_function(key
), key
, data
);
455 _mesa_hash_table_insert_pre_hashed(struct hash_table
*ht
, uint32_t hash
,
456 const void *key
, void *data
)
458 assert(ht
->key_hash_function
== NULL
|| hash
== ht
->key_hash_function(key
));
459 return hash_table_insert(ht
, hash
, key
, data
);
463 * This function deletes the given hash table entry.
465 * Note that deletion doesn't otherwise modify the table, so an iteration over
466 * the table deleting entries is safe.
469 _mesa_hash_table_remove(struct hash_table
*ht
,
470 struct hash_entry
*entry
)
475 entry
->key
= ht
->deleted_key
;
477 ht
->deleted_entries
++;
481 * Removes the entry with the corresponding key, if exists.
483 void _mesa_hash_table_remove_key(struct hash_table
*ht
,
486 _mesa_hash_table_remove(ht
, _mesa_hash_table_search(ht
, key
));
490 * This function is an iterator over the hash table.
492 * Pass in NULL for the first entry, as in the start of a for loop. Note that
493 * an iteration over the table is O(table_size) not O(entries).
496 _mesa_hash_table_next_entry(struct hash_table
*ht
,
497 struct hash_entry
*entry
)
504 for (; entry
!= ht
->table
+ ht
->size
; entry
++) {
505 if (entry_is_present(ht
, entry
)) {
514 * Returns a random entry from the hash table.
516 * This may be useful in implementing random replacement (as opposed
517 * to just removing everything) in caches based on this hash table
518 * implementation. @predicate may be used to filter entries, or may
519 * be set to NULL for no filtering.
522 _mesa_hash_table_random_entry(struct hash_table
*ht
,
523 bool (*predicate
)(struct hash_entry
*entry
))
525 struct hash_entry
*entry
;
526 uint32_t i
= rand() % ht
->size
;
528 if (ht
->entries
== 0)
531 for (entry
= ht
->table
+ i
; entry
!= ht
->table
+ ht
->size
; entry
++) {
532 if (entry_is_present(ht
, entry
) &&
533 (!predicate
|| predicate(entry
))) {
538 for (entry
= ht
->table
; entry
!= ht
->table
+ i
; entry
++) {
539 if (entry_is_present(ht
, entry
) &&
540 (!predicate
|| predicate(entry
))) {
550 * Quick FNV-1a hash implementation based on:
551 * http://www.isthe.com/chongo/tech/comp/fnv/
553 * FNV-1a is not be the best hash out there -- Jenkins's lookup3 is supposed
554 * to be quite good, and it probably beats FNV. But FNV has the advantage
555 * that it involves almost no code. For an improvement on both, see Paul
556 * Hsieh's http://www.azillionmonkeys.com/qed/hash.html
559 _mesa_hash_data(const void *data
, size_t size
)
561 return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias
,
565 /** FNV-1a string hash implementation */
567 _mesa_hash_string(const void *_key
)
569 uint32_t hash
= _mesa_fnv32_1a_offset_bias
;
570 const char *key
= _key
;
573 hash
= _mesa_fnv32_1a_accumulate(hash
, *key
);
581 * String compare function for use as the comparison callback in
582 * _mesa_hash_table_create().
585 _mesa_key_string_equal(const void *a
, const void *b
)
587 return strcmp(a
, b
) == 0;
591 _mesa_key_pointer_equal(const void *a
, const void *b
)
597 * Helper to create a hash table with pointer keys.
600 _mesa_pointer_hash_table_create(void *mem_ctx
)
602 return _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
603 _mesa_key_pointer_equal
);
607 * Hash table wrapper which supports 64-bit keys.
609 * TODO: unify all hash table implementations.
612 struct hash_key_u64
{
617 key_u64_hash(const void *key
)
619 return _mesa_hash_data(key
, sizeof(struct hash_key_u64
));
623 key_u64_equals(const void *a
, const void *b
)
625 const struct hash_key_u64
*aa
= a
;
626 const struct hash_key_u64
*bb
= b
;
628 return aa
->value
== bb
->value
;
631 #define FREED_KEY_VALUE 0
633 struct hash_table_u64
*
634 _mesa_hash_table_u64_create(void *mem_ctx
)
636 STATIC_ASSERT(FREED_KEY_VALUE
!= DELETED_KEY_VALUE
);
637 struct hash_table_u64
*ht
;
639 ht
= CALLOC_STRUCT(hash_table_u64
);
643 if (sizeof(void *) == 8) {
644 ht
->table
= _mesa_hash_table_create(mem_ctx
, _mesa_hash_pointer
,
645 _mesa_key_pointer_equal
);
647 ht
->table
= _mesa_hash_table_create(mem_ctx
, key_u64_hash
,
652 _mesa_hash_table_set_deleted_key(ht
->table
, uint_key(DELETED_KEY_VALUE
));
658 _mesa_hash_table_u64_clear(struct hash_table_u64
*ht
,
659 void (*delete_function
)(struct hash_entry
*entry
))
664 if (ht
->deleted_key_data
) {
665 if (delete_function
) {
666 struct hash_table
*table
= ht
->table
;
667 struct hash_entry entry
;
669 /* Create a fake entry for the delete function. */
670 if (sizeof(void *) == 8) {
671 entry
.hash
= table
->key_hash_function(table
->deleted_key
);
673 struct hash_key_u64 _key
= { .value
= (uintptr_t)table
->deleted_key
};
674 entry
.hash
= table
->key_hash_function(&_key
);
676 entry
.key
= table
->deleted_key
;
677 entry
.data
= ht
->deleted_key_data
;
679 delete_function(&entry
);
681 ht
->deleted_key_data
= NULL
;
684 if (ht
->freed_key_data
) {
685 if (delete_function
) {
686 struct hash_table
*table
= ht
->table
;
687 struct hash_entry entry
;
689 /* Create a fake entry for the delete function. */
690 if (sizeof(void *) == 8) {
691 entry
.hash
= table
->key_hash_function(uint_key(FREED_KEY_VALUE
));
693 struct hash_key_u64 _key
= { .value
= (uintptr_t)FREED_KEY_VALUE
};
694 entry
.hash
= table
->key_hash_function(&_key
);
696 entry
.key
= uint_key(FREED_KEY_VALUE
);
697 entry
.data
= ht
->freed_key_data
;
699 delete_function(&entry
);
701 ht
->freed_key_data
= NULL
;
704 _mesa_hash_table_clear(ht
->table
, delete_function
);
708 _mesa_hash_table_u64_destroy(struct hash_table_u64
*ht
,
709 void (*delete_function
)(struct hash_entry
*entry
))
714 _mesa_hash_table_u64_clear(ht
, delete_function
);
715 _mesa_hash_table_destroy(ht
->table
, delete_function
);
720 _mesa_hash_table_u64_insert(struct hash_table_u64
*ht
, uint64_t key
,
723 if (key
== FREED_KEY_VALUE
) {
724 ht
->freed_key_data
= data
;
728 if (key
== DELETED_KEY_VALUE
) {
729 ht
->deleted_key_data
= data
;
733 if (sizeof(void *) == 8) {
734 _mesa_hash_table_insert(ht
->table
, (void *)(uintptr_t)key
, data
);
736 struct hash_key_u64
*_key
= CALLOC_STRUCT(hash_key_u64
);
742 _mesa_hash_table_insert(ht
->table
, _key
, data
);
746 static struct hash_entry
*
747 hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
749 if (sizeof(void *) == 8) {
750 return _mesa_hash_table_search(ht
->table
, (void *)(uintptr_t)key
);
752 struct hash_key_u64 _key
= { .value
= key
};
753 return _mesa_hash_table_search(ht
->table
, &_key
);
758 _mesa_hash_table_u64_search(struct hash_table_u64
*ht
, uint64_t key
)
760 struct hash_entry
*entry
;
762 if (key
== FREED_KEY_VALUE
)
763 return ht
->freed_key_data
;
765 if (key
== DELETED_KEY_VALUE
)
766 return ht
->deleted_key_data
;
768 entry
= hash_table_u64_search(ht
, key
);
776 _mesa_hash_table_u64_remove(struct hash_table_u64
*ht
, uint64_t key
)
778 struct hash_entry
*entry
;
780 if (key
== FREED_KEY_VALUE
) {
781 ht
->freed_key_data
= NULL
;
785 if (key
== DELETED_KEY_VALUE
) {
786 ht
->deleted_key_data
= NULL
;
790 entry
= hash_table_u64_search(ht
, key
);
794 if (sizeof(void *) == 8) {
795 _mesa_hash_table_remove(ht
->table
, entry
);
797 struct hash_key
*_key
= (struct hash_key
*)entry
->key
;
799 _mesa_hash_table_remove(ht
->table
, entry
);