heap_array.h (11673B)
1 // SPDX-FileCopyrightText: 2019-2024 Connor McLaughlin <stenzek@gmail.com> 2 // SPDX-License-Identifier: (GPL-3.0 OR PolyForm-Strict-1.0.0) 3 4 #pragma once 5 6 #include <algorithm> 7 #include <cassert> 8 #include <cstdlib> 9 #include <cstring> 10 #include <span> 11 #include <type_traits> 12 13 template<typename T, std::size_t SIZE, std::size_t ALIGNMENT = 0> 14 class FixedHeapArray 15 { 16 public: 17 using value_type = T; 18 using size_type = std::size_t; 19 using difference_type = std::ptrdiff_t; 20 using reference = T&; 21 using const_reference = const T&; 22 using pointer = T*; 23 using const_pointer = const T*; 24 using this_type = FixedHeapArray<T, SIZE>; 25 26 FixedHeapArray() { allocate(); } 27 28 FixedHeapArray(const this_type& copy) 29 { 30 allocate(); 31 std::copy(copy.cbegin(), copy.cend(), begin()); 32 } 33 34 FixedHeapArray(this_type&& move) 35 { 36 m_data = move.m_data; 37 move.m_data = nullptr; 38 } 39 40 ~FixedHeapArray() { deallocate(); } 41 42 size_type size() const { return SIZE; } 43 size_type capacity() const { return SIZE; } 44 bool empty() const { return false; } 45 46 pointer begin() { return m_data; } 47 pointer end() { return m_data + SIZE; } 48 49 const_pointer data() const { return m_data; } 50 pointer data() { return m_data; } 51 52 const_pointer cbegin() const { return m_data; } 53 const_pointer cend() const { return m_data + SIZE; } 54 55 const_reference operator[](size_type index) const 56 { 57 assert(index < SIZE); 58 return m_data[index]; 59 } 60 reference operator[](size_type index) 61 { 62 assert(index < SIZE); 63 return m_data[index]; 64 } 65 66 const_reference front() const { return m_data[0]; } 67 const_reference back() const { return m_data[SIZE - 1]; } 68 reference front() { return m_data[0]; } 69 reference back() { return m_data[SIZE - 1]; } 70 71 void fill(const_reference value) { std::fill(begin(), end(), value); } 72 73 void swap(this_type& move) { std::swap(m_data, move.m_data); } 74 75 std::span<T, SIZE> span() { return std::span<T, SIZE>(m_data); } 76 std::span<const T, SIZE> cspan() const { return std::span<const T, SIZE>(m_data); } 77 78 this_type& operator=(const this_type& rhs) 79 { 80 std::copy(begin(), end(), rhs.cbegin()); 81 return *this; 82 } 83 84 this_type& operator=(this_type&& move) 85 { 86 deallocate(); 87 m_data = move.m_data; 88 move.m_data = nullptr; 89 return *this; 90 } 91 92 #define RELATIONAL_OPERATOR(op) \ 93 bool operator op(const this_type& rhs) const \ 94 { \ 95 for (size_type i = 0; i < SIZE; i++) \ 96 { \ 97 if (!(m_data[i] op rhs.m_data[i])) \ 98 return false; \ 99 } \ 100 } 101 102 RELATIONAL_OPERATOR(==); 103 RELATIONAL_OPERATOR(!=); 104 RELATIONAL_OPERATOR(<); 105 RELATIONAL_OPERATOR(<=); 106 RELATIONAL_OPERATOR(>); 107 RELATIONAL_OPERATOR(>=); 108 109 #undef RELATIONAL_OPERATOR 110 111 private: 112 void allocate() 113 { 114 if constexpr (ALIGNMENT > 0) 115 { 116 #ifdef _MSC_VER 117 m_data = static_cast<T*>(_aligned_malloc(SIZE * sizeof(T), ALIGNMENT)); 118 assert(m_data); 119 if (!m_data) [[unlikely]] 120 std::abort(); 121 #else 122 if (posix_memalign(reinterpret_cast<void**>(&m_data), ALIGNMENT, SIZE * sizeof(T)) != 0) [[unlikely]] 123 std::abort(); 124 #endif 125 } 126 else 127 { 128 m_data = static_cast<T*>(std::malloc(SIZE * sizeof(T))); 129 assert(m_data); 130 if (!m_data) [[unlikely]] 131 std::abort(); 132 } 133 } 134 void deallocate() 135 { 136 if constexpr (ALIGNMENT > 0) 137 { 138 #ifdef _MSC_VER 139 _aligned_free(m_data); 140 #else 141 std::free(m_data); 142 #endif 143 } 144 else 145 { 146 std::free(m_data); 147 } 148 } 149 150 T* m_data; 151 }; 152 153 template<typename T, size_t alignment = 0> 154 class DynamicHeapArray 155 { 156 static_assert(std::is_trivially_copyable_v<T>, "T is trivially copyable"); 157 static_assert(std::is_standard_layout_v<T>, "T is standard layout"); 158 159 public: 160 using value_type = T; 161 using size_type = std::size_t; 162 using difference_type = std::ptrdiff_t; 163 using reference = T&; 164 using const_reference = const T&; 165 using pointer = T*; 166 using const_pointer = const T*; 167 using this_type = DynamicHeapArray<T>; 168 169 DynamicHeapArray() : m_data(nullptr), m_size(0) {} 170 DynamicHeapArray(size_t size) { internal_resize(size, nullptr, 0); } 171 DynamicHeapArray(const T* begin, const T* end) 172 { 173 const size_t size = reinterpret_cast<const char*>(end) - reinterpret_cast<const char*>(begin); 174 if (size > 0) 175 { 176 internal_resize(size / sizeof(T), nullptr, 0); 177 std::memcpy(m_data, begin, size); 178 } 179 else 180 { 181 m_data = nullptr; 182 m_size = 0; 183 } 184 } 185 DynamicHeapArray(const T* begin, size_t count) 186 { 187 if (count > 0) 188 { 189 internal_resize(count, nullptr, 0); 190 std::memcpy(m_data, begin, sizeof(T) * count); 191 } 192 else 193 { 194 m_data = nullptr; 195 m_size = 0; 196 } 197 } 198 DynamicHeapArray(const std::span<const T> data) 199 { 200 if (!data.empty()) 201 { 202 internal_resize(data.size(), nullptr, 0); 203 std::memcpy(m_data, data.data(), sizeof(T) * data.size()); 204 } 205 else 206 { 207 m_data = nullptr; 208 m_size = 0; 209 } 210 } 211 212 DynamicHeapArray(const this_type& copy) 213 { 214 if (copy.m_size > 0) 215 { 216 internal_resize(copy.m_size, nullptr, 0); 217 std::memcpy(m_data, copy.m_data, sizeof(T) * copy.m_size); 218 } 219 else 220 { 221 m_data = nullptr; 222 m_size = 0; 223 } 224 } 225 226 DynamicHeapArray(this_type&& move) 227 { 228 m_data = move.m_data; 229 m_size = move.m_size; 230 move.m_data = nullptr; 231 move.m_size = 0; 232 } 233 234 ~DynamicHeapArray() { internal_deallocate(); } 235 236 size_type size() const { return m_size; } 237 size_type capacity() const { return m_size; } 238 bool empty() const { return (m_size == 0); } 239 240 pointer begin() { return m_data; } 241 pointer end() { return m_data + m_size; } 242 243 const_pointer data() const { return m_data; } 244 pointer data() { return m_data; } 245 246 const_pointer cbegin() const { return m_data; } 247 const_pointer cend() const { return m_data + m_size; } 248 249 const_reference operator[](size_type index) const 250 { 251 assert(index < m_size); 252 return m_data[index]; 253 } 254 reference operator[](size_type index) 255 { 256 assert(index < m_size); 257 return m_data[index]; 258 } 259 260 const_reference front() const { return m_data[0]; } 261 const_reference back() const { return m_data[m_size - 1]; } 262 reference front() { return m_data[0]; } 263 reference back() { return m_data[m_size - 1]; } 264 265 void fill(const_reference value) { std::fill(begin(), end(), value); } 266 267 void swap(this_type& rhs) 268 { 269 std::swap(m_data, rhs.m_data); 270 std::swap(m_size, rhs.m_size); 271 } 272 273 void resize(size_t new_size) { internal_resize(new_size, m_data, m_size); } 274 275 void deallocate() 276 { 277 internal_deallocate(); 278 m_data = nullptr; 279 m_size = 0; 280 } 281 282 void assign(const T* begin, const T* end) 283 { 284 const size_t size = reinterpret_cast<const char*>(end) - reinterpret_cast<const char*>(begin); 285 const size_t count = size / sizeof(T); 286 if (count > 0) 287 { 288 if (m_size != count) 289 { 290 internal_deallocate(); 291 internal_resize(count, nullptr, 0); 292 } 293 294 std::memcpy(m_data, begin, size); 295 } 296 else 297 { 298 internal_deallocate(); 299 300 m_data = nullptr; 301 m_size = 0; 302 } 303 } 304 void assign(const T* begin, size_t count) 305 { 306 if (count > 0) 307 { 308 if (m_size != count) 309 { 310 internal_deallocate(); 311 internal_resize(count, nullptr, 0); 312 } 313 314 std::memcpy(m_data, begin, sizeof(T) * count); 315 } 316 else 317 { 318 internal_deallocate(); 319 320 m_data = nullptr; 321 m_size = 0; 322 } 323 } 324 void assign(const this_type& copy) { assign(copy.m_data, copy.m_size); } 325 void assign(this_type&& move) 326 { 327 internal_deallocate(); 328 m_data = move.m_data; 329 m_size = move.m_size; 330 move.m_data = nullptr; 331 move.m_size = 0; 332 } 333 334 std::span<T> span() { return std::span<T>(m_data, m_size); } 335 std::span<const T> cspan() const { return std::span<const T>(m_data, m_size); } 336 337 std::span<T> span(size_t offset, size_t size = static_cast<size_t>(-1)) 338 { 339 std::span<T> ret; 340 if (offset < m_size) [[likely]] 341 ret = std::span<T>(m_data + offset, std::min(m_size - offset, size)); 342 return ret; 343 } 344 345 std::span<const T> cspan(size_t offset, size_t size = static_cast<size_t>(-1)) const 346 { 347 std::span<const T> ret; 348 if (offset < m_size) [[likely]] 349 ret = std::span<const T>(m_data + offset, std::min(m_size - offset, size)); 350 return ret; 351 } 352 353 this_type& operator=(const this_type& rhs) 354 { 355 assign(rhs); 356 return *this; 357 } 358 359 this_type& operator=(this_type&& move) 360 { 361 assign(std::move(move)); 362 return *this; 363 } 364 365 #define RELATIONAL_OPERATOR(op, size_op) \ 366 bool operator op(const this_type& rhs) const \ 367 { \ 368 if (m_size != rhs.m_size) \ 369 return m_size size_op rhs.m_size; \ 370 for (size_type i = 0; i < m_size; i++) \ 371 { \ 372 if (!(m_data[i] op rhs.m_data[i])) \ 373 return false; \ 374 } \ 375 } 376 377 RELATIONAL_OPERATOR(==, !=); 378 RELATIONAL_OPERATOR(!=, ==); 379 RELATIONAL_OPERATOR(<, <); 380 RELATIONAL_OPERATOR(<=, <=); 381 RELATIONAL_OPERATOR(>, >); 382 RELATIONAL_OPERATOR(>=, >=); 383 384 #undef RELATIONAL_OPERATOR 385 386 private: 387 void internal_resize(size_t size, T* prev_ptr, size_t prev_size) 388 { 389 if constexpr (alignment > 0) 390 { 391 #ifdef _MSC_VER 392 m_data = static_cast<T*>(_aligned_realloc(prev_ptr, size * sizeof(T), alignment)); 393 assert(m_data); 394 if (!m_data) [[unlikely]] 395 std::abort(); 396 #else 397 if (posix_memalign(reinterpret_cast<void**>(&m_data), alignment, size * sizeof(T)) != 0) [[unlikely]] 398 std::abort(); 399 400 if (prev_ptr) 401 { 402 std::memcpy(m_data, prev_ptr, prev_size * sizeof(T)); 403 std::free(prev_ptr); 404 } 405 #endif 406 } 407 else 408 { 409 m_data = static_cast<T*>(std::realloc(prev_ptr, size * sizeof(T))); 410 assert(m_data); 411 if (!m_data) [[unlikely]] 412 std::abort(); 413 } 414 415 m_size = size; 416 } 417 void internal_deallocate() 418 { 419 if constexpr (alignment > 0) 420 { 421 #ifdef _MSC_VER 422 _aligned_free(m_data); 423 #else 424 std::free(m_data); 425 #endif 426 } 427 else 428 { 429 std::free(m_data); 430 } 431 } 432 433 T* m_data; 434 size_t m_size; 435 };