hashset.c 16.8 KB
Newer Older
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Matthias Braun's avatar
Matthias Braun committed
20
21
/**
 * @file
22
 * @brief   Generic hashset implementation
Matthias Braun's avatar
Matthias Braun committed
23
24
 * @author  Matthias Braun, inspiration from densehash from google sparsehash
 *          package
25
 * @date    17.03.2007
Matthias Braun's avatar
Matthias Braun committed
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 *
 *
 * You have to specialize this file by defining:
 *
 * <ul>
 *  <li><b>HashSet</b>         The name of the hashset type</li>
 *  <li><b>HashSetIterator</b> The name of the hashset iterator type</li>
 *  <li><b>ValueType</b>       The type of the stored data values</li>
 *  <li><b>NullValue</b>       A special value representing no values</li>
 *  <li><b>DeletedValue</b>    A special value representing deleted entries</li>
 *  <li><b>Hash(hashset,key)</b> calculates the hash value for a given key</li>
 * </ul>
 *
 * Note that by default it is assumed that the data values themselfes are used
 * as keys. However you can change that with additional defines:
 *
 * <ul>
 *  <li><b>KeyType</b>         The type of the keys identifying data values.
 *                             Defining this implies, that a data value contains
 *                             more than just the key.</li>
 *  <li><b>GetKey(value)</b>   Extracts the key from a data value</li>
 *  <li><b>KeysEqual(hashset,key1,key2)</b>  Tests wether 2 keys are equal</li>
 *  <li><b>DO_REHASH</b>       Instead of storing the hash-values, recalculate
Christoph Mallon's avatar
Christoph Mallon committed
49
 *                             them on demand from the datavalues. (useful if
Matthias Braun's avatar
Matthias Braun committed
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 *                             calculating the hash-values takes less time than
 *                             a memory access)</li>
 * </ul>
 *
 * You can further fine tune your hashset by defining the following:
 *
 * <ul>
 *  <li><b>JUMP(num_probes)</b> The probing method</li>
 *  <li><b>Alloc(count)</b>     Allocates count hashset entries (NOT bytes)</li>
 *  <li><b>Free(ptr)</b>        Frees a block of memory allocated by Alloc</li>
 *  <li><b>SetRangeEmpty(ptr,count)</b> Efficiently sets a range of elements to
 *                                      the Null value</li>
 *  <li><b>ADDITIONAL_DATA<b>   Additional fields appended to the hashset struct</li>
 * </ul>
 */
#ifdef HashSet

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "bitfiddle.h"
#include "util.h"

/* quadratic probing */
#ifndef JUMP
#define JUMP(num_probes)      (num_probes)
Christian Würdig's avatar
Christian Würdig committed
77
#endif /* JUMP */
Matthias Braun's avatar
Matthias Braun committed
78
79
80

#ifndef Hash
#define ID_HASH
Michael Beck's avatar
Michael Beck committed
81
#define Hash(self,key)        ((unsigned)(((char *)key) - (char *)0))
Christian Würdig's avatar
Christian Würdig committed
82
#endif /* Hash */
Matthias Braun's avatar
Matthias Braun committed
83
84
85

#ifdef DO_REHASH
#define HashSetEntry                   ValueType
86
#define EntrySetHash(entry,new_hash)   (void)0
Matthias Braun's avatar
Matthias Braun committed
87
#define EntryGetHash(self,entry)       Hash(self, GetKey(entry))
Matthias Braun's avatar
Matthias Braun committed
88
#define EntryGetValue(entry)           (entry)
Christian Würdig's avatar
Christian Würdig committed
89
#else /* ! DO_REHASH */
90
#define EntryGetHash(self,entry)       (entry).hash
Matthias Braun's avatar
Matthias Braun committed
91
92
#define EntrySetHash(entry,new_hash)   (entry).hash = (new_hash)
#define EntryGetValue(entry)           (entry).data
Christian Würdig's avatar
Christian Würdig committed
93
#endif /* DO_REHASH */
Matthias Braun's avatar
Matthias Braun committed
94
95
96

