xenium
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 
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);
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