1 /*
2 * Copyright © 2009-2012 Intel Corporation
3 * Copyright © 1988-2004 Keith Packard and Bart Massey.
4 *
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:
11 *
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
14 * Software.
15 *
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
22 * IN THE SOFTWARE.
23 *
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
28 * authors.
29 *
30 * Authors:
31 * Eric Anholt <eric@anholt.net>
32 * Keith Packard <keithp@keithp.com>
33 */
34
35 #include <stdlib.h>
36 #include <assert.h>
37 #include <string.h>
38
39 #include "hash_table.h"
40 #include "macros.h"
41 #include "ralloc.h"
42 #include "set.h"
43 #include "fast_urem_by_const.h"
44
45 /*
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
49 */
50
51 static const uint32_t deleted_key_value;
52 static const void *deleted_key = &deleted_key_value;
53
54 static const struct {
55 uint32_t max_entries, size, rehash;
56 uint64_t size_magic, rehash_magic;
57 } hash_sizes[] = {
58 #define ENTRY(max_entries, size, rehash) \
59 { max_entries, size, rehash, \
60 REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
61
62 ENTRY(2, 5, 3 ),
63 ENTRY(4, 7, 5 ),
64 ENTRY(8, 13, 11 ),
65 ENTRY(16, 19, 17 ),
66 ENTRY(32, 43, 41 ),
67 ENTRY(64, 73, 71 ),
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 )
93 };
94
95 ASSERTED static inline bool
key_pointer_is_reserved(const void * key)96 key_pointer_is_reserved(const void *key)
97 {
98 return key == NULL || key == deleted_key;
99 }
100
101 static int
entry_is_free(struct set_entry * entry)102 entry_is_free(struct set_entry *entry)
103 {
104 return entry->key == NULL;
105 }
106
107 static int
entry_is_deleted(struct set_entry * entry)108 entry_is_deleted(struct set_entry *entry)
109 {
110 return entry->key == deleted_key;
111 }
112
113 static int
entry_is_present(struct set_entry * entry)114 entry_is_present(struct set_entry *entry)
115 {
116 return entry->key != NULL && entry->key != deleted_key;
117 }
118
119 struct set *
_mesa_set_create(void * mem_ctx,uint32_t (* key_hash_function)(const void * key),bool (* key_equals_function)(const void * a,const void * b))120 _mesa_set_create(void *mem_ctx,
121 uint32_t (*key_hash_function)(const void *key),
122 bool (*key_equals_function)(const void *a,
123 const void *b))
124 {
125 struct set *ht;
126
127 ht = ralloc(mem_ctx, struct set);
128 if (ht == NULL)
129 return NULL;
130
131 ht->size_index = 0;
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);
140 ht->entries = 0;
141 ht->deleted_entries = 0;
142
143 if (ht->table == NULL) {
144 ralloc_free(ht);
145 return NULL;
146 }
147
148 return ht;
149 }
150
151 static uint32_t
key_u32_hash(const void * key)152 key_u32_hash(const void *key)
153 {
154 uint32_t u = (uint32_t)(uintptr_t)key;
155 return _mesa_hash_uint(&u);
156 }
157
158 static bool
key_u32_equals(const void * a,const void * b)159 key_u32_equals(const void *a, const void *b)
160 {
161 return (uint32_t)(uintptr_t)a == (uint32_t)(uintptr_t)b;
162 }
163
164 /* key == 0 and key == deleted_key are not allowed */
165 struct set *
_mesa_set_create_u32_keys(void * mem_ctx)166 _mesa_set_create_u32_keys(void *mem_ctx)
167 {
168 return _mesa_set_create(NULL, key_u32_hash, key_u32_equals);
169 }
170
171 struct set *
_mesa_set_clone(struct set * set,void * dst_mem_ctx)172 _mesa_set_clone(struct set *set, void *dst_mem_ctx)
173 {
174 struct set *clone;
175
176 clone = ralloc(dst_mem_ctx, struct set);
177 if (clone == NULL)
178 return NULL;
179
180 memcpy(clone, set, sizeof(struct set));
181
182 clone->table = ralloc_array(clone, struct set_entry, clone->size);
183 if (clone->table == NULL) {
184 ralloc_free(clone);
185 return NULL;
186 }
187
188 memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
189
190 return clone;
191 }
192
193 /**
194 * Frees the given set.
195 *
196 * If delete_function is passed, it gets called on each entry present before
197 * freeing.
198 */
199 void
_mesa_set_destroy(struct set * ht,void (* delete_function)(struct set_entry * entry))200 _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
201 {
202 if (!ht)
203 return;
204
205 if (delete_function) {
206 set_foreach (ht, entry) {
207 delete_function(entry);
208 }
209 }
210 ralloc_free(ht->table);
211 ralloc_free(ht);
212 }
213
214 /**
215 * Clears all values from the given set.
216 *
217 * If delete_function is passed, it gets called on each entry present before
218 * the set is cleared.
219 */
220 void
_mesa_set_clear(struct set * set,void (* delete_function)(struct set_entry * entry))221 _mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry))
222 {
223 if (!set)
224 return;
225
226 struct set_entry *entry;
227
228 for (entry = set->table; entry != set->table + set->size; entry++) {
229 if (entry_is_present(entry) && delete_function != NULL)
230 delete_function(entry);
231
232 entry->key = NULL;
233 }
234
235 set->entries = 0;
236 set->deleted_entries = 0;
237 }
238
239 /**
240 * Finds a set entry with the given key and hash of that key.
241 *
242 * Returns NULL if no entry is found.
243 */
244 static struct set_entry *
set_search(const struct set * ht,uint32_t hash,const void * key)245 set_search(const struct set *ht, uint32_t hash, const void *key)
246 {
247 assert(!key_pointer_is_reserved(key));
248
249 uint32_t size = ht->size;
250 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
251 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
252 ht->rehash_magic) + 1;
253 uint32_t hash_address = start_address;
254 do {
255 struct set_entry *entry = ht->table + hash_address;
256
257 if (entry_is_free(entry)) {
258 return NULL;
259 } else if (entry_is_present(entry) && entry->hash == hash) {
260 if (ht->key_equals_function(key, entry->key)) {
261 return entry;
262 }
263 }
264
265 hash_address += double_hash;
266 if (hash_address >= size)
267 hash_address -= size;
268 } while (hash_address != start_address);
269
270 return NULL;
271 }
272
273 struct set_entry *
_mesa_set_search(const struct set * set,const void * key)274 _mesa_set_search(const struct set *set, const void *key)
275 {
276 assert(set->key_hash_function);
277 return set_search(set, set->key_hash_function(key), key);
278 }
279
280 struct set_entry *
_mesa_set_search_pre_hashed(const struct set * set,uint32_t hash,const void * key)281 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
282 const void *key)
283 {
284 assert(set->key_hash_function == NULL ||
285 hash == set->key_hash_function(key));
286 return set_search(set, hash, key);
287 }
288
289 static void
set_add_rehash(struct set * ht,uint32_t hash,const void * key)290 set_add_rehash(struct set *ht, uint32_t hash, const void *key)
291 {
292 uint32_t size = ht->size;
293 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
294 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
295 ht->rehash_magic) + 1;
296 uint32_t hash_address = start_address;
297 do {
298 struct set_entry *entry = ht->table + hash_address;
299 if (likely(entry->key == NULL)) {
300 entry->hash = hash;
301 entry->key = key;
302 return;
303 }
304
305 hash_address = hash_address + double_hash;
306 if (hash_address >= size)
307 hash_address -= size;
308 } while (true);
309 }
310
311 static void
set_rehash(struct set * ht,unsigned new_size_index)312 set_rehash(struct set *ht, unsigned new_size_index)
313 {
314 struct set old_ht;
315 struct set_entry *table;
316
317 if (new_size_index >= ARRAY_SIZE(hash_sizes))
318 return;
319
320 table = rzalloc_array(ht, struct set_entry,
321 hash_sizes[new_size_index].size);
322 if (table == NULL)
323 return;
324
325 old_ht = *ht;
326
327 ht->table = table;
328 ht->size_index = new_size_index;
329 ht->size = hash_sizes[ht->size_index].size;
330 ht->rehash = hash_sizes[ht->size_index].rehash;
331 ht->size_magic = hash_sizes[ht->size_index].size_magic;
332 ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
333 ht->max_entries = hash_sizes[ht->size_index].max_entries;
334 ht->entries = 0;
335 ht->deleted_entries = 0;
336
337 set_foreach(&old_ht, entry) {
338 set_add_rehash(ht, entry->hash, entry->key);
339 }
340
341 ht->entries = old_ht.entries;
342
343 ralloc_free(old_ht.table);
344 }
345
346 void
_mesa_set_resize(struct set * set,uint32_t entries)347 _mesa_set_resize(struct set *set, uint32_t entries)
348 {
349 /* You can't shrink a set below its number of entries */
350 if (set->entries > entries)
351 entries = set->entries;
352
353 unsigned size_index = 0;
354 while (hash_sizes[size_index].max_entries < entries)
355 size_index++;
356
357 set_rehash(set, size_index);
358 }
359
360 /**
361 * Find a matching entry for the given key, or insert it if it doesn't already
362 * exist.
363 *
364 * Note that insertion may rearrange the table on a resize or rehash,
365 * so previously found hash_entries are no longer valid after this function.
366 */
367 static struct set_entry *
set_search_or_add(struct set * ht,uint32_t hash,const void * key,bool * found)368 set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
369 {
370 struct set_entry *available_entry = NULL;
371
372 assert(!key_pointer_is_reserved(key));
373
374 if (ht->entries >= ht->max_entries) {
375 set_rehash(ht, ht->size_index + 1);
376 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
377 set_rehash(ht, ht->size_index);
378 }
379
380 uint32_t size = ht->size;
381 uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
382 uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
383 ht->rehash_magic) + 1;
384 uint32_t hash_address = start_address;
385 do {
386 struct set_entry *entry = ht->table + hash_address;
387
388 if (!entry_is_present(entry)) {
389 /* Stash the first available entry we find */
390 if (available_entry == NULL)
391 available_entry = entry;
392 if (entry_is_free(entry))
393 break;
394 }
395
396 if (!entry_is_deleted(entry) &&
397 entry->hash == hash &&
398 ht->key_equals_function(key, entry->key)) {
399 if (found)
400 *found = true;
401 return entry;
402 }
403
404 hash_address = hash_address + double_hash;
405 if (hash_address >= size)
406 hash_address -= size;
407 } while (hash_address != start_address);
408
409 if (available_entry) {
410 /* There is no matching entry, create it. */
411 if (entry_is_deleted(available_entry))
412 ht->deleted_entries--;
413 available_entry->hash = hash;
414 available_entry->key = key;
415 ht->entries++;
416 if (found)
417 *found = false;
418 return available_entry;
419 }
420
421 /* We could hit here if a required resize failed. An unchecked-malloc
422 * application could ignore this result.
423 */
424 return NULL;
425 }
426
427 /**
428 * Inserts the key with the given hash into the table.
429 *
430 * Note that insertion may rearrange the table on a resize or rehash,
431 * so previously found hash_entries are no longer valid after this function.
432 */
433 static struct set_entry *
set_add(struct set * ht,uint32_t hash,const void * key)434 set_add(struct set *ht, uint32_t hash, const void *key)
435 {
436 struct set_entry *entry = set_search_or_add(ht, hash, key, NULL);
437
438 if (unlikely(!entry))
439 return NULL;
440
441 /* Note: If a matching entry already exists, this will replace it. This is
442 * a relatively common feature of hash tables, with the alternative
443 * generally being "insert the new value as well, and return it first when
444 * the key is searched for".
445 *
446 * Note that the hash table doesn't have a delete callback. If freeing of
447 * old keys is required to avoid memory leaks, use the alternative
448 * _mesa_set_search_or_add function and implement the replacement yourself.
449 */
450 entry->key = key;
451 return entry;
452 }
453
454 struct set_entry *
_mesa_set_add(struct set * set,const void * key)455 _mesa_set_add(struct set *set, const void *key)
456 {
457 assert(set->key_hash_function);
458 return set_add(set, set->key_hash_function(key), key);
459 }
460
461 struct set_entry *
_mesa_set_add_pre_hashed(struct set * set,uint32_t hash,const void * key)462 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
463 {
464 assert(set->key_hash_function == NULL ||
465 hash == set->key_hash_function(key));
466 return set_add(set, hash, key);
467 }
468
469 struct set_entry *
_mesa_set_search_and_add(struct set * set,const void * key,bool * replaced)470 _mesa_set_search_and_add(struct set *set, const void *key, bool *replaced)
471 {
472 assert(set->key_hash_function);
473 return _mesa_set_search_and_add_pre_hashed(set,
474 set->key_hash_function(key),
475 key, replaced);
476 }
477
478 struct set_entry *
_mesa_set_search_and_add_pre_hashed(struct set * set,uint32_t hash,const void * key,bool * replaced)479 _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
480 const void *key, bool *replaced)
481 {
482 assert(set->key_hash_function == NULL ||
483 hash == set->key_hash_function(key));
484 struct set_entry *entry = set_search_or_add(set, hash, key, replaced);
485
486 if (unlikely(!entry))
487 return NULL;
488
489 /* This implements the replacement, same as _mesa_set_add(). The user will
490 * be notified if we're overwriting a found entry.
491 */
492 entry->key = key;
493 return entry;
494 }
495
496 struct set_entry *
_mesa_set_search_or_add(struct set * set,const void * key)497 _mesa_set_search_or_add(struct set *set, const void *key)
498 {
499 assert(set->key_hash_function);
500 return set_search_or_add(set, set->key_hash_function(key), key, NULL);
501 }
502
503 struct set_entry *
_mesa_set_search_or_add_pre_hashed(struct set * set,uint32_t hash,const void * key)504 _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
505 const void *key)
506 {
507 assert(set->key_hash_function == NULL ||
508 hash == set->key_hash_function(key));
509 return set_search_or_add(set, hash, key, NULL);
510 }
511
512 /**
513 * This function deletes the given hash table entry.
514 *
515 * Note that deletion doesn't otherwise modify the table, so an iteration over
516 * the table deleting entries is safe.
517 */
518 void
_mesa_set_remove(struct set * ht,struct set_entry * entry)519 _mesa_set_remove(struct set *ht, struct set_entry *entry)
520 {
521 if (!entry)
522 return;
523
524 entry->key = deleted_key;
525 ht->entries--;
526 ht->deleted_entries++;
527 }
528
529 /**
530 * Removes the entry with the corresponding key, if exists.
531 */
532 void
_mesa_set_remove_key(struct set * set,const void * key)533 _mesa_set_remove_key(struct set *set, const void *key)
534 {
535 _mesa_set_remove(set, _mesa_set_search(set, key));
536 }
537
538 /**
539 * This function is an iterator over the hash table.
540 *
541 * Pass in NULL for the first entry, as in the start of a for loop. Note that
542 * an iteration over the table is O(table_size) not O(entries).
543 */
544 struct set_entry *
_mesa_set_next_entry(const struct set * ht,struct set_entry * entry)545 _mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
546 {
547 if (entry == NULL)
548 entry = ht->table;
549 else
550 entry = entry + 1;
551
552 for (; entry != ht->table + ht->size; entry++) {
553 if (entry_is_present(entry)) {
554 return entry;
555 }
556 }
557
558 return NULL;
559 }
560
561 struct set_entry *
_mesa_set_random_entry(struct set * ht,int (* predicate)(struct set_entry * entry))562 _mesa_set_random_entry(struct set *ht,
563 int (*predicate)(struct set_entry *entry))
564 {
565 struct set_entry *entry;
566 uint32_t i = rand() % ht->size;
567
568 if (ht->entries == 0)
569 return NULL;
570
571 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
572 if (entry_is_present(entry) &&
573 (!predicate || predicate(entry))) {
574 return entry;
575 }
576 }
577
578 for (entry = ht->table; entry != ht->table + i; entry++) {
579 if (entry_is_present(entry) &&
580 (!predicate || predicate(entry))) {
581 return entry;
582 }
583 }
584
585 return NULL;
586 }
587
588 /**
589 * Helper to create a set with pointer keys.
590 */
591 struct set *
_mesa_pointer_set_create(void * mem_ctx)592 _mesa_pointer_set_create(void *mem_ctx)
593 {
594 return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
595 _mesa_key_pointer_equal);
596 }
597
598 bool
_mesa_set_intersects(struct set * a,struct set * b)599 _mesa_set_intersects(struct set *a, struct set *b)
600 {
601 assert(a->key_hash_function == b->key_hash_function);
602 assert(a->key_equals_function == b->key_equals_function);
603
604 /* iterate over the set with less entries */
605 if (b->entries < a->entries) {
606 struct set *tmp = a;
607 a = b;
608 b = tmp;
609 }
610
611 set_foreach(a, entry) {
612 if (_mesa_set_search_pre_hashed(b, entry->hash, entry->key))
613 return true;
614 }
615 return false;
616 }
617