1*61046927SAndroid Build Coastguard Worker /* 2*61046927SAndroid Build Coastguard Worker * Copyright Michael Schellenberger Costa 3*61046927SAndroid Build Coastguard Worker * Copyright © 2020 Valve Corporation 4*61046927SAndroid Build Coastguard Worker * 5*61046927SAndroid Build Coastguard Worker * SPDX-License-Identifier: MIT 6*61046927SAndroid Build Coastguard Worker */ 7*61046927SAndroid Build Coastguard Worker 8*61046927SAndroid Build Coastguard Worker #ifndef ACO_UTIL_H 9*61046927SAndroid Build Coastguard Worker #define ACO_UTIL_H 10*61046927SAndroid Build Coastguard Worker 11*61046927SAndroid Build Coastguard Worker #include "util/bitscan.h" 12*61046927SAndroid Build Coastguard Worker #include "util/macros.h" 13*61046927SAndroid Build Coastguard Worker #include "util/u_math.h" 14*61046927SAndroid Build Coastguard Worker 15*61046927SAndroid Build Coastguard Worker #include <array> 16*61046927SAndroid Build Coastguard Worker #include <cassert> 17*61046927SAndroid Build Coastguard Worker #include <cstddef> 18*61046927SAndroid Build Coastguard Worker #include <functional> 19*61046927SAndroid Build Coastguard Worker #include <iterator> 20*61046927SAndroid Build Coastguard Worker #include <map> 21*61046927SAndroid Build Coastguard Worker #include <type_traits> 22*61046927SAndroid Build Coastguard Worker #include <unordered_map> 23*61046927SAndroid Build Coastguard Worker #include <vector> 24*61046927SAndroid Build Coastguard Worker 25*61046927SAndroid Build Coastguard Worker namespace aco { 26*61046927SAndroid Build Coastguard Worker 27*61046927SAndroid Build Coastguard Worker /*! \brief Definition of a span object 28*61046927SAndroid Build Coastguard Worker * 29*61046927SAndroid Build Coastguard Worker * \details A "span" is an "array view" type for holding a view of contiguous 30*61046927SAndroid Build Coastguard Worker * data. The "span" object does not own the data itself. 31*61046927SAndroid Build Coastguard Worker */ 32*61046927SAndroid Build Coastguard Worker template <typename T> class span { 33*61046927SAndroid Build Coastguard Worker public: 34*61046927SAndroid Build Coastguard Worker using value_type = T; 35*61046927SAndroid Build Coastguard Worker using pointer = value_type*; 36*61046927SAndroid Build Coastguard Worker using const_pointer = const value_type*; 37*61046927SAndroid Build Coastguard Worker using reference = value_type&; 38*61046927SAndroid Build Coastguard Worker using const_reference = const value_type&; 39*61046927SAndroid Build Coastguard Worker using iterator = pointer; 40*61046927SAndroid Build Coastguard Worker using const_iterator = const_pointer; 41*61046927SAndroid Build Coastguard Worker using reverse_iterator = std::reverse_iterator<iterator>; 42*61046927SAndroid Build Coastguard Worker using const_reverse_iterator = std::reverse_iterator<const_iterator>; 43*61046927SAndroid Build Coastguard Worker using size_type = uint16_t; 44*61046927SAndroid Build Coastguard Worker using difference_type = std::ptrdiff_t; 45*61046927SAndroid Build Coastguard Worker 46*61046927SAndroid Build Coastguard Worker /*! \brief Compiler generated default constructor 47*61046927SAndroid Build Coastguard Worker */ 48*61046927SAndroid Build Coastguard Worker constexpr span() = default; 49*61046927SAndroid Build Coastguard Worker 50*61046927SAndroid Build Coastguard Worker /*! \brief Constructor taking a pointer and the length of the span 51*61046927SAndroid Build Coastguard Worker * \param[in] data Pointer to the underlying data array 52*61046927SAndroid Build Coastguard Worker * \param[in] length The size of the span 53*61046927SAndroid Build Coastguard Worker */ span(uint16_t offset_,const size_type length_)54*61046927SAndroid Build Coastguard Worker constexpr span(uint16_t offset_, const size_type length_) : offset{offset_}, length{length_} {} 55*61046927SAndroid Build Coastguard Worker 56*61046927SAndroid Build Coastguard Worker /*! \brief Returns an iterator to the begin of the span 57*61046927SAndroid Build Coastguard Worker * \return data 58*61046927SAndroid Build Coastguard Worker */ begin()59*61046927SAndroid Build Coastguard Worker constexpr iterator begin() noexcept { return (pointer)((uintptr_t)this + offset); } 60*61046927SAndroid Build Coastguard Worker 61*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_iterator to the begin of the span 62*61046927SAndroid Build Coastguard Worker * \return data 63*61046927SAndroid Build Coastguard Worker */ begin()64*61046927SAndroid Build Coastguard Worker constexpr const_iterator begin() const noexcept 65*61046927SAndroid Build Coastguard Worker { 66*61046927SAndroid Build Coastguard Worker return (const_pointer)((uintptr_t)this + offset); 67*61046927SAndroid Build Coastguard Worker } 68*61046927SAndroid Build Coastguard Worker 69*61046927SAndroid Build Coastguard Worker /*! \brief Returns an iterator to the end of the span 70*61046927SAndroid Build Coastguard Worker * \return data + length 71*61046927SAndroid Build Coastguard Worker */ end()72*61046927SAndroid Build Coastguard Worker constexpr iterator end() noexcept { return std::next(begin(), length); } 73*61046927SAndroid Build Coastguard Worker 74*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_iterator to the end of the span 75*61046927SAndroid Build Coastguard Worker * \return data + length 76*61046927SAndroid Build Coastguard Worker */ end()77*61046927SAndroid Build Coastguard Worker constexpr const_iterator end() const noexcept { return std::next(begin(), length); } 78*61046927SAndroid Build Coastguard Worker 79*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_iterator to the begin of the span 80*61046927SAndroid Build Coastguard Worker * \return data 81*61046927SAndroid Build Coastguard Worker */ cbegin()82*61046927SAndroid Build Coastguard Worker constexpr const_iterator cbegin() const noexcept { return begin(); } 83*61046927SAndroid Build Coastguard Worker 84*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_iterator to the end of the span 85*61046927SAndroid Build Coastguard Worker * \return data + length 86*61046927SAndroid Build Coastguard Worker */ cend()87*61046927SAndroid Build Coastguard Worker constexpr const_iterator cend() const noexcept { return std::next(begin(), length); } 88*61046927SAndroid Build Coastguard Worker 89*61046927SAndroid Build Coastguard Worker /*! \brief Returns a reverse_iterator to the end of the span 90*61046927SAndroid Build Coastguard Worker * \return reverse_iterator(end()) 91*61046927SAndroid Build Coastguard Worker */ rbegin()92*61046927SAndroid Build Coastguard Worker constexpr reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } 93*61046927SAndroid Build Coastguard Worker 94*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_reverse_iterator to the end of the span 95*61046927SAndroid Build Coastguard Worker * \return reverse_iterator(end()) 96*61046927SAndroid Build Coastguard Worker */ rbegin()97*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator rbegin() const noexcept 98*61046927SAndroid Build Coastguard Worker { 99*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(end()); 100*61046927SAndroid Build Coastguard Worker } 101*61046927SAndroid Build Coastguard Worker 102*61046927SAndroid Build Coastguard Worker /*! \brief Returns a reverse_iterator to the begin of the span 103*61046927SAndroid Build Coastguard Worker * \return reverse_iterator(begin()) 104*61046927SAndroid Build Coastguard Worker */ rend()105*61046927SAndroid Build Coastguard Worker constexpr reverse_iterator rend() noexcept { return reverse_iterator(begin()); } 106*61046927SAndroid Build Coastguard Worker 107*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_reverse_iterator to the begin of the span 108*61046927SAndroid Build Coastguard Worker * \return reverse_iterator(begin()) 109*61046927SAndroid Build Coastguard Worker */ rend()110*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator rend() const noexcept 111*61046927SAndroid Build Coastguard Worker { 112*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(begin()); 113*61046927SAndroid Build Coastguard Worker } 114*61046927SAndroid Build Coastguard Worker 115*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_reverse_iterator to the end of the span 116*61046927SAndroid Build Coastguard Worker * \return rbegin() 117*61046927SAndroid Build Coastguard Worker */ crbegin()118*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator crbegin() const noexcept 119*61046927SAndroid Build Coastguard Worker { 120*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(cend()); 121*61046927SAndroid Build Coastguard Worker } 122*61046927SAndroid Build Coastguard Worker 123*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_reverse_iterator to the begin of the span 124*61046927SAndroid Build Coastguard Worker * \return rend() 125*61046927SAndroid Build Coastguard Worker */ crend()126*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator crend() const noexcept 127*61046927SAndroid Build Coastguard Worker { 128*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(cbegin()); 129*61046927SAndroid Build Coastguard Worker } 130*61046927SAndroid Build Coastguard Worker 131*61046927SAndroid Build Coastguard Worker /*! \brief Unchecked access operator 132*61046927SAndroid Build Coastguard Worker * \param[in] index Index of the element we want to access 133*61046927SAndroid Build Coastguard Worker * \return *(std::next(data, index)) 134*61046927SAndroid Build Coastguard Worker */ 135*61046927SAndroid Build Coastguard Worker constexpr reference operator[](const size_type index) noexcept 136*61046927SAndroid Build Coastguard Worker { 137*61046927SAndroid Build Coastguard Worker assert(length > index); 138*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), index)); 139*61046927SAndroid Build Coastguard Worker } 140*61046927SAndroid Build Coastguard Worker 141*61046927SAndroid Build Coastguard Worker /*! \brief Unchecked const access operator 142*61046927SAndroid Build Coastguard Worker * \param[in] index Index of the element we want to access 143*61046927SAndroid Build Coastguard Worker * \return *(std::next(data, index)) 144*61046927SAndroid Build Coastguard Worker */ 145*61046927SAndroid Build Coastguard Worker constexpr const_reference operator[](const size_type index) const noexcept 146*61046927SAndroid Build Coastguard Worker { 147*61046927SAndroid Build Coastguard Worker assert(length > index); 148*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), index)); 149*61046927SAndroid Build Coastguard Worker } 150*61046927SAndroid Build Coastguard Worker 151*61046927SAndroid Build Coastguard Worker /*! \brief Returns a reference to the last element of the span 152*61046927SAndroid Build Coastguard Worker * \return *(std::next(data, length - 1)) 153*61046927SAndroid Build Coastguard Worker */ back()154*61046927SAndroid Build Coastguard Worker constexpr reference back() noexcept 155*61046927SAndroid Build Coastguard Worker { 156*61046927SAndroid Build Coastguard Worker assert(length > 0); 157*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), length - 1)); 158*61046927SAndroid Build Coastguard Worker } 159*61046927SAndroid Build Coastguard Worker 160*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_reference to the last element of the span 161*61046927SAndroid Build Coastguard Worker * \return *(std::next(data, length - 1)) 162*61046927SAndroid Build Coastguard Worker */ back()163*61046927SAndroid Build Coastguard Worker constexpr const_reference back() const noexcept 164*61046927SAndroid Build Coastguard Worker { 165*61046927SAndroid Build Coastguard Worker assert(length > 0); 166*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), length - 1)); 167*61046927SAndroid Build Coastguard Worker } 168*61046927SAndroid Build Coastguard Worker 169*61046927SAndroid Build Coastguard Worker /*! \brief Returns a reference to the first element of the span 170*61046927SAndroid Build Coastguard Worker * \return *begin() 171*61046927SAndroid Build Coastguard Worker */ front()172*61046927SAndroid Build Coastguard Worker constexpr reference front() noexcept 173*61046927SAndroid Build Coastguard Worker { 174*61046927SAndroid Build Coastguard Worker assert(length > 0); 175*61046927SAndroid Build Coastguard Worker return *begin(); 176*61046927SAndroid Build Coastguard Worker } 177*61046927SAndroid Build Coastguard Worker 178*61046927SAndroid Build Coastguard Worker /*! \brief Returns a const_reference to the first element of the span 179*61046927SAndroid Build Coastguard Worker * \return *cbegin() 180*61046927SAndroid Build Coastguard Worker */ front()181*61046927SAndroid Build Coastguard Worker constexpr const_reference front() const noexcept 182*61046927SAndroid Build Coastguard Worker { 183*61046927SAndroid Build Coastguard Worker assert(length > 0); 184*61046927SAndroid Build Coastguard Worker return *cbegin(); 185*61046927SAndroid Build Coastguard Worker } 186*61046927SAndroid Build Coastguard Worker 187*61046927SAndroid Build Coastguard Worker /*! \brief Returns true if the span is empty 188*61046927SAndroid Build Coastguard Worker * \return length == 0 189*61046927SAndroid Build Coastguard Worker */ empty()190*61046927SAndroid Build Coastguard Worker constexpr bool empty() const noexcept { return length == 0; } 191*61046927SAndroid Build Coastguard Worker 192*61046927SAndroid Build Coastguard Worker /*! \brief Returns the size of the span 193*61046927SAndroid Build Coastguard Worker * \return length == 0 194*61046927SAndroid Build Coastguard Worker */ size()195*61046927SAndroid Build Coastguard Worker constexpr size_type size() const noexcept { return length; } 196*61046927SAndroid Build Coastguard Worker 197*61046927SAndroid Build Coastguard Worker /*! \brief Decreases the size of the span by 1 198*61046927SAndroid Build Coastguard Worker */ pop_back()199*61046927SAndroid Build Coastguard Worker constexpr void pop_back() noexcept 200*61046927SAndroid Build Coastguard Worker { 201*61046927SAndroid Build Coastguard Worker assert(length > 0); 202*61046927SAndroid Build Coastguard Worker --length; 203*61046927SAndroid Build Coastguard Worker } 204*61046927SAndroid Build Coastguard Worker 205*61046927SAndroid Build Coastguard Worker /*! \brief Adds an element to the end of the span 206*61046927SAndroid Build Coastguard Worker */ push_back(const_reference val)207*61046927SAndroid Build Coastguard Worker constexpr void push_back(const_reference val) noexcept { *std::next(begin(), length++) = val; } 208*61046927SAndroid Build Coastguard Worker 209*61046927SAndroid Build Coastguard Worker /*! \brief Clears the span 210*61046927SAndroid Build Coastguard Worker */ clear()211*61046927SAndroid Build Coastguard Worker constexpr void clear() noexcept 212*61046927SAndroid Build Coastguard Worker { 213*61046927SAndroid Build Coastguard Worker offset = 0; 214*61046927SAndroid Build Coastguard Worker length = 0; 215*61046927SAndroid Build Coastguard Worker } 216*61046927SAndroid Build Coastguard Worker 217*61046927SAndroid Build Coastguard Worker private: 218*61046927SAndroid Build Coastguard Worker uint16_t offset{0}; //!> Byte offset from span to data 219*61046927SAndroid Build Coastguard Worker size_type length{0}; //!> Size of the span 220*61046927SAndroid Build Coastguard Worker }; 221*61046927SAndroid Build Coastguard Worker 222*61046927SAndroid Build Coastguard Worker /* 223*61046927SAndroid Build Coastguard Worker * Light-weight memory resource which allows to sequentially allocate from 224*61046927SAndroid Build Coastguard Worker * a buffer. Both, the release() method and the destructor release all managed 225*61046927SAndroid Build Coastguard Worker * memory. 226*61046927SAndroid Build Coastguard Worker * 227*61046927SAndroid Build Coastguard Worker * The memory resource is not thread-safe. 228*61046927SAndroid Build Coastguard Worker * This class mimics std::pmr::monotonic_buffer_resource 229*61046927SAndroid Build Coastguard Worker */ 230*61046927SAndroid Build Coastguard Worker class monotonic_buffer_resource final { 231*61046927SAndroid Build Coastguard Worker public: 232*61046927SAndroid Build Coastguard Worker explicit monotonic_buffer_resource(size_t size = initial_size) 233*61046927SAndroid Build Coastguard Worker { 234*61046927SAndroid Build Coastguard Worker /* The size parameter refers to the total size of the buffer. 235*61046927SAndroid Build Coastguard Worker * The usable data_size is size - sizeof(Buffer). 236*61046927SAndroid Build Coastguard Worker */ 237*61046927SAndroid Build Coastguard Worker size = MAX2(size, minimum_size); 238*61046927SAndroid Build Coastguard Worker buffer = (Buffer*)malloc(size); 239*61046927SAndroid Build Coastguard Worker buffer->next = nullptr; 240*61046927SAndroid Build Coastguard Worker buffer->data_size = size - sizeof(Buffer); 241*61046927SAndroid Build Coastguard Worker buffer->current_idx = 0; 242*61046927SAndroid Build Coastguard Worker } 243*61046927SAndroid Build Coastguard Worker ~monotonic_buffer_resource()244*61046927SAndroid Build Coastguard Worker ~monotonic_buffer_resource() 245*61046927SAndroid Build Coastguard Worker { 246*61046927SAndroid Build Coastguard Worker release(); 247*61046927SAndroid Build Coastguard Worker free(buffer); 248*61046927SAndroid Build Coastguard Worker } 249*61046927SAndroid Build Coastguard Worker 250*61046927SAndroid Build Coastguard Worker /* Move-constructor and -assignment */ monotonic_buffer_resource(monotonic_buffer_resource && other)251*61046927SAndroid Build Coastguard Worker monotonic_buffer_resource(monotonic_buffer_resource&& other) : monotonic_buffer_resource() 252*61046927SAndroid Build Coastguard Worker { 253*61046927SAndroid Build Coastguard Worker *this = std::move(other); 254*61046927SAndroid Build Coastguard Worker } 255*61046927SAndroid Build Coastguard Worker monotonic_buffer_resource& operator=(monotonic_buffer_resource&& other) 256*61046927SAndroid Build Coastguard Worker { 257*61046927SAndroid Build Coastguard Worker release(); 258*61046927SAndroid Build Coastguard Worker std::swap(buffer, other.buffer); 259*61046927SAndroid Build Coastguard Worker return *this; 260*61046927SAndroid Build Coastguard Worker } 261*61046927SAndroid Build Coastguard Worker 262*61046927SAndroid Build Coastguard Worker /* Delete copy-constructor and -assignment to avoid double free() */ 263*61046927SAndroid Build Coastguard Worker monotonic_buffer_resource(const monotonic_buffer_resource&) = delete; 264*61046927SAndroid Build Coastguard Worker monotonic_buffer_resource& operator=(const monotonic_buffer_resource&) = delete; 265*61046927SAndroid Build Coastguard Worker allocate(size_t size,size_t alignment)266*61046927SAndroid Build Coastguard Worker void* allocate(size_t size, size_t alignment) 267*61046927SAndroid Build Coastguard Worker { 268*61046927SAndroid Build Coastguard Worker buffer->current_idx = align(buffer->current_idx, alignment); 269*61046927SAndroid Build Coastguard Worker if (buffer->current_idx + size <= buffer->data_size) { 270*61046927SAndroid Build Coastguard Worker uint8_t* ptr = &buffer->data[buffer->current_idx]; 271*61046927SAndroid Build Coastguard Worker buffer->current_idx += size; 272*61046927SAndroid Build Coastguard Worker return ptr; 273*61046927SAndroid Build Coastguard Worker } 274*61046927SAndroid Build Coastguard Worker 275*61046927SAndroid Build Coastguard Worker /* create new larger buffer */ 276*61046927SAndroid Build Coastguard Worker uint32_t total_size = buffer->data_size + sizeof(Buffer); 277*61046927SAndroid Build Coastguard Worker do { 278*61046927SAndroid Build Coastguard Worker total_size *= 2; 279*61046927SAndroid Build Coastguard Worker } while (total_size - sizeof(Buffer) < size); 280*61046927SAndroid Build Coastguard Worker Buffer* next = buffer; 281*61046927SAndroid Build Coastguard Worker buffer = (Buffer*)malloc(total_size); 282*61046927SAndroid Build Coastguard Worker buffer->next = next; 283*61046927SAndroid Build Coastguard Worker buffer->data_size = total_size - sizeof(Buffer); 284*61046927SAndroid Build Coastguard Worker buffer->current_idx = 0; 285*61046927SAndroid Build Coastguard Worker 286*61046927SAndroid Build Coastguard Worker return allocate(size, alignment); 287*61046927SAndroid Build Coastguard Worker } 288*61046927SAndroid Build Coastguard Worker release()289*61046927SAndroid Build Coastguard Worker void release() 290*61046927SAndroid Build Coastguard Worker { 291*61046927SAndroid Build Coastguard Worker while (buffer->next) { 292*61046927SAndroid Build Coastguard Worker Buffer* next = buffer->next; 293*61046927SAndroid Build Coastguard Worker free(buffer); 294*61046927SAndroid Build Coastguard Worker buffer = next; 295*61046927SAndroid Build Coastguard Worker } 296*61046927SAndroid Build Coastguard Worker buffer->current_idx = 0; 297*61046927SAndroid Build Coastguard Worker } 298*61046927SAndroid Build Coastguard Worker 299*61046927SAndroid Build Coastguard Worker bool operator==(const monotonic_buffer_resource& other) { return buffer == other.buffer; } 300*61046927SAndroid Build Coastguard Worker 301*61046927SAndroid Build Coastguard Worker private: 302*61046927SAndroid Build Coastguard Worker struct Buffer { 303*61046927SAndroid Build Coastguard Worker Buffer* next; 304*61046927SAndroid Build Coastguard Worker uint32_t current_idx; 305*61046927SAndroid Build Coastguard Worker uint32_t data_size; 306*61046927SAndroid Build Coastguard Worker uint8_t data[]; 307*61046927SAndroid Build Coastguard Worker }; 308*61046927SAndroid Build Coastguard Worker 309*61046927SAndroid Build Coastguard Worker Buffer* buffer; 310*61046927SAndroid Build Coastguard Worker static constexpr size_t initial_size = 4096; 311*61046927SAndroid Build Coastguard Worker static constexpr size_t minimum_size = 128; 312*61046927SAndroid Build Coastguard Worker static_assert(minimum_size > sizeof(Buffer)); 313*61046927SAndroid Build Coastguard Worker }; 314*61046927SAndroid Build Coastguard Worker 315*61046927SAndroid Build Coastguard Worker /* 316*61046927SAndroid Build Coastguard Worker * Small memory allocator which wraps monotonic_buffer_resource 317*61046927SAndroid Build Coastguard Worker * in order to implement <allocator_traits>. 318*61046927SAndroid Build Coastguard Worker * 319*61046927SAndroid Build Coastguard Worker * This class mimics std::pmr::polymorphic_allocator with monotonic_buffer_resource 320*61046927SAndroid Build Coastguard Worker * as memory resource. The advantage of this specialization is the absence of 321*61046927SAndroid Build Coastguard Worker * virtual function calls and the propagation on swap, copy- and move assignment. 322*61046927SAndroid Build Coastguard Worker */ 323*61046927SAndroid Build Coastguard Worker template <typename T> class monotonic_allocator { 324*61046927SAndroid Build Coastguard Worker public: 325*61046927SAndroid Build Coastguard Worker monotonic_allocator() = delete; monotonic_allocator(monotonic_buffer_resource & m)326*61046927SAndroid Build Coastguard Worker monotonic_allocator(monotonic_buffer_resource& m) : memory_resource(m) {} 327*61046927SAndroid Build Coastguard Worker template <typename U> monotonic_allocator(const monotonic_allocator<U> & rhs)328*61046927SAndroid Build Coastguard Worker explicit monotonic_allocator(const monotonic_allocator<U>& rhs) 329*61046927SAndroid Build Coastguard Worker : memory_resource(rhs.memory_resource) 330*61046927SAndroid Build Coastguard Worker {} 331*61046927SAndroid Build Coastguard Worker 332*61046927SAndroid Build Coastguard Worker /* Memory Allocation */ allocate(size_t size)333*61046927SAndroid Build Coastguard Worker T* allocate(size_t size) 334*61046927SAndroid Build Coastguard Worker { 335*61046927SAndroid Build Coastguard Worker uint32_t bytes = sizeof(T) * size; 336*61046927SAndroid Build Coastguard Worker return (T*)memory_resource.get().allocate(bytes, alignof(T)); 337*61046927SAndroid Build Coastguard Worker } 338*61046927SAndroid Build Coastguard Worker 339*61046927SAndroid Build Coastguard Worker /* Memory will be freed on destruction of memory_resource */ deallocate(T * ptr,size_t size)340*61046927SAndroid Build Coastguard Worker void deallocate(T* ptr, size_t size) {} 341*61046927SAndroid Build Coastguard Worker 342*61046927SAndroid Build Coastguard Worker /* Implement <allocator_traits> */ 343*61046927SAndroid Build Coastguard Worker using value_type = T; 344*61046927SAndroid Build Coastguard Worker template <class U> struct rebind { 345*61046927SAndroid Build Coastguard Worker using other = monotonic_allocator<U>; 346*61046927SAndroid Build Coastguard Worker }; 347*61046927SAndroid Build Coastguard Worker 348*61046927SAndroid Build Coastguard Worker typedef std::true_type propagate_on_container_copy_assignment; 349*61046927SAndroid Build Coastguard Worker typedef std::true_type propagate_on_container_move_assignment; 350*61046927SAndroid Build Coastguard Worker typedef std::true_type propagate_on_container_swap; 351*61046927SAndroid Build Coastguard Worker 352*61046927SAndroid Build Coastguard Worker template <typename> friend class monotonic_allocator; 353*61046927SAndroid Build Coastguard Worker template <typename X, typename Y> 354*61046927SAndroid Build Coastguard Worker friend bool operator==(monotonic_allocator<X> const& a, monotonic_allocator<Y> const& b); 355*61046927SAndroid Build Coastguard Worker template <typename X, typename Y> 356*61046927SAndroid Build Coastguard Worker friend bool operator!=(monotonic_allocator<X> const& a, monotonic_allocator<Y> const& b); 357*61046927SAndroid Build Coastguard Worker 358*61046927SAndroid Build Coastguard Worker private: 359*61046927SAndroid Build Coastguard Worker std::reference_wrapper<monotonic_buffer_resource> memory_resource; 360*61046927SAndroid Build Coastguard Worker }; 361*61046927SAndroid Build Coastguard Worker 362*61046927SAndroid Build Coastguard Worker /* Necessary for <allocator_traits>. */ 363*61046927SAndroid Build Coastguard Worker template <typename X, typename Y> 364*61046927SAndroid Build Coastguard Worker inline bool 365*61046927SAndroid Build Coastguard Worker operator==(monotonic_allocator<X> const& a, monotonic_allocator<Y> const& b) 366*61046927SAndroid Build Coastguard Worker { 367*61046927SAndroid Build Coastguard Worker return a.memory_resource.get() == b.memory_resource.get(); 368*61046927SAndroid Build Coastguard Worker } 369*61046927SAndroid Build Coastguard Worker template <typename X, typename Y> 370*61046927SAndroid Build Coastguard Worker inline bool 371*61046927SAndroid Build Coastguard Worker operator!=(monotonic_allocator<X> const& a, monotonic_allocator<Y> const& b) 372*61046927SAndroid Build Coastguard Worker { 373*61046927SAndroid Build Coastguard Worker return !(a == b); 374*61046927SAndroid Build Coastguard Worker } 375*61046927SAndroid Build Coastguard Worker 376*61046927SAndroid Build Coastguard Worker /* 377*61046927SAndroid Build Coastguard Worker * aco::map - alias for std::map with monotonic_allocator 378*61046927SAndroid Build Coastguard Worker * 379*61046927SAndroid Build Coastguard Worker * This template specialization mimics std::pmr::map. 380*61046927SAndroid Build Coastguard Worker */ 381*61046927SAndroid Build Coastguard Worker template <class Key, class T, class Compare = std::less<Key>> 382*61046927SAndroid Build Coastguard Worker using map = std::map<Key, T, Compare, aco::monotonic_allocator<std::pair<const Key, T>>>; 383*61046927SAndroid Build Coastguard Worker 384*61046927SAndroid Build Coastguard Worker /* 385*61046927SAndroid Build Coastguard Worker * aco::unordered_map - alias for std::unordered_map with monotonic_allocator 386*61046927SAndroid Build Coastguard Worker * 387*61046927SAndroid Build Coastguard Worker * This template specialization mimics std::pmr::unordered_map. 388*61046927SAndroid Build Coastguard Worker */ 389*61046927SAndroid Build Coastguard Worker template <class Key, class T, class Hash = std::hash<Key>, class Pred = std::equal_to<Key>> 390*61046927SAndroid Build Coastguard Worker using unordered_map = 391*61046927SAndroid Build Coastguard Worker std::unordered_map<Key, T, Hash, Pred, aco::monotonic_allocator<std::pair<const Key, T>>>; 392*61046927SAndroid Build Coastguard Worker 393*61046927SAndroid Build Coastguard Worker /* 394*61046927SAndroid Build Coastguard Worker * Cache-friendly set of 32-bit IDs with fast insert/erase/lookup and 395*61046927SAndroid Build Coastguard Worker * the ability to efficiently iterate over contained elements. 396*61046927SAndroid Build Coastguard Worker * 397*61046927SAndroid Build Coastguard Worker * Internally implemented as a map of fixed-size bit vectors: If the set contains an ID, the 398*61046927SAndroid Build Coastguard Worker * corresponding bit in the appropriate bit vector is set. It doesn't use std::vector<bool> since 399*61046927SAndroid Build Coastguard Worker * we then couldn't efficiently iterate over the elements. 400*61046927SAndroid Build Coastguard Worker * 401*61046927SAndroid Build Coastguard Worker * The interface resembles a subset of std::set/std::unordered_set. 402*61046927SAndroid Build Coastguard Worker */ 403*61046927SAndroid Build Coastguard Worker struct IDSet { 404*61046927SAndroid Build Coastguard Worker static const uint32_t block_size = 1024u; 405*61046927SAndroid Build Coastguard Worker using block_t = std::array<uint64_t, block_size / 64>; 406*61046927SAndroid Build Coastguard Worker 407*61046927SAndroid Build Coastguard Worker struct Iterator { 408*61046927SAndroid Build Coastguard Worker const IDSet* set; 409*61046927SAndroid Build Coastguard Worker aco::map<uint32_t, block_t>::const_iterator block; 410*61046927SAndroid Build Coastguard Worker uint32_t id; 411*61046927SAndroid Build Coastguard Worker 412*61046927SAndroid Build Coastguard Worker Iterator& operator++(); 413*61046927SAndroid Build Coastguard Worker 414*61046927SAndroid Build Coastguard Worker bool operator!=(const Iterator& other) const; 415*61046927SAndroid Build Coastguard Worker 416*61046927SAndroid Build Coastguard Worker uint32_t operator*() const; 417*61046927SAndroid Build Coastguard Worker }; 418*61046927SAndroid Build Coastguard Worker countIDSet419*61046927SAndroid Build Coastguard Worker size_t count(uint32_t id) const { return find(id) != end(); } 420*61046927SAndroid Build Coastguard Worker findIDSet421*61046927SAndroid Build Coastguard Worker Iterator find(uint32_t id) const 422*61046927SAndroid Build Coastguard Worker { 423*61046927SAndroid Build Coastguard Worker uint32_t block_index = id / block_size; 424*61046927SAndroid Build Coastguard Worker auto it = words.find(block_index); 425*61046927SAndroid Build Coastguard Worker if (it == words.end()) 426*61046927SAndroid Build Coastguard Worker return end(); 427*61046927SAndroid Build Coastguard Worker 428*61046927SAndroid Build Coastguard Worker const block_t& block = it->second; 429*61046927SAndroid Build Coastguard Worker uint32_t sub_id = id % block_size; 430*61046927SAndroid Build Coastguard Worker 431*61046927SAndroid Build Coastguard Worker if (block[sub_id / 64u] & (1ull << (sub_id % 64u))) 432*61046927SAndroid Build Coastguard Worker return Iterator{this, it, id}; 433*61046927SAndroid Build Coastguard Worker else 434*61046927SAndroid Build Coastguard Worker return end(); 435*61046927SAndroid Build Coastguard Worker } 436*61046927SAndroid Build Coastguard Worker insertIDSet437*61046927SAndroid Build Coastguard Worker std::pair<Iterator, bool> insert(uint32_t id) 438*61046927SAndroid Build Coastguard Worker { 439*61046927SAndroid Build Coastguard Worker uint32_t block_index = id / block_size; 440*61046927SAndroid Build Coastguard Worker auto it = words.try_emplace(block_index).first; 441*61046927SAndroid Build Coastguard Worker block_t& block = it->second; 442*61046927SAndroid Build Coastguard Worker uint32_t sub_id = id % block_size; 443*61046927SAndroid Build Coastguard Worker 444*61046927SAndroid Build Coastguard Worker uint64_t* word = &block[sub_id / 64u]; 445*61046927SAndroid Build Coastguard Worker uint64_t mask = 1ull << (sub_id % 64u); 446*61046927SAndroid Build Coastguard Worker if (*word & mask) 447*61046927SAndroid Build Coastguard Worker return std::make_pair(Iterator{this, it, id}, false); 448*61046927SAndroid Build Coastguard Worker 449*61046927SAndroid Build Coastguard Worker *word |= mask; 450*61046927SAndroid Build Coastguard Worker return std::make_pair(Iterator{this, it, id}, true); 451*61046927SAndroid Build Coastguard Worker } 452*61046927SAndroid Build Coastguard Worker insertIDSet453*61046927SAndroid Build Coastguard Worker bool insert(const IDSet other) 454*61046927SAndroid Build Coastguard Worker { 455*61046927SAndroid Build Coastguard Worker bool inserted = false; 456*61046927SAndroid Build Coastguard Worker 457*61046927SAndroid Build Coastguard Worker for (auto it = other.words.begin(); it != other.words.end(); ++it) { 458*61046927SAndroid Build Coastguard Worker const block_t& src = it->second; 459*61046927SAndroid Build Coastguard Worker if (src == block_t{0}) 460*61046927SAndroid Build Coastguard Worker continue; 461*61046927SAndroid Build Coastguard Worker 462*61046927SAndroid Build Coastguard Worker block_t& dst = words[it->first]; 463*61046927SAndroid Build Coastguard Worker for (unsigned j = 0; j < src.size(); j++) { 464*61046927SAndroid Build Coastguard Worker uint64_t new_bits = src[j] & ~dst[j]; 465*61046927SAndroid Build Coastguard Worker if (new_bits) { 466*61046927SAndroid Build Coastguard Worker inserted = true; 467*61046927SAndroid Build Coastguard Worker dst[j] |= new_bits; 468*61046927SAndroid Build Coastguard Worker } 469*61046927SAndroid Build Coastguard Worker } 470*61046927SAndroid Build Coastguard Worker } 471*61046927SAndroid Build Coastguard Worker return inserted; 472*61046927SAndroid Build Coastguard Worker } 473*61046927SAndroid Build Coastguard Worker eraseIDSet474*61046927SAndroid Build Coastguard Worker size_t erase(uint32_t id) 475*61046927SAndroid Build Coastguard Worker { 476*61046927SAndroid Build Coastguard Worker uint32_t block_index = id / block_size; 477*61046927SAndroid Build Coastguard Worker auto it = words.find(block_index); 478*61046927SAndroid Build Coastguard Worker if (it == words.end()) 479*61046927SAndroid Build Coastguard Worker return 0; 480*61046927SAndroid Build Coastguard Worker 481*61046927SAndroid Build Coastguard Worker block_t& block = it->second; 482*61046927SAndroid Build Coastguard Worker uint32_t sub_id = id % block_size; 483*61046927SAndroid Build Coastguard Worker 484*61046927SAndroid Build Coastguard Worker uint64_t* word = &block[sub_id / 64u]; 485*61046927SAndroid Build Coastguard Worker uint64_t mask = 1ull << (sub_id % 64u); 486*61046927SAndroid Build Coastguard Worker if (!(*word & mask)) 487*61046927SAndroid Build Coastguard Worker return 0; 488*61046927SAndroid Build Coastguard Worker 489*61046927SAndroid Build Coastguard Worker *word ^= mask; 490*61046927SAndroid Build Coastguard Worker return 1; 491*61046927SAndroid Build Coastguard Worker } 492*61046927SAndroid Build Coastguard Worker cbeginIDSet493*61046927SAndroid Build Coastguard Worker Iterator cbegin() const 494*61046927SAndroid Build Coastguard Worker { 495*61046927SAndroid Build Coastguard Worker Iterator res; 496*61046927SAndroid Build Coastguard Worker res.set = this; 497*61046927SAndroid Build Coastguard Worker 498*61046927SAndroid Build Coastguard Worker for (auto it = words.begin(); it != words.end(); ++it) { 499*61046927SAndroid Build Coastguard Worker uint32_t first = get_first_set(it->second); 500*61046927SAndroid Build Coastguard Worker if (first != UINT32_MAX) { 501*61046927SAndroid Build Coastguard Worker res.block = it; 502*61046927SAndroid Build Coastguard Worker res.id = it->first * block_size + first; 503*61046927SAndroid Build Coastguard Worker return res; 504*61046927SAndroid Build Coastguard Worker } 505*61046927SAndroid Build Coastguard Worker } 506*61046927SAndroid Build Coastguard Worker 507*61046927SAndroid Build Coastguard Worker return cend(); 508*61046927SAndroid Build Coastguard Worker } 509*61046927SAndroid Build Coastguard Worker cendIDSet510*61046927SAndroid Build Coastguard Worker Iterator cend() const { return Iterator{this, words.end(), UINT32_MAX}; } 511*61046927SAndroid Build Coastguard Worker beginIDSet512*61046927SAndroid Build Coastguard Worker Iterator begin() const { return cbegin(); } 513*61046927SAndroid Build Coastguard Worker endIDSet514*61046927SAndroid Build Coastguard Worker Iterator end() const { return cend(); } 515*61046927SAndroid Build Coastguard Worker sizeIDSet516*61046927SAndroid Build Coastguard Worker size_t size() const 517*61046927SAndroid Build Coastguard Worker { 518*61046927SAndroid Build Coastguard Worker size_t bits_set = 0; 519*61046927SAndroid Build Coastguard Worker for (auto block : words) { 520*61046927SAndroid Build Coastguard Worker for (uint64_t word : block.second) 521*61046927SAndroid Build Coastguard Worker bits_set += util_bitcount64(word); 522*61046927SAndroid Build Coastguard Worker } 523*61046927SAndroid Build Coastguard Worker return bits_set; 524*61046927SAndroid Build Coastguard Worker } 525*61046927SAndroid Build Coastguard Worker emptyIDSet526*61046927SAndroid Build Coastguard Worker bool empty() const { return !size(); } 527*61046927SAndroid Build Coastguard Worker IDSetIDSet528*61046927SAndroid Build Coastguard Worker explicit IDSet(monotonic_buffer_resource& m) : words(m) {} IDSetIDSet529*61046927SAndroid Build Coastguard Worker explicit IDSet(const IDSet& other, monotonic_buffer_resource& m) : words(other.words, m) {} 530*61046927SAndroid Build Coastguard Worker 531*61046927SAndroid Build Coastguard Worker bool operator==(const IDSet& other) const 532*61046927SAndroid Build Coastguard Worker { 533*61046927SAndroid Build Coastguard Worker auto it = words.begin(); 534*61046927SAndroid Build Coastguard Worker for (auto block : other.words) { 535*61046927SAndroid Build Coastguard Worker if (block.second == block_t{0}) 536*61046927SAndroid Build Coastguard Worker continue; 537*61046927SAndroid Build Coastguard Worker while (it != words.end() && it->second == block_t{0}) 538*61046927SAndroid Build Coastguard Worker it++; 539*61046927SAndroid Build Coastguard Worker if (it == words.end() || block != *it) 540*61046927SAndroid Build Coastguard Worker return false; 541*61046927SAndroid Build Coastguard Worker it++; 542*61046927SAndroid Build Coastguard Worker } 543*61046927SAndroid Build Coastguard Worker 544*61046927SAndroid Build Coastguard Worker return true; 545*61046927SAndroid Build Coastguard Worker } 546*61046927SAndroid Build Coastguard Worker bool operator!=(const IDSet& other) const { return !(*this == other); } 547*61046927SAndroid Build Coastguard Worker 548*61046927SAndroid Build Coastguard Worker private: get_first_setIDSet549*61046927SAndroid Build Coastguard Worker static uint32_t get_first_set(const block_t& words) 550*61046927SAndroid Build Coastguard Worker { 551*61046927SAndroid Build Coastguard Worker for (size_t i = 0; i < words.size(); i++) { 552*61046927SAndroid Build Coastguard Worker if (words[i]) 553*61046927SAndroid Build Coastguard Worker return i * 64u + (ffsll(words[i]) - 1); 554*61046927SAndroid Build Coastguard Worker } 555*61046927SAndroid Build Coastguard Worker return UINT32_MAX; 556*61046927SAndroid Build Coastguard Worker } 557*61046927SAndroid Build Coastguard Worker 558*61046927SAndroid Build Coastguard Worker aco::map<uint32_t, block_t> words; 559*61046927SAndroid Build Coastguard Worker }; 560*61046927SAndroid Build Coastguard Worker 561*61046927SAndroid Build Coastguard Worker inline IDSet::Iterator& 562*61046927SAndroid Build Coastguard Worker IDSet::Iterator::operator++() 563*61046927SAndroid Build Coastguard Worker { 564*61046927SAndroid Build Coastguard Worker uint32_t block_index = id / block_size; 565*61046927SAndroid Build Coastguard Worker const block_t& block_words = block->second; 566*61046927SAndroid Build Coastguard Worker uint32_t sub_id = id % block_size; 567*61046927SAndroid Build Coastguard Worker 568*61046927SAndroid Build Coastguard Worker uint64_t m = block_words[sub_id / 64u]; 569*61046927SAndroid Build Coastguard Worker uint32_t bit = sub_id % 64u; 570*61046927SAndroid Build Coastguard Worker m = (m >> bit) >> 1; 571*61046927SAndroid Build Coastguard Worker if (m) { 572*61046927SAndroid Build Coastguard Worker id += ffsll(m); 573*61046927SAndroid Build Coastguard Worker return *this; 574*61046927SAndroid Build Coastguard Worker } 575*61046927SAndroid Build Coastguard Worker 576*61046927SAndroid Build Coastguard Worker for (uint32_t i = sub_id / 64u + 1; i < block_words.size(); i++) { 577*61046927SAndroid Build Coastguard Worker if (block_words[i]) { 578*61046927SAndroid Build Coastguard Worker id = block_index * block_size + i * 64u + ffsll(block_words[i]) - 1; 579*61046927SAndroid Build Coastguard Worker return *this; 580*61046927SAndroid Build Coastguard Worker } 581*61046927SAndroid Build Coastguard Worker } 582*61046927SAndroid Build Coastguard Worker 583*61046927SAndroid Build Coastguard Worker for (++block; block != set->words.end(); ++block) { 584*61046927SAndroid Build Coastguard Worker uint32_t first = get_first_set(block->second); 585*61046927SAndroid Build Coastguard Worker if (first != UINT32_MAX) { 586*61046927SAndroid Build Coastguard Worker id = block->first * block_size + first; 587*61046927SAndroid Build Coastguard Worker return *this; 588*61046927SAndroid Build Coastguard Worker } 589*61046927SAndroid Build Coastguard Worker } 590*61046927SAndroid Build Coastguard Worker 591*61046927SAndroid Build Coastguard Worker id = UINT32_MAX; 592*61046927SAndroid Build Coastguard Worker return *this; 593*61046927SAndroid Build Coastguard Worker } 594*61046927SAndroid Build Coastguard Worker 595*61046927SAndroid Build Coastguard Worker inline bool 596*61046927SAndroid Build Coastguard Worker IDSet::Iterator::operator!=(const IDSet::Iterator& other) const 597*61046927SAndroid Build Coastguard Worker { 598*61046927SAndroid Build Coastguard Worker assert(set == other.set); 599*61046927SAndroid Build Coastguard Worker assert(id != other.id || block == other.block); 600*61046927SAndroid Build Coastguard Worker return id != other.id; 601*61046927SAndroid Build Coastguard Worker } 602*61046927SAndroid Build Coastguard Worker 603*61046927SAndroid Build Coastguard Worker inline uint32_t 604*61046927SAndroid Build Coastguard Worker IDSet::Iterator::operator*() const 605*61046927SAndroid Build Coastguard Worker { 606*61046927SAndroid Build Coastguard Worker return id; 607*61046927SAndroid Build Coastguard Worker } 608*61046927SAndroid Build Coastguard Worker 609*61046927SAndroid Build Coastguard Worker /* 610*61046927SAndroid Build Coastguard Worker * Helper class for a integer/bool (access_type) packed into 611*61046927SAndroid Build Coastguard Worker * a bigger integer (data_type) with an offset and size. 612*61046927SAndroid Build Coastguard Worker * It can be implicitly converted to access_type and supports 613*61046927SAndroid Build Coastguard Worker * all arithmetic assignment operators. 614*61046927SAndroid Build Coastguard Worker * 615*61046927SAndroid Build Coastguard Worker * When used together with a union, this allows storing 616*61046927SAndroid Build Coastguard Worker * multiple fields packed into a single integer. 617*61046927SAndroid Build Coastguard Worker * 618*61046927SAndroid Build Coastguard Worker * Example usage: 619*61046927SAndroid Build Coastguard Worker * union { 620*61046927SAndroid Build Coastguard Worker * bitfield_uint<uint32_t, 0, 5, uint8_t> int5; 621*61046927SAndroid Build Coastguard Worker * bitfield_uint<uint32_t, 5, 26, uint32_t> int26; 622*61046927SAndroid Build Coastguard Worker * bitfield_uint<uint32_t, 31, 1, bool> bool1; 623*61046927SAndroid Build Coastguard Worker * }; 624*61046927SAndroid Build Coastguard Worker * 625*61046927SAndroid Build Coastguard Worker */ 626*61046927SAndroid Build Coastguard Worker template <typename data_type, unsigned offset, unsigned size, typename access_type> 627*61046927SAndroid Build Coastguard Worker class bitfield_uint { 628*61046927SAndroid Build Coastguard Worker public: 629*61046927SAndroid Build Coastguard Worker static_assert(sizeof(data_type) >= sizeof(access_type), ""); 630*61046927SAndroid Build Coastguard Worker static_assert(std::is_unsigned<access_type>::value, ""); 631*61046927SAndroid Build Coastguard Worker static_assert(std::is_unsigned<data_type>::value, ""); 632*61046927SAndroid Build Coastguard Worker static_assert(sizeof(data_type) * 8 >= offset + size, ""); 633*61046927SAndroid Build Coastguard Worker static_assert(sizeof(access_type) * 8 >= size, ""); 634*61046927SAndroid Build Coastguard Worker static_assert(size > 0, ""); 635*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool> || size == 1, ""); 636*61046927SAndroid Build Coastguard Worker 637*61046927SAndroid Build Coastguard Worker bitfield_uint() = default; 638*61046927SAndroid Build Coastguard Worker bitfield_uint(const access_type & value)639*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint(const access_type& value) { *this = value; } 640*61046927SAndroid Build Coastguard Worker access_type()641*61046927SAndroid Build Coastguard Worker constexpr operator access_type() const { return (storage >> offset) & mask; } 642*61046927SAndroid Build Coastguard Worker 643*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator=(const access_type& value) 644*61046927SAndroid Build Coastguard Worker { 645*61046927SAndroid Build Coastguard Worker storage &= ~(mask << offset); 646*61046927SAndroid Build Coastguard Worker storage |= data_type(value & mask) << offset; 647*61046927SAndroid Build Coastguard Worker return *this; 648*61046927SAndroid Build Coastguard Worker } 649*61046927SAndroid Build Coastguard Worker 650*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator=(const bitfield_uint& value) 651*61046927SAndroid Build Coastguard Worker { 652*61046927SAndroid Build Coastguard Worker return *this = access_type(value); 653*61046927SAndroid Build Coastguard Worker } 654*61046927SAndroid Build Coastguard Worker 655*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator|=(const access_type& value) 656*61046927SAndroid Build Coastguard Worker { 657*61046927SAndroid Build Coastguard Worker storage |= data_type(value & mask) << offset; 658*61046927SAndroid Build Coastguard Worker return *this; 659*61046927SAndroid Build Coastguard Worker } 660*61046927SAndroid Build Coastguard Worker 661*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator^=(const access_type& value) 662*61046927SAndroid Build Coastguard Worker { 663*61046927SAndroid Build Coastguard Worker storage ^= data_type(value & mask) << offset; 664*61046927SAndroid Build Coastguard Worker return *this; 665*61046927SAndroid Build Coastguard Worker } 666*61046927SAndroid Build Coastguard Worker 667*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator&=(const access_type& value) 668*61046927SAndroid Build Coastguard Worker { 669*61046927SAndroid Build Coastguard Worker storage &= (data_type(value & mask) << offset) | ~(mask << offset); 670*61046927SAndroid Build Coastguard Worker return *this; 671*61046927SAndroid Build Coastguard Worker } 672*61046927SAndroid Build Coastguard Worker 673*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator<<=(const access_type& shift) 674*61046927SAndroid Build Coastguard Worker { 675*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 676*61046927SAndroid Build Coastguard Worker assert(shift < size); 677*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) << shift; 678*61046927SAndroid Build Coastguard Worker } 679*61046927SAndroid Build Coastguard Worker 680*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator>>=(const access_type& shift) 681*61046927SAndroid Build Coastguard Worker { 682*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 683*61046927SAndroid Build Coastguard Worker assert(shift < size); 684*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) >> shift; 685*61046927SAndroid Build Coastguard Worker } 686*61046927SAndroid Build Coastguard Worker 687*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator*=(const access_type& op) 688*61046927SAndroid Build Coastguard Worker { 689*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 690*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) * op; 691*61046927SAndroid Build Coastguard Worker } 692*61046927SAndroid Build Coastguard Worker 693*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator/=(const access_type& op) 694*61046927SAndroid Build Coastguard Worker { 695*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 696*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) / op; 697*61046927SAndroid Build Coastguard Worker } 698*61046927SAndroid Build Coastguard Worker 699*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator%=(const access_type& op) 700*61046927SAndroid Build Coastguard Worker { 701*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 702*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) % op; 703*61046927SAndroid Build Coastguard Worker } 704*61046927SAndroid Build Coastguard Worker 705*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator+=(const access_type& op) 706*61046927SAndroid Build Coastguard Worker { 707*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 708*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) + op; 709*61046927SAndroid Build Coastguard Worker } 710*61046927SAndroid Build Coastguard Worker 711*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator-=(const access_type& op) 712*61046927SAndroid Build Coastguard Worker { 713*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 714*61046927SAndroid Build Coastguard Worker return *this = access_type(*this) - op; 715*61046927SAndroid Build Coastguard Worker } 716*61046927SAndroid Build Coastguard Worker 717*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator++() 718*61046927SAndroid Build Coastguard Worker { 719*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 720*61046927SAndroid Build Coastguard Worker return *this += 1; 721*61046927SAndroid Build Coastguard Worker } 722*61046927SAndroid Build Coastguard Worker 723*61046927SAndroid Build Coastguard Worker constexpr access_type operator++(int) 724*61046927SAndroid Build Coastguard Worker { 725*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 726*61046927SAndroid Build Coastguard Worker access_type temp = *this; 727*61046927SAndroid Build Coastguard Worker ++*this; 728*61046927SAndroid Build Coastguard Worker return temp; 729*61046927SAndroid Build Coastguard Worker } 730*61046927SAndroid Build Coastguard Worker 731*61046927SAndroid Build Coastguard Worker constexpr bitfield_uint& operator--() 732*61046927SAndroid Build Coastguard Worker { 733*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 734*61046927SAndroid Build Coastguard Worker return *this -= 1; 735*61046927SAndroid Build Coastguard Worker } 736*61046927SAndroid Build Coastguard Worker 737*61046927SAndroid Build Coastguard Worker constexpr access_type operator--(int) 738*61046927SAndroid Build Coastguard Worker { 739*61046927SAndroid Build Coastguard Worker static_assert(!std::is_same_v<access_type, bool>, ""); 740*61046927SAndroid Build Coastguard Worker access_type temp = *this; 741*61046927SAndroid Build Coastguard Worker --*this; 742*61046927SAndroid Build Coastguard Worker return temp; 743*61046927SAndroid Build Coastguard Worker } 744*61046927SAndroid Build Coastguard Worker swap(access_type & other)745*61046927SAndroid Build Coastguard Worker constexpr void swap(access_type& other) 746*61046927SAndroid Build Coastguard Worker { 747*61046927SAndroid Build Coastguard Worker access_type tmp = *this; 748*61046927SAndroid Build Coastguard Worker *this = other; 749*61046927SAndroid Build Coastguard Worker other = tmp; 750*61046927SAndroid Build Coastguard Worker } 751*61046927SAndroid Build Coastguard Worker 752*61046927SAndroid Build Coastguard Worker template <typename other_dt, unsigned other_off, unsigned other_s> swap(bitfield_uint<other_dt,other_off,other_s,access_type> & other)753*61046927SAndroid Build Coastguard Worker constexpr void swap(bitfield_uint<other_dt, other_off, other_s, access_type>& other) 754*61046927SAndroid Build Coastguard Worker { 755*61046927SAndroid Build Coastguard Worker access_type tmp = *this; 756*61046927SAndroid Build Coastguard Worker *this = other; 757*61046927SAndroid Build Coastguard Worker other = tmp; 758*61046927SAndroid Build Coastguard Worker } 759*61046927SAndroid Build Coastguard Worker 760*61046927SAndroid Build Coastguard Worker protected: 761*61046927SAndroid Build Coastguard Worker static const data_type mask = BITFIELD64_MASK(size); 762*61046927SAndroid Build Coastguard Worker 763*61046927SAndroid Build Coastguard Worker data_type storage; 764*61046927SAndroid Build Coastguard Worker }; 765*61046927SAndroid Build Coastguard Worker 766*61046927SAndroid Build Coastguard Worker /* 767*61046927SAndroid Build Coastguard Worker * Reference to a single bit in an integer that can be converted to a bool 768*61046927SAndroid Build Coastguard Worker * and supports bool (bitwise) assignment operators. 769*61046927SAndroid Build Coastguard Worker */ 770*61046927SAndroid Build Coastguard Worker template <typename T> struct bit_reference { bit_referencebit_reference771*61046927SAndroid Build Coastguard Worker constexpr bit_reference(T& s, unsigned b) : storage(s), bit(b) {} 772*61046927SAndroid Build Coastguard Worker 773*61046927SAndroid Build Coastguard Worker constexpr bit_reference& operator=(const bit_reference& other) { return *this = (bool)other; } 774*61046927SAndroid Build Coastguard Worker 775*61046927SAndroid Build Coastguard Worker constexpr bit_reference& operator=(bool val) 776*61046927SAndroid Build Coastguard Worker { 777*61046927SAndroid Build Coastguard Worker storage &= ~(T(0x1) << bit); 778*61046927SAndroid Build Coastguard Worker storage |= T(val) << bit; 779*61046927SAndroid Build Coastguard Worker return *this; 780*61046927SAndroid Build Coastguard Worker } 781*61046927SAndroid Build Coastguard Worker 782*61046927SAndroid Build Coastguard Worker constexpr bit_reference& operator^=(bool val) 783*61046927SAndroid Build Coastguard Worker { 784*61046927SAndroid Build Coastguard Worker storage ^= T(val) << bit; 785*61046927SAndroid Build Coastguard Worker return *this; 786*61046927SAndroid Build Coastguard Worker } 787*61046927SAndroid Build Coastguard Worker 788*61046927SAndroid Build Coastguard Worker constexpr bit_reference& operator|=(bool val) 789*61046927SAndroid Build Coastguard Worker { 790*61046927SAndroid Build Coastguard Worker storage |= T(val) << bit; 791*61046927SAndroid Build Coastguard Worker return *this; 792*61046927SAndroid Build Coastguard Worker } 793*61046927SAndroid Build Coastguard Worker 794*61046927SAndroid Build Coastguard Worker constexpr bit_reference& operator&=(bool val) 795*61046927SAndroid Build Coastguard Worker { 796*61046927SAndroid Build Coastguard Worker storage &= T(val) << bit; 797*61046927SAndroid Build Coastguard Worker return *this; 798*61046927SAndroid Build Coastguard Worker } 799*61046927SAndroid Build Coastguard Worker 800*61046927SAndroid Build Coastguard Worker constexpr operator bool() const { return (storage >> bit) & 0x1; } 801*61046927SAndroid Build Coastguard Worker swapbit_reference802*61046927SAndroid Build Coastguard Worker constexpr void swap(bool& other) 803*61046927SAndroid Build Coastguard Worker { 804*61046927SAndroid Build Coastguard Worker bool tmp = (bool)*this; 805*61046927SAndroid Build Coastguard Worker *this = other; 806*61046927SAndroid Build Coastguard Worker other = tmp; 807*61046927SAndroid Build Coastguard Worker } 808*61046927SAndroid Build Coastguard Worker swapbit_reference809*61046927SAndroid Build Coastguard Worker template <typename other_T> constexpr void swap(bit_reference<other_T> other) 810*61046927SAndroid Build Coastguard Worker { 811*61046927SAndroid Build Coastguard Worker bool tmp = (bool)*this; 812*61046927SAndroid Build Coastguard Worker *this = (bool)other; 813*61046927SAndroid Build Coastguard Worker other = tmp; 814*61046927SAndroid Build Coastguard Worker } 815*61046927SAndroid Build Coastguard Worker 816*61046927SAndroid Build Coastguard Worker T& storage; 817*61046927SAndroid Build Coastguard Worker unsigned bit; 818*61046927SAndroid Build Coastguard Worker }; 819*61046927SAndroid Build Coastguard Worker 820*61046927SAndroid Build Coastguard Worker /* 821*61046927SAndroid Build Coastguard Worker * Base template for (const) bit iterators over an integer. 822*61046927SAndroid Build Coastguard Worker * Only intended to be used with the two specializations 823*61046927SAndroid Build Coastguard Worker * bitfield_array::iterator and bitfield_array::const_iterator. 824*61046927SAndroid Build Coastguard Worker */ 825*61046927SAndroid Build Coastguard Worker template <typename T, typename refT, typename ptrT> struct bitfield_iterator { 826*61046927SAndroid Build Coastguard Worker using difference_type = int; 827*61046927SAndroid Build Coastguard Worker using value_type = bool; 828*61046927SAndroid Build Coastguard Worker using iterator_category = std::random_access_iterator_tag; 829*61046927SAndroid Build Coastguard Worker using reference = refT; 830*61046927SAndroid Build Coastguard Worker using const_reference = bool; 831*61046927SAndroid Build Coastguard Worker using pointer = ptrT; 832*61046927SAndroid Build Coastguard Worker using iterator = bitfield_iterator<T, refT, ptrT>; 833*61046927SAndroid Build Coastguard Worker using ncT = std::remove_const_t<T>; 834*61046927SAndroid Build Coastguard Worker bitfield_iteratorbitfield_iterator835*61046927SAndroid Build Coastguard Worker constexpr bitfield_iterator() : bf(nullptr), index(0) {} bitfield_iteratorbitfield_iterator836*61046927SAndroid Build Coastguard Worker constexpr bitfield_iterator(T* p, unsigned i) : bf(p), index(i) {} 837*61046927SAndroid Build Coastguard Worker 838*61046927SAndroid Build Coastguard Worker /* const iterator must be constructable from iterator */ bitfield_iteratorbitfield_iterator839*61046927SAndroid Build Coastguard Worker constexpr bitfield_iterator( 840*61046927SAndroid Build Coastguard Worker const bitfield_iterator<ncT, bit_reference<ncT>, bit_reference<ncT>*>& x) 841*61046927SAndroid Build Coastguard Worker : bf(x.bf), index(x.index) 842*61046927SAndroid Build Coastguard Worker {} 843*61046927SAndroid Build Coastguard Worker 844*61046927SAndroid Build Coastguard Worker constexpr bool operator==(const bitfield_iterator& other) const 845*61046927SAndroid Build Coastguard Worker { 846*61046927SAndroid Build Coastguard Worker return bf == other.bf && index == other.index; 847*61046927SAndroid Build Coastguard Worker } 848*61046927SAndroid Build Coastguard Worker 849*61046927SAndroid Build Coastguard Worker constexpr bool operator<(const bitfield_iterator& other) const { return index < other.index; } 850*61046927SAndroid Build Coastguard Worker 851*61046927SAndroid Build Coastguard Worker constexpr bool operator!=(const bitfield_iterator& other) const { return !(*this == other); } 852*61046927SAndroid Build Coastguard Worker 853*61046927SAndroid Build Coastguard Worker constexpr bool operator>(const bitfield_iterator& other) const { return other < *this; } 854*61046927SAndroid Build Coastguard Worker 855*61046927SAndroid Build Coastguard Worker constexpr bool operator<=(const bitfield_iterator& other) const { return !(other < *this); } 856*61046927SAndroid Build Coastguard Worker 857*61046927SAndroid Build Coastguard Worker constexpr bool operator>=(const bitfield_iterator& other) const { return !(*this < other); } 858*61046927SAndroid Build Coastguard Worker 859*61046927SAndroid Build Coastguard Worker constexpr reference operator*() const { return bit_reference<T>(*bf, index); } 860*61046927SAndroid Build Coastguard Worker 861*61046927SAndroid Build Coastguard Worker constexpr iterator& operator++() 862*61046927SAndroid Build Coastguard Worker { 863*61046927SAndroid Build Coastguard Worker index++; 864*61046927SAndroid Build Coastguard Worker return *this; 865*61046927SAndroid Build Coastguard Worker } 866*61046927SAndroid Build Coastguard Worker 867*61046927SAndroid Build Coastguard Worker constexpr iterator operator++(int) 868*61046927SAndroid Build Coastguard Worker { 869*61046927SAndroid Build Coastguard Worker iterator tmp = *this; 870*61046927SAndroid Build Coastguard Worker index++; 871*61046927SAndroid Build Coastguard Worker return tmp; 872*61046927SAndroid Build Coastguard Worker } 873*61046927SAndroid Build Coastguard Worker 874*61046927SAndroid Build Coastguard Worker constexpr iterator& operator--() 875*61046927SAndroid Build Coastguard Worker { 876*61046927SAndroid Build Coastguard Worker index--; 877*61046927SAndroid Build Coastguard Worker return *this; 878*61046927SAndroid Build Coastguard Worker } 879*61046927SAndroid Build Coastguard Worker 880*61046927SAndroid Build Coastguard Worker constexpr iterator operator--(int) 881*61046927SAndroid Build Coastguard Worker { 882*61046927SAndroid Build Coastguard Worker iterator tmp = *this; 883*61046927SAndroid Build Coastguard Worker index--; 884*61046927SAndroid Build Coastguard Worker return tmp; 885*61046927SAndroid Build Coastguard Worker } 886*61046927SAndroid Build Coastguard Worker 887*61046927SAndroid Build Coastguard Worker constexpr iterator& operator+=(difference_type value) 888*61046927SAndroid Build Coastguard Worker { 889*61046927SAndroid Build Coastguard Worker index += value; 890*61046927SAndroid Build Coastguard Worker return *this; 891*61046927SAndroid Build Coastguard Worker } 892*61046927SAndroid Build Coastguard Worker 893*61046927SAndroid Build Coastguard Worker constexpr iterator& operator-=(difference_type value) 894*61046927SAndroid Build Coastguard Worker { 895*61046927SAndroid Build Coastguard Worker *this += -value; 896*61046927SAndroid Build Coastguard Worker return *this; 897*61046927SAndroid Build Coastguard Worker } 898*61046927SAndroid Build Coastguard Worker 899*61046927SAndroid Build Coastguard Worker constexpr iterator operator+(difference_type value) const 900*61046927SAndroid Build Coastguard Worker { 901*61046927SAndroid Build Coastguard Worker iterator tmp = *this; 902*61046927SAndroid Build Coastguard Worker return tmp += value; 903*61046927SAndroid Build Coastguard Worker } 904*61046927SAndroid Build Coastguard Worker 905*61046927SAndroid Build Coastguard Worker constexpr iterator operator-(difference_type value) const 906*61046927SAndroid Build Coastguard Worker { 907*61046927SAndroid Build Coastguard Worker iterator tmp = *this; 908*61046927SAndroid Build Coastguard Worker return tmp -= value; 909*61046927SAndroid Build Coastguard Worker } 910*61046927SAndroid Build Coastguard Worker 911*61046927SAndroid Build Coastguard Worker constexpr reference operator[](difference_type value) const { return *(*this + value); } 912*61046927SAndroid Build Coastguard Worker 913*61046927SAndroid Build Coastguard Worker T* bf; 914*61046927SAndroid Build Coastguard Worker unsigned index; 915*61046927SAndroid Build Coastguard Worker }; 916*61046927SAndroid Build Coastguard Worker 917*61046927SAndroid Build Coastguard Worker template <typename T, typename refT, typename ptrT> 918*61046927SAndroid Build Coastguard Worker constexpr inline bitfield_iterator<T, refT, ptrT> 919*61046927SAndroid Build Coastguard Worker operator+(int n, const bitfield_iterator<T, refT, ptrT>& x) 920*61046927SAndroid Build Coastguard Worker { 921*61046927SAndroid Build Coastguard Worker return x + n; 922*61046927SAndroid Build Coastguard Worker } 923*61046927SAndroid Build Coastguard Worker 924*61046927SAndroid Build Coastguard Worker template <typename T, typename refT, typename ptrT> 925*61046927SAndroid Build Coastguard Worker constexpr inline int 926*61046927SAndroid Build Coastguard Worker operator-(const bitfield_iterator<T, refT, ptrT> x, const bitfield_iterator<T, refT, ptrT>& y) 927*61046927SAndroid Build Coastguard Worker { 928*61046927SAndroid Build Coastguard Worker return x.index - y.index; 929*61046927SAndroid Build Coastguard Worker } 930*61046927SAndroid Build Coastguard Worker 931*61046927SAndroid Build Coastguard Worker /* 932*61046927SAndroid Build Coastguard Worker * Extends bitfield_uint with operator[] and iterators that 933*61046927SAndroid Build Coastguard Worker * allow accessing single bits within the uint. Can be used 934*61046927SAndroid Build Coastguard Worker * as a more compact version of bool arrays that also still 935*61046927SAndroid Build Coastguard Worker * allows accessing the whole array as an integer. 936*61046927SAndroid Build Coastguard Worker */ 937*61046927SAndroid Build Coastguard Worker template <typename data_type, unsigned offset, unsigned size, typename access_type> 938*61046927SAndroid Build Coastguard Worker class bitfield_array : public bitfield_uint<data_type, offset, size, access_type> { 939*61046927SAndroid Build Coastguard Worker public: 940*61046927SAndroid Build Coastguard Worker using value_type = bool; 941*61046927SAndroid Build Coastguard Worker using size_type = unsigned; 942*61046927SAndroid Build Coastguard Worker using difference_type = int; 943*61046927SAndroid Build Coastguard Worker using reference = bit_reference<data_type>; 944*61046927SAndroid Build Coastguard Worker using const_reference = bool; 945*61046927SAndroid Build Coastguard Worker using pointer = bit_reference<data_type>*; 946*61046927SAndroid Build Coastguard Worker using const_pointer = const bool*; 947*61046927SAndroid Build Coastguard Worker using iterator = 948*61046927SAndroid Build Coastguard Worker bitfield_iterator<data_type, bit_reference<data_type>, bit_reference<data_type>*>; 949*61046927SAndroid Build Coastguard Worker using const_iterator = bitfield_iterator<const data_type, bool, const bool*>; 950*61046927SAndroid Build Coastguard Worker using reverse_iterator = std::reverse_iterator<iterator>; 951*61046927SAndroid Build Coastguard Worker using const_reverse_iterator = std::reverse_iterator<const_iterator>; 952*61046927SAndroid Build Coastguard Worker 953*61046927SAndroid Build Coastguard Worker bitfield_array() = default; 954*61046927SAndroid Build Coastguard Worker bitfield_array(const access_type & value)955*61046927SAndroid Build Coastguard Worker constexpr bitfield_array(const access_type& value) { *this = value; } 956*61046927SAndroid Build Coastguard Worker 957*61046927SAndroid Build Coastguard Worker constexpr bitfield_array& operator=(const access_type& value) 958*61046927SAndroid Build Coastguard Worker { 959*61046927SAndroid Build Coastguard Worker storage &= ~(mask << offset); 960*61046927SAndroid Build Coastguard Worker storage |= data_type(value & mask) << offset; 961*61046927SAndroid Build Coastguard Worker return *this; 962*61046927SAndroid Build Coastguard Worker } 963*61046927SAndroid Build Coastguard Worker 964*61046927SAndroid Build Coastguard Worker constexpr bitfield_array& operator=(const bitfield_array& value) 965*61046927SAndroid Build Coastguard Worker { 966*61046927SAndroid Build Coastguard Worker return *this = access_type(value); 967*61046927SAndroid Build Coastguard Worker } 968*61046927SAndroid Build Coastguard Worker 969*61046927SAndroid Build Coastguard Worker constexpr reference operator[](unsigned index) 970*61046927SAndroid Build Coastguard Worker { 971*61046927SAndroid Build Coastguard Worker assert(index < size); 972*61046927SAndroid Build Coastguard Worker return reference(storage, offset + index); 973*61046927SAndroid Build Coastguard Worker } 974*61046927SAndroid Build Coastguard Worker 975*61046927SAndroid Build Coastguard Worker constexpr bool operator[](unsigned index) const 976*61046927SAndroid Build Coastguard Worker { 977*61046927SAndroid Build Coastguard Worker assert(index < size); 978*61046927SAndroid Build Coastguard Worker return (storage >> (offset + index)) & 0x1; 979*61046927SAndroid Build Coastguard Worker } 980*61046927SAndroid Build Coastguard Worker begin()981*61046927SAndroid Build Coastguard Worker constexpr iterator begin() noexcept { return iterator(&storage, offset); } 982*61046927SAndroid Build Coastguard Worker end()983*61046927SAndroid Build Coastguard Worker constexpr iterator end() noexcept { return std::next(begin(), size); } 984*61046927SAndroid Build Coastguard Worker begin()985*61046927SAndroid Build Coastguard Worker constexpr const_iterator begin() const noexcept { return const_iterator(&storage, offset); } 986*61046927SAndroid Build Coastguard Worker end()987*61046927SAndroid Build Coastguard Worker constexpr const_iterator end() const noexcept { return std::next(begin(), size); } 988*61046927SAndroid Build Coastguard Worker cbegin()989*61046927SAndroid Build Coastguard Worker constexpr const_iterator cbegin() const noexcept { return begin(); } 990*61046927SAndroid Build Coastguard Worker cend()991*61046927SAndroid Build Coastguard Worker constexpr const_iterator cend() const noexcept { return std::next(begin(), size); } 992*61046927SAndroid Build Coastguard Worker rbegin()993*61046927SAndroid Build Coastguard Worker constexpr reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } 994*61046927SAndroid Build Coastguard Worker rend()995*61046927SAndroid Build Coastguard Worker constexpr reverse_iterator rend() noexcept { return reverse_iterator(begin()); } 996*61046927SAndroid Build Coastguard Worker rbegin()997*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator rbegin() const noexcept 998*61046927SAndroid Build Coastguard Worker { 999*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(end()); 1000*61046927SAndroid Build Coastguard Worker } 1001*61046927SAndroid Build Coastguard Worker rend()1002*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator rend() const noexcept 1003*61046927SAndroid Build Coastguard Worker { 1004*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(begin()); 1005*61046927SAndroid Build Coastguard Worker } 1006*61046927SAndroid Build Coastguard Worker crbegin()1007*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator crbegin() const noexcept 1008*61046927SAndroid Build Coastguard Worker { 1009*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(cend()); 1010*61046927SAndroid Build Coastguard Worker } 1011*61046927SAndroid Build Coastguard Worker crend()1012*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator crend() const noexcept 1013*61046927SAndroid Build Coastguard Worker { 1014*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(cbegin()); 1015*61046927SAndroid Build Coastguard Worker } 1016*61046927SAndroid Build Coastguard Worker 1017*61046927SAndroid Build Coastguard Worker private: 1018*61046927SAndroid Build Coastguard Worker using bitfield_uint<data_type, offset, size, access_type>::storage; 1019*61046927SAndroid Build Coastguard Worker using bitfield_uint<data_type, offset, size, access_type>::mask; 1020*61046927SAndroid Build Coastguard Worker }; 1021*61046927SAndroid Build Coastguard Worker 1022*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset> using bitfield_bool = bitfield_uint<T, offset, 1, bool>; 1023*61046927SAndroid Build Coastguard Worker 1024*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1025*61046927SAndroid Build Coastguard Worker using bitfield_uint8 = bitfield_uint<T, offset, size, uint8_t>; 1026*61046927SAndroid Build Coastguard Worker 1027*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1028*61046927SAndroid Build Coastguard Worker using bitfield_uint16 = bitfield_uint<T, offset, size, uint16_t>; 1029*61046927SAndroid Build Coastguard Worker 1030*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1031*61046927SAndroid Build Coastguard Worker using bitfield_uint32 = bitfield_uint<T, offset, size, uint32_t>; 1032*61046927SAndroid Build Coastguard Worker 1033*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1034*61046927SAndroid Build Coastguard Worker using bitfield_uint64 = bitfield_uint<T, offset, size, uint64_t>; 1035*61046927SAndroid Build Coastguard Worker 1036*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1037*61046927SAndroid Build Coastguard Worker using bitfield_array8 = bitfield_array<T, offset, size, uint8_t>; 1038*61046927SAndroid Build Coastguard Worker 1039*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1040*61046927SAndroid Build Coastguard Worker using bitfield_array16 = bitfield_array<T, offset, size, uint16_t>; 1041*61046927SAndroid Build Coastguard Worker 1042*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1043*61046927SAndroid Build Coastguard Worker using bitfield_array32 = bitfield_array<T, offset, size, uint32_t>; 1044*61046927SAndroid Build Coastguard Worker 1045*61046927SAndroid Build Coastguard Worker template <typename T, unsigned offset, unsigned size> 1046*61046927SAndroid Build Coastguard Worker using bitfield_array64 = bitfield_array<T, offset, size, uint64_t>; 1047*61046927SAndroid Build Coastguard Worker 1048*61046927SAndroid Build Coastguard Worker using bitarray8 = bitfield_array<uint8_t, 0, 8, uint8_t>; 1049*61046927SAndroid Build Coastguard Worker 1050*61046927SAndroid Build Coastguard Worker /* 1051*61046927SAndroid Build Coastguard Worker * Resizable array optimized for small lengths. If it's smaller than Size, the elements will be 1052*61046927SAndroid Build Coastguard Worker * inlined into the object. 1053*61046927SAndroid Build Coastguard Worker */ 1054*61046927SAndroid Build Coastguard Worker template <typename T, uint32_t Size> class small_vec { 1055*61046927SAndroid Build Coastguard Worker public: 1056*61046927SAndroid Build Coastguard Worker static_assert(std::is_trivial<T>::value); 1057*61046927SAndroid Build Coastguard Worker 1058*61046927SAndroid Build Coastguard Worker using value_type = T; 1059*61046927SAndroid Build Coastguard Worker using pointer = value_type*; 1060*61046927SAndroid Build Coastguard Worker using const_pointer = const value_type*; 1061*61046927SAndroid Build Coastguard Worker using reference = value_type&; 1062*61046927SAndroid Build Coastguard Worker using const_reference = const value_type&; 1063*61046927SAndroid Build Coastguard Worker using iterator = pointer; 1064*61046927SAndroid Build Coastguard Worker using const_iterator = const_pointer; 1065*61046927SAndroid Build Coastguard Worker using reverse_iterator = std::reverse_iterator<iterator>; 1066*61046927SAndroid Build Coastguard Worker using const_reverse_iterator = std::reverse_iterator<const_iterator>; 1067*61046927SAndroid Build Coastguard Worker using size_type = uint16_t; 1068*61046927SAndroid Build Coastguard Worker using difference_type = std::ptrdiff_t; 1069*61046927SAndroid Build Coastguard Worker 1070*61046927SAndroid Build Coastguard Worker constexpr small_vec() = default; 1071*61046927SAndroid Build Coastguard Worker constexpr small_vec(const small_vec&) = delete; small_vec(small_vec && other)1072*61046927SAndroid Build Coastguard Worker constexpr small_vec(small_vec&& other) { *this = std::move(other); } 1073*61046927SAndroid Build Coastguard Worker ~small_vec()1074*61046927SAndroid Build Coastguard Worker ~small_vec() 1075*61046927SAndroid Build Coastguard Worker { 1076*61046927SAndroid Build Coastguard Worker if (capacity > Size) 1077*61046927SAndroid Build Coastguard Worker free(data); 1078*61046927SAndroid Build Coastguard Worker } 1079*61046927SAndroid Build Coastguard Worker 1080*61046927SAndroid Build Coastguard Worker constexpr small_vec& operator=(const small_vec&) = delete; 1081*61046927SAndroid Build Coastguard Worker constexpr small_vec& operator=(small_vec&& other) 1082*61046927SAndroid Build Coastguard Worker { 1083*61046927SAndroid Build Coastguard Worker clear(); 1084*61046927SAndroid Build Coastguard Worker void* ptr = this; 1085*61046927SAndroid Build Coastguard Worker memcpy(ptr, &other, sizeof(*this)); 1086*61046927SAndroid Build Coastguard Worker other.length = 0; 1087*61046927SAndroid Build Coastguard Worker other.capacity = Size; 1088*61046927SAndroid Build Coastguard Worker return *this; 1089*61046927SAndroid Build Coastguard Worker } 1090*61046927SAndroid Build Coastguard Worker begin()1091*61046927SAndroid Build Coastguard Worker constexpr iterator begin() noexcept { return capacity > Size ? data : inline_data; } 1092*61046927SAndroid Build Coastguard Worker begin()1093*61046927SAndroid Build Coastguard Worker constexpr const_iterator begin() const noexcept { return capacity > Size ? data : inline_data; } 1094*61046927SAndroid Build Coastguard Worker end()1095*61046927SAndroid Build Coastguard Worker constexpr iterator end() noexcept { return std::next(begin(), length); } 1096*61046927SAndroid Build Coastguard Worker end()1097*61046927SAndroid Build Coastguard Worker constexpr const_iterator end() const noexcept { return std::next(begin(), length); } 1098*61046927SAndroid Build Coastguard Worker cbegin()1099*61046927SAndroid Build Coastguard Worker constexpr const_iterator cbegin() const noexcept { return begin(); } 1100*61046927SAndroid Build Coastguard Worker cend()1101*61046927SAndroid Build Coastguard Worker constexpr const_iterator cend() const noexcept { return std::next(begin(), length); } 1102*61046927SAndroid Build Coastguard Worker rbegin()1103*61046927SAndroid Build Coastguard Worker constexpr reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } 1104*61046927SAndroid Build Coastguard Worker rbegin()1105*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator rbegin() const noexcept 1106*61046927SAndroid Build Coastguard Worker { 1107*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(end()); 1108*61046927SAndroid Build Coastguard Worker } 1109*61046927SAndroid Build Coastguard Worker rend()1110*61046927SAndroid Build Coastguard Worker constexpr reverse_iterator rend() noexcept { return reverse_iterator(begin()); } 1111*61046927SAndroid Build Coastguard Worker rend()1112*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator rend() const noexcept 1113*61046927SAndroid Build Coastguard Worker { 1114*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(begin()); 1115*61046927SAndroid Build Coastguard Worker } 1116*61046927SAndroid Build Coastguard Worker crbegin()1117*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator crbegin() const noexcept 1118*61046927SAndroid Build Coastguard Worker { 1119*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(cend()); 1120*61046927SAndroid Build Coastguard Worker } 1121*61046927SAndroid Build Coastguard Worker crend()1122*61046927SAndroid Build Coastguard Worker constexpr const_reverse_iterator crend() const noexcept 1123*61046927SAndroid Build Coastguard Worker { 1124*61046927SAndroid Build Coastguard Worker return const_reverse_iterator(cbegin()); 1125*61046927SAndroid Build Coastguard Worker } 1126*61046927SAndroid Build Coastguard Worker 1127*61046927SAndroid Build Coastguard Worker constexpr reference operator[](const size_type index) noexcept 1128*61046927SAndroid Build Coastguard Worker { 1129*61046927SAndroid Build Coastguard Worker assert(length > index); 1130*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), index)); 1131*61046927SAndroid Build Coastguard Worker } 1132*61046927SAndroid Build Coastguard Worker 1133*61046927SAndroid Build Coastguard Worker constexpr const_reference operator[](const size_type index) const noexcept 1134*61046927SAndroid Build Coastguard Worker { 1135*61046927SAndroid Build Coastguard Worker assert(length > index); 1136*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), index)); 1137*61046927SAndroid Build Coastguard Worker } 1138*61046927SAndroid Build Coastguard Worker back()1139*61046927SAndroid Build Coastguard Worker constexpr reference back() noexcept 1140*61046927SAndroid Build Coastguard Worker { 1141*61046927SAndroid Build Coastguard Worker assert(length > 0); 1142*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), length - 1)); 1143*61046927SAndroid Build Coastguard Worker } 1144*61046927SAndroid Build Coastguard Worker back()1145*61046927SAndroid Build Coastguard Worker constexpr const_reference back() const noexcept 1146*61046927SAndroid Build Coastguard Worker { 1147*61046927SAndroid Build Coastguard Worker assert(length > 0); 1148*61046927SAndroid Build Coastguard Worker return *(std::next(begin(), length - 1)); 1149*61046927SAndroid Build Coastguard Worker } 1150*61046927SAndroid Build Coastguard Worker front()1151*61046927SAndroid Build Coastguard Worker constexpr reference front() noexcept 1152*61046927SAndroid Build Coastguard Worker { 1153*61046927SAndroid Build Coastguard Worker assert(length > 0); 1154*61046927SAndroid Build Coastguard Worker return *begin(); 1155*61046927SAndroid Build Coastguard Worker } 1156*61046927SAndroid Build Coastguard Worker front()1157*61046927SAndroid Build Coastguard Worker constexpr const_reference front() const noexcept 1158*61046927SAndroid Build Coastguard Worker { 1159*61046927SAndroid Build Coastguard Worker assert(length > 0); 1160*61046927SAndroid Build Coastguard Worker return *cbegin(); 1161*61046927SAndroid Build Coastguard Worker } 1162*61046927SAndroid Build Coastguard Worker empty()1163*61046927SAndroid Build Coastguard Worker constexpr bool empty() const noexcept { return length == 0; } 1164*61046927SAndroid Build Coastguard Worker size()1165*61046927SAndroid Build Coastguard Worker constexpr size_type size() const noexcept { return length; } 1166*61046927SAndroid Build Coastguard Worker pop_back()1167*61046927SAndroid Build Coastguard Worker constexpr void pop_back() noexcept 1168*61046927SAndroid Build Coastguard Worker { 1169*61046927SAndroid Build Coastguard Worker assert(length > 0); 1170*61046927SAndroid Build Coastguard Worker --length; 1171*61046927SAndroid Build Coastguard Worker } 1172*61046927SAndroid Build Coastguard Worker reserve(size_type n)1173*61046927SAndroid Build Coastguard Worker constexpr void reserve(size_type n) 1174*61046927SAndroid Build Coastguard Worker { 1175*61046927SAndroid Build Coastguard Worker if (n > capacity) { 1176*61046927SAndroid Build Coastguard Worker if (capacity > Size) { 1177*61046927SAndroid Build Coastguard Worker data = (T*)realloc(data, sizeof(T) * n); 1178*61046927SAndroid Build Coastguard Worker } else { 1179*61046927SAndroid Build Coastguard Worker T* ptr = (T*)malloc(sizeof(T) * n); 1180*61046927SAndroid Build Coastguard Worker memcpy(ptr, inline_data, sizeof(T) * length); 1181*61046927SAndroid Build Coastguard Worker data = ptr; 1182*61046927SAndroid Build Coastguard Worker } 1183*61046927SAndroid Build Coastguard Worker capacity = n; 1184*61046927SAndroid Build Coastguard Worker } 1185*61046927SAndroid Build Coastguard Worker } 1186*61046927SAndroid Build Coastguard Worker push_back(const value_type & val)1187*61046927SAndroid Build Coastguard Worker constexpr void push_back(const value_type& val) noexcept 1188*61046927SAndroid Build Coastguard Worker { 1189*61046927SAndroid Build Coastguard Worker if (length == capacity) 1190*61046927SAndroid Build Coastguard Worker reserve(2 * capacity); 1191*61046927SAndroid Build Coastguard Worker 1192*61046927SAndroid Build Coastguard Worker *std::next(begin(), length++) = val; 1193*61046927SAndroid Build Coastguard Worker } 1194*61046927SAndroid Build Coastguard Worker emplace_back(Args...args)1195*61046927SAndroid Build Coastguard Worker template <typename... Args> constexpr void emplace_back(Args... args) noexcept 1196*61046927SAndroid Build Coastguard Worker { 1197*61046927SAndroid Build Coastguard Worker if (length == capacity) 1198*61046927SAndroid Build Coastguard Worker reserve(2 * capacity); 1199*61046927SAndroid Build Coastguard Worker 1200*61046927SAndroid Build Coastguard Worker *std::next(begin(), length++) = T(args...); 1201*61046927SAndroid Build Coastguard Worker } 1202*61046927SAndroid Build Coastguard Worker clear()1203*61046927SAndroid Build Coastguard Worker constexpr void clear() noexcept 1204*61046927SAndroid Build Coastguard Worker { 1205*61046927SAndroid Build Coastguard Worker if (capacity > Size) 1206*61046927SAndroid Build Coastguard Worker free(data); 1207*61046927SAndroid Build Coastguard Worker length = 0; 1208*61046927SAndroid Build Coastguard Worker capacity = Size; 1209*61046927SAndroid Build Coastguard Worker } 1210*61046927SAndroid Build Coastguard Worker 1211*61046927SAndroid Build Coastguard Worker constexpr bool operator==(const small_vec& other) const 1212*61046927SAndroid Build Coastguard Worker { 1213*61046927SAndroid Build Coastguard Worker if (size() != other.size()) 1214*61046927SAndroid Build Coastguard Worker return false; 1215*61046927SAndroid Build Coastguard Worker for (unsigned i = 0; i < size(); i++) { 1216*61046927SAndroid Build Coastguard Worker if (*(std::next(begin(), i)) != other[i]) 1217*61046927SAndroid Build Coastguard Worker return false; 1218*61046927SAndroid Build Coastguard Worker } 1219*61046927SAndroid Build Coastguard Worker return true; 1220*61046927SAndroid Build Coastguard Worker } 1221*61046927SAndroid Build Coastguard Worker 1222*61046927SAndroid Build Coastguard Worker private: 1223*61046927SAndroid Build Coastguard Worker uint32_t length = 0; 1224*61046927SAndroid Build Coastguard Worker uint32_t capacity = Size; 1225*61046927SAndroid Build Coastguard Worker union { 1226*61046927SAndroid Build Coastguard Worker T* data = NULL; 1227*61046927SAndroid Build Coastguard Worker T inline_data[Size]; 1228*61046927SAndroid Build Coastguard Worker }; 1229*61046927SAndroid Build Coastguard Worker }; 1230*61046927SAndroid Build Coastguard Worker 1231*61046927SAndroid Build Coastguard Worker } // namespace aco 1232*61046927SAndroid Build Coastguard Worker 1233*61046927SAndroid Build Coastguard Worker #endif // ACO_UTIL_H 1234