]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- 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 SmallPtrSet class. See the doxygen comment for | |
1a4d82fc | 11 | // SmallPtrSetImplBase for more details on the algorithm used. |
223e47cc LB |
12 | // |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #ifndef LLVM_ADT_SMALLPTRSET_H | |
16 | #define LLVM_ADT_SMALLPTRSET_H | |
17 | ||
18 | #include "llvm/Support/Compiler.h" | |
19 | #include "llvm/Support/DataTypes.h" | |
20 | #include "llvm/Support/PointerLikeTypeTraits.h" | |
21 | #include <cassert> | |
22 | #include <cstddef> | |
23 | #include <cstring> | |
24 | #include <iterator> | |
85aaf69f | 25 | #include <utility> |
223e47cc LB |
26 | |
27 | namespace llvm { | |
28 | ||
29 | class SmallPtrSetIteratorImpl; | |
30 | ||
1a4d82fc | 31 | /// SmallPtrSetImplBase - This is the common code shared among all the |
223e47cc LB |
32 | /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one |
33 | /// for small and one for large sets. | |
34 | /// | |
35 | /// Small sets use an array of pointers allocated in the SmallPtrSet object, | |
36 | /// which is treated as a simple array of pointers. When a pointer is added to | |
37 | /// the set, the array is scanned to see if the element already exists, if not | |
38 | /// the element is 'pushed back' onto the array. If we run out of space in the | |
39 | /// array, we grow into the 'large set' case. SmallSet should be used when the | |
40 | /// sets are often small. In this case, no memory allocation is used, and only | |
41 | /// light-weight and cache-efficient scanning is used. | |
42 | /// | |
43 | /// Large sets use a classic exponentially-probed hash table. Empty buckets are | |
44 | /// represented with an illegal pointer value (-1) to allow null pointers to be | |
45 | /// inserted. Tombstones are represented with another illegal pointer value | |
46 | /// (-2), to allow deletion. The hash table is resized when the table is 3/4 or | |
47 | /// more. When this happens, the table is doubled in size. | |
48 | /// | |
1a4d82fc | 49 | class SmallPtrSetImplBase { |
223e47cc LB |
50 | friend class SmallPtrSetIteratorImpl; |
51 | protected: | |
52 | /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. | |
53 | const void **SmallArray; | |
54 | /// CurArray - This is the current set of buckets. If equal to SmallArray, | |
55 | /// then the set is in 'small mode'. | |
56 | const void **CurArray; | |
57 | /// CurArraySize - The allocated size of CurArray, always a power of two. | |
223e47cc LB |
58 | unsigned CurArraySize; |
59 | ||
60 | // If small, this is # elts allocated consecutively | |
61 | unsigned NumElements; | |
62 | unsigned NumTombstones; | |
63 | ||
1a4d82fc JJ |
64 | // Helpers to copy and move construct a SmallPtrSet. |
65 | SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that); | |
66 | SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, | |
67 | SmallPtrSetImplBase &&that); | |
68 | explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) : | |
223e47cc LB |
69 | SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { |
70 | assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && | |
71 | "Initial size must be a power of two!"); | |
223e47cc LB |
72 | clear(); |
73 | } | |
1a4d82fc | 74 | ~SmallPtrSetImplBase(); |
223e47cc LB |
75 | |
76 | public: | |
1a4d82fc JJ |
77 | typedef unsigned size_type; |
78 | bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; } | |
79 | size_type size() const { return NumElements; } | |
223e47cc LB |
80 | |
81 | void clear() { | |
82 | // If the capacity of the array is huge, and the # elements used is small, | |
83 | // shrink the array. | |
84 | if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32) | |
85 | return shrink_and_clear(); | |
86 | ||
87 | // Fill the array with empty markers. | |
88 | memset(CurArray, -1, CurArraySize*sizeof(void*)); | |
89 | NumElements = 0; | |
90 | NumTombstones = 0; | |
91 | } | |
92 | ||
93 | protected: | |
94 | static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); } | |
95 | static void *getEmptyMarker() { | |
96 | // Note that -1 is chosen to make clear() efficiently implementable with | |
97 | // memset and because it's not a valid pointer value. | |
98 | return reinterpret_cast<void*>(-1); | |
99 | } | |
100 | ||
101 | /// insert_imp - This returns true if the pointer was new to the set, false if | |
102 | /// it was already in the set. This is hidden from the client so that the | |
103 | /// derived class can check that the right type of pointer is passed in. | |
85aaf69f | 104 | std::pair<const void *const *, bool> insert_imp(const void *Ptr); |
223e47cc LB |
105 | |
106 | /// erase_imp - If the set contains the specified pointer, remove it and | |
107 | /// return true, otherwise return false. This is hidden from the client so | |
108 | /// that the derived class can check that the right type of pointer is passed | |
109 | /// in. | |
110 | bool erase_imp(const void * Ptr); | |
111 | ||
112 | bool count_imp(const void * Ptr) const { | |
113 | if (isSmall()) { | |
114 | // Linear search for the item. | |
115 | for (const void *const *APtr = SmallArray, | |
116 | *const *E = SmallArray+NumElements; APtr != E; ++APtr) | |
117 | if (*APtr == Ptr) | |
118 | return true; | |
119 | return false; | |
120 | } | |
121 | ||
122 | // Big set case. | |
123 | return *FindBucketFor(Ptr) == Ptr; | |
124 | } | |
125 | ||
126 | private: | |
127 | bool isSmall() const { return CurArray == SmallArray; } | |
128 | ||
129 | const void * const *FindBucketFor(const void *Ptr) const; | |
130 | void shrink_and_clear(); | |
131 | ||
132 | /// Grow - Allocate a larger backing store for the buckets and move it over. | |
133 | void Grow(unsigned NewSize); | |
134 | ||
1a4d82fc | 135 | void operator=(const SmallPtrSetImplBase &RHS) LLVM_DELETED_FUNCTION; |
223e47cc LB |
136 | protected: |
137 | /// swap - Swaps the elements of two sets. | |
138 | /// Note: This method assumes that both sets have the same small size. | |
1a4d82fc | 139 | void swap(SmallPtrSetImplBase &RHS); |
223e47cc | 140 | |
1a4d82fc JJ |
141 | void CopyFrom(const SmallPtrSetImplBase &RHS); |
142 | void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); | |
223e47cc LB |
143 | }; |
144 | ||
145 | /// SmallPtrSetIteratorImpl - This is the common base class shared between all | |
146 | /// instances of SmallPtrSetIterator. | |
147 | class SmallPtrSetIteratorImpl { | |
148 | protected: | |
149 | const void *const *Bucket; | |
1a4d82fc | 150 | const void *const *End; |
223e47cc | 151 | public: |
1a4d82fc JJ |
152 | explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) |
153 | : Bucket(BP), End(E) { | |
154 | AdvanceIfNotValid(); | |
223e47cc LB |
155 | } |
156 | ||
157 | bool operator==(const SmallPtrSetIteratorImpl &RHS) const { | |
158 | return Bucket == RHS.Bucket; | |
159 | } | |
160 | bool operator!=(const SmallPtrSetIteratorImpl &RHS) const { | |
161 | return Bucket != RHS.Bucket; | |
162 | } | |
163 | ||
164 | protected: | |
165 | /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket | |
166 | /// that is. This is guaranteed to stop because the end() bucket is marked | |
167 | /// valid. | |
168 | void AdvanceIfNotValid() { | |
1a4d82fc JJ |
169 | assert(Bucket <= End); |
170 | while (Bucket != End && | |
171 | (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || | |
172 | *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) | |
223e47cc LB |
173 | ++Bucket; |
174 | } | |
175 | }; | |
176 | ||
177 | /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. | |
178 | template<typename PtrTy> | |
179 | class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { | |
180 | typedef PointerLikeTypeTraits<PtrTy> PtrTraits; | |
181 | ||
182 | public: | |
183 | typedef PtrTy value_type; | |
184 | typedef PtrTy reference; | |
185 | typedef PtrTy pointer; | |
186 | typedef std::ptrdiff_t difference_type; | |
187 | typedef std::forward_iterator_tag iterator_category; | |
188 | ||
1a4d82fc JJ |
189 | explicit SmallPtrSetIterator(const void *const *BP, const void *const *E) |
190 | : SmallPtrSetIteratorImpl(BP, E) {} | |
223e47cc LB |
191 | |
192 | // Most methods provided by baseclass. | |
193 | ||
194 | const PtrTy operator*() const { | |
1a4d82fc | 195 | assert(Bucket < End); |
223e47cc LB |
196 | return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); |
197 | } | |
198 | ||
199 | inline SmallPtrSetIterator& operator++() { // Preincrement | |
200 | ++Bucket; | |
201 | AdvanceIfNotValid(); | |
202 | return *this; | |
203 | } | |
204 | ||
205 | SmallPtrSetIterator operator++(int) { // Postincrement | |
206 | SmallPtrSetIterator tmp = *this; ++*this; return tmp; | |
207 | } | |
208 | }; | |
209 | ||
210 | /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next | |
211 | /// power of two (which means N itself if N is already a power of two). | |
212 | template<unsigned N> | |
213 | struct RoundUpToPowerOfTwo; | |
214 | ||
215 | /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a | |
216 | /// helper template used to implement RoundUpToPowerOfTwo. | |
217 | template<unsigned N, bool isPowerTwo> | |
218 | struct RoundUpToPowerOfTwoH { | |
219 | enum { Val = N }; | |
220 | }; | |
221 | template<unsigned N> | |
222 | struct RoundUpToPowerOfTwoH<N, false> { | |
223 | enum { | |
224 | // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets | |
225 | // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111. | |
226 | Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val | |
227 | }; | |
228 | }; | |
229 | ||
230 | template<unsigned N> | |
231 | struct RoundUpToPowerOfTwo { | |
232 | enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val }; | |
233 | }; | |
234 | ||
235 | ||
1a4d82fc JJ |
236 | /// \brief A templated base class for \c SmallPtrSet which provides the |
237 | /// typesafe interface that is common across all small sizes. | |
238 | /// | |
239 | /// This is particularly useful for passing around between interface boundaries | |
240 | /// to avoid encoding a particular small size in the interface boundary. | |
241 | template <typename PtrType> | |
242 | class SmallPtrSetImpl : public SmallPtrSetImplBase { | |
223e47cc | 243 | typedef PointerLikeTypeTraits<PtrType> PtrTraits; |
223e47cc | 244 | |
1a4d82fc JJ |
245 | SmallPtrSetImpl(const SmallPtrSetImpl&) LLVM_DELETED_FUNCTION; |
246 | protected: | |
247 | // Constructors that forward to the base. | |
248 | SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that) | |
249 | : SmallPtrSetImplBase(SmallStorage, that) {} | |
250 | SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize, | |
251 | SmallPtrSetImpl &&that) | |
252 | : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {} | |
253 | explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize) | |
254 | : SmallPtrSetImplBase(SmallStorage, SmallSize) {} | |
223e47cc | 255 | |
1a4d82fc | 256 | public: |
85aaf69f SL |
257 | typedef SmallPtrSetIterator<PtrType> iterator; |
258 | typedef SmallPtrSetIterator<PtrType> const_iterator; | |
259 | ||
260 | /// Inserts Ptr if and only if there is no element in the container equal to | |
261 | /// Ptr. The bool component of the returned pair is true if and only if the | |
262 | /// insertion takes place, and the iterator component of the pair points to | |
263 | /// the element equal to Ptr. | |
264 | std::pair<iterator, bool> insert(PtrType Ptr) { | |
265 | auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); | |
266 | return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second); | |
223e47cc LB |
267 | } |
268 | ||
269 | /// erase - If the set contains the specified pointer, remove it and return | |
270 | /// true, otherwise return false. | |
271 | bool erase(PtrType Ptr) { | |
272 | return erase_imp(PtrTraits::getAsVoidPointer(Ptr)); | |
273 | } | |
274 | ||
1a4d82fc JJ |
275 | /// count - Return 1 if the specified pointer is in the set, 0 otherwise. |
276 | size_type count(PtrType Ptr) const { | |
277 | return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0; | |
223e47cc LB |
278 | } |
279 | ||
280 | template <typename IterT> | |
281 | void insert(IterT I, IterT E) { | |
282 | for (; I != E; ++I) | |
283 | insert(*I); | |
284 | } | |
285 | ||
223e47cc | 286 | inline iterator begin() const { |
1a4d82fc | 287 | return iterator(CurArray, CurArray+CurArraySize); |
223e47cc LB |
288 | } |
289 | inline iterator end() const { | |
1a4d82fc | 290 | return iterator(CurArray+CurArraySize, CurArray+CurArraySize); |
223e47cc | 291 | } |
1a4d82fc | 292 | }; |
223e47cc | 293 | |
1a4d82fc JJ |
294 | /// SmallPtrSet - This class implements a set which is optimized for holding |
295 | /// SmallSize or less elements. This internally rounds up SmallSize to the next | |
296 | /// power of two if it is not already a power of two. See the comments above | |
297 | /// SmallPtrSetImplBase for details of the algorithm. | |
298 | template<class PtrType, unsigned SmallSize> | |
299 | class SmallPtrSet : public SmallPtrSetImpl<PtrType> { | |
300 | typedef SmallPtrSetImpl<PtrType> BaseT; | |
301 | ||
302 | // Make sure that SmallSize is a power of two, round up if not. | |
303 | enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val }; | |
304 | /// SmallStorage - Fixed size storage used in 'small mode'. | |
305 | const void *SmallStorage[SmallSizePowTwo]; | |
306 | public: | |
307 | SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {} | |
308 | SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {} | |
309 | SmallPtrSet(SmallPtrSet &&that) | |
310 | : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {} | |
311 | ||
312 | template<typename It> | |
313 | SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) { | |
314 | this->insert(I, E); | |
315 | } | |
316 | ||
317 | SmallPtrSet<PtrType, SmallSize> & | |
223e47cc | 318 | operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) { |
1a4d82fc JJ |
319 | if (&RHS != this) |
320 | this->CopyFrom(RHS); | |
321 | return *this; | |
322 | } | |
323 | ||
324 | SmallPtrSet<PtrType, SmallSize>& | |
325 | operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) { | |
326 | if (&RHS != this) | |
327 | this->MoveFrom(SmallSizePowTwo, std::move(RHS)); | |
223e47cc LB |
328 | return *this; |
329 | } | |
330 | ||
331 | /// swap - Swaps the elements of two sets. | |
332 | void swap(SmallPtrSet<PtrType, SmallSize> &RHS) { | |
1a4d82fc | 333 | SmallPtrSetImplBase::swap(RHS); |
223e47cc LB |
334 | } |
335 | }; | |
336 | ||
337 | } | |
338 | ||
339 | namespace std { | |
340 | /// Implement std::swap in terms of SmallPtrSet swap. | |
341 | template<class T, unsigned N> | |
342 | inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { | |
343 | LHS.swap(RHS); | |
344 | } | |
345 | } | |
346 | ||
347 | #endif |