10e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===// 20e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 30e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// The LLVM Compiler Infrastructure 40e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 70e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 80e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 90e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 100e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// This file implements a hash set that can be used to remove duplication of 1179dcd43600c544dc16b100a8ad35fd6a5c0a711aChris Lattner// nodes in a graph. 120e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 130e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 140e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 150e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey#include "llvm/ADT/FoldingSet.h" 16abe24cf037553755df052bbc11c18ad288607849Chandler Carruth#include "llvm/ADT/Hashing.h" 17c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman#include "llvm/Support/Allocator.h" 18c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 191f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/Host.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/MathExtras.h" 2139c6d3aac1a049a9e9696b20fb9e9fdd6e906b91Rafael Espindola#include <cassert> 22ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov#include <cstring> 230e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskeyusing namespace llvm; 240e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 250e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 263063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman// FoldingSetNodeIDRef Implementation 273063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 283063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 293063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// used to lookup the node in the FoldingSetImpl. 303063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmanunsigned FoldingSetNodeIDRef::ComputeHash() const { 31abe24cf037553755df052bbc11c18ad288607849Chandler Carruth return static_cast<unsigned>(hash_combine_range(Data, Data+Size)); 323063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 333063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 343063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmanbool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { 353063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman if (Size != RHS.Size) return false; 363063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0; 373063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 383063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 390d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek/// Used to compare the "ordering" of two nodes as defined by the 400d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek/// profiled bits and their ordering defined by memcmp(). 410d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenekbool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const { 420d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek if (Size != RHS.Size) 430d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek return Size < RHS.Size; 440d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0; 450d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek} 460d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek 473063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman//===----------------------------------------------------------------------===// 480a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek// FoldingSetNodeID Implementation 490e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 50ed5edea96d72440679311d7d31d39804967f3220Duncan Sands/// Add* - Add various data types to Bit data. 51ed5edea96d72440679311d7d31d39804967f3220Duncan Sands/// 52ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddPointer(const void *Ptr) { 53ed5edea96d72440679311d7d31d39804967f3220Duncan Sands // Note: this adds pointers to the hash using sizes and endianness that 540c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // depend on the host. It doesn't matter, however, because hashing on 550c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar // pointer values is inherently unstable. Nothing should depend on the 56ed5edea96d72440679311d7d31d39804967f3220Duncan Sands // ordering of nodes in the folding set. 57ed5edea96d72440679311d7d31d39804967f3220Duncan Sands Bits.append(reinterpret_cast<unsigned *>(&Ptr), 58ed5edea96d72440679311d7d31d39804967f3220Duncan Sands reinterpret_cast<unsigned *>(&Ptr+1)); 59ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 60ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddInteger(signed I) { 61ed5edea96d72440679311d7d31d39804967f3220Duncan Sands Bits.push_back(I); 62ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 63ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddInteger(unsigned I) { 64ed5edea96d72440679311d7d31d39804967f3220Duncan Sands Bits.push_back(I); 65ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 66ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddInteger(long I) { 67ed5edea96d72440679311d7d31d39804967f3220Duncan Sands AddInteger((unsigned long)I); 68ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 69ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddInteger(unsigned long I) { 70ed5edea96d72440679311d7d31d39804967f3220Duncan Sands if (sizeof(long) == sizeof(int)) 71ed5edea96d72440679311d7d31d39804967f3220Duncan Sands AddInteger(unsigned(I)); 72ed5edea96d72440679311d7d31d39804967f3220Duncan Sands else if (sizeof(long) == sizeof(long long)) { 73ed5edea96d72440679311d7d31d39804967f3220Duncan Sands AddInteger((unsigned long long)I); 74ed5edea96d72440679311d7d31d39804967f3220Duncan Sands } else { 75ed5edea96d72440679311d7d31d39804967f3220Duncan Sands llvm_unreachable("unexpected sizeof(long)"); 76ed5edea96d72440679311d7d31d39804967f3220Duncan Sands } 77ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 78ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddInteger(long long I) { 79ed5edea96d72440679311d7d31d39804967f3220Duncan Sands AddInteger((unsigned long long)I); 80ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 81ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddInteger(unsigned long long I) { 82ed5edea96d72440679311d7d31d39804967f3220Duncan Sands AddInteger(unsigned(I)); 83ed5edea96d72440679311d7d31d39804967f3220Duncan Sands if ((uint64_t)(unsigned)I != I) 84ed5edea96d72440679311d7d31d39804967f3220Duncan Sands Bits.push_back(unsigned(I >> 32)); 85ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 86ed5edea96d72440679311d7d31d39804967f3220Duncan Sands 8727dba671c3f158a33c8cbdf5196a6fd16489be03Daniel Dunbarvoid FoldingSetNodeID::AddString(StringRef String) { 8827dba671c3f158a33c8cbdf5196a6fd16489be03Daniel Dunbar unsigned Size = String.size(); 8972e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson Bits.push_back(Size); 9072e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson if (!Size) return; 9172e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson 9272e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson unsigned Units = Size / 4; 9372e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson unsigned Pos = 0; 9427dba671c3f158a33c8cbdf5196a6fd16489be03Daniel Dunbar const unsigned *Base = (const unsigned*) String.data(); 9572e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson 9672e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson // If the string is aligned do a bulk transfer. 9772e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson if (!((intptr_t)Base & 3)) { 9872e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson Bits.append(Base, Base + Units); 9972e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson Pos = (Units + 1) * 4; 10072e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson } else { 10172e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson // Otherwise do it the hard way. 102c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen // To be compatible with above bulk transfer, we need to take endianness 103c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen // into account. 1044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost, 1054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar "Unexpected host endianness"); 10621a01d1ea89dba97c4f9e1f9f41485729a4046bcRafael Espindola if (sys::IsBigEndianHost) { 107c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen for (Pos += 4; Pos <= Size; Pos += 4) { 108c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen unsigned V = ((unsigned char)String[Pos - 4] << 24) | 109c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen ((unsigned char)String[Pos - 3] << 16) | 110c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen ((unsigned char)String[Pos - 2] << 8) | 111c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen (unsigned char)String[Pos - 1]; 112c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen Bits.push_back(V); 113c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen } 1144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { // Little-endian host 115c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen for (Pos += 4; Pos <= Size; Pos += 4) { 116c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen unsigned V = ((unsigned char)String[Pos - 1] << 24) | 117c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen ((unsigned char)String[Pos - 2] << 16) | 118c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen ((unsigned char)String[Pos - 3] << 8) | 119c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen (unsigned char)String[Pos - 4]; 120c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen Bits.push_back(V); 121c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen } 12272e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson } 12372e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson } 12472e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson 12572e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson // With the leftover bits. 12672e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson unsigned V = 0; 127c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen // Pos will have overshot size by 4 - #bytes left over. 128c81c7fe643e91bc6ed817bf5e17379b74e161b91Dale Johannesen // No need to take endianness into account here - this is always executed. 12972e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson switch (Pos - Size) { 13072e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. 13172e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. 13272e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 13372e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson default: return; // Nothing left. 13472e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson } 13572e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson 13672e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson Bits.push_back(V); 13772e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson} 13872e61b85017286418ca5266c2ff7b88782e2fe00Owen Anderson 139ed5edea96d72440679311d7d31d39804967f3220Duncan Sands// AddNodeID - Adds the Bit data of another ID to *this. 140ed5edea96d72440679311d7d31d39804967f3220Duncan Sandsvoid FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { 141ed5edea96d72440679311d7d31d39804967f3220Duncan Sands Bits.append(ID.Bits.begin(), ID.Bits.end()); 142ed5edea96d72440679311d7d31d39804967f3220Duncan Sands} 143ed5edea96d72440679311d7d31d39804967f3220Duncan Sands 144ed5edea96d72440679311d7d31d39804967f3220Duncan Sands/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 1450e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// lookup the node in the FoldingSetImpl. 1460a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenekunsigned FoldingSetNodeID::ComputeHash() const { 147365c53e3281860d46f771edf88156ca0aac581cfDan Gohman return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); 1480e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 1490e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 1500e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// operator== - Used to compare two nodes to each other. 1510e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 15208d785bc2a0b444efc98106460d6dae3768a0e7fNick Lewyckybool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const { 153365c53e3281860d46f771edf88156ca0aac581cfDan Gohman return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); 1543063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 1553063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 1563063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// operator== - Used to compare two nodes to each other. 1573063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// 1583063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmanbool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const { 159365c53e3281860d46f771edf88156ca0aac581cfDan Gohman return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS; 1600e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 1610e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 1620d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek/// Used to compare the "ordering" of two nodes as defined by the 1630d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek/// profiled bits and their ordering defined by memcmp(). 16408d785bc2a0b444efc98106460d6dae3768a0e7fNick Lewyckybool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const { 1650d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); 1660d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek} 1670d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek 1680d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenekbool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const { 1690d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS; 1700d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek} 1710d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek 172c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// Intern - Copy this node's data to a memory region allocated from the 173c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// given allocator and return a FoldingSetNodeIDRef describing the 174c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// interned data. 175c93b4cff89d85a13d4eaf1551af9fab276b88450Dan GohmanFoldingSetNodeIDRef 176c93b4cff89d85a13d4eaf1551af9fab276b88450Dan GohmanFoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { 177c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman unsigned *New = Allocator.Allocate<unsigned>(Bits.size()); 178c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman std::uninitialized_copy(Bits.begin(), Bits.end(), New); 179c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman return FoldingSetNodeIDRef(New, Bits.size()); 180c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman} 1810e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 1820e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 18318529f35151f18345519e38496ac72350ee15f38Jim Laskey/// Helper functions for FoldingSetImpl. 1840e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 1850e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// GetNextPtr - In order to save space, each bucket is a 1860e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// singly-linked-list. In order to make deletion more efficient, we make 1870e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// the list circular, so we can delete a node without computing its hash. 1880e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// The problem with this is that the start of the hash buckets are not 1893cab071f6f1534ff424d4b947715ae758edca790Chris Lattner/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: 1903cab071f6f1534ff424d4b947715ae758edca790Chris Lattner/// use GetBucketPtr when this happens. 1919a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattnerstatic FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { 1929a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner // The low bit is set if this is the pointer back to the bucket. 1939a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) 194dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1959a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner 19618529f35151f18345519e38496ac72350ee15f38Jim Laskey return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr); 1970e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 1980e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 19926e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek 2000e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// testing. 20118529f35151f18345519e38496ac72350ee15f38Jim Laskeystatic void **GetBucketPtr(void *NextInBucketPtr) { 2029a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); 203116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner assert((Ptr & 1) && "Not a bucket pointer"); 2049a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); 2050e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 2060e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 2070e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// GetBucketFor - Hash the specified node ID and return the hash bucket for 2080e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// the specified ID. 2093063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmanstatic void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) { 2100e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // NumBuckets is always a power of 2. 2113063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman unsigned BucketNum = Hash & (NumBuckets-1); 21218529f35151f18345519e38496ac72350ee15f38Jim Laskey return Buckets + BucketNum; 21318529f35151f18345519e38496ac72350ee15f38Jim Laskey} 21418529f35151f18345519e38496ac72350ee15f38Jim Laskey 2156118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer/// AllocateBuckets - Allocated initialized bucket memory. 2166118efa59ea751cb0790de860721695f5da819c1Benjamin Kramerstatic void **AllocateBuckets(unsigned NumBuckets) { 2176118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*))); 2186118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer // Set the very last bucket to be a non-null "pointer". 2196118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 2206118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer return Buckets; 2216118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer} 2226118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer 22318529f35151f18345519e38496ac72350ee15f38Jim Laskey//===----------------------------------------------------------------------===// 22418529f35151f18345519e38496ac72350ee15f38Jim Laskey// FoldingSetImpl Implementation 22518529f35151f18345519e38496ac72350ee15f38Jim Laskey 2264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarvoid FoldingSetImpl::anchor() {} 2274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 228535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan GohmanFoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { 2291f67a99260917d33fefc6a7d863b0cd850a34431Jim Laskey assert(5 < Log2InitSize && Log2InitSize < 32 && 2301f67a99260917d33fefc6a7d863b0cd850a34431Jim Laskey "Initial hash table size out of range"); 2311f67a99260917d33fefc6a7d863b0cd850a34431Jim Laskey NumBuckets = 1 << Log2InitSize; 2326118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer Buckets = AllocateBuckets(NumBuckets); 2336118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer NumNodes = 0; 23418529f35151f18345519e38496ac72350ee15f38Jim Laskey} 235f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 236f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarFoldingSetImpl::FoldingSetImpl(FoldingSetImpl &&Arg) 237f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) { 238f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Arg.Buckets = nullptr; 239f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Arg.NumBuckets = 0; 240f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Arg.NumNodes = 0; 241f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 242f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 243f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarFoldingSetImpl &FoldingSetImpl::operator=(FoldingSetImpl &&RHS) { 244f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar free(Buckets); // This may be null if the set is in a moved-from state. 245f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Buckets = RHS.Buckets; 246f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NumBuckets = RHS.NumBuckets; 247f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NumNodes = RHS.NumNodes; 248f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RHS.Buckets = nullptr; 249f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RHS.NumBuckets = 0; 250f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RHS.NumNodes = 0; 251f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return *this; 252f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 253f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 25418529f35151f18345519e38496ac72350ee15f38Jim LaskeyFoldingSetImpl::~FoldingSetImpl() { 2556118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer free(Buckets); 2560e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 257f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 258535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohmanvoid FoldingSetImpl::clear() { 259535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman // Set all but the last bucket to null pointers. 260535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman memset(Buckets, 0, NumBuckets*sizeof(void*)); 261535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman 262535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman // Set the very last bucket to be a non-null "pointer". 263535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 264535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman 265535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman // Reset the node count to zero. 266535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman NumNodes = 0; 267535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman} 2680e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 269de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid FoldingSetImpl::GrowBucketCount(unsigned NewBucketCount) { 270de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount"); 271de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!"); 2720e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void **OldBuckets = Buckets; 2730e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey unsigned OldNumBuckets = NumBuckets; 274de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumBuckets = NewBucketCount; 2750e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 2760e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Clear out new buckets. 2776118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer Buckets = AllocateBuckets(NumBuckets); 2786118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer NumNodes = 0; 2799a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner 2800e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Walk the old buckets, rehashing nodes into their new place. 2813063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID TempID; 2820e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey for (unsigned i = 0; i != OldNumBuckets; ++i) { 2830e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void *Probe = OldBuckets[i]; 2840e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey if (!Probe) continue; 2859a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner while (Node *NodeInBucket = GetNextPtr(Probe)) { 2860e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Figure out the next link, remove NodeInBucket from the old link. 2870e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey Probe = NodeInBucket->getNextInBucket(); 288dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeInBucket->SetNextInBucket(nullptr); 2890e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 2900e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Insert the node into the new bucket, after recomputing the hash. 2913063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman InsertNode(NodeInBucket, 2923063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), 2933063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman Buckets, NumBuckets)); 2943063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman TempID.clear(); 2950e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 2960e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 2970e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 2986118efa59ea751cb0790de860721695f5da819c1Benjamin Kramer free(OldBuckets); 2990e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 3000e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 301de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// GrowHashTable - Double the size of the hash table and rehash everything. 302de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 303de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid FoldingSetImpl::GrowHashTable() { 304de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GrowBucketCount(NumBuckets * 2); 305de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 306de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 307de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid FoldingSetImpl::reserve(unsigned EltCount) { 308de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // This will give us somewhere between EltCount / 2 and 309de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // EltCount buckets. This puts us in the load factor 310de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // range of 1.0 - 2.0. 311de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if(EltCount < capacity()) 312de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return; 313de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GrowBucketCount(PowerOf2Floor(EltCount)); 314de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 315de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 3160e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 3170e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// return it. If not, return the insertion token that will make insertion 3180e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// faster. 31927a8e0dc2f715da948517a6098f3c43108a87761Ted KremenekFoldingSetImpl::Node 32027a8e0dc2f715da948517a6098f3c43108a87761Ted Kremenek*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, 32127a8e0dc2f715da948517a6098f3c43108a87761Ted Kremenek void *&InsertPos) { 322f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer unsigned IDHash = ID.ComputeHash(); 323f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); 3240e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void *Probe = *Bucket; 3250e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InsertPos = nullptr; 3270e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3283063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID TempID; 3299a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner while (Node *NodeInBucket = GetNextPtr(Probe)) { 330f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer if (NodeEquals(NodeInBucket, ID, IDHash, TempID)) 3310e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey return NodeInBucket; 3323063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman TempID.clear(); 3330e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3340e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey Probe = NodeInBucket->getNextInBucket(); 3350e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 3360e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3370e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Didn't find the node, return null with the bucket as the InsertPos. 3380e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey InsertPos = Bucket; 339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 3400e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 3410e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3420e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// InsertNode - Insert the specified node into the folding set, knowing that it 3430e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// is not already in the map. InsertPos must be obtained from 3440e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// FindNodeOrInsertPos. 3450e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskeyvoid FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { 346dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(!N->getNextInBucket()); 3470e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Do we need to grow the hashtable? 348de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (NumNodes+1 > capacity()) { 3490e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey GrowHashTable(); 3503063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID TempID; 3513063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); 3520e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 353b85210f508556a81aecde07b87b2dfc6236de6e7Chris Lattner 354b85210f508556a81aecde07b87b2dfc6236de6e7Chris Lattner ++NumNodes; 3550e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3560e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// The insert position is actually a bucket pointer. 3570e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void **Bucket = static_cast<void**>(InsertPos); 3580e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3590e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void *Next = *Bucket; 3600e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3610e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // If this is the first insertion into this bucket, its next pointer will be 3629a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner // null. Pretend as if it pointed to itself, setting the low bit to indicate 3639a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner // that it is a pointer to the bucket. 364dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Next) 3659a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); 3660e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 367b85210f508556a81aecde07b87b2dfc6236de6e7Chris Lattner // Set the node's next pointer, and make the bucket point to the node. 3680e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey N->SetNextInBucket(Next); 3690e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey *Bucket = N; 3700e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 3710e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3720e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// RemoveNode - Remove a node from the folding set, returning true if one was 3730e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// removed or false if the node was not in the folding set. 3740e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskeybool FoldingSetImpl::RemoveNode(Node *N) { 3750e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Because each bucket is a circular list, we don't need to compute N's hash 3760de4439ad1c4b105680afed521aa3b1820a61409Chris Lattner // to remove it. 3770e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void *Ptr = N->getNextInBucket(); 378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Ptr) return false; // Not in folding set. 3790e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3800e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey --NumNodes; 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines N->SetNextInBucket(nullptr); 3820e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3830de4439ad1c4b105680afed521aa3b1820a61409Chris Lattner // Remember what N originally pointed to, either a bucket or another node. 3840e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void *NodeNextPtr = Ptr; 3850de4439ad1c4b105680afed521aa3b1820a61409Chris Lattner 3860de4439ad1c4b105680afed521aa3b1820a61409Chris Lattner // Chase around the list until we find the node (or bucket) which points to N. 3870e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey while (true) { 3889a7288b0c6caf5d6eeddaa8f3835b8e121c1e303Chris Lattner if (Node *NodeInBucket = GetNextPtr(Ptr)) { 3890e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Advance pointer. 3900e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey Ptr = NodeInBucket->getNextInBucket(); 3910e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 3920e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // We found a node that points to N, change it to point to N's next node, 3930e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // removing N from the list. 3940e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey if (Ptr == N) { 3950e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey NodeInBucket->SetNextInBucket(NodeNextPtr); 3960e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey return true; 3970e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 3980e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } else { 3990e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void **Bucket = GetBucketPtr(Ptr); 4000e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey Ptr = *Bucket; 4010e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 4020e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // If we found that the bucket points to N, update the bucket to point to 4030e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // whatever is next. 4040e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey if (Ptr == N) { 4050e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey *Bucket = NodeNextPtr; 4060e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey return true; 4070e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 4080e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 4090e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey } 4100e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 4110e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 4120e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// GetOrInsertNode - If there is an existing simple Node exactly 4130e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// equal to the specified node, return it. Otherwise, insert 'N' and it 4140e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// instead. 4150e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim LaskeyFoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 4160a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek FoldingSetNodeID ID; 4176616f7e2f147c2320973993cbfb241a82262b764Dan Gohman GetNodeProfile(N, ID); 4180e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void *IP; 4190e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey if (Node *E = FindNodeOrInsertPos(ID, IP)) 4200e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey return E; 4210e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey InsertNode(N, IP); 4220e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey return N; 4230e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey} 424116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 425116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner//===----------------------------------------------------------------------===// 426116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner// FoldingSetIteratorImpl Implementation 427116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 428116c3219df347f169b1bd24acca2d53ab0ae26ecChris LattnerFoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { 429116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner // Skip to the first non-null non-self-cycle bucket. 430e3e09574aecb8fabf5e4bd4e972183a06a1748f5Ted Kremenek while (*Bucket != reinterpret_cast<void*>(-1) && 431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (!*Bucket || !GetNextPtr(*Bucket))) 432116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner ++Bucket; 433116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 434116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner NodePtr = static_cast<FoldingSetNode*>(*Bucket); 435116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner} 436116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 437116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnervoid FoldingSetIteratorImpl::advance() { 438116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner // If there is another link within this bucket, go to it. 439116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner void *Probe = NodePtr->getNextInBucket(); 440116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 441116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) 442116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner NodePtr = NextNodeInBucket; 443116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner else { 444116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner // Otherwise, this is the last link in this bucket. 445116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner void **Bucket = GetBucketPtr(Probe); 446116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 447116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner // Skip to the next non-null non-self-cycle bucket. 448116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner do { 449116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner ++Bucket; 450e3e09574aecb8fabf5e4bd4e972183a06a1748f5Ted Kremenek } while (*Bucket != reinterpret_cast<void*>(-1) && 451dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (!*Bucket || !GetNextPtr(*Bucket))); 452116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 453116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner NodePtr = static_cast<FoldingSetNode*>(*Bucket); 454116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 455116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner} 456116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 45726e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek//===----------------------------------------------------------------------===// 45826e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek// FoldingSetBucketIteratorImpl Implementation 45926e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek 46026e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted KremenekFoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { 461dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket; 46226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek} 463