Line data Source code
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 6 : SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
53 :
54 4 : 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 1 : }
64 :
65 36 : SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) {
66 36 : if (isSmall)
67 18 : 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 18 : new (&SetIter) SetIterTy(Other.SetIter);
72 : }
73 :
74 4 : SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) {
75 4 : if (isSmall)
76 2 : 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 2 : new (&SetIter) SetIterTy(std::move(Other.SetIter));
81 : }
82 :
83 0 : 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 1 : isSmall = Other.isSmall;
90 1 : if (isSmall)
91 0 : VecIter = Other.VecIter;
92 : else
93 1 : new (&SetIter) SetIterTy(Other.SetIter);
94 0 : 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 1 : isSmall = Other.isSmall;
104 1 : if (isSmall)
105 0 : VecIter = std::move(Other.VecIter);
106 : else
107 1 : new (&SetIter) SetIterTy(std::move(Other.SetIter));
108 : return *this;
109 : }
110 :
111 : bool operator==(const SmallSetIterator &RHS) const {
112 45810 : if (isSmall != RHS.isSmall)
113 : return false;
114 45810 : if (isSmall)
115 45797 : return VecIter == RHS.VecIter;
116 13 : return SetIter == RHS.SetIter;
117 : }
118 :
119 : SmallSetIterator &operator++() { // Preincrement
120 977 : if (isSmall)
121 967 : VecIter++;
122 : else
123 : SetIter++;
124 : return *this;
125 : }
126 :
127 979 : 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 10 : 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 5329027 : return Vector.empty() && Set.empty();
158 : }
159 :
160 : size_type size() const {
161 460892 : return isSmall() ? Vector.size() : Set.size();
162 : }
163 :
164 : /// count - Return 1 if the element is in the set, 0 otherwise.
165 23636737 : size_type count(const T &V) const {
166 23636737 : if (isSmall()) {
167 : // Since the collection is small, just do a linear search.
168 21360996 : return vfind(V) == Vector.end() ? 0 : 1;
169 : } else {
170 142100 : return Set.count(V);
171 : }
172 : }
173 10350277 :
174 10350277 : /// 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 8455809 : /// The first value of the returned pair is unused and provided for
177 : /// partial compatibility with the standard library self-associative container
178 0 : /// concept.
179 : // FIXME: Add iterators that abstract over the small and large form, and then
180 : // return those here.
181 11175974 : std::pair<NoneType, bool> insert(const T &V) {
182 11175974 : if (!isSmall())
183 : return std::make_pair(None, Set.insert(V).second);
184 2992281 :
185 264 : VIterator I = vfind(V);
186 6627513 : if (I != Vector.end()) // Don't reinsert if it already exists.
187 1547681 : return std::make_pair(None, false);
188 5079832 : if (Vector.size() < N) {
189 5866164 : Vector.push_back(V);
190 5866164 : return std::make_pair(None, true);
191 : }
192 773089 :
193 : // Otherwise, grow from vector to set.
194 701635 : while (!Vector.empty()) {
195 : Set.insert(Vector.back());
196 4 : Vector.pop_back();
197 2722495 : }
198 2722495 : Set.insert(V);
199 121116 : return std::make_pair(None, true);
200 : }
201 860211 :
202 1975599 : template <typename IterT>
203 216465 : void insert(IterT I, IterT E) {
204 942540 : for (; I != E; ++I)
205 24566244 : insert(*I);
206 25108832 : }
207 173702 :
208 500204 : bool erase(const T &V) {
209 496409 : if (!isSmall())
210 24717047 : return Set.erase(V);
211 7295331 : for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
212 16500051 : if (*I == V) {
213 16491924 : Vector.erase(I);
214 16558309 : return true;
215 150581 : }
216 4 : return false;
217 2460683 : }
218 2476479 :
219 3795 : void clear() {
220 : Vector.clear();
221 324723 : Set.clear();
222 1231450 : }
223 130369 :
224 778158 : const_iterator begin() const {
225 7377079 : if (isSmall())
226 7646985 : return {Vector.begin()};
227 23914 : return {Set.begin()};
228 290821 : }
229 290330 :
230 7401524 : const_iterator end() const {
231 48102 : if (isSmall())
232 6689829 : return {Vector.end()};
233 6689679 : return {Set.end()};
234 6693762 : }
235 139364 :
236 : private:
237 261812 : bool isSmall() const { return Set.empty(); }
238 262322 :
239 2216 : VIterator vfind(const T &V) const {
240 31181364 : for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
241 18332315 : if (*I == V)
242 211044 : return I;
243 88046 : return Vector.end();
244 120798 : }
245 17006326 : };
246 17007304 :
247 690 : /// If this set is of pointer values, transparently switch over to using
248 296 : /// SmallPtrSet for performance.
249 290 : template <typename PointeeType, unsigned N>
250 18774721 : class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
251 7270664 :
252 9615521 : } // end namespace llvm
253 9613930 :
254 9613984 : #endif // LLVM_ADT_SMALLSET_H
|
