1 /*
2  * Copyright (C) 2023 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <algorithm>
20 #include <compare>
21 #include <cstddef>
22 #include <iterator>
23 #include <memory>
24 #include <type_traits>
25 #include <utility>
26 
27 #include <android-base/stringprintf.h>
28 
29 namespace android {
30 
31 // A fixed-size ring buffer of elements.
32 //
33 // Elements can only be removed from the front/back or added to the front/back, but with O(1)
34 // performance. Elements from the opposing side are evicted when new elements are pushed onto a full
35 // buffer.
36 template <typename T>
37 class RingBuffer {
38 public:
39     using value_type = T;
40     using size_type = size_t;
41     using difference_type = ptrdiff_t;
42     using reference = value_type&;
43     using const_reference = const value_type&;
44     using pointer = value_type*;
45     using const_pointer = const value_type*;
46 
47     template <typename U>
48     class Iterator;
49     using iterator = Iterator<T>;
50     using const_iterator = Iterator<const T>;
51 
52     // Creates an empty ring buffer that can hold some capacity.
RingBuffer(size_type capacity)53     explicit RingBuffer(size_type capacity)
54           : mBuffer(std::allocator<value_type>().allocate(capacity)), mCapacity(capacity) {}
55 
56     // Creates a full ring buffer holding a fixed number of elements initialised to some value.
RingBuffer(size_type count,const_reference value)57     explicit RingBuffer(size_type count, const_reference value) : RingBuffer(count) {
58         while (count) {
59             pushBack(value);
60             --count;
61         }
62     }
63 
RingBuffer(const RingBuffer & other)64     RingBuffer(const RingBuffer& other) : RingBuffer(other.capacity()) {
65         for (const auto& element : other) {
66             pushBack(element);
67         }
68     }
69 
RingBuffer(RingBuffer && other)70     RingBuffer(RingBuffer&& other) noexcept { *this = std::move(other); }
71 
~RingBuffer()72     ~RingBuffer() {
73         if (mBuffer) {
74             clear();
75             std::allocator<value_type>().deallocate(mBuffer, mCapacity);
76         }
77     }
78 
79     RingBuffer& operator=(const RingBuffer& other) { return *this = RingBuffer(other); }
80 
81     RingBuffer& operator=(RingBuffer&& other) noexcept {
82         if (this == &other) {
83             return *this;
84         }
85         if (mBuffer) {
86             clear();
87             std::allocator<value_type>().deallocate(mBuffer, mCapacity);
88         }
89         mBuffer = std::move(other.mBuffer);
90         mCapacity = other.mCapacity;
91         mBegin = other.mBegin;
92         mSize = other.mSize;
93         other.mBuffer = nullptr;
94         other.mCapacity = 0;
95         other.mBegin = 0;
96         other.mSize = 0;
97         return *this;
98     }
99 
begin()100     iterator begin() { return {*this, 0}; }
begin()101     const_iterator begin() const { return {*this, 0}; }
end()102     iterator end() { return {*this, mSize}; }
end()103     const_iterator end() const { return {*this, mSize}; }
104 
front()105     reference front() { return mBuffer[mBegin]; }
front()106     const_reference front() const { return mBuffer[mBegin]; }
back()107     reference back() { return mBuffer[bufferIndex(mSize - 1)]; }
back()108     const_reference back() const { return mBuffer[bufferIndex(mSize - 1)]; }
109 
110     reference operator[](size_type i) { return mBuffer[bufferIndex(i)]; }
111     const_reference operator[](size_type i) const { return mBuffer[bufferIndex(i)]; }
112 
113     // Removes all elements from the buffer.
clear()114     void clear() {
115         std::destroy(begin(), end());
116         mSize = 0;
117     }
118 
119     // Removes and returns the first element from the buffer.
popFront()120     value_type popFront() {
121         value_type element = mBuffer[mBegin];
122         std::destroy_at(std::addressof(mBuffer[mBegin]));
123         mBegin = next(mBegin);
124         --mSize;
125         return element;
126     }
127 
128     // Removes and returns the last element from the buffer.
popBack()129     value_type popBack() {
130         size_type backIndex = bufferIndex(mSize - 1);
131         value_type element = mBuffer[backIndex];
132         std::destroy_at(std::addressof(mBuffer[backIndex]));
133         --mSize;
134         return element;
135     }
136 
137     // Adds an element to the front of the buffer.
pushFront(const value_type & element)138     void pushFront(const value_type& element) { pushFront(value_type(element)); }
pushFront(value_type && element)139     void pushFront(value_type&& element) {
140         mBegin = previous(mBegin);
141         if (size() == capacity()) {
142             mBuffer[mBegin] = std::forward<value_type>(element);
143         } else {
144             // The space at mBuffer[mBegin] is uninitialised.
145             // TODO: Use std::construct_at when it becomes available.
146             new (std::addressof(mBuffer[mBegin])) value_type(std::forward<value_type>(element));
147             ++mSize;
148         }
149     }
150 
151     // Adds an element to the back of the buffer.
pushBack(const value_type & element)152     void pushBack(const value_type& element) { pushBack(value_type(element)); }
pushBack(value_type && element)153     void pushBack(value_type&& element) {
154         if (size() == capacity()) {
155             mBuffer[mBegin] = std::forward<value_type>(element);
156             mBegin = next(mBegin);
157         } else {
158             // The space at mBuffer[...] is uninitialised.
159             // TODO: Use std::construct_at when it becomes available.
160             new (std::addressof(mBuffer[bufferIndex(mSize)]))
161                     value_type(std::forward<value_type>(element));
162             ++mSize;
163         }
164     }
165 
empty()166     bool empty() const { return mSize == 0; }
capacity()167     size_type capacity() const { return mCapacity; }
size()168     size_type size() const { return mSize; }
169 
swap(RingBuffer & other)170     void swap(RingBuffer& other) noexcept {
171         using std::swap;
172         swap(mBuffer, other.mBuffer);
173         swap(mCapacity, other.mCapacity);
174         swap(mBegin, other.mBegin);
175         swap(mSize, other.mSize);
176     }
177 
swap(RingBuffer & lhs,RingBuffer & rhs)178     friend void swap(RingBuffer& lhs, RingBuffer& rhs) noexcept { lhs.swap(rhs); }
179 
180     template <typename U>
181     class Iterator {
182     private:
183         using ContainerType = std::conditional_t<std::is_const_v<U>, const RingBuffer, RingBuffer>;
184 
185     public:
186         using iterator_category = std::random_access_iterator_tag;
187         using size_type = ContainerType::size_type;
188         using difference_type = ContainerType::difference_type;
189         using value_type = std::remove_cv_t<U>;
190         using pointer = U*;
191         using reference = U&;
192 
Iterator(ContainerType & container,size_type index)193         Iterator(ContainerType& container, size_type index)
194               : mContainer(container), mIndex(index) {}
195 
196         Iterator(const Iterator&) = default;
197         Iterator& operator=(const Iterator&) = default;
198 
199         Iterator& operator++() {
200             ++mIndex;
201             return *this;
202         }
203 
204         Iterator operator++(int) {
205             Iterator iterator(*this);
206             ++(*this);
207             return iterator;
208         }
209 
210         Iterator& operator--() {
211             --mIndex;
212             return *this;
213         }
214 
215         Iterator operator--(int) {
216             Iterator iterator(*this);
217             --(*this);
218             return iterator;
219         }
220 
221         Iterator& operator+=(difference_type n) {
222             mIndex += n;
223             return *this;
224         }
225 
226         Iterator operator+(difference_type n) {
227             Iterator iterator(*this);
228             return iterator += n;
229         }
230 
231         Iterator& operator-=(difference_type n) { return *this += -n; }
232 
233         Iterator operator-(difference_type n) {
234             Iterator iterator(*this);
235             return iterator -= n;
236         }
237 
238         difference_type operator-(const Iterator& other) { return mIndex - other.mIndex; }
239 
240         bool operator==(const Iterator& rhs) const { return mIndex == rhs.mIndex; }
241 
242         bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }
243 
244         friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
245             return lhs.mIndex <=> rhs.mIndex;
246         }
247 
248         reference operator[](difference_type n) { return *(*this + n); }
249 
250         reference operator*() const { return mContainer[mIndex]; }
251         pointer operator->() const { return std::addressof(mContainer[mIndex]); }
252 
253     private:
254         ContainerType& mContainer;
255         size_type mIndex = 0;
256     };
257 
258 private:
259     // Returns the index of the next element in mBuffer.
next(size_type index)260     size_type next(size_type index) const {
261         if (index == capacity() - 1) {
262             return 0;
263         } else {
264             return index + 1;
265         }
266     }
267 
268     // Returns the index of the previous element in mBuffer.
previous(size_type index)269     size_type previous(size_type index) const {
270         if (index == 0) {
271             return capacity() - 1;
272         } else {
273             return index - 1;
274         }
275     }
276 
277     // Converts the index of an element in [0, size()] to its corresponding index in mBuffer.
bufferIndex(size_type elementIndex)278     size_type bufferIndex(size_type elementIndex) const {
279         if (elementIndex > size()) {
280             abort();
281         }
282         size_type index = mBegin + elementIndex;
283         if (index >= capacity()) {
284             index -= capacity();
285         }
286         if (index >= capacity()) {
287             abort();
288         }
289         return index;
290     }
291 
292     pointer mBuffer = nullptr;
293     size_type mCapacity = 0; // Total capacity of mBuffer.
294     size_type mBegin = 0;    // Index of the first initialised element in mBuffer.
295     size_type mSize = 0;     // Total number of initialised elements.
296 };
297 
298 } // namespace android
299