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
|
#ifndef SLANG_CORE_UINT_SET_H
#define SLANG_CORE_UINT_SET_H
#include "slang-list.h"
#include "slang-math.h"
#include "slang-common.h"
#include "slang-hash.h"
#include <memory.h>
namespace Slang
{
/* Hold a set of UInt values. Implementation works by storing as a bit per value */
class UIntSet
{
public:
typedef UIntSet ThisType;
typedef uint32_t Element; ///< Type that holds the bits to say if value is present
UIntSet() {}
UIntSet(const UIntSet& other) { m_buffer = other.m_buffer; }
UIntSet(UIntSet && other) { *this = (_Move(other)); }
UIntSet(UInt maxVal) { resizeAndClear(maxVal); }
UIntSet& operator=(UIntSet&& other);
UIntSet& operator=(const UIntSet& other);
HashCode getHashCode();
/// Return the count of all bits directly represented
Int getCount() const { return Int(m_buffer.getCount()) * kElementSize; }
/// Resize such that val can be stored and clear contents
void resizeAndClear(UInt val);
/// Set all of the values up to count, as set
void setAll();
/// Resize (but maintain contents) up to bit size.
/// NOTE! That since storage is in Element blocks, it may mean some values after size are set (up to the Element boundary)
void resize(UInt size);
/// Clear all of the contents (by clearing the bits)
void clear();
/// Clear all the contents and free memory
void clearAndDeallocate();
/// Add a value
inline void add(UInt val);
/// Remove a value
inline void remove(UInt val);
/// Returns true if the value is present
inline bool contains(UInt val) const;
inline bool contains(const UIntSet& set) const;
/// ==
bool operator==(const UIntSet& set) const;
/// !=
bool operator!=(const UIntSet& set) const { return !(*this == set); }
/// Store the union between this and set in this
void unionWith(const UIntSet& set);
/// Store the intersection between this and set in this
void intersectWith(const UIntSet& set);
///
bool isEmpty() const;
/// Swap this with rhs
void swapWith(ThisType& rhs) { m_buffer.swapWith(rhs.m_buffer); }
/// Store the union of set1 and set2 in outRs
static void calcUnion(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2);
/// Store the intersection of set1 and set2 in outRs
static void calcIntersection(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2);
/// Store the subtraction of set2 from set1 in outRs
static void calcSubtract(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2);
/// Returns true if set1 and set2 have a same value set (ie there is an intersection)
static bool hasIntersection(const UIntSet& set1, const UIntSet& set2);
private:
enum
{
kElementShift = 5, ///< How many bits to shift to get Element index from an index
kElementSize = sizeof(Element) * 8, ///< The number of bits in an element
kElementMask = kElementSize - 1, ///< Mask to get shift from an index
};
// Make sure they are correct for the Element type
SLANG_COMPILE_TIME_ASSERT((1 << kElementShift) == kElementSize);
List<Element> m_buffer;
};
// --------------------------------------------------------------------------
inline void UIntSet::remove(UInt val)
{
const Index idx = Index(val >> kElementShift);
if (idx < m_buffer.getCount())
{
m_buffer[idx] &= ~(Element(1) << (val & kElementMask));
}
}
// --------------------------------------------------------------------------
inline bool UIntSet::contains(UInt val) const
{
const Index idx = Index(val >> kElementShift);
return idx < m_buffer.getCount() &&
((m_buffer[idx] & (Element(1) << (val & kElementMask))) != 0);
}
// --------------------------------------------------------------------------
inline bool UIntSet::contains(const UIntSet& set) const
{
for (Index i = 0; i < set.m_buffer.getCount(); i++)
{
if (i >= m_buffer.getCount())
{
if (set.m_buffer[i])
return false;
}
else
{
if ((m_buffer[i] & set.m_buffer[i]) != set.m_buffer[i])
return false;
}
}
return true;
}
// --------------------------------------------------------------------------
inline void UIntSet::add(UInt val)
{
const Index idx = Index(val >> kElementShift);
if (idx >= m_buffer.getCount())
{
resize(val + 1);
}
m_buffer[idx] |= Element(1) << (val & kElementMask);
}
}
#endif
|
