17
17
#include " llvm/ADT/None.h"
18
18
#include " llvm/ADT/SmallPtrSet.h"
19
19
#include " llvm/ADT/SmallVector.h"
20
+ #include " llvm/ADT/iterator.h"
20
21
#include " llvm/Support/Compiler.h"
22
+ #include " llvm/Support/type_traits.h"
21
23
#include < cstddef>
22
24
#include < functional>
23
25
#include < set>
26
+ #include < type_traits>
24
27
#include < utility>
25
28
26
29
namespace llvm {
27
30
31
+ // / SmallSetIterator - This class implements a const_iterator for SmallSet by
32
+ // / delegating to the underlying SmallVector or Set iterators.
33
+ template <typename T, unsigned N, typename C>
34
+ class SmallSetIterator
35
+ : public iterator_facade_base<SmallSetIterator<T, N, C>,
36
+ std::forward_iterator_tag, T> {
37
+ private:
38
+ using SetIterTy = typename std::set<T, C>::const_iterator;
39
+ using VecIterTy = typename SmallVector<T, N>::const_iterator;
40
+ using SelfTy = SmallSetIterator<T, N, C>;
41
+
42
+ // / Iterators to the parts of the SmallSet containing the data. They are set
43
+ // / depending on isSmall.
44
+ union {
45
+ SetIterTy SetIter;
46
+ VecIterTy VecIter;
47
+ };
48
+
49
+ bool isSmall;
50
+
51
+ public:
52
+ SmallSetIterator (SetIterTy SetIter) : SetIter(SetIter), isSmall(false ) {}
53
+
54
+ SmallSetIterator (VecIterTy VecIter) : VecIter(VecIter), isSmall(true ) {}
55
+
56
+ // Spell out destructor, copy/move constructor and assignment operators for
57
+ // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
58
+ ~SmallSetIterator () {
59
+ if (isSmall)
60
+ VecIter.~VecIterTy ();
61
+ else
62
+ SetIter.~SetIterTy ();
63
+ }
64
+
65
+ SmallSetIterator (const SmallSetIterator &Other) : isSmall(Other.isSmall) {
66
+ if (isSmall)
67
+ VecIter = Other.VecIter ;
68
+ else
69
+ // Use placement new, to make sure SetIter is properly constructed, even
70
+ // if it is not trivially copy-able (e.g. in MSVC).
71
+ new (&SetIter) SetIterTy (Other.SetIter );
72
+ }
73
+
74
+ SmallSetIterator (SmallSetIterator &&Other) : isSmall(Other.isSmall) {
75
+ if (isSmall)
76
+ VecIter = std::move (Other.VecIter );
77
+ else
78
+ // Use placement new, to make sure SetIter is properly constructed, even
79
+ // if it is not trivially copy-able (e.g. in MSVC).
80
+ new (&SetIter) SetIterTy (std::move (Other.SetIter ));
81
+ }
82
+
83
+ SmallSetIterator& operator =(const SmallSetIterator& Other) {
84
+ // Call destructor for SetIter, so it gets properly destroyed if it is
85
+ // not trivially destructible in case we are setting VecIter.
86
+ if (!isSmall)
87
+ SetIter.~SetIterTy ();
88
+
89
+ isSmall = Other.isSmall ;
90
+ if (isSmall)
91
+ VecIter = Other.VecIter ;
92
+ else
93
+ new (&SetIter) SetIterTy (Other.SetIter );
94
+ return *this ;
95
+ }
96
+
97
+ SmallSetIterator& operator =(SmallSetIterator&& Other) {
98
+ // Call destructor for SetIter, so it gets properly destroyed if it is
99
+ // not trivially destructible in case we are setting VecIter.
100
+ if (!isSmall)
101
+ SetIter.~SetIterTy ();
102
+
103
+ isSmall = Other.isSmall ;
104
+ if (isSmall)
105
+ VecIter = std::move (Other.VecIter );
106
+ else
107
+ new (&SetIter) SetIterTy (std::move (Other.SetIter ));
108
+ return *this ;
109
+ }
110
+
111
+ bool operator ==(const SmallSetIterator &RHS) const {
112
+ if (isSmall != RHS.isSmall )
113
+ return false ;
114
+ if (isSmall)
115
+ return VecIter == RHS.VecIter ;
116
+ return SetIter == RHS.SetIter ;
117
+ }
118
+
119
+ SmallSetIterator &operator ++() { // Preincrement
120
+ if (isSmall)
121
+ VecIter++;
122
+ else
123
+ SetIter++;
124
+ return *this ;
125
+ }
126
+
127
+ const T &operator *() const { return isSmall ? *VecIter : *SetIter; }
128
+ };
129
+
28
130
// / SmallSet - This maintains a set of unique values, optimizing for the case
29
131
// / when the set is small (less than N). In this case, the set can be
30
132
// / maintained with no mallocs. If the set gets large, we expand to using an
31
133
// / std::set to maintain reasonable lookup times.
32
- // /
33
- // / Note that this set does not provide a way to iterate over members in the
34
- // / set.
35
134
template <typename T, unsigned N, typename C = std::less<T>>
36
135
class SmallSet {
37
136
// / Use a SmallVector to hold the elements here (even though it will never
@@ -50,6 +149,7 @@ class SmallSet {
50
149
51
150
public:
52
151
using size_type = size_t ;
152
+ using const_iterator = SmallSetIterator<T, N, C>;
53
153
54
154
SmallSet () = default ;
55
155
@@ -121,6 +221,18 @@ class SmallSet {
121
221
Set.clear ();
122
222
}
123
223
224
+ const_iterator begin () const {
225
+ if (isSmall ())
226
+ return {Vector.begin ()};
227
+ return {Set.begin ()};
228
+ }
229
+
230
+ const_iterator end () const {
231
+ if (isSmall ())
232
+ return {Vector.end ()};
233
+ return {Set.end ()};
234
+ }
235
+
124
236
private:
125
237
bool isSmall () const { return Set.empty (); }
126
238
0 commit comments