1 /*
2 * Copyright (C) 2015 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
18 #ifndef ANDROID_SERVICE_UTILS_RING_BUFFER_H
19 #define ANDROID_SERVICE_UTILS_RING_BUFFER_H
20
21 #include <utils/Log.h>
22 #include <cutils/compiler.h>
23
24 #include <iterator>
25 #include <utility>
26 #include <vector>
27
28 namespace android {
29
30 /**
31 * A RingBuffer class that maintains an array of objects that can grow up to a certain size.
32 * Elements added to the RingBuffer are inserted in the logical front of the buffer, and
33 * invalidate all current iterators for that RingBuffer object.
34 */
35 template <class T>
36 class RingBuffer final {
37 public:
38
39 /**
40 * Construct a RingBuffer that can grow up to the given length.
41 */
42 RingBuffer(size_t length);
43
44 /**
45 * Forward iterator to this class. Implements an std:forward_iterator.
46 */
47 class iterator : public std::iterator<std::forward_iterator_tag, T> {
48 public:
49 iterator(T* ptr, size_t size, size_t pos, size_t ctr);
50
51 iterator& operator++();
52
53 iterator operator++(int);
54
55 bool operator==(const iterator& rhs);
56
57 bool operator!=(const iterator& rhs);
58
59 T& operator*();
60
61 T* operator->();
62
63 private:
64 T* mPtr;
65 size_t mSize;
66 size_t mPos;
67 size_t mCtr;
68 };
69
70 /**
71 * Constant forward iterator to this class. Implements an std:forward_iterator.
72 */
73 class const_iterator : public std::iterator<std::forward_iterator_tag, T> {
74 public:
75 const_iterator(const T* ptr, size_t size, size_t pos, size_t ctr);
76
77 const_iterator& operator++();
78
79 const_iterator operator++(int);
80
81 bool operator==(const const_iterator& rhs);
82
83 bool operator!=(const const_iterator& rhs);
84
85 const T& operator*();
86
87 const T* operator->();
88
89 private:
90 const T* mPtr;
91 size_t mSize;
92 size_t mPos;
93 size_t mCtr;
94 };
95
96 /**
97 * Adds item to the front of this RingBuffer. If the RingBuffer is at its maximum length,
98 * this will result in the last element being replaced (this is done using the element's
99 * assignment operator).
100 *
101 * All current iterators are invalidated.
102 */
103 void add(const T& item);
104
105 /**
106 * Moves item to the front of this RingBuffer. Following a call to this, item should no
107 * longer be used. If the RingBuffer is at its maximum length, this will result in the
108 * last element being replaced (this is done using the element's assignment operator).
109 *
110 * All current iterators are invalidated.
111 */
112 void add(T&& item);
113
114 /**
115 * Construct item in-place in the front of this RingBuffer using the given arguments. If
116 * the RingBuffer is at its maximum length, this will result in the last element being
117 * replaced (this is done using the element's assignment operator).
118 *
119 * All current iterators are invalidated.
120 */
121 template <class... Args>
122 void emplace(Args&&... args);
123
124 /**
125 * Get an iterator to the front of this RingBuffer.
126 */
127 iterator begin();
128
129 /**
130 * Get an iterator to the end of this RingBuffer.
131 */
132 iterator end();
133
134 /**
135 * Get a const_iterator to the front of this RingBuffer.
136 */
137 const_iterator begin() const;
138
139 /**
140 * Get a const_iterator to the end of this RingBuffer.
141 */
142 const_iterator end() const;
143
144 /**
145 * Return a reference to the element at a given index. If the index is out of range for
146 * this ringbuffer, [0, size), the behavior for this is undefined.
147 */
148 T& operator[](size_t index);
149
150 /**
151 * Return a const reference to the element at a given index. If the index is out of range
152 * for this ringbuffer, [0, size), the behavior for this is undefined.
153 */
154 const T& operator[](size_t index) const;
155
156 /**
157 * Return the current size of this RingBuffer.
158 */
159 size_t size() const;
160
161 /**
162 * Remove all elements from this RingBuffer and set the size to 0.
163 */
164 void clear();
165
166 private:
167 size_t mFrontIdx;
168 size_t mMaxBufferSize;
169 std::vector<T> mBuffer;
170 }; // class RingBuffer
171
172
173 template <class T>
RingBuffer(size_t length)174 RingBuffer<T>::RingBuffer(size_t length) : mFrontIdx{0}, mMaxBufferSize{length} {}
175
176 template <class T>
iterator(T * ptr,size_t size,size_t pos,size_t ctr)177 RingBuffer<T>::iterator::iterator(T* ptr, size_t size, size_t pos, size_t ctr) :
178 mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {}
179
180 template <class T>
181 typename RingBuffer<T>::iterator& RingBuffer<T>::iterator::operator++() {
182 ++mCtr;
183
184 if (CC_UNLIKELY(mCtr == mSize)) {
185 mPos = mSize;
186 return *this;
187 }
188
189 mPos = ((CC_UNLIKELY(mPos == 0)) ? mSize - 1 : mPos - 1);
190 return *this;
191 }
192
193 template <class T>
194 typename RingBuffer<T>::iterator RingBuffer<T>::iterator::operator++(int) {
195 iterator tmp{mPtr, mSize, mPos, mCtr};
196 ++(*this);
197 return tmp;
198 }
199
200 template <class T>
201 bool RingBuffer<T>::iterator::operator==(const iterator& rhs) {
202 return (mPtr + mPos) == (rhs.mPtr + rhs.mPos);
203 }
204
205 template <class T>
206 bool RingBuffer<T>::iterator::operator!=(const iterator& rhs) {
207 return (mPtr + mPos) != (rhs.mPtr + rhs.mPos);
208 }
209
210 template <class T>
211 T& RingBuffer<T>::iterator::operator*() {
212 return *(mPtr + mPos);
213 }
214
215 template <class T>
216 T* RingBuffer<T>::iterator::operator->() {
217 return mPtr + mPos;
218 }
219
220 template <class T>
const_iterator(const T * ptr,size_t size,size_t pos,size_t ctr)221 RingBuffer<T>::const_iterator::const_iterator(const T* ptr, size_t size, size_t pos, size_t ctr) :
222 mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {}
223
224 template <class T>
225 typename RingBuffer<T>::const_iterator& RingBuffer<T>::const_iterator::operator++() {
226 ++mCtr;
227
228 if (CC_UNLIKELY(mCtr == mSize)) {
229 mPos = mSize;
230 return *this;
231 }
232
233 mPos = ((CC_UNLIKELY(mPos == 0)) ? mSize - 1 : mPos - 1);
234 return *this;
235 }
236
237 template <class T>
238 typename RingBuffer<T>::const_iterator RingBuffer<T>::const_iterator::operator++(int) {
239 const_iterator tmp{mPtr, mSize, mPos, mCtr};
240 ++(*this);
241 return tmp;
242 }
243
244 template <class T>
245 bool RingBuffer<T>::const_iterator::operator==(const const_iterator& rhs) {
246 return (mPtr + mPos) == (rhs.mPtr + rhs.mPos);
247 }
248
249 template <class T>
250 bool RingBuffer<T>::const_iterator::operator!=(const const_iterator& rhs) {
251 return (mPtr + mPos) != (rhs.mPtr + rhs.mPos);
252 }
253
254 template <class T>
255 const T& RingBuffer<T>::const_iterator::operator*() {
256 return *(mPtr + mPos);
257 }
258
259 template <class T>
260 const T* RingBuffer<T>::const_iterator::operator->() {
261 return mPtr + mPos;
262 }
263
264 template <class T>
add(const T & item)265 void RingBuffer<T>::add(const T& item) {
266 if (mBuffer.size() < mMaxBufferSize) {
267 mBuffer.push_back(item);
268 mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
269 return;
270 }
271
272 mBuffer[mFrontIdx] = item;
273 mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
274 }
275
276 template <class T>
add(T && item)277 void RingBuffer<T>::add(T&& item) {
278 if (mBuffer.size() != mMaxBufferSize) {
279 mBuffer.push_back(std::forward<T>(item));
280 mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
281 return;
282 }
283
284 // Only works for types with move assignment operator
285 mBuffer[mFrontIdx] = std::forward<T>(item);
286 mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
287 }
288
289 template <class T>
290 template <class... Args>
emplace(Args &&...args)291 void RingBuffer<T>::emplace(Args&&... args) {
292 if (mBuffer.size() != mMaxBufferSize) {
293 mBuffer.emplace_back(std::forward<Args>(args)...);
294 mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
295 return;
296 }
297
298 // Only works for types with move assignment operator
299 mBuffer[mFrontIdx] = T(std::forward<Args>(args)...);
300 mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize);
301 }
302
303 template <class T>
begin()304 typename RingBuffer<T>::iterator RingBuffer<T>::begin() {
305 size_t tmp = (mBuffer.size() == 0) ? 0 : mBuffer.size() - 1;
306 return iterator(mBuffer.data(), mBuffer.size(), (mFrontIdx == 0) ? tmp : mFrontIdx - 1, 0);
307 }
308
309 template <class T>
end()310 typename RingBuffer<T>::iterator RingBuffer<T>::end() {
311 size_t s = mBuffer.size();
312 return iterator(mBuffer.data(), s, s, s);
313 }
314
315 template <class T>
begin()316 typename RingBuffer<T>::const_iterator RingBuffer<T>::begin() const {
317 size_t tmp = (mBuffer.size() == 0) ? 0 : mBuffer.size() - 1;
318 return const_iterator(mBuffer.data(), mBuffer.size(),
319 (mFrontIdx == 0) ? tmp : mFrontIdx - 1, 0);
320 }
321
322 template <class T>
end()323 typename RingBuffer<T>::const_iterator RingBuffer<T>::end() const {
324 size_t s = mBuffer.size();
325 return const_iterator(mBuffer.data(), s, s, s);
326 }
327
328 template <class T>
329 T& RingBuffer<T>::operator[](size_t index) {
330 LOG_ALWAYS_FATAL_IF(index >= mBuffer.size(), "Index %zu out of bounds, size is %zu.",
331 index, mBuffer.size());
332 size_t pos = (index >= mFrontIdx) ?
333 mBuffer.size() - 1 - (index - mFrontIdx) : mFrontIdx - 1 - index;
334 return mBuffer[pos];
335 }
336
337 template <class T>
338 const T& RingBuffer<T>::operator[](size_t index) const {
339 LOG_ALWAYS_FATAL_IF(index >= mBuffer.size(), "Index %zu out of bounds, size is %zu.",
340 index, mBuffer.size());
341 size_t pos = (index >= mFrontIdx) ?
342 mBuffer.size() - 1 - (index - mFrontIdx) : mFrontIdx - 1 - index;
343 return mBuffer[pos];
344 }
345
346 template <class T>
size()347 size_t RingBuffer<T>::size() const {
348 return mBuffer.size();
349 }
350
351 template <class T>
clear()352 void RingBuffer<T>::clear() {
353 mBuffer.clear();
354 mFrontIdx = 0;
355 }
356
357 }; // namespace android
358
359 #endif // ANDROID_SERVICE_UTILS_RING_BUFFER_H
360
361
362