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