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#ifndef ANDROID_SENSOR_SERVICE_UTIL_RING_BUFFER_H
18#define ANDROID_SENSOR_SERVICE_UTIL_RING_BUFFER_H
19
20#include <utils/Log.h>
21#include <cutils/compiler.h>
22
23#include <iterator>
24#include <utility>
25#include <vector>
26
27namespace android {
28namespace SensorServiceUtil {
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 */
35template <class T>
36class RingBuffer final {
37public:
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
166private:
167    size_t mFrontIdx;
168    size_t mMaxBufferSize;
169    std::vector<T> mBuffer;
170}; // class RingBuffer
171
172
173template <class T>
174RingBuffer<T>::RingBuffer(size_t length) : mFrontIdx{0}, mMaxBufferSize{length} {}
175
176template <class T>
177RingBuffer<T>::iterator::iterator(T* ptr, size_t size, size_t pos, size_t ctr) :
178        mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {}
179
180template <class T>
181typename 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
193template <class T>
194typename RingBuffer<T>::iterator RingBuffer<T>::iterator::operator++(int) {
195    iterator tmp{mPtr, mSize, mPos, mCtr};
196    ++(*this);
197    return tmp;
198}
199
200template <class T>
201bool RingBuffer<T>::iterator::operator==(const iterator& rhs) {
202    return (mPtr + mPos) == (rhs.mPtr + rhs.mPos);
203}
204
205template <class T>
206bool RingBuffer<T>::iterator::operator!=(const iterator& rhs) {
207    return (mPtr + mPos) != (rhs.mPtr + rhs.mPos);
208}
209
210template <class T>
211T& RingBuffer<T>::iterator::operator*() {
212    return *(mPtr + mPos);
213}
214
215template <class T>
216T* RingBuffer<T>::iterator::operator->() {
217    return mPtr + mPos;
218}
219
220template <class T>
221RingBuffer<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
224template <class T>
225typename 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
237template <class T>
238typename 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
244template <class T>
245bool RingBuffer<T>::const_iterator::operator==(const const_iterator& rhs) {
246    return (mPtr + mPos) == (rhs.mPtr + rhs.mPos);
247}
248
249template <class T>
250bool RingBuffer<T>::const_iterator::operator!=(const const_iterator& rhs) {
251    return (mPtr + mPos) != (rhs.mPtr + rhs.mPos);
252}
253
254template <class T>
255const T& RingBuffer<T>::const_iterator::operator*() {
256    return *(mPtr + mPos);
257}
258
259template <class T>
260const T* RingBuffer<T>::const_iterator::operator->() {
261    return mPtr + mPos;
262}
263
264template <class T>
265void 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
276template <class T>
277void 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
289template <class T>
290template <class... Args>
291void 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
303template <class T>
304typename 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
309template <class T>
310typename RingBuffer<T>::iterator RingBuffer<T>::end() {
311    size_t s = mBuffer.size();
312    return iterator(mBuffer.data(), s, s, s);
313}
314
315template <class T>
316typename 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
322template <class T>
323typename 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
328template <class T>
329T& 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
337template <class T>
338const 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
346template <class T>
347size_t RingBuffer<T>::size() const {
348    return mBuffer.size();
349}
350
351template <class T>
352void RingBuffer<T>::clear() {
353    mBuffer.clear();
354    mFrontIdx = 0;
355}
356
357}  // namespace SensorServiceUtil
358}; // namespace android
359
360#endif // ANDROID_SENSOR_SERVICE_UTIL_RING_BUFFER_H
361
362