unique_ptrify FileOutputBuffer::FileOutputBuffer
[oota-llvm.git] / lib / Support / SmallPtrSet.cpp
index dd516d37f056c64646fd051df62efcb7c5a5f08b..621b90fa75572bfe4c534a90a1238cac24a3a66f 100644 (file)
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cstdlib>
 
 using namespace llvm;
 
-void SmallPtrSetImpl::shrink_and_clear() {
+void SmallPtrSetImplBase::shrink_and_clear() {
   assert(!isSmall() && "Can't shrink a small set!");
   free(CurArray);
 
@@ -28,16 +29,12 @@ void SmallPtrSetImpl::shrink_and_clear() {
   NumElements = NumTombstones = 0;
 
   // Install the new array.  Clear all the buckets to empty.
-  CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1));
+  CurArray = (const void**)malloc(sizeof(void*) * CurArraySize);
   assert(CurArray && "Failed to allocate memory?");
   memset(CurArray, -1, CurArraySize*sizeof(void*));
-  
-  // The end pointer, always valid, is set to a valid element to help the
-  // iterator.
-  CurArray[CurArraySize] = 0;
 }
 
-bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
+bool SmallPtrSetImplBase::insert_imp(const void * Ptr) {
   if (isSmall()) {
     // Check to see if it is already in the set.
     for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
@@ -46,7 +43,7 @@ bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
         return false;
     
     // Nope, there isn't.  If we stay small, just 'pushback' now.
-    if (NumElements < CurArraySize-1) {
+    if (NumElements < CurArraySize) {
       SmallArray[NumElements++] = Ptr;
       return true;
     }
@@ -74,7 +71,7 @@ bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
   return true;
 }
 
-bool SmallPtrSetImpl::erase_imp(const void * Ptr) {
+bool SmallPtrSetImplBase::erase_imp(const void * Ptr) {
   if (isSmall()) {
     // Check to see if it is in the set.
     for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
@@ -101,12 +98,12 @@ bool SmallPtrSetImpl::erase_imp(const void * Ptr) {
   return true;
 }
 
-const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const {
-  unsigned Bucket = Hash(Ptr);
+const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
+  unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
   unsigned ArraySize = CurArraySize;
   unsigned ProbeAmt = 1;
   const void *const *Array = CurArray;
-  const void *const *Tombstone = 0;
+  const void *const *Tombstone = nullptr;
   while (1) {
     // Found Ptr's bucket?
     if (Array[Bucket] == Ptr)
@@ -130,7 +127,7 @@ const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const {
 
 /// Grow - Allocate a larger backing store for the buckets and move it over.
 ///
-void SmallPtrSetImpl::Grow(unsigned NewSize) {
+void SmallPtrSetImplBase::Grow(unsigned NewSize) {
   // Allocate at twice as many buckets, but at least 128.
   unsigned OldSize = CurArraySize;
   
@@ -138,15 +135,11 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) {
   bool WasSmall = isSmall();
   
   // Install the new array.  Clear all the buckets to empty.
-  CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1));
+  CurArray = (const void**)malloc(sizeof(void*) * NewSize);
   assert(CurArray && "Failed to allocate memory?");
   CurArraySize = NewSize;
   memset(CurArray, -1, NewSize*sizeof(void*));
   
-  // The end pointer, always valid, is set to a valid element to help the
-  // iterator.
-  CurArray[NewSize] = 0;
-  
   // Copy over all the elements.
   if (WasSmall) {
     // Small sets store their elements in order.
@@ -170,8 +163,8 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) {
   }
 }
 
-SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage,
-                                 const SmallPtrSetImpl& that) {
+SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
+                                 const SmallPtrSetImplBase& that) {
   SmallArray = SmallStorage;
 
   // If we're becoming small, prepare to insert into our stack space
@@ -179,7 +172,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage,
     CurArray = SmallArray;
   // Otherwise, allocate new heap space (unless we were the same size)
   } else {
-    CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1));
+    CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize);
     assert(CurArray && "Failed to allocate memory?");
   }
   
@@ -187,19 +180,48 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage,
   CurArraySize = that.CurArraySize;
 
   // Copy over the contents from the other set
-  memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
+  memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize);
   
   NumElements = that.NumElements;
   NumTombstones = that.NumTombstones;
 }
 
+SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
+                                         unsigned SmallSize,
+                                         SmallPtrSetImplBase &&that) {
+  SmallArray = SmallStorage;
+
+  // Copy over the basic members.
+  CurArraySize = that.CurArraySize;
+  NumElements = that.NumElements;
+  NumTombstones = that.NumTombstones;
+
+  // When small, just copy into our small buffer.
+  if (that.isSmall()) {
+    CurArray = SmallArray;
+    memcpy(CurArray, that.CurArray, sizeof(void *) * CurArraySize);
+  } else {
+    // Otherwise, we steal the large memory allocation and no copy is needed.
+    CurArray = that.CurArray;
+    that.CurArray = that.SmallArray;
+  }
+
+  // Make the "that" object small and empty.
+  that.CurArraySize = SmallSize;
+  assert(that.CurArray == that.SmallArray);
+  that.NumElements = 0;
+  that.NumTombstones = 0;
+}
+
 /// CopyFrom - implement operator= from a smallptrset that has the same pointer
 /// type, but may have a different small size.
