17ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===// 27ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 37ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// The LLVM Compiler Infrastructure 47ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 57ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file is distributed under the University of Illinois Open Source 67ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// License. See LICENSE.TXT for details. 77ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 87ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 97ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file implements a hash set that can be used to remove duplication of 117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// nodes in a graph. 127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/FoldingSet.h" 167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/Hashing.h" 177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/Allocator.h" 187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/ErrorHandling.h" 197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/Host.h" 207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/MathExtras.h" 217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cassert> 227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cstring> 237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensusing namespace llvm; 247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// FoldingSetNodeIDRef Implementation 277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// used to lookup the node in the FoldingSetImpl. 307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensunsigned FoldingSetNodeIDRef::ComputeHash() const { 317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return static_cast<unsigned>(hash_combine_range(Data, Data+Size)); 327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { 357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Size != RHS.Size) return false; 367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0; 377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Used to compare the "ordering" of two nodes as defined by the 407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// profiled bits and their ordering defined by memcmp(). 417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const { 427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Size != RHS.Size) 437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return Size < RHS.Size; 447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0; 457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// FoldingSetNodeID Implementation 497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Add* - Add various data types to Bit data. 517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddPointer(const void *Ptr) { 537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Note: this adds pointers to the hash using sizes and endianness that 547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // depend on the host. It doesn't matter, however, because hashing on 557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // pointer values is inherently unstable. Nothing should depend on the 567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // ordering of nodes in the folding set. 572df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long), 582df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens "unexpected pointer size"); 592df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens AddInteger(reinterpret_cast<uintptr_t>(Ptr)); 607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddInteger(signed I) { 627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.push_back(I); 637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddInteger(unsigned I) { 657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.push_back(I); 667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddInteger(long I) { 687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens AddInteger((unsigned long)I); 697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddInteger(unsigned long I) { 717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (sizeof(long) == sizeof(int)) 727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens AddInteger(unsigned(I)); 737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens else if (sizeof(long) == sizeof(long long)) { 747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens AddInteger((unsigned long long)I); 757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else { 767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens llvm_unreachable("unexpected sizeof(long)"); 777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddInteger(long long I) { 807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens AddInteger((unsigned long long)I); 817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddInteger(unsigned long long I) { 837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens AddInteger(unsigned(I)); 842df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens AddInteger(unsigned(I >> 32)); 857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddString(StringRef String) { 887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned Size = String.size(); 897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.push_back(Size); 907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (!Size) return; 917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned Units = Size / 4; 937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned Pos = 0; 947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const unsigned *Base = (const unsigned*) String.data(); 957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If the string is aligned do a bulk transfer. 977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (!((intptr_t)Base & 3)) { 987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.append(Base, Base + Units); 997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Pos = (Units + 1) * 4; 1007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else { 1017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Otherwise do it the hard way. 1027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // To be compatible with above bulk transfer, we need to take endianness 1037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // into account. 1047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost, 1057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Unexpected host endianness"); 1067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (sys::IsBigEndianHost) { 1077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens for (Pos += 4; Pos <= Size; Pos += 4) { 1087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned V = ((unsigned char)String[Pos - 4] << 24) | 1097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ((unsigned char)String[Pos - 3] << 16) | 1107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ((unsigned char)String[Pos - 2] << 8) | 1117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (unsigned char)String[Pos - 1]; 1127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.push_back(V); 1137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else { // Little-endian host 1157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens for (Pos += 4; Pos <= Size; Pos += 4) { 1167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned V = ((unsigned char)String[Pos - 1] << 24) | 1177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ((unsigned char)String[Pos - 2] << 16) | 1187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ((unsigned char)String[Pos - 3] << 8) | 1197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (unsigned char)String[Pos - 4]; 1207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.push_back(V); 1217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // With the leftover bits. 1267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned V = 0; 1277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Pos will have overshot size by 4 - #bytes left over. 1287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // No need to take endianness into account here - this is always executed. 1297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens switch (Pos - Size) { 1307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens case 1: V = (V << 8) | (unsigned char)String[Size - 3]; LLVM_FALLTHROUGH; 1317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens case 2: V = (V << 8) | (unsigned char)String[Size - 2]; LLVM_FALLTHROUGH; 1327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 1337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens default: return; // Nothing left. 1347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.push_back(V); 1377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// AddNodeID - Adds the Bit data of another ID to *this. 1407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { 1417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Bits.append(ID.Bits.begin(), ID.Bits.end()); 1427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 1457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// lookup the node in the FoldingSetImpl. 1467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensunsigned FoldingSetNodeID::ComputeHash() const { 1477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); 1487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// operator== - Used to compare two nodes to each other. 1517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 1527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const { 1537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); 1547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// operator== - Used to compare two nodes to each other. 1577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 1587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const { 1597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS; 1607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Used to compare the "ordering" of two nodes as defined by the 1637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// profiled bits and their ordering defined by memcmp(). 1647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const { 1657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); 1667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const { 1697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS; 1707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Intern - Copy this node's data to a memory region allocated from the 1737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// given allocator and return a FoldingSetNodeIDRef describing the 1747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// interned data. 1757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetNodeIDRef 1767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { 1777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned *New = Allocator.Allocate<unsigned>(Bits.size()); 1787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::uninitialized_copy(Bits.begin(), Bits.end(), New); 1797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return FoldingSetNodeIDRef(New, Bits.size()); 1807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 1837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Helper functions for FoldingSetImpl. 1847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// GetNextPtr - In order to save space, each bucket is a 1867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// singly-linked-list. In order to make deletion more efficient, we make 1877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// the list circular, so we can delete a node without computing its hash. 1887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// The problem with this is that the start of the hash buckets are not 1897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: 1907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// use GetBucketPtr when this happens. 1917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstatic FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { 1927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // The low bit is set if this is the pointer back to the bucket. 1937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) 1947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return nullptr; 1957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr); 1977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// testing. 2017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstatic void **GetBucketPtr(void *NextInBucketPtr) { 2027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); 2037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert((Ptr & 1) && "Not a bucket pointer"); 2047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); 2057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// GetBucketFor - Hash the specified node ID and return the hash bucket for 2087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// the specified ID. 2097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstatic void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) { 2107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // NumBuckets is always a power of 2. 2117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned BucketNum = Hash & (NumBuckets-1); 2127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return Buckets + BucketNum; 2137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// AllocateBuckets - Allocated initialized bucket memory. 2167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstatic void **AllocateBuckets(unsigned NumBuckets) { 2177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*))); 2187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Set the very last bucket to be a non-null "pointer". 2197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 2207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return Buckets; 2217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 2247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// FoldingSetImpl Implementation 2257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetImpl::anchor() {} 2277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { 2297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(5 < Log2InitSize && Log2InitSize < 32 && 2307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Initial hash table size out of range"); 2317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets = 1 << Log2InitSize; 2327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Buckets = AllocateBuckets(NumBuckets); 2337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumNodes = 0; 2347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetImpl::FoldingSetImpl(FoldingSetImpl &&Arg) 2377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) { 2387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Arg.Buckets = nullptr; 2397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Arg.NumBuckets = 0; 2407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Arg.NumNodes = 0; 2417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetImpl &FoldingSetImpl::operator=(FoldingSetImpl &&RHS) { 2447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens free(Buckets); // This may be null if the set is in a moved-from state. 2457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Buckets = RHS.Buckets; 2467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets = RHS.NumBuckets; 2477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumNodes = RHS.NumNodes; 2487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens RHS.Buckets = nullptr; 2497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens RHS.NumBuckets = 0; 2507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens RHS.NumNodes = 0; 2517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this; 2527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetImpl::~FoldingSetImpl() { 2557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens free(Buckets); 2567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetImpl::clear() { 2597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Set all but the last bucket to null pointers. 2607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens memset(Buckets, 0, NumBuckets*sizeof(void*)); 2617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Set the very last bucket to be a non-null "pointer". 2637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 2647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Reset the node count to zero. 2667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumNodes = 0; 2677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetImpl::GrowBucketCount(unsigned NewBucketCount) { 2707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount"); 2717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!"); 2727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void **OldBuckets = Buckets; 2737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned OldNumBuckets = NumBuckets; 2747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets = NewBucketCount; 2757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Clear out new buckets. 2777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Buckets = AllocateBuckets(NumBuckets); 2787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumNodes = 0; 2797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Walk the old buckets, rehashing nodes into their new place. 2817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens FoldingSetNodeID TempID; 2827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens for (unsigned i = 0; i != OldNumBuckets; ++i) { 2837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *Probe = OldBuckets[i]; 2847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (!Probe) continue; 2857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (Node *NodeInBucket = GetNextPtr(Probe)) { 2867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Figure out the next link, remove NodeInBucket from the old link. 2877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Probe = NodeInBucket->getNextInBucket(); 2887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodeInBucket->SetNextInBucket(nullptr); 2897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Insert the node into the new bucket, after recomputing the hash. 2917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens InsertNode(NodeInBucket, 2927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), 2937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Buckets, NumBuckets)); 2947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TempID.clear(); 2957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens free(OldBuckets); 2997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 3007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// GrowHashTable - Double the size of the hash table and rehash everything. 3027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 3037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetImpl::GrowHashTable() { 3047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens GrowBucketCount(NumBuckets * 2); 3057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 3067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetImpl::reserve(unsigned EltCount) { 3087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // This will give us somewhere between EltCount / 2 and 3097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // EltCount buckets. This puts us in the load factor 3107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // range of 1.0 - 2.0. 3117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if(EltCount < capacity()) 3127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return; 3137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens GrowBucketCount(PowerOf2Floor(EltCount)); 3147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 3157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 3177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// return it. If not, return the insertion token that will make insertion 3187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// faster. 3197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetImpl::Node 3207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, 3217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *&InsertPos) { 3227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned IDHash = ID.ComputeHash(); 3237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets); 3247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *Probe = *Bucket; 3257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens InsertPos = nullptr; 3277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens FoldingSetNodeID TempID; 3297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (Node *NodeInBucket = GetNextPtr(Probe)) { 3307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (NodeEquals(NodeInBucket, ID, IDHash, TempID)) 3317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return NodeInBucket; 3327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TempID.clear(); 3337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Probe = NodeInBucket->getNextInBucket(); 3357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 3367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Didn't find the node, return null with the bucket as the InsertPos. 3387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens InsertPos = Bucket; 3397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return nullptr; 3407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 3417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// InsertNode - Insert the specified node into the folding set, knowing that it 3437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// is not already in the map. InsertPos must be obtained from 3447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// FindNodeOrInsertPos. 3457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { 3467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(!N->getNextInBucket()); 3477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Do we need to grow the hashtable? 3487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (NumNodes+1 > capacity()) { 3497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens GrowHashTable(); 3507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens FoldingSetNodeID TempID; 3517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); 3527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 3537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++NumNodes; 3557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// The insert position is actually a bucket pointer. 3577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void **Bucket = static_cast<void**>(InsertPos); 3587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *Next = *Bucket; 3607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If this is the first insertion into this bucket, its next pointer will be 3627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // null. Pretend as if it pointed to itself, setting the low bit to indicate 3637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // that it is a pointer to the bucket. 3647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (!Next) 3657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); 3667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Set the node's next pointer, and make the bucket point to the node. 3687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens N->SetNextInBucket(Next); 3697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens *Bucket = N; 3707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 3717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// RemoveNode - Remove a node from the folding set, returning true if one was 3737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// removed or false if the node was not in the folding set. 3747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool FoldingSetImpl::RemoveNode(Node *N) { 3757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Because each bucket is a circular list, we don't need to compute N's hash 3767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // to remove it. 3777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *Ptr = N->getNextInBucket(); 3787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (!Ptr) return false; // Not in folding set. 3797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens --NumNodes; 3817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens N->SetNextInBucket(nullptr); 3827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Remember what N originally pointed to, either a bucket or another node. 3847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *NodeNextPtr = Ptr; 3857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Chase around the list until we find the node (or bucket) which points to N. 3877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (true) { 3887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Node *NodeInBucket = GetNextPtr(Ptr)) { 3897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Advance pointer. 3907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Ptr = NodeInBucket->getNextInBucket(); 3917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // We found a node that points to N, change it to point to N's next node, 3937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // removing N from the list. 3947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Ptr == N) { 3957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodeInBucket->SetNextInBucket(NodeNextPtr); 3967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return true; 3977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 3987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else { 3997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void **Bucket = GetBucketPtr(Ptr); 4007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Ptr = *Bucket; 4017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If we found that the bucket points to N, update the bucket to point to 4037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // whatever is next. 4047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Ptr == N) { 4057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens *Bucket = NodeNextPtr; 4067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return true; 4077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 4087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 4097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 4107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 4117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// GetOrInsertNode - If there is an existing simple Node exactly 4137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// equal to the specified node, return it. Otherwise, insert 'N' and it 4147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// instead. 4157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 4167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens FoldingSetNodeID ID; 4177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens GetNodeProfile(N, ID); 4187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *IP; 4197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Node *E = FindNodeOrInsertPos(ID, IP)) 4207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return E; 4217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens InsertNode(N, IP); 4227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N; 4237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 4247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 4267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// FoldingSetIteratorImpl Implementation 4277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { 4297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Skip to the first non-null non-self-cycle bucket. 4307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (*Bucket != reinterpret_cast<void*>(-1) && 4317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (!*Bucket || !GetNextPtr(*Bucket))) 4327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++Bucket; 4337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodePtr = static_cast<FoldingSetNode*>(*Bucket); 4357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 4367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid FoldingSetIteratorImpl::advance() { 4387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If there is another link within this bucket, go to it. 4397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void *Probe = NodePtr->getNextInBucket(); 4407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) 4427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodePtr = NextNodeInBucket; 4437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens else { 4447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Otherwise, this is the last link in this bucket. 4457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void **Bucket = GetBucketPtr(Probe); 4467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Skip to the next non-null non-self-cycle bucket. 4487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens do { 4497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++Bucket; 4507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } while (*Bucket != reinterpret_cast<void*>(-1) && 4517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (!*Bucket || !GetNextPtr(*Bucket))); 4527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodePtr = static_cast<FoldingSetNode*>(*Bucket); 4547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 4557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 4567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 4587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// FoldingSetBucketIteratorImpl Implementation 4597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensFoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { 4617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket; 4627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 463