xref: /aosp_15_r20/external/mesa3d/src/amd/compiler/aco_util.h (revision 6104692788411f58d303aa86923a9ff6ecaded22)
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