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