6 #ifndef XENIUM_GROWING_CIRCULAR_ARRAY_HPP
7 #define XENIUM_GROWING_CIRCULAR_ARRAY_HPP
9 #include <xenium/utils.hpp>
15 namespace xenium {
namespace detail {
16 template <class T, std::size_t MinCapacity = 64, std::size_t MaxCapacity = static_cast<std::size_t>(1) << 31>
17 struct growing_circular_array {
18 static constexpr std::size_t min_capacity = MinCapacity;
19 static constexpr std::size_t max_capacity = MaxCapacity;
20 static constexpr std::size_t num_buckets = utils::find_last_bit_set(max_capacity);
22 static_assert(utils::is_power_of_two(min_capacity),
"MinCapacity must be a power of two");
23 static_assert(utils::is_power_of_two(max_capacity),
"MaxCapacity must be a power of two");
24 static_assert(min_capacity < max_capacity,
"MaxCapacity must be greater than MinCapacity");
26 growing_circular_array();
27 ~growing_circular_array();
29 std::size_t capacity()
const {
return _capacity.load(std::memory_order_relaxed); }
31 T* get(std::size_t idx, std::memory_order order) {
33 auto capacitiy = _capacity.load(std::memory_order_acquire);
34 return get_entry(idx, capacitiy).load(order);
37 void put(std::size_t idx, T* value, std::memory_order order) {
38 auto capacitiy = _capacity.load(std::memory_order_relaxed);
39 get_entry(idx, capacitiy).store(value, order);
42 bool can_grow() {
return capacity() < max_capacity; }
44 void grow(std::size_t bottom, std::size_t top);
46 using entry = std::atomic<T*>;
48 entry& get_entry(std::size_t idx, std::size_t capacity) {
49 idx = idx & (capacity - 1);
50 std::size_t bucket = utils::find_last_bit_set(idx);
51 assert(bucket < num_buckets);
53 idx ^= (1 << bucket) >> 1;
54 return _data[bucket][idx];
57 static constexpr std::size_t initial_buckets = utils::find_last_bit_set(MinCapacity);
60 std::atomic<std::size_t> _capacity;
61 entry* _data[num_buckets];
64 template <
class T, std::
size_t MinCapacity, std::
size_t Buckets>
65 growing_circular_array<T, MinCapacity, Buckets>::growing_circular_array() :
66 _buckets(initial_buckets),
67 _capacity(MinCapacity),
70 entry* ptr =
new entry[MinCapacity];
72 for(std::size_t i = 1; i < _buckets; ++i) {
74 ptr +=
static_cast<std::size_t
>(1) << (i - 1);
78 template <
class T, std::
size_t MinCapacity, std::
size_t Buckets>
79 growing_circular_array<T, MinCapacity, Buckets>::~growing_circular_array() {
81 for(std::size_t i = initial_buckets; i < num_buckets; ++i)
85 template <
class T, std::
size_t MinCapacity, std::
size_t Buckets>
86 void growing_circular_array<T, MinCapacity, Buckets>::grow(std::size_t bottom, std::size_t top) {
89 auto capacity = this->capacity();
90 auto mod_mask = capacity - 1;
91 assert((capacity & mod_mask) == 0);
93 _data[_buckets] =
new entry[capacity];
95 auto new_capacity = capacity * 2;
96 auto new_mod_mask = new_capacity - 1;
99 auto start_mod = top & mod_mask;
100 if(start_mod == (top & new_mod_mask)) {
102 start += capacity - start_mod;
105 for(std::size_t i = start; i < bottom; i++) {
106 auto oldI = i & mod_mask;
107 auto newI = i % new_mod_mask;
109 auto oldBit = utils::find_last_bit_set(oldI);
110 auto newBit = utils::find_last_bit_set(newI);
111 auto v = _data[oldBit][oldI ^ ((1 << (oldBit)) >> 1)].load(std::memory_order_relaxed);
112 _data[newBit][newI ^ ((1 << (newBit)) >> 1)].store(v, std::memory_order_relaxed);
120 _capacity.store(new_capacity, std::memory_order_release);