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