src/util/set.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 #include <stdlib.h>
  36 #include <assert.h>
  37 #include <string.h>
  38
  39 #include "hash_table.h"
  40 #include "macros.h"
  41 #include "ralloc.h"
  42 #include "set.h"
  43 #include "fast_urem_by_const.h"
  44
  45 /*
  46  * From Knuth -- a good choice for hash/rehash values is p, p-2 where
  47  * p and p-2 are both prime.  These tables are sized to have an extra 10%
  48  * free to avoid exponential performance degradation as the hash table fills
  49  */
  50
  51 static const uint32_t deleted_key_value;
  52 static const void *deleted_key = &deleted_key_value;
  53
  54 static const struct {
  55    uint32_t max_entries, size, rehash;
  56    uint64_t size_magic, rehash_magic;
  57 } hash_sizes[] = {
  58 #define ENTRY(max_entries, size, rehash) \
  59    { max_entries, size, rehash, \
  60       REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
  61
  62    ENTRY(2,            5,            3            ),
  63    ENTRY(4,            7,            5            ),
  64    ENTRY(8,            13,           11           ),
  65    ENTRY(16,           19,           17           ),
  66    ENTRY(32,           43,           41           ),
  67    ENTRY(64,           73,           71           ),
  68    ENTRY(128,          151,          149          ),
  69    ENTRY(256,          283,          281          ),
  70    ENTRY(512,          571,          569          ),
  71    ENTRY(1024,         1153,         1151         ),
  72    ENTRY(2048,         2269,         2267         ),
  73    ENTRY(4096,         4519,         4517         ),
  74    ENTRY(8192,         9013,         9011         ),
  75    ENTRY(16384,        18043,        18041        ),
  76    ENTRY(32768,        36109,        36107        ),
  77    ENTRY(65536,        72091,        72089        ),
  78    ENTRY(131072,       144409,       144407       ),
  79    ENTRY(262144,       288361,       288359       ),
  80    ENTRY(524288,       576883,       576881       ),
  81    ENTRY(1048576,      1153459,      1153457      ),
  82    ENTRY(2097152,      2307163,      2307161      ),
  83    ENTRY(4194304,      4613893,      4613891      ),
  84    ENTRY(8388608,      9227641,      9227639      ),
  85    ENTRY(16777216,     18455029,     18455027     ),
  86    ENTRY(33554432,     36911011,     36911009     ),
  87    ENTRY(67108864,     73819861,     73819859     ),
  88    ENTRY(134217728,    147639589,    147639587    ),
  89    ENTRY(268435456,    295279081,    295279079    ),
  90    ENTRY(536870912,    590559793,    590559791    ),
  91    ENTRY(1073741824,   1181116273,   1181116271   ),
  92    ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
  93 };
  94
  95 ASSERTED static inline bool
  96 key_pointer_is_reserved(const void *key)
  97 {
  98    return key == NULL || key == deleted_key;
  99 }
 100
 101 static int
 102 entry_is_free(struct set_entry *entry)
 103 {
 104    return entry->key == NULL;
 105 }
 106
 107 static int
 108 entry_is_deleted(struct set_entry *entry)
 109 {
 110    return entry->key == deleted_key;
 111 }
 112
 113 static int
 114 entry_is_present(struct set_entry *entry)
 115 {
 116    return entry->key != NULL && entry->key != deleted_key;
 117 }
 118
 119 struct set *
 120 _mesa_set_create(void *mem_ctx,
 121                  uint32_t (*key_hash_function)(const void *key),
 122                  bool (*key_equals_function)(const void *a,
 123                                              const void *b))
 124 {
 125    struct set *ht;
 126
 127    ht = ralloc(mem_ctx, struct set);
 128    if (ht == NULL)
 129       return NULL;
 130
 131    ht->size_index = 0;
 132    ht->size = hash_sizes[ht->size_index].size;
 133    ht->rehash = hash_sizes[ht->size_index].rehash;
 134    ht->size_magic = hash_sizes[ht->size_index].size_magic;
 135    ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
 136    ht->max_entries = hash_sizes[ht->size_index].max_entries;
 137    ht->key_hash_function = key_hash_function;
 138    ht->key_equals_function = key_equals_function;
 139    ht->table = rzalloc_array(ht, struct set_entry, ht->size);
 140    ht->entries = 0;
 141    ht->deleted_entries = 0;
 142
 143    if (ht->table == NULL) {
 144       ralloc_free(ht);
 145       return NULL;
 146    }
 147
 148    return ht;
 149 }
 150
 151 struct set *
 152 _mesa_set_clone(struct set *set, void *dst_mem_ctx)
 153 {
 154    struct set *clone;
 155
 156    clone = ralloc(dst_mem_ctx, struct set);
 157    if (clone == NULL)
 158       return NULL;
 159
 160    memcpy(clone, set, sizeof(struct set));
 161
 162    clone->table = ralloc_array(clone, struct set_entry, clone->size);
 163    if (clone->table == NULL) {
 164       ralloc_free(clone);
 165       return NULL;
 166    }
 167
 168    memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
 169
 170    return clone;
 171 }
 172
 173 /**
 174  * Frees the given set.
 175  *
 176  * If delete_function is passed, it gets called on each entry present before
 177  * freeing.
 178  */
 179 void
 180 _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
 181 {
 182    if (!ht)
 183       return;
 184
 185    if (delete_function) {
 186       set_foreach (ht, entry) {
 187          delete_function(entry);
 188       }
 189    }
 190    ralloc_free(ht->table);
 191    ralloc_free(ht);
 192 }
 193
 194 /**
 195  * Clears all values from the given set.
 196  *
 197  * If delete_function is passed, it gets called on each entry present before
 198  * the set is cleared.
 199  */
 200 void
 201 _mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry))
 202 {
 203    if (!set)
 204       return;
 205
 206    set_foreach (set, entry) {
 207       if (delete_function)
 208          delete_function(entry);
 209       entry->key = deleted_key;
 210    }
 211
 212    set->entries = set->deleted_entries = 0;
 213 }
 214
 215 /**
 216  * Finds a set entry with the given key and hash of that key.
 217  *
 218  * Returns NULL if no entry is found.
 219  */
 220 static struct set_entry *
 221 set_search(const struct set *ht, uint32_t hash, const void *key)
 222 {
 223    assert(!key_pointer_is_reserved(key));
 224
 225    uint32_t size = ht->size;
 226    uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
 227    uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
 228                                            ht->rehash_magic) + 1;
 229    uint32_t hash_address = start_address;
 230    do {
 231       struct set_entry *entry = ht->table + hash_address;
 232
 233       if (entry_is_free(entry)) {
 234          return NULL;
 235       } else if (entry_is_present(entry) && entry->hash == hash) {
 236          if (ht->key_equals_function(key, entry->key)) {
 237             return entry;
 238          }
 239       }
 240
 241       hash_address += double_hash;
 242       if (hash_address >= size)
 243          hash_address -= size;
 244    } while (hash_address != start_address);
 245
 246    return NULL;
 247 }
 248
 249 struct set_entry *
 250 _mesa_set_search(const struct set *set, const void *key)
 251 {
 252    assert(set->key_hash_function);
 253    return set_search(set, set->key_hash_function(key), key);
 254 }
 255
 256 struct set_entry *
 257 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
 258                             const void *key)
 259 {
 260    assert(set->key_hash_function == NULL ||
 261           hash == set->key_hash_function(key));
 262    return set_search(set, hash, key);
 263 }
 264
 265 static void
 266 set_add_rehash(struct set *ht, uint32_t hash, const void *key)
 267 {
 268    uint32_t size = ht->size;
 269    uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
 270    uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
 271                                            ht->rehash_magic) + 1;
 272    uint32_t hash_address = start_address;
 273    do {
 274       struct set_entry *entry = ht->table + hash_address;
 275       if (likely(entry->key == NULL)) {
 276          entry->hash = hash;
 277          entry->key = key;
 278          return;
 279       }
 280
 281       hash_address = hash_address + double_hash;
 282       if (hash_address >= size)
 283          hash_address -= size;
 284    } while (true);
 285 }
 286
 287 static void
 288 set_rehash(struct set *ht, unsigned new_size_index)
 289 {
 290    struct set old_ht;
 291    struct set_entry *table;
 292
 293    if (new_size_index >= ARRAY_SIZE(hash_sizes))
 294       return;
 295
 296    table = rzalloc_array(ht, struct set_entry,
 297                          hash_sizes[new_size_index].size);
 298    if (table == NULL)
 299       return;
 300
 301    old_ht = *ht;
 302
 303    ht->table = table;
 304    ht->size_index = new_size_index;
 305    ht->size = hash_sizes[ht->size_index].size;
 306    ht->rehash = hash_sizes[ht->size_index].rehash;
 307    ht->size_magic = hash_sizes[ht->size_index].size_magic;
 308    ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
 309    ht->max_entries = hash_sizes[ht->size_index].max_entries;
 310    ht->entries = 0;
 311    ht->deleted_entries = 0;
 312
 313    set_foreach(&old_ht, entry) {
 314       set_add_rehash(ht, entry->hash, entry->key);
 315    }
 316
 317    ht->entries = old_ht.entries;
 318
 319    ralloc_free(old_ht.table);
 320 }
 321
 322 void
 323 _mesa_set_resize(struct set *set, uint32_t entries)
 324 {
 325    /* You can't shrink a set below its number of entries */
 326    if (set->entries > entries)
 327       entries = set->entries;
 328
 329    unsigned size_index = 0;
 330    while (hash_sizes[size_index].max_entries < entries)
 331       size_index++;
 332
 333    set_rehash(set, size_index);
 334 }
 335
 336 /**
 337  * Find a matching entry for the given key, or insert it if it doesn't already
 338  * exist.
 339  *
 340  * Note that insertion may rearrange the table on a resize or rehash,
 341  * so previously found hash_entries are no longer valid after this function.
 342  */
 343 static struct set_entry *
 344 set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
 345 {
 346    struct set_entry *available_entry = NULL;
 347
 348    assert(!key_pointer_is_reserved(key));
 349
 350    if (ht->entries >= ht->max_entries) {
 351       set_rehash(ht, ht->size_index + 1);
 352    } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
 353       set_rehash(ht, ht->size_index);
 354    }
 355
 356    uint32_t size = ht->size;
 357    uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
 358    uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
 359                                            ht->rehash_magic) + 1;
 360    uint32_t hash_address = start_address;
 361    do {
 362       struct set_entry *entry = ht->table + hash_address;
 363
 364       if (!entry_is_present(entry)) {
 365          /* Stash the first available entry we find */
 366          if (available_entry == NULL)
 367             available_entry = entry;
 368          if (entry_is_free(entry))
 369             break;
 370       }
 371
 372       if (!entry_is_deleted(entry) &&
 373           entry->hash == hash &&
 374           ht->key_equals_function(key, entry->key)) {
 375          if (found)
 376             *found = true;
 377          return entry;
 378       }
 379
 380       hash_address = hash_address + double_hash;
 381       if (hash_address >= size)
 382          hash_address -= size;
 383    } while (hash_address != start_address);
 384
 385    if (available_entry) {
 386       /* There is no matching entry, create it. */
 387       if (entry_is_deleted(available_entry))
 388          ht->deleted_entries--;
 389       available_entry->hash = hash;
 390       available_entry->key = key;
 391       ht->entries++;
 392       if (found)
 393          *found = false;
 394       return available_entry;
 395    }
 396
 397    /* We could hit here if a required resize failed. An unchecked-malloc
 398     * application could ignore this result.
 399     */
 400    return NULL;
 401 }
 402
 403 /**
 404  * Inserts the key with the given hash into the table.
 405  *
 406  * Note that insertion may rearrange the table on a resize or rehash,
 407  * so previously found hash_entries are no longer valid after this function.
 408  */
 409 static struct set_entry *
 410 set_add(struct set *ht, uint32_t hash, const void *key)
 411 {
 412    struct set_entry *entry = set_search_or_add(ht, hash, key, NULL);
 413
 414    if (unlikely(!entry))
 415       return NULL;
 416
 417    /* Note: If a matching entry already exists, this will replace it.  This is
 418     * a relatively common feature of hash tables, with the alternative
 419     * generally being "insert the new value as well, and return it first when
 420     * the key is searched for".
 421     *
 422     * Note that the hash table doesn't have a delete callback.  If freeing of
 423     * old keys is required to avoid memory leaks, use the alternative
 424     * _mesa_set_search_or_add function and implement the replacement yourself.
 425     */
 426    entry->key = key;
 427    return entry;
 428 }
 429
 430 struct set_entry *
 431 _mesa_set_add(struct set *set, const void *key)
 432 {
 433    assert(set->key_hash_function);
 434    return set_add(set, set->key_hash_function(key), key);
 435 }
 436
 437 struct set_entry *
 438 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
 439 {
 440    assert(set->key_hash_function == NULL ||
 441           hash == set->key_hash_function(key));
 442    return set_add(set, hash, key);
 443 }
 444
 445 struct set_entry *
 446 _mesa_set_search_and_add(struct set *set, const void *key, bool *replaced)
 447 {
 448    assert(set->key_hash_function);
 449    return _mesa_set_search_and_add_pre_hashed(set,
 450                                               set->key_hash_function(key),
 451                                               key, replaced);
 452 }
 453
 454 struct set_entry *
 455 _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
 456                                     const void *key, bool *replaced)
 457 {
 458    assert(set->key_hash_function == NULL ||
 459           hash == set->key_hash_function(key));
 460    struct set_entry *entry = set_search_or_add(set, hash, key, replaced);
 461
 462    if (unlikely(!entry))
 463       return NULL;
 464
 465    /* This implements the replacement, same as _mesa_set_add(). The user will
 466     * be notified if we're overwriting a found entry.
 467     */
 468    entry->key = key;
 469    return entry;
 470 }
 471
 472 struct set_entry *
 473 _mesa_set_search_or_add(struct set *set, const void *key)
 474 {
 475    assert(set->key_hash_function);
 476    return set_search_or_add(set, set->key_hash_function(key), key, NULL);
 477 }
 478
 479 struct set_entry *
 480 _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
 481                                    const void *key)
 482 {
 483    assert(set->key_hash_function == NULL ||
 484           hash == set->key_hash_function(key));
 485    return set_search_or_add(set, hash, key, NULL);
 486 }
 487
 488 /**
 489  * This function deletes the given hash table entry.
 490  *
 491  * Note that deletion doesn't otherwise modify the table, so an iteration over
 492  * the table deleting entries is safe.
 493  */
 494 void
 495 _mesa_set_remove(struct set *ht, struct set_entry *entry)
 496 {
 497    if (!entry)
 498       return;
 499
 500    entry->key = deleted_key;
 501    ht->entries--;
 502    ht->deleted_entries++;
 503 }
 504
 505 /**
 506  * Removes the entry with the corresponding key, if exists.
 507  */
 508 void
 509 _mesa_set_remove_key(struct set *set, const void *key)
 510 {
 511    _mesa_set_remove(set, _mesa_set_search(set, key));
 512 }
 513
 514 /**
 515  * This function is an iterator over the hash table.
 516  *
 517  * Pass in NULL for the first entry, as in the start of a for loop.  Note that
 518  * an iteration over the table is O(table_size) not O(entries).
 519  */
 520 struct set_entry *
 521 _mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
 522 {
 523    if (entry == NULL)
 524       entry = ht->table;
 525    else
 526       entry = entry + 1;
 527
 528    for (; entry != ht->table + ht->size; entry++) {
 529       if (entry_is_present(entry)) {
 530          return entry;
 531       }
 532    }
 533
 534    return NULL;
 535 }
 536
 537 struct set_entry *
 538 _mesa_set_random_entry(struct set *ht,
 539                        int (*predicate)(struct set_entry *entry))
 540 {
 541    struct set_entry *entry;
 542    uint32_t i = rand() % ht->size;
 543
 544    if (ht->entries == 0)
 545       return NULL;
 546
 547    for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
 548       if (entry_is_present(entry) &&
 549           (!predicate || predicate(entry))) {
 550          return entry;
 551       }
 552    }
 553
 554    for (entry = ht->table; entry != ht->table + i; entry++) {
 555       if (entry_is_present(entry) &&
 556           (!predicate || predicate(entry))) {
 557          return entry;
 558       }
 559    }
 560
 561    return NULL;
 562 }
 563
 564 /**
 565  * Helper to create a set with pointer keys.
 566  */
 567 struct set *
 568 _mesa_pointer_set_create(void *mem_ctx)
 569 {
 570    return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
 571                            _mesa_key_pointer_equal);
 572 }