15#ifndef LLVM_ADT_SMALLPTRSET_H
16#define LLVM_ADT_SMALLPTRSET_H
26#include <initializer_list>
79 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
80 "Initial size must be a power of two!");
93 [[nodiscard]]
bool empty()
const {
return size() == 0; }
102 return shrink_and_clear();
117 return reinterpret_cast<void*
>(-1);
132 const void *
Value = *APtr;
134 return std::make_pair(APtr,
false);
145 return insert_imp_big(
Ptr);
165 auto *Bucket = FindBucketFor(
Ptr);
191 auto *Bucket = FindBucketFor(
Ptr);
200 std::pair<const void *const *, bool> insert_imp_big(
const void *
Ptr);
202 const void *
const *FindBucketFor(
const void *
Ptr)
const;
203 void shrink_and_clear();
206 void Grow(
unsigned NewSize);
269template <
typename PtrTy>
289 assert(isHandleInSync() &&
"invalid iterator access!");
292 return PtrTraits::getFromVoidPointer(
const_cast<void *
>(Bucket[-1]));
295 return PtrTraits::getFromVoidPointer(
const_cast<void*
>(*Bucket));
299 assert(isHandleInSync() &&
"invalid iterator access!");
322template <
typename PtrType>
346 return std::make_pair(makeIterator(p.first), p.second);
377 template <
typename UnaryPredicate>
379 bool Removed =
false;
383 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(*APtr));
397 const void *
Value = *APtr;
400 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(
Value));
416 return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(
Ptr)));
422 template <
typename IterT>
428 void insert(std::initializer_list<PtrType> IL) {
429 insert(IL.begin(), IL.end());
441 iterator makeIterator(
const void *
const *
P)
const {
452template <
typename PtrType>
455 if (
LHS.size() !=
RHS.size())
458 for (
const auto *KV :
LHS)
468template <
typename PtrType>
478template<
class PtrType,
unsigned SmallSize>
483 static_assert(SmallSize <= 32,
"SmallSize should be small");
489 static constexpr size_t RoundUpToPowerOfTwo(
size_t X) {
491 size_t CMax =
C << (std::numeric_limits<size_t>::digits - 1);
492 while (
C <
X &&
C < CMax)
498 static constexpr size_t SmallSizePowTwo = RoundUpToPowerOfTwo(SmallSize);
500 const void *SmallStorage[SmallSizePowTwo];
506 :
BaseT(SmallStorage, SmallSizePowTwo,
std::
move(that)) {}
508 template<
typename It>
514 :
BaseT(SmallStorage, SmallSizePowTwo) {
515 this->
insert(IL.begin(), IL.end());
535 this->
insert(IL.begin(), IL.end());
550 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
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.
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)
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.
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 ...