FoldingSet.cpp revision abe24cf037553755df052bbc11c18ad288607849
1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===// 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// The LLVM Compiler Infrastructure 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This file is distributed under the University of Illinois Open Source 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// License. See LICENSE.TXT for details. 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This file implements a hash set that can be used to remove duplication of 11436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// nodes in a graph. This code was originally created by Chris Lattner for use 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// with SelectionDAGCSEMap, but was isolated to provide use across the llvm code 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// set. 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/ADT/FoldingSet.h" 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/ADT/Hashing.h" 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Support/Allocator.h" 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Support/ErrorHandling.h" 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Support/MathExtras.h" 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Support/Host.h" 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <cassert> 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <cstring> 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownusing namespace llvm; 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// FoldingSetNodeIDRef Implementation 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// used to lookup the node in the FoldingSetImpl. 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownunsigned FoldingSetNodeIDRef::ComputeHash() const { 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return static_cast<unsigned>(hash_combine_range(Data, Data+Size)); 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const { 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Size != RHS.Size) return false; 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0; 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// FoldingSetNodeID Implementation 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 44436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/// Add* - Add various data types to Bit data. 45436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/// 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddPointer(const void *Ptr) { 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Note: this adds pointers to the hash using sizes and endianness that 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // depend on the host. It doesn't matter however, because hashing on 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // pointer values in inherently unstable. Nothing should depend on the 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // ordering of nodes in the folding set. 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.append(reinterpret_cast<unsigned *>(&Ptr), 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown reinterpret_cast<unsigned *>(&Ptr+1)); 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddInteger(signed I) { 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.push_back(I); 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddInteger(unsigned I) { 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.push_back(I); 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddInteger(long I) { 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AddInteger((unsigned long)I); 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddInteger(unsigned long I) { 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sizeof(long) == sizeof(int)) 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AddInteger(unsigned(I)); 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (sizeof(long) == sizeof(long long)) { 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AddInteger((unsigned long long)I); 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown llvm_unreachable("unexpected sizeof(long)"); 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddInteger(long long I) { 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AddInteger((unsigned long long)I); 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 75436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid FoldingSetNodeID::AddInteger(unsigned long long I) { 76436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov AddInteger(unsigned(I)); 77436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if ((uint64_t)(unsigned)I != I) 78436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Bits.push_back(unsigned(I >> 32)); 79436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddString(StringRef String) { 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned Size = String.size(); 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.push_back(Size); 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!Size) return; 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned Units = Size / 4; 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned Pos = 0; 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const unsigned *Base = (const unsigned*) String.data(); 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // If the string is aligned do a bulk transfer. 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!((intptr_t)Base & 3)) { 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.append(Base, Base + Units); 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Pos = (Units + 1) * 4; 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 95436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov // Otherwise do it the hard way. 96eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // To be compatible with above bulk transfer, we need to take endianness 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // into account. 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sys::isBigEndianHost()) { 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (Pos += 4; Pos <= Size; Pos += 4) { 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned V = ((unsigned char)String[Pos - 4] << 24) | 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((unsigned char)String[Pos - 3] << 16) | 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((unsigned char)String[Pos - 2] << 8) | 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (unsigned char)String[Pos - 1]; 104436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Bits.push_back(V); 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(sys::isLittleEndianHost() && "Unexpected host endianness"); 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (Pos += 4; Pos <= Size; Pos += 4) { 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned V = ((unsigned char)String[Pos - 1] << 24) | 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((unsigned char)String[Pos - 2] << 16) | 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((unsigned char)String[Pos - 3] << 8) | 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (unsigned char)String[Pos - 4]; 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.push_back(V); 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // With the leftover bits. 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned V = 0; 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Pos will have overshot size by 4 - #bytes left over. 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // No need to take endianness into account here - this is always executed. 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch (Pos - Size) { 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown default: return; // Nothing left. 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.push_back(V); 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// AddNodeID - Adds the Bit data of another ID to *this. 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) { 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bits.append(ID.Bits.begin(), ID.Bits.end()); 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// lookup the node in the FoldingSetImpl. 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownunsigned FoldingSetNodeID::ComputeHash() const { 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// operator== - Used to compare two nodes to each other. 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{ 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size()); 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// operator== - Used to compare two nodes to each other. 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const { 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS; 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// Intern - Copy this node's data to a memory region allocated from the 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// given allocator and return a FoldingSetNodeIDRef describing the 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// interned data. 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetNodeIDRef 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const { 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned *New = Allocator.Allocate<unsigned>(Bits.size()); 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown std::uninitialized_copy(Bits.begin(), Bits.end(), New); 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return FoldingSetNodeIDRef(New, Bits.size()); 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// Helper functions for FoldingSetImpl. 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// GetNextPtr - In order to save space, each bucket is a 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// singly-linked-list. In order to make deletion more efficient, we make 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// the list circular, so we can delete a node without computing its hash. 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// The problem with this is that the start of the hash buckets are not 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// use GetBucketPtr when this happens. 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // The low bit is set if this is the pointer back to the bucket. 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr); 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// testing. 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void **GetBucketPtr(void *NextInBucketPtr) { 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert((Ptr & 1) && "Not a bucket pointer"); 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// GetBucketFor - Hash the specified node ID and return the hash bucket for 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// the specified ID. 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) { 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // NumBuckets is always a power of 2. 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned BucketNum = Hash & (NumBuckets-1); 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return Buckets + BucketNum; 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// AllocateBuckets - Allocated initialized bucket memory. 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void **AllocateBuckets(unsigned NumBuckets) { 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*))); 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Set the very last bucket to be a non-null "pointer". 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return Buckets; 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// FoldingSetImpl Implementation 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(5 < Log2InitSize && Log2InitSize < 32 && 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown "Initial hash table size out of range"); 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NumBuckets = 1 << Log2InitSize; 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Buckets = AllocateBuckets(NumBuckets); 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NumNodes = 0; 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetImpl::~FoldingSetImpl() { 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown free(Buckets); 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetImpl::clear() { 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Set all but the last bucket to null pointers. 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown memset(Buckets, 0, NumBuckets*sizeof(void*)); 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Set the very last bucket to be a non-null "pointer". 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Reset the node count to zero. 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NumNodes = 0; 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// GrowHashTable - Double the size of the hash table and rehash everything. 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetImpl::GrowHashTable() { 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void **OldBuckets = Buckets; 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned OldNumBuckets = NumBuckets; 235436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov NumBuckets <<= 1; 236436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Clear out new buckets. 238436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Buckets = AllocateBuckets(NumBuckets); 239436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov NumNodes = 0; 240436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 241436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov // Walk the old buckets, rehashing nodes into their new place. 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown FoldingSetNodeID TempID; 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (unsigned i = 0; i != OldNumBuckets; ++i) { 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *Probe = OldBuckets[i]; 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!Probe) continue; 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (Node *NodeInBucket = GetNextPtr(Probe)) { 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Figure out the next link, remove NodeInBucket from the old link. 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Probe = NodeInBucket->getNextInBucket(); 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NodeInBucket->SetNextInBucket(0); 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the node into the new bucket, after recomputing the hash. 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown InsertNode(NodeInBucket, 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown GetBucketFor(ComputeNodeHash(NodeInBucket, TempID), 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Buckets, NumBuckets)); 255436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov TempID.clear(); 256436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown free(OldBuckets); 260436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// return it. If not, return the insertion token that will make insertion 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// faster. 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetImpl::Node 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *&InsertPos) { 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void **Bucket = GetBucketFor(ID.ComputeHash(), Buckets, NumBuckets); 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *Probe = *Bucket; 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown InsertPos = 0; 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown FoldingSetNodeID TempID; 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (Node *NodeInBucket = GetNextPtr(Probe)) { 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (NodeEquals(NodeInBucket, ID, TempID)) 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NodeInBucket; 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown TempID.clear(); 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Probe = NodeInBucket->getNextInBucket(); 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Didn't find the node, return null with the bucket as the InsertPos. 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown InsertPos = Bucket; 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// InsertNode - Insert the specified node into the folding set, knowing that it 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// is not already in the map. InsertPos must be obtained from 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// FindNodeOrInsertPos. 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(N->getNextInBucket() == 0); 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Do we need to grow the hashtable? 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (NumNodes+1 > NumBuckets*2) { 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown GrowHashTable(); 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown FoldingSetNodeID TempID; 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets); 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 299436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 300436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov ++NumNodes; 301436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 302436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /// The insert position is actually a bucket pointer. 303436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov void **Bucket = static_cast<void**>(InsertPos); 304436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 305436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov void *Next = *Bucket; 306436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 307eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // If this is the first insertion into this bucket, its next pointer will be 308eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // null. Pretend as if it pointed to itself, setting the low bit to indicate 309eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // that it is a pointer to the bucket. 310eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (Next == 0) 311eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); 312eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 313eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // Set the node's next pointer, and make the bucket point to the node. 314eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov N->SetNextInBucket(Next); 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *Bucket = N; 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// RemoveNode - Remove a node from the folding set, returning true if one was 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// removed or false if the node was not in the folding set. 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool FoldingSetImpl::RemoveNode(Node *N) { 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Because each bucket is a circular list, we don't need to compute N's hash 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // to remove it. 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *Ptr = N->getNextInBucket(); 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Ptr == 0) return false; // Not in folding set. 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown --NumNodes; 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown N->SetNextInBucket(0); 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Remember what N originally pointed to, either a bucket or another node. 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *NodeNextPtr = Ptr; 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Chase around the list until we find the node (or bucket) which points to N. 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (true) { 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Node *NodeInBucket = GetNextPtr(Ptr)) { 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Advance pointer. 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Ptr = NodeInBucket->getNextInBucket(); 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // We found a node that points to N, change it to point to N's next node, 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // removing N from the list. 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Ptr == N) { 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NodeInBucket->SetNextInBucket(NodeNextPtr); 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return true; 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void **Bucket = GetBucketPtr(Ptr); 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Ptr = *Bucket; 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // If we found that the bucket points to N, update the bucket to point to 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // whatever is next. 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Ptr == N) { 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *Bucket = NodeNextPtr; 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return true; 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// GetOrInsertNode - If there is an existing simple Node exactly 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// equal to the specified node, return it. Otherwise, insert 'N' and it 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// instead. 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown FoldingSetNodeID ID; 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown GetNodeProfile(N, ID); 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *IP; 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Node *E = FindNodeOrInsertPos(ID, IP)) 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return E; 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown InsertNode(N, IP); 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return N; 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// FoldingSetIteratorImpl Implementation 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Skip to the first non-null non-self-cycle bucket. 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*Bucket != reinterpret_cast<void*>(-1) && 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*Bucket == 0 || GetNextPtr(*Bucket) == 0)) 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++Bucket; 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NodePtr = static_cast<FoldingSetNode*>(*Bucket); 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid FoldingSetIteratorImpl::advance() { 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // If there is another link within this bucket, go to it. 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void *Probe = NodePtr->getNextInBucket(); 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NodePtr = NextNodeInBucket; 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else { 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Otherwise, this is the last link in this bucket. 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void **Bucket = GetBucketPtr(Probe); 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Skip to the next non-null non-self-cycle bucket. 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown do { 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++Bucket; 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } while (*Bucket != reinterpret_cast<void*>(-1) && 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NodePtr = static_cast<FoldingSetNode*>(*Bucket); 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// FoldingSetBucketIteratorImpl Implementation 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownFoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket; 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown