WPILibC++  unspecified
SmallPtrSet.h
1 //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the SmallPtrSet class. See the doxygen comment for
11 // SmallPtrSetImplBase for more details on the algorithm used.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ADT_SMALLPTRSET_H
16 #define LLVM_ADT_SMALLPTRSET_H
17 
18 #include "llvm/Compiler.h"
19 #include "llvm/PointerLikeTypeTraits.h"
20 #include <cassert>
21 #include <cstddef>
22 #include <cstdint>
23 #include <cstring>
24 #include <cstdlib>
25 #include <iterator>
26 #include <utility>
27 
28 namespace llvm {
29 
30 class SmallPtrSetIteratorImpl;
31 
51  friend class SmallPtrSetIteratorImpl;
52 
53 protected:
55  const void **SmallArray;
58  const void **CurArray;
60  unsigned CurArraySize;
61 
65  unsigned NumNonEmpty;
67  unsigned NumTombstones;
68 
69  // Helpers to copy and move construct a SmallPtrSet.
70  SmallPtrSetImplBase(const void **SmallStorage,
71  const SmallPtrSetImplBase &that);
72  SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
73  SmallPtrSetImplBase &&that);
74  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
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!");
79  }
81  if (!isSmall())
82  free(CurArray);
83  }
84 
85 public:
86  typedef unsigned size_type;
87  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; }
88  size_type size() const { return NumNonEmpty - NumTombstones; }
89 
90  void clear() {
91  // If the capacity of the array is huge, and the # elements used is small,
92  // shrink the array.
93  if (!isSmall()) {
94  if (size() * 4 < CurArraySize && CurArraySize > 32)
95  return shrink_and_clear();
96  // Fill the array with empty markers.
97  memset(CurArray, -1, CurArraySize * sizeof(void *));
98  }
99 
100  NumNonEmpty = 0;
101  NumTombstones = 0;
102  }
103 
104 protected:
105  static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
106  static void *getEmptyMarker() {
107  // Note that -1 is chosen to make clear() efficiently implementable with
108  // memset and because it's not a valid pointer value.
109  return reinterpret_cast<void*>(-1);
110  }
111 
112  const void **EndPointer() const {
113  return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
114  }
115 
119  std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
120  if (isSmall()) {
121  // Check to see if it is already in the set.
122  const void **LastTombstone = nullptr;
123  for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
124  APtr != E; ++APtr) {
125  const void *Value = *APtr;
126  if (Value == Ptr)
127  return std::make_pair(APtr, false);
128  if (Value == getTombstoneMarker())
129  LastTombstone = APtr;
130  }
131 
132  // Did we find any tombstone marker?
133  if (LastTombstone != nullptr) {
134  *LastTombstone = Ptr;
135  --NumTombstones;
136  return std::make_pair(LastTombstone, true);
137  }
138 
139  // Nope, there isn't. If we stay small, just 'pushback' now.
140  if (NumNonEmpty < CurArraySize) {
141  SmallArray[NumNonEmpty++] = Ptr;
142  return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
143  }
144  // Otherwise, hit the big set case, which will call grow.
145  }
146  return insert_imp_big(Ptr);
147  }
148 
153  bool erase_imp(const void * Ptr);
154 
155  bool count_imp(const void * Ptr) const {
156  if (isSmall()) {
157  // Linear search for the item.
158  for (const void *const *APtr = SmallArray,
159  *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
160  if (*APtr == Ptr)
161  return true;
162  return false;
163  }
164 
165  // Big set case.
166  return *FindBucketFor(Ptr) == Ptr;
167  }
168 
169 private:
170  bool isSmall() const { return CurArray == SmallArray; }
171 
172  std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
173 
174  const void * const *FindBucketFor(const void *Ptr) const;
175  void shrink_and_clear();
176 
178  void Grow(unsigned NewSize);
179 
180  void operator=(const SmallPtrSetImplBase &RHS) = delete;
181 
182 protected:
185  void swap(SmallPtrSetImplBase &RHS);
186 
187  void CopyFrom(const SmallPtrSetImplBase &RHS);
188  void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
189 
190 private:
192  void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
194  void CopyHelper(const SmallPtrSetImplBase &RHS);
195 };
196 
200 protected:
201  const void *const *Bucket;
202  const void *const *End;
203 
204 public:
205  explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
206  : Bucket(BP), End(E) {
207  AdvanceIfNotValid();
208  }
209 
210  bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
211  return Bucket == RHS.Bucket;
212  }
213  bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
214  return Bucket != RHS.Bucket;
215  }
216 
217 protected:
222  assert(Bucket <= End);
223  while (Bucket != End &&
224  (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
225  *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
226  ++Bucket;
227  }
228 };
229 
231 template<typename PtrTy>
234 
235 public:
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;
241 
242  explicit SmallPtrSetIterator(const void *const *BP, const void *const *E)
243  : SmallPtrSetIteratorImpl(BP, E) {}
244 
245  // Most methods provided by baseclass.
246 
247  const PtrTy operator*() const {
248  assert(Bucket < End);
249  return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
250  }
251 
252  inline SmallPtrSetIterator& operator++() { // Preincrement
253  ++Bucket;
254  AdvanceIfNotValid();
255  return *this;
256  }
257 
258  SmallPtrSetIterator operator++(int) { // Postincrement
259  SmallPtrSetIterator tmp = *this; ++*this; return tmp;
260  }
261 };
262 
265 template<unsigned N>
267 
270 template<unsigned N, bool isPowerTwo>
272  enum { Val = N };
273 };
274 template<unsigned N>
275 struct RoundUpToPowerOfTwoH<N, false> {
276  enum {
277  // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
278  // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
279  Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
280  };
281 };
282 
283 template<unsigned N>
284 struct RoundUpToPowerOfTwo {
285  enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
286 };
287 
293 template <typename PtrType>
296 
297  SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
298 
299 protected:
300  // Constructors that forward to the base.
301  SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
302  : SmallPtrSetImplBase(SmallStorage, that) {}
303  SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
304  SmallPtrSetImpl &&that)
305  : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
306  explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize)
307  : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
308 
309 public:
312 
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);
320  }
321 
324  bool erase(PtrType Ptr) {
325  return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
326  }
327 
329  size_type count(PtrType Ptr) const {
330  return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
331  }
332 
333  template <typename IterT>
334  void insert(IterT I, IterT E) {
335  for (; I != E; ++I)
336  insert(*I);
337  }
338 
339  inline iterator begin() const {
340  return iterator(CurArray, EndPointer());
341  }
342  inline iterator end() const {
343  const void *const *End = EndPointer();
344  return iterator(End, End);
345  }
346 };
347 
352 template<class PtrType, unsigned SmallSize>
353 class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
354  // In small mode SmallPtrSet uses linear search for the elements, so it is
355  // not a good idea to choose this value too high. You may consider using a
356  // DenseSet<> instead if you expect many elements in the set.
357  static_assert(SmallSize <= 32, "SmallSize should be small");
358 
360 
361  // Make sure that SmallSize is a power of two, round up if not.
362  enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
364  const void *SmallStorage[SmallSizePowTwo];
365 
366 public:
367  SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
368  SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
369  SmallPtrSet(SmallPtrSet &&that)
370  : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
371 
372  template<typename It>
373  SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
374  this->insert(I, E);
375  }
376 
378  operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
379  if (&RHS != this)
380  this->CopyFrom(RHS);
381  return *this;
382  }
383 
385  operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
386  if (&RHS != this)
387  this->MoveFrom(SmallSizePowTwo, std::move(RHS));
388  return *this;
389  }
390 
394  }
395 };
396 }
397 
398 namespace std {
400  template<class T, unsigned N>
401  inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
402  LHS.swap(RHS);
403  }
404 }
405 
406 #endif
Definition: Path.inc:27
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&#39;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 &#39;small mode&#39;.
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<>&#39;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