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
11// SmallPtrSetImplBase for more details on the algorithm used.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_SMALLPTRSET_H
16#define LLVM_ADT_SMALLPTRSET_H
17
18#include "llvm/ADT/EpochTracker.h"
19#include "llvm/Support/Compiler.h"
20#include "llvm/Support/ReverseIteration.h"
21#include "llvm/Support/type_traits.h"
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25#include <cstring>
26#include <initializer_list>
27#include <iterator>
28#include <utility>
29
30namespace llvm {
31
32/// SmallPtrSetImplBase - This is the common code shared among all the
33/// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one
34/// for small and one for large sets.
35///
36/// Small sets use an array of pointers allocated in the SmallPtrSet object,
37/// which is treated as a simple array of pointers. When a pointer is added to
38/// the set, the array is scanned to see if the element already exists, if not
39/// the element is 'pushed back' onto the array. If we run out of space in the
40/// array, we grow into the 'large set' case. SmallSet should be used when the
41/// sets are often small. In this case, no memory allocation is used, and only
42/// light-weight and cache-efficient scanning is used.
43///
44/// Large sets use a classic exponentially-probed hash table. Empty buckets are
45/// represented with an illegal pointer value (-1) to allow null pointers to be
46/// inserted. Tombstones are represented with another illegal pointer value
47/// (-2), to allow deletion. The hash table is resized when the table is 3/4 or
48/// more. When this happens, the table is doubled in size.
49///
50class SmallPtrSetImplBase : public DebugEpochBase {
51 friend class SmallPtrSetIteratorImpl;
52
53protected:
54 /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
55 const void **SmallArray;
56 /// CurArray - This is the current set of buckets. If equal to SmallArray,
57 /// then the set is in 'small mode'.
58 const void **CurArray;
59 /// CurArraySize - The allocated size of CurArray, always a power of two.
60 unsigned CurArraySize;
61
62 /// Number of elements in CurArray that contain a value or are a tombstone.
63 /// If small, all these elements are at the beginning of CurArray and the rest
64 /// is uninitialized.
65 unsigned NumNonEmpty;
66 /// Number of tombstones in CurArray.
67 unsigned NumTombstones;
68
69 // Helpers to copy and move construct a SmallPtrSet.
70 SmallPtrSetImplBase(const void **SmallStorage,
71 const SmallPtrSetImplBase &that);
72 SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
73 SmallPtrSetImplBase &&that);
74
75 explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
76 : SmallArray(SmallStorage), CurArray(SmallStorage),
77 CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
78 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
79 "Initial size must be a power of two!");
80 }
81
82 ~SmallPtrSetImplBase() {
83 if (!isSmall())
84 free(CurArray);
85 }
86
87public:
88 using size_type = unsigned;
89
90 SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;
91
92 LLVM_NODISCARD bool empty() const { return size() == 0; }
93 size_type size() const { return NumNonEmpty - NumTombstones; }
94
95 void clear() {
96 incrementEpoch();
97 // If the capacity of the array is huge, and the # elements used is small,
98 // shrink the array.
99 if (!isSmall()) {
100 if (size() * 4 < CurArraySize && CurArraySize > 32)
101 return shrink_and_clear();
102 // Fill the array with empty markers.
103 memset(CurArray, -1, CurArraySize * sizeof(void *));
104 }
105
106 NumNonEmpty = 0;
107 NumTombstones = 0;
108 }
109
110protected:
111 static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
112
113 static void *getEmptyMarker() {
114 // Note that -1 is chosen to make clear() efficiently implementable with
115 // memset and because it's not a valid pointer value.
116 return reinterpret_cast<void*>(-1);
117 }
118
119 const void **EndPointer() const {
120 return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
121 }
122
123 /// insert_imp - This returns true if the pointer was new to the set, false if
124 /// it was already in the set. This is hidden from the client so that the
125 /// derived class can check that the right type of pointer is passed in.
126 std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
127 if (isSmall()) {
128 // Check to see if it is already in the set.
129 const void **LastTombstone = nullptr;
130 for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
131 APtr != E; ++APtr) {
132 const void *Value = *APtr;
133 if (Value == Ptr)
134 return std::make_pair(APtr, false);
135 if (Value == getTombstoneMarker())
136 LastTombstone = APtr;
137 }
138
139 // Did we find any tombstone marker?
140 if (LastTombstone != nullptr) {
141 *LastTombstone = Ptr;
142 --NumTombstones;
143 incrementEpoch();
144 return std::make_pair(LastTombstone, true);
145 }
146
147 // Nope, there isn't. If we stay small, just 'pushback' now.
148 if (NumNonEmpty < CurArraySize) {
149 SmallArray[NumNonEmpty++] = Ptr;
150 incrementEpoch();
151 return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
152 }
153 // Otherwise, hit the big set case, which will call grow.
154 }
155 return insert_imp_big(Ptr);
156 }
157
158 /// erase_imp - If the set contains the specified pointer, remove it and
159 /// return true, otherwise return false. This is hidden from the client so
160 /// that the derived class can check that the right type of pointer is passed
161 /// in.
162 bool erase_imp(const void * Ptr) {
163 const void *const *P = find_imp(Ptr);
164 if (P == EndPointer())
165 return false;
166
167 const void **Loc = const_cast<const void **>(P);
168 assert(*Loc == Ptr && "broken find!");
169 *Loc = getTombstoneMarker();
170 NumTombstones++;
171 return true;
172 }
173
174 /// Returns the raw pointer needed to construct an iterator. If element not
175 /// found, this will be EndPointer. Otherwise, it will be a pointer to the
176 /// slot which stores Ptr;
177 const void *const * find_imp(const void * Ptr) const {
178 if (isSmall()) {
179 // Linear search for the item.
180 for (const void *const *APtr = SmallArray,
181 *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
182 if (*APtr == Ptr)
183 return APtr;
184 return EndPointer();
185 }
186
187 // Big set case.
188 auto *Bucket = FindBucketFor(Ptr);
189 if (*Bucket == Ptr)
190 return Bucket;
191 return EndPointer();
192 }
193
194private:
195 bool isSmall() const { return CurArray == SmallArray; }
196
197 std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
198
199 const void * const *FindBucketFor(const void *Ptr) const;
200 void shrink_and_clear();
201
202 /// Grow - Allocate a larger backing store for the buckets and move it over.
203 void Grow(unsigned NewSize);
204
205protected:
206 /// swap - Swaps the elements of two sets.
207 /// Note: This method assumes that both sets have the same small size.
208 void swap(SmallPtrSetImplBase &RHS);
209
210 void CopyFrom(const SmallPtrSetImplBase &RHS);
211 void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
212
213private:
214 /// Code shared by MoveFrom() and move constructor.
215 void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
216 /// Code shared by CopyFrom() and copy constructor.
217 void CopyHelper(const SmallPtrSetImplBase &RHS);
218};
219
220/// SmallPtrSetIteratorImpl - This is the common base class shared between all
221/// instances of SmallPtrSetIterator.
222class SmallPtrSetIteratorImpl {
223protected:
224 const void *const *Bucket;
225 const void *const *End;
226
227public:
228 explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
229 : Bucket(BP), End(E) {
230 if (shouldReverseIterate()) {
231 RetreatIfNotValid();
232 return;
233 }
234 AdvanceIfNotValid();
235 }
236
237 bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
238 return Bucket == RHS.Bucket;
239 }
240 bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
241 return Bucket != RHS.Bucket;
242 }
243
244protected:
245 /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
246 /// that is. This is guaranteed to stop because the end() bucket is marked
247 /// valid.
248 void AdvanceIfNotValid() {
249 assert(Bucket <= End);
250 while (Bucket != End &&
251 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
252 *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
253 ++Bucket;
254 }
255 void RetreatIfNotValid() {
256 assert(Bucket >= End);
257 while (Bucket != End &&
258 (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
259 Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
260 --Bucket;
261 }
262 }
263};
264
265/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
266template <typename PtrTy>
267class SmallPtrSetIterator : public SmallPtrSetIteratorImpl,
268 DebugEpochBase::HandleBase {
269 using PtrTraits = PointerLikeTypeTraits<PtrTy>;
270
271public:
272 using value_type = PtrTy;
273 using reference = PtrTy;
274 using pointer = PtrTy;
275 using difference_type = std::ptrdiff_t;
276 using iterator_category = std::forward_iterator_tag;
277
278 explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,
279 const DebugEpochBase &Epoch)
280 : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {}
281
282 // Most methods provided by baseclass.
283
284 const PtrTy operator*() const {
285 assert(isHandleInSync() && "invalid iterator access!");
286 if (shouldReverseIterate()) {
287 assert(Bucket > End);
288 return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
289 }
290 assert(Bucket < End);
291 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
292 }
293
294 inline SmallPtrSetIterator& operator++() { // Preincrement
295 assert(isHandleInSync() && "invalid iterator access!");
296 if (shouldReverseIterate()) {
297 --Bucket;
298 RetreatIfNotValid();
299 return *this;
300 }
301 ++Bucket;
302 AdvanceIfNotValid();
303 return *this;
304 }
305
306 SmallPtrSetIterator operator++(int) { // Postincrement
307 SmallPtrSetIterator tmp = *this;
308 ++*this;
309 return tmp;
310 }
311};
312
313/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
314/// power of two (which means N itself if N is already a power of two).
315template<unsigned N>
316struct RoundUpToPowerOfTwo;
317
318/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a
319/// helper template used to implement RoundUpToPowerOfTwo.
320template<unsigned N, bool isPowerTwo>
321struct RoundUpToPowerOfTwoH {
322 enum { Val = N };
323};
324template<unsigned N>
325struct RoundUpToPowerOfTwoH<N, false> {
326 enum {
327 // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
328 // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
329 Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
330 };
331};
332
333template<unsigned N>
334struct RoundUpToPowerOfTwo {
335 enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
336};
337
338/// A templated base class for \c SmallPtrSet which provides the
339/// typesafe interface that is common across all small sizes.
340///
341/// This is particularly useful for passing around between interface boundaries
342/// to avoid encoding a particular small size in the interface boundary.
343template <typename PtrType>
344class SmallPtrSetImpl : public SmallPtrSetImplBase {
345 using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
346 using PtrTraits = PointerLikeTypeTraits<PtrType>;
347 using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;
348
349protected:
350 // Constructors that forward to the base.
351 SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
352 : SmallPtrSetImplBase(SmallStorage, that) {}
353 SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
354 SmallPtrSetImpl &&that)
355 : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
356 explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize)
357 : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
358
359public:
360 using iterator = SmallPtrSetIterator<PtrType>;
361 using const_iterator = SmallPtrSetIterator<PtrType>;
362 using key_type = ConstPtrType;
363 using value_type = PtrType;
364
365 SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
366
367 /// Inserts Ptr if and only if there is no element in the container equal to
368 /// Ptr. The bool component of the returned pair is true if and only if the
369 /// insertion takes place, and the iterator component of the pair points to
370 /// the element equal to Ptr.
371 std::pair<iterator, bool> insert(PtrType Ptr) {
372 auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
373 return std::make_pair(makeIterator(p.first), p.second);
374 }
375
376 /// erase - If the set contains the specified pointer, remove it and return
377 /// true, otherwise return false.
378 bool erase(PtrType Ptr) {
379 return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
380 }
381 /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
382 size_type count(ConstPtrType Ptr) const { return find(Ptr) != end() ? 1 : 0; }
383 iterator find(ConstPtrType Ptr) const {
384 return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
385 }
386
387 template <typename IterT>
388 void insert(IterT I, IterT E) {
389 for (; I != E; ++I)
390 insert(*I);
391 }
392
393 void insert(std::initializer_list<PtrType> IL) {
394 insert(IL.begin(), IL.end());
395 }
396
397 iterator begin() const {
398 if (shouldReverseIterate())
399 return makeIterator(EndPointer() - 1);
400 return makeIterator(CurArray);
401 }
402 iterator end() const { return makeIterator(EndPointer()); }
403
404private:
405 /// Create an iterator that dereferences to same place as the given pointer.
406 iterator makeIterator(const void *const *P) const {
407 if (shouldReverseIterate())
408 return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);
409 return iterator(P, EndPointer(), *this);
410 }
411};
412
413/// SmallPtrSet - This class implements a set which is optimized for holding
414/// SmallSize or less elements. This internally rounds up SmallSize to the next
415/// power of two if it is not already a power of two. See the comments above
416/// SmallPtrSetImplBase for details of the algorithm.
417template<class PtrType, unsigned SmallSize>
418class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
419 // In small mode SmallPtrSet uses linear search for the elements, so it is
420 // not a good idea to choose this value too high. You may consider using a
421 // DenseSet<> instead if you expect many elements in the set.
422 static_assert(SmallSize <= 32, "SmallSize should be small");
423
424 using BaseT = SmallPtrSetImpl<PtrType>;
425
426 // Make sure that SmallSize is a power of two, round up if not.
427 enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
428 /// SmallStorage - Fixed size storage used in 'small mode'.
429 const void *SmallStorage[SmallSizePowTwo];
430
431public:
432 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
433 SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
434 SmallPtrSet(SmallPtrSet &&that)
435 : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
436
437 template<typename It>
438 SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
439 this->insert(I, E);
440 }
441
442 SmallPtrSet(std::initializer_list<PtrType> IL)
443 : BaseT(SmallStorage, SmallSizePowTwo) {
444 this->insert(IL.begin(), IL.end());
445 }
446
447 SmallPtrSet<PtrType, SmallSize> &
448 operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
449 if (&RHS != this)
450 this->CopyFrom(RHS);
451 return *this;
452 }
453
454 SmallPtrSet<PtrType, SmallSize> &
455 operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
456 if (&RHS != this)
457 this->MoveFrom(SmallSizePowTwo, std::move(RHS));
458 return *this;
459 }
460
461 SmallPtrSet<PtrType, SmallSize> &
462 operator=(std::initializer_list<PtrType> IL) {
463 this->clear();
464 this->insert(IL.begin(), IL.end());
465 return *this;
466 }
467
468 /// swap - Swaps the elements of two sets.
469 void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
470 SmallPtrSetImplBase::swap(RHS);
471 }
472};
473
474} // end namespace llvm
475
476namespace std {
477
478 /// Implement std::swap in terms of SmallPtrSet swap.
479 template<class T, unsigned N>
480 inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
481 LHS.swap(RHS);
482 }
483
484} // end namespace std
485
486#endif // LLVM_ADT_SMALLPTRSET_H
487