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     explicit 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