4 * @brief Geberic hashset implementation
5 * @author Matthias Braun, inspiration from densehash from google sparsehash
10 * You have to specialize this file by defining:
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>
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:
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>
36 * You can further fine tune your hashset by defining the following:
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
44 * <li><b>ADDITIONAL_DATA<b> Additional fields appended to the hashset struct</li>
53 #include "bitfiddle.h"
56 /* quadratic probing */
58 #define JUMP(num_probes) (num_probes)
63 #define Hash(this,value) ((unsigned)(value))
67 #define HashSetEntry ValueType
68 #define EntrySetHash(entry,new_hash)
69 #define EntryGetHash(this,entry) Hash(this,entry)
70 #define EntryGetValue(entry) (entry)
72 #define EntryGetHash(this,entry) (entry).hash
73 #define EntrySetHash(entry,new_hash) (entry).hash = (new_hash)
74 #define EntryGetValue(entry) (entry).data
79 #define Alloc(size) (HashSetEntry*) xmalloc((size) * sizeof(HashSetEntry))
80 #define Free(ptr) free(ptr)
84 #define InsertReturnValue int
85 #define GetInsertReturnValue(entry,new) (new)
87 #define InsertReturnValue ValueType
88 #define GetInsertReturnValue(entry,new) EntryGetValue(entry)
92 #define KeyType ValueType
93 #define GetKey(value) (value)
94 #define InitData(this,value,key) (value) = (key)
98 #define ConstKeyType const KeyType
101 #ifndef EntrySetEmpty
102 #define EntrySetEmpty(entry) EntryGetValue(entry) = NullValue
104 #ifndef EntrySetDeleted
105 #define EntrySetDeleted(entry) EntryGetValue(entry) = DeletedValue
108 #define EntryIsEmpty(entry) (EntryGetValue(entry) == NullValue)
110 #ifndef EntryIsDeleted
111 #define EntryIsDeleted(entry) (EntryGetValue(entry) == DeletedValue)
113 #ifndef SetRangeEmpty
114 #define SetRangeEmpty(ptr,size) \
117 size_t _size = (size); \
118 HashSetEntry *entries = (ptr); \
119 for(_i = 0; _i < _size; ++_i) { \
120 HashSetEntry *entry = & entries[_i]; \
121 EntrySetEmpty(*entry); \
126 #ifndef HT_OCCUPANCY_FLT
127 /** how full before we double size */
128 #define HT_OCCUPANCY_FLT 0.5f
132 /** how empty before we half size */
133 #define HT_EMPTY_FLT (0.4f * (HT_OCCUPANCY_FLT))
136 #ifndef HT_MIN_BUCKETS
137 /** default smallest bucket size */
138 #define HT_MIN_BUCKETS 32
141 #define ILLEGAL_POS ((size_t)-1)
144 #error You have to redefine hashset_init
146 #ifndef hashset_init_size
147 #error You have to redefine hashset_init_size
149 #ifndef hashset_destroy
150 #error You have to redefine hashset_destroy
152 #ifndef hashset_insert
153 #error You have to redefine hashset_insert
155 #ifndef hashset_remove
156 #error You have to redefine hashset_remove
159 #error You have to redefine hashset_find
162 #error You have to redefine hashset_size
164 #ifndef hashset_iterator_init
165 #error You have to redefine hashset_iterator_init
167 #ifndef hashset_iterator_next
168 #error You have to redefine hashset_iterator_next
170 #ifndef hashset_remove_iterator
171 #error You have to redefine hashset_remove_iterator
175 * Returns the number of elements in the hashset
177 size_t hashset_size(const HashSet *this)
179 return this->num_elements - this->num_deleted;
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()
189 InsertReturnValue insert_nogrow(HashSet *this, KeyType key)
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;
198 assert((num_buckets & (num_buckets - 1)) == 0);
201 HashSetEntry *entry = & this->entries[bucknum];
203 if(EntryIsEmpty(*entry)) {
205 HashSetEntry *nentry;
207 if(insert_pos != ILLEGAL_POS) {
213 nentry = &this->entries[p];
214 InitData(this, EntryGetValue(*nentry), key);
215 EntrySetHash(*nentry, hash);
216 this->num_elements++;
217 return GetInsertReturnValue(*nentry, 1);
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);
230 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
231 assert(num_probes < num_buckets);
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.
241 void insert_new(HashSet *this, unsigned hash, ValueType value)
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;
249 assert(value != NullValue);
252 HashSetEntry *entry = & this->entries[bucknum];
254 if(EntryIsEmpty(*entry)) {
256 HashSetEntry *nentry;
258 if(insert_pos != ILLEGAL_POS) {
263 nentry = &this->entries[p];
265 EntryGetValue(*nentry) = value;
266 EntrySetHash(*nentry, hash);
267 this->num_elements++;
270 assert(!EntryIsDeleted(*entry));
273 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
274 assert(num_probes < num_buckets);
279 * calculate shrink and enlarge limits
283 void reset_thresholds(HashSet *this)
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;
295 void resize(HashSet *this, size_t new_size)
297 size_t num_buckets = this->num_buckets;
299 HashSetEntry *old_entries = this->entries;
300 HashSetEntry *new_entries;
302 /* allocate a new array with double size */
303 new_entries = Alloc(new_size);
304 SetRangeEmpty(new_entries, new_size);
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;
312 this->entries_version++;
314 reset_thresholds(this);
316 /* reinsert all elements */
317 for(i = 0; i < num_buckets; ++i) {
318 HashSetEntry *entry = & old_entries[i];
319 if(EntryIsEmpty(*entry) || EntryIsDeleted(*entry))
322 insert_new(this, EntryGetHash(this, *entry), EntryGetValue(*entry));
325 /* now we can free the old array */
330 * grow the hashset if adding 1 more elements would make it too crowded
334 void maybe_grow(HashSet *this)
338 if(LIKELY(this->num_elements + 1 <= this->enlarge_threshold))
341 /* double table size */
342 resize_to = this->num_buckets * 2;
343 resize(this, resize_to);
347 * shrink the hashset if it is only sparsely filled
351 void maybe_shrink(HashSet *this)
356 if(!this->consider_shrink)
359 this->consider_shrink = 0;
360 size = hashset_size(this);
361 if(LIKELY(size > this->shrink_threshold))
364 resize_to = ceil_po2(size);
369 resize(this, resize_to);
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.)
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)
382 InsertReturnValue hashset_insert(HashSet *this, KeyType key)
385 this->entries_version++;
390 return insert_nogrow(this, key);
394 * Searchs for an element with key @p key.
396 * @param this the hashset
397 * @param key the key to search for
398 * @returns the found value or NullValue if nothing was found
400 ValueType hashset_find(const HashSet *this, ConstKeyType key)
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;
409 HashSetEntry *entry = & this->entries[bucknum];
411 if(EntryIsEmpty(*entry)) {
414 if(EntryIsDeleted(*entry)) {
416 } else if(EntryGetHash(this, *entry) == hash) {
417 if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) {
419 return EntryGetValue(*entry);
424 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
425 assert(num_probes < num_buckets);
430 * Removes an element from a hashset. Does nothing if the set doesn't contain
433 * @param this the hashset
434 * @param key key that identifies the data to remove
436 void hashset_remove(HashSet *this, ConstKeyType key)
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;
445 this->entries_version++;
449 HashSetEntry *entry = & this->entries[bucknum];
451 if(EntryIsEmpty(*entry)) {
454 if(EntryIsDeleted(*entry)) {
456 } else if(EntryGetHash(this, *entry) == hash) {
457 if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) {
458 EntrySetDeleted(*entry);
460 this->consider_shrink = 1;
466 bucknum = (bucknum + JUMP(num_probes)) & hashmask;
467 assert(num_probes < num_buckets);
472 * Initializes hashset with a specific size
476 void init_size(HashSet *this, size_t initial_size)
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;
488 this->entries_version = 0;
491 reset_thresholds(this);
495 * Initialializes a hashset with the default size. The memory for the set has to
498 void hashset_init(HashSet *this)
500 init_size(this, HT_MIN_BUCKETS);
504 * Destroys a hashset, freeing all used memory (except the memory for the
505 * HashSet struct itself).
507 void hashset_destroy(HashSet *this)
511 this->entries = NULL;
516 * Initializes a hashset expecting expected_element size
518 void hashset_init_size(HashSet *this, size_t expected_elements)
523 if(expected_elements >= UINT_MAX/2) {
527 needed_size = expected_elements * (1.0 / HT_OCCUPANCY_FLT);
528 po2size = ceil_po2(needed_size);
529 init_size(this, po2size);
533 * Initializes a hashset iterator. The memory for the allocator has to be
535 * @note it is not allowed to remove or insert elements while iterating
537 void hashset_iterator_init(HashSetIterator *this, const HashSet *hashset)
539 this->current_bucket = hashset->entries - 1;
540 this->end = hashset->entries + hashset->num_buckets;
543 this->entries_version = hashset->entries_version;
548 * Returns the next value in the iterator or NULL if no value is left
550 * @note it is not allowed to remove or insert elements while iterating
552 ValueType hashset_iterator_next(HashSetIterator *this)
554 HashSetEntry *current_bucket = this->current_bucket;
555 HashSetEntry *end = this->end;
557 if(current_bucket >= end)
560 /* using hashset_insert or hashset_remove is not allowed while iterating */
561 assert(this->entries_version == this->set->entries_version);
565 } while(current_bucket < end &&
566 (EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket)));
568 if(current_bucket >= end)
571 this->current_bucket = current_bucket;
572 return EntryGetValue(*current_bucket);
576 * Removes the element the iterator points to. Removing an element a second time
579 void hashset_remove_iterator(HashSet *this, const HashSetIterator *iter)
581 HashSetEntry *entry = iter->current_bucket;
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);
588 if(EntryIsDeleted(*entry))
591 EntrySetDeleted(*entry);
593 this->consider_shrink = 1;
597 __attribute__((unused)) static int dummy;