Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright © 2009-2012 Intel Corporation |
| 3 | * |
| 4 | * Permission is hereby granted, free of charge, to any person obtaining a |
| 5 | * copy of this software and associated documentation files (the "Software"), |
| 6 | * to deal in the Software without restriction, including without limitation |
| 7 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| 8 | * and/or sell copies of the Software, and to permit persons to whom the |
| 9 | * Software is furnished to do so, subject to the following conditions: |
| 10 | * |
| 11 | * The above copyright notice and this permission notice (including the next |
| 12 | * paragraph) shall be included in all copies or substantial portions of the |
| 13 | * Software. |
| 14 | * |
| 15 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 16 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 17 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| 18 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 19 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| 20 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
| 21 | * IN THE SOFTWARE. |
| 22 | * |
| 23 | * Authors: |
| 24 | * Eric Anholt <eric@anholt.net> |
| 25 | * |
| 26 | */ |
| 27 | |
| 28 | #ifndef _SET_H |
| 29 | #define _SET_H |
| 30 | |
| 31 | #include <inttypes.h> |
| 32 | #include <stdbool.h> |
| 33 | |
| 34 | #ifdef __cplusplus |
| 35 | extern "C" { |
| 36 | #endif |
| 37 | |
| 38 | struct set_entry { |
| 39 | uint32_t hash; |
| 40 | const void *key; |
| 41 | }; |
| 42 | |
| 43 | struct set { |
| 44 | void *mem_ctx; |
| 45 | struct set_entry *table; |
Jason Ekstrand | 153b8b3 | 2015-01-15 09:31:18 -0800 | [diff] [blame] | 46 | uint32_t (*key_hash_function)(const void *key); |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 47 | bool (*key_equals_function)(const void *a, const void *b); |
| 48 | uint32_t size; |
| 49 | uint32_t rehash; |
Connor Abbott | 83667f7 | 2019-05-20 15:14:04 +0200 | [diff] [blame] | 50 | uint64_t size_magic; |
| 51 | uint64_t rehash_magic; |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 52 | uint32_t max_entries; |
| 53 | uint32_t size_index; |
| 54 | uint32_t entries; |
| 55 | uint32_t deleted_entries; |
| 56 | }; |
| 57 | |
| 58 | struct set * |
| 59 | _mesa_set_create(void *mem_ctx, |
Jason Ekstrand | 153b8b3 | 2015-01-15 09:31:18 -0800 | [diff] [blame] | 60 | uint32_t (*key_hash_function)(const void *key), |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 61 | bool (*key_equals_function)(const void *a, |
| 62 | const void *b)); |
Caio Marcelo de Oliveira Filho | b034fac | 2018-06-25 09:51:20 -0700 | [diff] [blame] | 63 | struct set * |
Marek Olšák | 10a7682 | 2020-09-29 17:29:09 -0400 | [diff] [blame] | 64 | _mesa_set_create_u32_keys(void *mem_ctx); |
| 65 | |
| 66 | struct set * |
Caio Marcelo de Oliveira Filho | b034fac | 2018-06-25 09:51:20 -0700 | [diff] [blame] | 67 | _mesa_set_clone(struct set *set, void *dst_mem_ctx); |
| 68 | |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 69 | void |
| 70 | _mesa_set_destroy(struct set *set, |
| 71 | void (*delete_function)(struct set_entry *entry)); |
Scott D Phillips | 5c075b0 | 2018-05-02 09:01:02 -0700 | [diff] [blame] | 72 | void |
Jason Ekstrand | bab08c7 | 2019-05-10 13:50:56 -0500 | [diff] [blame] | 73 | _mesa_set_resize(struct set *set, uint32_t entries); |
| 74 | void |
Scott D Phillips | 5c075b0 | 2018-05-02 09:01:02 -0700 | [diff] [blame] | 75 | _mesa_set_clear(struct set *set, |
| 76 | void (*delete_function)(struct set_entry *entry)); |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 77 | |
| 78 | struct set_entry * |
Jason Ekstrand | 153b8b3 | 2015-01-15 09:31:18 -0800 | [diff] [blame] | 79 | _mesa_set_add(struct set *set, const void *key); |
| 80 | struct set_entry * |
| 81 | _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key); |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 82 | |
| 83 | struct set_entry * |
Connor Abbott | 8a838e1 | 2019-03-27 12:00:54 +0100 | [diff] [blame] | 84 | _mesa_set_search_or_add(struct set *set, const void *key); |
| 85 | struct set_entry * |
| 86 | _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash, |
| 87 | const void *key); |
| 88 | |
| 89 | struct set_entry * |
Jason Ekstrand | 153b8b3 | 2015-01-15 09:31:18 -0800 | [diff] [blame] | 90 | _mesa_set_search(const struct set *set, const void *key); |
| 91 | struct set_entry * |
| 92 | _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash, |
| 93 | const void *key); |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 94 | |
Jason Ekstrand | abb4508 | 2019-05-10 13:37:42 -0500 | [diff] [blame] | 95 | struct set_entry * |
| 96 | _mesa_set_search_and_add(struct set *set, const void *key, bool *replaced); |
| 97 | struct set_entry * |
| 98 | _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash, |
| 99 | const void *key, bool *replaced); |
| 100 | |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 101 | void |
| 102 | _mesa_set_remove(struct set *set, struct set_entry *entry); |
Caio Marcelo de Oliveira Filho | fa0c19d | 2018-06-25 13:42:22 -0700 | [diff] [blame] | 103 | void |
| 104 | _mesa_set_remove_key(struct set *set, const void *key); |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 105 | |
| 106 | struct set_entry * |
| 107 | _mesa_set_next_entry(const struct set *set, struct set_entry *entry); |
| 108 | |
| 109 | struct set_entry * |
| 110 | _mesa_set_random_entry(struct set *set, |
| 111 | int (*predicate)(struct set_entry *entry)); |
| 112 | |
Caio Marcelo de Oliveira Filho | ee23e8b | 2018-09-11 16:37:33 -0700 | [diff] [blame] | 113 | struct set * |
| 114 | _mesa_pointer_set_create(void *mem_ctx); |
| 115 | |
Karol Herbst | 16f8589 | 2020-05-15 11:11:13 +0200 | [diff] [blame] | 116 | bool |
| 117 | _mesa_set_intersects(struct set *a, struct set *b); |
| 118 | |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 119 | /** |
| 120 | * This foreach function is safe against deletion, but not against |
| 121 | * insertion (which may rehash the set, making entry a dangling |
| 122 | * pointer). |
| 123 | */ |
Eric Engestrom | e27902a | 2018-10-20 18:00:09 +0100 | [diff] [blame] | 124 | #define set_foreach(set, entry) \ |
| 125 | for (struct set_entry *entry = _mesa_set_next_entry(set, NULL); \ |
| 126 | entry != NULL; \ |
Eric Anholt | 82c9d98 | 2012-12-04 01:03:57 -0800 | [diff] [blame] | 127 | entry = _mesa_set_next_entry(set, entry)) |
| 128 | |
| 129 | #ifdef __cplusplus |
| 130 | } /* extern C */ |
| 131 | #endif |
| 132 | |
| 133 | #endif /* _SET_H */ |