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