Line data Source code
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 358126 : void SmallPtrSetImplBase::shrink_and_clear() {
26 : assert(!isSmall() && "Can't shrink a small set!");
27 358126 : free(CurArray);
28 :
29 : // Reduce the number of buckets.
30 358126 : unsigned Size = size();
31 358126 : CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32;
32 358126 : NumNonEmpty = NumTombstones = 0;
33 :
34 : // Install the new array. Clear all the buckets to empty.
35 358126 : CurArray = (const void**)safe_malloc(sizeof(void*) * CurArraySize);
36 :
37 358126 : memset(CurArray, -1, CurArraySize*sizeof(void*));
38 358126 : }
39 :
40 : std::pair<const void *const *, bool>
41 319961347 : SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {
42 639922694 : if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) {
43 : // If more than 3/4 of the array is full, grow.
44 5395912 : Grow(CurArraySize < 64 ? 128 : CurArraySize * 2);
45 314565435 : } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) {
46 : // If fewer of 1/8 of the array is empty (meaning that many are filled with
47 : // tombstones), rehash.
48 6473 : Grow(CurArraySize);
49 : }
50 :
51 : // Okay, we know we have space. Find a hash bucket.
52 319961347 : const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
53 319961347 : if (*Bucket == Ptr)
54 119344365 : return std::make_pair(Bucket, false); // Already inserted, good.
55 :
56 : // Otherwise, insert it!
57 200616982 : if (*Bucket == getTombstoneMarker())
58 3304098 : --NumTombstones;
59 : else
60 197312884 : ++NumNonEmpty; // Track density.
61 200616982 : *Bucket = Ptr;
62 : incrementEpoch();
63 200616982 : return std::make_pair(Bucket, true);
64 : }
65 :
66 873298029 : const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
67 873298029 : unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
68 : unsigned ArraySize = CurArraySize;
69 : unsigned ProbeAmt = 1;
70 873298029 : const void *const *Array = CurArray;
71 : const void *const *Tombstone = nullptr;
72 : while (true) {
73 : // If we found an empty bucket, the pointer doesn't exist in the set.
74 : // Return a tombstone if we've seen one so far, or the empty bucket if
75 : // not.
76 1244500553 : if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker()))
77 1082571205 : return Tombstone ? Tombstone : Array+Bucket;
78 :
79 : // Found Ptr's bucket?
80 699785150 : if (LLVM_LIKELY(Array[Bucket] == Ptr))
81 328582626 : return Array+Bucket;
82 :
83 : // If this is a tombstone, remember it. If Ptr ends up not in the set, we
84 : // prefer to return it than something that would require more probing.
85 371202524 : if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
86 : Tombstone = Array+Bucket; // Remember the first tombstone found.
87 :
88 : // It's a hash collision or a tombstone. Reprobe.
89 371202524 : Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
90 : }
91 : }
92 :
93 : /// Grow - Allocate a larger backing store for the buckets and move it over.
94 : ///
95 5402385 : void SmallPtrSetImplBase::Grow(unsigned NewSize) {
96 5402385 : const void **OldBuckets = CurArray;
97 : const void **OldEnd = EndPointer();
98 : bool WasSmall = isSmall();
99 :
100 : // Install the new array. Clear all the buckets to empty.
101 5402385 : const void **NewBuckets = (const void**) safe_malloc(sizeof(void*) * NewSize);
102 :
103 : // Reset member only if memory was allocated successfully
104 5402385 : CurArray = NewBuckets;
105 5402385 : CurArraySize = NewSize;
106 5402385 : memset(CurArray, -1, NewSize*sizeof(void*));
107 :
108 : // Copy over all valid entries.
109 205651122 : for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {
110 : // Copy over the element if it is valid.
111 200248737 : const void *Elt = *BucketPtr;
112 200248737 : if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
113 171449701 : *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
114 : }
115 :
116 5402385 : if (!WasSmall)
117 630207 : free(OldBuckets);
118 5402385 : NumNonEmpty -= NumTombstones;
119 5402385 : NumTombstones = 0;
120 5402385 : }
121 :
122 29825495 : SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
123 29825495 : const SmallPtrSetImplBase &that) {
124 29825495 : SmallArray = SmallStorage;
125 :
126 : // If we're becoming small, prepare to insert into our stack space
127 29825495 : if (that.isSmall()) {
128 29621599 : CurArray = SmallArray;
129 : // Otherwise, allocate new heap space (unless we were the same size)
130 : } else {
131 203896 : CurArray = (const void**)safe_malloc(sizeof(void*) * that.CurArraySize);
132 : }
133 :
134 : // Copy over the that array.
135 29825495 : CopyHelper(that);
136 29825498 : }
137 :
138 38690418 : SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
139 : unsigned SmallSize,
140 38690418 : SmallPtrSetImplBase &&that) {
141 38690418 : SmallArray = SmallStorage;
142 38690418 : MoveHelper(SmallSize, std::move(that));
143 38690418 : }
144 :
145 374758 : void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) {
146 : assert(&RHS != this && "Self-copy should be handled by the caller.");
147 :
148 374758 : if (isSmall() && RHS.isSmall())
149 : assert(CurArraySize == RHS.CurArraySize &&
150 : "Cannot assign sets with different small sizes");
151 :
152 : // If we're becoming small, prepare to insert into our stack space
153 374758 : if (RHS.isSmall()) {
154 374720 : if (!isSmall())
155 12 : free(CurArray);
156 374720 : CurArray = SmallArray;
157 : // Otherwise, allocate new heap space (unless we were the same size)
158 38 : } else if (CurArraySize != RHS.CurArraySize) {
159 38 : if (isSmall())
160 36 : CurArray = (const void**)safe_malloc(sizeof(void*) * RHS.CurArraySize);
161 : else {
162 2 : const void **T = (const void**)safe_realloc(CurArray,
163 2 : sizeof(void*) * RHS.CurArraySize);
164 2 : CurArray = T;
165 : }
166 : }
167 :
168 374758 : CopyHelper(RHS);
169 374758 : }
170 :
171 30200255 : void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
172 : // Copy over the new array size
173 30200255 : CurArraySize = RHS.CurArraySize;
174 :
175 : // Copy over the contents from the other set
176 30200255 : std::copy(RHS.CurArray, RHS.EndPointer(), CurArray);
177 :
178 30200255 : NumNonEmpty = RHS.NumNonEmpty;
179 30200255 : NumTombstones = RHS.NumTombstones;
180 30200255 : }
181 :
182 58012 : void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
183 : SmallPtrSetImplBase &&RHS) {
184 58012 : if (!isSmall())
185 0 : free(CurArray);
186 58012 : MoveHelper(SmallSize, std::move(RHS));
187 58012 : }
188 :
189 38748435 : void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
190 : SmallPtrSetImplBase &&RHS) {
191 : assert(&RHS != this && "Self-move should be handled by the caller.");
192 :
193 38748435 : if (RHS.isSmall()) {
194 : // Copy a small RHS rather than moving.
195 38472334 : CurArray = SmallArray;
196 38472334 : std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray);
197 : } else {
198 276101 : CurArray = RHS.CurArray;
199 276101 : RHS.CurArray = RHS.SmallArray;
200 : }
201 :
202 : // Copy the rest of the trivial members.
203 38748435 : CurArraySize = RHS.CurArraySize;
204 38748435 : NumNonEmpty = RHS.NumNonEmpty;
205 38748435 : NumTombstones = RHS.NumTombstones;
206 :
207 : // Make the RHS small and empty.
208 38748435 : RHS.CurArraySize = SmallSize;
209 : assert(RHS.CurArray == RHS.SmallArray);
210 38748435 : RHS.NumNonEmpty = 0;
211 38748435 : RHS.NumTombstones = 0;
212 38748435 : }
213 :
214 311388551 : void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
215 311388551 : if (this == &RHS) return;
216 :
217 : // We can only avoid copying elements if neither set is small.
218 311388551 : if (!this->isSmall() && !RHS.isSmall()) {
219 : std::swap(this->CurArray, RHS.CurArray);
220 : std::swap(this->CurArraySize, RHS.CurArraySize);
221 : std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
222 : std::swap(this->NumTombstones, RHS.NumTombstones);
223 1 : return;
224 : }
225 :
226 : // FIXME: From here on we assume that both sets have the same small size.
227 :
228 : // If only RHS is small, copy the small elements into LHS and move the pointer
229 : // from LHS to RHS.
230 311388550 : if (!this->isSmall() && RHS.isSmall()) {
231 : assert(RHS.CurArray == RHS.SmallArray);
232 45062 : std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray);
233 : std::swap(RHS.CurArraySize, this->CurArraySize);
234 : std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
235 : std::swap(this->NumTombstones, RHS.NumTombstones);
236 45062 : RHS.CurArray = this->CurArray;
237 45062 : this->CurArray = this->SmallArray;
238 45062 : return;
239 : }
240 :
241 : // If only LHS is small, copy the small elements into RHS and move the pointer
242 : // from RHS to LHS.
243 311343488 : if (this->isSmall() && !RHS.isSmall()) {
244 : assert(this->CurArray == this->SmallArray);
245 11639 : std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,
246 : RHS.SmallArray);
247 : std::swap(RHS.CurArraySize, this->CurArraySize);
248 : std::swap(RHS.NumNonEmpty, this->NumNonEmpty);
249 : std::swap(RHS.NumTombstones, this->NumTombstones);
250 11639 : this->CurArray = RHS.CurArray;
251 11639 : RHS.CurArray = RHS.SmallArray;
252 11639 : return;
253 : }
254 :
255 : // Both a small, just swap the small elements.
256 : assert(this->isSmall() && RHS.isSmall());
257 311331849 : unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty);
258 311331849 : std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty,
259 : RHS.SmallArray);
260 311331849 : if (this->NumNonEmpty > MinNonEmpty) {
261 5801660 : std::copy(this->SmallArray + MinNonEmpty,
262 2900830 : this->SmallArray + this->NumNonEmpty,
263 2900830 : RHS.SmallArray + MinNonEmpty);
264 : } else {
265 308431019 : std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty,
266 308431019 : this->SmallArray + MinNonEmpty);
267 : }
268 : assert(this->CurArraySize == RHS.CurArraySize);
269 : std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
270 : std::swap(this->NumTombstones, RHS.NumTombstones);
271 : }
|
