1e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko#ifndef ANDROID_DVR_RING_BUFFER_H_ 2e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko#define ANDROID_DVR_RING_BUFFER_H_ 3e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 4e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko#include <utility> 5e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko#include <vector> 6e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 7e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenkonamespace android { 8e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenkonamespace dvr { 9e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 10e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// A simple ring buffer implementation. 11e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// 12e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// A vector works but you either have to keep track of start_ and size_ yourself 13e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// or erase() from the front which is inefficient. 14e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// 15e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// A deque works but the common usage pattern of Append() PopFront() Append() 16e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// PopFront() looks like it allocates each time size goes from 0 --> 1, which we 17e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko// don't want. This class allocates only once. 18e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenkotemplate <typename T> 19e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenkoclass RingBuffer { 20e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko public: 21e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko RingBuffer() { Reset(0); } 22e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 23e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko explicit RingBuffer(size_t capacity) { Reset(capacity); } 24e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 25e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko RingBuffer(const RingBuffer& other) = default; 26e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko RingBuffer(RingBuffer&& other) = default; 27e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko RingBuffer& operator=(const RingBuffer& other) = default; 28e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko RingBuffer& operator=(RingBuffer&& other) = default; 29e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 30e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko void Append(const T& val) { 31e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko if (IsFull()) 32e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko PopFront(); 33e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko Get(size_) = val; 34e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_++; 35e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 36e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 37e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko void Append(T&& val) { 38e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko if (IsFull()) 39e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko PopFront(); 40e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko Get(size_) = std::move(val); 41e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_++; 42e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 43e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 44e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko bool IsEmpty() const { return size_ == 0; } 45e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 46e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko bool IsFull() const { return size_ == buffer_.size(); } 47e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 48e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_t GetSize() const { return size_; } 49e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 50e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_t GetCapacity() const { return buffer_.size(); } 51e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 52e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko T& Get(size_t i) { return buffer_[(start_ + i) % buffer_.size()]; } 53e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 54e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko const T& Get(size_t i) const { 55e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko return buffer_[(start_ + i) % buffer_.size()]; 56e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 57e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 58e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko const T& Back() const { return Get(size_ - 1); } 59e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 60e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko T& Back() { return Get(size_ - 1); } 61e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 62e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko const T& Front() const { return Get(0); } 63e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 64e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko T& Front() { return Get(0); } 65e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 66e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko void PopBack() { 67e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko if (size_ != 0) { 68e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko Get(size_ - 1) = T(); 69e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_--; 70e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 71e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 72e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 73e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko void PopFront() { 74e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko if (size_ != 0) { 75e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko Get(0) = T(); 76e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko start_ = (start_ + 1) % buffer_.size(); 77e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_--; 78e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 79e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 80e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 81e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko void Clear() { Reset(GetCapacity()); } 82e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 83e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko void Reset(size_t capacity) { 84e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko start_ = size_ = 0; 85e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko buffer_.clear(); 86e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko buffer_.resize(capacity); 87e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko } 88e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 89e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko private: 90e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko // Ideally we'd allocate our own memory and use placement new to instantiate 91e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko // instances of T instead of using a vector, but the vector is simpler. 92e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko std::vector<T> buffer_; 93e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko size_t start_, size_; 94e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko}; 95e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 96e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko} // namespace dvr 97e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko} // namespace android 98e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko 99e4eec20f6263f4a42ae462456f60ea6c4518bb0aAlex Vakulenko#endif // ANDROID_DVR_RING_BUFFER_H_ 100