1//===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 10/// This file defines the SmallPtrSet class. See the doxygen comment for 11/// SmallPtrSetImplBase for more details on the algorithm used. 13//===----------------------------------------------------------------------===// 15#ifndef LLVM_ADT_SMALLPTRSET_H 16#define LLVM_ADT_SMALLPTRSET_H 27#include <initializer_list> 34/// SmallPtrSetImplBase - This is the common code shared among all the 35/// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one 36/// for small and one for large sets. 38/// Small sets use an array of pointers allocated in the SmallPtrSet object, 39/// which is treated as a simple array of pointers. When a pointer is added to 40/// the set, the array is scanned to see if the element already exists, if not 41/// the element is 'pushed back' onto the array. If we run out of space in the 42/// array, we grow into the 'large set' case. SmallSet should be used when the 43/// sets are often small. In this case, no memory allocation is used, and only 44/// light-weight and cache-efficient scanning is used. 46/// Large sets use a classic exponentially-probed hash table. Empty buckets are 47/// represented with an illegal pointer value (-1) to allow null pointers to be 48/// inserted. Tombstones are represented with another illegal pointer value 49/// (-2), to allow deletion. The hash table is resized when the table is 3/4 or 50/// more. When this happens, the table is doubled in size. 56 /// The current set of buckets, in either small or big representation. 58 /// CurArraySize - The allocated size of CurArray, always a power of two. 61 /// Number of elements in CurArray that contain a value or are a tombstone. 62 /// If small, all these elements are at the beginning of CurArray and the rest 65 /// Number of tombstones in CurArray. 67 /// Whether the set is in small representation. 70// Helpers to copy and move construct a SmallPtrSet. 79assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
80"Initial size must be a power of two!");
99// If the capacity of the array is huge, and the # elements used is small, 103return shrink_and_clear();
104// Fill the array with empty markers. 114// Do nothing if we're given zero as a reservation size. 117// No need to expand if we're small and NumEntries will fit in the space. 120// insert_imp_big will reallocate if stores is more than 75% full, on the 124// We must Grow -- find the size where we'd be 75% full, then round up to 125// the next power of two. 126size_type NewSize = NumEntries + (NumEntries / 3);
128// Like insert_imp_big, always allocate at least 128 elements. 129 NewSize = std::max(128u, NewSize);
137// Note that -1 is chosen to make clear() efficiently implementable with 138// memset and because it's not a valid pointer value. 139returnreinterpret_cast<void*
>(-1);
146 /// insert_imp - This returns true if the pointer was new to the set, false if 147 /// it was already in the set. This is hidden from the client so that the 148 /// derived class can check that the right type of pointer is passed in. 151// Check to see if it is already in the set. 154constvoid *
Value = *APtr;
156return std::make_pair(APtr,
false);
159// Nope, there isn't. If we stay small, just 'pushback' now. 165// Otherwise, hit the big set case, which will call grow. 167return insert_imp_big(
Ptr);
170 /// erase_imp - If the set contains the specified pointer, remove it and 171 /// return true, otherwise return false. This is hidden from the client so 172 /// that the derived class can check that the right type of pointer is passed 187auto *Bucket = doFind(
Ptr);
193// Treat this consistently from an API perspective, even if we don't 194// actually invalidate iterators here. 199 /// Returns the raw pointer needed to construct an iterator. If element not 200 /// found, this will be EndPointer. Otherwise, it will be a pointer to the 201 /// slot which stores Ptr; 204// Linear search for the item. 205for (
constvoid *
const *APtr =
CurArray, *
const *
E =
214if (
auto *Bucket = doFind(
Ptr))
221// Linear search for the item. 224for (; APtr !=
E; ++APtr)
230return doFind(
Ptr) !=
nullptr;
236 std::pair<const void *const *, bool> insert_imp_big(
constvoid *
Ptr);
238constvoid *
const *doFind(
constvoid *
Ptr)
const;
239constvoid *
const *FindBucketFor(
constvoid *
Ptr)
const;
240void shrink_and_clear();
242 /// Grow - Allocate a larger backing store for the buckets and move it over. 243void Grow(
unsigned NewSize);
246 /// swap - Swaps the elements of two sets. 247 /// Note: This method assumes that both sets have the same small size. 248void swap(
constvoid **SmallStorage,
constvoid **RHSSmallStorage,
252voidmoveFrom(
constvoid **SmallStorage,
unsigned SmallSize,
256 /// Code shared by moveFrom() and move constructor. 257void moveHelper(
constvoid **SmallStorage,
unsigned SmallSize,
259 /// Code shared by copyFrom() and copy constructor. 263/// SmallPtrSetIteratorImpl - This is the common base class shared between all 264/// instances of SmallPtrSetIterator. 288 /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket 289 /// that is. This is guaranteed to stop because the end() bucket is marked 308/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. 309template <
typename PtrTy>
326// Most methods are provided by the base class. 329assert(isHandleInSync() &&
"invalid iterator access!");
332return PtrTraits::getFromVoidPointer(
const_cast<void *
>(Bucket[-1]));
335return PtrTraits::getFromVoidPointer(
const_cast<void*
>(*Bucket));
339assert(isHandleInSync() &&
"invalid iterator access!");
357/// A templated base class for \c SmallPtrSet which provides the 358/// typesafe interface that is common across all small sizes. 360/// This is particularly useful for passing around between interface boundaries 361/// to avoid encoding a particular small size in the interface boundary. 362template <
typename PtrType>
369// Forward constructors to the base. 380 /// Inserts Ptr if and only if there is no element in the container equal to 381 /// Ptr. The bool component of the returned pair is true if and only if the 382 /// insertion takes place, and the iterator component of the pair points to 383 /// the element equal to Ptr. 386return std::make_pair(makeIterator(p.first), p.second);
389 /// Insert the given pointer with an iterator hint that is ignored. This is 390 /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by 391 /// std::insert_iterator and std::inserter(). 396 /// Remove pointer from the set. 398 /// Returns whether the pointer was in the set. Invalidates iterators if 399 /// true is returned. To remove elements while iterating over the set, use 400 /// remove_if() instead. 405 /// Remove elements that match the given predicate. 407 /// This method is a safe replacement for the following pattern, which is not 408 /// valid, because the erase() calls would invalidate the iterator: 410 /// for (PtrType *Ptr : Set) 414 /// Returns whether anything was removed. It is safe to read the set inside 415 /// the predicate function. However, the predicate must not modify the set 416 /// itself, only indicate a removal by returning true. 417template <
typename UnaryPredicate>
423 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(*APtr));
437constvoid *
Value = *APtr;
440 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(
Value));
451 /// count - Return 1 if the specified pointer is in the set, 0 otherwise. 456return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(
Ptr)));
462template <
typename IterT>
468voidinsert(std::initializer_list<PtrType> IL) {
469insert(IL.begin(), IL.end());
480 /// Create an iterator that dereferences to same place as the given pointer. 481iterator makeIterator(
constvoid *
const *
P)
const{
488/// Equality comparison for SmallPtrSet. 490/// Iterates over elements of LHS confirming that each value from LHS is also in 491/// RHS, and that no additional values are in RHS. 492template <
typename PtrType>
495if (
LHS.size() !=
RHS.size())
498for (
constauto *KV :
LHS)
505/// Inequality comparison for SmallPtrSet. 507/// Equivalent to !(LHS == RHS). 508template <
typename PtrType>
514/// SmallPtrSet - This class implements a set which is optimized for holding 515/// SmallSize or less elements. This internally rounds up SmallSize to the next 516/// power of two if it is not already a power of two. See the comments above 517/// SmallPtrSetImplBase for details of the algorithm. 518template<
class PtrType,
unsigned SmallSize>
520// In small mode SmallPtrSet uses linear search for the elements, so it is 521// not a good idea to choose this value too high. You may consider using a 522// DenseSet<> instead if you expect many elements in the set. 523static_assert(SmallSize <= 32,
"SmallSize should be small");
527// A constexpr version of llvm::bit_ceil. 528// TODO: Replace this with std::bit_ceil once C++20 is available. 529staticconstexprsize_t RoundUpToPowerOfTwo(
size_tX) {
531size_t CMax =
C << (std::numeric_limits<size_t>::digits - 1);
532while (
C <
X &&
C < CMax)
537// Make sure that SmallSize is a power of two, round up if not. 538staticconstexprsize_t SmallSizePowTwo = RoundUpToPowerOfTwo(SmallSize);
539 /// SmallStorage - Fixed size storage used in 'small mode'. 540constvoid *SmallStorage[SmallSizePowTwo];
546 :
BaseT(SmallStorage, SmallSizePowTwo, that.SmallStorage,
555 :
BaseT(SmallStorage, SmallSizePowTwo) {
556 this->
insert(IL.begin(), IL.end());
569 this->
moveFrom(SmallStorage, SmallSizePowTwo,
RHS.SmallStorage,
577 this->
insert(IL.begin(), IL.end());
581 /// swap - Swaps the elements of two sets. 587}
// end namespace llvm 591 /// Implement std::swap in terms of SmallPtrSet swap. 592template<
class T,
unsigned N>
599#endif// LLVM_ADT_SMALLPTRSET_H static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
#define LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...
const void *const * find_imp(const void *Ptr) const
Returns the raw pointer needed to construct an iterator.
unsigned NumTombstones
Number of tombstones in CurArray.
SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
const void ** CurArray
The current set of buckets, in either small or big representation.
bool IsSmall
Whether the set is in small representation.
void copyFrom(const void **SmallStorage, const SmallPtrSetImplBase &RHS)
bool contains_imp(const void *Ptr) const
unsigned NumNonEmpty
Number of elements in CurArray that contain a value or are a tombstone.
std::pair< const void *const *, bool > insert_imp(const void *Ptr)
insert_imp - This returns true if the pointer was new to the set, false if it was already in the set.
SmallPtrSetImplBase & operator=(const SmallPtrSetImplBase &)=delete
void moveFrom(const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS)
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
const void ** EndPointer() const
bool erase_imp(const void *Ptr)
erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return fa...
static void * getEmptyMarker()
void reserve(size_type NumEntries)
static void * getTombstoneMarker()
void swap(const void **SmallStorage, const void **RHSSmallStorage, SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
size_type capacity() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
iterator insert(iterator, PtrType Ptr)
Insert the given pointer with an iterator hint that is ignored.
bool erase(PtrType Ptr)
Remove pointer from the set.
iterator find(ConstPtrType Ptr) const
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
SmallPtrSetImpl(const SmallPtrSetImpl &)=delete
void insert(IterT I, IterT E)
bool remove_if(UnaryPredicate P)
Remove elements that match the given predicate.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSetIterator< PtrType > iterator
void insert(std::initializer_list< PtrType > IL)
bool contains(ConstPtrType Ptr) const
SmallPtrSetIteratorImpl - This is the common base class shared between all instances of SmallPtrSetIt...
bool operator!=(const SmallPtrSetIteratorImpl &RHS) const
SmallPtrSetIteratorImpl(const void *const *BP, const void *const *E)
const void *const * Bucket
bool operator==(const SmallPtrSetIteratorImpl &RHS) const
void AdvanceIfNotValid()
AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket that is.
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
const PtrTy operator*() const
std::ptrdiff_t difference_type
SmallPtrSetIterator(const void *const *BP, const void *const *E, const DebugEpochBase &Epoch)
SmallPtrSetIterator operator++(int)
SmallPtrSetIterator & operator++()
std::forward_iterator_tag iterator_category
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallPtrSet(SmallPtrSet &&that)
SmallPtrSet< PtrType, SmallSize > & operator=(SmallPtrSet< PtrType, SmallSize > &&RHS)
void swap(SmallPtrSet< PtrType, SmallSize > &RHS)
swap - Swaps the elements of two sets.
SmallPtrSet(std::initializer_list< PtrType > IL)
SmallPtrSet< PtrType, SmallSize > & operator=(const SmallPtrSet< PtrType, SmallSize > &RHS)
SmallPtrSet(const SmallPtrSet &that)
SmallPtrSet< PtrType, SmallSize > & operator=(std::initializer_list< PtrType > IL)
LLVM Value Representation.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
bool operator!=(uint64_t V1, const APInt &V2)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool shouldReverseIterate()
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
