1//===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
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/ADL.h"
19#include "llvm/ADT/EpochTracker.h"
20#include "llvm/ADT/STLForwardCompat.h"
21#include "llvm/Support/Compiler.h"
22#include "llvm/Support/MathExtras.h"
23#include "llvm/Support/ReverseIteration.h"
24#include "llvm/Support/type_traits.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdlib>
29#include <cstring>
30#include <initializer_list>
31#include <iterator>
32#include <limits>
33#include <utility>
34
35namespace llvm {
36
37/// SmallPtrSetImplBase - This is the common code shared among all the
38/// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one
39/// for small and one for large sets.
40///
41/// Small sets use an array of pointers allocated in the SmallPtrSet object,
42/// which is treated as a simple array of pointers. When a pointer is added to
43/// the set, the array is scanned to see if the element already exists, if not
44/// the element is 'pushed back' onto the array. If we run out of space in the
45/// array, we grow into the 'large set' case. SmallSet should be used when the
46/// sets are often small. In this case, no memory allocation is used, and only
47/// light-weight and cache-efficient scanning is used.
48///
49/// Large sets use a classic exponentially-probed hash table. Empty buckets are
50/// represented with an illegal pointer value (-1) to allow null pointers to be
51/// inserted. Tombstones are represented with another illegal pointer value
52/// (-2), to allow deletion. The hash table is resized when the table is 3/4 or
53/// more. When this happens, the table is doubled in size.
54///
55class SmallPtrSetImplBase : public DebugEpochBase {
56 friend class SmallPtrSetIteratorImpl;
57
58protected:
59 /// The current set of buckets, in either small or big representation.
60 const void **CurArray;
61 /// CurArraySize - The allocated size of CurArray, always a power of two.
62 unsigned CurArraySize;
63
64 /// Number of elements in CurArray that contain a value or are a tombstone.
65 /// If small, all these elements are at the beginning of CurArray and the rest
66 /// is uninitialized.
67 unsigned NumNonEmpty;
68 /// Number of tombstones in CurArray.
69 unsigned NumTombstones;
70 /// Whether the set is in small representation.
71 bool IsSmall;
72
73 // Helpers to copy and move construct a SmallPtrSet.
74 LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage,
75 const SmallPtrSetImplBase &that);
76 LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
77 const void **RHSSmallStorage,
78 SmallPtrSetImplBase &&that);
79
80 explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
81 : CurArray(SmallStorage), CurArraySize(SmallSize), NumNonEmpty(0),
82 NumTombstones(0), IsSmall(true) {
83 assert(llvm::has_single_bit(SmallSize) &&
84 "Initial size must be a power of two!");
85 }
86
87 ~SmallPtrSetImplBase() {
88 if (!isSmall())
89 free(ptr: CurArray);
90 }
91
92public:
93 using size_type = unsigned;
94
95 SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;
96
97 [[nodiscard]] bool empty() const { return size() == 0; }
98 size_type size() const { return NumNonEmpty - NumTombstones; }
99 size_type capacity() const { return CurArraySize; }
100
101 void clear() {
102 incrementEpoch();
103 // If the capacity of the array is huge, and the # elements used is small,
104 // shrink the array.
105 if (!isSmall()) {
106 if (size() * 4 < CurArraySize && CurArraySize > 32)
107 return shrink_and_clear();
108 // Fill the array with empty markers.
109 memset(s: CurArray, c: -1, n: CurArraySize * sizeof(void *));
110 }
111
112 NumNonEmpty = 0;
113 NumTombstones = 0;
114 }
115
116 void reserve(size_type NumEntries) {
117 incrementEpoch();
118 // Do nothing if we're given zero as a reservation size.
119 if (NumEntries == 0)
120 return;
121 // No need to expand if we're small and NumEntries will fit in the space.
122 if (isSmall() && NumEntries <= CurArraySize)
123 return;
124 // insert_imp_big will reallocate if stores is more than 75% full, on the
125 // /final/ insertion.
126 if (!isSmall() && ((NumEntries - 1) * 4) < (CurArraySize * 3))
127 return;
128 // We must Grow -- find the size where we'd be 75% full, then round up to
129 // the next power of two.
130 size_type NewSize = NumEntries + (NumEntries / 3);
131 NewSize = 1 << (Log2_32_Ceil(Value: NewSize) + 1);
132 // Like insert_imp_big, always allocate at least 128 elements.
133 NewSize = std::max(a: 128u, b: NewSize);
134 Grow(NewSize);
135 }
136
137protected:
138 static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
139
140 static void *getEmptyMarker() {
141 // Note that -1 is chosen to make clear() efficiently implementable with
142 // memset and because it's not a valid pointer value.
143 return reinterpret_cast<void*>(-1);
144 }
145
146 const void **EndPointer() const {
147 return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
148 }
149
150 /// insert_imp - This returns true if the pointer was new to the set, false if
151 /// it was already in the set. This is hidden from the client so that the
152 /// derived class can check that the right type of pointer is passed in.
153 std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
154 if (isSmall()) {
155 // Check to see if it is already in the set.
156 for (const void **APtr = CurArray, **E = CurArray + NumNonEmpty;
157 APtr != E; ++APtr) {
158 const void *Value = *APtr;
159 if (Value == Ptr)
160 return std::make_pair(x&: APtr, y: false);
161 }
162
163 // Nope, there isn't. If we stay small, just 'pushback' now.
164 if (NumNonEmpty < CurArraySize) {
165 CurArray[NumNonEmpty++] = Ptr;
166 incrementEpoch();
167 return std::make_pair(x: CurArray + (NumNonEmpty - 1), y: true);
168 }
169 // Otherwise, hit the big set case, which will call grow.
170 }
171 return insert_imp_big(Ptr);
172 }
173
174 /// erase_imp - If the set contains the specified pointer, remove it and
175 /// return true, otherwise return false. This is hidden from the client so
176 /// that the derived class can check that the right type of pointer is passed
177 /// in.
178 bool erase_imp(const void * Ptr) {
179 if (isSmall()) {
180 for (const void **APtr = CurArray, **E = CurArray + NumNonEmpty;
181 APtr != E; ++APtr) {
182 if (*APtr == Ptr) {
183 *APtr = CurArray[--NumNonEmpty];
184 incrementEpoch();
185 return true;
186 }
187 }
188 return false;
189 }
190
191 auto *Bucket = doFind(Ptr);
192 if (!Bucket)
193 return false;
194
195 *const_cast<const void **>(Bucket) = getTombstoneMarker();
196 NumTombstones++;
197 // Treat this consistently from an API perspective, even if we don't
198 // actually invalidate iterators here.
199 incrementEpoch();
200 return true;
201 }
202
203 /// Returns the raw pointer needed to construct an iterator. If element not
204 /// found, this will be EndPointer. Otherwise, it will be a pointer to the
205 /// slot which stores Ptr;
206 const void *const * find_imp(const void * Ptr) const {
207 if (isSmall()) {
208 // Linear search for the item.
209 for (const void *const *APtr = CurArray, *const *E =
210 CurArray + NumNonEmpty;
211 APtr != E; ++APtr)
212 if (*APtr == Ptr)
213 return APtr;
214 return EndPointer();
215 }
216
217 // Big set case.
218 if (auto *Bucket = doFind(Ptr))
219 return Bucket;
220 return EndPointer();
221 }
222
223 bool contains_imp(const void *Ptr) const {
224 if (isSmall()) {
225 // Linear search for the item.
226 const void *const *APtr = CurArray;
227 const void *const *E = CurArray + NumNonEmpty;
228 for (; APtr != E; ++APtr)
229 if (*APtr == Ptr)
230 return true;
231 return false;
232 }
233
234 return doFind(Ptr) != nullptr;
235 }
236
237 bool isSmall() const { return IsSmall; }
238
239private:
240 LLVM_ABI std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
241
242 LLVM_ABI const void *const *doFind(const void *Ptr) const;
243 const void * const *FindBucketFor(const void *Ptr) const;
244 LLVM_ABI void shrink_and_clear();
245
246 /// Grow - Allocate a larger backing store for the buckets and move it over.
247 LLVM_ABI void Grow(unsigned NewSize);
248
249protected:
250 /// swap - Swaps the elements of two sets.
251 /// Note: This method assumes that both sets have the same small size.
252 LLVM_ABI void swap(const void **SmallStorage, const void **RHSSmallStorage,
253 SmallPtrSetImplBase &RHS);
254
255 LLVM_ABI void copyFrom(const void **SmallStorage,
256 const SmallPtrSetImplBase &RHS);
257 LLVM_ABI void moveFrom(const void **SmallStorage, unsigned SmallSize,
258 const void **RHSSmallStorage,
259 SmallPtrSetImplBase &&RHS);
260
261private:
262 /// Code shared by moveFrom() and move constructor.
263 void moveHelper(const void **SmallStorage, unsigned SmallSize,
264 const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS);
265 /// Code shared by copyFrom() and copy constructor.
266 void copyHelper(const SmallPtrSetImplBase &RHS);
267};
268
269/// SmallPtrSetIteratorImpl - This is the common base class shared between all
270/// instances of SmallPtrSetIterator.
271class SmallPtrSetIteratorImpl {
272protected:
273 const void *const *Bucket;
274 const void *const *End;
275
276public:
277 explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
278 : Bucket(BP), End(E) {
279 if (shouldReverseIterate()) {
280 RetreatIfNotValid();
281 return;
282 }
283 AdvanceIfNotValid();
284 }
285
286 bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
287 return Bucket == RHS.Bucket;
288 }
289 bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
290 return Bucket != RHS.Bucket;
291 }
292
293protected:
294 /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
295 /// that is. This is guaranteed to stop because the end() bucket is marked
296 /// valid.
297 void AdvanceIfNotValid() {
298 assert(Bucket <= End);
299 while (Bucket != End &&
300 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
301 *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
302 ++Bucket;
303 }
304 void RetreatIfNotValid() {
305 assert(Bucket >= End);
306 while (Bucket != End &&
307 (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
308 Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
309 --Bucket;
310 }
311 }
312};
313
314/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
315template <typename PtrTy>
316class LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE SmallPtrSetIterator
317 : public SmallPtrSetIteratorImpl,
318 DebugEpochBase::HandleBase {
319 using PtrTraits = PointerLikeTypeTraits<PtrTy>;
320
321public:
322 using value_type = PtrTy;
323 using reference = PtrTy;
324 using pointer = PtrTy;
325 using difference_type = std::ptrdiff_t;
326 using iterator_category = std::forward_iterator_tag;
327
328 explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,
329 const DebugEpochBase &Epoch)
330 : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {}
331
332 // Most methods are provided by the base class.
333
334 const PtrTy operator*() const {
335 assert(isHandleInSync() && "invalid iterator access!");
336 if (shouldReverseIterate()) {
337 assert(Bucket > End);
338 return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
339 }
340 assert(Bucket < End);
341 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
342 }
343
344 inline SmallPtrSetIterator& operator++() { // Preincrement
345 assert(isHandleInSync() && "invalid iterator access!");
346 if (shouldReverseIterate()) {
347 --Bucket;
348 RetreatIfNotValid();
349 return *this;
350 }
351 ++Bucket;
352 AdvanceIfNotValid();
353 return *this;
354 }
355
356 SmallPtrSetIterator operator++(int) { // Postincrement
357 SmallPtrSetIterator tmp = *this;
358 ++*this;
359 return tmp;
360 }
361};
362
363/// A templated base class for \c SmallPtrSet which provides the
364/// typesafe interface that is common across all small sizes.
365///
366/// This is particularly useful for passing around between interface boundaries
367/// to avoid encoding a particular small size in the interface boundary.
368template <typename PtrType>
369class SmallPtrSetImpl : public SmallPtrSetImplBase {
370 using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
371 using PtrTraits = PointerLikeTypeTraits<PtrType>;
372 using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;
373
374protected:
375 // Forward constructors to the base.
376 using SmallPtrSetImplBase::SmallPtrSetImplBase;
377
378public:
379 using iterator = SmallPtrSetIterator<PtrType>;
380 using const_iterator = SmallPtrSetIterator<PtrType>;
381 using key_type = ConstPtrType;
382 using value_type = PtrType;
383
384 SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
385
386 /// Inserts Ptr if and only if there is no element in the container equal to
387 /// Ptr. The bool component of the returned pair is true if and only if the
388 /// insertion takes place, and the iterator component of the pair points to
389 /// the element equal to Ptr.
390 std::pair<iterator, bool> insert(PtrType Ptr) {
391 auto p = insert_imp(Ptr: PtrTraits::getAsVoidPointer(Ptr));
392 return std::make_pair(makeIterator(P: p.first), p.second);
393 }
394
395 /// Insert the given pointer with an iterator hint that is ignored. This is
396 /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by
397 /// std::insert_iterator and std::inserter().
398 iterator insert(iterator, PtrType Ptr) {
399 return insert(Ptr).first;
400 }
401
402 /// Remove pointer from the set.
403 ///
404 /// Returns whether the pointer was in the set. Invalidates iterators if
405 /// true is returned. To remove elements while iterating over the set, use
406 /// remove_if() instead.
407 bool erase(PtrType Ptr) {
408 return erase_imp(Ptr: PtrTraits::getAsVoidPointer(Ptr));
409 }
410
411 /// Remove elements that match the given predicate.
412 ///
413 /// This method is a safe replacement for the following pattern, which is not
414 /// valid, because the erase() calls would invalidate the iterator:
415 ///
416 /// for (PtrType *Ptr : Set)
417 /// if (Pred(P))
418 /// Set.erase(P);
419 ///
420 /// Returns whether anything was removed. It is safe to read the set inside
421 /// the predicate function. However, the predicate must not modify the set
422 /// itself, only indicate a removal by returning true.
423 template <typename UnaryPredicate>
424 bool remove_if(UnaryPredicate P) {
425 bool Removed = false;
426 if (isSmall()) {
427 const void **APtr = CurArray, **E = CurArray + NumNonEmpty;
428 while (APtr != E) {
429 PtrType Ptr = PtrTraits::getFromVoidPointer(const_cast<void *>(*APtr));
430 if (P(Ptr)) {
431 *APtr = *--E;
432 --NumNonEmpty;
433 incrementEpoch();
434 Removed = true;
435 } else {
436 ++APtr;
437 }
438 }
439 return Removed;
440 }
441
442 for (const void **APtr = CurArray, **E = EndPointer(); APtr != E; ++APtr) {
443 const void *Value = *APtr;
444 if (Value == getTombstoneMarker() || Value == getEmptyMarker())
445 continue;
446 PtrType Ptr = PtrTraits::getFromVoidPointer(const_cast<void *>(Value));
447 if (P(Ptr)) {
448 *APtr = getTombstoneMarker();
449 ++NumTombstones;
450 incrementEpoch();
451 Removed = true;
452 }
453 }
454 return Removed;
455 }
456
457 /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
458 size_type count(ConstPtrType Ptr) const {
459 return contains_imp(Ptr: ConstPtrTraits::getAsVoidPointer(Ptr));
460 }
461 iterator find(ConstPtrType Ptr) const {
462 return makeIterator(P: find_imp(Ptr: ConstPtrTraits::getAsVoidPointer(Ptr)));
463 }
464 bool contains(ConstPtrType Ptr) const {
465 return contains_imp(Ptr: ConstPtrTraits::getAsVoidPointer(Ptr));
466 }
467
468 template <typename IterT>
469 void insert(IterT I, IterT E) {
470 for (; I != E; ++I)
471 insert(*I);
472 }
473
474 void insert(std::initializer_list<PtrType> IL) {
475 insert(IL.begin(), IL.end());
476 }
477
478 template <typename Range> void insert_range(Range &&R) {
479 insert(adl_begin(R), adl_end(R));
480 }
481
482 iterator begin() const {
483 if (shouldReverseIterate())
484 return makeIterator(P: EndPointer() - 1);
485 return makeIterator(P: CurArray);
486 }
487 iterator end() const { return makeIterator(P: EndPointer()); }
488
489private:
490 /// Create an iterator that dereferences to same place as the given pointer.
491 iterator makeIterator(const void *const *P) const {
492 if (shouldReverseIterate())
493 return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);
494 return iterator(P, EndPointer(), *this);
495 }
496};
497
498/// Equality comparison for SmallPtrSet.
499///
500/// Iterates over elements of LHS confirming that each value from LHS is also in
501/// RHS, and that no additional values are in RHS.
502template <typename PtrType>
503bool operator==(const SmallPtrSetImpl<PtrType> &LHS,
504 const SmallPtrSetImpl<PtrType> &RHS) {
505 if (LHS.size() != RHS.size())
506 return false;
507
508 for (const auto *KV : LHS)
509 if (!RHS.count(KV))
510 return false;
511
512 return true;
513}
514
515/// Inequality comparison for SmallPtrSet.
516///
517/// Equivalent to !(LHS == RHS).
518template <typename PtrType>
519bool operator!=(const SmallPtrSetImpl<PtrType> &LHS,
520 const SmallPtrSetImpl<PtrType> &RHS) {
521 return !(LHS == RHS);
522}
523
524/// SmallPtrSet - This class implements a set which is optimized for holding
525/// SmallSize or less elements. This internally rounds up SmallSize to the next
526/// power of two if it is not already a power of two. See the comments above
527/// SmallPtrSetImplBase for details of the algorithm.
528template<class PtrType, unsigned SmallSize>
529class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
530 // In small mode SmallPtrSet uses linear search for the elements, so it is
531 // not a good idea to choose this value too high. You may consider using a
532 // DenseSet<> instead if you expect many elements in the set.
533 static_assert(SmallSize <= 32, "SmallSize should be small");
534
535 using BaseT = SmallPtrSetImpl<PtrType>;
536
537 // A constexpr version of llvm::bit_ceil.
538 // TODO: Replace this with std::bit_ceil once C++20 is available.
539 static constexpr size_t RoundUpToPowerOfTwo(size_t X) {
540 size_t C = 1;
541 size_t CMax = C << (std::numeric_limits<size_t>::digits - 1);
542 while (C < X && C < CMax)
543 C <<= 1;
544 return C;
545 }
546
547 // Make sure that SmallSize is a power of two, round up if not.
548 static constexpr size_t SmallSizePowTwo = RoundUpToPowerOfTwo(X: SmallSize);
549 /// SmallStorage - Fixed size storage used in 'small mode'.
550 const void *SmallStorage[SmallSizePowTwo];
551
552public:
553 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
554 SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
555 SmallPtrSet(SmallPtrSet &&that)
556 : BaseT(SmallStorage, SmallSizePowTwo, that.SmallStorage,
557 std::move(that)) {}
558
559 template<typename It>
560 SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
561 this->insert(I, E);
562 }
563
564 template <typename Range>
565 SmallPtrSet(llvm::from_range_t, Range &&R)
566 : SmallPtrSet(adl_begin(R), adl_end(R)) {}
567
568 SmallPtrSet(std::initializer_list<PtrType> IL)
569 : BaseT(SmallStorage, SmallSizePowTwo) {
570 this->insert(IL.begin(), IL.end());
571 }
572
573 SmallPtrSet<PtrType, SmallSize> &
574 operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
575 if (&RHS != this)
576 this->copyFrom(SmallStorage, RHS);
577 return *this;
578 }
579
580 SmallPtrSet<PtrType, SmallSize> &
581 operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
582 if (&RHS != this)
583 this->moveFrom(SmallStorage, SmallSizePowTwo, RHS.SmallStorage,
584 std::move(RHS));
585 return *this;
586 }
587
588 SmallPtrSet<PtrType, SmallSize> &
589 operator=(std::initializer_list<PtrType> IL) {
590 this->clear();
591 this->insert(IL.begin(), IL.end());
592 return *this;
593 }
594
595 /// swap - Swaps the elements of two sets.
596 void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
597 SmallPtrSetImplBase::swap(SmallStorage, RHSSmallStorage: RHS.SmallStorage, RHS);
598 }
599};
600
601} // end namespace llvm
602
603namespace std {
604
605 /// Implement std::swap in terms of SmallPtrSet swap.
606 template<class T, unsigned N>
607 inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
608 LHS.swap(RHS);
609 }
610
611} // end namespace std
612
613#endif // LLVM_ADT_SMALLPTRSET_H
614

source code of llvm/include/llvm/ADT/SmallPtrSet.h