1 | //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file defines the SmallSet class. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ADT_SMALLSET_H |
15 | #define LLVM_ADT_SMALLSET_H |
16 | |
17 | #include "llvm/ADT/None.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/ADT/iterator.h" |
21 | #include "llvm/Support/Compiler.h" |
22 | #include "llvm/Support/type_traits.h" |
23 | #include <cstddef> |
24 | #include <functional> |
25 | #include <set> |
26 | #include <type_traits> |
27 | #include <utility> |
28 | |
29 | namespace llvm { |
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 | |
130 | /// SmallSet - This maintains a set of unique values, optimizing for the case |
131 | /// when the set is small (less than N). In this case, the set can be |
132 | /// maintained with no mallocs. If the set gets large, we expand to using an |
133 | /// std::set to maintain reasonable lookup times. |
134 | template <typename T, unsigned N, typename C = std::less<T>> |
135 | class SmallSet { |
136 | /// Use a SmallVector to hold the elements here (even though it will never |
137 | /// reach its 'large' stage) to avoid calling the default ctors of elements |
138 | /// we will never use. |
139 | SmallVector<T, N> Vector; |
140 | std::set<T, C> Set; |
141 | |
142 | using VIterator = typename SmallVector<T, N>::const_iterator; |
143 | using mutable_iterator = typename SmallVector<T, N>::iterator; |
144 | |
145 | // In small mode SmallPtrSet uses linear search for the elements, so it is |
146 | // not a good idea to choose this value too high. You may consider using a |
147 | // DenseSet<> instead if you expect many elements in the set. |
148 | static_assert(N <= 32, "N should be small" ); |
149 | |
150 | public: |
151 | using size_type = size_t; |
152 | using const_iterator = SmallSetIterator<T, N, C>; |
153 | |
154 | SmallSet() = default; |
155 | |
156 | LLVM_NODISCARD bool empty() const { |
157 | return Vector.empty() && Set.empty(); |
158 | } |
159 | |
160 | size_type size() const { |
161 | return isSmall() ? Vector.size() : Set.size(); |
162 | } |
163 | |
164 | /// count - Return 1 if the element is in the set, 0 otherwise. |
165 | size_type count(const T &V) const { |
166 | if (isSmall()) { |
167 | // Since the collection is small, just do a linear search. |
168 | return vfind(V) == Vector.end() ? 0 : 1; |
169 | } else { |
170 | return Set.count(V); |
171 | } |
172 | } |
173 | |
174 | /// insert - Insert an element into the set if it isn't already there. |
175 | /// Returns true if the element is inserted (it was not in the set before). |
176 | /// The first value of the returned pair is unused and provided for |
177 | /// partial compatibility with the standard library self-associative container |
178 | /// concept. |
179 | // FIXME: Add iterators that abstract over the small and large form, and then |
180 | // return those here. |
181 | std::pair<NoneType, bool> insert(const T &V) { |
182 | if (!isSmall()) |
183 | return std::make_pair(None, Set.insert(V).second); |
184 | |
185 | VIterator I = vfind(V); |
186 | if (I != Vector.end()) // Don't reinsert if it already exists. |
187 | return std::make_pair(None, false); |
188 | if (Vector.size() < N) { |
189 | Vector.push_back(V); |
190 | return std::make_pair(None, true); |
191 | } |
192 | |
193 | // Otherwise, grow from vector to set. |
194 | while (!Vector.empty()) { |
195 | Set.insert(Vector.back()); |
196 | Vector.pop_back(); |
197 | } |
198 | Set.insert(V); |
199 | return std::make_pair(None, true); |
200 | } |
201 | |
202 | template <typename IterT> |
203 | void insert(IterT I, IterT E) { |
204 | for (; I != E; ++I) |
205 | insert(*I); |
206 | } |
207 | |
208 | bool erase(const T &V) { |
209 | if (!isSmall()) |
210 | return Set.erase(V); |
211 | for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) |
212 | if (*I == V) { |
213 | Vector.erase(I); |
214 | return true; |
215 | } |
216 | return false; |
217 | } |
218 | |
219 | void clear() { |
220 | Vector.clear(); |
221 | Set.clear(); |
222 | } |
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 | |
236 | private: |
237 | bool isSmall() const { return Set.empty(); } |
238 | |
239 | VIterator vfind(const T &V) const { |
240 | for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) |
241 | if (*I == V) |
242 | return I; |
243 | return Vector.end(); |
244 | } |
245 | }; |
246 | |
247 | /// If this set is of pointer values, transparently switch over to using |
248 | /// SmallPtrSet for performance. |
249 | template <typename PointeeType, unsigned N> |
250 | class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; |
251 | |
252 | } // end namespace llvm |
253 | |
254 | #endif // LLVM_ADT_SMALLSET_H |
255 | |