hphp/util/tiny-vector.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #pragma once
  18
  19 #include <algorithm>
  20 #include <memory>
  21 #include <type_traits>
  22
  23 #include <boost/iterator/iterator_facade.hpp>
  24 #include <folly/lang/Launder.h>
  25 #include <folly/portability/Malloc.h>
  26
  27 #include "hphp/util/alloc.h"
  28 #include "hphp/util/assertions.h"
  29 #include "hphp/util/compact-tagged-ptrs.h"
  30
  31 namespace HPHP {
  32
  33 // Replace with std::is_nothrow_swappable in c++17
  34 namespace tiny_vector_detail {
  35 using std::swap;
  36
  37 template <typename U>
  38 struct is_nothrow_swappable {
  39   static constexpr bool value =
  40     noexcept(swap(std::declval<U&>(), std::declval<U&>()));
  41 };
  42
  43 }
  44
  45 //////////////////////////////////////////////////////////////////////
  46
  47 /*
  48  * Simple, small buffer-optimized sequence of T.
  49  *
  50  * Notes:
  51  *
  52  *    - Unlike std::vector, storage is not guaranteed to be contiguous.
  53  *
  54  *    - Insertion and removal can only happen at the end of the
  55  *      sequence (although you can modify elements anywhere in the
  56  *      sequence).
  57  *
  58  *    - There is no non-const iterator support, and we have forward
  59  *      iterators only.
  60  *
  61  *    - The elements must be nothrow move constructible and nothrow swappable.
  62  *
  63  * Currently, does not invalidate pointers or references to elements
  64  * at indexes less than InternalSize, but we don't want to depend on
  65  * this without documenting it here.  Iterators should be considered
  66  * invalidated after any mutation.
  67  *
  68  * Also: if you have a T*, and the list almost always contains at most
  69  * one element, PointerList is a smaller object so may be preferable
  70  * in that case.  (Unless you want the first element to remain
  71  * accessible inline instead of moved to the heap.)
  72  */
  73
  74 // Allocator interface with an additional `usable_size()` API.
  75 template <typename T>
  76 struct TinyVectorMallocAllocator {
  77   using size_type = std::size_t;
  78   using value_type = T;
  79   template <typename U> struct rebind {
  80     using other = TinyVectorMallocAllocator<U>;
  81   };
  82
  83   T* allocate(std::size_t size) const {
  84     return reinterpret_cast<T*>(malloc(size));
  85   }
  86   void deallocate(T* ptr, size_t) const { free(ptr); }
  87   std::size_t usable_size(T* ptr, std::size_t) const {
  88     return malloc_usable_size(ptr);
  89   }
  90 };
  91
  92 template<typename T,
  93          size_t InternalSize = 1,
  94          size_t MinHeapCapacity = 0,
  95          typename OrigAllocator = TinyVectorMallocAllocator<T>>
  96 struct TinyVector {
  97   static_assert(std::is_nothrow_move_constructible<T>::value,
  98                 "TinyVector only supports elements with "
  99                 "non-throwing move constructors");
 100   static_assert(tiny_vector_detail::is_nothrow_swappable<T>::value,
 101                 "TinyVector only supports elements with non-throwing swaps");
 102   static_assert(InternalSize >= 1,
 103                 "TinyVector assumes that the internal size is at least 1");
 104
 105   /*
 106    * We need to see if the allocator implements a member named `usable_size`.
 107    * If it does, we assume it is a method like
 108    *   size_type Alloc::usable_size(pointer, size_type);
 109    */
 110   template <typename Alloc> struct alloc_traits : std::allocator_traits<Alloc> {
 111     using typename std::allocator_traits<Alloc>::size_type;
 112
 113    private:
 114     template <typename AT, decltype(&AT::usable_size)* = nullptr>
 115     struct valid_type;
 116     template <typename AT = Alloc>
 117     static std::true_type helper(valid_type<AT>*);
 118     template <typename AT = Alloc> static std::false_type helper(...);
 119     static constexpr bool has_usable_size =
 120       std::is_same<std::true_type, decltype(helper(nullptr))>::value;
 121
 122     template<typename AT = Alloc> static size_type usable_size_impl(
 123       typename std::enable_if<alloc_traits<AT>::has_usable_size, AT>::type& a,
 124       void* ptr, size_type size) {
 125       return a.usable_size(ptr, size);
 126     }
 127     template<typename AT = Alloc> static size_type usable_size_impl(
 128       typename std::enable_if<!alloc_traits<AT>::has_usable_size, AT>::type&,
 129       void*, size_type size) {
 130       return size;
 131     }
 132    public:
 133     static size_type usable_size(Alloc& a, void* ptr, size_type size) {
 134       return usable_size_impl(a, ptr, size);
 135     }
 136   };
 137
 138   using Allocator = typename OrigAllocator::template rebind<uint8_t>::other;
 139   using AT = alloc_traits<Allocator>;
 140   using AllocPtr = typename AT::pointer;
 141
 142   struct const_iterator;
 143
 144   TinyVector() = default;
 145   ~TinyVector() { clear(); }
 146
 147   TinyVector(const TinyVector& o) {
 148     reserve(o.size());
 149     for (auto const& elem : o) push_back(elem);
 150   }
 151   TinyVector(TinyVector&& o) noexcept { swap(o); }
 152
 153   TinyVector& operator=(const TinyVector& o) {
 154     if (this != &o) {
 155       auto temp = o;
 156       swap(temp);
 157     }
 158     return *this;
 159   }
 160   TinyVector& operator=(TinyVector&& o) noexcept {
 161     if (this != &o) swap(o);
 162     return *this;
 163   }
 164
 165   template <typename U>
 166   TinyVector(std::initializer_list<U> il) {
 167     reserve(il.size());
 168     for (auto const& elem : il) push_back(elem);
 169   }
 170
 171   size_t size() const { return m_impl.m_data.size(); }
 172   bool empty() const { return !size(); }
 173
 174   void swap(TinyVector& o) noexcept {
 175     auto const size1 = m_impl.m_data.size();
 176     auto const size2 = o.m_impl.m_data.size();
 177     auto const internal1 = std::min<size_t>(size1, InternalSize);
 178     auto const internal2 = std::min<size_t>(size2, InternalSize);
 179
 180     // Swap the prefix of the inline storage which both have initialized.
 181     auto const both = std::min(internal1, internal2);
 182     for (size_t i = 0; i < both; ++i) {
 183       using std::swap;
 184       swap(*location(i), *o.location(i));
 185     }
 186
 187     // Move data out of the vector with more initialized inline data into the
 188     // one with less. Then destroy the moved from data.
 189     if (internal1 > internal2) {
 190       uninitialized_move_n(
 191         location(internal2),
 192         internal1 - internal2,
 193         o.location(internal2)
 194       );
 195       if (!std::is_trivially_destructible<T>::value) {
 196         for (size_t i = internal2; i < internal1; ++i) location(i)->~T();
 197       }
 198     } else {
 199       uninitialized_move_n(
 200         o.location(internal1),
 201         internal2 - internal1,
 202         location(internal1)
 203       );
 204       if (!std::is_trivially_destructible<T>::value) {
 205         for (size_t i = internal1; i < internal2; ++i) o.location(i)->~T();
 206       }
 207     }
 208
 209     // Move the non-inline data. This is just a simple pointer swap.
 210     using std::swap;
 211     swap(m_impl.m_data, o.m_impl.m_data);
 212   }
 213
 214   const_iterator begin() const { return const_iterator(this, 0); }
 215   const_iterator end()   const { return const_iterator(this); }
 216
 217   T& operator[](size_t index) {
 218     assert(index < size());
 219     return *location(index);
 220   }
 221
 222   const T& operator[](size_t index) const {
 223     return const_cast<TinyVector*>(this)->operator[](index);
 224   }
 225
 226   void clear() {
 227     if (!std::is_trivially_destructible<T>::value) {
 228       auto const current = size();
 229       for (size_t i = 0; i < current; ++i) location(i)->~T();
 230     }
 231
 232     if (HeapData* p = m_impl.m_data.ptr()) {
 233       alloc_traits<Impl>::deallocate(m_impl, reinterpret_cast<AllocPtr>(p),
 234                                      allocSize(p->capacity));
 235     }
 236     m_impl.m_data.set(0, 0);
 237   }
 238
 239   template <typename U>
 240   T& push_back(const U& u) {
 241     auto const current = size();
 242     reserve(current + 1);
 243     auto ptr = location(current);
 244     ::new (ptr) T(u);
 245     m_impl.m_data.set(current + 1, m_impl.m_data.ptr());
 246     return *ptr;
 247   }
 248
 249   template <typename U>
 250   T& push_back(U&& u) {
 251     auto const current = size();
 252     reserve(current + 1);
 253     auto ptr = location(current);
 254     ::new (ptr) T(std::move(u));
 255     m_impl.m_data.set(current + 1, m_impl.m_data.ptr());
 256     return *ptr;
 257   }
 258
 259   template <typename... Args>
 260   T& emplace_back(Args&&... args) {
 261     auto const current = size();
 262     reserve(current + 1);
 263     auto ptr = location(current);
 264     ::new (ptr) T(std::forward<Args>(args)...);
 265     m_impl.m_data.set(current + 1, m_impl.m_data.ptr());
 266     return *ptr;
 267   }
 268
 269   template <typename I>
 270   void insert(I begin, I end) {
 271     while (begin != end) emplace_back(*begin++);
 272   }
 273
 274   void pop_back() {
 275     assert(!empty());
 276     location(size() - 1)->~T();
 277     m_impl.m_data.set(size() - 1, m_impl.m_data.ptr());
 278   }
 279
 280   T& back() {
 281     assert(!empty());
 282     return (*this)[size() - 1];
 283   }
 284
 285   const T& back() const {
 286     assert(!empty());
 287     return (*this)[size() - 1];
 288   }
 289
 290   T& front() {
 291     assert(!empty());
 292     return (*this)[0];
 293   }
 294
 295   const T& front() const {
 296     assert(!empty());
 297     return (*this)[0];
 298   }
 299
 300   void reserve(size_t sz) {
 301     if (sz < InternalSize) return;
 302
 303     const size_t currentHeap =
 304       m_impl.m_data.ptr() ? m_impl.m_data.ptr()->capacity : 0;
 305     const size_t neededHeap = sz - InternalSize;
 306     if (neededHeap <= currentHeap) {
 307       return;
 308     }
 309
 310     const size_t newCapacity = std::max(
 311       currentHeap ? currentHeap * 4 / 3
 312                   : std::max(neededHeap, MinHeapCapacity),
 313       neededHeap);
 314     const size_t requested = allocSize(newCapacity);
 315     auto newHeap = reinterpret_cast<HeapData*>(AT::allocate(m_impl, requested));
 316     const size_t usableSize = AT::usable_size(m_impl, newHeap, requested);
 317     newHeap->capacity = (usableSize - offsetof(HeapData, vals)) / sizeof(T);
 318
 319     if (auto p = m_impl.m_data.ptr()) {
 320       auto const current = size();
 321       uninitialized_move_n(
 322         &m_impl.m_data.ptr()->vals[0],
 323         current - InternalSize,
 324         &newHeap->vals[0]
 325       );
 326       if (!std::is_trivially_destructible<T>::value) {
 327         for (size_t i = InternalSize; i < current; ++i) location(i)->~T();
 328       }
 329       AT::deallocate(
 330         m_impl,
 331         reinterpret_cast<AllocPtr>(p),
 332         allocSize(p->capacity)
 333       );
 334     }
 335     m_impl.m_data.set(size(), newHeap);
 336   }
 337
 338   template<size_t isize, size_t minheap, typename origalloc>
 339   bool operator==(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 340     if (size() != tv.size()) return false;
 341     return std::equal(begin(), end(), tv.begin());
 342   }
 343   template<size_t isize, size_t minheap, typename origalloc>
 344   bool operator!=(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 345     return !(*this == tv);
 346   }
 347
 348   template<size_t isize, size_t minheap, typename origalloc>
 349   bool operator<(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 350     return std::lexicographical_compare(begin(), end(), tv.begin(), tv.end());
 351   }
 352   template<size_t isize, size_t minheap, typename origalloc>
 353   bool operator<=(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 354     return (*this < tv) || (*this == tv);
 355   }
 356   template<size_t isize, size_t minheap, typename origalloc>
 357   bool operator>(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 358     return !(*this <= tv);
 359   }
 360   template<size_t isize, size_t minheap, typename origalloc>
 361   bool operator>=(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 362     return !(*this < tv);
 363   }
 364
 365 private:
 366   struct HeapData {
 367     uint32_t capacity; // numbers of vals---excludes this capacity field
 368     T vals[0];
 369   };
 370
 371   static constexpr std::size_t allocSize(uint32_t capacity) {
 372     return sizeof(HeapData) + sizeof(T) * capacity;
 373   }
 374
 375   T* location(size_t index) {
 376     return (index < InternalSize)
 377       ? folly::launder(reinterpret_cast<T*>(&m_impl.m_vals[index]))
 378       : &m_impl.m_data.ptr()->vals[index - InternalSize];
 379   }
 380
 381   // Replace with std::uninitialized_move_n in c++17
 382   template<typename InputIt, typename ForwardIt>
 383   static void uninitialized_move_n(InputIt first,
 384                                    size_t count,
 385                                    ForwardIt d_first) {
 386     using Value = typename std::iterator_traits<ForwardIt>::value_type;
 387     auto current = d_first;
 388     try {
 389       for (; count > 0; ++first, ++current, --count) {
 390         ::new (static_cast<void*>(std::addressof(*current)))
 391           Value(std::move(*first));
 392       }
 393     } catch (...) {
 394       for (; d_first != current; ++d_first) {
 395         d_first->~Value();
 396       }
 397       throw;
 398     }
 399   }
 400
 401   using RawBuffer = typename std::aligned_storage<sizeof(T), alignof(T)>::type;
 402   using InternalStorage = RawBuffer[InternalSize];
 403
 404   struct Impl : Allocator {
 405     CompactSizedPtr<HeapData> m_data;
 406     InternalStorage m_vals;
 407   };
 408   Impl m_impl;
 409 };
 410
 411 //////////////////////////////////////////////////////////////////////
 412
 413 template<typename T,
 414          size_t InternalSize,
 415          size_t MinHeapCapacity,
 416          typename Allocator>
 417 struct TinyVector<T,InternalSize,MinHeapCapacity,Allocator>::const_iterator
 418   : boost::iterator_facade<const_iterator,
 419                            const T,
 420                            boost::forward_traversal_tag>
 421 {
 422   explicit const_iterator(const TinyVector* p, uint32_t idx)
 423     : m_p(p)
 424     , m_idx(idx)
 425   {}
 426
 427   explicit const_iterator(const TinyVector* p)
 428     : m_p(p)
 429     , m_idx(m_p->size())
 430   {}
 431
 432 private:
 433   friend class boost::iterator_core_access;
 434
 435   void increment() {
 436     ++m_idx;
 437   }
 438
 439   bool equal(const const_iterator& o) const {
 440     assert(m_p == o.m_p);
 441     return m_idx == o.m_idx;
 442   }
 443
 444   const T& dereference() const {
 445     return (*m_p)[m_idx];
 446   }
 447
 448 private:
 449   const TinyVector* m_p;
 450   uint32_t m_idx;
 451 };
 452
 453 //////////////////////////////////////////////////////////////////////
 454
 455 template<typename T,
 456          size_t InternalSize,
 457          size_t MinHeapCapacity,
 458          typename Allocator>
 459 void swap(TinyVector<T, InternalSize, MinHeapCapacity, Allocator>& v1,
 460           TinyVector<T, InternalSize, MinHeapCapacity, Allocator>& v2)
 461   noexcept {
 462   v1.swap(v2);
 463 }
 464
 465 //////////////////////////////////////////////////////////////////////
 466
 467 }
 468