X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fsmall_vector.h;h=132ff241ee51621e8b3900ee7e7c4e9d449bff29;hb=dd280141ac92814bed18aad661411a89c6b9ccda;hp=a339e138cdf9f070a7d345e9b30deab93fa93fa0;hpb=22afce906d7e98d95f8c45c3301072d9fd891d41;p=folly.git

diff --git a/folly/small_vector.h b/folly/small_vector.h
index a339e138..132ff241 100644
--- a/folly/small_vector.h
+++ b/folly/small_vector.h
@@ -15,14 +15,15 @@
  */
 
 /*
- * For high-level documentation and usage examples see folly/doc/small_vector.md
+ * For high-level documentation and usage examples see
+ * folly/docs/small_vector.md
  *
  * @author Jordan DeLong <delong.j@fb.com>
  */
 #ifndef FOLLY_SMALL_VECTOR_H_
 #define FOLLY_SMALL_VECTOR_H_
 
-#include "Portability.h"
+#include <folly/Portability.h>
 
 #include <stdexcept>
 #include <cstdlib>
@@ -45,13 +46,17 @@
 #include <boost/mpl/count.hpp>
 #include <boost/mpl/max.hpp>
 
-#include "folly/Malloc.h"
+#include <folly/Malloc.h>
 
-#if defined(__GNUC__) && defined(__x86_64__)
-# include "folly/SmallLocks.h"
-# define FB_PACKED __attribute__((packed))
+#if defined(__GNUC__) && FOLLY_X64
+# include <folly/SmallLocks.h>
+# define FB_PACK_ATTR FOLLY_PACK_ATTR
+# define FB_PACK_PUSH FOLLY_PACK_PUSH
+# define FB_PACK_POP FOLLY_PACK_POP
 #else
-# define FB_PACKED
+# define FB_PACK_ATTR
+# define FB_PACK_PUSH
+# define FB_PACK_POP
 #endif
 
 #if FOLLY_HAVE_MALLOC_SIZE
@@ -82,21 +87,6 @@ namespace small_vector_policy {
  */
 struct NoHeap;
 
-/*
- * Passing this policy will cause small_vector to provide lock() and
- * unlock() functions using a 1-bit spin lock in the size value.
- *
- * Note that this is intended for a fairly specialized (although
- * strangely common at facebook) use case, where you have billions of
- * vectors in memory where none of them are "hot" and most of them are
- * small.  This allows you to get fine-grained locks without spending
- * a lot of memory on mutexes (the alternative of a large hashtable of
- * locks leads to extra cache misses in the lookup path).
- *
- * __x86_64__ only.
- */
-struct OneBitMutex;
-
 //////////////////////////////////////////////////////////////////////
 
 } // small_vector_policy
