android: panfrost: Redirect cmdstream includes through GenXML (v2)
[mesa.git] / src / util / set.c
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
96 key_pointer_is_reserved(const void *key)
97 {
98 return key == NULL || key == deleted_key;
99 }
100
101 static int
102 entry_is_free(struct set_entry *entry)
103 {
104 return entry->key == NULL;
105 }
106
107 static int
108 entry_is_deleted(struct set_entry *entry)
109 {
110 return entry->key == deleted_key;
111 }
112
113 static int
114 entry_is_present(struct set_entry *entry)
115 {
116 return entry->key != NULL && entry->key != deleted_key;
117 }
118
119 struct set *
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 struct set *
152 _mesa_set_clone(struct set *set, void *dst_mem_ctx)
153 {
154 struct set *clone;
155
156 clone = ralloc(dst_mem_ctx, struct set);
157 if (clone == NULL)
158 return NULL;
159
160 memcpy(clone, set, sizeof(struct set));
161
162 clone->table = ralloc_array(clone, struct set_entry, clone->size);
163 if (clone->table == NULL) {
164 ralloc_free(clone);
165 return NULL;
166 }
167
168 memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
169
170 return clone;
171 }
172
173 /**
174 * Frees the given set.
175 *
176 * If delete_function is passed, it gets called on each entry present before
177 * freeing.
178 */
179 void
180 _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
181 {
182 if (!ht)
183 return;
184
185 if (delete_function) {
186 set_foreach (ht, entry) {
187 delete_function(entry);
188 }
189 }
190 ralloc_free(ht->table);
191 ralloc_free(ht);
192 }
193
194 /**
195 * Clears all values from the given set.
196 *
197 * If delete_function is passed, it gets called on each entry present before
198 * the set is cleared.
199 */
200 void
201 _mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry))
202 {
203 if (!set)
204 return;
205
206 set_foreach (set, entry) {
207 if (delete_function)
208 delete_function(entry);
209 entry->key = deleted_key;
210 }
211
212 set->entries = set->deleted_entries = 0;
213 }
214
215 /**
216 * Finds a set entry with the given key and hash of that key.
217 *
218 * Returns NULL if no entry is found.
219 */
220 static struct set_entry *
221 set_search(const struct set *ht, uint32_t hash, const void *key)
222 {
223 assert(!key_pointer_is_reserved(key));
224
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;
230 do {
231 struct set_entry *entry = ht->table + hash_address;
232
233 if (entry_is_free(entry)) {
234 return NULL;
235 } else if (entry_is_present(entry) && entry->hash == hash) {
236 if (ht->key_equals_function(key, entry->key)) {
237 return entry;
238 }
239 }
240
241 hash_address += double_hash;
242 if (hash_address >= size)
243 hash_address -= size;
244 } while (hash_address != start_address);
245
246 return NULL;
247 }
248
249 struct set_entry *
250 _mesa_set_search(const struct set *set, const void *key)
251 {
252 assert(set->key_hash_function);
253 return set_search(set, set->key_hash_function(key), key);
254 }
255
256 struct set_entry *
257 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
258 const void *key)
259 {
260 assert(set->key_hash_function == NULL ||
261 hash == set->key_hash_function(key));
262 return set_search(set, hash, key);
263 }
264
265 static void
266 set_add_rehash(struct set *ht, uint32_t hash, const void *key)
267 {
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;
273 do {
274 struct set_entry *entry = ht->table + hash_address;
275 if (likely(entry->key == NULL)) {
276 entry->hash = hash;
277 entry->key = key;
278 return;
279 }
280
281 hash_address = hash_address + double_hash;
282 if (hash_address >= size)
283 hash_address -= size;
284 } while (true);
285 }
286
287 static void
288 set_rehash(struct set *ht, unsigned new_size_index)
289 {
290 struct set old_ht;
291 struct set_entry *table;
292
293 if (new_size_index >= ARRAY_SIZE(hash_sizes))
294 return;
295
296 table = rzalloc_array(ht, struct set_entry,
297 hash_sizes[new_size_index].size);
298 if (table == NULL)
299 return;
300
301 old_ht = *ht;
302
303 ht->table = table;
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;
310 ht->entries = 0;
311 ht->deleted_entries = 0;
312
313 set_foreach(&old_ht, entry) {
314 set_add_rehash(ht, entry->hash, entry->key);
315 }
316
317 ht->entries = old_ht.entries;
318
319 ralloc_free(old_ht.table);
320 }
321
322 void
323 _mesa_set_resize(struct set *set, uint32_t entries)
324 {
325 /* You can't shrink a set below its number of entries */
326 if (set->entries > entries)
327 entries = set->entries;
328
329 unsigned size_index = 0;
330 while (hash_sizes[size_index].max_entries < entries)
331 size_index++;
332
333 set_rehash(set, size_index);
334 }
335
336 /**
337 * Find a matching entry for the given key, or insert it if it doesn't already
338 * exist.
339 *
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.
342 */
343 static struct set_entry *
344 set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
345 {
346 struct set_entry *available_entry = NULL;
347
348 assert(!key_pointer_is_reserved(key));
349
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);
354 }
355
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;
361 do {
362 struct set_entry *entry = ht->table + hash_address;
363
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))
369 break;
370 }
371
372 if (!entry_is_deleted(entry) &&
373 entry->hash == hash &&
374 ht->key_equals_function(key, entry->key)) {
375 if (found)
376 *found = true;
377 return entry;
378 }
379
380 hash_address = hash_address + double_hash;
381 if (hash_address >= size)
382 hash_address -= size;
383 } while (hash_address != start_address);
384
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;
391 ht->entries++;
392 if (found)
393 *found = false;
394 return available_entry;
395 }
396
397 /* We could hit here if a required resize failed. An unchecked-malloc
398 * application could ignore this result.
399 */
400 return NULL;
401 }
402
403 /**
404 * Inserts the key with the given hash into the table.
405 *
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.
408 */
409 static struct set_entry *
410 set_add(struct set *ht, uint32_t hash, const void *key)
411 {
412 struct set_entry *entry = set_search_or_add(ht, hash, key, NULL);
413
414 if (unlikely(!entry))
415 return NULL;
416
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".
421 *
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.
425 */
426 entry->key = key;
427 return entry;
428 }
429
430 struct set_entry *
431 _mesa_set_add(struct set *set, const void *key)
432 {
433 assert(set->key_hash_function);
434 return set_add(set, set->key_hash_function(key), key);
435 }
436
437 struct set_entry *
438 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
439 {
440 assert(set->key_hash_function == NULL ||
441 hash == set->key_hash_function(key));
442 return set_add(set, hash, key);
443 }
444
445 struct set_entry *
446 _mesa_set_search_and_add(struct set *set, const void *key, bool *replaced)
447 {
448 assert(set->key_hash_function);
449 return _mesa_set_search_and_add_pre_hashed(set,
450 set->key_hash_function(key),
451 key, replaced);
452 }
453
454 struct set_entry *
455 _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
456 const void *key, bool *replaced)
457 {
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);
461
462 if (unlikely(!entry))
463 return NULL;
464
465 /* This implements the replacement, same as _mesa_set_add(). The user will
466 * be notified if we're overwriting a found entry.
467 */
468 entry->key = key;
469 return entry;
470 }
471
472 struct set_entry *
473 _mesa_set_search_or_add(struct set *set, const void *key)
474 {
475 assert(set->key_hash_function);
476 return set_search_or_add(set, set->key_hash_function(key), key, NULL);
477 }
478
479 struct set_entry *
480 _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
481 const void *key)
482 {
483 assert(set->key_hash_function == NULL ||
484 hash == set->key_hash_function(key));
485 return set_search_or_add(set, hash, key, NULL);
486 }
487
488 /**
489 * This function deletes the given hash table entry.
490 *
491 * Note that deletion doesn't otherwise modify the table, so an iteration over
492 * the table deleting entries is safe.
493 */
494 void
495 _mesa_set_remove(struct set *ht, struct set_entry *entry)
496 {
497 if (!entry)
498 return;
499
500 entry->key = deleted_key;
501 ht->entries--;
502 ht->deleted_entries++;
503 }
504
505 /**
506 * Removes the entry with the corresponding key, if exists.
507 */
508 void
509 _mesa_set_remove_key(struct set *set, const void *key)
510 {
511 _mesa_set_remove(set, _mesa_set_search(set, key));
512 }
513
514 /**
515 * This function is an iterator over the hash table.
516 *
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).
519 */
520 struct set_entry *
521 _mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
522 {
523 if (entry == NULL)
524 entry = ht->table;
525 else
526 entry = entry + 1;
527
528 for (; entry != ht->table + ht->size; entry++) {
529 if (entry_is_present(entry)) {
530 return entry;
531 }
532 }
533
534 return NULL;
535 }
536
537 struct set_entry *
538 _mesa_set_random_entry(struct set *ht,
539 int (*predicate)(struct set_entry *entry))
540 {
541 struct set_entry *entry;
542 uint32_t i = rand() % ht->size;
543
544 if (ht->entries == 0)
545 return NULL;
546
547 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
548 if (entry_is_present(entry) &&
549 (!predicate || predicate(entry))) {
550 return entry;
551 }
552 }
553
554 for (entry = ht->table; entry != ht->table + i; entry++) {
555 if (entry_is_present(entry) &&
556 (!predicate || predicate(entry))) {
557 return entry;
558 }
559 }
560
561 return NULL;
562 }
563
564 /**
565 * Helper to create a set with pointer keys.
566 */
567 struct set *
568 _mesa_pointer_set_create(void *mem_ctx)
569 {
570 return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
571 _mesa_key_pointer_equal);
572 }