15 #ifndef WPIUTIL_WPI_SMALLPTRSET_H 16 #define WPIUTIL_WPI_SMALLPTRSET_H 18 #include "wpi/Compiler.h" 19 #include "wpi/PointerLikeTypeTraits.h" 20 #include "wpi/type_traits.h" 26 #include <initializer_list> 76 : SmallArray(SmallStorage), CurArray(SmallStorage),
77 CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
78 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
79 "Initial size must be a power of two!");
88 using size_type = unsigned;
92 LLVM_NODISCARD
bool empty()
const {
return size() == 0; }
93 size_type size()
const {
return NumNonEmpty -
NumTombstones; }
99 if (size() * 4 < CurArraySize && CurArraySize > 32)
100 return shrink_and_clear();
102 memset(CurArray, -1, CurArraySize *
sizeof(
void *));
110 static void *getTombstoneMarker() {
return reinterpret_cast<void*
>(-2); }
112 static void *getEmptyMarker() {
115 return reinterpret_cast<void*
>(-1);
118 const void **EndPointer()
const {
119 return isSmall() ? CurArray + NumNonEmpty : CurArray +
CurArraySize;
125 std::pair<const void *const *, bool>
insert_imp(
const void *Ptr) {
128 const void **LastTombstone =
nullptr;
129 for (
const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
131 const void *Value = *APtr;
133 return std::make_pair(APtr,
false);
134 if (Value == getTombstoneMarker())
135 LastTombstone = APtr;
139 if (LastTombstone !=
nullptr) {
140 *LastTombstone = Ptr;
142 return std::make_pair(LastTombstone,
true);
146 if (NumNonEmpty < CurArraySize) {
147 SmallArray[NumNonEmpty++] = Ptr;
148 return std::make_pair(SmallArray + (NumNonEmpty - 1),
true);
152 return insert_imp_big(Ptr);
160 const void *
const *P =
find_imp(Ptr);
161 if (P == EndPointer())
164 const void **Loc =
const_cast<const void **
>(P);
165 assert(*Loc == Ptr &&
"broken find!");
166 *Loc = getTombstoneMarker();
174 const void *
const *
find_imp(
const void * Ptr)
const {
177 for (
const void *
const *APtr = SmallArray,
178 *
const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
185 auto *Bucket = FindBucketFor(Ptr);
192 bool isSmall()
const {
return CurArray ==
SmallArray; }
194 std::pair<const void *const *, bool> insert_imp_big(
const void *Ptr);
196 const void *
const *FindBucketFor(
const void *Ptr)
const;
197 void shrink_and_clear();
200 void Grow(
unsigned NewSize);
221 const void *
const *Bucket;
222 const void *
const *End;
226 : Bucket(BP), End(E) {
231 return Bucket == RHS.Bucket;
234 return Bucket != RHS.Bucket;
242 assert(Bucket <= End);
243 while (Bucket != End &&
244 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
245 *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
248 void RetreatIfNotValid() {
249 assert(Bucket >= End);
250 while (Bucket != End &&
251 (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
252 Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
259 template <
typename PtrTy>
264 using value_type = PtrTy;
265 using reference = PtrTy;
266 using pointer = PtrTy;
267 using difference_type = std::ptrdiff_t;
268 using iterator_category = std::forward_iterator_tag;
275 const PtrTy operator*()
const {
276 assert(Bucket < End);
277 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
300 template<
unsigned N,
bool isPowerTwo>
323 template <
typename PtrType>
325 using ConstPtrType =
typename add_const_past_pointer<PtrType>::type;
336 explicit SmallPtrSetImpl(
const void **SmallStorage,
unsigned SmallSize)
342 using key_type = ConstPtrType;
343 using value_type = PtrType;
351 std::pair<iterator, bool>
insert(PtrType Ptr) {
352 auto p =
insert_imp(PtrTraits::getAsVoidPointer(Ptr));
353 return std::make_pair(makeIterator(p.first), p.second);
359 return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
363 size_type
count(ConstPtrType Ptr)
const {
return find(Ptr) != end() ? 1 : 0; }
365 return makeIterator(
find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
368 template <
typename IterT>
369 void insert(IterT I, IterT E) {
374 void insert(std::initializer_list<PtrType> IL) {
375 insert(IL.begin(), IL.end());
379 return makeIterator(CurArray);
381 iterator end()
const {
return makeIterator(EndPointer()); }
385 iterator makeIterator(
const void *
const *P)
const {
386 return iterator(P, EndPointer(), *
this);
394 template<
class PtrType,
unsigned SmallSize>
399 static_assert(SmallSize <= 32,
"SmallSize should be small");
406 const void *SmallStorage[SmallSizePowTwo];
412 :
BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
414 template<
typename It>
420 :
BaseT(SmallStorage, SmallSizePowTwo) {
421 this->insert(IL.begin(), IL.end());
434 this->MoveFrom(SmallSizePowTwo, std::move(RHS));
439 operator=(std::initializer_list<PtrType> IL) {
441 this->insert(IL.begin(), IL.end());
456 template<
class T,
unsigned N>
463 #endif // LLVM_ADT_SMALLPTRSET_H RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next power of two (which mean...
Definition: SmallPtrSet.h:296
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.cpp:212
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.h:159
unsigned NumTombstones
Number of tombstones in CurArray.
Definition: SmallPtrSet.h:67
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
Definition: SmallPtrSet.h:60
Definition: SmallVector.h:946
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:125
const void ** SmallArray
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
Definition: SmallPtrSet.h:55
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
Definition: PointerLikeTypeTraits.h:26
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything.
Definition: SmallPtrSet.h:50
namespace to hold default to_json function
Definition: json_binary_writer.cpp:39
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:324
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:896
const void ** CurArray
CurArray - This is the current set of buckets.
Definition: SmallPtrSet.h:58
unsigned NumNonEmpty
Number of elements in CurArray that contain a value or are a tombstone.
Definition: SmallPtrSet.h:65
RoundUpToPowerOfTwoH - If N is not a power of two, increase it.
Definition: SmallPtrSet.h:301
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:363
void AdvanceIfNotValid()
AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket that is.
Definition: SmallPtrSet.h:241
const void *const * find_imp(const void *Ptr) const
Returns the raw pointer needed to construct an iterator.
Definition: SmallPtrSet.h:174
void swap(SmallPtrSet< PtrType, SmallSize > &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.h:446
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:260
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:358
bool operator==(json::const_reference lhs, json::const_reference rhs) noexcept
Definition: json.cpp:921
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:395
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:351
SmallPtrSetIteratorImpl - This is the common base class shared between all instances of SmallPtrSetIt...
Definition: SmallPtrSet.h:219