FoldingSet.cpp revision 541ed9fd02ea48d2739f4a9dd681ba2d5da26886
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// This file implements a hash set that can be used to remove duplication of 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// nodes in a graph. This code was originally created by Chris Lattner for use 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// with SelectionDAGCSEMap, but was isolated to provide use across the llvm code 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// set. 147dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 167dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 17d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)#include "llvm/ADT/FoldingSet.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/MathExtras.h" 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <cassert> 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <cstring> 212385ea399aae016c0806a4f9ef3c9cfe3d2a39dfBen Murdochusing namespace llvm; 2290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 23eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch//===----------------------------------------------------------------------===// 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// FoldingSetNodeID Implementation 252385ea399aae016c0806a4f9ef3c9cfe3d2a39dfBen Murdoch 26a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// Add* - Add various data types to Bit data. 272385ea399aae016c0806a4f9ef3c9cfe3d2a39dfBen Murdoch/// 282385ea399aae016c0806a4f9ef3c9cfe3d2a39dfBen Murdochvoid FoldingSetNodeID::AddPointer(const void *Ptr) { 2990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Note: this adds pointers to the hash using sizes and endianness that 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // depend on the host. It doesn't matter however, because hashing on 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // pointer values in inherently unstable. Nothing should depend on the 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // ordering of nodes in the folding set. 337dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch intptr_t PtrI = (intptr_t)Ptr; 34f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) Bits.push_back(unsigned(PtrI)); 3568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (sizeof(intptr_t) > sizeof(unsigned)) 36eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch Bits.push_back(unsigned(uint64_t(PtrI) >> 32)); 3790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FoldingSetNodeID::AddInteger(signed I) { 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bits.push_back(I); 40d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)} 41d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)void FoldingSetNodeID::AddInteger(unsigned I) { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bits.push_back(I); 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FoldingSetNodeID::AddInteger(long I) { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddInteger((unsigned long)I); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void FoldingSetNodeID::AddInteger(unsigned long I) { 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (sizeof(long) == sizeof(int)) 49a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) AddInteger(unsigned(I)); 50a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) else if (sizeof(long) == sizeof(long long)) { 51a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) AddInteger((unsigned long long)I); 52c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) assert(0 && "unexpected sizeof(long)"); 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void FoldingSetNodeID::AddInteger(long long I) { 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) AddInteger((unsigned long long)I); 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void FoldingSetNodeID::AddInteger(unsigned long long I) { 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) AddInteger(unsigned(I)); 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if ((uint64_t)(int)I != I) 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Bits.push_back(unsigned(I >> 32)); 63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void FoldingSetNodeID::AddString(const char *String) { 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) unsigned Size = static_cast<unsigned>(strlen(String)); 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Bits.push_back(Size); 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!Size) return; 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) unsigned Units = Size / 4; 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) unsigned Pos = 0; 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const unsigned *Base = (const unsigned *)String; 73a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) 74a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // If the string is aligned do a bulk transfer. 75b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) if (!((intptr_t)Base & 3)) { 76b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) Bits.append(Base, Base + Units); 77a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Pos = (Units + 1) * 4; 78a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } else { 7990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Otherwise do it the hard way. 8090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for ( Pos += 4; Pos <= Size; Pos += 4) { 81a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) unsigned V = ((unsigned char)String[Pos - 4] << 24) | 8290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ((unsigned char)String[Pos - 3] << 16) | 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ((unsigned char)String[Pos - 2] << 8) | 84a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) (unsigned char)String[Pos - 1]; 8590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Bits.push_back(V); 8690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 87a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) } 8890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // With the leftover bits. 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) unsigned V = 0; 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Pos will have overshot size by 4 - #bytes left over. 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) switch (Pos - Size) { 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) default: return; // Nothing left. 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Bits.push_back(V); 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 10290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)void FoldingSetNodeID::AddString(const std::string &String) { 10390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned Size = static_cast<unsigned>(String.size()); 10490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Bits.push_back(Size); 10590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (!Size) return; 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) unsigned Units = Size / 4; 1087dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch unsigned Pos = 0; 1097dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const unsigned *Base = (const unsigned *)String.data(); 1107dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 1117dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // If the string is aligned do a bulk transfer. 1127dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch if (!((intptr_t)Base & 3)) { 1137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) Bits.append(Base, Base + Units); 1147dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch Pos = (Units + 1) * 4; 1157dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } else { 1167d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Otherwise do it the hard way. 1177dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch for ( Pos += 4; Pos <= Size; Pos += 4) { 1187dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch unsigned V = ((unsigned char)String[Pos - 4] << 24) | 1197d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) ((unsigned char)String[Pos - 3] << 16) | 1207d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) ((unsigned char)String[Pos - 2] << 8) | 1217dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch (unsigned char)String[Pos - 1]; 1227d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) Bits.push_back(V); 1237d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) } 1247dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 1257dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 1267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // With the leftover bits. 1277d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) unsigned V = 0; 1287dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // Pos will have overshot size by 4 - #bytes left over. 1297dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch switch (Pos - Size) { 1307d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. 1317d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. 1327dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 1337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) default: return; // Nothing left. 1347d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) } 135a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 136a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Bits.push_back(V); 137a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 138a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 139a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 140a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// lookup the node in the FoldingSetImpl. 141a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)unsigned FoldingSetNodeID::ComputeHash() const { 142a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // This is adapted from SuperFastHash by Paul Hsieh. 143a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) unsigned Hash = static_cast<unsigned>(Bits.size()); 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) { 145a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) unsigned Data = *BP; 146d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) Hash += Data & 0xFFFF; 147a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) unsigned Tmp = ((Data >> 16) << 11) ^ Hash; 148a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash = (Hash << 16) ^ Tmp; 149d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) Hash += Hash >> 11; 150a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 151a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 152a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Force "avalanching" of final 127 bits. 153a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash ^= Hash << 3; 154a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash += Hash >> 5; 155a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash ^= Hash << 4; 156a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash += Hash >> 17; 157a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash ^= Hash << 25; 158a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Hash += Hash >> 6; 159a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return Hash; 160a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 161a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 162a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// operator== - Used to compare two nodes to each other. 163d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)/// 164d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{ 165a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (Bits.size() != RHS.Bits.size()) return false; 166a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0; 167a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 168d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 169a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 170d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)//===----------------------------------------------------------------------===// 171a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// Helper functions for FoldingSetImpl. 172a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 173a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// GetNextPtr - In order to save space, each bucket is a 174a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// singly-linked-list. In order to make deletion more efficient, we make 175d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)/// the list circular, so we can delete a node without computing its hash. 176d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)/// The problem with this is that the start of the hash buckets are not 177a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: 178a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// use GetBucketPtr when this happens. 179a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { 180a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // The low bit is set if this is the pointer back to the bucket. 181d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) 182a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return 0; 183a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 184a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr); 185a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 186d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 187d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 188a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// testing. 189a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)static void **GetBucketPtr(void *NextInBucketPtr) { 190a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); 191d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) assert((Ptr & 1) && "Not a bucket pointer"); 192a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); 193a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 194a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 195a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// GetBucketFor - Hash the specified node ID and return the hash bucket for 196a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// the specified ID. 197a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)static void **GetBucketFor(const FoldingSetNodeID &ID, 198a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void **Buckets, unsigned NumBuckets) { 199a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // NumBuckets is always a power of 2. 200a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1); 201a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return Buckets + BucketNum; 202a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 203a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 204a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)//===----------------------------------------------------------------------===// 205a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)// FoldingSetImpl Implementation 206a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 207a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { 208a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) assert(5 < Log2InitSize && Log2InitSize < 32 && 209d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) "Initial hash table size out of range"); 210a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) NumBuckets = 1 << Log2InitSize; 211a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Buckets = new void*[NumBuckets+1]; 212d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) clear(); 213d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)} 214a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)FoldingSetImpl::~FoldingSetImpl() { 215a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) delete [] Buckets; 216a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 217d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)void FoldingSetImpl::clear() { 218a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Set all but the last bucket to null pointers. 219d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) memset(Buckets, 0, NumBuckets*sizeof(void*)); 220a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 221a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Set the very last bucket to be a non-null "pointer". 222a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 223a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 224d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) // Reset the node count to zero. 225a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) NumNodes = 0; 226a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)} 227a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 228a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// GrowHashTable - Double the size of the hash table and rehash everything. 229a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// 230a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)void FoldingSetImpl::GrowHashTable() { 231a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void **OldBuckets = Buckets; 232d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) unsigned OldNumBuckets = NumBuckets; 233a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) NumBuckets <<= 1; 234a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 235a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Clear out new buckets. 236a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Buckets = new void*[NumBuckets+1]; 237a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) clear(); 238a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 239a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Walk the old buckets, rehashing nodes into their new place. 240a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) FoldingSetNodeID ID; 241a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) for (unsigned i = 0; i != OldNumBuckets; ++i) { 242a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void *Probe = OldBuckets[i]; 243a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (!Probe) continue; 244a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) while (Node *NodeInBucket = GetNextPtr(Probe)) { 245a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Figure out the next link, remove NodeInBucket from the old link. 246a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Probe = NodeInBucket->getNextInBucket(); 247a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) NodeInBucket->SetNextInBucket(0); 248a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 249d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) // Insert the node into the new bucket, after recomputing the hash. 250d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) GetNodeProfile(ID, NodeInBucket); 251d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets)); 252a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) ID.clear(); 253a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 254a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 255d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 256d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) delete[] OldBuckets; 257d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)} 258a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 259d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// return it. If not, return the insertion token that will make insertion 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// faster. 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FoldingSetImpl::Node 263a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, 264a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void *&InsertPos) { 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 266a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void **Bucket = GetBucketFor(ID, Buckets, NumBuckets); 267a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void *Probe = *Bucket; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InsertPos = 0; 2702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FoldingSetNodeID OtherID; 2722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (Node *NodeInBucket = GetNextPtr(Probe)) { 2732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GetNodeProfile(OtherID, NodeInBucket); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (OtherID == ID) 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NodeInBucket; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Probe = NodeInBucket->getNextInBucket(); 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OtherID.clear(); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Didn't find the node, return null with the bucket as the InsertPos. 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InsertPos = Bucket; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 286a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// InsertNode - Insert the specified node into the folding set, knowing that it 287a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)/// is not already in the map. InsertPos must be obtained from 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// FindNodeOrInsertPos. 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { 2907d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) assert(N->getNextInBucket() == 0); 2917d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Do we need to grow the hashtable? 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (NumNodes+1 > NumBuckets*2) { 293a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) GrowHashTable(); 294868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FoldingSetNodeID ID; 2952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GetNodeProfile(ID, N); 2962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InsertPos = GetBucketFor(ID, Buckets, NumBuckets); 2972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 299c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ++NumNodes; 300a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 301a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) /// The insert position is actually a bucket pointer. 302c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) void **Bucket = static_cast<void**>(InsertPos); 303c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 304868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) void *Next = *Bucket; 305868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 306868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // If this is the first insertion into this bucket, its next pointer will be 307a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // null. Pretend as if it pointed to itself, setting the low bit to indicate 308a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // that it is a pointer to the bucket. 309a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (Next == 0) 310a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); 311868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 312868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Set the node's next pointer, and make the bucket point to the node. 3137dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch N->SetNextInBucket(Next); 3147dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch *Bucket = N; 315eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch} 3167d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3177dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch/// RemoveNode - Remove a node from the folding set, returning true if one was 3187dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch/// removed or false if the node was not in the folding set. 3197dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdochbool FoldingSetImpl::RemoveNode(Node *N) { 3207dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // Because each bucket is a circular list, we don't need to compute N's hash 321a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // to remove it. 3227dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch void *Ptr = N->getNextInBucket(); 3237dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch if (Ptr == 0) return false; // Not in folding set. 3247dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 3257d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) --NumNodes; 3267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) N->SetNextInBucket(0); 327a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 328a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Remember what N originally pointed to, either a bucket or another node. 329a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void *NodeNextPtr = Ptr; 330a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 331a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Chase around the list until we find the node (or bucket) which points to N. 332a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) while (true) { 333a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (Node *NodeInBucket = GetNextPtr(Ptr)) { 334a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Advance pointer. 335a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Ptr = NodeInBucket->getNextInBucket(); 336a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 337a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // We found a node that points to N, change it to point to N's next node, 338a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // removing N from the list. 339a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (Ptr == N) { 340a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) NodeInBucket->SetNextInBucket(NodeNextPtr); 341a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return true; 342a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 343a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } else { 344a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) void **Bucket = GetBucketPtr(Ptr); 3452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Ptr = *Bucket; 3462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 347a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // If we found that the bucket points to N, update the bucket to point to 348a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // whatever is next. 3492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (Ptr == N) { 3502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *Bucket = NodeNextPtr; 3512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 3522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// GetOrInsertNode - If there is an existing simple Node exactly 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// equal to the specified node, return it. Otherwise, insert 'N' and it 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// instead. 360a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FoldingSetNodeID ID; 3622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GetNodeProfile(ID, N); 3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void *IP; 3642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (Node *E = FindNodeOrInsertPos(ID, IP)) 3652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return E; 3662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InsertNode(N, IP); 3672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return N; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 369a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 3702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 3712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// FoldingSetIteratorImpl Implementation 3722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Skip to the first non-null non-self-cycle bucket. 3752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (*Bucket != reinterpret_cast<void*>(-1) && 3762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (*Bucket == 0 || GetNextPtr(*Bucket) == 0)) 3772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ++Bucket; 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NodePtr = static_cast<FoldingSetNode*>(*Bucket); 3802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FoldingSetIteratorImpl::advance() { 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is another link within this bucket, go to it. 3842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void *Probe = NodePtr->getNextInBucket(); 3852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 386a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodePtr = NextNodeInBucket; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { 3892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Otherwise, this is the last link in this bucket. 3902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void **Bucket = GetBucketPtr(Probe); 391a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 392a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) // Skip to the next non-null non-self-cycle bucket. 393a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) do { 394a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) ++Bucket; 395a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } while (*Bucket != reinterpret_cast<void*>(-1) && 396a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodePtr = static_cast<FoldingSetNode*>(*Bucket); 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FoldingSetBucketIteratorImpl Implementation 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { 406a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket; 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 408a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)