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
|
#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 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;
/// ==
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;
/// 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 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
|
