LLVM  6.0.0svn
SmallPtrSet.cpp
Go to the documentation of this file.
1 //===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===//
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 implements the SmallPtrSet class. See SmallPtrSet.h for an
11 // overview of the algorithm.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/DenseMapInfo.h"
19 #include <algorithm>
20 #include <cassert>
21 #include <cstdlib>
22 
23 using namespace llvm;
24 
25 void SmallPtrSetImplBase::shrink_and_clear() {
26  assert(!isSmall() && "Can't shrink a small set!");
27  free(CurArray);
28 
29  // Reduce the number of buckets.
30  unsigned Size = size();
31  CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32;
33 
34  // Install the new array. Clear all the buckets to empty.
35  CurArray = (const void**)malloc(sizeof(void*) * CurArraySize);
36  if (CurArray == nullptr)
37  report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
38 
39  memset(CurArray, -1, CurArraySize*sizeof(void*));
40 }
41 
42 std::pair<const void *const *, bool>
43 SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {
44  if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) {
45  // If more than 3/4 of the array is full, grow.
46  Grow(CurArraySize < 64 ? 128 : CurArraySize * 2);
47  } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) {
48  // If fewer of 1/8 of the array is empty (meaning that many are filled with
49  // tombstones), rehash.
50  Grow(CurArraySize);
51  }
52 
53  // Okay, we know we have space. Find a hash bucket.
54  const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
55  if (*Bucket == Ptr)
56  return std::make_pair(Bucket, false); // Already inserted, good.
57 
58  // Otherwise, insert it!
59  if (*Bucket == getTombstoneMarker())
60  --NumTombstones;
61  else
62  ++NumNonEmpty; // Track density.
63  *Bucket = Ptr;
65  return std::make_pair(Bucket, true);
66 }
67 
68 const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
69  unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
70  unsigned ArraySize = CurArraySize;
71  unsigned ProbeAmt = 1;
72  const void *const *Array = CurArray;
73  const void *const *Tombstone = nullptr;
74  while (true) {
75  // If we found an empty bucket, the pointer doesn't exist in the set.
76  // Return a tombstone if we've seen one so far, or the empty bucket if
77  // not.
78  if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker()))
79  return Tombstone ? Tombstone : Array+Bucket;
80 
81  // Found Ptr's bucket?
82  if (LLVM_LIKELY(Array[Bucket] == Ptr))
83  return Array+Bucket;
84 
85  // If this is a tombstone, remember it. If Ptr ends up not in the set, we
86  // prefer to return it than something that would require more probing.
87  if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
88  Tombstone = Array+Bucket; // Remember the first tombstone found.
89 
90  // It's a hash collision or a tombstone. Reprobe.
91  Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
92  }
93 }
94 
95 /// Grow - Allocate a larger backing store for the buckets and move it over.
96 ///
97 void SmallPtrSetImplBase::Grow(unsigned NewSize) {
98  const void **OldBuckets = CurArray;
99  const void **OldEnd = EndPointer();
100  bool WasSmall = isSmall();
101 
102  // Install the new array. Clear all the buckets to empty.
103  const void **NewBuckets = (const void**) malloc(sizeof(void*) * NewSize);
104  if (NewBuckets == nullptr)
105  report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
106 
107  // Reset member only if memory was allocated successfully
108  CurArray = NewBuckets;
109  CurArraySize = NewSize;
110  memset(CurArray, -1, NewSize*sizeof(void*));
111 
112  // Copy over all valid entries.
113  for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {
114  // Copy over the element if it is valid.
115  const void *Elt = *BucketPtr;
116  if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
117  *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
118  }
119 
120  if (!WasSmall)
121  free(OldBuckets);
122  NumNonEmpty -= NumTombstones;
123  NumTombstones = 0;
124 }
125 
127  const SmallPtrSetImplBase &that) {
128  SmallArray = SmallStorage;
129 
130  // If we're becoming small, prepare to insert into our stack space
131  if (that.isSmall()) {
133  // Otherwise, allocate new heap space (unless we were the same size)
134  } else {
135  CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize);
136  if (CurArray == nullptr)
137  report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
138  }
139 
140  // Copy over the that array.
141  CopyHelper(that);
142 }
143 
145  unsigned SmallSize,
146  SmallPtrSetImplBase &&that) {
147  SmallArray = SmallStorage;
148  MoveHelper(SmallSize, std::move(that));
149 }
150 
152  assert(&RHS != this && "Self-copy should be handled by the caller.");
153 
154  if (isSmall() && RHS.isSmall())
156  "Cannot assign sets with different small sizes");
157 
158  // If we're becoming small, prepare to insert into our stack space
159  if (RHS.isSmall()) {
160  if (!isSmall())
161  free(CurArray);
163  // Otherwise, allocate new heap space (unless we were the same size)
164  } else if (CurArraySize != RHS.CurArraySize) {
165  if (isSmall())
166  CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize);
167  else {
168  const void **T = (const void**)realloc(CurArray,
169  sizeof(void*) * RHS.CurArraySize);
170  if (!T)
171  free(CurArray);
172  CurArray = T;
173  }
174  if (CurArray == nullptr)
175  report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
176  }
177 
178  CopyHelper(RHS);
179 }
180 
181 void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
182  // Copy over the new array size
184 
185  // Copy over the contents from the other set
186  std::copy(RHS.CurArray, RHS.EndPointer(), CurArray);
187 
188  NumNonEmpty = RHS.NumNonEmpty;
190 }
191 
192 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
193  SmallPtrSetImplBase &&RHS) {
194  if (!isSmall())
195  free(CurArray);
196  MoveHelper(SmallSize, std::move(RHS));
197 }
198 
199 void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
200  SmallPtrSetImplBase &&RHS) {
201  assert(&RHS != this && "Self-move should be handled by the caller.");
202 
203  if (RHS.isSmall()) {
204  // Copy a small RHS rather than moving.
206  std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray);
207  } else {
208  CurArray = RHS.CurArray;
209  RHS.CurArray = RHS.SmallArray;
210  }
211 
212  // Copy the rest of the trivial members.
214  NumNonEmpty = RHS.NumNonEmpty;
216 
217  // Make the RHS small and empty.
218  RHS.CurArraySize = SmallSize;
219  assert(RHS.CurArray == RHS.SmallArray);
220  RHS.NumNonEmpty = 0;
221  RHS.NumTombstones = 0;
222 }
223 
225  if (this == &RHS) return;
226 
227  // We can only avoid copying elements if neither set is small.
228  if (!this->isSmall() && !RHS.isSmall()) {
229  std::swap(this->CurArray, RHS.CurArray);
230  std::swap(this->CurArraySize, RHS.CurArraySize);
231  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
233  return;
234  }
235 
236  // FIXME: From here on we assume that both sets have the same small size.
237 
238  // If only RHS is small, copy the small elements into LHS and move the pointer
239  // from LHS to RHS.
240  if (!this->isSmall() && RHS.isSmall()) {
241  assert(RHS.CurArray == RHS.SmallArray);
242  std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray);
243  std::swap(RHS.CurArraySize, this->CurArraySize);
244  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
246  RHS.CurArray = this->CurArray;
247  this->CurArray = this->SmallArray;
248  return;
249  }
250 
251  // If only LHS is small, copy the small elements into RHS and move the pointer
252  // from RHS to LHS.
253  if (this->isSmall() && !RHS.isSmall()) {
254  assert(this->CurArray == this->SmallArray);
255  std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,
256  RHS.SmallArray);
257  std::swap(RHS.CurArraySize, this->CurArraySize);
258  std::swap(RHS.NumNonEmpty, this->NumNonEmpty);
259  std::swap(RHS.NumTombstones, this->NumTombstones);
260  this->CurArray = RHS.CurArray;
261  RHS.CurArray = RHS.SmallArray;
262  return;
263  }
264 
265  // Both a small, just swap the small elements.
266  assert(this->isSmall() && RHS.isSmall());
267  unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty);
268  std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty,
269  RHS.SmallArray);
270  if (this->NumNonEmpty > MinNonEmpty) {
271  std::copy(this->SmallArray + MinNonEmpty,
272  this->SmallArray + this->NumNonEmpty,
273  RHS.SmallArray + MinNonEmpty);
274  } else {
275  std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty,
276  this->SmallArray + MinNonEmpty);
277  }
278  assert(this->CurArraySize == RHS.CurArraySize);
279  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
281 }
static void * getTombstoneMarker()
Definition: SmallPtrSet.h:111
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:544
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:176
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:175
void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS)
unsigned NumNonEmpty
Number of elements in CurArray that contain a value or are a tombstone.
Definition: SmallPtrSet.h:65
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
void incrementEpoch()
Calling incrementEpoch invalidates all handles pointing into the calling instance.
Definition: EpochTracker.h:45
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
static void * getEmptyMarker()
Definition: SmallPtrSet.h:113
#define T
const void ** EndPointer() const
Definition: SmallPtrSet.h:119
void CopyFrom(const SmallPtrSetImplBase &RHS)
size_type size() const
Definition: SmallPtrSet.h:93
void report_bad_alloc_error(const char *Reason, bool GenCrashDiag=true)
Reports a bad alloc error, calling any user defined bad alloc error handler.
const void ** SmallArray
SmallArray - Points to a fixed size set of buckets, used in &#39;small mode&#39;.
Definition: SmallPtrSet.h:55
SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.