WPILibC++  unspecified
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Pages
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 <cstring>
23 #include <iterator>
24 #include <utility>
25 
26 namespace llvm {
27 
28 class SmallPtrSetIteratorImpl;
29 
49  friend class SmallPtrSetIteratorImpl;
50 protected:
52  const void **SmallArray;
55  const void **CurArray;
57  unsigned CurArraySize;
58 
59  // If small, this is # elts allocated consecutively
60  unsigned NumElements;
61  unsigned NumTombstones;
62 
63  // Helpers to copy and move construct a SmallPtrSet.
64  SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that);
65  SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
66  SmallPtrSetImplBase &&that);
67  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) :
68  SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) {
69  assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
70  "Initial size must be a power of two!");
71  clear();
72  }
74 
75 public:
76  typedef unsigned size_type;
77  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; }
78  size_type size() const { return NumElements; }
79 
80  void clear() {
81  // If the capacity of the array is huge, and the # elements used is small,
82  // shrink the array.
83  if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
84  return shrink_and_clear();
85 
86  // Fill the array with empty markers.
87  memset(CurArray, -1, CurArraySize*sizeof(void*));
88  NumElements = 0;
89  NumTombstones = 0;
90  }
91 
92 protected:
93  static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
94  static void *getEmptyMarker() {
95  // Note that -1 is chosen to make clear() efficiently implementable with
96  // memset and because it's not a valid pointer value.
97  return reinterpret_cast<void*>(-1);
98  }
99 
103  std::pair<const void *const *, bool> insert_imp(const void *Ptr);
104 
109  bool erase_imp(const void * Ptr);
110 
111  bool count_imp(const void * Ptr) const {
112  if (isSmall()) {
113  // Linear search for the item.
114  for (const void *const *APtr = SmallArray,
115  *const *E = SmallArray+NumElements; APtr != E; ++APtr)
116  if (*APtr == Ptr)
117  return true;
118  return false;
119  }
120 
121  // Big set case.
122  return *FindBucketFor(Ptr) == Ptr;
123  }
124 
125 private:
126  bool isSmall() const { return CurArray == SmallArray; }
127 
128  const void * const *FindBucketFor(const void *Ptr) const;
129  void shrink_and_clear();
130 
132  void Grow(unsigned NewSize);
133 
134  void operator=(const SmallPtrSetImplBase &RHS) = delete;
135 protected:
138  void swap(SmallPtrSetImplBase &RHS);
139 
140  void CopyFrom(const SmallPtrSetImplBase &RHS);
141  void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
142 };
143 
147 protected:
148  const void *const *Bucket;
149  const void *const *End;
150 public:
151  explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
152  : Bucket(BP), End(E) {
154  }
155 
156  bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
157  return Bucket == RHS.Bucket;
158  }
159  bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
160  return Bucket != RHS.Bucket;
161  }
162 
163 protected:
168  assert(Bucket <= End);
169  while (Bucket != End &&
170  (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
171  *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
172  ++Bucket;
173  }
174 };
175 
177 template<typename PtrTy>
180 
181 public:
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;
187 
188  explicit SmallPtrSetIterator(const void *const *BP, const void *const *E)
189  : SmallPtrSetIteratorImpl(BP, E) {}
190 
191  // Most methods provided by baseclass.
192 
193  const PtrTy operator*() const {
194  assert(Bucket < End);
195  return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
196  }
197 
198  inline SmallPtrSetIterator& operator++() { // Preincrement
199  ++Bucket;
201  return *this;
202  }
203 
204  SmallPtrSetIterator operator++(int) { // Postincrement
205  SmallPtrSetIterator tmp = *this; ++*this; return tmp;
206  }
207 };
208 
211 template<unsigned N>
213 
216 template<unsigned N, bool isPowerTwo>
218  enum { Val = N };
219 };
220 template<unsigned N>
221 struct RoundUpToPowerOfTwoH<N, false> {
222  enum {
223  // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
224  // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
225  Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
226  };
227 };
228 
229 template<unsigned N>
230 struct RoundUpToPowerOfTwo {
231  enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
232 };
233 
234 
240 template <typename PtrType>
243 
244  SmallPtrSetImpl(const SmallPtrSetImpl&) = delete;
245 protected:
246  // Constructors that forward to the base.
247  SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
248  : SmallPtrSetImplBase(SmallStorage, that) {}
249  SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
250  SmallPtrSetImpl &&that)
251  : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
252  explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize)
253  : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
254 
255 public:
258 
263  std::pair<iterator, bool> insert(PtrType Ptr) {
264  auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
265  return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second);
266  }
267 
270  bool erase(PtrType Ptr) {
271  return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
272  }
273 
275  size_type count(PtrType Ptr) const {
276  return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
277  }
278 
279  template <typename IterT>
280  void insert(IterT I, IterT E) {
281  for (; I != E; ++I)
282  insert(*I);
283  }
284 
285  inline iterator begin() const {
286  return iterator(CurArray, CurArray+CurArraySize);
287  }
288  inline iterator end() const {
289  return iterator(CurArray+CurArraySize, CurArray+CurArraySize);
290  }
291 };
292 
297 template<class PtrType, unsigned SmallSize>
298 class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
300 
301  // Make sure that SmallSize is a power of two, round up if not.
302  enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
304  const void *SmallStorage[SmallSizePowTwo];
305 public:
306  SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
307  SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
308  SmallPtrSet(SmallPtrSet &&that)
309  : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
310 
311  template<typename It>
312  SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
313  this->insert(I, E);
314  }
315 
317  operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
318  if (&RHS != this)
319  this->CopyFrom(RHS);
320  return *this;
321  }
322 
324  operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
325  if (&RHS != this)
326  this->MoveFrom(SmallSizePowTwo, std::move(RHS));
327  return *this;
328  }
329 
333  }
334 };
335 
336 } // namespace llvm
337 
338 namespace std {
340  template<class T, unsigned N>
341  inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
342  LHS.swap(RHS);
343  }
344 }
345 
346 #endif
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