File: | lib/Support/SmallPtrSet.cpp |
Warning: | line 110, column 3 Null pointer passed as an argument to a 'nonnull' parameter |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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!")(static_cast <bool> (!isSmall() && "Can't shrink a small set!" ) ? void (0) : __assert_fail ("!isSmall() && \"Can't shrink a small set!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 26, __extension__ __PRETTY_FUNCTION__)); | |||
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)__builtin_expect((bool)(size() * 4 >= CurArraySize * 3), false )) { | |||
| ||||
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)__builtin_expect((bool)(CurArraySize - NumNonEmpty < CurArraySize / 8), false)) { | |||
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 | incrementEpoch(); | |||
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())__builtin_expect((bool)(Array[Bucket] == getEmptyMarker()), true )) | |||
79 | return Tombstone ? Tombstone : Array+Bucket; | |||
80 | ||||
81 | // Found Ptr's bucket? | |||
82 | if (LLVM_LIKELY(Array[Bucket] == Ptr)__builtin_expect((bool)(Array[Bucket] == Ptr), true)) | |||
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 | ||||
126 | SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, | |||
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()) { | |||
132 | CurArray = SmallArray; | |||
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 | ||||
144 | SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, | |||
145 | unsigned SmallSize, | |||
146 | SmallPtrSetImplBase &&that) { | |||
147 | SmallArray = SmallStorage; | |||
148 | MoveHelper(SmallSize, std::move(that)); | |||
149 | } | |||
150 | ||||
151 | void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) { | |||
152 | assert(&RHS != this && "Self-copy should be handled by the caller.")(static_cast <bool> (&RHS != this && "Self-copy should be handled by the caller." ) ? void (0) : __assert_fail ("&RHS != this && \"Self-copy should be handled by the caller.\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 152, __extension__ __PRETTY_FUNCTION__)); | |||
153 | ||||
154 | if (isSmall() && RHS.isSmall()) | |||
155 | assert(CurArraySize == RHS.CurArraySize &&(static_cast <bool> (CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes") ? void (0) : __assert_fail ("CurArraySize == RHS.CurArraySize && \"Cannot assign sets with different small sizes\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 156, __extension__ __PRETTY_FUNCTION__)) | |||
156 | "Cannot assign sets with different small sizes")(static_cast <bool> (CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes") ? void (0) : __assert_fail ("CurArraySize == RHS.CurArraySize && \"Cannot assign sets with different small sizes\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 156, __extension__ __PRETTY_FUNCTION__)); | |||
157 | ||||
158 | // If we're becoming small, prepare to insert into our stack space | |||
159 | if (RHS.isSmall()) { | |||
160 | if (!isSmall()) | |||
161 | free(CurArray); | |||
162 | CurArray = SmallArray; | |||
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 | |||
183 | CurArraySize = RHS.CurArraySize; | |||
184 | ||||
185 | // Copy over the contents from the other set | |||
186 | std::copy(RHS.CurArray, RHS.EndPointer(), CurArray); | |||
187 | ||||
188 | NumNonEmpty = RHS.NumNonEmpty; | |||
189 | NumTombstones = RHS.NumTombstones; | |||
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.")(static_cast <bool> (&RHS != this && "Self-move should be handled by the caller." ) ? void (0) : __assert_fail ("&RHS != this && \"Self-move should be handled by the caller.\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 201, __extension__ __PRETTY_FUNCTION__)); | |||
202 | ||||
203 | if (RHS.isSmall()) { | |||
204 | // Copy a small RHS rather than moving. | |||
205 | CurArray = SmallArray; | |||
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. | |||
213 | CurArraySize = RHS.CurArraySize; | |||
214 | NumNonEmpty = RHS.NumNonEmpty; | |||
215 | NumTombstones = RHS.NumTombstones; | |||
216 | ||||
217 | // Make the RHS small and empty. | |||
218 | RHS.CurArraySize = SmallSize; | |||
219 | assert(RHS.CurArray == RHS.SmallArray)(static_cast <bool> (RHS.CurArray == RHS.SmallArray) ? void (0) : __assert_fail ("RHS.CurArray == RHS.SmallArray", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 219, __extension__ __PRETTY_FUNCTION__)); | |||
220 | RHS.NumNonEmpty = 0; | |||
221 | RHS.NumTombstones = 0; | |||
222 | } | |||
223 | ||||
224 | void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) { | |||
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); | |||
232 | std::swap(this->NumTombstones, RHS.NumTombstones); | |||
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)(static_cast <bool> (RHS.CurArray == RHS.SmallArray) ? void (0) : __assert_fail ("RHS.CurArray == RHS.SmallArray", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 241, __extension__ __PRETTY_FUNCTION__)); | |||
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); | |||
245 | std::swap(this->NumTombstones, RHS.NumTombstones); | |||
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)(static_cast <bool> (this->CurArray == this->SmallArray ) ? void (0) : __assert_fail ("this->CurArray == this->SmallArray" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 254, __extension__ __PRETTY_FUNCTION__)); | |||
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())(static_cast <bool> (this->isSmall() && RHS. isSmall()) ? void (0) : __assert_fail ("this->isSmall() && RHS.isSmall()" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 266, __extension__ __PRETTY_FUNCTION__)); | |||
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)(static_cast <bool> (this->CurArraySize == RHS.CurArraySize ) ? void (0) : __assert_fail ("this->CurArraySize == RHS.CurArraySize" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/SmallPtrSet.cpp" , 278, __extension__ __PRETTY_FUNCTION__)); | |||
279 | std::swap(this->NumNonEmpty, RHS.NumNonEmpty); | |||
280 | std::swap(this->NumTombstones, RHS.NumTombstones); | |||
281 | } |