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/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(ptr: CurArray);
85 }
86
87public:
88 using size_type = unsigned;
89
90 SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;
91
92 [[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(s: CurArray, c: -1, n: 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(x&: APtr, y: 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(x&: LastTombstone, y: 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(x: SmallArray + (NumNonEmpty - 1), y: 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 LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE SmallPtrSetIterator
268 : public SmallPtrSetIteratorImpl,
269 DebugEpochBase::HandleBase {
270 using PtrTraits = PointerLikeTypeTraits<PtrTy>;
271
272public:
273 using value_type = PtrTy;
274 using reference = PtrTy;
275 using pointer = PtrTy;
276 using difference_type = std::ptrdiff_t;
277 using iterator_category = std::forward_iterator_tag;
278
279 explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,
280 const DebugEpochBase &Epoch)
281 : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {}
282
283 // Most methods are provided by the base class.
284
285 const PtrTy operator*() const {
286 assert(isHandleInSync() && "invalid iterator access!");
287 if (shouldReverseIterate()) {
288 assert(Bucket > End);
289 return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
290 }
291 assert(Bucket < End);
292 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
293 }
294
295 inline SmallPtrSetIterator& operator++() { // Preincrement
296 assert(isHandleInSync() && "invalid iterator access!");
297 if (shouldReverseIterate()) {
298 --Bucket;
299 RetreatIfNotValid();
300 return *this;
301 }
302 ++Bucket;
303 AdvanceIfNotValid();
304 return *this;
305 }
306
307 SmallPtrSetIterator operator++(int) { // Postincrement
308 SmallPtrSetIterator tmp = *this;
309 ++*this;
310 return tmp;
311 }
312};
313
314/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
315/// power of two (which means N itself if N is already a power of two).
316template<unsigned N>
317struct RoundUpToPowerOfTwo;
318
319/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a
320/// helper template used to implement RoundUpToPowerOfTwo.
321template<unsigned N, bool isPowerTwo>
322struct RoundUpToPowerOfTwoH {
323 enum { Val = N };
324};
325template<unsigned N>
326struct RoundUpToPowerOfTwoH<N, false> {
327 enum {
328 // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
329 // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
330 Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
331 };
332};
333
334template<unsigned N>
335struct RoundUpToPowerOfTwo {
336 enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
337};
338
339/// A templated base class for \c SmallPtrSet which provides the
340/// typesafe interface that is common across all small sizes.
341///
342/// This is particularly useful for passing around between interface boundaries
343/// to avoid encoding a particular small size in the interface boundary.
344template <typename PtrType>
345class SmallPtrSetImpl : public SmallPtrSetImplBase {
346 using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
347 using PtrTraits = PointerLikeTypeTraits<PtrType>;
348 using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;
349
350protected:
351 // Forward constructors to the base.
352 using SmallPtrSetImplBase::SmallPtrSetImplBase;
353
354public:
355 using iterator = SmallPtrSetIterator<PtrType>;
356 using const_iterator = SmallPtrSetIterator<PtrType>;
357 using key_type = ConstPtrType;
358 using value_type = PtrType;
359
360 SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
361
362 /// Inserts Ptr if and only if there is no element in the container equal to
363 /// Ptr. The bool component of the returned pair is true if and only if the
364 /// insertion takes place, and the iterator component of the pair points to
365 /// the element equal to Ptr.
366 std::pair<iterator, bool> insert(PtrType Ptr) {
367 auto p = insert_imp(Ptr: PtrTraits::getAsVoidPointer(Ptr));
368 return std::make_pair(makeIterator(P: p.first), p.second);
369 }
370
371 /// Insert the given pointer with an iterator hint that is ignored. This is
372 /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by
373 /// std::insert_iterator and std::inserter().
374 iterator insert(iterator, PtrType Ptr) {
375 return insert(Ptr).first;
376 }
377
378 /// erase - If the set contains the specified pointer, remove it and return
379 /// true, otherwise return false.
380 bool erase(PtrType Ptr) {
381 return erase_imp(Ptr: PtrTraits::getAsVoidPointer(Ptr));
382 }
383 /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
384 size_type count(ConstPtrType Ptr) const {
385 return find_imp(Ptr: ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
386 }
387 iterator find(ConstPtrType Ptr) const {
388 return makeIterator(P: find_imp(Ptr: ConstPtrTraits::getAsVoidPointer(Ptr)));
389 }
390 bool contains(ConstPtrType Ptr) const {
391 return find_imp(Ptr: ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
392 }
393
394 template <typename IterT>
395 void insert(IterT I, IterT E) {
396 for (; I != E; ++I)
397 insert(*I);
398 }
399
400 void insert(std::initializer_list<PtrType> IL) {
401 insert(IL.begin(), IL.end());
402 }
403
404 iterator begin() const {
405 if (shouldReverseIterate())
406 return makeIterator(P: EndPointer() - 1);
407 return makeIterator(P: CurArray);
408 }
409 iterator end() const { return makeIterator(P: EndPointer()); }
410
411private:
412 /// Create an iterator that dereferences to same place as the given pointer.
413 iterator makeIterator(const void *const *P) const {
414 if (shouldReverseIterate())
415 return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);
416 return iterator(P, EndPointer(), *this);
417 }
418};
419
420/// Equality comparison for SmallPtrSet.
421///
422/// Iterates over elements of LHS confirming that each value from LHS is also in
423/// RHS, and that no additional values are in RHS.
424template <typename PtrType>
425bool operator==(const SmallPtrSetImpl<PtrType> &LHS,
426 const SmallPtrSetImpl<PtrType> &RHS) {
427 if (LHS.size() != RHS.size())
428 return false;
429
430 for (const auto *KV : LHS)
431 if (!RHS.count(KV))
432 return false;
433
434 return true;
435}
436
437/// Inequality comparison for SmallPtrSet.
438///
439/// Equivalent to !(LHS == RHS).
440template <typename PtrType>
441bool operator!=(const SmallPtrSetImpl<PtrType> &LHS,
442 const SmallPtrSetImpl<PtrType> &RHS) {
443 return !(LHS == RHS);
444}
445
446/// SmallPtrSet - This class implements a set which is optimized for holding
447/// SmallSize or less elements. This internally rounds up SmallSize to the next
448/// power of two if it is not already a power of two. See the comments above
449/// SmallPtrSetImplBase for details of the algorithm.
450template<class PtrType, unsigned SmallSize>
451class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
452 // In small mode SmallPtrSet uses linear search for the elements, so it is
453 // not a good idea to choose this value too high. You may consider using a
454 // DenseSet<> instead if you expect many elements in the set.
455 static_assert(SmallSize <= 32, "SmallSize should be small");
456
457 using BaseT = SmallPtrSetImpl<PtrType>;
458
459 // Make sure that SmallSize is a power of two, round up if not.
460 enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
461 /// SmallStorage - Fixed size storage used in 'small mode'.
462 const void *SmallStorage[SmallSizePowTwo];
463
464public:
465 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
466 SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
467 SmallPtrSet(SmallPtrSet &&that)
468 : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
469
470 template<typename It>
471 SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
472 this->insert(I, E);
473 }
474
475 SmallPtrSet(std::initializer_list<PtrType> IL)
476 : BaseT(SmallStorage, SmallSizePowTwo) {
477 this->insert(IL.begin(), IL.end());
478 }
479
480 SmallPtrSet<PtrType, SmallSize> &
481 operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
482 if (&RHS != this)
483 this->CopyFrom(RHS);
484 return *this;
485 }
486
487 SmallPtrSet<PtrType, SmallSize> &
488 operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
489 if (&RHS != this)
490 this->MoveFrom(SmallSizePowTwo, std::move(RHS));
491 return *this;
492 }
493
494 SmallPtrSet<PtrType, SmallSize> &
495 operator=(std::initializer_list<PtrType> IL) {
496 this->clear();
497 this->insert(IL.begin(), IL.end());
498 return *this;
499 }
500
501 /// swap - Swaps the elements of two sets.
502 void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
503 SmallPtrSetImplBase::swap(RHS);
504 }
505};
506
507} // end namespace llvm
508
509namespace std {
510
511 /// Implement std::swap in terms of SmallPtrSet swap.
512 template<class T, unsigned N>
513 inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
514 LHS.swap(RHS);
515 }
516
517} // end namespace std
518
519#endif // LLVM_ADT_SMALLPTRSET_H
520

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