#ifndef Alloc
#include "xmalloc.h"
97
#define Alloc(size) XMALLOCN(HashSetEntry, (size))
Matthias Braun's avatar
Matthias Braun committed
98
#define Free(ptr)      free(ptr)
Christian Würdig's avatar
Christian Würdig committed
99
#endif /* Alloc */
Matthias Braun's avatar
Matthias Braun committed
100
101

#ifdef ID_HASH
102
103
104
105
#define FindReturnValue                 bool
#define GetFindReturnValue(entry,found) (found)
#define NullReturnValue                 false
#define InsertReturnValue(findreturn)   !(findreturn)
Christian Würdig's avatar
Christian Würdig committed
106
#else /* ! ID_HASH */
Matthias Braun's avatar
Matthias Braun committed
107
#ifdef SCALAR_RETURN
108
109
110
#define FindReturnValue                 ValueType
#define GetFindReturnValue(entry,found) EntryGetValue(entry)
#define NullReturnValue                 NullValue
Matthias Braun's avatar
Matthias Braun committed
111
#else
112
113
114
#define FindReturnValue                 ValueType*
#define GetFindReturnValue(entry,found) & EntryGetValue(entry)
#define NullReturnValue                 & NullValue
Matthias Braun's avatar
Matthias Braun committed
115
#endif
Christian Würdig's avatar
Christian Würdig committed
116
#endif /* ID_HASH */
Matthias Braun's avatar
Matthias Braun committed
117

118
119
120
121
#ifndef InsertReturnValue
#define InsertReturnValue(findreturn)   findreturn
#endif

Matthias Braun's avatar
Matthias Braun committed
122
123
124
#ifndef KeyType
#define KeyType                  ValueType
#define GetKey(value)            (value)
125
#define InitData(self,value,key) (value) = (key)
Christian Würdig's avatar
Christian Würdig committed
126
#endif /* KeyType */
Matthias Braun's avatar
Matthias Braun committed
127
128
129

#ifndef ConstKeyType
#define ConstKeyType             const KeyType
Christian Würdig's avatar
Christian Würdig committed
130
#endif /* ConstKeyType */
Matthias Braun's avatar
Matthias Braun committed
131
132
133

#ifndef EntrySetEmpty
#define EntrySetEmpty(entry)    EntryGetValue(entry) = NullValue
Christian Würdig's avatar
Christian Würdig committed
134
#endif /* EntrySetEmpty */
Matthias Braun's avatar
Matthias Braun committed
135
136
#ifndef EntrySetDeleted
#define EntrySetDeleted(entry)  EntryGetValue(entry) = DeletedValue
Christian Würdig's avatar
Christian Würdig committed
137
#endif /* EntrySetDeleted */
Matthias Braun's avatar
Matthias Braun committed
138
139
#ifndef EntryIsEmpty
#define EntryIsEmpty(entry)     (EntryGetValue(entry) == NullValue)
Christian Würdig's avatar
Christian Würdig committed
140
#endif /* EntryIsEmpty */
Matthias Braun's avatar
Matthias Braun committed
141
142
#ifndef EntryIsDeleted
#define EntryIsDeleted(entry)   (EntryGetValue(entry) == DeletedValue)
Christian Würdig's avatar
Christian Würdig committed
143
#endif /* EntryIsDeleted */
Matthias Braun's avatar
Matthias Braun committed
144
145
146
147
148
149
#ifndef SetRangeEmpty
#define SetRangeEmpty(ptr,size)                \
{                                              \
	size_t _i;                                 \
	size_t _size = (size);                     \
	HashSetEntry *entries = (ptr);             \
150
	for (_i = 0; _i < _size; ++_i) {            \
Matthias Braun's avatar
Matthias Braun committed
151
152
153
154
		HashSetEntry *entry = & entries[_i];   \
		EntrySetEmpty(*entry);                 \
	}                                          \
}
Christian Würdig's avatar
Christian Würdig committed
155
#endif /* SetRangeEmpty */
Matthias Braun's avatar
Matthias Braun committed
156
157
158

#ifndef HT_OCCUPANCY_FLT
/** how full before we double size */
159
#define HT_OCCUPANCY_FLT(x) ((x)/2)
Christian Würdig's avatar
Christian Würdig committed
160
#endif /* HT_OCCUPANCY_FLT */
161
162
163
#ifndef HT_1_DIV_OCCUPANCY_FLT
#define HT_1_DIV_OCCUPANCY_FLT 2
#endif
Matthias Braun's avatar
Matthias Braun committed
164
165
166

#ifndef HT_EMPTY_FLT
/** how empty before we half size */
167
#define HT_EMPTY_FLT(x)     ((x)/5)
Christian Würdig's avatar
Christian Würdig committed
168
#endif /* HT_EMPTY_FLT */
Matthias Braun's avatar
Matthias Braun committed
169
170
171
172

#ifndef HT_MIN_BUCKETS
/** default smallest bucket size */
#define HT_MIN_BUCKETS    32
Christian Würdig's avatar
Christian Würdig committed
173
#endif /* HT_MIN_BUCKETS */
Matthias Braun's avatar
Matthias Braun committed
174
175
176

#define ILLEGAL_POS       ((size_t)-1)

Christian Würdig's avatar
Christian Würdig committed
177
/* check that all needed functions are defined */
Matthias Braun's avatar
Matthias Braun committed
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#ifndef hashset_init
#error You have to redefine hashset_init
#endif
#ifndef hashset_init_size
#error You have to redefine hashset_init_size
#endif
#ifndef hashset_destroy
#error You have to redefine hashset_destroy
#endif
#ifndef hashset_insert
#error You have to redefine hashset_insert
#endif
#ifndef hashset_remove
#error You have to redefine hashset_remove
#endif
#ifndef hashset_find
#error You have to redefine hashset_find
#endif
#ifndef hashset_size
#error You have to redefine hashset_size
#endif
Michael Beck's avatar
Michael Beck committed
199
200

#ifndef NO_ITERATOR
Matthias Braun's avatar
Matthias Braun committed
201
202
203
204
205
206
207
208
209
#ifndef hashset_iterator_init
#error You have to redefine hashset_iterator_init
#endif
#ifndef hashset_iterator_next
#error You have to redefine hashset_iterator_next
#endif
#ifndef hashset_remove_iterator
#error You have to redefine hashset_remove_iterator
#endif
Matthias Braun's avatar
Matthias Braun committed
210
#endif
Matthias Braun's avatar
Matthias Braun committed
211
212
213
214

/**
 * Returns the number of elements in the hashset
 */
215
size_t hashset_size(const HashSet *self)
Matthias Braun's avatar
Matthias Braun committed
216
{
217
	return self->num_elements - self->num_deleted;
Matthias Braun's avatar
Matthias Braun committed
218
219
220
221
222
}

/**
 * Inserts an element into a hashset without growing the set (you have to make
 * sure there's enough room for that.
223
 * @returns  previous value if found, NullValue otherwise
Matthias Braun's avatar
Matthias Braun committed
224
225
226
 * @note also see comments for hashset_insert()
 * @internal
 */