-void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
+void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) {
+  assert(&RHS != this && "Self-copy should be handled by the caller.");
+
   if (isSmall() && RHS.isSmall())
     assert(CurArraySize == RHS.CurArraySize &&
            "Cannot assign sets with different small sizes");
-           
+
   // If we're becoming small, prepare to insert into our stack space
   if (RHS.isSmall()) {
     if (!isSmall())
@@ -208,9 +230,14 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
   // Otherwise, allocate new heap space (unless we were the same size)
   } else if (CurArraySize != RHS.CurArraySize) {
     if (isSmall())
-      CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1));
-    else
-      CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1));
+      CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize);
+    else {
+      const void **T = (const void**)realloc(CurArray,
+                                             sizeof(void*) * RHS.CurArraySize);
+      if (!T)
+        free(CurArray);
+      CurArray = T;
+    }
     assert(CurArray && "Failed to allocate memory?");
   }
   
@@ -218,13 +245,41 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
   CurArraySize = RHS.CurArraySize;
 
   // Copy over the contents from the other set
-  memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1));
+  memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize);
   
   NumElements = RHS.NumElements;
   NumTombstones = RHS.NumTombstones;
 }
 
-void SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) {
+void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
+                                   SmallPtrSetImplBase &&RHS) {
+  assert(&RHS != this && "Self-move should be handled by the caller.");
+
+  if (!isSmall())
+    free(CurArray);
+
+  if (RHS.isSmall()) {
+    // Copy a small RHS rather than moving.
+    CurArray = SmallArray;
+    memcpy(CurArray, RHS.CurArray, sizeof(void*)*RHS.CurArraySize);
+  } else {
+    CurArray = RHS.CurArray;
+    RHS.CurArray = RHS.SmallArray;
+  }
+
+  // Copy the rest of the trivial members.
+  CurArraySize = RHS.CurArraySize;
+  NumElements = RHS.NumElements;
+  NumTombstones = RHS.NumTombstones;
+
+  // Make the RHS small and empty.
+  RHS.CurArraySize = SmallSize;
+  assert(RHS.CurArray == RHS.SmallArray);
+  RHS.NumElements = 0;
+  RHS.NumTombstones = 0;
+}
+
+void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
   if (this == &RHS) return;
 
   // We can only avoid copying elements if neither set is small.
@@ -241,7 +296,8 @@ void SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) {
   // If only RHS is small, copy the small elements into LHS and move the pointer
   // from LHS to RHS.
   if (!this->isSmall() && RHS.isSmall()) {
-    std::copy(RHS.SmallArray, RHS.SmallArray+RHS.NumElements, this->SmallArray);
+    std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize,
+              this->SmallArray);
     std::swap(this->NumElements, RHS.NumElements);
     std::swap(this->CurArraySize, RHS.CurArraySize);
     RHS.CurArray = this->CurArray;
@@ -254,7 +310,7 @@ void SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) {
   // If only LHS is small, copy the small elements into RHS and move the pointer
   // from RHS to LHS.
   if (this->isSmall() && !RHS.isSmall()) {
-    std::copy(this->SmallArray, this->SmallArray+this->NumElements,
+    std::copy(this->SmallArray, this->SmallArray+this->CurArraySize,
               RHS.SmallArray);
     std::swap(RHS.NumElements, this->NumElements);
     std::swap(RHS.CurArraySize, this->CurArraySize);
@@ -268,12 +324,12 @@ void SmallPtrSetImpl::swap(SmallPtrSetImpl &RHS) {
   // Both a small, just swap the small elements.
   assert(this->isSmall() && RHS.isSmall());
   assert(this->CurArraySize == RHS.CurArraySize);
-  unsigned MaxElems = std::max(this->NumElements, RHS.NumElements);
-  std::swap_ranges(this->SmallArray, this->SmallArray+MaxElems, RHS.SmallArray);
+  std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize,
+                   RHS.SmallArray);
   std::swap(this->NumElements, RHS.NumElements);
 }
 
-SmallPtrSetImpl::~SmallPtrSetImpl() {
+SmallPtrSetImplBase::~SmallPtrSetImplBase() {
   if (!isSmall())
     free(CurArray);
 }