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);
130 const void **LastTombstone =
nullptr;
133 const void *
Value = *APtr;
135 return std::make_pair(APtr,
false);
137 LastTombstone = APtr;
141 if (LastTombstone !=
nullptr) {
142 *LastTombstone =
Ptr;
145 return std::make_pair(LastTombstone,
true);
156 return insert_imp_big(
Ptr);
168 const void **Loc =
const_cast<const void **
>(
P);
189 auto *Bucket = FindBucketFor(
Ptr);
198 std::pair<const void *const *, bool> insert_imp_big(
const void *
Ptr);
200 const void *
const *FindBucketFor(
const void *
Ptr)
const;
201 void shrink_and_clear();
204 void Grow(
unsigned NewSize);
209 void swap(SmallPtrSetImplBase &
RHS);
212 void MoveFrom(
unsigned SmallSize, SmallPtrSetImplBase &&
RHS);
216 void MoveHelper(
unsigned SmallSize, SmallPtrSetImplBase &&
RHS);
218 void CopyHelper(
const SmallPtrSetImplBase &
RHS);
267template <
typename PtrTy>
287 assert(isHandleInSync() &&
"invalid iterator access!");
290 return PtrTraits::getFromVoidPointer(
const_cast<void *
>(Bucket[-1]));
293 return PtrTraits::getFromVoidPointer(
const_cast<void*
>(*Bucket));
297 assert(isHandleInSync() &&
"invalid iterator access!");
320template <
typename PtrType>
344 return std::make_pair(makeIterator(p.first), p.second);
364 return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(
Ptr)));
370 template <
typename IterT>
376 void insert(std::initializer_list<PtrType> IL) {
377 insert(IL.begin(), IL.end());
389 iterator makeIterator(
const void *
const *
P)
const {
400template <
typename PtrType>
403 if (
LHS.size() !=
RHS.size())
406 for (
const auto *KV :
LHS)
416template <
typename PtrType>
426template<
class PtrType,
unsigned SmallSize>
431 static_assert(SmallSize <= 32,
"SmallSize should be small");
437 static constexpr size_t RoundUpToPowerOfTwo(
size_t X) {
439 size_t CMax =
C << (std::numeric_limits<size_t>::digits - 1);
440 while (
C <
X &&
C < CMax)
446 static constexpr size_t SmallSizePowTwo = RoundUpToPowerOfTwo(SmallSize);
448 const void *SmallStorage[SmallSizePowTwo];
454 :
BaseT(SmallStorage, SmallSizePowTwo,
std::
move(that)) {}
456 template<
typename It>
462 :
BaseT(SmallStorage, SmallSizePowTwo) {
463 this->
insert(IL.begin(), IL.end());
483 this->
insert(IL.begin(), IL.end());
498 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)
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.
@ 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 ...