hphp/util/compact-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 <stdlib.h>
  20 #include <cstring>
  21 #include <memory>
  22 #include <type_traits>
  23 #include <initializer_list>
  24
  25 #include "hphp/util/assertions.h"
  26 #include "hphp/util/safe-cast.h"
  27
  28 namespace HPHP {
  29 ///////////////////////////////////////////////////////////////////////////////
  30
  31 /**
  32  * During its lifetime, an instance of CompactVector can transition
  33  * between 2 states:
  34  *   State 0: m_val == 0
  35  *     This is the initial state for a newly constructed CompactVector.
  36  *     There are no elements and no allocated block of memory.
  37  *   State 1: m_val != 0
  38  *     In this state, m_data points to a malloced block of memory. The
  39  *     number of elements, the capacity of the block, and the values of
  40  *     all the elements reside in the allocated block of memory.
  41  */
  42 template <typename T, typename Alloc = std::allocator<char>>
  43 struct CompactVector : private std::allocator_traits<Alloc>::template rebind_alloc<char> {
  44   using size_type = std::size_t;
  45   using value_type = T;
  46   using iterator = T*;
  47   using const_iterator = const T*;
  48   using Allocator = typename std::allocator_traits<Alloc>::template rebind_alloc<char>;
  49
  50   friend iterator begin(CompactVector& v) { return v.begin(); }
  51   friend iterator end(CompactVector& v) { return v.end(); }
  52   friend const_iterator begin(const CompactVector& v) { return v.begin(); }
  53   friend const_iterator end(const CompactVector& v) { return v.end(); }
  54
  55   CompactVector();
  56   explicit CompactVector(size_type n);
  57   CompactVector(size_type n, const T&);
  58   CompactVector(CompactVector&& other) noexcept;
  59   CompactVector(const CompactVector& other);
  60   CompactVector(std::initializer_list<T> init);
  61   CompactVector& operator=(CompactVector&&);
  62   CompactVector& operator=(const CompactVector&);
  63   ~CompactVector();
  64
  65   void swap(CompactVector& other) noexcept;
  66
  67   bool operator==(const CompactVector& other) const;
  68
  69   bool operator!=(const CompactVector& other) const {
  70     return !(*this == other);
  71   }
  72
  73   iterator begin() { return m_data ? elems() : nullptr; }
  74   iterator end() { return m_data ? elems() + size() : nullptr; }
  75   const_iterator begin() const { return m_data ? elems() : nullptr; }
  76   const_iterator end() const { return m_data ? elems() + size() : nullptr; }
  77   T* data() { return m_data ? elems() : nullptr; }
  78   const T* data() const { return m_data ? elems() : nullptr; }
  79
  80   bool empty() const;
  81   size_type size() const;
  82   size_type capacity() const;
  83   void clear();
  84   void push_back(const T& val);
  85   void push_back(T&& val);
  86   template <class... Args>
  87   void emplace_back(Args&&... args);
  88   void pop_back();
  89   void erase(iterator);
  90   void erase(iterator, iterator);
  91   iterator insert(iterator p, const T& v) { return insert_impl(p, 1, v); }
  92   iterator insert(iterator p, T&& v) { return insert_impl(p, 1, std::move(v)); };
  93   iterator insert(iterator p, size_t num, const T& v) {
  94     return insert_impl(p, num, v);
  95   };
  96   template<typename U>
  97   iterator insert(iterator p, U i1, U i2);
  98   void resize(size_type sz);
  99   void resize(size_type sz, const value_type& value);
 100   void shrink_to_fit();
 101
 102   T& operator[](size_type index) { return *get(index); }
 103   const T& operator[](size_type index) const { return *get(index); }
 104   T& front() { return *get(0); }
 105   const T& front() const { return *get(0); }
 106   T& back() { return *get(m_data->m_len - 1); }
 107   const T& back() const { return *get(m_data->m_len - 1); }
 108
 109   void reserve(size_type sz);
 110 private:
 111   using Allocator::allocate;
 112   using Allocator::deallocate;
 113
 114   struct CompactVectorData {
 115     uint32_t m_len;
 116     uint32_t m_capacity;
 117   };
 118
 119   iterator insert_elems(iterator, size_t num);
 120   template <class U>
 121   iterator insert_impl(iterator, size_t num, U&&);
 122   void assign(const CompactVector& other);
 123   void grow();
 124   T* get(size_type index) const;
 125   T* elems() const;
 126   static size_t required_mem(size_type n);
 127   void reserve_impl(size_type sz);
 128   bool resize_helper(size_type sz);
 129
 130   CompactVectorData* m_data;
 131
 132   static constexpr size_type initial_capacity = 4;
 133   /* We mainly want this so pretty.py can figure out the alignment */
 134   static constexpr size_type elems_offset =
 135     alignof(T) >= sizeof(CompactVectorData) ?
 136     alignof(T) : sizeof(CompactVectorData);
 137   /* And we need this to prevent gcc from throwing away elems_offset */
 138   using elems_offset_type = char[elems_offset];
 139 };
 140
 141 template <typename T, typename A>
 142 CompactVector<T, A>::CompactVector() {
 143   m_data = nullptr;
 144 }
 145
 146 template <typename T, typename A>
 147 CompactVector<T, A>::CompactVector(size_type n) {
 148   m_data = nullptr;
 149   resize(n);
 150 }
 151
 152 template <typename T, typename A>
 153 CompactVector<T, A>::CompactVector(size_type n, const T& val) {
 154   m_data = nullptr;
 155   resize(n, val);
 156 }
 157
 158 template <typename T, typename A>
 159 CompactVector<T, A>::CompactVector(CompactVector&& other) noexcept
 160   : m_data(other.m_data) {
 161   other.m_data = nullptr;
 162 }
 163
 164 template <typename T, typename A>
 165 CompactVector<T, A>::CompactVector(const CompactVector& other)
 166   : m_data(nullptr) {
 167   assign(other);
 168 }
 169
 170 template <typename T, typename A>
 171 CompactVector<T, A>&
 172 CompactVector<T, A>::operator=(const CompactVector& other) {
 173   if (this == &other) return *this;
 174   clear();
 175   assign(other);
 176   return *this;
 177 }
 178
 179 template <typename T, typename A>
 180 CompactVector<T, A>::CompactVector(std::initializer_list<T> init) :
 181     m_data(nullptr) {
 182   reserve_impl(init.size());
 183   for (auto const& e : init) {
 184     push_back(e);
 185   }
 186 }
 187
 188 template <typename T, typename A>
 189 void CompactVector<T, A>::assign(const CompactVector& other) {
 190   assert(!m_data);
 191   if (!other.size()) return;
 192   reserve_impl(other.m_data->m_len);
 193   auto const sz = other.m_data->m_len;
 194   for (size_type i = 0; i < sz; ++i) {
 195     push_back(other[i]);
 196   }
 197 }
 198
 199 template <typename T, typename A>
 200 CompactVector<T, A>& CompactVector<T, A>::operator=(CompactVector&& other) {
 201   std::swap(m_data, other.m_data);
 202   return *this;
 203 }
 204
 205 template <typename T, typename A>
 206 void CompactVector<T, A>::swap(CompactVector& other) noexcept {
 207   std::swap(m_data, other.m_data);
 208 }
 209
 210 template <typename T, typename A>
 211 bool CompactVector<T, A>::operator==(const CompactVector& other) const {
 212   auto const sz = size();
 213   if (sz != other.size()) return false;
 214   for (size_type i = 0; i < sz; ++i) {
 215     if (!(*get(i) == other[i])) return false;
 216   }
 217   return true;
 218 }
 219
 220 template <typename T, typename A>
 221 CompactVector<T, A>::~CompactVector() {
 222   clear();
 223 }
 224
 225 template <typename T, typename A>
 226 T* CompactVector<T, A>::elems() const {
 227   assert(m_data);
 228   return (T*)((char*)m_data + elems_offset);
 229 }
 230
 231 template <typename T, typename A>
 232 size_t CompactVector<T, A>::required_mem(size_type n) {
 233   return elems_offset + sizeof(T) * n;
 234 }
 235
 236 template <typename T, typename A>
 237 T* CompactVector<T, A>::get(size_type index) const {
 238   // Index into the allocated block of memory
 239   auto e = elems();
 240   assert(index < m_data->m_len);
 241   return e + index;
 242 }
 243
 244 template <typename T, typename A>
 245 bool CompactVector<T, A>::empty() const {
 246   return size() == 0;
 247 }
 248
 249 template <typename T, typename A>
 250 typename CompactVector<T, A>::size_type CompactVector<T, A>::size() const {
 251   return m_data ? m_data->m_len : 0;
 252 }
 253
 254 template <typename T, typename A>
 255 typename CompactVector<T, A>::size_type CompactVector<T, A>::capacity() const {
 256   return m_data ? m_data->m_capacity : 0;
 257 }
 258
 259 template <typename T, typename A>
 260 void CompactVector<T, A>::erase(iterator elm) {
 261   assert(elm - elems() < size());
 262   auto const e = end();
 263   while (++elm != e) {
 264     elm[-1] = std::move(*elm);
 265   }
 266   elm[-1].~T();
 267   m_data->m_len--;
 268 }
 269
 270 template <typename T, typename A>
 271 void CompactVector<T, A>::erase(iterator elm1, iterator elm2) {
 272   if (elm1 == elm2) return;
 273   assert(elems() <= elm1 && elm1 <= elm2 && elm2 <= end());
 274   auto const e = end();
 275   while (elm2 != e) {
 276     *elm1++ = std::move(*elm2++);
 277   }
 278   m_data->m_len -= elm2 - elm1;
 279   while (elm1 != e) {
 280     elm1++->~T();
 281   }
 282 }
 283
 284 template <typename T, typename A>
 285 bool CompactVector<T, A>::resize_helper(size_type sz) {
 286   auto const old_size = size();
 287   if (sz == old_size) return true;
 288   if (sz > old_size) {
 289     reserve_impl(sz);
 290     return false;
 291   }
 292   auto elm = get(sz);
 293   m_data->m_len = sz;
 294   do {
 295     elm++->~T();
 296   } while (++sz < old_size);
 297   return true;
 298 }
 299
 300 template <typename T, typename A>
 301 void CompactVector<T, A>::resize(size_type sz, const value_type& v) {
 302   if (resize_helper(sz)) return;
 303   while (m_data->m_len < sz) {
 304     push_back(v);
 305   }
 306 }
 307
 308 template <typename T, typename A>
 309 void CompactVector<T, A>::resize(size_type sz) {
 310   if (resize_helper(sz)) return;
 311   while (m_data->m_len < sz) {
 312     push_back(T{});
 313   }
 314 }
 315
 316 template <typename T, typename A>
 317 void CompactVector<T, A>::shrink_to_fit() {
 318   if (!m_data || m_data->m_capacity == m_data->m_len) return;
 319   if (!m_data->m_len) {
 320     clear();
 321     return;
 322   }
 323   reserve_impl(m_data->m_len);
 324 }
 325
 326 template <typename T, typename A>
 327 void copy(CompactVector<T, A>& dest, const std::vector<T>& src) {
 328   dest.clear();
 329   dest.reserve(src.size());
 330   for (auto const& v : src) dest.push_back(v);
 331 }
 332
 333 template <typename T, typename A>
 334 void CompactVector<T, A>::clear() {
 335   if (!m_data) return;
 336   if (!std::is_trivially_destructible<T>::value) {
 337     if (auto sz = size()) {
 338       auto elm = elems();
 339       do { elm++->~T(); } while (--sz);
 340     }
 341   }
 342   deallocate(reinterpret_cast<char*>(m_data),
 343              required_mem(m_data->m_capacity));
 344   m_data = nullptr;
 345 }
 346
 347 template <typename T, typename A>
 348 void CompactVector<T, A>::grow() {
 349   reserve_impl(m_data ? m_data->m_capacity * 2LL : initial_capacity);
 350 }
 351
 352 template <typename T, typename A>
 353 void CompactVector<T, A>::reserve_impl(size_type new_capacity) {
 354   auto new_data = (CompactVectorData*)allocate(required_mem(new_capacity));
 355   if (!new_data) throw std::bad_alloc{};
 356
 357   if (m_data) {
 358     auto len = m_data->m_len;
 359     auto old_data = m_data;
 360     auto const old_capacity = old_data->m_capacity;
 361     auto old_elems = elems();
 362     m_data = new_data;
 363     auto new_elems = elems();
 364     m_data->m_len = len;
 365     m_data->m_capacity = safe_cast<uint32_t>(new_capacity);
 366     while (len--) {
 367       new (new_elems++) T(std::move(*old_elems));
 368       old_elems++->~T();
 369     }
 370     deallocate(reinterpret_cast<char*>(old_data), required_mem(old_capacity));
 371   } else {
 372     // If there are currently no elements, all we have to do is allocate a
 373     // block of memory and initialize m_len and m_capacity.
 374     m_data = new_data;
 375     m_data->m_len = 0;
 376     m_data->m_capacity = new_capacity;
 377   }
 378 }
 379
 380 template <typename T, typename A>
 381 void CompactVector<T, A>::reserve(size_type new_capacity) {
 382   if (new_capacity > capacity()) reserve_impl(new_capacity);
 383 }
 384
 385 template <typename T, typename A>
 386 typename CompactVector<T, A>::iterator
 387 CompactVector<T, A>::insert_elems(iterator before, size_t num) {
 388   if (!num) return before;
 389   auto const sz = size();
 390   assert(sz <= capacity());
 391   auto cap = capacity();
 392   if (sz + num > cap) {
 393     auto const pos = sz ? before - elems() : 0;
 394     assert(pos <= sz);
 395     cap <<= 1;
 396     if (sz + num > cap) {
 397       cap = sz + num;
 398       if (cap < initial_capacity) cap = initial_capacity;
 399     }
 400     reserve(cap);
 401     before = elems() + pos;
 402   }
 403
 404   auto e = end();
 405   m_data->m_len += num;
 406   while (e != before) {
 407     --e;
 408     new (e + num) T(std::move(*e));
 409     e->~T();
 410   }
 411   return e;
 412 }
 413
 414
 415 template <typename T, typename A>
 416 template <typename U>
 417 typename CompactVector<T, A>::iterator
 418 CompactVector<T, A>::insert_impl(iterator before, size_t num, U&& val) {
 419   auto e = insert_elems(before, num);
 420   while (num--) {
 421     new (e + num) T(std::forward<U>(val));
 422   }
 423   return e;
 424 }
 425
 426 template <typename T, typename A>
 427 template <typename U>
 428 typename CompactVector<T, A>::iterator
 429 CompactVector<T, A>::insert(iterator before, U i1, U i2) {
 430   auto e = insert_elems(before, i2 - i1);
 431   auto i = e;
 432   while (i1 != i2) {
 433     new (i++) T(*i1++);
 434   }
 435   return e;
 436 }
 437
 438 template <typename T, typename A>
 439 void CompactVector<T, A>::push_back(const T& val) {
 440   auto const sz = size();
 441   assert(sz <= capacity());
 442   if (sz == capacity()) grow();
 443   ++(m_data->m_len);
 444   new (get(sz)) T(val);
 445 }
 446
 447 template <typename T, typename A>
 448 void CompactVector<T, A>::push_back(T&& val) {
 449   auto const sz = size();
 450   assert(sz <= capacity());
 451   if (sz == capacity()) grow();
 452   ++(m_data->m_len);
 453   new (get(sz)) T(std::move(val));
 454 }
 455
 456 template <typename T, typename A>
 457 template <class... Args>
 458 void CompactVector<T, A>::emplace_back(Args&&... args) {
 459   auto const sz = size();
 460   assert(sz <= capacity());
 461   if (sz == capacity()) grow();
 462   ++(m_data->m_len);
 463   new (get(sz)) T(std::forward<Args>(args)...);
 464 }
 465
 466 template <typename T, typename A>
 467 void CompactVector<T, A>::pop_back() {
 468   if (m_data && m_data->m_len > 0) {
 469     back().~T();
 470     --(m_data->m_len);
 471   }
 472 }
 473
 474 ///////////////////////////////////////////////////////////////////////////////
 475 }