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

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