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