ImutAVLTree now allocates tree nodes from the BumpPtrAllocator using

[oota-llvm.git] / include / llvm / ADT / SmallVector.h

diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 723cbcdaf0dc817a5744a6c86d6502e22eb03a04..eb2ffb9d8a20502f2e55ed94f1adf187997575ab 100644 (file)
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -14,16 +14,16 @@
 #ifndef LLVM_ADT_SMALLVECTOR_H
 #define LLVM_ADT_SMALLVECTOR_H
 
+#include "llvm/ADT/iterator"
 #include <algorithm>
-#include <iterator>
 #include <memory>
 
 #ifdef _MSC_VER
 namespace std {
+#if _MSC_VER <= 1310
   // Work around flawed VC++ implementation of std::uninitialized_copy.  Define
   // additional overloads so that elements with pointer types are recognized as
   // scalars and not objects, causing bizarre type conversion errors.
-  // FIXME: this hack may or may not be correct for Visual Studio 2005.
   template<class T1, class T2>
   inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) {
     _Scalar_ptr_iterator_tag _Cat;
@@ -35,6 +35,10 @@ namespace std {
     _Scalar_ptr_iterator_tag _Cat;
     return _Cat;
   }
+#else
+// FIXME: It is not clear if the problem is fixed in VS 2005.  What is clear
+// is that the above hack won't work if it wasn't fixed.
+#endif
 }
 #endif
 
@@ -69,7 +73,9 @@ protected:
 public:
   // Default ctor - Initialize to empty.
   SmallVectorImpl(unsigned N)
-    : Begin((T*)&FirstEl), End((T*)&FirstEl), Capacity((T*)&FirstEl+N) {
+    : Begin(reinterpret_cast<T*>(&FirstEl)), 
+      End(reinterpret_cast<T*>(&FirstEl)), 
+      Capacity(reinterpret_cast<T*>(&FirstEl)+N) {
   }
   
   ~SmallVectorImpl() {
@@ -78,24 +84,35 @@ public:
 
     // If this wasn't grown from the inline copy, deallocate the old space.
     if (!isSmall())
-      delete[] (char*)Begin;
+      delete[] reinterpret_cast<char*>(Begin);
   }
   
   typedef size_t size_type;
   typedef T* iterator;
   typedef const T* const_iterator;
+  
+  typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
+  typedef std::reverse_iterator<iterator>  reverse_iterator;
+  
   typedef T& reference;
   typedef const T& const_reference;
 
   bool empty() const { return Begin == End; }
   size_type size() const { return End-Begin; }
-  
+
+  // forward iterator creation methods.
   iterator begin() { return Begin; }
   const_iterator begin() const { return Begin; }
-
   iterator end() { return End; }
   const_iterator end() const { return End; }
   
+  // reverse iterator creation methods.
+  reverse_iterator rbegin()            { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
+  reverse_iterator rend()              { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
+  
+  
   reference operator[](unsigned idx) {
     return Begin[idx];
   }
@@ -143,7 +160,7 @@ public:
       destroy_range(Begin+N, End);
       End = Begin+N;
     } else if (N > size()) {
-      if (Begin+N > Capacity)
+      if (unsigned(Capacity-Begin) < N)
         grow(N);
       construct_range(End, Begin+N, T());
       End = Begin+N;
@@ -155,7 +172,7 @@ public:
       destroy_range(Begin+N, End);
       End = Begin+N;
     } else if (N > size()) {
-      if (Begin+N > Capacity)
+      if (unsigned(Capacity-Begin) < N)
         grow(N);
       construct_range(End, Begin+N, NV);
       End = Begin+N;
@@ -185,7 +202,7 @@ public:
   
   void assign(unsigned NumElts, const T &Elt) {
     clear();
-    if (Begin+NumElts > Capacity)
+    if (unsigned(Capacity-Begin) < NumElts)
       grow(NumElts);
     End = Begin+NumElts;
     construct_range(Begin, End, Elt);
@@ -281,7 +298,8 @@ private:
   /// isSmall - Return true if this is a smallvector which has not had dynamic
   /// memory allocated for it.
   bool isSmall() const {
-    return (void*)Begin == (void*)&FirstEl;
+    return reinterpret_cast<const void*>(Begin) == 
+           reinterpret_cast<const void*>(&FirstEl);
   }
 
   /// grow - double the size of the allocated memory, guaranteeing space for at
@@ -304,8 +322,8 @@ private:
 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 template <typename T>
 void SmallVectorImpl<T>::grow(unsigned MinSize) {
-  unsigned CurCapacity = Capacity-Begin;
-  unsigned CurSize = size();
+  unsigned CurCapacity = unsigned(Capacity-Begin);
+  unsigned CurSize = unsigned(size());
   unsigned NewCapacity = 2*CurCapacity;
   if (NewCapacity < MinSize)
     NewCapacity = MinSize;
@@ -319,7 +337,7 @@ void SmallVectorImpl<T>::grow(unsigned MinSize) {
   
   // If this wasn't grown from the inline copy, deallocate the old space.
   if (!isSmall())
-    delete[] (char*)Begin;
+    delete[] reinterpret_cast<char*>(Begin);
   
   Begin = NewElts;
   End = NewElts+CurSize;
@@ -372,11 +390,15 @@ SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) {
   
   // If we already have sufficient space, assign the common elements, then
   // destroy any excess.
-  unsigned RHSSize = RHS.size();
-  unsigned CurSize = size();
+  unsigned RHSSize = unsigned(RHS.size());
+  unsigned CurSize = unsigned(size());
   if (CurSize >= RHSSize) {
     // Assign common elements.
-    iterator NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
+    iterator NewEnd;
+    if (RHSSize)
+      NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
+    else
+      NewEnd = Begin;
     
     // Destroy excess elements.
     destroy_range(NewEnd, End);
@@ -438,7 +460,7 @@ public:
   SmallVector() : SmallVectorImpl<T>(NumTsAvailable) {
   }
   
-  SmallVector(unsigned Size, const T &Value)
+  explicit SmallVector(unsigned Size, const T &Value = T())
     : SmallVectorImpl<T>(NumTsAvailable) {
     this->reserve(Size);
     while (Size--)
@@ -451,7 +473,8 @@ public:
   }
   
   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) {
-    operator=(RHS);
+    if (!RHS.empty())
+      operator=(RHS);
   }
   
   const SmallVector &operator=(const SmallVector &RHS) {