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