15#ifndef LLVM_ADT_SMALLPTRSET_H
16#define LLVM_ADT_SMALLPTRSET_H
26#include <initializer_list>
78 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
79 "Initial size must be a power of two!");
92 [[nodiscard]]
bool empty()
const {
return size() == 0; }
101 return shrink_and_clear();
116 return reinterpret_cast<void*
>(-1);
129 const void **LastTombstone =
nullptr;
132 const void *
Value = *APtr;
134 return std::make_pair(APtr,
false);
136 LastTombstone = APtr;
140 if (LastTombstone !=
nullptr) {
141 *LastTombstone =
Ptr;
144 return std::make_pair(LastTombstone,
true);
155 return insert_imp_big(
Ptr);
167 const void **Loc =
const_cast<const void **
>(
P);
188 auto *Bucket = FindBucketFor(
Ptr);
197 std::pair<const void *const *, bool> insert_imp_big(
const void *
Ptr);
199 const void *
const *FindBucketFor(
const void *
Ptr)
const;
200 void shrink_and_clear();
203 void Grow(
unsigned NewSize);
208 void swap(SmallPtrSetImplBase &
RHS);
211 void MoveFrom(
unsigned SmallSize, SmallPtrSetImplBase &&
RHS);
215 void MoveHelper(
unsigned SmallSize, SmallPtrSetImplBase &&
RHS);
217 void CopyHelper(
const SmallPtrSetImplBase &
RHS);
266template <
typename PtrTy>
286 assert(isHandleInSync() &&
"invalid iterator access!");
289 return PtrTraits::getFromVoidPointer(
const_cast<void *
>(Bucket[-1]));
292 return PtrTraits::getFromVoidPointer(
const_cast<void*
>(*Bucket));
296 assert(isHandleInSync() &&
"invalid iterator access!");
317struct RoundUpToPowerOfTwo;
321template<
unsigned N,
bool isPowerTwo>
344template <
typename PtrType>
368 return std::make_pair(makeIterator(p.first), p.second);
388 return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(
Ptr)));
394 template <
typename IterT>
400 void insert(std::initializer_list<PtrType> IL) {
401 insert(IL.begin(), IL.end());
413 iterator makeIterator(
const void *
const *
P)
const {
424template <
typename PtrType>
427 if (
LHS.size() !=
RHS.size())
430 for (
const auto *KV :
LHS)
440template <
typename PtrType>
450template<
class PtrType,
unsigned SmallSize>
455 static_assert(SmallSize <= 32,
"SmallSize should be small");
462 const void *SmallStorage[SmallSizePowTwo];
468 :
BaseT(SmallStorage, SmallSizePowTwo,
std::
move(that)) {}
470 template<
typename It>
476 :
BaseT(SmallStorage, SmallSizePowTwo) {
477 this->
insert(IL.begin(), IL.end());
497 this->
insert(IL.begin(), IL.end());
512 template<
class T,
unsigned N>
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
#define LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE
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.
void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS)
SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
const void ** CurArray
CurArray - This is the current set of buckets.
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
const void ** SmallArray
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
void CopyFrom(const 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()
static void * getTombstoneMarker()
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
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)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
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)
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.
This is an optimization pass for GlobalISel generic memory operations.
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 ...
RoundUpToPowerOfTwoH - If N is not a power of two, increase it.
RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next power of two (which mean...