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