nsz Git - cparser/blob - adt/hashset.c

   1 /**
   2  * @file
   3  * @date    17.03.2007
   4  * @brief   Geberic hashset implementation
   5  * @author  Matthias Braun, inspiration from densehash from google sparsehash
   6  *          package
   7  * @version $Id$
   8  *
   9  *
  10  * You have to specialize this file by defining:
  11  *
  12  * <ul>
  13  *  <li><b>HashSet</b>         The name of the hashset type</li>
  14  *  <li><b>HashSetIterator</b> The name of the hashset iterator type</li>
  15  *  <li><b>ValueType</b>       The type of the stored data values</li>
  16  *  <li><b>NullValue</b>       A special value representing no values</li>
  17  *  <li><b>DeletedValue</b>    A special value representing deleted entries</li>
  18  *  <li><b>Hash(hashset,key)</b> calculates the hash value for a given key</li>
  19  * </ul>
  20  *
  21  * Note that by default it is assumed that the data values themselfes are used
  22  * as keys. However you can change that with additional defines:
  23  *
  24  * <ul>
  25  *  <li><b>KeyType</b>         The type of the keys identifying data values.
  26  *                             Defining this implies, that a data value contains
  27  *                             more than just the key.</li>
  28  *  <li><b>GetKey(value)</b>   Extracts the key from a data value</li>
  29  *  <li><b>KeysEqual(hashset,key1,key2)</b>  Tests wether 2 keys are equal</li>
  30  *  <li><b>DO_REHASH</b>       Instead of storing the hash-values, recalculate
  31  *                             them on demand from the datavalues. (usefull if
  32  *                             calculating the hash-values takes less time than
  33  *                             a memory access)</li>
  34  * </ul>
  35  *
  36  * You can further fine tune your hashset by defining the following:
  37  *
  38  * <ul>
  39  *  <li><b>JUMP(num_probes)</b> The probing method</li>
  40  *  <li><b>Alloc(count)</b>     Allocates count hashset entries (NOT bytes)</li>
  41  *  <li><b>Free(ptr)</b>        Frees a block of memory allocated by Alloc</li>
  42  *  <li><b>SetRangeEmpty(ptr,count)</b> Efficiently sets a range of elements to
  43  *                                      the Null value</li>
  44  *  <li><b>ADDITIONAL_DATA<b>   Additional fields appended to the hashset struct</li>
  45  * </ul>
  46  */
  47 #ifdef HashSet
  48
  49 #include <stdlib.h>
  50 #include <string.h>
  51 #include <assert.h>
  52
  53 #include "bitfiddle.h"
  54 #include "util.h"
  55
  56 /* quadratic probing */
  57 #ifndef JUMP
  58 #define JUMP(num_probes)      (num_probes)
  59 #endif
  60
  61 #ifndef Hash
  62 #define ID_HASH
  63 #define Hash(this,value)      ((unsigned)(value))
  64 #endif
  65
  66 #ifdef DO_REHASH
  67 #define HashSetEntry                   ValueType
  68 #define EntrySetHash(entry,new_hash)
  69 #define EntryGetHash(this,entry)       Hash(this,entry)
  70 #define EntryGetValue(entry)           (entry)
  71 #else
  72 #define EntryGetHash(this,entry)       (entry).hash
  73 #define EntrySetHash(entry,new_hash)   (entry).hash = (new_hash)
  74 #define EntryGetValue(entry)           (entry).data
  75 #endif
  76
  77 #ifndef Alloc
  78 #include "xmalloc.h"
  79 #define Alloc(size)    (HashSetEntry*) xmalloc((size) * sizeof(HashSetEntry))
  80 #define Free(ptr)      free(ptr)
  81 #endif
  82
  83 #ifdef ID_HASH
  84 #define InsertReturnValue               int
  85 #define GetInsertReturnValue(entry,new) (new)
  86 #else
  87 #define InsertReturnValue               ValueType
  88 #define GetInsertReturnValue(entry,new) EntryGetValue(entry)
  89 #endif
  90
  91 #ifndef KeyType
  92 #define KeyType                  ValueType
  93 #define GetKey(value)            (value)
  94 #define InitData(this,value,key) (value) = (key)
  95 #endif
  96
  97 #ifndef ConstKeyType
  98 #define ConstKeyType             const KeyType
  99 #endif
 100
 101 #ifndef EntrySetEmpty
 102 #define EntrySetEmpty(entry)    EntryGetValue(entry) = NullValue
 103 #endif
 104 #ifndef EntrySetDeleted
 105 #define EntrySetDeleted(entry)  EntryGetValue(entry) = DeletedValue
 106 #endif
 107 #ifndef EntryIsEmpty
 108 #define EntryIsEmpty(entry)     (EntryGetValue(entry) == NullValue)
 109 #endif
 110 #ifndef EntryIsDeleted
 111 #define EntryIsDeleted(entry)   (EntryGetValue(entry) == DeletedValue)
 112 #endif
 113 #ifndef SetRangeEmpty
 114 #define SetRangeEmpty(ptr,size)                \
 115 {                                              \
 116         size_t _i;                                 \
 117         size_t _size = (size);                     \
 118         HashSetEntry *entries = (ptr);             \
 119         for(_i = 0; _i < _size; ++_i) {            \
 120                 HashSetEntry *entry = & entries[_i];   \
 121                 EntrySetEmpty(*entry);                 \
 122         }                                          \
 123 }
 124 #endif
 125
 126 #ifndef HT_OCCUPANCY_FLT
 127 /** how full before we double size */
 128 #define HT_OCCUPANCY_FLT  0.5f
 129 #endif
 130
 131 #ifndef HT_EMPTY_FLT
 132 /** how empty before we half size */
 133 #define HT_EMPTY_FLT      (0.4f * (HT_OCCUPANCY_FLT))
 134 #endif
 135
 136 #ifndef HT_MIN_BUCKETS
 137 /** default smallest bucket size */
 138 #define HT_MIN_BUCKETS    32
 139 #endif
 140
 141 #define ILLEGAL_POS       ((size_t)-1)
 142
 143 #ifndef hashset_init
 144 #error You have to redefine hashset_init
 145 #endif
 146 #ifndef hashset_init_size
 147 #error You have to redefine hashset_init_size
 148 #endif
 149 #ifndef hashset_destroy
 150 #error You have to redefine hashset_destroy
 151 #endif
 152 #ifndef hashset_insert
 153 #error You have to redefine hashset_insert
 154 #endif
 155 #ifndef hashset_remove
 156 #error You have to redefine hashset_remove
 157 #endif
 158 #ifndef hashset_find
 159 #error You have to redefine hashset_find
 160 #endif
 161 #ifndef hashset_size
 162 #error You have to redefine hashset_size
 163 #endif
 164 #ifndef hashset_iterator_init
 165 #error You have to redefine hashset_iterator_init
 166 #endif
 167 #ifndef hashset_iterator_next
 168 #error You have to redefine hashset_iterator_next
 169 #endif
 170 #ifndef hashset_remove_iterator
 171 #error You have to redefine hashset_remove_iterator
 172 #endif
 173
 174 /**
 175  * Returns the number of elements in the hashset
 176  */
 177 size_t hashset_size(const HashSet *this)
 178 {
 179         return this->num_elements - this->num_deleted;
 180 }
 181
 182 /**
 183  * Inserts an element into a hashset without growing the set (you have to make
 184  * sure there's enough room for that.
 185  * @note also see comments for hashset_insert()
 186  * @internal
 187  */
 188 static inline
 189 InsertReturnValue insert_nogrow(HashSet *this, KeyType key)
 190 {
 191         size_t num_probes = 0;
 192         size_t num_buckets = this->num_buckets;
 193         size_t hashmask = num_buckets - 1;
 194         unsigned hash = Hash(this, key);
 195         size_t bucknum = hash & hashmask;
 196         size_t insert_pos = ILLEGAL_POS;
 197
 198         assert((num_buckets & (num_buckets - 1)) == 0);
 199
 200         while(1) {
 201                 HashSetEntry *entry = & this->entries[bucknum];
 202
 203                 if(EntryIsEmpty(*entry)) {
 204                         size_t p;
 205                         HashSetEntry *nentry;
 206
 207                         if(insert_pos != ILLEGAL_POS) {
 208                                 p = insert_pos;
 209                         } else {
 210                                 p = bucknum;
 211                         }
 212
 213                         nentry = &this->entries[p];
 214                         InitData(this, EntryGetValue(*nentry), key);
 215                         EntrySetHash(*nentry, hash);
 216                         this->num_elements++;
 217                         return GetInsertReturnValue(*nentry, 1);
 218                 }
 219                 if(EntryIsDeleted(*entry)) {
 220                         if(insert_pos == ILLEGAL_POS)
 221                                 insert_pos = bucknum;
 222                 } else if(EntryGetHash(this, *entry) == hash) {
 223                         if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) {
 224                                 // Value already in the set, return it
 225                                 return GetInsertReturnValue(*entry, 0);
 226                         }
 227                 }
 228
 229                 ++num_probes;
 230                 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
 231                 assert(num_probes < num_buckets);
 232         }
 233 }
 234
 235 /**
 236  * Inserts an element into a hashset under the assumption that the hashset
 237  * contains no deleted entries and the element doesn't exist in the hashset yet.
 238  * @internal
 239  */
 240 static
 241 void insert_new(HashSet *this, unsigned hash, ValueType value)
 242 {
 243         size_t num_probes = 0;
 244         size_t num_buckets = this->num_buckets;
 245         size_t hashmask = num_buckets - 1;
 246         size_t bucknum = hash & hashmask;
 247         size_t insert_pos = ILLEGAL_POS;
 248
 249         assert(value != NullValue);
 250
 251         while(1) {
 252                 HashSetEntry *entry = & this->entries[bucknum];
 253
 254                 if(EntryIsEmpty(*entry)) {
 255                         size_t p;
 256                         HashSetEntry *nentry;
 257
 258                         if(insert_pos != ILLEGAL_POS) {
 259                                 p = insert_pos;
 260                         } else {
 261                                 p = bucknum;
 262                         }
 263                         nentry = &this->entries[p];
 264
 265                         EntryGetValue(*nentry) = value;
 266                         EntrySetHash(*nentry, hash);
 267                         this->num_elements++;
 268                         return;
 269                 }
 270                 assert(!EntryIsDeleted(*entry));
 271
 272                 ++num_probes;
 273                 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
 274                 assert(num_probes < num_buckets);
 275         }
 276 }
 277
 278 /**
 279  * calculate shrink and enlarge limits
 280  * @internal
 281  */
 282 static inline
 283 void reset_thresholds(HashSet *this)
 284 {
 285         this->enlarge_threshold = (size_t) (this->num_buckets * HT_OCCUPANCY_FLT);
 286         this->shrink_threshold = (size_t) (this->num_buckets * HT_EMPTY_FLT);
 287         this->consider_shrink = 0;
 288 }
 289
 290 /**
 291  * Resize the hashset
 292  * @internal
 293  */
 294 static inline
 295 void resize(HashSet *this, size_t new_size)
 296 {
 297         size_t num_buckets = this->num_buckets;
 298         size_t i;
 299         HashSetEntry *old_entries = this->entries;
 300         HashSetEntry *new_entries;
 301
 302         /* allocate a new array with double size */
 303         new_entries = Alloc(new_size);
 304         SetRangeEmpty(new_entries, new_size);
 305
 306         /* use the new array */
 307         this->entries = new_entries;
 308         this->num_buckets = new_size;
 309         this->num_elements = 0;
 310         this->num_deleted = 0;
 311 #ifndef NDEBUG
 312         this->entries_version++;
 313 #endif
 314         reset_thresholds(this);
 315
 316         /* reinsert all elements */
 317         for(i = 0; i < num_buckets; ++i) {
 318                 HashSetEntry *entry = & old_entries[i];
 319                 if(EntryIsEmpty(*entry) || EntryIsDeleted(*entry))
 320                         continue;
 321
 322                 insert_new(this, EntryGetHash(this, *entry), EntryGetValue(*entry));
 323         }
 324
 325         /* now we can free the old array */
 326         Free(old_entries);
 327 }
 328
 329 /**
 330  * grow the hashset if adding 1 more elements would make it too crowded
 331  * @internal
 332  */
 333 static inline
 334 void maybe_grow(HashSet *this)
 335 {
 336         size_t resize_to;
 337
 338         if(LIKELY(this->num_elements + 1 <= this->enlarge_threshold))
 339                 return;
 340
 341         /* double table size */
 342         resize_to = this->num_buckets * 2;
 343         resize(this, resize_to);
 344 }
 345
 346 /**
 347  * shrink the hashset if it is only sparsely filled
 348  * @internal
 349  */
 350 static inline
 351 void maybe_shrink(HashSet *this)
 352 {
 353         size_t size;
 354         size_t resize_to;
 355
 356         if(!this->consider_shrink)
 357                 return;
 358
 359         this->consider_shrink = 0;
 360         size = hashset_size(this);
 361         if(LIKELY(size > this->shrink_threshold))
 362                 return;
 363
 364         resize_to = ceil_po2(size);
 365
 366         if(resize_to < 4)
 367                 resize_to = 4;
 368
 369         resize(this, resize_to);
 370 }
 371
 372 /**
 373  * Insert an element into the hashset. If no element with key key exists yet,
 374  * then a new one is created and initialized with the InitData function.
 375  * Otherwise the exisiting element is returned (for hashs where key is equal to
 376  * value, nothing is returned.)
 377  *
 378  * @param this   the hashset
 379  * @param key    the key that identifies the data
 380  * @returns      the existing or newly created data element (or nothing in case of hashs where keys are the while value)
 381  */
 382 InsertReturnValue hashset_insert(HashSet *this, KeyType key)
 383 {
 384 #ifndef NDEBUG
 385         this->entries_version++;
 386 #endif
 387
 388         maybe_shrink(this);
 389         maybe_grow(this);
 390         return insert_nogrow(this, key);
 391 }
 392
 393 /**
 394  * Searchs for an element with key @p key.
 395  *
 396  * @param this      the hashset
 397  * @param key       the key to search for
 398  * @returns         the found value or NullValue if nothing was found
 399  */
 400 ValueType hashset_find(const HashSet *this, ConstKeyType key)
 401 {
 402         size_t num_probes = 0;
 403         size_t num_buckets = this->num_buckets;
 404         size_t hashmask = num_buckets - 1;
 405         unsigned hash = Hash(this, key);
 406         size_t bucknum = hash & hashmask;
 407
 408         while(1) {
 409                 HashSetEntry *entry = & this->entries[bucknum];
 410
 411                 if(EntryIsEmpty(*entry)) {
 412                         return NullValue;
 413                 }
 414                 if(EntryIsDeleted(*entry)) {
 415                         // value is deleted
 416                 } else if(EntryGetHash(this, *entry) == hash) {
 417                         if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) {
 418                                 // found the value
 419                                 return EntryGetValue(*entry);
 420                         }
 421                 }
 422
 423                 ++num_probes;
 424                 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
 425                 assert(num_probes < num_buckets);
 426         }
 427 }
 428
 429 /**
 430  * Removes an element from a hashset. Does nothing if the set doesn't contain
 431  * the element.
 432  *
 433  * @param this    the hashset
 434  * @param key     key that identifies the data to remove
 435  */
 436 void hashset_remove(HashSet *this, ConstKeyType key)
 437 {
 438         size_t num_probes = 0;
 439         size_t num_buckets = this->num_buckets;
 440         size_t hashmask = num_buckets - 1;
 441         unsigned hash = Hash(this, key);
 442         size_t bucknum = hash & hashmask;
 443
 444 #ifndef NDEBUG
 445         this->entries_version++;
 446 #endif
 447
 448         while(1) {
 449                 HashSetEntry *entry = & this->entries[bucknum];
 450
 451                 if(EntryIsEmpty(*entry)) {
 452                         return;
 453                 }
 454                 if(EntryIsDeleted(*entry)) {
 455                         // entry is deleted
 456                 } else if(EntryGetHash(this, *entry) == hash) {
 457                         if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) {
 458                                 EntrySetDeleted(*entry);
 459                                 this->num_deleted++;
 460                                 this->consider_shrink = 1;
 461                                 return;
 462                         }
 463                 }
 464
 465                 ++num_probes;
 466                 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
 467                 assert(num_probes < num_buckets);
 468         }
 469 }
 470
 471 /**
 472  * Initializes hashset with a specific size
 473  * @internal
 474  */
 475 static inline
 476 void init_size(HashSet *this, size_t initial_size)
 477 {
 478         if(initial_size < 4)
 479                 initial_size = 4;
 480
 481         this->entries = Alloc(initial_size);
 482         SetRangeEmpty(this->entries, initial_size);
 483         this->num_buckets = initial_size;
 484         this->consider_shrink = 0;
 485         this->num_elements = 0;
 486         this->num_deleted = 0;
 487 #ifndef NDEBUG
 488         this->entries_version = 0;
 489 #endif
 490
 491         reset_thresholds(this);
 492 }
 493
 494 /**
 495  * Initialializes a hashset with the default size. The memory for the set has to
 496  * already allocated.
 497  */
 498 void hashset_init(HashSet *this)
 499 {
 500         init_size(this, HT_MIN_BUCKETS);
 501 }
 502
 503 /**
 504  * Destroys a hashset, freeing all used memory (except the memory for the
 505  * HashSet struct itself).
 506  */
 507 void hashset_destroy(HashSet *this)
 508 {
 509         Free(this->entries);
 510 #ifndef NDEBUG
 511         this->entries = NULL;
 512 #endif
 513 }
 514
 515 /**
 516  * Initializes a hashset expecting expected_element size
 517  */
 518 void hashset_init_size(HashSet *this, size_t expected_elements)
 519 {
 520         size_t needed_size;
 521         size_t po2size;
 522
 523         if(expected_elements >= UINT_MAX/2) {
 524                 abort();
 525         }
 526
 527         needed_size = expected_elements * (1.0 / HT_OCCUPANCY_FLT);
 528         po2size = ceil_po2(needed_size);
 529         init_size(this, po2size);
 530 }
 531
 532 /**
 533  * Initializes a hashset iterator. The memory for the allocator has to be
 534  * already allocated.
 535  * @note it is not allowed to remove or insert elements while iterating
 536  */
 537 void hashset_iterator_init(HashSetIterator *this, const HashSet *hashset)
 538 {
 539         this->current_bucket = hashset->entries - 1;
 540         this->end = hashset->entries + hashset->num_buckets;
 541 #ifndef NDEBUG
 542         this->set = hashset;
 543         this->entries_version = hashset->entries_version;
 544 #endif
 545 }
 546
 547 /**
 548  * Returns the next value in the iterator or NULL if no value is left
 549  * in the hashset.
 550  * @note it is not allowed to remove or insert elements while iterating
 551  */
 552 ValueType hashset_iterator_next(HashSetIterator *this)
 553 {
 554         HashSetEntry *current_bucket = this->current_bucket;
 555         HashSetEntry *end = this->end;
 556
 557         if(current_bucket >= end)
 558                 return NullValue;
 559
 560         /* using hashset_insert or hashset_remove is not allowed while iterating */
 561         assert(this->entries_version == this->set->entries_version);
 562
 563         do {
 564                 current_bucket++;
 565         } while(current_bucket < end &&
 566                         (EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket)));
 567
 568         if(current_bucket >= end)
 569                 return NullValue;
 570
 571         this->current_bucket = current_bucket;
 572         return EntryGetValue(*current_bucket);
 573 }
 574
 575 /**
 576  * Removes the element the iterator points to. Removing an element a second time
 577  * has no result.
 578  */
 579 void hashset_remove_iterator(HashSet *this, const HashSetIterator *iter)
 580 {
 581         HashSetEntry *entry = iter->current_bucket;
 582
 583         /* iterator_next needs to have been called at least once */
 584         assert(entry >= this->entries);
 585         /* needs to be on a valid element */
 586         assert(entry < this->entries + this->num_buckets);
 587
 588         if(EntryIsDeleted(*entry))
 589                 return;
 590
 591         EntrySetDeleted(*entry);
 592         this->num_deleted++;
 593         this->consider_shrink = 1;
 594 }
 595
 596 #endif