-
Notifications
You must be signed in to change notification settings - Fork 0
/
circle_queue.h
128 lines (105 loc) · 2.69 KB
/
circle_queue.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#pragma once
#include <limits>
#include <memory>
#include <new>
#include <type_traits>
template <typename T>
class CircleQueue {
public:
class iterator;
explicit CircleQueue(const size_t capacity): size_(capacity), data(alloc()) {}
~CircleQueue() /* noexcept */ {
clear();
}
void clear() noexcept {
if constexpr (!std::is_trivially_destructible_v<T>) {
std::ranges::destroy_n(std::launder(data.get()), size());
}
full = false;
start = 0;
}
T& operator[](const size_t i) {
return *std::launder(data.get() + index(i));
}
T const& operator[](const size_t i) const {
return *std::launder(data.get() + index(i));
}
size_t size() const noexcept {
return full ? size_ : start;
}
template <typename... Args>
void emplace(Args&&... args) {
if (!full) {
std::construct_at(data.get() + start, std::forward<Args>(args)...);
}
else {
// construct-and-move so that the container remains in a consistent state
// on exception.
data[start] = T(std::forward<Args>(args)...);
}
if (++start == size_) {
full = true;
start = 0;
}
}
iterator begin() noexcept {
static_assert(std::input_iterator<iterator>);
return iterator(this, 0);
}
iterator end() noexcept {
return iterator(this, size());
}
private:
using Deleter = decltype([](T* ptr) {
::operator delete(ptr, std::align_val_t(alignof(T)));
});
inline size_t index(const size_t i) const noexcept {
return full ? (start + i) % size_ : i;
}
std::unique_ptr<T[], Deleter> alloc() {
if (!size_) {
return nullptr;
}
if (size_ > std::numeric_limits<ssize_t>::max()) [[unlikely]] {
throw std::runtime_error{"CircleQueue capacity too large"};
}
return std::unique_ptr<T[], Deleter>(
static_cast<T*>(
::operator new(size_ * sizeof(T), std::align_val_t(alignof(T)))),
Deleter());
}
const size_t size_;
bool full : 1 = false;
size_t start : std::numeric_limits<ssize_t>::digits = 0;
const std::unique_ptr<T[], Deleter> data;
};
template <typename T>
class CircleQueue<T>::iterator {
public:
using value_type = T;
using difference_type = ssize_t;
T& operator*() const {
return (*obj)[i];
}
T* operator->() const {
return std::addressof((*obj)[i]);
}
iterator& operator++() noexcept {
++i;
return *this;
}
iterator operator++(int) noexcept {
iterator r(*this);
++*this;
return r;
}
bool operator==(const iterator r) const noexcept {
assert(obj == r.obj);
return i == r.i;
}
private:
iterator(CircleQueue* obj, size_t i) noexcept: obj(obj), i(i) {}
friend class CircleQueue;
CircleQueue* obj;
size_t i;
};