src/prevector.h

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