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> 45#include <assert.h> 46 47#include "hash_table.h" 48#include "ralloc.h" 49#include "macros.h" 50 51static const uint32_t deleted_key_value; 52 53/** 54 * From Knuth -- a good choice for hash/rehash values is p, p-2 where 55 * p and p-2 are both prime. These tables are sized to have an extra 10% 56 * free to avoid exponential performance degradation as the hash table fills 57 */ 58static const struct { 59 uint32_t max_entries, size, rehash; 60} hash_sizes[] = { 61 { 2, 5, 3 }, 62 { 4, 7, 5 }, 63 { 8, 13, 11 }, 64 { 16, 19, 17 }, 65 { 32, 43, 41 }, 66 { 64, 73, 71 }, 67 { 128, 151, 149 }, 68 { 256, 283, 281 }, 69 { 512, 571, 569 }, 70 { 1024, 1153, 1151 }, 71 { 2048, 2269, 2267 }, 72 { 4096, 4519, 4517 }, 73 { 8192, 9013, 9011 }, 74 { 16384, 18043, 18041 }, 75 { 32768, 36109, 36107 }, 76 { 65536, 72091, 72089 }, 77 { 131072, 144409, 144407 }, 78 { 262144, 288361, 288359 }, 79 { 524288, 576883, 576881 }, 80 { 1048576, 1153459, 1153457 }, 81 { 2097152, 2307163, 2307161 }, 82 { 4194304, 4613893, 4613891 }, 83 { 8388608, 9227641, 9227639 }, 84 { 16777216, 18455029, 18455027 }, 85 { 33554432, 36911011, 36911009 }, 86 { 67108864, 73819861, 73819859 }, 87 { 134217728, 147639589, 147639587 }, 88 { 268435456, 295279081, 295279079 }, 89 { 536870912, 590559793, 590559791 }, 90 { 1073741824, 1181116273, 1181116271}, 91 { 2147483648ul, 2362232233ul, 2362232231ul} 92}; 93 94static int 95entry_is_free(const struct hash_entry *entry) 96{ 97 return entry->key == NULL; 98} 99 100static int 101entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) 102{ 103 return entry->key == ht->deleted_key; 104} 105 106static int 107entry_is_present(const struct hash_table *ht, struct hash_entry *entry) 108{ 109 return entry->key != NULL && entry->key != ht->deleted_key; 110} 111 112struct hash_table * 113_mesa_hash_table_create(void *mem_ctx, 114 uint32_t (*key_hash_function)(const void *key), 115 bool (*key_equals_function)(const void *a, 116 const void *b)) 117{ 118 struct hash_table *ht; 119 120 ht = ralloc(mem_ctx, struct hash_table); 121 if (ht == NULL) 122 return NULL; 123 124 ht->size_index = 0; 125 ht->size = hash_sizes[ht->size_index].size; 126 ht->rehash = hash_sizes[ht->size_index].rehash; 127 ht->max_entries = hash_sizes[ht->size_index].max_entries; 128 ht->key_hash_function = key_hash_function; 129 ht->key_equals_function = key_equals_function; 130 ht->table = rzalloc_array(ht, struct hash_entry, ht->size); 131 ht->entries = 0; 132 ht->deleted_entries = 0; 133 ht->deleted_key = &deleted_key_value; 134 135 if (ht->table == NULL) { 136 ralloc_free(ht); 137 return NULL; 138 } 139 140 return ht; 141} 142 143/** 144 * Frees the given hash table. 145 * 146 * If delete_function is passed, it gets called on each entry present before 147 * freeing. 148 */ 149void 150_mesa_hash_table_destroy(struct hash_table *ht, 151 void (*delete_function)(struct hash_entry *entry)) 152{ 153 if (!ht) 154 return; 155 156 if (delete_function) { 157 struct hash_entry *entry; 158 159 hash_table_foreach(ht, entry) { 160 delete_function(entry); 161 } 162 } 163 ralloc_free(ht); 164} 165 166/** 167 * Deletes all entries of the given hash table without deleting the table 168 * itself or changing its structure. 169 * 170 * If delete_function is passed, it gets called on each entry present. 171 */ 172void 173_mesa_hash_table_clear(struct hash_table *ht, 174 void (*delete_function)(struct hash_entry *entry)) 175{ 176 struct hash_entry *entry; 177 178 for (entry = ht->table; entry != ht->table + ht->size; entry++) { 179 if (entry->key == NULL) 180 continue; 181 182 if (delete_function != NULL && entry->key != ht->deleted_key) 183 delete_function(entry); 184 185 entry->key = NULL; 186 } 187 188 ht->entries = 0; 189 ht->deleted_entries = 0; 190} 191 192/** Sets the value of the key pointer used for deleted entries in the table. 193 * 194 * The assumption is that usually keys are actual pointers, so we use a 195 * default value of a pointer to an arbitrary piece of storage in the library. 196 * But in some cases a consumer wants to store some other sort of value in the 197 * table, like a uint32_t, in which case that pointer may conflict with one of 198 * their valid keys. This lets that user select a safe value. 199 * 200 * This must be called before any keys are actually deleted from the table. 201 */ 202void 203_mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key) 204{ 205 ht->deleted_key = deleted_key; 206} 207 208static struct hash_entry * 209hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) 210{ 211 uint32_t start_hash_address = hash % ht->size; 212 uint32_t hash_address = start_hash_address; 213 214 do { 215 uint32_t double_hash; 216 217 struct hash_entry *entry = ht->table + hash_address; 218 219 if (entry_is_free(entry)) { 220 return NULL; 221 } else if (entry_is_present(ht, entry) && entry->hash == hash) { 222 if (ht->key_equals_function(key, entry->key)) { 223 return entry; 224 } 225 } 226 227 double_hash = 1 + hash % ht->rehash; 228 229 hash_address = (hash_address + double_hash) % ht->size; 230 } while (hash_address != start_hash_address); 231 232 return NULL; 233} 234 235/** 236 * Finds a hash table entry with the given key and hash of that key. 237 * 238 * Returns NULL if no entry is found. Note that the data pointer may be 239 * modified by the user. 240 */ 241struct hash_entry * 242_mesa_hash_table_search(struct hash_table *ht, const void *key) 243{ 244 assert(ht->key_hash_function); 245 return hash_table_search(ht, ht->key_hash_function(key), key); 246} 247 248struct hash_entry * 249_mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, 250 const void *key) 251{ 252 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); 253 return hash_table_search(ht, hash, key); 254} 255 256static struct hash_entry * 257hash_table_insert(struct hash_table *ht, uint32_t hash, 258 const void *key, void *data); 259 260static void 261_mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) 262{ 263 struct hash_table old_ht; 264 struct hash_entry *table, *entry; 265 266 if (new_size_index >= ARRAY_SIZE(hash_sizes)) 267 return; 268 269 table = rzalloc_array(ht, struct hash_entry, 270 hash_sizes[new_size_index].size); 271 if (table == NULL) 272 return; 273 274 old_ht = *ht; 275 276 ht->table = table; 277 ht->size_index = new_size_index; 278 ht->size = hash_sizes[ht->size_index].size; 279 ht->rehash = hash_sizes[ht->size_index].rehash; 280 ht->max_entries = hash_sizes[ht->size_index].max_entries; 281 ht->entries = 0; 282 ht->deleted_entries = 0; 283 284 hash_table_foreach(&old_ht, entry) { 285 hash_table_insert(ht, entry->hash, entry->key, entry->data); 286 } 287 288 ralloc_free(old_ht.table); 289} 290 291static struct hash_entry * 292hash_table_insert(struct hash_table *ht, uint32_t hash, 293 const void *key, void *data) 294{ 295 uint32_t start_hash_address, hash_address; 296 struct hash_entry *available_entry = NULL; 297 298 assert(key != NULL); 299 300 if (ht->entries >= ht->max_entries) { 301 _mesa_hash_table_rehash(ht, ht->size_index + 1); 302 } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { 303 _mesa_hash_table_rehash(ht, ht->size_index); 304 } 305 306 start_hash_address = hash % ht->size; 307 hash_address = start_hash_address; 308 do { 309 struct hash_entry *entry = ht->table + hash_address; 310 uint32_t double_hash; 311 312 if (!entry_is_present(ht, entry)) { 313 /* Stash the first available entry we find */ 314 if (available_entry == NULL) 315 available_entry = entry; 316 if (entry_is_free(entry)) 317 break; 318 } 319 320 /* Implement replacement when another insert happens 321 * with a matching key. This is a relatively common 322 * feature of hash tables, with the alternative 323 * generally being "insert the new value as well, and 324 * return it first when the key is searched for". 325 * 326 * Note that the hash table doesn't have a delete 327 * callback. If freeing of old data pointers is 328 * required to avoid memory leaks, perform a search 329 * before inserting. 330 */ 331 if (!entry_is_deleted(ht, entry) && 332 entry->hash == hash && 333 ht->key_equals_function(key, entry->key)) { 334 entry->key = key; 335 entry->data = data; 336 return entry; 337 } 338 339 340 double_hash = 1 + hash % ht->rehash; 341 342 hash_address = (hash_address + double_hash) % ht->size; 343 } while (hash_address != start_hash_address); 344 345 if (available_entry) { 346 if (entry_is_deleted(ht, available_entry)) 347 ht->deleted_entries--; 348 available_entry->hash = hash; 349 available_entry->key = key; 350 available_entry->data = data; 351 ht->entries++; 352 return available_entry; 353 } 354 355 /* We could hit here if a required resize failed. An unchecked-malloc 356 * application could ignore this result. 357 */ 358 return NULL; 359} 360 361/** 362 * Inserts the key with the given hash into the table. 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 */ 367struct hash_entry * 368_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data) 369{ 370 assert(ht->key_hash_function); 371 return hash_table_insert(ht, ht->key_hash_function(key), key, data); 372} 373 374struct hash_entry * 375_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, 376 const void *key, void *data) 377{ 378 assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); 379 return hash_table_insert(ht, hash, key, data); 380} 381 382/** 383 * This function deletes the given hash table entry. 384 * 385 * Note that deletion doesn't otherwise modify the table, so an iteration over 386 * the table deleting entries is safe. 387 */ 388void 389_mesa_hash_table_remove(struct hash_table *ht, 390 struct hash_entry *entry) 391{ 392 if (!entry) 393 return; 394 395 entry->key = ht->deleted_key; 396 ht->entries--; 397 ht->deleted_entries++; 398} 399 400/** 401 * This function is an iterator over the hash table. 402 * 403 * Pass in NULL for the first entry, as in the start of a for loop. Note that 404 * an iteration over the table is O(table_size) not O(entries). 405 */ 406struct hash_entry * 407_mesa_hash_table_next_entry(struct hash_table *ht, 408 struct hash_entry *entry) 409{ 410 if (entry == NULL) 411 entry = ht->table; 412 else 413 entry = entry + 1; 414 415 for (; entry != ht->table + ht->size; entry++) { 416 if (entry_is_present(ht, entry)) { 417 return entry; 418 } 419 } 420 421 return NULL; 422} 423 424/** 425 * Returns a random entry from the hash table. 426 * 427 * This may be useful in implementing random replacement (as opposed 428 * to just removing everything) in caches based on this hash table 429 * implementation. @predicate may be used to filter entries, or may 430 * be set to NULL for no filtering. 431 */ 432struct hash_entry * 433_mesa_hash_table_random_entry(struct hash_table *ht, 434 bool (*predicate)(struct hash_entry *entry)) 435{ 436 struct hash_entry *entry; 437 uint32_t i = rand() % ht->size; 438 439 if (ht->entries == 0) 440 return NULL; 441 442 for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { 443 if (entry_is_present(ht, entry) && 444 (!predicate || predicate(entry))) { 445 return entry; 446 } 447 } 448 449 for (entry = ht->table; entry != ht->table + i; entry++) { 450 if (entry_is_present(ht, entry) && 451 (!predicate || predicate(entry))) { 452 return entry; 453 } 454 } 455 456 return NULL; 457} 458 459 460/** 461 * Quick FNV-1a hash implementation based on: 462 * http://www.isthe.com/chongo/tech/comp/fnv/ 463 * 464 * FNV-1a is not be the best hash out there -- Jenkins's lookup3 is supposed 465 * to be quite good, and it probably beats FNV. But FNV has the advantage 466 * that it involves almost no code. For an improvement on both, see Paul 467 * Hsieh's http://www.azillionmonkeys.com/qed/hash.html 468 */ 469uint32_t 470_mesa_hash_data(const void *data, size_t size) 471{ 472 return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias, 473 data, size); 474} 475 476/** FNV-1a string hash implementation */ 477uint32_t 478_mesa_hash_string(const char *key) 479{ 480 uint32_t hash = _mesa_fnv32_1a_offset_bias; 481 482 while (*key != 0) { 483 hash = _mesa_fnv32_1a_accumulate(hash, *key); 484 key++; 485 } 486 487 return hash; 488} 489 490/** 491 * String compare function for use as the comparison callback in 492 * _mesa_hash_table_create(). 493 */ 494bool 495_mesa_key_string_equal(const void *a, const void *b) 496{ 497 return strcmp(a, b) == 0; 498} 499 500bool 501_mesa_key_pointer_equal(const void *a, const void *b) 502{ 503 return a == b; 504} 505