15 #ifndef LLVM_ADT_SMALLPTRSET_H
16 #define LLVM_ADT_SMALLPTRSET_H
18 #include "llvm/Compiler.h"
19 #include "llvm/PointerLikeTypeTraits.h"
28 class SmallPtrSetIteratorImpl;
61 unsigned NumTombstones;
69 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
70 "Initial size must be a power of two!");
76 typedef unsigned size_type;
77 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty()
const {
return size() == 0; }
78 size_type size()
const {
return NumElements; }
84 return shrink_and_clear();
93 static void *getTombstoneMarker() {
return reinterpret_cast<void*
>(-2); }
94 static void *getEmptyMarker() {
97 return reinterpret_cast<void*
>(-1);
103 std::pair<const void *const *, bool>
insert_imp(
const void *Ptr);
111 bool count_imp(
const void * Ptr)
const {
115 *
const *E =
SmallArray+NumElements; APtr != E; ++APtr)
122 return *FindBucketFor(Ptr) == Ptr;
128 const void *
const *FindBucketFor(
const void *Ptr)
const;
129 void shrink_and_clear();
132 void Grow(
unsigned NewSize);
134 void operator=(
const SmallPtrSetImplBase &RHS) =
delete;
138 void swap(SmallPtrSetImplBase &RHS);
140 void CopyFrom(
const SmallPtrSetImplBase &RHS);
141 void MoveFrom(
unsigned SmallSize, SmallPtrSetImplBase &&RHS);
148 const void *
const *Bucket;
149 const void *
const *End;
152 : Bucket(BP), End(E) {
157 return Bucket == RHS.Bucket;
160 return Bucket != RHS.Bucket;
168 assert(Bucket <= End);
169 while (Bucket != End &&
170 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
171 *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
177 template<
typename PtrTy>
182 typedef PtrTy value_type;
183 typedef PtrTy reference;
184 typedef PtrTy pointer;
185 typedef std::ptrdiff_t difference_type;
186 typedef std::forward_iterator_tag iterator_category;
193 const PtrTy operator*()
const {
194 assert(Bucket < End);
195 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
216 template<
unsigned N,
bool isPowerTwo>
240 template <
typename PtrType>
252 explicit SmallPtrSetImpl(
const void **SmallStorage,
unsigned SmallSize)
263 std::pair<iterator, bool>
insert(PtrType Ptr) {
264 auto p =
insert_imp(PtrTraits::getAsVoidPointer(Ptr));
271 return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
275 size_type
count(PtrType Ptr)
const {
276 return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
279 template <
typename IterT>
280 void insert(IterT I, IterT E) {
285 inline iterator begin()
const {
288 inline iterator end()
const {
297 template<
class PtrType,
unsigned SmallSize>
304 const void *SmallStorage[SmallSizePowTwo];
309 :
BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
311 template<
typename It>
326 this->MoveFrom(SmallSizePowTwo, std::move(RHS));
340 template<
class T,
unsigned N>
size_type count(PtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:275
PointerLikeTypeTraits - This is a traits object that is used to handle pointer types and things that ...
Definition: PointerLikeTypeTraits.h:26
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:241
SmallPtrSetIteratorImpl - This is the common base class shared between all instances of SmallPtrSetIt...
Definition: SmallPtrSet.h:146
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.cpp:285
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
Definition: SmallPtrSet.h:57
const void ** CurArray
CurArray - This is the current set of buckets.
Definition: SmallPtrSet.h:55
RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next power of two (which mean...
Definition: SmallPtrSet.h:212
void AdvanceIfNotValid()
AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket that is.
Definition: SmallPtrSet.h:167
void CopyFrom(const SmallPtrSetImplBase &RHS)
CopyFrom - implement operator= from a smallptrset that has the same pointer type, but may have a diff...
Definition: SmallPtrSet.cpp:221
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:263
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:178
bool erase_imp(const void *Ptr)
erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return fa...
Definition: SmallPtrSet.cpp:77
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:298
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:270
const void ** SmallArray
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
Definition: SmallPtrSet.h:52
RoundUpToPowerOfTwoH - If N is not a power of two, increase it.
Definition: SmallPtrSet.h:217
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything.
Definition: SmallPtrSet.h:48
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...
Definition: SmallPtrSet.cpp:38
void swap(SmallPtrSet< PtrType, SmallSize > &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.h:331