Add hooks to FoldingSetTrait to allow specializations to provide

implementations of equality comparison and hash computation. This
can be used to optimize node lookup by avoiding creating lots of
temporary ID values just for hashing and comparison purposes.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111130 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 52 insertions, 35 deletions

diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp
index c1b6511a93..4da220382d 100644
--- a/lib/Support/FoldingSet.cpp
+++ b/lib/Support/FoldingSet.cpp
@@ -23,6 +23,37 @@
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
+// FoldingSetNodeIDRef Implementation
+
+/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
+/// used to lookup the node in the FoldingSetImpl.
+unsigned FoldingSetNodeIDRef::ComputeHash() const {
+  // This is adapted from SuperFastHash by Paul Hsieh.
+  unsigned Hash = static_cast<unsigned>(Size);
+  for (const unsigned *BP = Data, *E = BP+Size; BP != E; ++BP) {
+    unsigned Data = *BP;
+    Hash         += Data & 0xFFFF;
+    unsigned Tmp  = ((Data >> 16) << 11) ^ Hash;
+    Hash          = (Hash << 16) ^ Tmp;
+    Hash         += Hash >> 11;
+  }
+  
+  // Force "avalanching" of final 127 bits.
+  Hash ^= Hash << 3;
+  Hash += Hash >> 5;
+  Hash ^= Hash << 4;
+  Hash += Hash >> 17;
+  Hash ^= Hash << 25;
+  Hash += Hash >> 6;
+  return Hash;
+}
+
+bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
+  if (Size != RHS.Size) return false;
+  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
+}
+
+//===----------------------------------------------------------------------===//
 // FoldingSetNodeID Implementation
 
 /// Add* - Add various data types to Bit data.
@@ -104,31 +135,19 @@ void FoldingSetNodeID::AddString(StringRef String) {
 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 
 /// lookup the node in the FoldingSetImpl.
 unsigned FoldingSetNodeID::ComputeHash() const {
-  // This is adapted from SuperFastHash by Paul Hsieh.
-  unsigned Hash = static_cast<unsigned>(Bits.size());
-  for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) {
-    unsigned Data = *BP;
-    Hash         += Data & 0xFFFF;
-    unsigned Tmp  = ((Data >> 16) << 11) ^ Hash;
-    Hash          = (Hash << 16) ^ Tmp;
-    Hash         += Hash >> 11;
-  }
-  
-  // Force "avalanching" of final 127 bits.
-  Hash ^= Hash << 3;
-  Hash += Hash >> 5;
-  Hash ^= Hash << 4;
-  Hash += Hash >> 17;
-  Hash ^= Hash << 25;
-  Hash += Hash >> 6;
-  return Hash;
+  return FoldingSetNodeIDRef(&Bits[0], Bits.size()).ComputeHash();
 }
 
 /// operator== - Used to compare two nodes to each other.
 ///
 bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{
-  if (Bits.size() != RHS.Bits.size()) return false;
-  return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0;
+  return *this == FoldingSetNodeIDRef(&RHS.Bits[0], RHS.Bits.size());
+}
+
+/// operator== - Used to compare two nodes to each other.
+///
+bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
+  return FoldingSetNodeIDRef(&Bits[0], Bits.size()) == RHS;
 }
 
 /// Intern - Copy this node's data to a memory region allocated from the
@@ -168,10 +187,9 @@ static void **GetBucketPtr(void *NextInBucketPtr) {
 
 /// GetBucketFor - Hash the specified node ID and return the hash bucket for
 /// the specified ID.
-static void **GetBucketFor(const FoldingSetNodeID &ID,
-                           void **Buckets, unsigned NumBuckets) {
+static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
   // NumBuckets is always a power of 2.
-  unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
+  unsigned BucketNum = Hash & (NumBuckets-1);
   return Buckets + BucketNum;
 }
 
@@ -219,7 +237,7 @@ void FoldingSetImpl::GrowHashTable() {
   NumNodes = 0;
 
   // Walk the old buckets, rehashing nodes into their new place.
-  FoldingSetNodeID ID;
+  FoldingSetNodeID TempID;
   for (unsigned i = 0; i != OldNumBuckets; ++i) {
     void *Probe = OldBuckets[i];
     if (!Probe) continue;
@@ -229,9 +247,10 @@ void FoldingSetImpl::GrowHashTable() {
       NodeInBucket->SetNextInBucket(0);
 
       // Insert the node into the new bucket, after recomputing the hash.
-      GetNodeProfile(NodeInBucket, ID);
-      InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets));
-      ID.clear();
+      InsertNode(NodeInBucket,
+                 GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
+                              Buckets, NumBuckets));
+      TempID.clear();
     }
   }
   
@@ -245,19 +264,18 @@ FoldingSetImpl::Node
 *FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
                                      void *&InsertPos) {
   
-  void **Bucket = GetBucketFor(ID, Buckets, NumBuckets);
+  void **Bucket = GetBucketFor(ID.ComputeHash(), Buckets, NumBuckets);
   void *Probe = *Bucket;
   
   InsertPos = 0;
   
-  FoldingSetNodeID OtherID;
+  FoldingSetNodeID TempID;
   while (Node *NodeInBucket = GetNextPtr(Probe)) {
-    GetNodeProfile(NodeInBucket, OtherID);
-    if (OtherID == ID)
+    if (NodeEquals(NodeInBucket, ID, TempID))
       return NodeInBucket;
+    TempID.clear();
 
     Probe = NodeInBucket->getNextInBucket();
-    OtherID.clear();
   }
   
   // Didn't find the node, return null with the bucket as the InsertPos.
@@ -273,9 +291,8 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
   // Do we need to grow the hashtable?
   if (NumNodes+1 > NumBuckets*2) {
     GrowHashTable();
-    FoldingSetNodeID ID;
-    GetNodeProfile(N, ID);
-    InsertPos = GetBucketFor(ID, Buckets, NumBuckets);
+    FoldingSetNodeID TempID;
+    InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
   }
 
   ++NumNodes;