227
static inline FindReturnValue insert_nogrow(HashSet *self, KeyType key)
Matthias Braun's avatar
Matthias Braun committed
228
{
Matthias Braun's avatar
Matthias Braun committed
229
230
231
232
233
234
	size_t   num_probes  = 0;
	size_t   num_buckets = self->num_buckets;
	size_t   hashmask    = num_buckets - 1;
	unsigned hash        = Hash(self, key);
	size_t   bucknum     = hash & hashmask;
	size_t   insert_pos  = ILLEGAL_POS;
Matthias Braun's avatar
Matthias Braun committed
235
236
237

	assert((num_buckets & (num_buckets - 1)) == 0);

238
	for (;;) {
239
		HashSetEntry *entry = & self->entries[bucknum];
Matthias Braun's avatar
Matthias Braun committed
240

241
		if (EntryIsEmpty(*entry)) {
Matthias Braun's avatar
Matthias Braun committed
242
243
244
			size_t p;
			HashSetEntry *nentry;

245
			if (insert_pos != ILLEGAL_POS) {
Matthias Braun's avatar
Matthias Braun committed
246
247
248
249
250
				p = insert_pos;
			} else {
				p = bucknum;
			}

251
252
			nentry = &self->entries[p];
			InitData(self, EntryGetValue(*nentry), key);
Matthias Braun's avatar
Matthias Braun committed
253
			EntrySetHash(*nentry, hash);
254
			self->num_elements++;
255
			return GetFindReturnValue(*nentry, false);
Matthias Braun's avatar
Matthias Braun committed
256
		}
257
258
		if (EntryIsDeleted(*entry)) {
			if (insert_pos == ILLEGAL_POS)
Matthias Braun's avatar
Matthias Braun committed
259
				insert_pos = bucknum;
260
261
		} else if (EntryGetHash(self, *entry) == hash) {
			if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) {
Matthias Braun's avatar
Matthias Braun committed
262
				// Value already in the set, return it
263
				return GetFindReturnValue(*entry, true);
Matthias Braun's avatar
Matthias Braun committed
264
265
266
267
268
269
270
271
272
			}
		}

		++num_probes;
		bucknum = (bucknum + JUMP(num_probes)) & hashmask;
		assert(num_probes < num_buckets);
	}
}

Michael Beck's avatar
Michael Beck committed
273
274
275
276
/**
 * calculate shrink and enlarge limits
 * @internal
 */
277
static inline void reset_thresholds(HashSet *self)
Michael Beck's avatar
Michael Beck committed
278
279
280
281
282
283
284
{
	self->enlarge_threshold = (size_t) HT_OCCUPANCY_FLT(self->num_buckets);
	self->shrink_threshold  = (size_t) HT_EMPTY_FLT(self->num_buckets);
	self->consider_shrink   = 0;
}

#ifndef HAVE_OWN_RESIZE
Matthias Braun's avatar
Matthias Braun committed
285
286
287
288
289
/**
 * Inserts an element into a hashset under the assumption that the hashset
 * contains no deleted entries and the element doesn't exist in the hashset yet.
 * @internal
 */
290
static void insert_new(HashSet *self, unsigned hash, ValueType value)
Matthias Braun's avatar
Matthias Braun committed
291
{
Matthias Braun's avatar
Matthias Braun committed
292
	size_t num_probes  = 0;
293
	size_t num_buckets = self->num_buckets;
Matthias Braun's avatar
Matthias Braun committed
294
295
296
	size_t hashmask    = num_buckets - 1;
	size_t bucknum     = hash & hashmask;
	size_t insert_pos  = ILLEGAL_POS;
Matthias Braun's avatar
Matthias Braun committed
297

Matthias Braun's avatar
Matthias Braun committed
298
	//assert(value != NullValue);
Matthias Braun's avatar
Matthias Braun committed
299

300
	for (;;) {
301
		HashSetEntry *entry = & self->entries[bucknum];
Matthias Braun's avatar
Matthias Braun committed
302

303
		if (EntryIsEmpty(*entry)) {
304
			size_t        p;
Matthias Braun's avatar
Matthias Braun committed
305
306
			HashSetEntry *nentry;

307
			if (insert_pos != ILLEGAL_POS) {
Matthias Braun's avatar
Matthias Braun committed
308
309
310
311
				p = insert_pos;
			} else {
				p = bucknum;
			}
312
			nentry = &self->entries[p];
Matthias Braun's avatar
Matthias Braun committed
313
314
315

			EntryGetValue(*nentry) = value;
			EntrySetHash(*nentry, hash);
316
			self->num_elements++;
Matthias Braun's avatar
Matthias Braun committed
317
318
319
320
321
322
323
324
325
326
327
328
329
330
			return;
		}
		assert(!EntryIsDeleted(*entry));

		++num_probes;
		bucknum = (bucknum + JUMP(num_probes)) & hashmask;
		assert(num_probes < num_buckets);
	}
}

