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