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"
17 #include "llvm/Support/MathExtras.h"
18 #include "llvm/Support/ErrorHandling.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;
32   NumNonEmpty = NumTombstones = 0;
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;
64   return std::make_pair(Bucket, true);
65 }
66 
67 const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
68   unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
69   unsigned ArraySize = CurArraySize;
70   unsigned ProbeAmt = 1;
71   const void *const *Array = CurArray;
72   const void *const *Tombstone = nullptr;
73   while (true) {
74     // If we found an empty bucket, the pointer doesn't exist in the set.
75     // Return a tombstone if we've seen one so far, or the empty bucket if
76     // not.
77     if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker()))
78       return Tombstone ? Tombstone : Array+Bucket;
79 
80     // Found Ptr's bucket?
81     if (LLVM_LIKELY(Array[Bucket] == Ptr))
82       return Array+Bucket;
83 
84     // If this is a tombstone, remember it.  If Ptr ends up not in the set, we
85     // prefer to return it than something that would require more probing.
86     if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
87       Tombstone = Array+Bucket;  // Remember the first tombstone found.
88 
89     // It's a hash collision or a tombstone. Reprobe.
90     Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
91   }
92 }
93 
94 /// Grow - Allocate a larger backing store for the buckets and move it over.
95 ///
96 void SmallPtrSetImplBase::Grow(unsigned NewSize) {
97   const void **OldBuckets = CurArray;
98   const void **OldEnd = EndPointer();
99   bool WasSmall = isSmall();
100 
101   // Install the new array.  Clear all the buckets to empty.
102   const void **NewBuckets = (const void**) malloc(sizeof(void*) * NewSize);
103   if (NewBuckets == nullptr)
104     report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
105 
106   // Reset member only if memory was allocated successfully
107   CurArray = NewBuckets;
108   CurArraySize = NewSize;
109   memset(CurArray, -1, NewSize*sizeof(void*));
110 
111   // Copy over all valid entries.
112   for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {
113     // Copy over the element if it is valid.
114     const void *Elt = *BucketPtr;
115     if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
116       *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
117   }
118 
119   if (!WasSmall)
120     free(OldBuckets);
121   NumNonEmpty -= NumTombstones;
122   NumTombstones = 0;
123 }
124 
125 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
126                                          const SmallPtrSetImplBase &that) {
127   SmallArray = SmallStorage;
128 
129   // If we're becoming small, prepare to insert into our stack space
130   if (that.isSmall()) {
131     CurArray = SmallArray;
132   // Otherwise, allocate new heap space (unless we were the same size)
133   } else {
134     CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize);
135     if (CurArray == nullptr)
136       report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
137   }
138 
139   // Copy over the that array.
140   CopyHelper(that);
141 }
142 
143 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
144                                          unsigned SmallSize,
145                                          SmallPtrSetImplBase &&that) {
146   SmallArray = SmallStorage;
147   MoveHelper(SmallSize, std::move(that));
148 }
149 
150 void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) {
151   assert(&RHS != this && "Self-copy should be handled by the caller.");
152 
153   if (isSmall() && RHS.isSmall())
154     assert(CurArraySize == RHS.CurArraySize &&
155            "Cannot assign sets with different small sizes");
156 
157   // If we're becoming small, prepare to insert into our stack space
158   if (RHS.isSmall()) {
159     if (!isSmall())
160       free(CurArray);
161     CurArray = SmallArray;
162   // Otherwise, allocate new heap space (unless we were the same size)
163   } else if (CurArraySize != RHS.CurArraySize) {
164     if (isSmall())
165       CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize);
166     else {
167       const void **T = (const void**)realloc(CurArray,
168                                              sizeof(void*) * RHS.CurArraySize);
169       if (!T)
170         free(CurArray);
171       CurArray = T;
172     }
173     if (CurArray == nullptr)
174       report_bad_alloc_error("Allocation of SmallPtrSet bucket array failed.");
175   }
176 
177   CopyHelper(RHS);
178 }
179 
180 void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
181   // Copy over the new array size
182   CurArraySize = RHS.CurArraySize;
183 
184   // Copy over the contents from the other set
185   std::copy(RHS.CurArray, RHS.EndPointer(), CurArray);
186 
187   NumNonEmpty = RHS.NumNonEmpty;
188   NumTombstones = RHS.NumTombstones;
189 }
190 
191 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
192                                    SmallPtrSetImplBase &&RHS) {
193   if (!isSmall())
194     free(CurArray);
195   MoveHelper(SmallSize, std::move(RHS));
196 }
197 
198 void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
199                                      SmallPtrSetImplBase &&RHS) {
200   assert(&RHS != this && "Self-move should be handled by the caller.");
201 
202   if (RHS.isSmall()) {
203     // Copy a small RHS rather than moving.
204     CurArray = SmallArray;
205     std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray);
206   } else {
207     CurArray = RHS.CurArray;
208     RHS.CurArray = RHS.SmallArray;
209   }
210 
211   // Copy the rest of the trivial members.
212   CurArraySize = RHS.CurArraySize;
213   NumNonEmpty = RHS.NumNonEmpty;
214   NumTombstones = RHS.NumTombstones;
215 
216   // Make the RHS small and empty.
217   RHS.CurArraySize = SmallSize;
218   assert(RHS.CurArray == RHS.SmallArray);
219   RHS.NumNonEmpty = 0;
220   RHS.NumTombstones = 0;
221 }
222 
223 void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
224   if (this == &RHS) return;
225 
226   // We can only avoid copying elements if neither set is small.
227   if (!this->isSmall() && !RHS.isSmall()) {
228     std::swap(this->CurArray, RHS.CurArray);
229     std::swap(this->CurArraySize, RHS.CurArraySize);
230     std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
231     std::swap(this->NumTombstones, RHS.NumTombstones);
232     return;
233   }
234 
235   // FIXME: From here on we assume that both sets have the same small size.
236 
237   // If only RHS is small, copy the small elements into LHS and move the pointer
238   // from LHS to RHS.
239   if (!this->isSmall() && RHS.isSmall()) {
240     assert(RHS.CurArray == RHS.SmallArray);
241     std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray);
242     std::swap(RHS.CurArraySize, this->CurArraySize);
243     std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
244     std::swap(this->NumTombstones, RHS.NumTombstones);
245     RHS.CurArray = this->CurArray;
246     this->CurArray = this->SmallArray;
247     return;
248   }
249 
250   // If only LHS is small, copy the small elements into RHS and move the pointer
251   // from RHS to LHS.
252   if (this->isSmall() && !RHS.isSmall()) {
253     assert(this->CurArray == this->SmallArray);
254     std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,
255               RHS.SmallArray);
256     std::swap(RHS.CurArraySize, this->CurArraySize);
257     std::swap(RHS.NumNonEmpty, this->NumNonEmpty);
258     std::swap(RHS.NumTombstones, this->NumTombstones);
259     this->CurArray = RHS.CurArray;
260     RHS.CurArray = RHS.SmallArray;
261     return;
262   }
263 
264   // Both a small, just swap the small elements.
265   assert(this->isSmall() && RHS.isSmall());
266   unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty);
267   std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty,
268                    RHS.SmallArray);
269   if (this->NumNonEmpty > MinNonEmpty) {
270     std::copy(this->SmallArray + MinNonEmpty,
271               this->SmallArray + this->NumNonEmpty,
272               RHS.SmallArray + MinNonEmpty);
273   } else {
274     std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty,
275               this->SmallArray + MinNonEmpty);
276   }
277   assert(this->CurArraySize == RHS.CurArraySize);
278   std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
279   std::swap(this->NumTombstones, RHS.NumTombstones);
280 }
281