@@ -227,7 +217,7 @@ namespace detail {
     IntegralSizePolicy() : size_(0) {}
 
   protected:
-    std::size_t policyMaxSize() const {
+    static constexpr std::size_t policyMaxSize() {
       return SizeType(~kExternMask);
     }
 
@@ -267,65 +257,6 @@ namespace detail {
     SizeType size_;
   };
 
-#ifdef __x86_64__
-  template<class SizeType, bool ShouldUseHeap>
-  struct OneBitMutexImpl {
-    typedef SizeType InternalSizeType;
-
-    OneBitMutexImpl() { psl_.init(); }
-
-    void lock()     const { psl_.lock(); }
-    void unlock()   const { psl_.unlock(); }
-    bool try_lock() const { return psl_.try_lock(); }
-
-  protected:
-    static bool const kShouldUseHeap = ShouldUseHeap;
-
-    std::size_t policyMaxSize() const {
-      return SizeType(~(SizeType(1) << kLockBit | kExternMask));
-    }
-
-    std::size_t doSize() const {
-      return psl_.getData() & ~kExternMask;
-    }
-
-    std::size_t isExtern() const {
-      return psl_.getData() & kExternMask;
-    }
-
-    void setExtern(bool b) {
-      if (b) {
-        setSize(SizeType(doSize()) | kExternMask);
-      } else {
-        setSize(SizeType(doSize()) & ~kExternMask);
-      }
-    }
-
-    void setSize(std::size_t sz) {
-      assert(sz < (std::size_t(1) << kLockBit));
-      psl_.setData((kExternMask & psl_.getData()) | SizeType(sz));
-    }
-
-    void swapSizePolicy(OneBitMutexImpl& o) {
-      std::swap(psl_, o.psl_);
-    }
-
-  private:
-    static SizeType const kLockBit = sizeof(SizeType) * 8 - 1;
-    static SizeType const kExternMask =
-      kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 2)
-                     : 0;
-
-    PicoSpinLock<SizeType,kLockBit> psl_;
-  };
-#else
-  template<class SizeType, bool ShouldUseHeap>
-  struct OneBitMutexImpl {
-    static_assert(std::is_same<SizeType,void>::value,
-                  "OneBitMutex only works on x86-64");
-  };
-#endif
-
   /*
    * If you're just trying to use this class, ignore everything about
    * this next small_vector_base class thing.
@@ -365,17 +296,6 @@ namespace detail {
                     mpl::size<Integrals>::value == 1,
                   "Multiple size types specified in small_vector<>");
 
-    /*
-     * Figure out if we're supposed to supply a one-bit mutex. :)
-     */
-    typedef typename mpl::count<
-      PolicyList,small_vector_policy::OneBitMutex
-    >::type HasMutex;
-
-    static_assert(HasMutex::value == 0 || HasMutex::value == 1,
-                  "Multiple copies of small_vector_policy::OneBitMutex "
-                  "supplied; this is probably a mistake");
-
     /*
      * Determine whether we should allow spilling to the heap or not.
      */
@@ -390,11 +310,8 @@ namespace detail {
     /*
      * Make the real policy base classes.
      */
-    typedef typename mpl::if_<
-      HasMutex,
-      OneBitMutexImpl<SizeType,!HasNoHeap::value>,
-      IntegralSizePolicy<SizeType,!HasNoHeap::value>
-    >::type ActualSizePolicy;
+    typedef IntegralSizePolicy<SizeType,!HasNoHeap::value>
+      ActualSizePolicy;
 
     /*
      * Now inherit from them all.  This is done in such a convoluted
@@ -426,7 +343,7 @@ namespace detail {
 }
 
 //////////////////////////////////////////////////////////////////////
-
+FB_PACK_PUSH
 template<class Value,
          std::size_t RequestedMaxInline    = 1,
          class PolicyA                     = void,
@@ -455,7 +372,7 @@ class small_vector
   };
 
 public:
-  typedef std::size_t size_type;
+  typedef std::size_t        size_type;
   typedef Value              value_type;
   typedef value_type&        reference;
   typedef value_type const&  const_reference;
@@ -469,11 +386,29 @@ public:
   explicit small_vector() {}
 
   small_vector(small_vector const& o) {
-    assign(o.begin(), o.end());
+    auto n = o.size();
+    makeSize(n);
+    try {
+      std::uninitialized_copy(o.begin(), o.end(), begin());
+    } catch (...) {
+      if (this->isExtern()) {
+        u.freeHeap();
+      }
+      throw;
+    }
+    this->setSize(n);
   }
 
-  small_vector(small_vector&& o) {
-    *this = std::move(o);
+  small_vector(small_vector&& o)
+  noexcept(std::is_nothrow_move_constructible<Value>::value) {
+    if (o.isExtern()) {
+      swap(o);
+    } else {
+      std::uninitialized_copy(std::make_move_iterator(o.begin()),
+                              std::make_move_iterator(o.end()),
+                              begin());
+      this->setSize(o.size());
+    }
   }
 
   small_vector(std::initializer_list<value_type> il) {
@@ -507,16 +442,11 @@ public:
   }
 
   small_vector& operator=(small_vector&& o) {
+    // TODO: optimization:
+    // if both are internal, use move assignment where possible
+    if (this == &o) return *this;
     clear();
-    if (!o.isExtern()) {
-      makeSize(o.size());
-      for (std::size_t i = 0; i < o.size(); ++i) {
-        new (data() + i) value_type(std::move(o[i]));
-      }
-      this->setSize(o.size());
-    } else {
-      swap(o);
-    }
+    swap(o);
     return *this;
   }
 
@@ -528,9 +458,9 @@ public:
     return std::lexicographical_compare(begin(), end(), o.begin(), o.end());
   }
 
-  size_type max_size() const {
+  static constexpr size_type max_size() {
     return !BaseType::kShouldUseHeap ? MaxInline
-                                     : this->policyMaxSize();
+                                     : BaseType::policyMaxSize();
   }
 
   size_type size()         const { return this->doSize(); }
@@ -591,19 +521,23 @@ public:
       }
 
       size_type i = oldSmall.size();
+      const size_type ci = i;
       try {
         for (; i < oldLarge.size(); ++i) {
-          new (&oldSmall[i]) value_type(std::move(oldLarge[i]));
+          auto addr = oldSmall.begin() + i;
+          new (addr) value_type(std::move(oldLarge[i]));
           oldLarge[i].~value_type();
         }
       } catch (...) {
+        oldSmall.setSize(i);
         for (; i < oldLarge.size(); ++i) {
           oldLarge[i].~value_type();
         }
-        oldLarge.setSize(oldSmall.size());
+        oldLarge.setSize(ci);
         throw;
       }
-      this->swapSizePolicy(o);
+      oldSmall.setSize(i);
+      oldLarge.setSize(ci);
       return;
     }
 
@@ -806,8 +740,9 @@ public:
   }
 
   iterator erase(const_iterator q1, const_iterator q2) {
+    if (q1 == q2) return unconst(q1);
     std::move(unconst(q2), end(), unconst(q1));
-    for (auto it = q1; it != end(); ++it) {
+    for (auto it = (end() - std::distance(q1, q2)); it != end(); ++it) {
       it->~value_type();
     }
     this->setSize(size() - (q2 - q1));
@@ -945,18 +880,31 @@ private:
     auto distance = std::distance(first, last);
     makeSize(distance);
     this->setSize(distance);
-
-    detail::populateMemForward(data(), distance,
-      [&] (void* p) { new (p) value_type(*first++); }
-    );
+    try {
+      detail::populateMemForward(data(), distance,
+        [&] (void* p) { new (p) value_type(*first++); }
+      );
+    } catch (...) {
+      if (this->isExtern()) {
+        u.freeHeap();
+      }
+      throw;
+    }
   }
 
   void doConstruct(size_type n, value_type const& val) {
     makeSize(n);
     this->setSize(n);
-    detail::populateMemForward(data(), n,
-      [&] (void* p) { new (p) value_type(val); }
-    );
+    try {
+      detail::populateMemForward(data(), n,
+        [&] (void* p) { new (p) value_type(val); }
+      );
+    } catch (...) {
+      if (this->isExtern()) {
+        u.freeHeap();
+      }
+      throw;
+    }
   }
 
   // The true_type means we should forward to the size_t,value_type
@@ -965,7 +913,7 @@ private:
     doConstruct(n, val);
   }
 
-  void makeSize(size_type size, value_type* v = NULL) {
+  void makeSize(size_type size, value_type* v = nullptr) {
     makeSize(size, v, size - 1);
   }
 
@@ -1008,7 +956,7 @@ private:
         detail::shiftPointer(newh, kHeapifyCapacitySize) :
         newh);
 
-    if (v != NULL) {
+    if (v != nullptr) {
       // move new element
       try {
         new (&newp[pos]) value_type(std::move(*v));
@@ -1085,7 +1033,7 @@ private:
     InternalSizeType* getCapacity() {
       return &capacity_;
     }
-  } FB_PACKED;
+  } FB_PACK_ATTR;
 
   struct HeapPtr {
     // Lower order bit of heap_ is used as flag to indicate whether capacity is
@@ -1097,9 +1045,9 @@ private:
       return static_cast<InternalSizeType*>(
         detail::pointerFlagClear(heap_));
     }
-  } FB_PACKED;
+  } FB_PACK_ATTR;
 
-#if defined(__x86_64_)
+#if FOLLY_X64
   typedef unsigned char InlineStorageType[sizeof(value_type) * MaxInline];
 #else
   typedef typename std::aligned_storage<
@@ -1166,8 +1114,9 @@ private:
       auto vp = detail::pointerFlagClear(pdata_.heap_);
       free(vp);
     }
-  } FB_PACKED u;
-} FB_PACKED;
+  } FB_PACK_ATTR u;
+} FB_PACK_ATTR;
+FB_PACK_POP
 
 //////////////////////////////////////////////////////////////////////
 
@@ -1185,8 +1134,10 @@ void swap(small_vector<T,MaxInline,A,B,C>& a,
 
 #pragma GCC diagnostic pop
 
-#ifdef FB_PACKED
-# undef FB_PACKED
+#ifdef FB_PACK_ATTR
+# undef FB_PACK_ATTR
+# undef FB_PACK_PUSH
+# undef FB_PACK_POP
 #endif
 
 #endif