xenium
Loading...
Searching...
No Matches
growing_circular_array.hpp
1//
2// Copyright (c) 2018-2020 Manuel Pöter.
3// Licensed under the MIT License. See LICENSE file in the project root for full license information.
4//
5
6#ifndef XENIUM_GROWING_CIRCULAR_ARRAY_HPP
7#define XENIUM_GROWING_CIRCULAR_ARRAY_HPP
8
9#include <xenium/utils.hpp>
10
11#include <atomic>
12#include <cassert>
13#include <cstdint>
14
15namespace 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);
21
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");
25
26 growing_circular_array();
27 ~growing_circular_array();
28
29 std::size_t capacity() const { return _capacity.load(std::memory_order_relaxed); }
30
31 T* get(std::size_t idx, std::memory_order order) {
32 // (1) - this acquire-load synchronizes-with the release-store (2)
33 auto capacitiy = _capacity.load(std::memory_order_acquire);
34 return get_entry(idx, capacitiy).load(order);
35 }
36
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);
40 }
41
42 bool can_grow() { return capacity() < max_capacity; }
43
44 void grow(std::size_t bottom, std::size_t top);
45 private:
46 using entry = std::atomic<T*>;
47
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);
52 // bucket can be zero, so we have to use two shifts here.
53 idx ^= (1 << bucket) >> 1;
54 return _data[bucket][idx];
55 }
56
57 static constexpr std::size_t initial_buckets = utils::find_last_bit_set(MinCapacity);
58
59 std::size_t _buckets;
60 std::atomic<std::size_t> _capacity;
61 entry* _data[num_buckets];
62 };
63
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),
68 _data()
69 {
70 entry* ptr = new entry[MinCapacity];
71 _data[0] = ptr++;
72 for(std::size_t i = 1; i < _buckets; ++i) {
73 _data[i] = ptr;
74 ptr += static_cast<std::size_t>(1) << (i - 1);
75 }
76 }
77
78 template <class T, std::size_t MinCapacity, std::size_t Buckets>
79 growing_circular_array<T, MinCapacity, Buckets>::~growing_circular_array() {
80 delete[](_data[0]);
81 for(std::size_t i = initial_buckets; i < num_buckets; ++i)
82 delete[](_data[i]);
83 }
84
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) {
87 assert(can_grow());
88
89 auto capacity = this->capacity();
90 auto mod_mask = capacity - 1;
91 assert((capacity & mod_mask) == 0);
92
93 _data[_buckets] = new entry[capacity];
94 _buckets++;
95 auto new_capacity = capacity * 2;
96 auto new_mod_mask = new_capacity - 1;
97
98 auto start = top;
99 auto start_mod = top & mod_mask;
100 if(start_mod == (top & new_mod_mask)) {
101 // Make sure we don't iterate through useless indices
102 start += capacity - start_mod;
103 }
104
105 for(std::size_t i = start; i < bottom; i++) {
106 auto oldI = i & mod_mask;
107 auto newI = i % new_mod_mask;
108 if(oldI != newI) {
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);
113 } else {
114 // Make sure we don't iterate through useless indices
115 break;
116 }
117 }
118
119 // (2) - this release-store synchronizes-with the acquire-load (1)
120 _capacity.store(new_capacity, std::memory_order_release);
121 }
122}}
123
124#endif