/**
 * Resize the hashset
 * @internal
 */
331
static inline void resize(HashSet *self, size_t new_size)
Matthias Braun's avatar
Matthias Braun committed
332
{
333
	size_t num_buckets = self->num_buckets;
Matthias Braun's avatar
Matthias Braun committed
334
	size_t i;
335
	HashSetEntry *old_entries = self->entries;
Matthias Braun's avatar
Matthias Braun committed
336
337
338
339
340
341
342
	HashSetEntry *new_entries;

	/* allocate a new array with double size */
	new_entries = Alloc(new_size);
	SetRangeEmpty(new_entries, new_size);

	/* use the new array */
Matthias Braun's avatar
Matthias Braun committed
343
344
	self->entries      = new_entries;
	self->num_buckets  = new_size;
345
	self->num_elements = 0;
Matthias Braun's avatar
Matthias Braun committed
346
	self->num_deleted  = 0;
Matthias Braun's avatar
Matthias Braun committed
347
#ifndef NDEBUG
348
	self->entries_version++;
Matthias Braun's avatar
Matthias Braun committed
349
#endif
350
	reset_thresholds(self);
Matthias Braun's avatar
Matthias Braun committed
351
352

	/* reinsert all elements */
353
	for (i = 0; i < num_buckets; ++i) {
Matthias Braun's avatar
Matthias Braun committed
354
		HashSetEntry *entry = & old_entries[i];
355
		if (EntryIsEmpty(*entry) || EntryIsDeleted(*entry))
Matthias Braun's avatar
Matthias Braun committed
356
357
			continue;

358
		insert_new(self, EntryGetHash(self, *entry), EntryGetValue(*entry));
Matthias Braun's avatar
Matthias Braun committed
359
360
361
362
363
	}

	/* now we can free the old array */
	Free(old_entries);
}
364
365
366
#else

/* resize must be defined outside */
367
static inline void resize(HashSet *self, size_t new_size);
368
369

#endif
Matthias Braun's avatar
Matthias Braun committed
370
371
372
373
374

/**
 * grow the hashset if adding 1 more elements would make it too crowded
 * @internal
 */
375
static inline void maybe_grow(HashSet *self)
Matthias Braun's avatar
Matthias Braun committed
376
377
378
{
	size_t resize_to;

379
	if (LIKELY(self->num_elements + 1 <= self->enlarge_threshold))
Matthias Braun's avatar
Matthias Braun committed
380
381
382
		return;

	/* double table size */
383
384
	resize_to = self->num_buckets * 2;
	resize(self, resize_to);
Matthias Braun's avatar
Matthias Braun committed
385
386
387
388
389
390
}

/**
 * shrink the hashset if it is only sparsely filled
 * @internal
 */
391
static inline void maybe_shrink(HashSet *self)
Matthias Braun's avatar
Matthias Braun committed
392
393
394
395
{
	size_t size;
	size_t resize_to;

396
	if (!self->consider_shrink)
Matthias Braun's avatar
Matthias Braun committed
397
398
		return;

399
	self->consider_shrink = 0;
400
	size                  = hashset_size(self);
401
	if (size <= HT_MIN_BUCKETS)
402
403
		return;

404
	if (LIKELY(size > self->shrink_threshold))
Matthias Braun's avatar
Matthias Braun committed
405
406
407
408
		return;

	resize_to = ceil_po2(size);

409
	if (resize_to < 4)
Matthias Braun's avatar
Matthias Braun committed
410
411
		resize_to = 4;

412
	resize(self, resize_to);
Matthias Braun's avatar
Matthias Braun committed
413
414
415
}

