src/prevector.h

   1 // Copyright (c) 2015-2016 The Bitcoin Core developers
   2 // Distributed under the MIT software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #ifndef BITCOIN_PREVECTOR_H
   6 #define BITCOIN_PREVECTOR_H
   7
   8 #include <assert.h>
   9 #include <stdlib.h>
  10 #include <stdint.h>
  11 #include <string.h>
  12
  13 #include <iterator>
  14 #include <type_traits>
  15
  16 #pragma pack(push, 1)
  17 /** Implements a drop-in replacement for std::vector<T> which stores up to N
  18  *  elements directly (without heap allocation). The types Size and Diff are
  19  *  used to store element counts, and can be any unsigned + signed type.
  20  *
  21  *  Storage layout is either:
  22  *  - Direct allocation:
  23  *    - Size _size: the number of used elements (between 0 and N)
  24  *    - T direct[N]: an array of N elements of type T
  25  *      (only the first _size are initialized).
  26  *  - Indirect allocation:
  27  *    - Size _size: the number of used elements plus N + 1
  28  *    - Size capacity: the number of allocated elements
  29  *    - T* indirect: a pointer to an array of capacity elements of type T
  30  *      (only the first _size are initialized).
  31  *
  32  *  The data type T must be movable by memmove/realloc(). Once we switch to C++,
  33  *  move constructors can be used instead.
  34  */
  35 template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
  36 class prevector {
  37 public:
  38     typedef Size size_type;
  39     typedef Diff difference_type;
  40     typedef T value_type;
  41     typedef value_type& reference;
  42     typedef const value_type& const_reference;
  43     typedef value_type* pointer;
  44     typedef const value_type* const_pointer;
  45
  46     class iterator {
  47         T* ptr;
  48     public:
  49         typedef Diff difference_type;
  50         typedef T value_type;
  51         typedef T* pointer;
  52         typedef T& reference;
  53         typedef std::random_access_iterator_tag iterator_category;
  54         iterator(T* ptr_) : ptr(ptr_) {}
  55         T& operator*() const { return *ptr; }
  56         T* operator->() const { return ptr; }
  57         T& operator[](size_type pos) { return ptr[pos]; }
  58         const T& operator[](size_type pos) const { return ptr[pos]; }
  59         iterator& operator++() { ptr++; return *this; }
  60         iterator& operator--() { ptr--; return *this; }
  61         iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
  62         iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
  63         difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
  64         iterator operator+(size_type n) { return iterator(ptr + n); }
  65         iterator& operator+=(size_type n) { ptr += n; return *this; }
  66         iterator operator-(size_type n) { return iterator(ptr - n); }
  67         iterator& operator-=(size_type n) { ptr -= n; return *this; }
  68         bool operator==(iterator x) const { return ptr == x.ptr; }
  69         bool operator!=(iterator x) const { return ptr != x.ptr; }
  70         bool operator>=(iterator x) const { return ptr >= x.ptr; }
  71         bool operator<=(iterator x) const { return ptr <= x.ptr; }
  72         bool operator>(iterator x) const { return ptr > x.ptr; }
  73         bool operator<(iterator x) const { return ptr < x.ptr; }
  74     };
  75
  76     class reverse_iterator {
  77         T* ptr;
  78     public:
  79         typedef Diff difference_type;
  80         typedef T value_type;
  81         typedef T* pointer;
  82         typedef T& reference;
  83         typedef std::bidirectional_iterator_tag iterator_category;
  84         reverse_iterator(T* ptr_) : ptr(ptr_) {}
  85         T& operator*() { return *ptr; }
  86         const T& operator*() const { return *ptr; }
  87         T* operator->() { return ptr; }
  88         const T* operator->() const { return ptr; }
  89         reverse_iterator& operator--() { ptr++; return *this; }
  90         reverse_iterator& operator++() { ptr--; return *this; }
  91         reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
  92         reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
  93         bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
  94         bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
  95     };
  96
  97     class const_iterator {
  98         const T* ptr;
  99     public:
 100         typedef Diff difference_type;
 101         typedef const T value_type;
 102         typedef const T* pointer;
 103         typedef const T& reference;
 104         typedef std::random_access_iterator_tag iterator_category;
 105         const_iterator(const T* ptr_) : ptr(ptr_) {}
 106         const_iterator(iterator x) : ptr(&(*x)) {}
 107         const T& operator*() const { return *ptr; }
 108         const T* operator->() const { return ptr; }
 109         const T& operator[](size_type pos) const { return ptr[pos]; }
 110         const_iterator& operator++() { ptr++; return *this; }
 111         const_iterator& operator--() { ptr--; return *this; }
 112         const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
 113         const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
 114         difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
 115         const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
 116         const_iterator& operator+=(size_type n) { ptr += n; return *this; }
 117         const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
 118         const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
 119         bool operator==(const_iterator x) const { return ptr == x.ptr; }
 120         bool operator!=(const_iterator x) const { return ptr != x.ptr; }
 121         bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
 122         bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
 123         bool operator>(const_iterator x) const { return ptr > x.ptr; }
 124         bool operator<(const_iterator x) const { return ptr < x.ptr; }
 125     };
 126
 127     class const_reverse_iterator {
 128         const T* ptr;
 129     public:
 130         typedef Diff difference_type;
 131         typedef const T value_type;
 132         typedef const T* pointer;
 133         typedef const T& reference;
 134         typedef std::bidirectional_iterator_tag iterator_category;
 135         const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
 136         const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
 137         const T& operator*() const { return *ptr; }
 138         const T* operator->() const { return ptr; }
 139         const_reverse_iterator& operator--() { ptr++; return *this; }
 140         const_reverse_iterator& operator++() { ptr--; return *this; }
 141         const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
 142         const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
 143         bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
 144         bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
 145     };
 146
 147 private:
 148     size_type _size;
 149     union direct_or_indirect {
 150         char direct[sizeof(T) * N];
 151         struct {
 152             size_type capacity;
 153             char* indirect;
 154         };
 155     } _union;
 156
 157     T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
 158     const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
 159     T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
 160     const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
 161     bool is_direct() const { return _size <= N; }
 162
 163     void change_capacity(size_type new_capacity) {
 164         if (new_capacity <= N) {
 165             if (!is_direct()) {
 166                 T* indirect = indirect_ptr(0);
 167                 T* src = indirect;
 168                 T* dst = direct_ptr(0);
 169                 memcpy(dst, src, size() * sizeof(T));
 170                 free(indirect);
 171                 _size -= N + 1;
 172             }
 173         } else {
 174             if (!is_direct()) {
 175                 /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
 176                     success. These should instead use an allocator or new/delete so that handlers
 177                     are called as necessary, but performance would be slightly degraded by doing so. */
 178                 _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
 179                 assert(_union.indirect);
 180                 _union.capacity = new_capacity;
 181             } else {
 182                 char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
 183                 assert(new_indirect);
 184                 T* src = direct_ptr(0);
 185                 T* dst = reinterpret_cast<T*>(new_indirect);
 186                 memcpy(dst, src, size() * sizeof(T));
 187                 _union.indirect = new_indirect;
 188                 _union.capacity = new_capacity;
 189                 _size += N + 1;
 190             }
 191         }
 192     }
 193
 194     T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
 195     const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
 196
 197 public:
 198     void assign(size_type n, const T& val) {
 199         clear();
 200         if (capacity() < n) {
 201             change_capacity(n);
 202         }
 203         while (size() < n) {
 204             _size++;
 205             new(static_cast<void*>(item_ptr(size() - 1))) T(val);
 206         }
 207     }
 208
 209     template<typename InputIterator>
 210     void assign(InputIterator first, InputIterator last) {
 211         size_type n = last - first;
 212         clear();
 213         if (capacity() < n) {
 214             change_capacity(n);
 215         }
 216         while (first != last) {
 217             _size++;
 218             new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
 219             ++first;
 220         }
 221     }
 222
 223     prevector() : _size(0), _union{{}} {}
 224
 225     explicit prevector(size_type n) : _size(0) {
 226         resize(n);
 227     }
 228
 229     explicit prevector(size_type n, const T& val = T()) : _size(0) {
 230         change_capacity(n);
 231         while (size() < n) {
 232             _size++;
 233             new(static_cast<void*>(item_ptr(size() - 1))) T(val);
 234         }
 235     }
 236
 237     template<typename InputIterator>
 238     prevector(InputIterator first, InputIterator last) : _size(0) {
 239         size_type n = last - first;
 240         change_capacity(n);
 241         while (first != last) {
 242             _size++;
 243             new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
 244             ++first;
 245         }
 246     }
 247
 248     prevector(const prevector<N, T, Size, Diff>& other) : _size(0) {
 249         change_capacity(other.size());
 250         const_iterator it = other.begin();
 251         while (it != other.end()) {
 252             _size++;
 253             new(static_cast<void*>(item_ptr(size() - 1))) T(*it);
 254             ++it;
 255         }
 256     }
 257
 258     prevector(prevector<N, T, Size, Diff>&& other) : _size(0) {
 259         swap(other);
 260     }
 261
 262     prevector& operator=(const prevector<N, T, Size, Diff>& other) {
 263         if (&other == this) {
 264             return *this;
 265         }
 266         resize(0);
 267         change_capacity(other.size());
 268         const_iterator it = other.begin();
 269         while (it != other.end()) {
 270             _size++;
 271             new(static_cast<void*>(item_ptr(size() - 1))) T(*it);
 272             ++it;
 273         }
 274         return *this;
 275     }
 276
 277     prevector& operator=(prevector<N, T, Size, Diff>&& other) {
 278         swap(other);
 279         return *this;
 280     }
 281
 282     size_type size() const {
 283         return is_direct() ? _size : _size - N - 1;
 284     }
 285
 286     bool empty() const {
 287         return size() == 0;
 288     }
 289
 290     iterator begin() { return iterator(item_ptr(0)); }
 291     const_iterator begin() const { return const_iterator(item_ptr(0)); }
 292     iterator end() { return iterator(item_ptr(size())); }
 293     const_iterator end() const { return const_iterator(item_ptr(size())); }
 294
 295     reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
 296     const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
 297     reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
 298     const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
 299
 300     size_t capacity() const {
 301         if (is_direct()) {
 302             return N;
 303         } else {
 304             return _union.capacity;
 305         }
 306     }
 307
 308     T& operator[](size_type pos) {
 309         return *item_ptr(pos);
 310     }
 311
 312     const T& operator[](size_type pos) const {
 313         return *item_ptr(pos);
 314     }
 315
 316     void resize(size_type new_size) {
 317         if (size() > new_size) {
 318             erase(item_ptr(new_size), end());
 319         }
 320         if (new_size > capacity()) {
 321             change_capacity(new_size);
 322         }
 323         while (size() < new_size) {
 324             _size++;
 325             new(static_cast<void*>(item_ptr(size() - 1))) T();
 326         }
 327     }
 328
 329     void reserve(size_type new_capacity) {
 330         if (new_capacity > capacity()) {
 331             change_capacity(new_capacity);
 332         }
 333     }
 334
 335     void shrink_to_fit() {
 336         change_capacity(size());
 337     }
 338
 339     void clear() {
 340         resize(0);
 341     }
 342
 343     iterator insert(iterator pos, const T& value) {
 344         size_type p = pos - begin();
 345         size_type new_size = size() + 1;
 346         if (capacity() < new_size) {
 347             change_capacity(new_size + (new_size >> 1));
 348         }
 349         memmove(item_ptr(p + 1), item_ptr(p), (size() - p) * sizeof(T));
 350         _size++;
 351         new(static_cast<void*>(item_ptr(p))) T(value);
 352         return iterator(item_ptr(p));
 353     }
 354
 355     void insert(iterator pos, size_type count, const T& value) {
 356         size_type p = pos - begin();
 357         size_type new_size = size() + count;
 358         if (capacity() < new_size) {
 359             change_capacity(new_size + (new_size >> 1));
 360         }
 361         memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
 362         _size += count;
 363         for (size_type i = 0; i < count; i++) {
 364             new(static_cast<void*>(item_ptr(p + i))) T(value);
 365         }
 366     }
 367
 368     template<typename InputIterator>
 369     void insert(iterator pos, InputIterator first, InputIterator last) {
 370         size_type p = pos - begin();
 371         difference_type count = last - first;
 372         size_type new_size = size() + count;
 373         if (capacity() < new_size) {
 374             change_capacity(new_size + (new_size >> 1));
 375         }
 376         memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
 377         _size += count;
 378         while (first != last) {
 379             new(static_cast<void*>(item_ptr(p))) T(*first);
 380             ++p;
 381             ++first;
 382         }
 383     }
 384
 385     iterator erase(iterator pos) {
 386         return erase(pos, pos + 1);
 387     }
 388
 389     iterator erase(iterator first, iterator last) {
 390         // Erase is not allowed to the change the object's capacity. That means
 391         // that when starting with an indirectly allocated prevector with
 392         // size and capacity > N, the result may be a still indirectly allocated
 393         // prevector with size <= N and capacity > N. A shrink_to_fit() call is
 394         // necessary to switch to the (more efficient) directly allocated
 395         // representation (with capacity N and size <= N).
 396         iterator p = first;
 397         char* endp = (char*)&(*end());
 398         if (!std::is_trivially_destructible<T>::value) {
 399             while (p != last) {
 400                 (*p).~T();
 401                 _size--;
 402                 ++p;
 403             }
 404         } else {
 405             _size -= last - p;
 406         }
 407         memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
 408         return first;
 409     }
 410
 411     void push_back(const T& value) {
 412         size_type new_size = size() + 1;
 413         if (capacity() < new_size) {
 414             change_capacity(new_size + (new_size >> 1));
 415         }
 416         new(item_ptr(size())) T(value);
 417         _size++;
 418     }
 419
 420     void pop_back() {
 421         erase(end() - 1, end());
 422     }
 423
 424     T& front() {
 425         return *item_ptr(0);
 426     }
 427
 428     const T& front() const {
 429         return *item_ptr(0);
 430     }
 431
 432     T& back() {
 433         return *item_ptr(size() - 1);
 434     }
 435
 436     const T& back() const {
 437         return *item_ptr(size() - 1);
 438     }
 439
 440     void swap(prevector<N, T, Size, Diff>& other) {
 441         std::swap(_union, other._union);
 442         std::swap(_size, other._size);
 443     }
 444
 445     ~prevector() {
 446         if (!std::is_trivially_destructible<T>::value) {
 447             clear();
 448         }
 449         if (!is_direct()) {
 450             free(_union.indirect);
 451             _union.indirect = nullptr;
 452         }
 453     }
 454
 455     bool operator==(const prevector<N, T, Size, Diff>& other) const {
 456         if (other.size() != size()) {
 457             return false;
 458         }
 459         const_iterator b1 = begin();
 460         const_iterator b2 = other.begin();
 461         const_iterator e1 = end();
 462         while (b1 != e1) {
 463             if ((*b1) != (*b2)) {
 464                 return false;
 465             }
 466             ++b1;
 467             ++b2;
 468         }
 469         return true;
 470     }
 471
 472     bool operator!=(const prevector<N, T, Size, Diff>& other) const {
 473         return !(*this == other);
 474     }
 475
 476     bool operator<(const prevector<N, T, Size, Diff>& other) const {
 477         if (size() < other.size()) {
 478             return true;
 479         }
 480         if (size() > other.size()) {
 481             return false;
 482         }
 483         const_iterator b1 = begin();
 484         const_iterator b2 = other.begin();
 485         const_iterator e1 = end();
 486         while (b1 != e1) {
 487             if ((*b1) < (*b2)) {
 488                 return true;
 489             }
 490             if ((*b2) < (*b1)) {
 491                 return false;
 492             }
 493             ++b1;
 494             ++b2;
 495         }
 496         return false;
 497     }
 498
 499     size_t allocated_memory() const {
 500         if (is_direct()) {
 501             return 0;
 502         } else {
 503             return ((size_t)(sizeof(T))) * _union.capacity;
 504         }
 505     }
 506
 507     value_type* data() {
 508         return item_ptr(0);
 509     }
 510
 511     const value_type* data() const {
 512         return item_ptr(0);
 513     }
 514 };
 515 #pragma pack(pop)
 516
 517 #endif // BITCOIN_PREVECTOR_H