Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 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 | /** |
| 36 | * Implements an open-addressing, linear-reprobing hash table. |
| 37 | * |
| 38 | * For more information, see: |
| 39 | * |
| 40 | * http://cgit.freedesktop.org/~anholt/hash_table/tree/README |
| 41 | */ |
| 42 | |
| 43 | #include <stdlib.h> |
| 44 | #include <string.h> |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 45 | #include <assert.h> |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 46 | |
Kenneth Graunke | 72e55bb | 2014-02-25 01:08:45 -0800 | [diff] [blame] | 47 | #include "hash_table.h" |
Kenneth Graunke | 72e55bb | 2014-02-25 01:08:45 -0800 | [diff] [blame] | 48 | #include "ralloc.h" |
Jason Ekstrand | efa0aa8 | 2014-07-23 14:58:52 -0700 | [diff] [blame] | 49 | #include "macros.h" |
Marek Olšák | 76f79db | 2020-03-25 21:26:24 -0400 | [diff] [blame] | 50 | #include "u_memory.h" |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 51 | #include "fast_urem_by_const.h" |
Dylan Baker | b857759 | 2018-09-12 15:56:30 -0700 | [diff] [blame] | 52 | #include "util/u_memory.h" |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 53 | |
Anthony Pesch | 931388c | 2020-01-18 00:54:10 -0500 | [diff] [blame] | 54 | #define XXH_INLINE_ALL |
| 55 | #include "xxhash.h" |
| 56 | |
Marek Olšák | 76f79db | 2020-03-25 21:26:24 -0400 | [diff] [blame] | 57 | /** |
| 58 | * Magic number that gets stored outside of the struct hash_table. |
| 59 | * |
| 60 | * The hash table needs a particular pointer to be the marker for a key that |
| 61 | * was deleted from the table, along with NULL for the "never allocated in the |
| 62 | * table" marker. Legacy GL allows any GLuint to be used as a GL object name, |
| 63 | * and we use a 1:1 mapping from GLuints to key pointers, so we need to be |
| 64 | * able to track a GLuint that happens to match the deleted key outside of |
| 65 | * struct hash_table. We tell the hash table to use "1" as the deleted key |
| 66 | * value, so that we test the deleted-key-in-the-table path as best we can. |
| 67 | */ |
| 68 | #define DELETED_KEY_VALUE 1 |
| 69 | |
| 70 | static inline void * |
| 71 | uint_key(unsigned id) |
| 72 | { |
| 73 | return (void *)(uintptr_t) id; |
| 74 | } |
| 75 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 76 | static const uint32_t deleted_key_value; |
| 77 | |
| 78 | /** |
| 79 | * From Knuth -- a good choice for hash/rehash values is p, p-2 where |
| 80 | * p and p-2 are both prime. These tables are sized to have an extra 10% |
| 81 | * free to avoid exponential performance degradation as the hash table fills |
| 82 | */ |
| 83 | static const struct { |
| 84 | uint32_t max_entries, size, rehash; |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 85 | uint64_t size_magic, rehash_magic; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 86 | } hash_sizes[] = { |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 87 | #define ENTRY(max_entries, size, rehash) \ |
| 88 | { max_entries, size, rehash, \ |
| 89 | REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) } |
| 90 | |
| 91 | ENTRY(2, 5, 3 ), |
| 92 | ENTRY(4, 7, 5 ), |
| 93 | ENTRY(8, 13, 11 ), |
| 94 | ENTRY(16, 19, 17 ), |
| 95 | ENTRY(32, 43, 41 ), |
| 96 | ENTRY(64, 73, 71 ), |
| 97 | ENTRY(128, 151, 149 ), |
| 98 | ENTRY(256, 283, 281 ), |
| 99 | ENTRY(512, 571, 569 ), |
| 100 | ENTRY(1024, 1153, 1151 ), |
| 101 | ENTRY(2048, 2269, 2267 ), |
| 102 | ENTRY(4096, 4519, 4517 ), |
| 103 | ENTRY(8192, 9013, 9011 ), |
| 104 | ENTRY(16384, 18043, 18041 ), |
| 105 | ENTRY(32768, 36109, 36107 ), |
| 106 | ENTRY(65536, 72091, 72089 ), |
| 107 | ENTRY(131072, 144409, 144407 ), |
| 108 | ENTRY(262144, 288361, 288359 ), |
| 109 | ENTRY(524288, 576883, 576881 ), |
| 110 | ENTRY(1048576, 1153459, 1153457 ), |
| 111 | ENTRY(2097152, 2307163, 2307161 ), |
| 112 | ENTRY(4194304, 4613893, 4613891 ), |
| 113 | ENTRY(8388608, 9227641, 9227639 ), |
| 114 | ENTRY(16777216, 18455029, 18455027 ), |
| 115 | ENTRY(33554432, 36911011, 36911009 ), |
| 116 | ENTRY(67108864, 73819861, 73819859 ), |
| 117 | ENTRY(134217728, 147639589, 147639587 ), |
| 118 | ENTRY(268435456, 295279081, 295279079 ), |
| 119 | ENTRY(536870912, 590559793, 590559791 ), |
| 120 | ENTRY(1073741824, 1181116273, 1181116271 ), |
| 121 | ENTRY(2147483648ul, 2362232233ul, 2362232231ul ) |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 122 | }; |
| 123 | |
Kristian H. Kristensen | f1dc4c9 | 2020-02-18 14:40:00 -0800 | [diff] [blame] | 124 | ASSERTED static inline bool |
Jason Ekstrand | b38dab1 | 2019-06-05 17:30:47 -0500 | [diff] [blame] | 125 | key_pointer_is_reserved(const struct hash_table *ht, const void *key) |
| 126 | { |
| 127 | return key == NULL || key == ht->deleted_key; |
| 128 | } |
| 129 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 130 | static int |
| 131 | entry_is_free(const struct hash_entry *entry) |
| 132 | { |
| 133 | return entry->key == NULL; |
| 134 | } |
| 135 | |
| 136 | static int |
| 137 | entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) |
| 138 | { |
| 139 | return entry->key == ht->deleted_key; |
| 140 | } |
| 141 | |
| 142 | static int |
| 143 | entry_is_present(const struct hash_table *ht, struct hash_entry *entry) |
| 144 | { |
| 145 | return entry->key != NULL && entry->key != ht->deleted_key; |
| 146 | } |
| 147 | |
Ian Romanick | e3043e1 | 2018-11-21 13:45:52 -0800 | [diff] [blame] | 148 | bool |
| 149 | _mesa_hash_table_init(struct hash_table *ht, |
| 150 | void *mem_ctx, |
| 151 | uint32_t (*key_hash_function)(const void *key), |
| 152 | bool (*key_equals_function)(const void *a, |
| 153 | const void *b)) |
| 154 | { |
| 155 | ht->size_index = 0; |
| 156 | ht->size = hash_sizes[ht->size_index].size; |
| 157 | ht->rehash = hash_sizes[ht->size_index].rehash; |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 158 | ht->size_magic = hash_sizes[ht->size_index].size_magic; |
| 159 | ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic; |
Ian Romanick | e3043e1 | 2018-11-21 13:45:52 -0800 | [diff] [blame] | 160 | ht->max_entries = hash_sizes[ht->size_index].max_entries; |
| 161 | ht->key_hash_function = key_hash_function; |
| 162 | ht->key_equals_function = key_equals_function; |
| 163 | ht->table = rzalloc_array(mem_ctx, struct hash_entry, ht->size); |
| 164 | ht->entries = 0; |
| 165 | ht->deleted_entries = 0; |
| 166 | ht->deleted_key = &deleted_key_value; |
| 167 | |
| 168 | return ht->table != NULL; |
| 169 | } |
| 170 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 171 | struct hash_table * |
| 172 | _mesa_hash_table_create(void *mem_ctx, |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 173 | uint32_t (*key_hash_function)(const void *key), |
Brian Paul | 7383373 | 2013-07-08 09:58:12 -0600 | [diff] [blame] | 174 | bool (*key_equals_function)(const void *a, |
| 175 | const void *b)) |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 176 | { |
| 177 | struct hash_table *ht; |
| 178 | |
Ian Romanick | e3043e1 | 2018-11-21 13:45:52 -0800 | [diff] [blame] | 179 | /* mem_ctx is used to allocate the hash table, but the hash table is used |
| 180 | * to allocate all of the suballocations. |
| 181 | */ |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 182 | ht = ralloc(mem_ctx, struct hash_table); |
| 183 | if (ht == NULL) |
| 184 | return NULL; |
| 185 | |
Ian Romanick | e3043e1 | 2018-11-21 13:45:52 -0800 | [diff] [blame] | 186 | if (!_mesa_hash_table_init(ht, ht, key_hash_function, key_equals_function)) { |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 187 | ralloc_free(ht); |
| 188 | return NULL; |
| 189 | } |
| 190 | |
| 191 | return ht; |
| 192 | } |
| 193 | |
Thomas Helland | 6baaf42 | 2017-01-09 23:01:50 +0100 | [diff] [blame] | 194 | struct hash_table * |
| 195 | _mesa_hash_table_clone(struct hash_table *src, void *dst_mem_ctx) |
| 196 | { |
| 197 | struct hash_table *ht; |
| 198 | |
| 199 | ht = ralloc(dst_mem_ctx, struct hash_table); |
| 200 | if (ht == NULL) |
| 201 | return NULL; |
| 202 | |
| 203 | memcpy(ht, src, sizeof(struct hash_table)); |
| 204 | |
| 205 | ht->table = ralloc_array(ht, struct hash_entry, ht->size); |
| 206 | if (ht->table == NULL) { |
| 207 | ralloc_free(ht); |
| 208 | return NULL; |
| 209 | } |
| 210 | |
| 211 | memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry)); |
| 212 | |
| 213 | return ht; |
| 214 | } |
| 215 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 216 | /** |
| 217 | * Frees the given hash table. |
| 218 | * |
| 219 | * If delete_function is passed, it gets called on each entry present before |
| 220 | * freeing. |
| 221 | */ |
| 222 | void |
| 223 | _mesa_hash_table_destroy(struct hash_table *ht, |
| 224 | void (*delete_function)(struct hash_entry *entry)) |
| 225 | { |
| 226 | if (!ht) |
| 227 | return; |
| 228 | |
| 229 | if (delete_function) { |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 230 | hash_table_foreach(ht, entry) { |
| 231 | delete_function(entry); |
| 232 | } |
| 233 | } |
| 234 | ralloc_free(ht); |
| 235 | } |
| 236 | |
Nicolai Hähnle | 8b11d8c | 2016-01-06 14:50:46 -0500 | [diff] [blame] | 237 | /** |
| 238 | * Deletes all entries of the given hash table without deleting the table |
| 239 | * itself or changing its structure. |
| 240 | * |
| 241 | * If delete_function is passed, it gets called on each entry present. |
| 242 | */ |
| 243 | void |
| 244 | _mesa_hash_table_clear(struct hash_table *ht, |
| 245 | void (*delete_function)(struct hash_entry *entry)) |
| 246 | { |
| 247 | struct hash_entry *entry; |
| 248 | |
| 249 | for (entry = ht->table; entry != ht->table + ht->size; entry++) { |
| 250 | if (entry->key == NULL) |
| 251 | continue; |
| 252 | |
| 253 | if (delete_function != NULL && entry->key != ht->deleted_key) |
| 254 | delete_function(entry); |
| 255 | |
| 256 | entry->key = NULL; |
| 257 | } |
| 258 | |
| 259 | ht->entries = 0; |
| 260 | ht->deleted_entries = 0; |
| 261 | } |
| 262 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 263 | /** Sets the value of the key pointer used for deleted entries in the table. |
| 264 | * |
| 265 | * The assumption is that usually keys are actual pointers, so we use a |
| 266 | * default value of a pointer to an arbitrary piece of storage in the library. |
| 267 | * But in some cases a consumer wants to store some other sort of value in the |
| 268 | * table, like a uint32_t, in which case that pointer may conflict with one of |
| 269 | * their valid keys. This lets that user select a safe value. |
| 270 | * |
| 271 | * This must be called before any keys are actually deleted from the table. |
| 272 | */ |
| 273 | void |
| 274 | _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key) |
| 275 | { |
| 276 | ht->deleted_key = deleted_key; |
| 277 | } |
| 278 | |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 279 | static struct hash_entry * |
| 280 | hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 281 | { |
Jason Ekstrand | b38dab1 | 2019-06-05 17:30:47 -0500 | [diff] [blame] | 282 | assert(!key_pointer_is_reserved(ht, key)); |
| 283 | |
Connor Abbott | 4512117 | 2019-05-21 12:21:53 +0200 | [diff] [blame] | 284 | uint32_t size = ht->size; |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 285 | uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic); |
| 286 | uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash, |
| 287 | ht->rehash_magic); |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 288 | uint32_t hash_address = start_hash_address; |
| 289 | |
| 290 | do { |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 291 | struct hash_entry *entry = ht->table + hash_address; |
| 292 | |
| 293 | if (entry_is_free(entry)) { |
| 294 | return NULL; |
| 295 | } else if (entry_is_present(ht, entry) && entry->hash == hash) { |
| 296 | if (ht->key_equals_function(key, entry->key)) { |
| 297 | return entry; |
| 298 | } |
| 299 | } |
| 300 | |
Connor Abbott | 4512117 | 2019-05-21 12:21:53 +0200 | [diff] [blame] | 301 | hash_address += double_hash; |
| 302 | if (hash_address >= size) |
| 303 | hash_address -= size; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 304 | } while (hash_address != start_hash_address); |
| 305 | |
| 306 | return NULL; |
| 307 | } |
| 308 | |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 309 | /** |
| 310 | * Finds a hash table entry with the given key and hash of that key. |
| 311 | * |
| 312 | * Returns NULL if no entry is found. Note that the data pointer may be |
| 313 | * modified by the user. |
| 314 | */ |
| 315 | struct hash_entry * |
| 316 | _mesa_hash_table_search(struct hash_table *ht, const void *key) |
| 317 | { |
| 318 | assert(ht->key_hash_function); |
| 319 | return hash_table_search(ht, ht->key_hash_function(key), key); |
| 320 | } |
| 321 | |
| 322 | struct hash_entry * |
| 323 | _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, |
| 324 | const void *key) |
| 325 | { |
| 326 | assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); |
| 327 | return hash_table_search(ht, hash, key); |
| 328 | } |
| 329 | |
| 330 | static struct hash_entry * |
| 331 | hash_table_insert(struct hash_table *ht, uint32_t hash, |
| 332 | const void *key, void *data); |
| 333 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 334 | static void |
Connor Abbott | 983b001 | 2019-05-21 12:36:56 +0200 | [diff] [blame] | 335 | hash_table_insert_rehash(struct hash_table *ht, uint32_t hash, |
| 336 | const void *key, void *data) |
| 337 | { |
| 338 | uint32_t size = ht->size; |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 339 | uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic); |
| 340 | uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash, |
| 341 | ht->rehash_magic); |
Connor Abbott | 983b001 | 2019-05-21 12:36:56 +0200 | [diff] [blame] | 342 | uint32_t hash_address = start_hash_address; |
Connor Abbott | 983b001 | 2019-05-21 12:36:56 +0200 | [diff] [blame] | 343 | do { |
| 344 | struct hash_entry *entry = ht->table + hash_address; |
| 345 | |
| 346 | if (likely(entry->key == NULL)) { |
| 347 | entry->hash = hash; |
| 348 | entry->key = key; |
| 349 | entry->data = data; |
| 350 | return; |
| 351 | } |
| 352 | |
| 353 | hash_address += double_hash; |
| 354 | if (hash_address >= size) |
| 355 | hash_address -= size; |
| 356 | } while (true); |
| 357 | } |
| 358 | |
| 359 | static void |
Jan Vesely | 3cb10cc | 2015-01-15 13:41:04 -0500 | [diff] [blame] | 360 | _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 361 | { |
| 362 | struct hash_table old_ht; |
Eric Engestrom | bb84fa1 | 2018-10-20 18:00:08 +0100 | [diff] [blame] | 363 | struct hash_entry *table; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 364 | |
| 365 | if (new_size_index >= ARRAY_SIZE(hash_sizes)) |
| 366 | return; |
| 367 | |
Ian Romanick | e3043e1 | 2018-11-21 13:45:52 -0800 | [diff] [blame] | 368 | table = rzalloc_array(ralloc_parent(ht->table), struct hash_entry, |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 369 | hash_sizes[new_size_index].size); |
| 370 | if (table == NULL) |
| 371 | return; |
| 372 | |
| 373 | old_ht = *ht; |
| 374 | |
| 375 | ht->table = table; |
| 376 | ht->size_index = new_size_index; |
| 377 | ht->size = hash_sizes[ht->size_index].size; |
| 378 | ht->rehash = hash_sizes[ht->size_index].rehash; |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 379 | ht->size_magic = hash_sizes[ht->size_index].size_magic; |
| 380 | ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 381 | ht->max_entries = hash_sizes[ht->size_index].max_entries; |
| 382 | ht->entries = 0; |
| 383 | ht->deleted_entries = 0; |
| 384 | |
| 385 | hash_table_foreach(&old_ht, entry) { |
Connor Abbott | 983b001 | 2019-05-21 12:36:56 +0200 | [diff] [blame] | 386 | hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data); |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 387 | } |
| 388 | |
Connor Abbott | 983b001 | 2019-05-21 12:36:56 +0200 | [diff] [blame] | 389 | ht->entries = old_ht.entries; |
| 390 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 391 | ralloc_free(old_ht.table); |
| 392 | } |
| 393 | |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 394 | static struct hash_entry * |
| 395 | hash_table_insert(struct hash_table *ht, uint32_t hash, |
| 396 | const void *key, void *data) |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 397 | { |
Jason Ekstrand | c9287e7 | 2015-02-04 18:29:32 -0800 | [diff] [blame] | 398 | struct hash_entry *available_entry = NULL; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 399 | |
Jason Ekstrand | b38dab1 | 2019-06-05 17:30:47 -0500 | [diff] [blame] | 400 | assert(!key_pointer_is_reserved(ht, key)); |
Tapani Pälli | 0abebec | 2016-08-19 14:33:13 +0300 | [diff] [blame] | 401 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 402 | if (ht->entries >= ht->max_entries) { |
| 403 | _mesa_hash_table_rehash(ht, ht->size_index + 1); |
| 404 | } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { |
| 405 | _mesa_hash_table_rehash(ht, ht->size_index); |
| 406 | } |
| 407 | |
Connor Abbott | 4512117 | 2019-05-21 12:21:53 +0200 | [diff] [blame] | 408 | uint32_t size = ht->size; |
Connor Abbott | 8c74772 | 2019-05-21 12:56:31 +0200 | [diff] [blame] | 409 | uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic); |
| 410 | uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash, |
| 411 | ht->rehash_magic); |
Connor Abbott | 4512117 | 2019-05-21 12:21:53 +0200 | [diff] [blame] | 412 | uint32_t hash_address = start_hash_address; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 413 | do { |
| 414 | struct hash_entry *entry = ht->table + hash_address; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 415 | |
| 416 | if (!entry_is_present(ht, entry)) { |
Jason Ekstrand | c9287e7 | 2015-02-04 18:29:32 -0800 | [diff] [blame] | 417 | /* Stash the first available entry we find */ |
| 418 | if (available_entry == NULL) |
| 419 | available_entry = entry; |
| 420 | if (entry_is_free(entry)) |
| 421 | break; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 422 | } |
| 423 | |
| 424 | /* Implement replacement when another insert happens |
| 425 | * with a matching key. This is a relatively common |
| 426 | * feature of hash tables, with the alternative |
| 427 | * generally being "insert the new value as well, and |
| 428 | * return it first when the key is searched for". |
| 429 | * |
| 430 | * Note that the hash table doesn't have a delete |
| 431 | * callback. If freeing of old data pointers is |
| 432 | * required to avoid memory leaks, perform a search |
| 433 | * before inserting. |
| 434 | */ |
Connor Abbott | 19db718 | 2015-11-14 20:24:31 -0500 | [diff] [blame] | 435 | if (!entry_is_deleted(ht, entry) && |
| 436 | entry->hash == hash && |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 437 | ht->key_equals_function(key, entry->key)) { |
| 438 | entry->key = key; |
| 439 | entry->data = data; |
| 440 | return entry; |
| 441 | } |
| 442 | |
Connor Abbott | 4512117 | 2019-05-21 12:21:53 +0200 | [diff] [blame] | 443 | hash_address += double_hash; |
| 444 | if (hash_address >= size) |
| 445 | hash_address -= size; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 446 | } while (hash_address != start_hash_address); |
| 447 | |
Jason Ekstrand | c9287e7 | 2015-02-04 18:29:32 -0800 | [diff] [blame] | 448 | if (available_entry) { |
| 449 | if (entry_is_deleted(ht, available_entry)) |
| 450 | ht->deleted_entries--; |
| 451 | available_entry->hash = hash; |
| 452 | available_entry->key = key; |
| 453 | available_entry->data = data; |
| 454 | ht->entries++; |
| 455 | return available_entry; |
| 456 | } |
| 457 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 458 | /* We could hit here if a required resize failed. An unchecked-malloc |
| 459 | * application could ignore this result. |
| 460 | */ |
| 461 | return NULL; |
| 462 | } |
| 463 | |
| 464 | /** |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 465 | * Inserts the key with the given hash into the table. |
| 466 | * |
| 467 | * Note that insertion may rearrange the table on a resize or rehash, |
| 468 | * so previously found hash_entries are no longer valid after this function. |
| 469 | */ |
| 470 | struct hash_entry * |
| 471 | _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data) |
| 472 | { |
| 473 | assert(ht->key_hash_function); |
Eric Anholt | 6c3115a | 2014-12-14 20:21:32 -0800 | [diff] [blame] | 474 | return hash_table_insert(ht, ht->key_hash_function(key), key, data); |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 475 | } |
| 476 | |
| 477 | struct hash_entry * |
Jason Ekstrand | 8ed5305 | 2015-01-15 07:58:07 -0800 | [diff] [blame] | 478 | _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, |
| 479 | const void *key, void *data) |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 480 | { |
| 481 | assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); |
Eric Anholt | 6c3115a | 2014-12-14 20:21:32 -0800 | [diff] [blame] | 482 | return hash_table_insert(ht, hash, key, data); |
Jason Ekstrand | 94303a0 | 2014-11-24 22:19:50 -0800 | [diff] [blame] | 483 | } |
| 484 | |
| 485 | /** |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 486 | * This function deletes the given hash table entry. |
| 487 | * |
| 488 | * Note that deletion doesn't otherwise modify the table, so an iteration over |
| 489 | * the table deleting entries is safe. |
| 490 | */ |
| 491 | void |
| 492 | _mesa_hash_table_remove(struct hash_table *ht, |
| 493 | struct hash_entry *entry) |
| 494 | { |
| 495 | if (!entry) |
| 496 | return; |
| 497 | |
| 498 | entry->key = ht->deleted_key; |
| 499 | ht->entries--; |
| 500 | ht->deleted_entries++; |
| 501 | } |
| 502 | |
| 503 | /** |
Caio Marcelo de Oliveira Filho | 4ec8b39 | 2018-07-12 11:17:04 -0700 | [diff] [blame] | 504 | * Removes the entry with the corresponding key, if exists. |
| 505 | */ |
| 506 | void _mesa_hash_table_remove_key(struct hash_table *ht, |
| 507 | const void *key) |
| 508 | { |
| 509 | _mesa_hash_table_remove(ht, _mesa_hash_table_search(ht, key)); |
| 510 | } |
| 511 | |
| 512 | /** |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 513 | * This function is an iterator over the hash table. |
| 514 | * |
| 515 | * Pass in NULL for the first entry, as in the start of a for loop. Note that |
| 516 | * an iteration over the table is O(table_size) not O(entries). |
| 517 | */ |
| 518 | struct hash_entry * |
| 519 | _mesa_hash_table_next_entry(struct hash_table *ht, |
| 520 | struct hash_entry *entry) |
| 521 | { |
| 522 | if (entry == NULL) |
| 523 | entry = ht->table; |
| 524 | else |
| 525 | entry = entry + 1; |
| 526 | |
| 527 | for (; entry != ht->table + ht->size; entry++) { |
| 528 | if (entry_is_present(ht, entry)) { |
| 529 | return entry; |
| 530 | } |
| 531 | } |
| 532 | |
| 533 | return NULL; |
| 534 | } |
| 535 | |
| 536 | /** |
| 537 | * Returns a random entry from the hash table. |
| 538 | * |
| 539 | * This may be useful in implementing random replacement (as opposed |
| 540 | * to just removing everything) in caches based on this hash table |
| 541 | * implementation. @predicate may be used to filter entries, or may |
| 542 | * be set to NULL for no filtering. |
| 543 | */ |
| 544 | struct hash_entry * |
| 545 | _mesa_hash_table_random_entry(struct hash_table *ht, |
| 546 | bool (*predicate)(struct hash_entry *entry)) |
| 547 | { |
| 548 | struct hash_entry *entry; |
Vinson Lee | bb28466 | 2012-11-12 22:15:42 -0800 | [diff] [blame] | 549 | uint32_t i = rand() % ht->size; |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 550 | |
| 551 | if (ht->entries == 0) |
| 552 | return NULL; |
| 553 | |
| 554 | for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { |
| 555 | if (entry_is_present(ht, entry) && |
| 556 | (!predicate || predicate(entry))) { |
| 557 | return entry; |
| 558 | } |
| 559 | } |
| 560 | |
| 561 | for (entry = ht->table; entry != ht->table + i; entry++) { |
| 562 | if (entry_is_present(ht, entry) && |
| 563 | (!predicate || predicate(entry))) { |
| 564 | return entry; |
| 565 | } |
| 566 | } |
| 567 | |
| 568 | return NULL; |
| 569 | } |
| 570 | |
| 571 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 572 | uint32_t |
| 573 | _mesa_hash_data(const void *data, size_t size) |
| 574 | { |
Anthony Pesch | 931388c | 2020-01-18 00:54:10 -0500 | [diff] [blame] | 575 | return XXH32(data, size, 0); |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 576 | } |
| 577 | |
Anthony Pesch | 1496cc9 | 2020-01-18 01:38:31 -0500 | [diff] [blame] | 578 | uint32_t |
| 579 | _mesa_hash_int(const void *key) |
| 580 | { |
| 581 | return XXH32(key, sizeof(int), 0); |
| 582 | } |
| 583 | |
| 584 | uint32_t |
| 585 | _mesa_hash_uint(const void *key) |
| 586 | { |
| 587 | return XXH32(key, sizeof(unsigned), 0); |
| 588 | } |
| 589 | |
| 590 | uint32_t |
| 591 | _mesa_hash_u32(const void *key) |
| 592 | { |
| 593 | return XXH32(key, 4, 0); |
| 594 | } |
| 595 | |
Timothy Arceri | b3721cd | 2014-11-18 21:58:11 +1100 | [diff] [blame] | 596 | /** FNV-1a string hash implementation */ |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 597 | uint32_t |
Lionel Landwerlin | a8b1715 | 2017-10-27 17:43:45 +0100 | [diff] [blame] | 598 | _mesa_hash_string(const void *_key) |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 599 | { |
Dmitriy Nester | 3871768 | 2020-02-27 15:17:45 +0200 | [diff] [blame] | 600 | uint32_t hash = 0; |
Lionel Landwerlin | a8b1715 | 2017-10-27 17:43:45 +0100 | [diff] [blame] | 601 | const char *key = _key; |
Dmitriy Nester | 3871768 | 2020-02-27 15:17:45 +0200 | [diff] [blame] | 602 | size_t len = strlen(key); |
| 603 | #if defined(_WIN64) || defined(__x86_64__) |
| 604 | hash = (uint32_t)XXH64(key, len, hash); |
| 605 | #else |
| 606 | hash = XXH32(key, len, hash); |
| 607 | #endif |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 608 | return hash; |
| 609 | } |
| 610 | |
Anthony Pesch | 1496cc9 | 2020-01-18 01:38:31 -0500 | [diff] [blame] | 611 | uint32_t |
| 612 | _mesa_hash_pointer(const void *pointer) |
| 613 | { |
| 614 | uintptr_t num = (uintptr_t) pointer; |
| 615 | return (uint32_t) ((num >> 2) ^ (num >> 6) ^ (num >> 10) ^ (num >> 14)); |
| 616 | } |
| 617 | |
| 618 | bool |
| 619 | _mesa_key_int_equal(const void *a, const void *b) |
| 620 | { |
| 621 | return *((const int *)a) == *((const int *)b); |
| 622 | } |
| 623 | |
| 624 | bool |
| 625 | _mesa_key_uint_equal(const void *a, const void *b) |
| 626 | { |
| 627 | |
| 628 | return *((const unsigned *)a) == *((const unsigned *)b); |
| 629 | } |
| 630 | |
| 631 | bool |
| 632 | _mesa_key_u32_equal(const void *a, const void *b) |
| 633 | { |
| 634 | return *((const uint32_t *)a) == *((const uint32_t *)b); |
| 635 | } |
| 636 | |
Eric Anholt | 35fd61b | 2012-11-06 23:18:41 -0800 | [diff] [blame] | 637 | /** |
| 638 | * String compare function for use as the comparison callback in |
| 639 | * _mesa_hash_table_create(). |
| 640 | */ |
| 641 | bool |
| 642 | _mesa_key_string_equal(const void *a, const void *b) |
| 643 | { |
| 644 | return strcmp(a, b) == 0; |
| 645 | } |
| 646 | |
| 647 | bool |
| 648 | _mesa_key_pointer_equal(const void *a, const void *b) |
| 649 | { |
| 650 | return a == b; |
| 651 | } |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 652 | |
| 653 | /** |
Caio Marcelo de Oliveira Filho | ee23e8b | 2018-09-11 16:37:33 -0700 | [diff] [blame] | 654 | * Helper to create a hash table with pointer keys. |
| 655 | */ |
| 656 | struct hash_table * |
| 657 | _mesa_pointer_hash_table_create(void *mem_ctx) |
| 658 | { |
| 659 | return _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, |
| 660 | _mesa_key_pointer_equal); |
| 661 | } |
| 662 | |
Mike Blumenkrantz | 0b96b7b | 2020-10-06 16:30:47 -0400 | [diff] [blame] | 663 | |
| 664 | bool |
| 665 | _mesa_hash_table_reserve(struct hash_table *ht, unsigned size) |
| 666 | { |
| 667 | if (size < ht->max_entries) |
| 668 | return true; |
| 669 | for (unsigned i = ht->size_index + 1; i < ARRAY_SIZE(hash_sizes); i++) { |
| 670 | if (hash_sizes[i].max_entries >= size) { |
| 671 | _mesa_hash_table_rehash(ht, i); |
| 672 | break; |
| 673 | } |
| 674 | } |
| 675 | return ht->max_entries >= size; |
| 676 | } |
| 677 | |
Caio Marcelo de Oliveira Filho | ee23e8b | 2018-09-11 16:37:33 -0700 | [diff] [blame] | 678 | /** |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 679 | * Hash table wrapper which supports 64-bit keys. |
| 680 | * |
| 681 | * TODO: unify all hash table implementations. |
| 682 | */ |
| 683 | |
| 684 | struct hash_key_u64 { |
| 685 | uint64_t value; |
| 686 | }; |
| 687 | |
| 688 | static uint32_t |
| 689 | key_u64_hash(const void *key) |
| 690 | { |
| 691 | return _mesa_hash_data(key, sizeof(struct hash_key_u64)); |
| 692 | } |
| 693 | |
| 694 | static bool |
| 695 | key_u64_equals(const void *a, const void *b) |
| 696 | { |
| 697 | const struct hash_key_u64 *aa = a; |
| 698 | const struct hash_key_u64 *bb = b; |
| 699 | |
| 700 | return aa->value == bb->value; |
| 701 | } |
| 702 | |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 703 | #define FREED_KEY_VALUE 0 |
| 704 | |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 705 | struct hash_table_u64 * |
| 706 | _mesa_hash_table_u64_create(void *mem_ctx) |
| 707 | { |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 708 | STATIC_ASSERT(FREED_KEY_VALUE != DELETED_KEY_VALUE); |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 709 | struct hash_table_u64 *ht; |
| 710 | |
| 711 | ht = CALLOC_STRUCT(hash_table_u64); |
| 712 | if (!ht) |
| 713 | return NULL; |
| 714 | |
| 715 | if (sizeof(void *) == 8) { |
| 716 | ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, |
| 717 | _mesa_key_pointer_equal); |
| 718 | } else { |
| 719 | ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash, |
| 720 | key_u64_equals); |
| 721 | } |
| 722 | |
| 723 | if (ht->table) |
| 724 | _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE)); |
| 725 | |
| 726 | return ht; |
| 727 | } |
| 728 | |
| 729 | void |
Caio Marcelo de Oliveira Filho | 608257c | 2019-06-10 14:23:34 -0700 | [diff] [blame] | 730 | _mesa_hash_table_u64_clear(struct hash_table_u64 *ht, |
| 731 | void (*delete_function)(struct hash_entry *entry)) |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 732 | { |
| 733 | if (!ht) |
| 734 | return; |
| 735 | |
| 736 | if (ht->deleted_key_data) { |
| 737 | if (delete_function) { |
| 738 | struct hash_table *table = ht->table; |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 739 | struct hash_entry entry; |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 740 | |
| 741 | /* Create a fake entry for the delete function. */ |
Tomeu Vizoso | 5804d75 | 2019-08-05 11:22:49 +0200 | [diff] [blame] | 742 | if (sizeof(void *) == 8) { |
| 743 | entry.hash = table->key_hash_function(table->deleted_key); |
| 744 | } else { |
| 745 | struct hash_key_u64 _key = { .value = (uintptr_t)table->deleted_key }; |
| 746 | entry.hash = table->key_hash_function(&_key); |
| 747 | } |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 748 | entry.key = table->deleted_key; |
| 749 | entry.data = ht->deleted_key_data; |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 750 | |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 751 | delete_function(&entry); |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 752 | } |
| 753 | ht->deleted_key_data = NULL; |
| 754 | } |
| 755 | |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 756 | if (ht->freed_key_data) { |
| 757 | if (delete_function) { |
| 758 | struct hash_table *table = ht->table; |
| 759 | struct hash_entry entry; |
| 760 | |
| 761 | /* Create a fake entry for the delete function. */ |
Tomeu Vizoso | 5804d75 | 2019-08-05 11:22:49 +0200 | [diff] [blame] | 762 | if (sizeof(void *) == 8) { |
| 763 | entry.hash = table->key_hash_function(uint_key(FREED_KEY_VALUE)); |
| 764 | } else { |
| 765 | struct hash_key_u64 _key = { .value = (uintptr_t)FREED_KEY_VALUE }; |
| 766 | entry.hash = table->key_hash_function(&_key); |
| 767 | } |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 768 | entry.key = uint_key(FREED_KEY_VALUE); |
| 769 | entry.data = ht->freed_key_data; |
| 770 | |
| 771 | delete_function(&entry); |
| 772 | } |
| 773 | ht->freed_key_data = NULL; |
| 774 | } |
| 775 | |
Caio Marcelo de Oliveira Filho | 608257c | 2019-06-10 14:23:34 -0700 | [diff] [blame] | 776 | _mesa_hash_table_clear(ht->table, delete_function); |
| 777 | } |
| 778 | |
| 779 | void |
| 780 | _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht, |
| 781 | void (*delete_function)(struct hash_entry *entry)) |
| 782 | { |
| 783 | if (!ht) |
| 784 | return; |
| 785 | |
| 786 | _mesa_hash_table_u64_clear(ht, delete_function); |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 787 | _mesa_hash_table_destroy(ht->table, delete_function); |
| 788 | free(ht); |
| 789 | } |
| 790 | |
| 791 | void |
| 792 | _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key, |
| 793 | void *data) |
| 794 | { |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 795 | if (key == FREED_KEY_VALUE) { |
| 796 | ht->freed_key_data = data; |
| 797 | return; |
| 798 | } |
| 799 | |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 800 | if (key == DELETED_KEY_VALUE) { |
| 801 | ht->deleted_key_data = data; |
| 802 | return; |
| 803 | } |
| 804 | |
| 805 | if (sizeof(void *) == 8) { |
Tapani Pälli | 8dba6f8 | 2017-07-25 08:38:03 +0300 | [diff] [blame] | 806 | _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data); |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 807 | } else { |
| 808 | struct hash_key_u64 *_key = CALLOC_STRUCT(hash_key_u64); |
| 809 | |
| 810 | if (!_key) |
| 811 | return; |
| 812 | _key->value = key; |
| 813 | |
| 814 | _mesa_hash_table_insert(ht->table, _key, data); |
| 815 | } |
| 816 | } |
| 817 | |
| 818 | static struct hash_entry * |
| 819 | hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key) |
| 820 | { |
| 821 | if (sizeof(void *) == 8) { |
Tapani Pälli | 8dba6f8 | 2017-07-25 08:38:03 +0300 | [diff] [blame] | 822 | return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key); |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 823 | } else { |
| 824 | struct hash_key_u64 _key = { .value = key }; |
| 825 | return _mesa_hash_table_search(ht->table, &_key); |
| 826 | } |
| 827 | } |
| 828 | |
| 829 | void * |
| 830 | _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key) |
| 831 | { |
| 832 | struct hash_entry *entry; |
| 833 | |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 834 | if (key == FREED_KEY_VALUE) |
| 835 | return ht->freed_key_data; |
| 836 | |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 837 | if (key == DELETED_KEY_VALUE) |
| 838 | return ht->deleted_key_data; |
| 839 | |
| 840 | entry = hash_table_u64_search(ht, key); |
| 841 | if (!entry) |
| 842 | return NULL; |
| 843 | |
| 844 | return entry->data; |
| 845 | } |
| 846 | |
| 847 | void |
| 848 | _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key) |
| 849 | { |
| 850 | struct hash_entry *entry; |
| 851 | |
Caio Marcelo de Oliveira Filho | eb41ce1 | 2019-06-10 12:10:54 -0700 | [diff] [blame] | 852 | if (key == FREED_KEY_VALUE) { |
| 853 | ht->freed_key_data = NULL; |
| 854 | return; |
| 855 | } |
| 856 | |
Samuel Pitoiset | 6649b84 | 2017-06-12 16:51:04 +0200 | [diff] [blame] | 857 | if (key == DELETED_KEY_VALUE) { |
| 858 | ht->deleted_key_data = NULL; |
| 859 | return; |
| 860 | } |
| 861 | |
| 862 | entry = hash_table_u64_search(ht, key); |
| 863 | if (!entry) |
| 864 | return; |
| 865 | |
| 866 | if (sizeof(void *) == 8) { |
| 867 | _mesa_hash_table_remove(ht->table, entry); |
| 868 | } else { |
| 869 | struct hash_key *_key = (struct hash_key *)entry->key; |
| 870 | |
| 871 | _mesa_hash_table_remove(ht->table, entry); |
| 872 | free(_key); |
| 873 | } |
| 874 | } |