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