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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
#pragma once
#include <string.h>
#include "WAVM/Inline/Assert.h"
#include "WAVM/Inline/BasicTypes.h"
#include "WAVM/Inline/Errors.h"
#include "WAVM/Inline/Hash.h"
#include "WAVM/Platform/Intrinsic.h"
namespace WAVM {
// Encapsulates a set of integers that are in the range 0 to maxIndexPlusOne (excluding
// maxIndexPlusOne). It uses 1 bit of storage for each integer in the range, and many operations
// look at all bits, so it's best suited to small ranges. However, this avoids heap allocations,
// and so is pretty fast for sets of small integers (e.g. U8).
template<typename Index, Uptr maxIndexPlusOne> struct DenseStaticIntSet
{
DenseStaticIntSet() { memset(elements, 0, sizeof(elements)); }
DenseStaticIntSet(Index index)
{
memset(elements, 0, sizeof(elements));
add(index);
}
// Queries
inline bool contains(Index index) const
{
WAVM_ASSERT((Uptr)index < maxIndexPlusOne);
return (elements[index / indicesPerElement]
& (Element(1) << (index % indicesPerElement)))
!= 0;
}
bool isEmpty() const
{
Element combinedElements = 0;
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{ combinedElements |= elements[elementIndex]; }
return combinedElements == 0;
}
inline Index getSmallestMember() const
{
// Find the first element that has any bits set.
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{
if(elements[elementIndex])
{
// Find the index of the lowest set bit in the element using
// countTrailingZeroes.
const Index result = (Index)(elementIndex * indicesPerElement
+ countTrailingZeroes(elements[elementIndex]));
WAVM_ASSERT(contains(result));
return result;
}
}
return maxIndexPlusOne;
}
inline Index getSmallestNonMember() const
{
// Find the first element that doesn't have all bits set.
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{
if(~elements[elementIndex] != 0)
{
// Find the index of the lowest set bit in the element using
// countTrailingZeroes.
const Index result = (Index)(elementIndex * indicesPerElement
+ countTrailingZeroes(~elements[elementIndex]));
if(result >= maxIndexPlusOne) { break; }
else
{
WAVM_ASSERT(!contains(result));
return result;
}
}
}
return maxIndexPlusOne;
}
// Adding/removing indices
inline void add(Index index)
{
WAVM_ASSERT((Uptr)index < maxIndexPlusOne);
elements[index / indicesPerElement] |= Element(1) << (index % indicesPerElement);
}
inline void addRange(Index rangeMin, Index rangeMax)
{
WAVM_ASSERT(rangeMin <= rangeMax);
WAVM_ASSERT((Uptr)rangeMax < maxIndexPlusOne);
for(Index index = rangeMin; index <= rangeMax; ++index) { add(index); }
}
inline bool remove(Index index)
{
const Element elementMask = Element(1) << (index % indicesPerElement);
const bool hadIndex = (elements[index / indicesPerElement] & elementMask) != 0;
elements[index / indicesPerElement] &= ~elementMask;
return hadIndex;
}
// Logical operators
friend DenseStaticIntSet operator~(const DenseStaticIntSet& set)
{
DenseStaticIntSet result;
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{ result.elements[elementIndex] = ~set.elements[elementIndex]; }
return result;
}
friend DenseStaticIntSet operator|(const DenseStaticIntSet& left,
const DenseStaticIntSet& right)
{
DenseStaticIntSet result;
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{
result.elements[elementIndex]
= left.elements[elementIndex] | right.elements[elementIndex];
}
return result;
}
friend DenseStaticIntSet operator&(const DenseStaticIntSet& left,
const DenseStaticIntSet& right)
{
DenseStaticIntSet result;
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{
result.elements[elementIndex]
= left.elements[elementIndex] & right.elements[elementIndex];
}
return result;
}
friend DenseStaticIntSet operator^(const DenseStaticIntSet& left,
const DenseStaticIntSet& right)
{
DenseStaticIntSet result;
for(Uptr elementIndex = 0; elementIndex < numElements; ++elementIndex)
{
result.elements[elementIndex]
= left.elements[elementIndex] ^ right.elements[elementIndex];
}
return result;
}
// Comparisons
friend bool operator==(const DenseStaticIntSet& left, const DenseStaticIntSet& right)
{
return memcmp(left.elements, right.elements, sizeof(DenseStaticIntSet::elements)) == 0;
}
friend bool operator!=(const DenseStaticIntSet& left, const DenseStaticIntSet& right)
{
return memcmp(left.elements, right.elements, sizeof(DenseStaticIntSet::elements)) != 0;
}
friend bool operator<(const DenseStaticIntSet& left, const DenseStaticIntSet& right)
{
return memcmp(left.elements, right.elements, sizeof(DenseStaticIntSet::elements)) < 0;
}
Uptr getHash(Uptr seed = 0) const { return XXH<Uptr>(elements, sizeof(elements), seed); }
private:
typedef Uptr Element;
static constexpr Uptr indicesPerElement = sizeof(Element) * 8;
static constexpr Uptr numElements
= (maxIndexPlusOne + indicesPerElement - 1) / indicesPerElement;
Element elements[numElements];
};
template<typename Index, Uptr maxIndexPlusOne>
struct Hash<DenseStaticIntSet<Index, maxIndexPlusOne>>
{
Uptr operator()(const DenseStaticIntSet<Index, maxIndexPlusOne>& set, Uptr seed = 0) const
{
return set.getHash(seed);
}
};
}
|
