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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#pragma once
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
class RingBufferSentinel {};
template <typename TContainer>
class RingBufferIterator {
public:
using difference_type = TContainer::difference_type;
using value_type = TContainer::value_type; // C++20 relaxed usage requirements of `typename`, now locations where a type is required (like here in a using statement) it's no longer mandatory
using pointer = value_type*;
using reference = value_type&;
using iterator_category = std::random_access_iterator_tag;
public:
TContainer* container;
TContainer::size_type curr; // C++20 relaxed usage requirements of `typename`, same here
bool needsWrapAround;
bool hasWrappedAround = false;
public:
reference operator*() const {
return container->mRing[curr];
}
RingBufferIterator& operator++() {
assert(*this != RingBufferSentinel{});
++curr;
if (needsWrapAround && curr == container->mCapacity) {
hasWrappedAround = true;
curr = 0;
}
return *this;
}
bool operator==(const RingBufferIterator& that) const {
assert(this->container == that.container);
return this->curr == that.curr;
}
bool operator==(const RingBufferSentinel&) const {
return curr == container->mTailIdx && (!needsWrapAround || hasWrappedAround);
}
};
template <typename T>
class RingBuffer {
public:
using value_type = T;
using reference = T&;
using const_reference = const T&;
friend class RingBufferIterator<RingBuffer>;
using iterator = RingBufferIterator<RingBuffer>;
friend class RingBufferIterator<const RingBuffer>;
using const_iterator = RingBufferIterator<const RingBuffer>;
using sentinel = RingBufferSentinel; // Not a part of C++'s Container named requirements, added here for convenience
using difference_type = ptrdiff_t;
using size_type = size_t;
private:
T* mRing = nullptr;
size_type mHeadIdx = 0;
size_type mTailIdx = 0;
size_type mCapacity = 0;
size_type mSize = 0;
public:
RingBuffer() noexcept = default;
~RingBuffer() noexcept {
delete mRing;
}
RingBuffer(const RingBuffer&) noexcept = delete;
RingBuffer& operator=(const RingBuffer&) noexcept = delete;
RingBuffer(RingBuffer&& that) noexcept
: mRing{ that.mRing }
, mHeadIdx{ that.mHeadIdx }
, mTailIdx{ that.mTailIdx }
, mCapacity{ that.mCapacity }
, mSize{ that.mSize } {
that.mRing = nullptr;
}
RingBuffer& operator=(RingBuffer&& that) noexcept {
if (this != &that) {
auto oldThisRing = this->mRing;
this->mRing = that.mRing;
that.mRing = nullptr;
delete oldThisRing;
this->mHeadIdx = that.mHeadIdx;
this->mTailIdx = that.mTailIdx;
this->mCapacity = that.mCapacity;
this->mSize = that.mSize;
}
return *this;
}
[[nodiscard]] iterator begin() {
return {
.container = this,
.curr = mHeadIdx,
.needsWrapAround = mHeadIdx >= mTailIdx,
};
}
[[nodiscard]] const_iterator begin() const { return cbegin(); }
// Same type for both const this and non-const `this`
[[nodiscard]] sentinel end() const { return sentinel{}; }
[[nodiscard]] const_iterator cbegin() const {
return {
.container = this,
.curr = mHeadIdx,
.needsWrapAround = mHeadIdx >= mTailIdx,
};
}
[[nodiscard]] sentinel cend() const { return sentinel{}; }
[[nodiscard]] T& operator[](size_type i) { return const_cast<T&>(const_cast<const RingBuffer&>(*this)[i]); }
[[nodiscard]] const T& operator[](size_type i) const {
size_type idx = mHeadIdx + i;
if (idx >= mCapacity) {
idx -= mCapacity;
}
return mRing[idx];
}
void push_back(T t) {
if (mTailIdx == mCapacity) {
// Ring buffer is filled to the right, warp around to the beginning
// mHeadIdx > 0 must be true, since we checked that as condition (1) above
mRing[0] = std::move(t);
mTailIdx = 1;
} else {
mRing[mTailIdx] = std::move(t);
mTailIdx += 1;
}
// Push mHeadIdx backwards if overwrote element in a filled buffer
bool bufferFilled = mSize == mCapacity;
if (bufferFilled && mTailIdx > mHeadIdx) {
mHeadIdx += 1;
if (mHeadIdx == mCapacity) {
mHeadIdx = 0;
}
}
if (!bufferFilled) {
++mSize;
}
}
[[nodiscard]] size_type capacity() const {
return mCapacity;
}
[[nodiscard]] size_type size() const {
return mSize;
}
[[nodiscard]] T* GetBuffer() const { return mRing; }
[[nodiscard]] size_type GetHeadIdx() const { return mHeadIdx; }
[[nodiscard]] size_type GetTailIdx() const { return mTailIdx; }
void resize(size_type newCapacity) {
auto size = this->size();
auto oldRing = mRing;
auto newRing = mRing = new T[newCapacity];
std::rotate_copy(oldRing, oldRing + mHeadIdx, oldRing + mCapacity, newRing);
delete oldRing;
mCapacity = newCapacity;
mHeadIdx = 0;
mTailIdx = size;
}
};
|
