15#ifndef LLVM_ADT_SMALLPTRSET_H
16#define LLVM_ADT_SMALLPTRSET_H
31#include <initializer_list>
78 const void **RHSSmallStorage,
85 "Initial size must be a power of two!");
98 [[nodiscard]]
bool empty()
const {
return size() == 0; }
108 return shrink_and_clear();
120 if (NewNumEntries == 0)
131 size_type NewSize = NewNumEntries + (NewNumEntries / 3);
134 NewSize = std::max(128u, NewSize);
144 return reinterpret_cast<void*
>(-1);
175 return {&Bucket,
false};
186 return insert_imp_big(
Ptr);
205 auto *Bucket = doFind(
Ptr);
231 if (
auto *Bucket = doFind(
Ptr))
245 return doFind(
Ptr) !=
nullptr;
251 LLVM_ABI std::pair<const void *const *, bool> insert_imp_big(
const void *
Ptr);
253 LLVM_ABI const void *
const *doFind(
const void *
Ptr)
const;
254 const void *
const *FindBucketFor(
const void *
Ptr)
const;
258 LLVM_ABI void Grow(
unsigned NewSize);
263 LLVM_ABI void swap(
const void **SmallStorage,
const void **RHSSmallStorage,
269 const void **RHSSmallStorage,
274 void moveHelper(
const void **SmallStorage,
unsigned SmallSize,
326template <
typename PtrTy>
349 return PtrTraits::getFromVoidPointer(
const_cast<void *
>(
Bucket[-1]));
352 return PtrTraits::getFromVoidPointer(
const_cast<void*
>(*
Bucket));
379template <
typename PtrType>
403 return {makeIterator(p.first), p.second};
434 template <
typename UnaryPredicate>
436 bool Removed =
false;
439 const void **APtr = Buckets.begin(), **
E = Buckets.end();
441 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(*APtr));
454 for (
const void *&Bucket :
buckets()) {
457 PtrType
Ptr = PtrTraits::getFromVoidPointer(
const_cast<void *
>(Bucket));
474 return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(
Ptr)));
480 template <
typename IterT>
486 void insert(std::initializer_list<PtrType> IL) {
487 insert(IL.begin(), IL.end());
503 iterator makeIterator(
const void *
const *
P)
const {
514template <
typename PtrType>
517 if (
LHS.size() !=
RHS.size())
520 for (
const auto *KV :
LHS)
530template <
typename PtrType>
540template<
class PtrType,
unsigned SmallSize>
545 static_assert(SmallSize <= 32,
"SmallSize should be small");
551 static constexpr size_t RoundUpToPowerOfTwo(
size_t X) {
553 size_t CMax =
C << (std::numeric_limits<size_t>::digits - 1);
554 while (
C <
X &&
C < CMax)
560 static constexpr size_t SmallSizePowTwo = RoundUpToPowerOfTwo(SmallSize);
562 const void *SmallStorage[SmallSizePowTwo];
568 : BaseT(SmallStorage, SmallSizePowTwo, that.SmallStorage,
571 template<
typename It>
576 template <
typename Range>
581 : BaseT(SmallStorage, SmallSizePowTwo) {
582 this->
insert(IL.begin(), IL.end());
595 this->
moveFrom(SmallStorage, SmallSizePowTwo,
RHS.SmallStorage,
603 this->
insert(IL.begin(), IL.end());
618 template<
class T,
unsigned N>
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
#define LLVM_DEBUGEPOCHBASE_HANDLEBASE_EMPTYBASE
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file contains library features backported from future STL versions.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
bool isHandleInSync() const
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...
iterator_range< const void ** > buckets()
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.
iterator_range< const void *const * > small_buckets() const
LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
unsigned NumEntries
Number of elements in CurArray that contain a value.
const void ** CurArray
The current set of buckets, in either small or big representation.
bool IsSmall
Whether the set is in small representation.
LLVM_ABI void copyFrom(const void **SmallStorage, const SmallPtrSetImplBase &RHS)
void reserve(size_type NewNumEntries)
bool contains_imp(const void *Ptr) const
friend class SmallPtrSetIteratorImpl
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
LLVM_ABI void moveFrom(const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS)
iterator_range< const void ** > small_buckets()
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
iterator_range< const void *const * > buckets() const
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()
LLVM_ABI 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...
SmallPtrSetIterator< PtrType > const_iterator
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
LLVM_ABI SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
void insert(IterT I, IterT E)
bool remove_if(UnaryPredicate P)
Remove elements that match the given predicate.
void insert_range(Range &&R)
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
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(llvm::from_range_t, Range &&R)
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)
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))
Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...
bool operator!=(uint64_t V1, const APInt &V2)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))
Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...
T bit_ceil(T Value)
Returns the smallest integral power of two no smaller than Value if Value is nonzero.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
constexpr bool has_single_bit(T Value) noexcept
constexpr 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 ...