File: | lib/Support/FoldingSet.cpp |
Warning: | line 223, column 23 Array access (from variable 'Buckets') results in a null pointer dereference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- Support/FoldingSet.cpp - Uniquing Hash 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 implements a hash set that can be used to remove duplication of | |||
11 | // nodes in a graph. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "llvm/ADT/FoldingSet.h" | |||
16 | #include "llvm/ADT/Hashing.h" | |||
17 | #include "llvm/Support/Allocator.h" | |||
18 | #include "llvm/Support/ErrorHandling.h" | |||
19 | #include "llvm/Support/Host.h" | |||
20 | #include "llvm/Support/MathExtras.h" | |||
21 | #include <cassert> | |||
22 | #include <cstring> | |||
23 | using namespace llvm; | |||
24 | ||||
25 | //===----------------------------------------------------------------------===// | |||
26 | // FoldingSetNodeIDRef Implementation | |||
27 | ||||
28 | /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, | |||
29 | /// used to lookup the node in the FoldingSetBase. | |||
30 | unsigned FoldingSetNodeIDRef::ComputeHash() const { | |||
31 | return static_cast<unsigned>(hash_combine_range(Data, Data+Size)); | |||
32 | } | |||
33 | ||||
34 | bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { | |||
35 | if (Size != RHS.Size) return false; | |||
36 | return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0; | |||
37 | } | |||
38 | ||||
39 | /// Used to compare the "ordering" of two nodes as defined by the | |||
40 | /// profiled bits and their ordering defined by memcmp(). | |||
41 | bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const { | |||
42 | if (Size != RHS.Size) | |||
43 | return Size < RHS.Size; | |||
44 | return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0; | |||
45 | } | |||
46 | ||||
47 | //===----------------------------------------------------------------------===// | |||
48 | // FoldingSetNodeID Implementation | |||
49 | ||||
50 | /// Add* - Add various data types to Bit data. | |||
51 | /// | |||
52 | void FoldingSetNodeID::AddPointer(const void *Ptr) { | |||
53 | // Note: this adds pointers to the hash using sizes and endianness that | |||
54 | // depend on the host. It doesn't matter, however, because hashing on | |||
55 | // pointer values is inherently unstable. Nothing should depend on the | |||
56 | // ordering of nodes in the folding set. | |||
57 | static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long), | |||
58 | "unexpected pointer size"); | |||
59 | AddInteger(reinterpret_cast<uintptr_t>(Ptr)); | |||
60 | } | |||
61 | void FoldingSetNodeID::AddInteger(signed I) { | |||
62 | Bits.push_back(I); | |||
63 | } | |||
64 | void FoldingSetNodeID::AddInteger(unsigned I) { | |||
65 | Bits.push_back(I); | |||
66 | } | |||
67 | void FoldingSetNodeID::AddInteger(long I) { | |||
68 | AddInteger((unsigned long)I); | |||
69 | } | |||
70 | void FoldingSetNodeID::AddInteger(unsigned long I) { | |||
71 | if (sizeof(long) == sizeof(int)) | |||
72 | AddInteger(unsigned(I)); | |||
73 | else if (sizeof(long) == sizeof(long long)) { | |||
74 | AddInteger((unsigned long long)I); | |||
75 | } else { | |||
76 | llvm_unreachable("unexpected sizeof(long)")::llvm::llvm_unreachable_internal("unexpected sizeof(long)", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 76); | |||
77 | } | |||
78 | } | |||
79 | void FoldingSetNodeID::AddInteger(long long I) { | |||
80 | AddInteger((unsigned long long)I); | |||
81 | } | |||
82 | void FoldingSetNodeID::AddInteger(unsigned long long I) { | |||
83 | AddInteger(unsigned(I)); | |||
84 | AddInteger(unsigned(I >> 32)); | |||
85 | } | |||
86 | ||||
87 | void FoldingSetNodeID::AddString(StringRef String) { | |||
88 | unsigned Size = String.size(); | |||
89 | Bits.push_back(Size); | |||
90 | if (!Size) return; | |||
91 | ||||
92 | unsigned Units = Size / 4; | |||
93 | unsigned Pos = 0; | |||
94 | const unsigned *Base = (const unsigned*) String.data(); | |||
95 | ||||
96 | // If the string is aligned do a bulk transfer. | |||
97 | if (!((intptr_t)Base & 3)) { | |||
98 | Bits.append(Base, Base + Units); | |||
99 | Pos = (Units + 1) * 4; | |||
100 | } else { | |||
101 | // Otherwise do it the hard way. | |||
102 | // To be compatible with above bulk transfer, we need to take endianness | |||
103 | // into account. | |||
104 | static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost, | |||
105 | "Unexpected host endianness"); | |||
106 | if (sys::IsBigEndianHost) { | |||
107 | for (Pos += 4; Pos <= Size; Pos += 4) { | |||
108 | unsigned V = ((unsigned char)String[Pos - 4] << 24) | | |||
109 | ((unsigned char)String[Pos - 3] << 16) | | |||
110 | ((unsigned char)String[Pos - 2] << 8) | | |||
111 | (unsigned char)String[Pos - 1]; | |||
112 | Bits.push_back(V); | |||
113 | } | |||
114 | } else { // Little-endian host | |||
115 | for (Pos += 4; Pos <= Size; Pos += 4) { | |||
116 | unsigned V = ((unsigned char)String[Pos - 1] << 24) | | |||
117 | ((unsigned char)String[Pos - 2] << 16) | | |||
118 | ((unsigned char)String[Pos - 3] << 8) | | |||
119 | (unsigned char)String[Pos - 4]; | |||
120 | Bits.push_back(V); | |||
121 | } | |||
122 | } | |||
123 | } | |||
124 | ||||
125 | // With the leftover bits. | |||
126 | unsigned V = 0; | |||
127 | // Pos will have overshot size by 4 - #bytes left over. | |||
128 | // No need to take endianness into account here - this is always executed. | |||
129 | switch (Pos - Size) { | |||
130 | case 1: V = (V << 8) | (unsigned char)String[Size - 3]; LLVM_FALLTHROUGH[[clang::fallthrough]]; | |||
131 | case 2: V = (V << 8) | (unsigned char)String[Size - 2]; LLVM_FALLTHROUGH[[clang::fallthrough]]; | |||
132 | case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; | |||
133 | default: return; // Nothing left. | |||
134 | } | |||
135 | ||||
136 | Bits.push_back(V); | |||
137 | } | |||
138 | ||||
139 | // AddNodeID - Adds the Bit data of another ID to *this. | |||
140 | void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { | |||
141 | Bits.append(ID.Bits.begin(), ID.Bits.end()); | |||
142 | } | |||
143 | ||||
144 | /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to | |||
145 | /// lookup the node in the FoldingSetBase. | |||
146 | unsigned FoldingSetNodeID::ComputeHash() const { | |||
147 | return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); | |||
148 | } | |||
149 | ||||
150 | /// operator== - Used to compare two nodes to each other. | |||
151 | /// | |||
152 | bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const { | |||
153 | return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); | |||
154 | } | |||
155 | ||||
156 | /// operator== - Used to compare two nodes to each other. | |||
157 | /// | |||
158 | bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const { | |||
159 | return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS; | |||
160 | } | |||
161 | ||||
162 | /// Used to compare the "ordering" of two nodes as defined by the | |||
163 | /// profiled bits and their ordering defined by memcmp(). | |||
164 | bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const { | |||
165 | return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); | |||
166 | } | |||
167 | ||||
168 | bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const { | |||
169 | return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS; | |||
170 | } | |||
171 | ||||
172 | /// Intern - Copy this node's data to a memory region allocated from the | |||
173 | /// given allocator and return a FoldingSetNodeIDRef describing the | |||
174 | /// interned data. | |||
175 | FoldingSetNodeIDRef | |||
176 | FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { | |||
177 | unsigned *New = Allocator.Allocate<unsigned>(Bits.size()); | |||
178 | std::uninitialized_copy(Bits.begin(), Bits.end(), New); | |||
179 | return FoldingSetNodeIDRef(New, Bits.size()); | |||
180 | } | |||
181 | ||||
182 | //===----------------------------------------------------------------------===// | |||
183 | /// Helper functions for FoldingSetBase. | |||
184 | ||||
185 | /// GetNextPtr - In order to save space, each bucket is a | |||
186 | /// singly-linked-list. In order to make deletion more efficient, we make | |||
187 | /// the list circular, so we can delete a node without computing its hash. | |||
188 | /// The problem with this is that the start of the hash buckets are not | |||
189 | /// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: | |||
190 | /// use GetBucketPtr when this happens. | |||
191 | static FoldingSetBase::Node *GetNextPtr(void *NextInBucketPtr) { | |||
192 | // The low bit is set if this is the pointer back to the bucket. | |||
193 | if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) | |||
194 | return nullptr; | |||
195 | ||||
196 | return static_cast<FoldingSetBase::Node*>(NextInBucketPtr); | |||
197 | } | |||
198 | ||||
199 | ||||
200 | /// testing. | |||
201 | static void **GetBucketPtr(void *NextInBucketPtr) { | |||
202 | intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); | |||
203 | assert((Ptr & 1) && "Not a bucket pointer")(static_cast <bool> ((Ptr & 1) && "Not a bucket pointer" ) ? void (0) : __assert_fail ("(Ptr & 1) && \"Not a bucket pointer\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 203, __extension__ __PRETTY_FUNCTION__)); | |||
204 | return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); | |||
205 | } | |||
206 | ||||
207 | /// GetBucketFor - Hash the specified node ID and return the hash bucket for | |||
208 | /// the specified ID. | |||
209 | static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) { | |||
210 | // NumBuckets is always a power of 2. | |||
211 | unsigned BucketNum = Hash & (NumBuckets-1); | |||
212 | return Buckets + BucketNum; | |||
213 | } | |||
214 | ||||
215 | /// AllocateBuckets - Allocated initialized bucket memory. | |||
216 | static void **AllocateBuckets(unsigned NumBuckets) { | |||
217 | void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*))); | |||
218 | ||||
219 | if (Buckets == nullptr) | |||
220 | report_bad_alloc_error("Allocation of Buckets failed."); | |||
221 | ||||
222 | // Set the very last bucket to be a non-null "pointer". | |||
223 | Buckets[NumBuckets] = reinterpret_cast<void*>(-1); | |||
| ||||
224 | return Buckets; | |||
225 | } | |||
226 | ||||
227 | //===----------------------------------------------------------------------===// | |||
228 | // FoldingSetBase Implementation | |||
229 | ||||
230 | void FoldingSetBase::anchor() {} | |||
231 | ||||
232 | FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) { | |||
233 | assert(5 < Log2InitSize && Log2InitSize < 32 &&(static_cast <bool> (5 < Log2InitSize && Log2InitSize < 32 && "Initial hash table size out of range") ? void (0) : __assert_fail ("5 < Log2InitSize && Log2InitSize < 32 && \"Initial hash table size out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 234, __extension__ __PRETTY_FUNCTION__)) | |||
234 | "Initial hash table size out of range")(static_cast <bool> (5 < Log2InitSize && Log2InitSize < 32 && "Initial hash table size out of range") ? void (0) : __assert_fail ("5 < Log2InitSize && Log2InitSize < 32 && \"Initial hash table size out of range\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 234, __extension__ __PRETTY_FUNCTION__)); | |||
235 | NumBuckets = 1 << Log2InitSize; | |||
236 | Buckets = AllocateBuckets(NumBuckets); | |||
| ||||
237 | NumNodes = 0; | |||
238 | } | |||
239 | ||||
240 | FoldingSetBase::FoldingSetBase(FoldingSetBase &&Arg) | |||
241 | : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) { | |||
242 | Arg.Buckets = nullptr; | |||
243 | Arg.NumBuckets = 0; | |||
244 | Arg.NumNodes = 0; | |||
245 | } | |||
246 | ||||
247 | FoldingSetBase &FoldingSetBase::operator=(FoldingSetBase &&RHS) { | |||
248 | free(Buckets); // This may be null if the set is in a moved-from state. | |||
249 | Buckets = RHS.Buckets; | |||
250 | NumBuckets = RHS.NumBuckets; | |||
251 | NumNodes = RHS.NumNodes; | |||
252 | RHS.Buckets = nullptr; | |||
253 | RHS.NumBuckets = 0; | |||
254 | RHS.NumNodes = 0; | |||
255 | return *this; | |||
256 | } | |||
257 | ||||
258 | FoldingSetBase::~FoldingSetBase() { | |||
259 | free(Buckets); | |||
260 | } | |||
261 | ||||
262 | void FoldingSetBase::clear() { | |||
263 | // Set all but the last bucket to null pointers. | |||
264 | memset(Buckets, 0, NumBuckets*sizeof(void*)); | |||
265 | ||||
266 | // Set the very last bucket to be a non-null "pointer". | |||
267 | Buckets[NumBuckets] = reinterpret_cast<void*>(-1); | |||
268 | ||||
269 | // Reset the node count to zero. | |||
270 | NumNodes = 0; | |||
271 | } | |||
272 | ||||
273 | void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) { | |||
274 | assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount")(static_cast <bool> ((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount") ? void (0 ) : __assert_fail ("(NewBucketCount > NumBuckets) && \"Can't shrink a folding set with GrowBucketCount\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 274, __extension__ __PRETTY_FUNCTION__)); | |||
275 | assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!")(static_cast <bool> (isPowerOf2_32(NewBucketCount) && "Bad bucket count!") ? void (0) : __assert_fail ("isPowerOf2_32(NewBucketCount) && \"Bad bucket count!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 275, __extension__ __PRETTY_FUNCTION__)); | |||
276 | void **OldBuckets = Buckets; | |||
277 | unsigned OldNumBuckets = NumBuckets; | |||
278 | ||||
279 | // Clear out new buckets. | |||
280 | Buckets = AllocateBuckets(NewBucketCount); | |||
281 | // Set NumBuckets only if allocation of new buckets was succesful | |||
282 | NumBuckets = NewBucketCount; | |||
283 | NumNodes = 0; | |||
284 | ||||
285 | // Walk the old buckets, rehashing nodes into their new place. | |||
286 | FoldingSetNodeID TempID; | |||
287 | for (unsigned i = 0; i != OldNumBuckets; ++i) { | |||
288 | void *Probe = OldBuckets[i]; | |||
289 | if (!Probe) continue; | |||
290 | while (Node *NodeInBucket = GetNextPtr(Probe)) { | |||
291 | // Figure out the next link, remove NodeInBucket from the old link. | |||
292 | Probe = NodeInBucket->getNextInBucket(); | |||
293 | NodeInBucket->SetNextInBucket(nullptr); | |||
294 | ||||
295 | // Insert the node into the new bucket, after recomputing the hash. | |||
296 | InsertNode(NodeInBucket, | |||
297 | GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), | |||
298 | Buckets, NumBuckets)); | |||
299 | TempID.clear(); | |||
300 | } | |||
301 | } | |||
302 | ||||
303 | free(OldBuckets); | |||
304 | } | |||
305 | ||||
306 | /// GrowHashTable - Double the size of the hash table and rehash everything. | |||
307 | /// | |||
308 | void FoldingSetBase::GrowHashTable() { | |||
309 | GrowBucketCount(NumBuckets * 2); | |||
310 | } | |||
311 | ||||
312 | void FoldingSetBase::reserve(unsigned EltCount) { | |||
313 | // This will give us somewhere between EltCount / 2 and | |||
314 | // EltCount buckets. This puts us in the load factor | |||
315 | // range of 1.0 - 2.0. | |||
316 | if(EltCount < capacity()) | |||
317 | return; | |||
318 | GrowBucketCount(PowerOf2Floor(EltCount)); | |||
319 | } | |||
320 | ||||
321 | /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, | |||
322 | /// return it. If not, return the insertion token that will make insertion | |||
323 | /// faster. | |||
324 | FoldingSetBase::Node * | |||
325 | FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID, | |||
326 | void *&InsertPos) { | |||
327 | unsigned IDHash = ID.ComputeHash(); | |||
328 | void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); | |||
329 | void *Probe = *Bucket; | |||
330 | ||||
331 | InsertPos = nullptr; | |||
332 | ||||
333 | FoldingSetNodeID TempID; | |||
334 | while (Node *NodeInBucket = GetNextPtr(Probe)) { | |||
335 | if (NodeEquals(NodeInBucket, ID, IDHash, TempID)) | |||
336 | return NodeInBucket; | |||
337 | TempID.clear(); | |||
338 | ||||
339 | Probe = NodeInBucket->getNextInBucket(); | |||
340 | } | |||
341 | ||||
342 | // Didn't find the node, return null with the bucket as the InsertPos. | |||
343 | InsertPos = Bucket; | |||
344 | return nullptr; | |||
345 | } | |||
346 | ||||
347 | /// InsertNode - Insert the specified node into the folding set, knowing that it | |||
348 | /// is not already in the map. InsertPos must be obtained from | |||
349 | /// FindNodeOrInsertPos. | |||
350 | void FoldingSetBase::InsertNode(Node *N, void *InsertPos) { | |||
351 | assert(!N->getNextInBucket())(static_cast <bool> (!N->getNextInBucket()) ? void ( 0) : __assert_fail ("!N->getNextInBucket()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/FoldingSet.cpp" , 351, __extension__ __PRETTY_FUNCTION__)); | |||
352 | // Do we need to grow the hashtable? | |||
353 | if (NumNodes+1 > capacity()) { | |||
354 | GrowHashTable(); | |||
355 | FoldingSetNodeID TempID; | |||
356 | InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); | |||
357 | } | |||
358 | ||||
359 | ++NumNodes; | |||
360 | ||||
361 | /// The insert position is actually a bucket pointer. | |||
362 | void **Bucket = static_cast<void**>(InsertPos); | |||
363 | ||||
364 | void *Next = *Bucket; | |||
365 | ||||
366 | // If this is the first insertion into this bucket, its next pointer will be | |||
367 | // null. Pretend as if it pointed to itself, setting the low bit to indicate | |||
368 | // that it is a pointer to the bucket. | |||
369 | if (!Next) | |||
370 | Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); | |||
371 | ||||
372 | // Set the node's next pointer, and make the bucket point to the node. | |||
373 | N->SetNextInBucket(Next); | |||
374 | *Bucket = N; | |||
375 | } | |||
376 | ||||
377 | /// RemoveNode - Remove a node from the folding set, returning true if one was | |||
378 | /// removed or false if the node was not in the folding set. | |||
379 | bool FoldingSetBase::RemoveNode(Node *N) { | |||
380 | // Because each bucket is a circular list, we don't need to compute N's hash | |||
381 | // to remove it. | |||
382 | void *Ptr = N->getNextInBucket(); | |||
383 | if (!Ptr) return false; // Not in folding set. | |||
384 | ||||
385 | --NumNodes; | |||
386 | N->SetNextInBucket(nullptr); | |||
387 | ||||
388 | // Remember what N originally pointed to, either a bucket or another node. | |||
389 | void *NodeNextPtr = Ptr; | |||
390 | ||||
391 | // Chase around the list until we find the node (or bucket) which points to N. | |||
392 | while (true) { | |||
393 | if (Node *NodeInBucket = GetNextPtr(Ptr)) { | |||
394 | // Advance pointer. | |||
395 | Ptr = NodeInBucket->getNextInBucket(); | |||
396 | ||||
397 | // We found a node that points to N, change it to point to N's next node, | |||
398 | // removing N from the list. | |||
399 | if (Ptr == N) { | |||
400 | NodeInBucket->SetNextInBucket(NodeNextPtr); | |||
401 | return true; | |||
402 | } | |||
403 | } else { | |||
404 | void **Bucket = GetBucketPtr(Ptr); | |||
405 | Ptr = *Bucket; | |||
406 | ||||
407 | // If we found that the bucket points to N, update the bucket to point to | |||
408 | // whatever is next. | |||
409 | if (Ptr == N) { | |||
410 | *Bucket = NodeNextPtr; | |||
411 | return true; | |||
412 | } | |||
413 | } | |||
414 | } | |||
415 | } | |||
416 | ||||
417 | /// GetOrInsertNode - If there is an existing simple Node exactly | |||
418 | /// equal to the specified node, return it. Otherwise, insert 'N' and it | |||
419 | /// instead. | |||
420 | FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) { | |||
421 | FoldingSetNodeID ID; | |||
422 | GetNodeProfile(N, ID); | |||
423 | void *IP; | |||
424 | if (Node *E = FindNodeOrInsertPos(ID, IP)) | |||
425 | return E; | |||
426 | InsertNode(N, IP); | |||
427 | return N; | |||
428 | } | |||
429 | ||||
430 | //===----------------------------------------------------------------------===// | |||
431 | // FoldingSetIteratorImpl Implementation | |||
432 | ||||
433 | FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { | |||
434 | // Skip to the first non-null non-self-cycle bucket. | |||
435 | while (*Bucket != reinterpret_cast<void*>(-1) && | |||
436 | (!*Bucket || !GetNextPtr(*Bucket))) | |||
437 | ++Bucket; | |||
438 | ||||
439 | NodePtr = static_cast<FoldingSetNode*>(*Bucket); | |||
440 | } | |||
441 | ||||
442 | void FoldingSetIteratorImpl::advance() { | |||
443 | // If there is another link within this bucket, go to it. | |||
444 | void *Probe = NodePtr->getNextInBucket(); | |||
445 | ||||
446 | if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) | |||
447 | NodePtr = NextNodeInBucket; | |||
448 | else { | |||
449 | // Otherwise, this is the last link in this bucket. | |||
450 | void **Bucket = GetBucketPtr(Probe); | |||
451 | ||||
452 | // Skip to the next non-null non-self-cycle bucket. | |||
453 | do { | |||
454 | ++Bucket; | |||
455 | } while (*Bucket != reinterpret_cast<void*>(-1) && | |||
456 | (!*Bucket || !GetNextPtr(*Bucket))); | |||
457 | ||||
458 | NodePtr = static_cast<FoldingSetNode*>(*Bucket); | |||
459 | } | |||
460 | } | |||
461 | ||||
462 | //===----------------------------------------------------------------------===// | |||
463 | // FoldingSetBucketIteratorImpl Implementation | |||
464 | ||||
465 | FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { | |||
466 | Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket; | |||
467 | } |