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 static int
  96 entry_is_free(struct set_entry *entry)
  97 {
  98    return entry->key == NULL;
  99 }
 100
 101 static int
 102 entry_is_deleted(struct set_entry *entry)
 103 {
 104    return entry->key == deleted_key;
 105 }
 106
 107 static int
 108 entry_is_present(struct set_entry *entry)
 109 {
 110    return entry->key != NULL && entry->key != deleted_key;
 111 }
 112
 113 struct set *
 114 _mesa_set_create(void *mem_ctx,
 115                  uint32_t (*key_hash_function)(const void *key),
 116                  bool (*key_equals_function)(const void *a,
 117                                              const void *b))
 118 {
 119    struct set *ht;
 120
 121    ht = ralloc(mem_ctx, struct set);
 122    if (ht == NULL)
 123       return NULL;
 124
 125    ht->size_index = 0;
 126    ht->size = hash_sizes[ht->size_index].size;
 127    ht->rehash = hash_sizes[ht->size_index].rehash;
 128    ht->size_magic = hash_sizes[ht->size_index].size_magic;
 129    ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
 130    ht->max_entries = hash_sizes[ht->size_index].max_entries;
 131    ht->key_hash_function = key_hash_function;
 132    ht->key_equals_function = key_equals_function;
 133    ht->table = rzalloc_array(ht, struct set_entry, ht->size);
 134    ht->entries = 0;
 135    ht->deleted_entries = 0;
 136
 137    if (ht->table == NULL) {
 138       ralloc_free(ht);
 139       return NULL;
 140    }
 141
 142    return ht;
 143 }
 144
 145 struct set *
 146 _mesa_set_clone(struct set *set, void *dst_mem_ctx)
 147 {
 148    struct set *clone;
 149
 150    clone = ralloc(dst_mem_ctx, struct set);
 151    if (clone == NULL)
 152       return NULL;
 153
 154    memcpy(clone, set, sizeof(struct set));
 155
 156    clone->table = ralloc_array(clone, struct set_entry, clone->size);
 157    if (clone->table == NULL) {
 158       ralloc_free(clone);
 159       return NULL;
 160    }
 161
 162    memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
 163
 164    return clone;
 165 }
 166
 167 /**
 168  * Frees the given set.
 169  *
 170  * If delete_function is passed, it gets called on each entry present before
 171  * freeing.
 172  */
 173 void
 174 _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
 175 {
 176    if (!ht)
 177       return;
 178
 179    if (delete_function) {
 180       set_foreach (ht, entry) {
 181          delete_function(entry);
 182       }
 183    }
 184    ralloc_free(ht->table);
 185    ralloc_free(ht);
 186 }
 187
 188 /**
 189  * Clears all values from the given set.
 190  *
 191  * If delete_function is passed, it gets called on each entry present before
 192  * the set is cleared.
 193  */
 194 void
 195 _mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry))
 196 {
 197    if (!set)
 198       return;
 199
 200    set_foreach (set, entry) {
 201       if (delete_function)
 202          delete_function(entry);
 203       entry->key = deleted_key;
 204    }
 205
 206    set->entries = set->deleted_entries = 0;
 207 }
 208
 209 /**
 210  * Finds a set entry with the given key and hash of that key.
 211  *
 212  * Returns NULL if no entry is found.
 213  */
 214 static struct set_entry *
 215 set_search(const struct set *ht, uint32_t hash, const void *key)
 216 {
 217    uint32_t size = ht->size;
 218    uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
 219    uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
 220                                            ht->rehash_magic) + 1;
 221    uint32_t hash_address = start_address;
 222    do {
 223       struct set_entry *entry = ht->table + hash_address;
 224
 225       if (entry_is_free(entry)) {
 226          return NULL;
 227       } else if (entry_is_present(entry) && entry->hash == hash) {
 228          if (ht->key_equals_function(key, entry->key)) {
 229             return entry;
 230          }
 231       }
 232
 233       hash_address += double_hash;
 234       if (hash_address >= size)
 235          hash_address -= size;
 236    } while (hash_address != start_address);
 237
 238    return NULL;
 239 }
 240
 241 struct set_entry *
 242 _mesa_set_search(const struct set *set, const void *key)
 243 {
 244    assert(set->key_hash_function);
 245    return set_search(set, set->key_hash_function(key), key);
 246 }
 247
 248 struct set_entry *
 249 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
 250                             const void *key)
 251 {
 252    assert(set->key_hash_function == NULL ||
 253           hash == set->key_hash_function(key));
 254    return set_search(set, hash, key);
 255 }
 256
 257 static void
 258 set_add_rehash(struct set *ht, uint32_t hash, const void *key)
 259 {
 260    uint32_t size = ht->size;
 261    uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
 262    uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
 263                                            ht->rehash_magic) + 1;
 264    uint32_t hash_address = start_address;
 265    do {
 266       struct set_entry *entry = ht->table + hash_address;
 267       if (likely(entry->key == NULL)) {
 268          entry->hash = hash;
 269          entry->key = key;
 270          return;
 271       }
 272
 273       hash_address = hash_address + double_hash;
 274       if (hash_address >= size)
 275          hash_address -= size;
 276    } while (true);
 277 }
 278
 279 static void
 280 set_rehash(struct set *ht, unsigned new_size_index)
 281 {
 282    struct set old_ht;
 283    struct set_entry *table;
 284
 285    if (new_size_index >= ARRAY_SIZE(hash_sizes))
 286       return;
 287
 288    table = rzalloc_array(ht, struct set_entry,
 289                          hash_sizes[new_size_index].size);
 290    if (table == NULL)
 291       return;
 292
 293    old_ht = *ht;
 294
 295    ht->table = table;
 296    ht->size_index = new_size_index;
 297    ht->size = hash_sizes[ht->size_index].size;
 298    ht->rehash = hash_sizes[ht->size_index].rehash;
 299    ht->size_magic = hash_sizes[ht->size_index].size_magic;
 300    ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
 301    ht->max_entries = hash_sizes[ht->size_index].max_entries;
 302    ht->entries = 0;
 303    ht->deleted_entries = 0;
 304
 305    set_foreach(&old_ht, entry) {
 306       set_add_rehash(ht, entry->hash, entry->key);
 307    }
 308
 309    ht->entries = old_ht.entries;
 310
 311    ralloc_free(old_ht.table);
 312 }
 313
 314 void
 315 _mesa_set_resize(struct set *set, uint32_t entries)
 316 {
 317    /* You can't shrink a set below its number of entries */
 318    if (set->entries > entries)
 319       entries = set->entries;
 320
 321    unsigned size_index = 0;
 322    while (hash_sizes[size_index].max_entries < entries)
 323       size_index++;
 324
 325    set_rehash(set, size_index);
 326 }
 327
 328 /**
 329  * Find a matching entry for the given key, or insert it if it doesn't already
 330  * exist.
 331  *
 332  * Note that insertion may rearrange the table on a resize or rehash,
 333  * so previously found hash_entries are no longer valid after this function.
 334  */
 335 static struct set_entry *
 336 set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
 337 {
 338    struct set_entry *available_entry = NULL;
 339
 340    if (ht->entries >= ht->max_entries) {
 341       set_rehash(ht, ht->size_index + 1);
 342    } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
 343       set_rehash(ht, ht->size_index);
 344    }
 345
 346    uint32_t size = ht->size;
 347    uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
 348    uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
 349                                            ht->rehash_magic) + 1;
 350    uint32_t hash_address = start_address;
 351    do {
 352       struct set_entry *entry = ht->table + hash_address;
 353
 354       if (!entry_is_present(entry)) {
 355          /* Stash the first available entry we find */
 356          if (available_entry == NULL)
 357             available_entry = entry;
 358          if (entry_is_free(entry))
 359             break;
 360       }
 361
 362       if (!entry_is_deleted(entry) &&
 363           entry->hash == hash &&
 364           ht->key_equals_function(key, entry->key)) {
 365          if (found)
 366             *found = true;
 367          return entry;
 368       }
 369
 370       hash_address = hash_address + double_hash;
 371       if (hash_address >= size)
 372          hash_address -= size;
 373    } while (hash_address != start_address);
 374
 375    if (available_entry) {
 376       /* There is no matching entry, create it. */
 377       if (entry_is_deleted(available_entry))
 378          ht->deleted_entries--;
 379       available_entry->hash = hash;
 380       available_entry->key = key;
 381       ht->entries++;
 382       if (found)
 383          *found = false;
 384       return available_entry;
 385    }
 386
 387    /* We could hit here if a required resize failed. An unchecked-malloc
 388     * application could ignore this result.
 389     */
 390    return NULL;
 391 }
 392
 393 /**
 394  * Inserts the key with the given hash into the table.
 395  *
 396  * Note that insertion may rearrange the table on a resize or rehash,
 397  * so previously found hash_entries are no longer valid after this function.
 398  */
 399 static struct set_entry *
 400 set_add(struct set *ht, uint32_t hash, const void *key)
 401 {
 402    struct set_entry *entry = set_search_or_add(ht, hash, key, NULL);
 403
 404    if (unlikely(!entry))
 405       return NULL;
 406
 407    /* Note: If a matching entry already exists, this will replace it.  This is
 408     * a relatively common feature of hash tables, with the alternative
 409     * generally being "insert the new value as well, and return it first when
 410     * the key is searched for".
 411     *
 412     * Note that the hash table doesn't have a delete callback.  If freeing of
 413     * old keys is required to avoid memory leaks, use the alternative
 414     * _mesa_set_search_or_add function and implement the replacement yourself.
 415     */
 416    entry->key = key;
 417    return entry;
 418 }
 419
 420 struct set_entry *
 421 _mesa_set_add(struct set *set, const void *key)
 422 {
 423    assert(set->key_hash_function);
 424    return set_add(set, set->key_hash_function(key), key);
 425 }
 426
 427 struct set_entry *
 428 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
 429 {
 430    assert(set->key_hash_function == NULL ||
 431           hash == set->key_hash_function(key));
 432    return set_add(set, hash, key);
 433 }
 434
 435 struct set_entry *
 436 _mesa_set_search_and_add(struct set *set, const void *key, bool *replaced)
 437 {
 438    assert(set->key_hash_function);
 439    return _mesa_set_search_and_add_pre_hashed(set,
 440                                               set->key_hash_function(key),
 441                                               key, replaced);
 442 }
 443
 444 struct set_entry *
 445 _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
 446                                     const void *key, bool *replaced)
 447 {
 448    assert(set->key_hash_function == NULL ||
 449           hash == set->key_hash_function(key));
 450    struct set_entry *entry = set_search_or_add(set, hash, key, replaced);
 451
 452    if (unlikely(!entry))
 453       return NULL;
 454
 455    /* This implements the replacement, same as _mesa_set_add(). The user will
 456     * be notified if we're overwriting a found entry.
 457     */
 458    entry->key = key;
 459    return entry;
 460 }
 461
 462 struct set_entry *
 463 _mesa_set_search_or_add(struct set *set, const void *key)
 464 {
 465    assert(set->key_hash_function);
 466    return set_search_or_add(set, set->key_hash_function(key), key, NULL);
 467 }
 468
 469 struct set_entry *
 470 _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
 471                                    const void *key)
 472 {
 473    assert(set->key_hash_function == NULL ||
 474           hash == set->key_hash_function(key));
 475    return set_search_or_add(set, hash, key, NULL);
 476 }
 477
 478 /**
 479  * This function deletes the given hash table entry.
 480  *
 481  * Note that deletion doesn't otherwise modify the table, so an iteration over
 482  * the table deleting entries is safe.
 483  */
 484 void
 485 _mesa_set_remove(struct set *ht, struct set_entry *entry)
 486 {
 487    if (!entry)
 488       return;
 489
 490    entry->key = deleted_key;
 491    ht->entries--;
 492    ht->deleted_entries++;
 493 }
 494
 495 /**
 496  * Removes the entry with the corresponding key, if exists.
 497  */
 498 void
 499 _mesa_set_remove_key(struct set *set, const void *key)
 500 {
 501    _mesa_set_remove(set, _mesa_set_search(set, key));
 502 }
 503
 504 /**
 505  * This function is an iterator over the hash table.
 506  *
 507  * Pass in NULL for the first entry, as in the start of a for loop.  Note that
 508  * an iteration over the table is O(table_size) not O(entries).
 509  */
 510 struct set_entry *
 511 _mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
 512 {
 513    if (entry == NULL)
 514       entry = ht->table;
 515    else
 516       entry = entry + 1;
 517
 518    for (; entry != ht->table + ht->size; entry++) {
 519       if (entry_is_present(entry)) {
 520          return entry;
 521       }
 522    }
 523
 524    return NULL;
 525 }
 526
 527 struct set_entry *
 528 _mesa_set_random_entry(struct set *ht,
 529                        int (*predicate)(struct set_entry *entry))
 530 {
 531    struct set_entry *entry;
 532    uint32_t i = rand() % ht->size;
 533
 534    if (ht->entries == 0)
 535       return NULL;
 536
 537    for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
 538       if (entry_is_present(entry) &&
 539           (!predicate || predicate(entry))) {
 540          return entry;
 541       }
 542    }
 543
 544    for (entry = ht->table; entry != ht->table + i; entry++) {
 545       if (entry_is_present(entry) &&
 546           (!predicate || predicate(entry))) {
 547          return entry;
 548       }
 549    }
 550
 551    return NULL;
 552 }
 553
 554 /**
 555  * Helper to create a set with pointer keys.
 556  */
 557 struct set *
 558 _mesa_pointer_set_create(void *mem_ctx)
 559 {
 560    return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
 561                            _mesa_key_pointer_equal);
 562 }