Line data Source code
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 :
30 : namespace 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 : ///
50 : class SmallPtrSetImplBase : public DebugEpochBase {
51 : friend class SmallPtrSetIteratorImpl;
52 :
53 : protected:
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 1463535563 : : SmallArray(SmallStorage), CurArray(SmallStorage),
77 1420231773 : 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 480149118 : if (!isSmall())
84 2951501 : free(CurArray);
85 : }
86 :
87 : public:
88 : using size_type = unsigned;
89 :
90 : SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;
91 :
92 668896365 : LLVM_NODISCARD bool empty() const { return size() == 0; }
93 359718133 : size_type size() const { return NumNonEmpty - NumTombstones; }
94 :
95 536505359 : void clear() {
96 : incrementEpoch();
97 : // If the capacity of the array is huge, and the # elements used is small,
98 : // shrink the array.
99 536505359 : if (!isSmall()) {
100 26844965 : if (size() * 4 < CurArraySize && CurArraySize > 32)
101 358126 : return shrink_and_clear();
102 : // Fill the array with empty markers.
103 26486839 : memset(CurArray, -1, CurArraySize * sizeof(void *));
104 : }
105 :
106 536147233 : NumNonEmpty = 0;
107 536147233 : NumTombstones = 0;
108 : }
109 :
110 : protected:
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 5466903249 : 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 1815178553 : std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
127 1815178553 : if (isSmall()) {
128 : // Check to see if it is already in the set.
129 : const void **LastTombstone = nullptr;
130 4796261234 : for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
131 4796261234 : APtr != E; ++APtr) {
132 3459973733 : const void *Value = *APtr;
133 3459973733 : if (Value == Ptr)
134 163701883 : return std::make_pair(APtr, false);
135 3296271850 : if (Value == getTombstoneMarker())
136 : LastTombstone = APtr;
137 : }
138 :
139 : // Did we find any tombstone marker?
140 1336287501 : if (LastTombstone != nullptr) {
141 12092550 : *LastTombstone = Ptr;
142 12092550 : --NumTombstones;
143 : incrementEpoch();
144 12092550 : return std::make_pair(LastTombstone, true);
145 : }
146 :
147 : // Nope, there isn't. If we stay small, just 'pushback' now.
148 1324194951 : if (NumNonEmpty < CurArraySize) {
149 1319422779 : SmallArray[NumNonEmpty++] = Ptr;
150 : incrementEpoch();
151 1319422779 : return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
152 : }
153 : // Otherwise, hit the big set case, which will call grow.
154 : }
155 319961341 : 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 94542761 : bool erase_imp(const void * Ptr) {
163 94542761 : const void *const *P = find_imp(Ptr);
164 94542761 : if (P == EndPointer())
165 : return false;
166 :
167 : const void **Loc = const_cast<const void **>(P);
168 : assert(*Loc == Ptr && "broken find!");
169 26561728 : *Loc = getTombstoneMarker();
170 26561728 : NumTombstones++;
171 26561728 : 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 1280787029 : const void *const * find_imp(const void * Ptr) const {
178 1280787029 : if (isSmall()) {
179 : // Linear search for the item.
180 2205651782 : for (const void *const *APtr = SmallArray,
181 3104551830 : *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
182 2372295892 : if (*APtr == Ptr)
183 166644110 : return APtr;
184 732255938 : return EndPointer();
185 : }
186 :
187 : // Big set case.
188 381886981 : auto *Bucket = FindBucketFor(Ptr);
189 381886981 : if (*Bucket == Ptr)
190 : return Bucket;
191 : return EndPointer();
192 : }
193 :
194 : private:
195 0 : 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 :
205 : protected:
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 :
213 : private:
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.
222 : class SmallPtrSetIteratorImpl {
223 : protected:
224 : const void *const *Bucket;
225 : const void *const *End;
226 :
227 : public:
228 : explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
229 0 : : Bucket(BP), End(E) {
230 : if (shouldReverseIterate()) {
231 : RetreatIfNotValid();
232 : return;
233 : }
234 : AdvanceIfNotValid();
235 : }
236 :
237 0 : bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
238 180 : return Bucket == RHS.Bucket;
239 : }
240 0 : bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
241 68708 : return Bucket != RHS.Bucket;
242 : }
243 :
244 : protected:
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 0 : void AdvanceIfNotValid() {
249 : assert(Bucket <= End);
250 6012365508 : while (Bucket != End &&
251 3014600625 : (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
252 : *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
253 641909160 : ++Bucket;
254 0 : }
255 0 : void RetreatIfNotValid() {
256 : assert(Bucket >= End);
257 0 : while (Bucket != End &&
258 0 : (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
259 : Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
260 0 : --Bucket;
261 : }
262 0 : }
263 : };
264 :
265 : /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
266 : template <typename PtrTy>
267 : class SmallPtrSetIterator : public SmallPtrSetIteratorImpl,
268 : DebugEpochBase::HandleBase {
269 : using PtrTraits = PointerLikeTypeTraits<PtrTy>;
270 :
271 : public:
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 0 : explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,
279 : const DebugEpochBase &Epoch)
280 0 : : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {}
281 :
282 : // Most methods provided by baseclass.
283 :
284 0 : 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 206750025 : return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
292 : }
293 0 :
294 : inline SmallPtrSetIterator& operator++() { // Preincrement
295 : assert(isHandleInSync() && "invalid iterator access!");
296 : if (shouldReverseIterate()) {
297 : --Bucket;
298 : RetreatIfNotValid();
299 : return *this;
300 0 : }
301 194261999 : ++Bucket;
302 67389155 : AdvanceIfNotValid();
303 : return *this;
304 : }
305 :
306 : SmallPtrSetIterator operator++(int) { // Postincrement
307 : SmallPtrSetIterator tmp = *this;
308 : ++*this;
309 0 : return tmp;
310 : }
311 0 : };
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).
315 : template<unsigned N>
316 : struct RoundUpToPowerOfTwo;
317 :
318 0 : /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a
319 7366640 : /// helper template used to implement RoundUpToPowerOfTwo.
320 11022561 : template<unsigned N, bool isPowerTwo>
321 : struct RoundUpToPowerOfTwoH {
322 : enum { Val = N };
323 : };
324 : template<unsigned N>
325 : struct RoundUpToPowerOfTwoH<N, false> {
326 : enum {
327 0 : // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
328 210671 : // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
329 210923 : Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
330 : };
331 : };
332 :
333 : template<unsigned N>
334 : struct RoundUpToPowerOfTwo {
335 : enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
336 0 : };
337 21690 :
338 21690 : /// 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.
343 : template <typename PtrType>
344 : class SmallPtrSetImpl : public SmallPtrSetImplBase {
345 : using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
346 1010 : using PtrTraits = PointerLikeTypeTraits<PtrType>;
347 1202 : using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;
348 :
349 : protected:
350 : // Constructors that forward to the base.
351 15397831 : SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
352 27187373 : : SmallPtrSetImplBase(SmallStorage, that) {}
353 1967717 : SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
354 : SmallPtrSetImpl &&that)
355 1967717 : : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
356 : explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize)
357 : : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
358 :
359 : public:
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 221143 : /// insertion takes place, and the iterator component of the pair points to
370 265987 : /// the element equal to Ptr.
371 883203646 : std::pair<iterator, bool> insert(PtrType Ptr) {
372 888137082 : auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
373 883274605 : return std::make_pair(makeIterator(p.first), p.second);
374 : }
375 190256679 :
376 192212905 : /// erase - If the set contains the specified pointer, remove it and return
377 190256680 : /// true, otherwise return false.
378 15835 : bool erase(PtrType Ptr) {
379 146142663 : return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
380 141093187 : }
381 137896278 : /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
382 135637245 : size_type count(ConstPtrType Ptr) const { return find(Ptr) != end() ? 1 : 0; }
383 156377564 : iterator find(ConstPtrType Ptr) const {
384 156415292 : return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
385 21265448 : }
386 711467 :
387 125288731 : template <typename IterT>
388 123296637 : void insert(IterT I, IterT E) {
389 1050225227 : for (; I != E; ++I)
390 1079939723 : insert(*I);
391 1127463389 : }
392 156757835 :
393 766662216 : void insert(std::initializer_list<PtrType> IL) {
394 1043500019 : insert(IL.begin(), IL.end());
395 1077431411 : }
396 244907332 :
397 191801945 : iterator begin() const {
398 568428420 : if (shouldReverseIterate())
399 569581169 : return makeIterator(EndPointer() - 1);
400 563089360 : return makeIterator(CurArray);
401 330837817 : }
402 463265931 : iterator end() const { return makeIterator(EndPointer()); }
403 65828905 :
404 35157358 : private:
405 12512442 : /// Create an iterator that dereferences to same place as the given pointer.
406 4190138 : iterator makeIterator(const void *const *P) const {
407 8870894 : if (shouldReverseIterate())
408 18189847 : return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);
409 43081478 : return iterator(P, EndPointer(), *this);
410 65360227 : }
411 427225102 : };
412 604706927 :
413 180724222 : /// SmallPtrSet - This class implements a set which is optimized for holding
414 192209507 : /// SmallSize or less elements. This internally rounds up SmallSize to the next
415 376937559 : /// power of two if it is not already a power of two. See the comments above
416 231487302 : /// SmallPtrSetImplBase for details of the algorithm.
417 188811041 : template<class PtrType, unsigned SmallSize>
418 450939193 : class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
419 89391681 : // In small mode SmallPtrSet uses linear search for the elements, so it is
420 590480536 : // not a good idea to choose this value too high. You may consider using a
421 4504111 : // DenseSet<> instead if you expect many elements in the set.
422 672656 : static_assert(SmallSize <= 32, "SmallSize should be small");
423 14441876 :
424 3951639 : using BaseT = SmallPtrSetImpl<PtrType>;
425 54983827 :
426 13586057 : // Make sure that SmallSize is a power of two, round up if not.
427 17121917 : enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
428 70161305 : /// SmallStorage - Fixed size storage used in 'small mode'.
429 130885 : const void *SmallStorage[SmallSizePowTwo];
430 482062882 :
431 30401920 : public:
432 381079131 : SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
433 15198521 : SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
434 6796055 : SmallPtrSet(SmallPtrSet &&that)
435 6595092 : : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
436 3068231 :
437 7659807 : template<typename It>
438 3765299 : SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
439 691975 : this->insert(I, E);
440 145462919 : }
441 430675 :
442 6725959 : SmallPtrSet(std::initializer_list<PtrType> IL)
443 176707 : : BaseT(SmallStorage, SmallSizePowTwo) {
444 14659422 : this->insert(IL.begin(), IL.end());
445 1308616 : }
446 57244438 :
447 11697278 : SmallPtrSet<PtrType, SmallSize> &
448 193171666 : operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
449 339524935 : if (&RHS != this)
450 7091107 : this->CopyFrom(RHS);
451 2284520 : return *this;
452 11920721 : }
453 15913772 :
454 7708660 : SmallPtrSet<PtrType, SmallSize> &
455 4728086 : operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
456 206456 : if (&RHS != this)
457 4105581 : this->MoveFrom(SmallSizePowTwo, std::move(RHS));
458 3293734 : return *this;
459 2378037 : }
460 6162925 :
461 10764474 : SmallPtrSet<PtrType, SmallSize> &
462 2851579 : operator=(std::initializer_list<PtrType> IL) {
463 2575241 : this->clear();
464 11087504 : this->insert(IL.begin(), IL.end());
465 769340 : return *this;
466 867898 : }
467 197942 :
468 15818594 : /// swap - Swaps the elements of two sets.
469 275853 : void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
470 5323360 : SmallPtrSetImplBase::swap(RHS);
471 421798 : }
472 5709133 : };
473 514626 :
474 1845480 : } // end namespace llvm
475 1585657 :
476 607168 : namespace std {
477 3107 :
478 15076489 : /// Implement std::swap in terms of SmallPtrSet swap.
479 29 : template<class T, unsigned N>
480 2072385 : inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
481 97897 : LHS.swap(RHS);
482 4125257 : }
483 288464 :
484 177259 : } // end namespace std
485 653878 :
486 8165376 : #endif // LLVM_ADT_SMALLPTRSET_H
|
