+/*
+ * Move objects in memory to the right into some uninitialized
+ * memory, where the region overlaps. This doesn't just use
+ * std::move_backward because move_backward only works if all the
+ * memory is initialized to type T already.
+ */
+template <class T>
+typename std::enable_if<!FOLLY_IS_TRIVIALLY_COPYABLE(T)>::type
+moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
+ if (lastConstructed == realLast) {
+ return;
+ }
+
+ T* end = first - 1; // Past the end going backwards.
+ T* out = realLast - 1;
+ T* in = lastConstructed - 1;
+ try {
+ for (; in != end && out >= lastConstructed; --in, --out) {
+ new (out) T(std::move(*in));
+ }
+ for (; in != end; --in, --out) {
+ *out = std::move(*in);
+ }
+ for (; out >= lastConstructed; --out) {
+ new (out) T();
+ }
+ } catch (...) {
+ // We want to make sure the same stuff is uninitialized memory
+ // if we exit via an exception (this is to make sure we provide
+ // the basic exception safety guarantee for insert functions).
+ if (out < lastConstructed) {
+ out = lastConstructed - 1;
+ }
+ for (auto it = out + 1; it != realLast; ++it) {
+ it->~T();
+ }
+ throw;
+ }
+}
+
+// Specialization for trivially copyable types. The call to
+// std::move_backward here will just turn into a memmove. (TODO:
+// change to std::is_trivially_copyable when that works.)
+template <class T>
+typename std::enable_if<FOLLY_IS_TRIVIALLY_COPYABLE(T)>::type
+moveObjectsRight(T* first, T* lastConstructed, T* realLast) {
+ std::move_backward(first, lastConstructed, realLast);
+}
+
+/*
+ * Populate a region of memory using `op' to construct elements. If
+ * anything throws, undo what we did.
+ */
+template <class T, class Function>
+void populateMemForward(T* mem, std::size_t n, Function const& op) {
+ std::size_t idx = 0;
+ try {
+ for (size_t i = 0; i < n; ++i) {
+ op(&mem[idx]);
+ ++idx;
+ }
+ } catch (...) {
+ for (std::size_t i = 0; i < idx; ++i) {
+ mem[i].~T();
+ }
+ throw;
+ }
+}
+
+template <class SizeType, bool ShouldUseHeap>
+struct IntegralSizePolicyBase {
+ typedef SizeType InternalSizeType;
+
+ IntegralSizePolicyBase() : size_(0) {}
+
+ protected:
+ static constexpr std::size_t policyMaxSize() {
+ return SizeType(~kExternMask);
+ }
+
+ std::size_t doSize() const {
+ return size_ & ~kExternMask;
+ }
+
+ std::size_t isExtern() const {
+ return kExternMask & size_;
+ }
+
+ void setExtern(bool b) {
+ if (b) {
+ size_ |= kExternMask;
+ } else {
+ size_ &= ~kExternMask;
+ }
+ }
+
+ void setSize(std::size_t sz) {
+ assert(sz <= policyMaxSize());
+ size_ = (kExternMask & size_) | SizeType(sz);
+ }
+
+ void swapSizePolicy(IntegralSizePolicyBase& o) {
+ std::swap(size_, o.size_);
+ }
+
+ protected:
+ static bool constexpr kShouldUseHeap = ShouldUseHeap;
+
+ private:
+ static SizeType constexpr kExternMask =
+ kShouldUseHeap ? SizeType(1) << (sizeof(SizeType) * 8 - 1) : 0;
+
+ SizeType size_;
+};
+
+template <class SizeType, bool ShouldUseHeap>
+struct IntegralSizePolicy;
+
+template <class SizeType>
+struct IntegralSizePolicy<SizeType, true>
+ : public IntegralSizePolicyBase<SizeType, true> {
+ public: