1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#pragma once
#include "Compat.h"
#include "BigAlloc.h"
#include "FixedSizeMap.h"
#include "exit.h"
#include "Error.h"
//
// A fixed-capacity hash set that allows for efficient clearing and reuse through epochs
// and does not perform any memory allocation.
//
// This class only allows the capacity to be a power of 2.
//
template< typename K, typename Hash = NumericHash<K> >
class FixedSizeSet
{
public:
FixedSizeSet(int capacity_ = 16): entries(NULL), size(0) {
reserve(capacity_);
}
~FixedSizeSet() {
delete[] entries;
}
void reserve(int capacity) {
if (!isPowerOf2(capacity)) {
WriteErrorMessage("FixedSizeSet capacity must be a power of 2\n");
soft_exit(1);
}
if (entries != NULL) {
if (size > 0) {
WriteErrorMessage("reserve() called on a non-empty FixedSizeSet\n");
soft_exit(1);
}
delete[] entries;
}
this->capacity = capacity;
this->mask = capacity - 1;
entries = new Entry[capacity];
for (int i = 0; i < capacity; i++) {
entries[i].epoch = 0;
}
epoch = 1;
}
void clear() {
size = 0;
epoch++;
if (epoch > 100000000) {
// Reset the epoch of every bucket to 0 and the current epoch to 1
for (int i = 0; i < capacity; i++) {
entries[i].epoch = 0;
}
epoch = 1;
}
}
inline bool contains(K key) {
unsigned pos = hash(key) & mask;
int i = 1;
while (true) {
if (entries[pos].epoch != epoch) {
return false;
} else if (entries[pos].key == key) {
return true;
} else {
pos = (pos + i) & mask;
i++;
}
}
}
inline void add(K key) {
_ASSERT(size < capacity);
unsigned pos = hash(key) & mask;
int i = 1;
while (true) {
if (entries[pos].epoch != epoch) {
entries[pos].key = key;
entries[pos].epoch = epoch;
size++;
if (size >= capacity) { // Can't be exactly equal, because then contains with a non-existant element infinite loops
WriteErrorMessage("FixedSizeSet overflowed. Code bug.\n");
soft_exit(1);
}
return;
} else if (entries[pos].key == key) {
return;
} else {
pos = (pos + i) & mask;
i++;
}
}
}
void *operator new(size_t size) {return BigAlloc(size);}
void operator delete(void *ptr) {BigDealloc(ptr);}
private:
struct Entry {
K key;
int epoch;
void *operator new[](size_t size) {return BigAlloc(size);}
void operator delete[](void *ptr) {BigDealloc(ptr);}
};
Entry *entries;
int capacity;
int size;
int maxSize;
int mask;
int epoch;
Hash hash;
bool isPowerOf2(int n) {
while (n > 0) {
if (n == 1) {
return true;
} else if (n % 2 == 1) {
return false;
} else {
n /= 2;
}
}
return false;
}
};
|