/**
Michael Beck's avatar
Michael Beck committed
416
 * Insert an element into the hashset. If no element with the given key exists yet,
Matthias Braun's avatar
Matthias Braun committed
417
 * then a new one is created and initialized with the InitData function.
Michael Beck's avatar
Michael Beck committed
418
 * Otherwise the existing element is returned (for hashs where key is equal to
Matthias Braun's avatar
Matthias Braun committed
419
420
 * value, nothing is returned.)
 *
421
 * @param self   the hashset
Matthias Braun's avatar
Matthias Braun committed
422
423
424
 * @param key    the key that identifies the data
 * @returns      the existing or newly created data element (or nothing in case of hashs where keys are the while value)
 */
425
FindReturnValue hashset_insert(HashSet *self, KeyType key)
Matthias Braun's avatar
Matthias Braun committed
426
427
{
#ifndef NDEBUG
428
	self->entries_version++;
Matthias Braun's avatar
Matthias Braun committed
429
430
#endif

431
432
	maybe_shrink(self);
	maybe_grow(self);
433
	return InsertReturnValue(insert_nogrow(self, key));
Matthias Braun's avatar
Matthias Braun committed
434
435
436
}

/**
Michael Beck's avatar
Michael Beck committed
437
 * Searches for an element with key @p key.
Matthias Braun's avatar
Matthias Braun committed
438
 *
439
 * @param self      the hashset
Matthias Braun's avatar
Matthias Braun committed
440
441
442
 * @param key       the key to search for
 * @returns         the found value or NullValue if nothing was found
 */
443
FindReturnValue hashset_find(const HashSet *self, ConstKeyType key)
Matthias Braun's avatar
Matthias Braun committed
444
{
Matthias Braun's avatar
Matthias Braun committed
445
446
447
448
449
	size_t   num_probes  = 0;
	size_t   num_buckets = self->num_buckets;
	size_t   hashmask    = num_buckets - 1;
	unsigned hash        = Hash(self, key);
	size_t   bucknum     = hash & hashmask;
Matthias Braun's avatar
Matthias Braun committed
450

451
	for (;;) {
452
		HashSetEntry *entry = & self->entries[bucknum];
Matthias Braun's avatar
Matthias Braun committed
453

454
		if (EntryIsEmpty(*entry)) {
Matthias Braun's avatar
Matthias Braun committed
455
			return NullReturnValue;
Matthias Braun's avatar
Matthias Braun committed
456
		}
457
		if (EntryIsDeleted(*entry)) {
Matthias Braun's avatar
Matthias Braun committed
458
			// value is deleted
459
460
		} else if (EntryGetHash(self, *entry) == hash) {
			if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) {
Matthias Braun's avatar
Matthias Braun committed
461
				// found the value
462
				return GetFindReturnValue(*entry, true);
Matthias Braun's avatar
Matthias Braun committed
463
464
465
466
467
468
469
470
471
472
473
474
475
			}
		}

		++num_probes;
		bucknum = (bucknum + JUMP(num_probes)) & hashmask;
		assert(num_probes < num_buckets);
	}
}

/**
 * Removes an element from a hashset. Does nothing if the set doesn't contain
 * the element.
 *
476
 * @param self    the hashset
Matthias Braun's avatar
Matthias Braun committed
477
478
 * @param key     key that identifies the data to remove
 */
