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 #ifndef incl_HPHP_UTIL_TINYVECTOR_H_
  18 #define incl_HPHP_UTIL_TINYVECTOR_H_
  19
  20 #include <algorithm>
  21 #include <memory>
  22 #include <type_traits>
  23
  24 #include <boost/iterator/iterator_facade.hpp>
  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
  32 namespace HPHP {
  33
  34 //////////////////////////////////////////////////////////////////////
  35
  36 /*
  37  * Simple, small buffer-optimized sequence of T.
  38  *
  39  * Notes:
  40  *
  41  *    - Unlike std::vector, storage is not guaranteed to be contiguous.
  42  *
  43  *    - Insertion and removal can only happen at the end of the
  44  *      sequence (although you can modify elements anywhere in the
  45  *      sequence).
  46  *
  47  *    - There is no non-const iterator support, and we have forward
  48  *      iterators only.
  49  *
  50  *    - The elements must be trivially copyable/assignable and have
  51  *      trivial destructors.
  52  *
  53  * Currently, does not invalidate pointers or references to elements
  54  * at indexes less than InternalSize, but we don't want to depend on
  55  * this without documenting it here.  Iterators should be considered
  56  * invalidated after any mutation.
  57  *
  58  * Also: if you have a T*, and the list almost always contains at most
  59  * one element, PointerList is a smaller object so may be preferable
  60  * in that case.  (Unless you want the first element to remain
  61  * accessible inline instead of moved to the heap.)
  62  */
  63
  64 // Allocator interface with an additional `usable_size()` API.
  65 template <typename T>
  66 struct TinyVectorMallocAllocator {
  67   using size_type = std::size_t;
  68   using value_type = T;
  69   template <typename U> struct rebind {
  70     using other = TinyVectorMallocAllocator<U>;
  71   };
  72
  73   void* allocate(std::size_t size) const { return malloc(size); }
  74   void deallocate(void* ptr, size_t) const { free(ptr); }
  75   std::size_t usable_size(void* ptr, std::size_t /*size*/) const {
  76     return malloc_usable_size(ptr);
  77   }
  78 };
  79
  80 template<class T,
  81          size_t InternalSize = 1,
  82          size_t MinHeapCapacity = 0,
  83          typename OrigAllocator = std::allocator<char>>
  84 struct TinyVector {
  85   static_assert(std::is_trivially_destructible<T>::value,
  86                 "TinyVector only supports elements with trivial destructors");
  87   static_assert(std::is_trivially_copy_constructible<T>::value &&
  88                 std::is_trivially_copy_assignable<T>::value,
  89                 "TinyVector only supports elements with trivial copy "
  90                 "constructors and trivial assignment operators");
  91   static_assert(InternalSize >= 1,
  92                 "TinyVector assumes that the internal size is at least 1");
  93
  94   /*
  95    * We need to see if the allocator implements a member named `usable_size`.
  96    * If it does, we assume it is a method like
  97    *   size_type Alloc::usable_size(pointer, size_type);
  98    */
  99   template <typename Alloc> struct alloc_traits : std::allocator_traits<Alloc> {
 100     using typename std::allocator_traits<Alloc>::size_type;
 101
 102    private:
 103     template <typename AT, decltype(&AT::usable_size)* = nullptr>
 104     struct valid_type;
 105     template <typename AT = Alloc>
 106     static std::true_type helper(valid_type<AT>*);
 107     template <typename AT = Alloc> static std::false_type helper(...);
 108     static constexpr bool has_usable_size =
 109       std::is_same<std::true_type, decltype(helper(nullptr))>::value;
 110
 111     template<typename AT = Alloc> static size_type usable_size_impl(
 112       typename std::enable_if<alloc_traits<AT>::has_usable_size, AT>::type& a,
 113       void* ptr, size_type size) {
 114       return a.usable_size(ptr, size);
 115     }
 116     template<typename AT = Alloc> static size_type usable_size_impl(
 117       typename std::enable_if<!alloc_traits<AT>::has_usable_size, AT>::type&,
 118       void*, size_type size) {
 119       return size;
 120     }
 121    public:
 122     static size_type usable_size(Alloc& a, void* ptr, size_type size) {
 123       return usable_size_impl(a, ptr, size);
 124     }
 125   };
 126
 127   using Allocator = typename OrigAllocator::template rebind<uint8_t>::other;
 128   using AT = alloc_traits<Allocator>;
 129   using AllocPtr = typename AT::pointer;
 130
 131   struct const_iterator;
 132
 133   TinyVector() {}
 134   ~TinyVector() { clear(); }
 135
 136   TinyVector(const TinyVector&) = delete;
 137   TinyVector& operator=(const TinyVector&) = delete;
 138
 139   size_t size() const { return m_impl.m_data.size(); }
 140   bool empty() const { return !size(); }
 141
 142   const_iterator begin() const { return const_iterator(this, 0); }
 143   const_iterator end()   const { return const_iterator(this); }
 144
 145   T& operator[](size_t index) {
 146     assert(index < size());
 147     return *location(index);
 148   }
 149
 150   const T& operator[](size_t index) const {
 151     return const_cast<TinyVector*>(this)->operator[](index);
 152   }
 153
 154   void clear() {
 155     if (HeapData* p = m_impl.m_data.ptr()) {
 156       alloc_traits<Impl>::deallocate(m_impl, reinterpret_cast<AllocPtr>(p),
 157                                      allocSize(p->capacity));
 158     }
 159     m_impl.m_data.set(0, 0);
 160   }
 161
 162   void push_back(const T& t) {
 163     alloc_back() = t;
 164   }
 165
 166   /*
 167    * Increase the size of this TinyVector by 1 and return a reference to the
 168    * new object, which will be uninitialized.
 169    */
 170   T& alloc_back() {
 171     size_t current = size();
 172     reserve(current + 1);
 173     m_impl.m_data.set(current + 1, m_impl.m_data.ptr());
 174     return back();
 175   }
 176
 177   void pop_back() {
 178     assert(!empty());
 179     m_impl.m_data.set(size() - 1, m_impl.m_data.ptr());
 180   }
 181
 182   T& back() {
 183     assert(!empty());
 184     return (*this)[size() - 1];
 185   }
 186
 187   const T& back() const {
 188     assert(!empty());
 189     return (*this)[size() - 1];
 190   }
 191
 192   T& front() {
 193     assert(!empty());
 194     return m_impl.m_vals[0];
 195   }
 196
 197   const T& front() const {
 198     assert(!empty());
 199     return m_impl.m_vals[0];
 200   }
 201
 202   void reserve(size_t sz) {
 203     if (sz < InternalSize) return;
 204
 205     const size_t currentHeap =
 206       m_impl.m_data.ptr() ? m_impl.m_data.ptr()->capacity : 0;
 207     const size_t neededHeap = sz - InternalSize;
 208     if (neededHeap <= currentHeap) {
 209       return;
 210     }
 211
 212     const size_t newCapacity = std::max(
 213       currentHeap ? currentHeap * 4 / 3
 214                   : std::max(neededHeap, MinHeapCapacity),
 215       neededHeap);
 216     const size_t requested = allocSize(newCapacity);
 217     auto newHeap = reinterpret_cast<HeapData*>(AT::allocate(m_impl, requested));
 218     const size_t usableSize = AT::usable_size(m_impl, newHeap, requested);
 219     newHeap->capacity = (usableSize - offsetof(HeapData, vals)) / sizeof(T);
 220
 221     if (HeapData* p = m_impl.m_data.ptr()) {
 222       std::copy(&m_impl.m_data.ptr()->vals[0],
 223                 &m_impl.m_data.ptr()->vals[size() - InternalSize],
 224                 &newHeap->vals[0]);
 225       AT::deallocate(m_impl, reinterpret_cast<AllocPtr>(p),
 226                      allocSize(p->capacity));
 227     }
 228     m_impl.m_data.set(size(), newHeap);
 229   }
 230
 231   template<size_t isize, size_t minheap, typename origalloc>
 232   bool operator==(const TinyVector<T, isize, minheap, origalloc>& tv) const {
 233     if (size() != tv.size()) return false;
 234
 235     for (size_t i = 0; i < size(); ++i) {
 236       if ((*this)[i] != tv[i]) return false;
 237     }
 238     return true;
 239   }
 240
 241 private:
 242   struct HeapData {
 243     uint32_t capacity; // numbers of vals---excludes this capacity field
 244     T vals[0];
 245   };
 246
 247   static constexpr std::size_t allocSize(uint32_t capacity) {
 248     return sizeof(HeapData) + sizeof(T) * capacity;
 249   }
 250
 251   T* location(size_t index) {
 252     return index < InternalSize
 253                    ? &m_impl.m_vals[index]
 254                    : &m_impl.m_data.ptr()->vals[index - InternalSize];
 255   }
 256
 257 private:
 258   struct Impl : Allocator {
 259     CompactSizedPtr<HeapData> m_data;
 260     T m_vals[InternalSize];
 261   };
 262   Impl m_impl;
 263 };
 264
 265 //////////////////////////////////////////////////////////////////////
 266
 267 template<class T,
 268          size_t InternalSize,
 269          size_t MinHeapCapacity,
 270          typename Allocator>
 271 struct TinyVector<T,InternalSize,MinHeapCapacity,Allocator>::const_iterator
 272   : boost::iterator_facade<const_iterator,
 273                            const T,
 274                            boost::forward_traversal_tag>
 275 {
 276   explicit const_iterator(const TinyVector* p, uint32_t idx)
 277     : m_p(p)
 278     , m_idx(idx)
 279   {}
 280
 281   explicit const_iterator(const TinyVector* p)
 282     : m_p(p)
 283     , m_idx(m_p->size())
 284   {}
 285
 286 private:
 287   friend class boost::iterator_core_access;
 288
 289   void increment() {
 290     ++m_idx;
 291   }
 292
 293   bool equal(const const_iterator& o) const {
 294     assert(m_p == o.m_p);
 295     return m_idx == o.m_idx;
 296   }
 297
 298   const T& dereference() const {
 299     return (*m_p)[m_idx];
 300   }
 301
 302 private:
 303   const TinyVector* m_p;
 304   uint32_t m_idx;
 305 };
 306
 307 //////////////////////////////////////////////////////////////////////
 308
 309 }
 310
 311 #endif