src/prevector.h

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