479
void hashset_remove(HashSet *self, ConstKeyType key)
Matthias Braun's avatar
Matthias Braun committed
480
{
Matthias Braun's avatar
Matthias Braun committed
481
482
483
484
485
	size_t   num_probes  = 0;
	size_t   num_buckets = self->num_buckets;
	size_t   hashmask    = num_buckets - 1;
	unsigned hash        = Hash(self, key);
	size_t   bucknum     = hash & hashmask;
Matthias Braun's avatar
Matthias Braun committed
486
487

#ifndef NDEBUG
488
	self->entries_version++;
Matthias Braun's avatar
Matthias Braun committed
489
490
#endif

491
	for (;;) {
492
		HashSetEntry *entry = & self->entries[bucknum];
Matthias Braun's avatar
Matthias Braun committed
493

494
		if (EntryIsEmpty(*entry)) {
Matthias Braun's avatar
Matthias Braun committed
495
496
			return;
		}
497
		if (EntryIsDeleted(*entry)) {
Matthias Braun's avatar
Matthias Braun committed
498
			// entry is deleted
499
500
		} else if (EntryGetHash(self, *entry) == hash) {
			if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) {
Matthias Braun's avatar
Matthias Braun committed
501
				EntrySetDeleted(*entry);
502
503
				self->num_deleted++;
				self->consider_shrink = 1;
Matthias Braun's avatar
Matthias Braun committed
504
505
506
507
508
509
510
511
512
513
514
515
516
517
				return;
			}
		}

		++num_probes;
		bucknum = (bucknum + JUMP(num_probes)) & hashmask;
		assert(num_probes < num_buckets);
	}
}

/**
 * Initializes hashset with a specific size
 * @internal
 */
518
static inline void init_size(HashSet *self, size_t initial_size)
Matthias Braun's avatar
Matthias Braun committed
519
{
520
	if (initial_size < 4)
Matthias Braun's avatar
Matthias Braun committed
521
522
		initial_size = 4;

Matthias Braun's avatar
Matthias Braun committed
523
	self->entries         = Alloc(initial_size);
524
	SetRangeEmpty(self->entries, initial_size);
Matthias Braun's avatar
Matthias Braun committed
525
	self->num_buckets     = initial_size;
526
	self->consider_shrink = 0;
Matthias Braun's avatar
Matthias Braun committed
527
528
	self->num_elements    = 0;
	self->num_deleted     = 0;
Matthias Braun's avatar
Matthias Braun committed
529
#ifndef NDEBUG
530
	self->entries_version = 0;
Matthias Braun's avatar
Matthias Braun committed
531
#endif
Michael Beck's avatar
Michael Beck committed
532
533
534
#ifdef ADDITIONAL_INIT
	ADDITIONAL_INIT
#endif
Matthias Braun's avatar
Matthias Braun committed
535

536
	reset_thresholds(self);
Matthias Braun's avatar
Matthias Braun committed
537
538
539
}

/**
Michael Beck's avatar
Michael Beck committed
540
 * Initializes a hashset with the default size. The memory for the set has to
Matthias Braun's avatar
Matthias Braun committed
541
542
 * already allocated.
 */
543
void hashset_init(HashSet *self)
Matthias Braun's avatar
Matthias Braun committed
544
{
545
	init_size(self, HT_MIN_BUCKETS);
Matthias Braun's avatar
Matthias Braun committed
546
547
548
549
550
551
}

/**
 * Destroys a hashset, freeing all used memory (except the memory for the
 * HashSet struct itself).
 */
552
void hashset_destroy(HashSet *self)
Matthias Braun's avatar
Matthias Braun committed
553
{
Michael Beck's avatar
Michael Beck committed
554
555
556
#ifdef ADDITIONAL_TERM
	ADDITIONAL_TERM
#endif
557
	Free(self->entries);
Matthias Braun's avatar
Matthias Braun committed
558
#ifndef NDEBUG
559
	self->entries = NULL;
Matthias Braun's avatar
Matthias Braun committed
560
561
562
563
#endif
}

/**
Michael Beck's avatar
Michael Beck committed
564
 * Initializes a hashset expecting expected_element size.
Matthias Braun's avatar
Matthias Braun committed
565
 */
