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>
39 #include "hash_table.h"
43 #include "fast_urem_by_const.h"
46 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
47 * p and p-2 are both prime. These tables are sized to have an extra 10%
48 * free to avoid exponential performance degradation as the hash table fills
51 static const uint32_t deleted_key_value
;
52 static const void *deleted_key
= &deleted_key_value
;
55 uint32_t max_entries
, size
, rehash
;
56 uint64_t size_magic
, rehash_magic
;
58 #define ENTRY(max_entries, size, rehash) \
59 { max_entries, size, rehash, \
60 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
68 ENTRY(128, 151, 149 ),
69 ENTRY(256, 283, 281 ),
70 ENTRY(512, 571, 569 ),
71 ENTRY(1024, 1153, 1151 ),
72 ENTRY(2048, 2269, 2267 ),
73 ENTRY(4096, 4519, 4517 ),
74 ENTRY(8192, 9013, 9011 ),
75 ENTRY(16384, 18043, 18041 ),
76 ENTRY(32768, 36109, 36107 ),
77 ENTRY(65536, 72091, 72089 ),
78 ENTRY(131072, 144409, 144407 ),
79 ENTRY(262144, 288361, 288359 ),
80 ENTRY(524288, 576883, 576881 ),
81 ENTRY(1048576, 1153459, 1153457 ),
82 ENTRY(2097152, 2307163, 2307161 ),
83 ENTRY(4194304, 4613893, 4613891 ),
84 ENTRY(8388608, 9227641, 9227639 ),
85 ENTRY(16777216, 18455029, 18455027 ),
86 ENTRY(33554432, 36911011, 36911009 ),
87 ENTRY(67108864, 73819861, 73819859 ),
88 ENTRY(134217728, 147639589, 147639587 ),
89 ENTRY(268435456, 295279081, 295279079 ),
90 ENTRY(536870912, 590559793, 590559791 ),
91 ENTRY(1073741824, 1181116273, 1181116271 ),
92 ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
95 ASSERTED
static inline bool
96 key_pointer_is_reserved(const void *key
)
98 return key
== NULL
|| key
== deleted_key
;
102 entry_is_free(struct set_entry
*entry
)
104 return entry
->key
== NULL
;
108 entry_is_deleted(struct set_entry
*entry
)
110 return entry
->key
== deleted_key
;
114 entry_is_present(struct set_entry
*entry
)
116 return entry
->key
!= NULL
&& entry
->key
!= deleted_key
;
120 _mesa_set_create(void *mem_ctx
,
121 uint32_t (*key_hash_function
)(const void *key
),
122 bool (*key_equals_function
)(const void *a
,
127 ht
= ralloc(mem_ctx
, struct set
);
132 ht
->size
= hash_sizes
[ht
->size_index
].size
;
133 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
134 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
135 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
136 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
137 ht
->key_hash_function
= key_hash_function
;
138 ht
->key_equals_function
= key_equals_function
;
139 ht
->table
= rzalloc_array(ht
, struct set_entry
, ht
->size
);
141 ht
->deleted_entries
= 0;
143 if (ht
->table
== NULL
) {
152 _mesa_set_clone(struct set
*set
, void *dst_mem_ctx
)
156 clone
= ralloc(dst_mem_ctx
, struct set
);
160 memcpy(clone
, set
, sizeof(struct set
));
162 clone
->table
= ralloc_array(clone
, struct set_entry
, clone
->size
);
163 if (clone
->table
== NULL
) {
168 memcpy(clone
->table
, set
->table
, clone
->size
* sizeof(struct set_entry
));
174 * Frees the given set.
176 * If delete_function is passed, it gets called on each entry present before
180 _mesa_set_destroy(struct set
*ht
, void (*delete_function
)(struct set_entry
*entry
))
185 if (delete_function
) {
186 set_foreach (ht
, entry
) {
187 delete_function(entry
);
190 ralloc_free(ht
->table
);
195 * Clears all values from the given set.
197 * If delete_function is passed, it gets called on each entry present before
198 * the set is cleared.
201 _mesa_set_clear(struct set
*set
, void (*delete_function
)(struct set_entry
*entry
))
206 set_foreach (set
, entry
) {
208 delete_function(entry
);
209 entry
->key
= deleted_key
;
212 set
->entries
= set
->deleted_entries
= 0;
216 * Finds a set entry with the given key and hash of that key.
218 * Returns NULL if no entry is found.
220 static struct set_entry
*
221 set_search(const struct set
*ht
, uint32_t hash
, const void *key
)
223 assert(!key_pointer_is_reserved(key
));
225 uint32_t size
= ht
->size
;
226 uint32_t start_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
227 uint32_t double_hash
= util_fast_urem32(hash
, ht
->rehash
,
228 ht
->rehash_magic
) + 1;
229 uint32_t hash_address
= start_address
;
231 struct set_entry
*entry
= ht
->table
+ hash_address
;
233 if (entry_is_free(entry
)) {
235 } else if (entry_is_present(entry
) && entry
->hash
== hash
) {
236 if (ht
->key_equals_function(key
, entry
->key
)) {
241 hash_address
+= double_hash
;
242 if (hash_address
>= size
)
243 hash_address
-= size
;
244 } while (hash_address
!= start_address
);
250 _mesa_set_search(const struct set
*set
, const void *key
)
252 assert(set
->key_hash_function
);
253 return set_search(set
, set
->key_hash_function(key
), key
);
257 _mesa_set_search_pre_hashed(const struct set
*set
, uint32_t hash
,
260 assert(set
->key_hash_function
== NULL
||
261 hash
== set
->key_hash_function(key
));
262 return set_search(set
, hash
, key
);
266 set_add_rehash(struct set
*ht
, uint32_t hash
, const void *key
)
268 uint32_t size
= ht
->size
;
269 uint32_t start_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
270 uint32_t double_hash
= util_fast_urem32(hash
, ht
->rehash
,
271 ht
->rehash_magic
) + 1;
272 uint32_t hash_address
= start_address
;
274 struct set_entry
*entry
= ht
->table
+ hash_address
;
275 if (likely(entry
->key
== NULL
)) {
281 hash_address
= hash_address
+ double_hash
;
282 if (hash_address
>= size
)
283 hash_address
-= size
;
288 set_rehash(struct set
*ht
, unsigned new_size_index
)
291 struct set_entry
*table
;
293 if (new_size_index
>= ARRAY_SIZE(hash_sizes
))
296 table
= rzalloc_array(ht
, struct set_entry
,
297 hash_sizes
[new_size_index
].size
);
304 ht
->size_index
= new_size_index
;
305 ht
->size
= hash_sizes
[ht
->size_index
].size
;
306 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
307 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
308 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
309 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
311 ht
->deleted_entries
= 0;
313 set_foreach(&old_ht
, entry
) {
314 set_add_rehash(ht
, entry
->hash
, entry
->key
);
317 ht
->entries
= old_ht
.entries
;
319 ralloc_free(old_ht
.table
);
323 _mesa_set_resize(struct set
*set
, uint32_t entries
)
325 /* You can't shrink a set below its number of entries */
326 if (set
->entries
> entries
)
327 entries
= set
->entries
;
329 unsigned size_index
= 0;
330 while (hash_sizes
[size_index
].max_entries
< entries
)
333 set_rehash(set
, size_index
);
337 * Find a matching entry for the given key, or insert it if it doesn't already
340 * Note that insertion may rearrange the table on a resize or rehash,
341 * so previously found hash_entries are no longer valid after this function.
343 static struct set_entry
*
344 set_search_or_add(struct set
*ht
, uint32_t hash
, const void *key
, bool *found
)
346 struct set_entry
*available_entry
= NULL
;
348 assert(!key_pointer_is_reserved(key
));
350 if (ht
->entries
>= ht
->max_entries
) {
351 set_rehash(ht
, ht
->size_index
+ 1);
352 } else if (ht
->deleted_entries
+ ht
->entries
>= ht
->max_entries
) {
353 set_rehash(ht
, ht
->size_index
);
356 uint32_t size
= ht
->size
;
357 uint32_t start_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
358 uint32_t double_hash
= util_fast_urem32(hash
, ht
->rehash
,
359 ht
->rehash_magic
) + 1;
360 uint32_t hash_address
= start_address
;
362 struct set_entry
*entry
= ht
->table
+ hash_address
;
364 if (!entry_is_present(entry
)) {
365 /* Stash the first available entry we find */
366 if (available_entry
== NULL
)
367 available_entry
= entry
;
368 if (entry_is_free(entry
))
372 if (!entry_is_deleted(entry
) &&
373 entry
->hash
== hash
&&
374 ht
->key_equals_function(key
, entry
->key
)) {
380 hash_address
= hash_address
+ double_hash
;
381 if (hash_address
>= size
)
382 hash_address
-= size
;
383 } while (hash_address
!= start_address
);
385 if (available_entry
) {
386 /* There is no matching entry, create it. */
387 if (entry_is_deleted(available_entry
))
388 ht
->deleted_entries
--;
389 available_entry
->hash
= hash
;
390 available_entry
->key
= key
;
394 return available_entry
;
397 /* We could hit here if a required resize failed. An unchecked-malloc
398 * application could ignore this result.
404 * Inserts the key with the given hash into the table.
406 * Note that insertion may rearrange the table on a resize or rehash,
407 * so previously found hash_entries are no longer valid after this function.
409 static struct set_entry
*
410 set_add(struct set
*ht
, uint32_t hash
, const void *key
)
412 struct set_entry
*entry
= set_search_or_add(ht
, hash
, key
, NULL
);
414 if (unlikely(!entry
))
417 /* Note: If a matching entry already exists, this will replace it. This is
418 * a relatively common feature of hash tables, with the alternative
419 * generally being "insert the new value as well, and return it first when
420 * the key is searched for".
422 * Note that the hash table doesn't have a delete callback. If freeing of
423 * old keys is required to avoid memory leaks, use the alternative
424 * _mesa_set_search_or_add function and implement the replacement yourself.
431 _mesa_set_add(struct set
*set
, const void *key
)
433 assert(set
->key_hash_function
);
434 return set_add(set
, set
->key_hash_function(key
), key
);
438 _mesa_set_add_pre_hashed(struct set
*set
, uint32_t hash
, const void *key
)
440 assert(set
->key_hash_function
== NULL
||
441 hash
== set
->key_hash_function(key
));
442 return set_add(set
, hash
, key
);
446 _mesa_set_search_and_add(struct set
*set
, const void *key
, bool *replaced
)
448 assert(set
->key_hash_function
);
449 return _mesa_set_search_and_add_pre_hashed(set
,
450 set
->key_hash_function(key
),
455 _mesa_set_search_and_add_pre_hashed(struct set
*set
, uint32_t hash
,
456 const void *key
, bool *replaced
)
458 assert(set
->key_hash_function
== NULL
||
459 hash
== set
->key_hash_function(key
));
460 struct set_entry
*entry
= set_search_or_add(set
, hash
, key
, replaced
);
462 if (unlikely(!entry
))
465 /* This implements the replacement, same as _mesa_set_add(). The user will
466 * be notified if we're overwriting a found entry.
473 _mesa_set_search_or_add(struct set
*set
, const void *key
)
475 assert(set
->key_hash_function
);
476 return set_search_or_add(set
, set
->key_hash_function(key
), key
, NULL
);
480 _mesa_set_search_or_add_pre_hashed(struct set
*set
, uint32_t hash
,
483 assert(set
->key_hash_function
== NULL
||
484 hash
== set
->key_hash_function(key
));
485 return set_search_or_add(set
, hash
, key
, NULL
);
489 * This function deletes the given hash table entry.
491 * Note that deletion doesn't otherwise modify the table, so an iteration over
492 * the table deleting entries is safe.
495 _mesa_set_remove(struct set
*ht
, struct set_entry
*entry
)
500 entry
->key
= deleted_key
;
502 ht
->deleted_entries
++;
506 * Removes the entry with the corresponding key, if exists.
509 _mesa_set_remove_key(struct set
*set
, const void *key
)
511 _mesa_set_remove(set
, _mesa_set_search(set
, key
));
515 * This function is an iterator over the hash table.
517 * Pass in NULL for the first entry, as in the start of a for loop. Note that
518 * an iteration over the table is O(table_size) not O(entries).
521 _mesa_set_next_entry(const struct set
*ht
, struct set_entry
*entry
)
528 for (; entry
!= ht
->table
+ ht
->size
; entry
++) {
529 if (entry_is_present(entry
)) {
538 _mesa_set_random_entry(struct set
*ht
,
539 int (*predicate
)(struct set_entry
*entry
))
541 struct set_entry
*entry
;
542 uint32_t i
= rand() % ht
->size
;
544 if (ht
->entries
== 0)
547 for (entry
= ht
->table
+ i
; entry
!= ht
->table
+ ht
->size
; entry
++) {
548 if (entry_is_present(entry
) &&
549 (!predicate
|| predicate(entry
))) {
554 for (entry
= ht
->table
; entry
!= ht
->table
+ i
; entry
++) {
555 if (entry_is_present(entry
) &&
556 (!predicate
|| predicate(entry
))) {
565 * Helper to create a set with pointer keys.
568 _mesa_pointer_set_create(void *mem_ctx
)
570 return _mesa_set_create(mem_ctx
, _mesa_hash_pointer
,
571 _mesa_key_pointer_equal
);