Remove attribution from file headers, per discussion on llvmdev.
[oota-llvm.git] / lib / Support / FoldingSet.cpp
index 1bd20145f45ca2d244c675bde71ae6b2655ff07c..ff7fa71c036f40cd342e4519d65ded8d2e881f34 100644 (file)
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by James M. Laskey and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -15,7 +15,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/APFloat.h"
 #include "llvm/Support/MathExtras.h"
+#include <cassert>
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
@@ -39,9 +41,15 @@ void FoldingSetImpl::NodeID::AddInteger(signed I) {
 void FoldingSetImpl::NodeID::AddInteger(unsigned I) {
   Bits.push_back(I);
 }
+void FoldingSetImpl::NodeID::AddInteger(int64_t I) {
+  AddInteger((uint64_t)I);
+}
 void FoldingSetImpl::NodeID::AddInteger(uint64_t I) {
   Bits.push_back(unsigned(I));
-  Bits.push_back(unsigned(I >> 32));
+  
+  // If the integer is small, encode it just as 32-bits.
+  if ((uint64_t)(int)I != I)
+    Bits.push_back(unsigned(I >> 32));
 }
 void FoldingSetImpl::NodeID::AddFloat(float F) {
   Bits.push_back(FloatToBits(F));
@@ -49,6 +57,12 @@ void FoldingSetImpl::NodeID::AddFloat(float F) {
 void FoldingSetImpl::NodeID::AddDouble(double D) {
  AddInteger(DoubleToBits(D));
 }
+void FoldingSetImpl::NodeID::AddAPFloat(const APFloat& apf) {
+  APInt api = apf.convertToAPInt();
+  const uint64_t *p = api.getRawData();
+  for (unsigned i=0; i<api.getNumWords(); i++)
+    AddInteger(*p++);
+}
 void FoldingSetImpl::NodeID::AddString(const std::string &String) {
   unsigned Size = String.size();
   Bits.push_back(Size);
@@ -124,19 +138,22 @@ bool FoldingSetImpl::NodeID::operator==(const FoldingSetImpl::NodeID &RHS)const{
 /// singly-linked-list. In order to make deletion more efficient, we make
 /// the list circular, so we can delete a node without computing its hash.
 /// The problem with this is that the start of the hash buckets are not
-/// Nodes.  If NextInBucketPtr is a bucket pointer, this method returns null
-/// use GetBucketPtr when this happens.
-static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr,
-                                        void **Buckets, unsigned NumBuckets) {
-  if (NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets + NumBuckets)
+/// Nodes.  If NextInBucketPtr is a bucket pointer, this method returns null:
+/// use GetBucketPtr when this happens.
+static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
+  // The low bit is set if this is the pointer back to the bucket.
+  if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
     return 0;
+  
   return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
 }
 
 /// GetBucketPtr - Provides a casting of a bucket pointer for isNode
 /// testing.
 static void **GetBucketPtr(void *NextInBucketPtr) {
-  return static_cast<void**>(NextInBucketPtr);
+  intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
+  assert((Ptr & 1) && "Not a bucket pointer");
+  return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
 }
 
 /// GetBucketFor - Hash the specified node ID and return the hash bucket for
@@ -151,10 +168,15 @@ static void **GetBucketFor(const FoldingSetImpl::NodeID &ID,
 //===----------------------------------------------------------------------===//
 // FoldingSetImpl Implementation
 
-FoldingSetImpl::FoldingSetImpl() : NumNodes(0) {
-  NumBuckets = 64;
-  Buckets = new void*[NumBuckets];
+FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) : NumNodes(0) {
+  assert(5 < Log2InitSize && Log2InitSize < 32 &&
+         "Initial hash table size out of range");
+  NumBuckets = 1 << Log2InitSize;
+  Buckets = new void*[NumBuckets+1];
   memset(Buckets, 0, NumBuckets*sizeof(void*));
+  
+  // Set the very last bucket to be a non-null "pointer".
+  Buckets[NumBuckets] = reinterpret_cast<void*>(-2);
 }
 FoldingSetImpl::~FoldingSetImpl() {
   delete [] Buckets;
@@ -171,14 +193,17 @@ void FoldingSetImpl::GrowHashTable() {
   NumNodes = 0;
   
   // Clear out new buckets.
-  Buckets = new void*[NumBuckets];
+  Buckets = new void*[NumBuckets+1];
   memset(Buckets, 0, NumBuckets*sizeof(void*));
 
+  // Set the very last bucket to be a non-null "pointer".
+  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
+
   // Walk the old buckets, rehashing nodes into their new place.
   for (unsigned i = 0; i != OldNumBuckets; ++i) {
     void *Probe = OldBuckets[i];
     if (!Probe) continue;
-    while (Node *NodeInBucket = GetNextPtr(Probe, OldBuckets, OldNumBuckets)){
+    while (Node *NodeInBucket = GetNextPtr(Probe)) {
       // Figure out the next link, remove NodeInBucket from the old link.
       Probe = NodeInBucket->getNextInBucket();
       NodeInBucket->SetNextInBucket(0);
@@ -203,7 +228,7 @@ FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const NodeID &ID,
   
   InsertPos = 0;
   
-  while (Node *NodeInBucket = GetNextPtr(Probe, Buckets, NumBuckets)) {
+  while (Node *NodeInBucket = GetNextPtr(Probe)) {
     NodeID OtherID;
     GetNodeProfile(OtherID, NodeInBucket);
     if (OtherID == ID)
@@ -221,14 +246,16 @@ FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const NodeID &ID,
 /// is not already in the map.  InsertPos must be obtained from 
 /// FindNodeOrInsertPos.
 void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
-  ++NumNodes;
+  assert(N->getNextInBucket() == 0);
   // Do we need to grow the hashtable?
-  if (NumNodes > NumBuckets*2) {
+  if (NumNodes+1 > NumBuckets*2) {
     GrowHashTable();
     NodeID ID;
     GetNodeProfile(ID, N);
     InsertPos = GetBucketFor(ID, Buckets, NumBuckets);
   }
+
+  ++NumNodes;
   
   /// The insert position is actually a bucket pointer.
   void **Bucket = static_cast<void**>(InsertPos);
@@ -236,11 +263,12 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
   void *Next = *Bucket;
   
   // If this is the first insertion into this bucket, its next pointer will be
-  // null.  Pretend as if it pointed to itself.
+  // null.  Pretend as if it pointed to itself, setting the low bit to indicate
+  // that it is a pointer to the bucket.
   if (Next == 0)
-    Next = Bucket;
+    Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
 
-  // Set the nodes next pointer, and make the bucket point to the node.
+  // Set the node's next pointer, and make the bucket point to the node.
   N->SetNextInBucket(Next);
   *Bucket = N;
 }
@@ -249,17 +277,19 @@ void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
 /// removed or false if the node was not in the folding set.
 bool FoldingSetImpl::RemoveNode(Node *N) {
   // Because each bucket is a circular list, we don't need to compute N's hash
-  // to remove it.  Chase around the list until we find the node (or bucket)
-  // which points to N.
+  // to remove it.
   void *Ptr = N->getNextInBucket();
   if (Ptr == 0) return false;  // Not in folding set.
 
   --NumNodes;
+  N->SetNextInBucket(0);
 
+  // Remember what N originally pointed to, either a bucket or another node.
   void *NodeNextPtr = Ptr;
-  N->SetNextInBucket(0);
+  
+  // Chase around the list until we find the node (or bucket) which points to N.
   while (true) {
-    if (Node *NodeInBucket = GetNextPtr(Ptr, Buckets, NumBuckets)) {
+    if (Node *NodeInBucket = GetNextPtr(Ptr)) {
       // Advance pointer.
       Ptr = NodeInBucket->getNextInBucket();
       
@@ -295,3 +325,34 @@ FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) {
   InsertNode(N, IP);
   return N;
 }
+
+//===----------------------------------------------------------------------===//
+// FoldingSetIteratorImpl Implementation
+
+FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
+  // Skip to the first non-null non-self-cycle bucket.
+  while (*Bucket == 0 || GetNextPtr(*Bucket) == 0)
+    ++Bucket;
+  
+  NodePtr = static_cast<FoldingSetNode*>(*Bucket);
+}
+
+void FoldingSetIteratorImpl::advance() {
+  // If there is another link within this bucket, go to it.
+  void *Probe = NodePtr->getNextInBucket();
+
+  if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
+    NodePtr = NextNodeInBucket;
+  else {
+    // Otherwise, this is the last link in this bucket.  
+    void **Bucket = GetBucketPtr(Probe);
+
+    // Skip to the next non-null non-self-cycle bucket.
+    do {
+      ++Bucket;
+    } while (*Bucket == 0 || GetNextPtr(*Bucket) == 0);
+    
+    NodePtr = static_cast<FoldingSetNode*>(*Bucket);
+  }
+}
+