566
void hashset_init_size(HashSet *self, size_t expected_elements)
Matthias Braun's avatar
Matthias Braun committed
567
568
569
570
{
	size_t needed_size;
	size_t po2size;

571
	if (expected_elements >= UINT_MAX/2) {
Matthias Braun's avatar
Matthias Braun committed
572
573
574
		abort();
	}

575
	needed_size = expected_elements * HT_1_DIV_OCCUPANCY_FLT;
Matthias Braun's avatar
Matthias Braun committed
576
	po2size     = ceil_po2(needed_size);
577
	init_size(self, po2size);
Matthias Braun's avatar
Matthias Braun committed
578
579
}

Michael Beck's avatar
Michael Beck committed
580
#ifndef NO_ITERATOR
Matthias Braun's avatar
Matthias Braun committed
581
582
583
584
585
/**
 * Initializes a hashset iterator. The memory for the allocator has to be
 * already allocated.
 * @note it is not allowed to remove or insert elements while iterating
 */
586
void hashset_iterator_init(HashSetIterator *self, const HashSet *hashset)
Matthias Braun's avatar
Matthias Braun committed
587
{
588
	self->current_bucket = hashset->entries - 1;
Matthias Braun's avatar
Matthias Braun committed
589
	self->end            = hashset->entries + hashset->num_buckets;
Matthias Braun's avatar
Matthias Braun committed
590
#ifndef NDEBUG
Matthias Braun's avatar
Matthias Braun committed
591
	self->set             = hashset;
592
	self->entries_version = hashset->entries_version;
Matthias Braun's avatar
Matthias Braun committed
593
594
595
596
597
598
599
600
#endif
}

/**
 * Returns the next value in the iterator or NULL if no value is left
 * in the hashset.
 * @note it is not allowed to remove or insert elements while iterating
 */
601
ValueType hashset_iterator_next(HashSetIterator *self)
Matthias Braun's avatar
Matthias Braun committed
602
{
603
	HashSetEntry *current_bucket = self->current_bucket;
Matthias Braun's avatar
Matthias Braun committed
604
	HashSetEntry *end            = self->end;
Matthias Braun's avatar
Matthias Braun committed
605
606

	/* using hashset_insert or hashset_remove is not allowed while iterating */
607
	assert(self->entries_version == self->set->entries_version);
Matthias Braun's avatar
Matthias Braun committed
608
609
610

	do {
		current_bucket++;
611
		if (current_bucket >= end)
612
			return NullValue;
613
	} while (EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket));
Matthias Braun's avatar
Matthias Braun committed
614

615
	self->current_bucket = current_bucket;
Matthias Braun's avatar
Matthias Braun committed
616
617
618
619
620
621
622
	return EntryGetValue(*current_bucket);
}

/**
 * Removes the element the iterator points to. Removing an element a second time
 * has no result.
 */
623
void hashset_remove_iterator(HashSet *self, const HashSetIterator *iter)
Matthias Braun's avatar
Matthias Braun committed
624
625
626
627
{
	HashSetEntry *entry = iter->current_bucket;

	/* iterator_next needs to have been called at least once */
628
	assert(entry >= self->entries);
Matthias Braun's avatar
Matthias Braun committed
629
	/* needs to be on a valid element */
630
	assert(entry < self->entries + self->num_buckets);
Matthias Braun's avatar
Matthias Braun committed
631

632
	if (EntryIsDeleted(*entry))
Matthias Braun's avatar
Matthias Braun committed
633
634
635
		return;

	EntrySetDeleted(*entry);
636
637
	self->num_deleted++;
	self->consider_shrink = 1;
Matthias Braun's avatar
Matthias Braun committed
638
}
Michael Beck's avatar
Michael Beck committed
639
#endif /* NO_ITERATOR */
Matthias Braun's avatar
Matthias Braun committed
640

Michael Beck's avatar
Michael Beck committed
641
#endif /* HashSet */