| /* |
| * Copyright (C) 2015 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| |
| #ifndef ANDROID_SERVICE_UTILS_RING_BUFFER_H |
| #define ANDROID_SERVICE_UTILS_RING_BUFFER_H |
| |
| #include <utils/Log.h> |
| #include <cutils/compiler.h> |
| |
| #include <iterator> |
| #include <utility> |
| #include <vector> |
| |
| namespace android { |
| |
| /** |
| * A RingBuffer class that maintains an array of objects that can grow up to a certain size. |
| * Elements added to the RingBuffer are inserted in the logical front of the buffer, and |
| * invalidate all current iterators for that RingBuffer object. |
| */ |
| template <class T> |
| class RingBuffer final { |
| public: |
| |
| /** |
| * Construct a RingBuffer that can grow up to the given length. |
| */ |
| RingBuffer(size_t length); |
| |
| /** |
| * Forward iterator to this class. Implements an std:forward_iterator. |
| */ |
| class iterator : public std::iterator<std::forward_iterator_tag, T> { |
| public: |
| iterator(T* ptr, size_t size, size_t pos, size_t ctr); |
| |
| iterator& operator++(); |
| |
| iterator operator++(int); |
| |
| bool operator==(const iterator& rhs); |
| |
| bool operator!=(const iterator& rhs); |
| |
| T& operator*(); |
| |
| T* operator->(); |
| |
| private: |
| T* mPtr; |
| size_t mSize; |
| size_t mPos; |
| size_t mCtr; |
| }; |
| |
| /** |
| * Constant forward iterator to this class. Implements an std:forward_iterator. |
| */ |
| class const_iterator : public std::iterator<std::forward_iterator_tag, T> { |
| public: |
| const_iterator(const T* ptr, size_t size, size_t pos, size_t ctr); |
| |
| const_iterator& operator++(); |
| |
| const_iterator operator++(int); |
| |
| bool operator==(const const_iterator& rhs); |
| |
| bool operator!=(const const_iterator& rhs); |
| |
| const T& operator*(); |
| |
| const T* operator->(); |
| |
| private: |
| const T* mPtr; |
| size_t mSize; |
| size_t mPos; |
| size_t mCtr; |
| }; |
| |
| /** |
| * Adds item to the front of this RingBuffer. If the RingBuffer is at its maximum length, |
| * this will result in the last element being replaced (this is done using the element's |
| * assignment operator). |
| * |
| * All current iterators are invalidated. |
| */ |
| void add(const T& item); |
| |
| /** |
| * Moves item to the front of this RingBuffer. Following a call to this, item should no |
| * longer be used. If the RingBuffer is at its maximum length, this will result in the |
| * last element being replaced (this is done using the element's assignment operator). |
| * |
| * All current iterators are invalidated. |
| */ |
| void add(T&& item); |
| |
| /** |
| * Construct item in-place in the front of this RingBuffer using the given arguments. If |
| * the RingBuffer is at its maximum length, this will result in the last element being |
| * replaced (this is done using the element's assignment operator). |
| * |
| * All current iterators are invalidated. |
| */ |
| template <class... Args> |
| void emplace(Args&&... args); |
| |
| /** |
| * Get an iterator to the front of this RingBuffer. |
| */ |
| iterator begin(); |
| |
| /** |
| * Get an iterator to the end of this RingBuffer. |
| */ |
| iterator end(); |
| |
| /** |
| * Get a const_iterator to the front of this RingBuffer. |
| */ |
| const_iterator begin() const; |
| |
| /** |
| * Get a const_iterator to the end of this RingBuffer. |
| */ |
| const_iterator end() const; |
| |
| /** |
| * Return a reference to the element at a given index. If the index is out of range for |
| * this ringbuffer, [0, size), the behavior for this is undefined. |
| */ |
| T& operator[](size_t index); |
| |
| /** |
| * Return a const reference to the element at a given index. If the index is out of range |
| * for this ringbuffer, [0, size), the behavior for this is undefined. |
| */ |
| const T& operator[](size_t index) const; |
| |
| /** |
| * Return the current size of this RingBuffer. |
| */ |
| size_t size() const; |
| |
| /** |
| * Remove all elements from this RingBuffer and set the size to 0. |
| */ |
| void clear(); |
| |
| private: |
| size_t mFrontIdx; |
| size_t mMaxBufferSize; |
| std::vector<T> mBuffer; |
| }; // class RingBuffer |
| |
| |
| template <class T> |
| RingBuffer<T>::RingBuffer(size_t length) : mFrontIdx{0}, mMaxBufferSize{length} {} |
| |
| template <class T> |
| RingBuffer<T>::iterator::iterator(T* ptr, size_t size, size_t pos, size_t ctr) : |
| mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {} |
| |
| template <class T> |
| typename RingBuffer<T>::iterator& RingBuffer<T>::iterator::operator++() { |
| ++mCtr; |
| |
| if (CC_UNLIKELY(mCtr == mSize)) { |
| mPos = mSize; |
| return *this; |
| } |
| |
| mPos = ((CC_UNLIKELY(mPos == 0)) ? mSize - 1 : mPos - 1); |
| return *this; |
| } |
| |
| template <class T> |
| typename RingBuffer<T>::iterator RingBuffer<T>::iterator::operator++(int) { |
| iterator tmp{mPtr, mSize, mPos, mCtr}; |
| ++(*this); |
| return tmp; |
| } |
| |
| template <class T> |
| bool RingBuffer<T>::iterator::operator==(const iterator& rhs) { |
| return (mPtr + mPos) == (rhs.mPtr + rhs.mPos); |
| } |
| |
| template <class T> |
| bool RingBuffer<T>::iterator::operator!=(const iterator& rhs) { |
| return (mPtr + mPos) != (rhs.mPtr + rhs.mPos); |
| } |
| |
| template <class T> |
| T& RingBuffer<T>::iterator::operator*() { |
| return *(mPtr + mPos); |
| } |
| |
| template <class T> |
| T* RingBuffer<T>::iterator::operator->() { |
| return mPtr + mPos; |
| } |
| |
| template <class T> |
| RingBuffer<T>::const_iterator::const_iterator(const T* ptr, size_t size, size_t pos, size_t ctr) : |
| mPtr{ptr}, mSize{size}, mPos{pos}, mCtr{ctr} {} |
| |
| template <class T> |
| typename RingBuffer<T>::const_iterator& RingBuffer<T>::const_iterator::operator++() { |
| ++mCtr; |
| |
| if (CC_UNLIKELY(mCtr == mSize)) { |
| mPos = mSize; |
| return *this; |
| } |
| |
| mPos = ((CC_UNLIKELY(mPos == 0)) ? mSize - 1 : mPos - 1); |
| return *this; |
| } |
| |
| template <class T> |
| typename RingBuffer<T>::const_iterator RingBuffer<T>::const_iterator::operator++(int) { |
| const_iterator tmp{mPtr, mSize, mPos, mCtr}; |
| ++(*this); |
| return tmp; |
| } |
| |
| template <class T> |
| bool RingBuffer<T>::const_iterator::operator==(const const_iterator& rhs) { |
| return (mPtr + mPos) == (rhs.mPtr + rhs.mPos); |
| } |
| |
| template <class T> |
| bool RingBuffer<T>::const_iterator::operator!=(const const_iterator& rhs) { |
| return (mPtr + mPos) != (rhs.mPtr + rhs.mPos); |
| } |
| |
| template <class T> |
| const T& RingBuffer<T>::const_iterator::operator*() { |
| return *(mPtr + mPos); |
| } |
| |
| template <class T> |
| const T* RingBuffer<T>::const_iterator::operator->() { |
| return mPtr + mPos; |
| } |
| |
| template <class T> |
| void RingBuffer<T>::add(const T& item) { |
| if (mBuffer.size() < mMaxBufferSize) { |
| mBuffer.push_back(item); |
| mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize); |
| return; |
| } |
| |
| mBuffer[mFrontIdx] = item; |
| mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize); |
| } |
| |
| template <class T> |
| void RingBuffer<T>::add(T&& item) { |
| if (mBuffer.size() != mMaxBufferSize) { |
| mBuffer.push_back(std::forward<T>(item)); |
| mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize); |
| return; |
| } |
| |
| // Only works for types with move assignment operator |
| mBuffer[mFrontIdx] = std::forward<T>(item); |
| mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize); |
| } |
| |
| template <class T> |
| template <class... Args> |
| void RingBuffer<T>::emplace(Args&&... args) { |
| if (mBuffer.size() != mMaxBufferSize) { |
| mBuffer.emplace_back(std::forward<Args>(args)...); |
| mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize); |
| return; |
| } |
| |
| // Only works for types with move assignment operator |
| mBuffer[mFrontIdx] = T(std::forward<Args>(args)...); |
| mFrontIdx = ((mFrontIdx + 1) % mMaxBufferSize); |
| } |
| |
| template <class T> |
| typename RingBuffer<T>::iterator RingBuffer<T>::begin() { |
| size_t tmp = (mBuffer.size() == 0) ? 0 : mBuffer.size() - 1; |
| return iterator(mBuffer.data(), mBuffer.size(), (mFrontIdx == 0) ? tmp : mFrontIdx - 1, 0); |
| } |
| |
| template <class T> |
| typename RingBuffer<T>::iterator RingBuffer<T>::end() { |
| size_t s = mBuffer.size(); |
| return iterator(mBuffer.data(), s, s, s); |
| } |
| |
| template <class T> |
| typename RingBuffer<T>::const_iterator RingBuffer<T>::begin() const { |
| size_t tmp = (mBuffer.size() == 0) ? 0 : mBuffer.size() - 1; |
| return const_iterator(mBuffer.data(), mBuffer.size(), |
| (mFrontIdx == 0) ? tmp : mFrontIdx - 1, 0); |
| } |
| |
| template <class T> |
| typename RingBuffer<T>::const_iterator RingBuffer<T>::end() const { |
| size_t s = mBuffer.size(); |
| return const_iterator(mBuffer.data(), s, s, s); |
| } |
| |
| template <class T> |
| T& RingBuffer<T>::operator[](size_t index) { |
| LOG_ALWAYS_FATAL_IF(index >= mBuffer.size(), "Index %zu out of bounds, size is %zu.", |
| index, mBuffer.size()); |
| size_t pos = (index >= mFrontIdx) ? |
| mBuffer.size() - 1 - (index - mFrontIdx) : mFrontIdx - 1 - index; |
| return mBuffer[pos]; |
| } |
| |
| template <class T> |
| const T& RingBuffer<T>::operator[](size_t index) const { |
| LOG_ALWAYS_FATAL_IF(index >= mBuffer.size(), "Index %zu out of bounds, size is %zu.", |
| index, mBuffer.size()); |
| size_t pos = (index >= mFrontIdx) ? |
| mBuffer.size() - 1 - (index - mFrontIdx) : mFrontIdx - 1 - index; |
| return mBuffer[pos]; |
| } |
| |
| template <class T> |
| size_t RingBuffer<T>::size() const { |
| return mBuffer.size(); |
| } |
| |
| template <class T> |
| void RingBuffer<T>::clear() { |
| mBuffer.clear(); |
| mFrontIdx = 0; |
| } |
| |
| }; // namespace android |
| |
| #endif // ANDROID_SERVICE_UTILS_RING_BUFFER_H |
| |
| |