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 )
96 entry_is_free(struct set_entry
*entry
)
98 return entry
->key
== NULL
;
102 entry_is_deleted(struct set_entry
*entry
)
104 return entry
->key
== deleted_key
;
108 entry_is_present(struct set_entry
*entry
)
110 return entry
->key
!= NULL
&& entry
->key
!= deleted_key
;
114 _mesa_set_create(void *mem_ctx
,
115 uint32_t (*key_hash_function
)(const void *key
),
116 bool (*key_equals_function
)(const void *a
,
121 ht
= ralloc(mem_ctx
, struct set
);
126 ht
->size
= hash_sizes
[ht
->size_index
].size
;
127 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
128 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
129 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
130 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
131 ht
->key_hash_function
= key_hash_function
;
132 ht
->key_equals_function
= key_equals_function
;
133 ht
->table
= rzalloc_array(ht
, struct set_entry
, ht
->size
);
135 ht
->deleted_entries
= 0;
137 if (ht
->table
== NULL
) {
146 _mesa_set_clone(struct set
*set
, void *dst_mem_ctx
)
150 clone
= ralloc(dst_mem_ctx
, struct set
);
154 memcpy(clone
, set
, sizeof(struct set
));
156 clone
->table
= ralloc_array(clone
, struct set_entry
, clone
->size
);
157 if (clone
->table
== NULL
) {
162 memcpy(clone
->table
, set
->table
, clone
->size
* sizeof(struct set_entry
));
168 * Frees the given set.
170 * If delete_function is passed, it gets called on each entry present before
174 _mesa_set_destroy(struct set
*ht
, void (*delete_function
)(struct set_entry
*entry
))
179 if (delete_function
) {
180 set_foreach (ht
, entry
) {
181 delete_function(entry
);
184 ralloc_free(ht
->table
);
189 * Clears all values from the given set.
191 * If delete_function is passed, it gets called on each entry present before
192 * the set is cleared.
195 _mesa_set_clear(struct set
*set
, void (*delete_function
)(struct set_entry
*entry
))
200 set_foreach (set
, entry
) {
202 delete_function(entry
);
203 entry
->key
= deleted_key
;
206 set
->entries
= set
->deleted_entries
= 0;
210 * Finds a set entry with the given key and hash of that key.
212 * Returns NULL if no entry is found.
214 static struct set_entry
*
215 set_search(const struct set
*ht
, uint32_t hash
, const void *key
)
217 uint32_t size
= ht
->size
;
218 uint32_t start_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
219 uint32_t double_hash
= util_fast_urem32(hash
, ht
->rehash
,
220 ht
->rehash_magic
) + 1;
221 uint32_t hash_address
= start_address
;
223 struct set_entry
*entry
= ht
->table
+ hash_address
;
225 if (entry_is_free(entry
)) {
227 } else if (entry_is_present(entry
) && entry
->hash
== hash
) {
228 if (ht
->key_equals_function(key
, entry
->key
)) {
233 hash_address
+= double_hash
;
234 if (hash_address
>= size
)
235 hash_address
-= size
;
236 } while (hash_address
!= start_address
);
242 _mesa_set_search(const struct set
*set
, const void *key
)
244 assert(set
->key_hash_function
);
245 return set_search(set
, set
->key_hash_function(key
), key
);
249 _mesa_set_search_pre_hashed(const struct set
*set
, uint32_t hash
,
252 assert(set
->key_hash_function
== NULL
||
253 hash
== set
->key_hash_function(key
));
254 return set_search(set
, hash
, key
);
258 set_add_rehash(struct set
*ht
, uint32_t hash
, const void *key
)
260 uint32_t size
= ht
->size
;
261 uint32_t start_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
262 uint32_t double_hash
= util_fast_urem32(hash
, ht
->rehash
,
263 ht
->rehash_magic
) + 1;
264 uint32_t hash_address
= start_address
;
266 struct set_entry
*entry
= ht
->table
+ hash_address
;
267 if (likely(entry
->key
== NULL
)) {
273 hash_address
= hash_address
+ double_hash
;
274 if (hash_address
>= size
)
275 hash_address
-= size
;
280 set_rehash(struct set
*ht
, unsigned new_size_index
)
283 struct set_entry
*table
;
285 if (new_size_index
>= ARRAY_SIZE(hash_sizes
))
288 table
= rzalloc_array(ht
, struct set_entry
,
289 hash_sizes
[new_size_index
].size
);
296 ht
->size_index
= new_size_index
;
297 ht
->size
= hash_sizes
[ht
->size_index
].size
;
298 ht
->rehash
= hash_sizes
[ht
->size_index
].rehash
;
299 ht
->size_magic
= hash_sizes
[ht
->size_index
].size_magic
;
300 ht
->rehash_magic
= hash_sizes
[ht
->size_index
].rehash_magic
;
301 ht
->max_entries
= hash_sizes
[ht
->size_index
].max_entries
;
303 ht
->deleted_entries
= 0;
305 set_foreach(&old_ht
, entry
) {
306 set_add_rehash(ht
, entry
->hash
, entry
->key
);
309 ht
->entries
= old_ht
.entries
;
311 ralloc_free(old_ht
.table
);
315 _mesa_set_resize(struct set
*set
, uint32_t entries
)
317 /* You can't shrink a set below its number of entries */
318 if (set
->entries
> entries
)
319 entries
= set
->entries
;
321 unsigned size_index
= 0;
322 while (hash_sizes
[size_index
].max_entries
< entries
)
325 set_rehash(set
, size_index
);
329 * Find a matching entry for the given key, or insert it if it doesn't already
332 * Note that insertion may rearrange the table on a resize or rehash,
333 * so previously found hash_entries are no longer valid after this function.
335 static struct set_entry
*
336 set_search_or_add(struct set
*ht
, uint32_t hash
, const void *key
, bool *found
)
338 struct set_entry
*available_entry
= NULL
;
340 if (ht
->entries
>= ht
->max_entries
) {
341 set_rehash(ht
, ht
->size_index
+ 1);
342 } else if (ht
->deleted_entries
+ ht
->entries
>= ht
->max_entries
) {
343 set_rehash(ht
, ht
->size_index
);
346 uint32_t size
= ht
->size
;
347 uint32_t start_address
= util_fast_urem32(hash
, size
, ht
->size_magic
);
348 uint32_t double_hash
= util_fast_urem32(hash
, ht
->rehash
,
349 ht
->rehash_magic
) + 1;
350 uint32_t hash_address
= start_address
;
352 struct set_entry
*entry
= ht
->table
+ hash_address
;
354 if (!entry_is_present(entry
)) {
355 /* Stash the first available entry we find */
356 if (available_entry
== NULL
)
357 available_entry
= entry
;
358 if (entry_is_free(entry
))
362 if (!entry_is_deleted(entry
) &&
363 entry
->hash
== hash
&&
364 ht
->key_equals_function(key
, entry
->key
)) {
370 hash_address
= hash_address
+ double_hash
;
371 if (hash_address
>= size
)
372 hash_address
-= size
;
373 } while (hash_address
!= start_address
);
375 if (available_entry
) {
376 /* There is no matching entry, create it. */
377 if (entry_is_deleted(available_entry
))
378 ht
->deleted_entries
--;
379 available_entry
->hash
= hash
;
380 available_entry
->key
= key
;
384 return available_entry
;
387 /* We could hit here if a required resize failed. An unchecked-malloc
388 * application could ignore this result.
394 * Inserts the key with the given hash into the table.
396 * Note that insertion may rearrange the table on a resize or rehash,
397 * so previously found hash_entries are no longer valid after this function.
399 static struct set_entry
*
400 set_add(struct set
*ht
, uint32_t hash
, const void *key
)
402 struct set_entry
*entry
= set_search_or_add(ht
, hash
, key
, NULL
);
404 if (unlikely(!entry
))
407 /* Note: If a matching entry already exists, this will replace it. This is
408 * a relatively common feature of hash tables, with the alternative
409 * generally being "insert the new value as well, and return it first when
410 * the key is searched for".
412 * Note that the hash table doesn't have a delete callback. If freeing of
413 * old keys is required to avoid memory leaks, use the alternative
414 * _mesa_set_search_or_add function and implement the replacement yourself.
421 _mesa_set_add(struct set
*set
, const void *key
)
423 assert(set
->key_hash_function
);
424 return set_add(set
, set
->key_hash_function(key
), key
);
428 _mesa_set_add_pre_hashed(struct set
*set
, uint32_t hash
, const void *key
)
430 assert(set
->key_hash_function
== NULL
||
431 hash
== set
->key_hash_function(key
));
432 return set_add(set
, hash
, key
);
436 _mesa_set_search_and_add(struct set
*set
, const void *key
, bool *replaced
)
438 assert(set
->key_hash_function
);
439 return _mesa_set_search_and_add_pre_hashed(set
,
440 set
->key_hash_function(key
),
445 _mesa_set_search_and_add_pre_hashed(struct set
*set
, uint32_t hash
,
446 const void *key
, bool *replaced
)
448 assert(set
->key_hash_function
== NULL
||
449 hash
== set
->key_hash_function(key
));
450 struct set_entry
*entry
= set_search_or_add(set
, hash
, key
, replaced
);
452 if (unlikely(!entry
))
455 /* This implements the replacement, same as _mesa_set_add(). The user will
456 * be notified if we're overwriting a found entry.
463 _mesa_set_search_or_add(struct set
*set
, const void *key
)
465 assert(set
->key_hash_function
);
466 return set_search_or_add(set
, set
->key_hash_function(key
), key
, NULL
);
470 _mesa_set_search_or_add_pre_hashed(struct set
*set
, uint32_t hash
,
473 assert(set
->key_hash_function
== NULL
||
474 hash
== set
->key_hash_function(key
));
475 return set_search_or_add(set
, hash
, key
, NULL
);
479 * This function deletes the given hash table entry.
481 * Note that deletion doesn't otherwise modify the table, so an iteration over
482 * the table deleting entries is safe.
485 _mesa_set_remove(struct set
*ht
, struct set_entry
*entry
)
490 entry
->key
= deleted_key
;
492 ht
->deleted_entries
++;
496 * Removes the entry with the corresponding key, if exists.
499 _mesa_set_remove_key(struct set
*set
, const void *key
)
501 _mesa_set_remove(set
, _mesa_set_search(set
, key
));
505 * This function is an iterator over the hash table.
507 * Pass in NULL for the first entry, as in the start of a for loop. Note that
508 * an iteration over the table is O(table_size) not O(entries).
511 _mesa_set_next_entry(const struct set
*ht
, struct set_entry
*entry
)
518 for (; entry
!= ht
->table
+ ht
->size
; entry
++) {
519 if (entry_is_present(entry
)) {
528 _mesa_set_random_entry(struct set
*ht
,
529 int (*predicate
)(struct set_entry
*entry
))
531 struct set_entry
*entry
;
532 uint32_t i
= rand() % ht
->size
;
534 if (ht
->entries
== 0)
537 for (entry
= ht
->table
+ i
; entry
!= ht
->table
+ ht
->size
; entry
++) {
538 if (entry_is_present(entry
) &&
539 (!predicate
|| predicate(entry
))) {
544 for (entry
= ht
->table
; entry
!= ht
->table
+ i
; entry
++) {
545 if (entry_is_present(entry
) &&
546 (!predicate
|| predicate(entry
))) {
555 * Helper to create a set with pointer keys.
558 _mesa_pointer_set_create(void *mem_ctx
)
560 return _mesa_set_create(mem_ctx
, _mesa_hash_pointer
,
561 _mesa_key_pointer_equal
);