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 uint32_t
 550 _mesa_hash_data(const void *data, size_t size)
 551 {
 552    return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
 553                                           data, size);
 554 }
 555
 556 /** FNV-1a string hash implementation */
 557 uint32_t
 558 _mesa_hash_string(const void *_key)
 559 {
 560    uint32_t hash = _mesa_fnv32_1a_offset_bias;
 561    const char *key = _key;
 562
 563    while (*key != 0) {
 564       hash = _mesa_fnv32_1a_accumulate(hash, *key);
 565       key++;
 566    }
 567
 568    return hash;
 569 }
 570
 571 /**
 572  * String compare function for use as the comparison callback in
 573  * _mesa_hash_table_create().
 574  */
 575 bool
 576 _mesa_key_string_equal(const void *a, const void *b)
 577 {
 578    return strcmp(a, b) == 0;
 579 }
 580
 581 bool
 582 _mesa_key_pointer_equal(const void *a, const void *b)
 583 {
 584    return a == b;
 585 }
 586
 587 /**
 588  * Helper to create a hash table with pointer keys.
 589  */
 590 struct hash_table *
 591 _mesa_pointer_hash_table_create(void *mem_ctx)
 592 {
 593    return _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
 594                                   _mesa_key_pointer_equal);
 595 }
 596
 597 /**
 598  * Hash table wrapper which supports 64-bit keys.
 599  *
 600  * TODO: unify all hash table implementations.
 601  */
 602
 603 struct hash_key_u64 {
 604    uint64_t value;
 605 };
 606
 607 static uint32_t
 608 key_u64_hash(const void *key)
 609 {
 610    return _mesa_hash_data(key, sizeof(struct hash_key_u64));
 611 }
 612
 613 static bool
 614 key_u64_equals(const void *a, const void *b)
 615 {
 616    const struct hash_key_u64 *aa = a;
 617    const struct hash_key_u64 *bb = b;
 618
 619    return aa->value == bb->value;
 620 }
 621
 622 #define FREED_KEY_VALUE 0
 623
 624 struct hash_table_u64 *
 625 _mesa_hash_table_u64_create(void *mem_ctx)
 626 {
 627    STATIC_ASSERT(FREED_KEY_VALUE != DELETED_KEY_VALUE);
 628    struct hash_table_u64 *ht;
 629
 630    ht = CALLOC_STRUCT(hash_table_u64);
 631    if (!ht)
 632       return NULL;
 633
 634    if (sizeof(void *) == 8) {
 635       ht->table = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
 636                                           _mesa_key_pointer_equal);
 637    } else {
 638       ht->table = _mesa_hash_table_create(mem_ctx, key_u64_hash,
 639                                           key_u64_equals);
 640    }
 641
 642    if (ht->table)
 643       _mesa_hash_table_set_deleted_key(ht->table, uint_key(DELETED_KEY_VALUE));
 644
 645    return ht;
 646 }
 647
 648 void
 649 _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
 650                            void (*delete_function)(struct hash_entry *entry))
 651 {
 652    if (!ht)
 653       return;
 654
 655    if (ht->deleted_key_data) {
 656       if (delete_function) {
 657          struct hash_table *table = ht->table;
 658          struct hash_entry entry;
 659
 660          /* Create a fake entry for the delete function. */
 661          if (sizeof(void *) == 8) {
 662             entry.hash = table->key_hash_function(table->deleted_key);
 663          } else {
 664             struct hash_key_u64 _key = { .value = (uintptr_t)table->deleted_key };
 665             entry.hash = table->key_hash_function(&_key);
 666          }
 667          entry.key = table->deleted_key;
 668          entry.data = ht->deleted_key_data;
 669
 670          delete_function(&entry);
 671       }
 672       ht->deleted_key_data = NULL;
 673    }
 674
 675    if (ht->freed_key_data) {
 676       if (delete_function) {
 677          struct hash_table *table = ht->table;
 678          struct hash_entry entry;
 679
 680          /* Create a fake entry for the delete function. */
 681          if (sizeof(void *) == 8) {
 682             entry.hash = table->key_hash_function(uint_key(FREED_KEY_VALUE));
 683          } else {
 684             struct hash_key_u64 _key = { .value = (uintptr_t)FREED_KEY_VALUE };
 685             entry.hash = table->key_hash_function(&_key);
 686          }
 687          entry.key = uint_key(FREED_KEY_VALUE);
 688          entry.data = ht->freed_key_data;
 689
 690          delete_function(&entry);
 691       }
 692       ht->freed_key_data = NULL;
 693    }
 694
 695    _mesa_hash_table_clear(ht->table, delete_function);
 696 }
 697
 698 void
 699 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht,
 700                              void (*delete_function)(struct hash_entry *entry))
 701 {
 702    if (!ht)
 703       return;
 704
 705    _mesa_hash_table_u64_clear(ht, delete_function);
 706    _mesa_hash_table_destroy(ht->table, delete_function);
 707    free(ht);
 708 }
 709
 710 void
 711 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
 712                             void *data)
 713 {
 714    if (key == FREED_KEY_VALUE) {
 715       ht->freed_key_data = data;
 716       return;
 717    }
 718
 719    if (key == DELETED_KEY_VALUE) {
 720       ht->deleted_key_data = data;
 721       return;
 722    }
 723
 724    if (sizeof(void *) == 8) {
 725       _mesa_hash_table_insert(ht->table, (void *)(uintptr_t)key, data);
 726    } else {
 727       struct hash_key_u64 *_key = CALLOC_STRUCT(hash_key_u64);
 728
 729       if (!_key)
 730          return;
 731       _key->value = key;
 732
 733       _mesa_hash_table_insert(ht->table, _key, data);
 734    }
 735 }
 736
 737 static struct hash_entry *
 738 hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
 739 {
 740    if (sizeof(void *) == 8) {
 741       return _mesa_hash_table_search(ht->table, (void *)(uintptr_t)key);
 742    } else {
 743       struct hash_key_u64 _key = { .value = key };
 744       return _mesa_hash_table_search(ht->table, &_key);
 745    }
 746 }
 747
 748 void *
 749 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key)
 750 {
 751    struct hash_entry *entry;
 752
 753    if (key == FREED_KEY_VALUE)
 754       return ht->freed_key_data;
 755
 756    if (key == DELETED_KEY_VALUE)
 757       return ht->deleted_key_data;
 758
 759    entry = hash_table_u64_search(ht, key);
 760    if (!entry)
 761       return NULL;
 762
 763    return entry->data;
 764 }
 765
 766 void
 767 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key)
 768 {
 769    struct hash_entry *entry;
 770
 771    if (key == FREED_KEY_VALUE) {
 772       ht->freed_key_data = NULL;
 773       return;
 774    }
 775
 776    if (key == DELETED_KEY_VALUE) {
 777       ht->deleted_key_data = NULL;
 778       return;
 779    }
 780
 781    entry = hash_table_u64_search(ht, key);
 782    if (!entry)
 783       return;
 784
 785    if (sizeof(void *) == 8) {
 786       _mesa_hash_table_remove(ht->table, entry);
 787    } else {
 788       struct hash_key *_key = (struct hash_key *)entry->key;
 789
 790       _mesa_hash_table_remove(ht->table, entry);
 791       free(_key);
 792    }
 793 }