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