arenavector.h (18826B)
1 // This file is part of AsmJit project <https://asmjit.com> 2 // 3 // See <asmjit/core.h> or LICENSE.md for license and copyright information 4 // SPDX-License-Identifier: Zlib 5 6 #ifndef ASMJIT_CORE_ARENAVECTOR_H_INCLUDED 7 #define ASMJIT_CORE_ARENAVECTOR_H_INCLUDED 8 9 #include "../core/arena.h" 10 #include "../core/span.h" 11 #include "../core/support.h" 12 13 ASMJIT_BEGIN_NAMESPACE 14 15 //! \addtogroup asmjit_support 16 //! \{ 17 18 //! Base class used by \ref ArenaVector template. 19 class ArenaVectorBase { 20 public: 21 ASMJIT_NONCOPYABLE(ArenaVectorBase) 22 23 //! \name Types (C++ compatibility) 24 //! \{ 25 26 using size_type = size_t; 27 using difference_type = ptrdiff_t; 28 29 //! \} 30 31 //! \name Members 32 //! \{ 33 34 //! Vector data (untyped). 35 void* _data {}; 36 //! Size of the vector. 37 uint32_t _size {}; 38 //! Capacity of the vector. 39 uint32_t _capacity {}; 40 41 //! \} 42 43 protected: 44 //! \name Construction & Destruction 45 //! \{ 46 47 //! Creates a new instance of `ArenaVectorBase`. 48 ASMJIT_INLINE_NODEBUG ArenaVectorBase() noexcept {} 49 50 ASMJIT_INLINE_NODEBUG ArenaVectorBase(ArenaVectorBase&& other) noexcept 51 : _data(other._data), 52 _size(other._size), 53 _capacity(other._capacity) { other.reset(); } 54 55 //! \} 56 57 //! \cond INTERNAL 58 //! \name Internal 59 //! \{ 60 61 inline void _release(Arena& arena, uint32_t item_byte_size) noexcept { 62 if (_data != nullptr) { 63 arena.free_reusable(_data, _capacity * item_byte_size); 64 reset(); 65 } 66 } 67 68 ASMJIT_INLINE_NODEBUG void _move_from(ArenaVectorBase&& other) noexcept { 69 void* data = other._data; 70 uint32_t size = other._size; 71 uint32_t capacity = other._capacity; 72 73 other._data = nullptr; 74 other._size = 0u; 75 other._capacity = 0u; 76 77 _data = data; 78 _size = size; 79 _capacity = capacity; 80 } 81 82 ASMJIT_API Error _reserve_fit(Arena& arena, size_t n, Support::ByteSize byte_size) noexcept; 83 ASMJIT_API Error _reserve_fit(Arena& arena, size_t n, Support::Log2Size log2_size) noexcept; 84 85 ASMJIT_API Error _reserve_grow(Arena& arena, size_t n, Support::ByteSize byte_size) noexcept; 86 ASMJIT_API Error _reserve_grow(Arena& arena, size_t n, Support::Log2Size log2_size) noexcept; 87 88 ASMJIT_API Error _reserve_additional(Arena& arena, size_t n, Support::ByteSize byte_size) noexcept; 89 ASMJIT_API Error _reserve_additional(Arena& arena, size_t n, Support::Log2Size log2_size) noexcept; 90 91 ASMJIT_API Error _resize_fit(Arena& arena, size_t n, Support::ByteSize byte_size) noexcept; 92 ASMJIT_API Error _resize_fit(Arena& arena, size_t n, Support::Log2Size log2_size) noexcept; 93 94 ASMJIT_API Error _resize_grow(Arena& arena, size_t n, Support::ByteSize byte_size) noexcept; 95 ASMJIT_API Error _resize_grow(Arena& arena, size_t n, Support::Log2Size log2_size) noexcept; 96 97 ASMJIT_INLINE_NODEBUG void _swap(ArenaVectorBase& other) noexcept { 98 std::swap(_data, other._data); 99 std::swap(_size, other._size); 100 std::swap(_capacity, other._capacity); 101 } 102 103 //! \} 104 //! \endcond 105 106 public: 107 //! \name Accessors 108 //! \{ 109 110 //! Tests whether the vector is empty. 111 [[nodiscard]] 112 ASMJIT_INLINE_NODEBUG bool is_empty() const noexcept { return _size == 0; } 113 114 //! Returns the vector size. 115 [[nodiscard]] 116 ASMJIT_INLINE_NODEBUG size_t size() const noexcept { return _size; } 117 118 //! Returns the vector capacity. 119 [[nodiscard]] 120 ASMJIT_INLINE_NODEBUG size_t capacity() const noexcept { return _capacity; } 121 122 //! \} 123 124 //! \name Utilities 125 //! \{ 126 127 //! Makes the vector empty (won't change the capacity or data pointer). 128 ASMJIT_INLINE_NODEBUG void clear() noexcept { _size = 0u; } 129 130 //! Resets the vector data and set its `size` to zero. 131 ASMJIT_INLINE_NODEBUG void reset() noexcept { 132 _data = nullptr; 133 _size = 0; 134 _capacity = 0; 135 } 136 137 //! Truncates the vector to at most `n` items. 138 ASMJIT_INLINE_NODEBUG void truncate(size_t n) noexcept { 139 _size = uint32_t(Support::min<size_t>(_size, n)); 140 } 141 142 //! Sets size of the vector to `n`. Used internally by some algorithms. 143 inline void _set_size(size_t n) noexcept { 144 ASMJIT_ASSERT(n <= _capacity); 145 _size = uint32_t(n); 146 } 147 148 //! \} 149 }; 150 151 //! Template used to store and manage array of \ref Arena allocated data. 152 //! 153 //! This template has these advantages over other std::vector<>: 154 //! - Always non-copyable (designed to be non-copyable, we want it). 155 //! - Optimized for working only with POD types. 156 //! - Explicit allocation - \ref Arena is not part of the data for improved memory footprint. 157 template <typename T> 158 class ArenaVector : public ArenaVectorBase { 159 public: 160 ASMJIT_NONCOPYABLE(ArenaVector) 161 162 //! \name Types (C++ compatibility) 163 //! \{ 164 165 using value_type = T; 166 using pointer = T*; 167 using const_pointer = const T*; 168 using reference = T&; 169 using const_reference = const T&; 170 171 using iterator = T*; 172 using const_iterator = const T*; 173 174 //! \} 175 176 //! \name Construction & Destruction 177 //! \{ 178 179 //! Creates a default constructed ArenaVector (data pointer is null, and both length/capacity is zero). 180 ASMJIT_INLINE_NODEBUG ArenaVector() noexcept : ArenaVectorBase() {} 181 182 //! Moves an existing vector into this instance and resets the `other` instance. 183 ASMJIT_INLINE_NODEBUG ArenaVector(ArenaVector&& other) noexcept : ArenaVectorBase(std::move(other)) {} 184 185 //! \} 186 187 //! \name Overloaded Operators 188 //! \{ 189 190 //! Implements a move assignment operator. The `other` instance is reset before this instance is set. 191 //! 192 //! \note It's recommended to first release the memory of the destination vector as there is no way 193 //! how to do it after the move, unless it's guaranteed that the destination vector is default 194 //! constructed. 195 ASMJIT_INLINE_NODEBUG ArenaVector& operator=(ArenaVector&& other) noexcept { 196 _move_from(other); 197 return *this; 198 } 199 200 //! \} 201 202 //! \name Overloaded Operators 203 //! \{ 204 205 //! Returns item at index `i`. 206 [[nodiscard]] 207 ASMJIT_INLINE T& operator[](size_t i) noexcept { 208 ASMJIT_ASSERT(i < _size); 209 return data()[i]; 210 } 211 212 //! Returns item at index `i`. 213 [[nodiscard]] 214 ASMJIT_INLINE const T& operator[](size_t i) const noexcept { 215 ASMJIT_ASSERT(i < _size); 216 return data()[i]; 217 } 218 219 //! Returns a non-owning span of this vector. 220 [[nodiscard]] 221 ASMJIT_INLINE_NODEBUG operator Span<T>() const noexcept { return Span<T>(static_cast<T*>(_data), _size); } 222 223 //! \} 224 225 //! \name Accessors 226 //! \{ 227 228 //! Returns a non-owning span of this vector. 229 [[nodiscard]] 230 ASMJIT_INLINE_NODEBUG Span<T> as_span() const noexcept { return Span<T>(static_cast<T*>(_data), _size); } 231 232 //! Returns vector data (mutable). 233 [[nodiscard]] 234 ASMJIT_INLINE_NODEBUG T* data() noexcept { return static_cast<T*>(_data); } 235 236 //! Returns vector data (const) 237 [[nodiscard]] 238 ASMJIT_INLINE_NODEBUG const T* data() const noexcept { return static_cast<const T*>(_data); } 239 240 //! Returns vector data (const) 241 [[nodiscard]] 242 ASMJIT_INLINE_NODEBUG const T* cdata() const noexcept { return static_cast<const T*>(_data); } 243 244 //! Returns item at the given index `i` (const). 245 [[nodiscard]] 246 inline const T& at(size_t i) const noexcept { 247 ASMJIT_ASSERT(i < _size); 248 return data()[i]; 249 } 250 251 inline void _set_end(T* p) noexcept { 252 ASMJIT_ASSERT(p >= data() && p <= data() + _capacity); 253 _set_size(size_t(p - data())); 254 } 255 256 //! Returns a reference to the first element of the vector. 257 //! 258 //! \note The vector must have at least one element. Attempting to use `first()` on empty vector will trigger 259 //! an assertion failure in debug builds. 260 [[nodiscard]] 261 ASMJIT_INLINE T& first() noexcept { return operator[](0); } 262 263 //! \overload 264 [[nodiscard]] 265 ASMJIT_INLINE const T& first() const noexcept { return operator[](0); } 266 267 //! Returns a reference to the last element of the vector. 268 //! 269 //! \note The vector must have at least one element. Attempting to use `last()` on empty vector will trigger 270 //! an assertion failure in debug builds. 271 [[nodiscard]] 272 ASMJIT_INLINE T& last() noexcept { return operator[](_size - 1); } 273 274 //! \overload 275 [[nodiscard]] 276 ASMJIT_INLINE const T& last() const noexcept { return operator[](_size - 1); } 277 278 //! \} 279 280 //! \name C++ Compatibility (Iterators) 281 //! \{ 282 283 [[nodiscard]] 284 ASMJIT_INLINE_NODEBUG iterator begin() noexcept { return iterator(data()); }; 285 286 [[nodiscard]] 287 ASMJIT_INLINE_NODEBUG const_iterator begin() const noexcept { return const_iterator(data()); }; 288 289 [[nodiscard]] 290 ASMJIT_INLINE_NODEBUG iterator end() noexcept { return iterator(data() + _size); }; 291 292 [[nodiscard]] 293 ASMJIT_INLINE_NODEBUG const_iterator end() const noexcept { return const_iterator(data() + _size); }; 294 295 [[nodiscard]] 296 ASMJIT_INLINE_NODEBUG const_iterator cbegin() const noexcept { return const_iterator(data()); }; 297 298 [[nodiscard]] 299 ASMJIT_INLINE_NODEBUG const_iterator cend() const noexcept { return const_iterator(data() + _size); }; 300 301 //! \} 302 303 //! \name Iteration 304 //! \{ 305 306 ASMJIT_INLINE_NODEBUG SpanForwardIteratorAdaptor<T> iterate() const noexcept { 307 T* p = static_cast<T*>(_data); 308 return SpanForwardIteratorAdaptor<T>{p, p + _size}; 309 } 310 311 ASMJIT_INLINE_NODEBUG SpanReverseIteratorAdaptor<T> iterate_reverse() const noexcept { 312 T* p = static_cast<T*>(_data); 313 return SpanReverseIteratorAdaptor<T>{p, p + _size}; 314 } 315 316 //! \} 317 318 //! \name Utilities 319 //! \{ 320 321 //! Swaps this vector with `other`. 322 ASMJIT_INLINE void swap(ArenaVector<T>& other) noexcept { _swap(other); } 323 324 //! Prepends `item` to the vector. 325 ASMJIT_INLINE Error prepend(Arena& arena, const T& item) noexcept { 326 ASMJIT_PROPAGATE(reserve_additional(arena)); 327 328 memmove(static_cast<void*>(static_cast<T*>(_data) + 1), 329 static_cast<const void*>(_data), 330 size_t(_size) * sizeof(T)); 331 332 memcpy(static_cast<void*>(_data), 333 static_cast<const void*>(&item), 334 sizeof(T)); 335 336 _size++; 337 return Error::kOk; 338 } 339 340 //! Inserts an `item` at the specified `index`. 341 ASMJIT_INLINE Error insert(Arena& arena, size_t index, const T& item) noexcept { 342 ASMJIT_ASSERT(index <= _size); 343 ASMJIT_PROPAGATE(reserve_additional(arena)); 344 345 T* dst = static_cast<T*>(_data) + index; 346 memmove(static_cast<void*>(dst + 1), 347 static_cast<const void*>(dst), 348 size_t(_size - index) * sizeof(T)); 349 350 memcpy(static_cast<void*>(dst), 351 static_cast<const void*>(&item), 352 sizeof(T)); 353 354 _size++; 355 return Error::kOk; 356 } 357 358 //! Appends `item` to the vector. 359 ASMJIT_INLINE Error append(Arena& arena, const T& item) noexcept { 360 ASMJIT_PROPAGATE(reserve_additional(arena)); 361 362 memcpy(static_cast<void*>(static_cast<T*>(_data) + _size), 363 static_cast<const void*>(&item), 364 sizeof(T)); 365 366 _size++; 367 return Error::kOk; 368 } 369 370 //! Appends `other` vector at the end of this vector. 371 ASMJIT_INLINE Error concat(Arena& arena, const ArenaVector<T>& other) noexcept { 372 uint32_t size = other._size; 373 374 if (_capacity - _size < size) { 375 ASMJIT_PROPAGATE(reserve_additional(arena, size)); 376 } 377 378 if (size) { 379 memcpy(static_cast<void*>(static_cast<T*>(_data) + _size), 380 static_cast<const void*>(other._data), 381 size_t(size) * sizeof(T)); 382 _size += size; 383 } 384 385 return Error::kOk; 386 } 387 388 ASMJIT_INLINE void assign_unchecked(const ArenaVector<T>& other) noexcept { 389 uint32_t size = other._size; 390 ASMJIT_ASSERT(_capacity >= other._size); 391 392 if (size) { 393 memcpy(_data, other._data, size_t(size) * sizeof(T)); 394 } 395 396 _size = size; 397 } 398 399 //! Prepends `item` to the vector (unsafe case). 400 //! 401 //! Can only be used together with `reserve_additional()`. If `reserve_additional(N)` returns `Error::kOk` then N elements 402 //! can be added to the vector without checking if there is a place for them. Used mostly internally. 403 ASMJIT_INLINE void prepend_unchecked(const T& item) noexcept { 404 ASMJIT_ASSERT(_size < _capacity); 405 T* data = static_cast<T*>(_data); 406 407 if (_size) { 408 memmove(static_cast<void*>(data + 1), 409 static_cast<const void*>(data), 410 size_t(_size) * sizeof(T)); 411 } 412 413 memcpy(static_cast<void*>(data), 414 static_cast<const void*>(&item), 415 sizeof(T)); 416 _size++; 417 } 418 419 //! Append s`item` to the vector (unsafe case). 420 //! 421 //! Can only be used together with `reserve_additional()`. If `reserve_additional(N)` returns `Error::kOk` then N elements 422 //! can be added to the vector without checking if there is a place for them. Used mostly internally. 423 ASMJIT_INLINE void append_unchecked(const T& item) noexcept { 424 ASMJIT_ASSERT(_size < _capacity); 425 426 memcpy(static_cast<void*>(static_cast<T*>(_data) + _size), 427 static_cast<const void*>(&item), 428 sizeof(T)); 429 _size++; 430 } 431 432 //! Inserts an `item` at the specified `index` (unsafe case). 433 ASMJIT_INLINE void insert_unchecked(size_t index, const T& item) noexcept { 434 ASMJIT_ASSERT(_size < _capacity); 435 ASMJIT_ASSERT(index <= _size); 436 437 T* dst = static_cast<T*>(_data) + index; 438 memmove(static_cast<void*>(dst + 1), 439 static_cast<const void*>(dst), 440 size_t(_size - index) * sizeof(T)); 441 442 memcpy(static_cast<void*>(dst), 443 static_cast<const void*>(&item), 444 sizeof(T)); 445 446 _size++; 447 } 448 449 //! Concatenates all items of `other` at the end of the vector. 450 ASMJIT_INLINE void concat_unchecked(const ArenaVector<T>& other) noexcept { 451 uint32_t size = other._size; 452 ASMJIT_ASSERT(_capacity - _size >= size); 453 454 if (size) { 455 memcpy(static_cast<void*>(static_cast<T*>(_data) + _size), 456 static_cast<const void*>(other._data), 457 size_t(size) * sizeof(T)); 458 _size += size; 459 } 460 } 461 462 //! Removes item at index `i`. 463 ASMJIT_INLINE void remove_at(size_t i) noexcept { 464 ASMJIT_ASSERT(i < _size); 465 466 T* data = static_cast<T*>(_data) + i; 467 size_t size = --_size - i; 468 469 if (size) { 470 memmove(static_cast<void*>(data), 471 static_cast<const void*>(data + 1), 472 size_t(size) * sizeof(T)); 473 } 474 } 475 476 //! Pops the last element from the vector and returns it. 477 [[nodiscard]] 478 ASMJIT_INLINE T pop() noexcept { 479 ASMJIT_ASSERT(_size > 0); 480 481 uint32_t index = --_size; 482 return data()[index]; 483 } 484 485 template<typename CompareT = Support::Compare<Support::SortOrder::kAscending>> 486 ASMJIT_INLINE void sort(const CompareT& cmp = CompareT()) noexcept { 487 Support::sort<T, CompareT>(data(), size(), cmp); 488 } 489 490 //! \} 491 492 //! \name Utility Functions 493 //! \{ 494 495 //! Tests whether the vector contains `value`. 496 template<typename Value> 497 ASMJIT_INLINE bool contains(Value&& value) const noexcept { 498 return as_span().contains(std::forward<Value>(value)); 499 } 500 501 //! Returns the first index of the given `value` or `Globals::kNPos` if it wasn't found. 502 template<typename Value> 503 ASMJIT_INLINE size_t index_of(Value&& value) const noexcept { 504 return as_span().index_of(std::forward<Value>(value)); 505 } 506 507 //! Returns the last index of the given `value` or `Globals::kNPos` if it wasn't found. 508 template<typename Value> 509 ASMJIT_INLINE size_t last_index_of(Value&& value) const noexcept { 510 return as_span().index_of(std::forward<Value>(value)); 511 } 512 513 //! \} 514 515 //! \cond INTERNAL 516 //! \name Memory Management (internal) 517 //! \{ 518 519 ASMJIT_INLINE Error _reserve_fit(Arena& arena, size_t n) noexcept { 520 return ArenaVectorBase::_reserve_fit(arena, n, Support::as_item_size<sizeof(T)>()); 521 } 522 523 ASMJIT_INLINE Error _reserve_grow(Arena& arena, size_t n) noexcept { 524 return ArenaVectorBase::_reserve_grow(arena, n, Support::as_item_size<sizeof(T)>()); 525 } 526 527 ASMJIT_INLINE Error _resize_fit(Arena& arena, size_t n) noexcept { 528 return ArenaVectorBase::_resize_fit(arena, n, Support::as_item_size<sizeof(T)>()); 529 } 530 531 ASMJIT_INLINE Error _resize_grow(Arena& arena, size_t n) noexcept { 532 return ArenaVectorBase::_resize_grow(arena, n, Support::as_item_size<sizeof(T)>()); 533 } 534 535 ASMJIT_INLINE Error _reserve_additional(Arena& arena, size_t n) noexcept { 536 return ArenaVectorBase::_reserve_additional(arena, n, Support::as_item_size<sizeof(T)>()); 537 } 538 539 //! \} 540 //! \endcond 541 542 //! \name Memory Management 543 //! \{ 544 545 //! Releases the memory held by `ArenaVector<T>` back to the `arena`. 546 ASMJIT_INLINE void release(Arena& arena) noexcept { 547 _release(arena, sizeof(T)); 548 } 549 550 //! Reallocates the underlying array to fit at least `n` items with fit semantics. 551 //! 552 //! \remarks This function uses a fit policy, which means that when possible the underlying array would be 553 //! allocated to hold at least `n` elements exactly or the resulting capacity would be slightly higher. 554 [[nodiscard]] 555 ASMJIT_INLINE Error reserve_fit(Arena& arena, size_t n) noexcept { 556 if (ASMJIT_UNLIKELY(n > _capacity)) { 557 return _reserve_fit(arena, n); 558 } 559 else { 560 return Error(Error::kOk); 561 } 562 } 563 564 //! Reallocates the underlying array to fit at least `n` items with grow semantics. 565 //! 566 //! If the vector is smaller than `n` the same growing calculations will be used as if `n` items were appended 567 //! to an empty vector, which means reserving additional space for more append operations that could follow. 568 [[nodiscard]] 569 inline Error reserve_grow(Arena& arena, size_t n) noexcept { 570 if (ASMJIT_UNLIKELY(n > _capacity)) { 571 return _reserve_grow(arena, n); 572 } 573 else { 574 return Error(Error::kOk); 575 } 576 } 577 578 //! Called to grow the buffer to fit at least 1 element more. 579 [[nodiscard]] 580 ASMJIT_INLINE Error reserve_additional(Arena& arena) noexcept { 581 if (ASMJIT_UNLIKELY(_size == _capacity)) { 582 return _reserve_additional(arena, 1u); 583 } 584 else { 585 return Error::kOk; 586 } 587 } 588 589 //! Called to grow the buffer to fit at least `n` elements more. 590 [[nodiscard]] 591 ASMJIT_INLINE Error reserve_additional(Arena& arena, size_t n) noexcept { 592 if (ASMJIT_UNLIKELY(_capacity - _size < n)) { 593 return _reserve_additional(arena, n); 594 } 595 else { 596 return Error::kOk; 597 } 598 } 599 600 //! Resizes the vector to hold `n` elements with fit semantics. 601 //! 602 //! If `n` is greater than the current size then the additional elements' content will be initialized to zero. 603 //! If `n` is less than the current size then the vector will be truncated to exactly `n` elements. 604 [[nodiscard]] 605 ASMJIT_INLINE Error resize_fit(Arena& arena, size_t n) noexcept { 606 return _resize_fit(arena, n); 607 } 608 609 //! Resizes the vector to hold `n` elements. 610 //! 611 //! If `n` is greater than the current size then the additional elements' content will be initialized to zero. 612 //! If `n` is less than the current size then the vector will be truncated to exactly `n` elements. 613 [[nodiscard]] 614 ASMJIT_INLINE Error resize_grow(Arena& arena, size_t n) noexcept { 615 return _resize_grow(arena, n); 616 } 617 618 //! \} 619 }; 620 621 //! \} 622 623 ASMJIT_END_NAMESPACE 624 625 #endif // ASMJIT_CORE_ARENAVECTOR_H_INCLUDED