-
Notifications
You must be signed in to change notification settings - Fork 67
/
FixedSizeSet.h
125 lines (112 loc) · 3.01 KB
/
FixedSizeSet.h
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
#pragma once
#include "Compat.h"
#include "BigAlloc.h"
#include "FixedSizeMap.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)) {
fprintf(stderr, "FixedSizeSet capacity must be a power of 2\n");
exit(1);
}
if (entries != NULL) {
if (size > 0) {
fprintf(stderr, "reserve() called on a non-empty FixedSizeSet\n");
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++;
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;
}
};