15#ifndef LLVM_ADT_SMALLPTRSET_H
16#define LLVM_ADT_SMALLPTRSET_H
28#include <initializer_list>
81 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
82 "Initial size must be a power of two!");
95 [[nodiscard]]
bool empty()
const {
return size() == 0; }
105 return shrink_and_clear();
128 size_type NewSize = NumEntries + (NumEntries / 3);
131 NewSize = std::max(128u, NewSize);
141 return reinterpret_cast<void*
>(-1);
156 const void *
Value = *APtr;
158 return std::make_pair(APtr,
false);
169 return insert_imp_big(
Ptr);
189 auto *Bucket = FindBucketFor(
Ptr);
215 auto *Bucket = FindBucketFor(
Ptr);
224 std::pair<const void *const *, bool> insert_imp_big(
const void *
Ptr);
226 const void *
const *FindBucketFor(
const void *
Ptr)
const;
227 void shrink_and_clear();
230 void Grow(
unsigned NewSize);
293template <
typename PtrTy>
313 assert(isHandleInSync() &&
"invalid iterator access!");
316 return PtrTraits::getFromVoidPointer(
const_cast<void *
>(Bucket[-1]));
319 return PtrTraits::getFromVoidPointer(
const_cast<void*
>(*Bucket));
323 assert(isHandleInSync() &&
"invalid iterator access!");
346template <
typename PtrType>
370 return std::make_pair(makeIterator(p.first), p.second);
401 template <
typename UnaryPredicate>
403 bool Removed =
false;
407 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(*APtr));
421 const void *
Value = *APtr;
424 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(
Value));
440 return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(
Ptr)));
446 template <
typename IterT>
452 void insert(std::initializer_list<PtrType> IL) {
453 insert(IL.begin(), IL.end());
465 iterator makeIterator(
const void *
const *
P)
const {
476template <
typename PtrType>
479 if (
LHS.size() !=
RHS.size())
482 for (
const auto *KV :
LHS)
492template <
typename PtrType>
502template<
class PtrType,
unsigned SmallSize>
507 static_assert(SmallSize <= 32,
"SmallSize should be small");
513 static constexpr size_t RoundUpToPowerOfTwo(
size_t X) {
515 size_t CMax =
C << (std::numeric_limits<size_t>::digits - 1);
516 while (
C <
X &&
C < CMax)
522 static constexpr size_t SmallSizePowTwo = RoundUpToPowerOfTwo(SmallSize);
524 const void *SmallStorage[SmallSizePowTwo];
530 :
BaseT(SmallStorage, SmallSizePowTwo,
std::
move(that)) {}
532 template<
typename It>
538 :
BaseT(SmallStorage, SmallSizePowTwo) {
539 this->
insert(IL.begin(), IL.end());
559 this->
insert(IL.begin(), IL.end());
574 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()
void reserve(size_type NumEntries)
static void * getTombstoneMarker()
void swap(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 ...