15 #ifndef LLVM_ADT_SMALLPTRSET_H 16 #define LLVM_ADT_SMALLPTRSET_H 18 #include "llvm/Compiler.h" 19 #include "llvm/PointerLikeTypeTraits.h" 30 class SmallPtrSetIteratorImpl;
75 : SmallArray(SmallStorage), CurArray(SmallStorage),
76 CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
77 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
78 "Initial size must be a power of two!");
86 typedef unsigned size_type;
87 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty()
const {
return size() == 0; }
88 size_type size()
const {
return NumNonEmpty -
NumTombstones; }
94 if (size() * 4 < CurArraySize && CurArraySize > 32)
95 return shrink_and_clear();
97 memset(CurArray, -1, CurArraySize *
sizeof(
void *));
105 static void *getTombstoneMarker() {
return reinterpret_cast<void*
>(-2); }
106 static void *getEmptyMarker() {
109 return reinterpret_cast<void*
>(-1);
112 const void **EndPointer()
const {
113 return isSmall() ? CurArray + NumNonEmpty : CurArray +
CurArraySize;
119 std::pair<const void *const *, bool>
insert_imp(
const void *Ptr) {
122 const void **LastTombstone =
nullptr;
123 for (
const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
125 const void *Value = *APtr;
127 return std::make_pair(APtr,
false);
128 if (Value == getTombstoneMarker())
129 LastTombstone = APtr;
133 if (LastTombstone !=
nullptr) {
134 *LastTombstone = Ptr;
136 return std::make_pair(LastTombstone,
true);
140 if (NumNonEmpty < CurArraySize) {
141 SmallArray[NumNonEmpty++] = Ptr;
142 return std::make_pair(SmallArray + (NumNonEmpty - 1),
true);
146 return insert_imp_big(Ptr);
155 bool count_imp(
const void * Ptr)
const {
158 for (
const void *
const *APtr = SmallArray,
159 *
const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
166 return *FindBucketFor(Ptr) == Ptr;
170 bool isSmall()
const {
return CurArray ==
SmallArray; }
172 std::pair<const void *const *, bool> insert_imp_big(
const void *Ptr);
174 const void *
const *FindBucketFor(
const void *Ptr)
const;
175 void shrink_and_clear();
178 void Grow(
unsigned NewSize);
201 const void *
const *Bucket;
202 const void *
const *End;
206 : Bucket(BP), End(E) {
211 return Bucket == RHS.Bucket;
214 return Bucket != RHS.Bucket;
222 assert(Bucket <= End);
223 while (Bucket != End &&
224 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
225 *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
231 template<
typename PtrTy>
236 typedef PtrTy value_type;
237 typedef PtrTy reference;
238 typedef PtrTy pointer;
239 typedef std::ptrdiff_t difference_type;
240 typedef std::forward_iterator_tag iterator_category;
247 const PtrTy operator*()
const {
248 assert(Bucket < End);
249 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
270 template<
unsigned N,
bool isPowerTwo>
293 template <
typename PtrType>
306 explicit SmallPtrSetImpl(
const void **SmallStorage,
unsigned SmallSize)
317 std::pair<iterator, bool>
insert(PtrType Ptr) {
318 auto p =
insert_imp(PtrTraits::getAsVoidPointer(Ptr));
319 return std::make_pair(iterator(p.first, EndPointer()), p.second);
325 return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
329 size_type
count(PtrType Ptr)
const {
330 return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
333 template <
typename IterT>
334 void insert(IterT I, IterT E) {
339 inline iterator begin()
const {
340 return iterator(CurArray, EndPointer());
342 inline iterator end()
const {
343 const void *
const *End = EndPointer();
344 return iterator(End, End);
352 template<
class PtrType,
unsigned SmallSize>
357 static_assert(SmallSize <= 32,
"SmallSize should be small");
364 const void *SmallStorage[SmallSizePowTwo];
367 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
370 : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
372 template<
typename It>
373 SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
387 this->MoveFrom(SmallSizePowTwo, std::move(RHS));
400 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:329
unsigned NumNonEmpty
Number of elements in CurArray that contain a value or are a tombstone.
Definition: SmallPtrSet.h:65
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
Definition: PointerLikeTypeTraits.h:25
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:294
SmallPtrSetIteratorImpl - This is the common base class shared between all instances of SmallPtrSetIt...
Definition: SmallPtrSet.h:199
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.cpp:238
Definition: json.cpp:1170
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
Definition: SmallPtrSet.h:60
const void ** CurArray
CurArray - This is the current set of buckets.
Definition: SmallPtrSet.h:58
RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next power of two (which mean...
Definition: SmallPtrSet.h:266
void AdvanceIfNotValid()
AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket that is.
Definition: SmallPtrSet.h: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:317
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:232
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:63
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:353
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:324
const void ** SmallArray
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
Definition: SmallPtrSet.h:55
RoundUpToPowerOfTwoH - If N is not a power of two, increase it.
Definition: SmallPtrSet.h:271
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything.
Definition: SmallPtrSet.h:50
unsigned NumTombstones
Number of tombstones in CurArray.
Definition: SmallPtrSet.h:67
void swap(SmallPtrSet< PtrType, SmallSize > &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.h:392
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.h:119