1#ifndef ANDROID_DVR_RING_BUFFER_H_
2#define ANDROID_DVR_RING_BUFFER_H_
3
4#include <utility>
5#include <vector>
6
7namespace android {
8namespace 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.
18template <typename T>
19class RingBuffer {
20 public:
21  RingBuffer() { Reset(0); }
22
23  explicit RingBuffer(size_t capacity) { Reset(capacity); }
24
25  RingBuffer(const RingBuffer& other) = default;
26  RingBuffer(RingBuffer&& other) = default;
27  RingBuffer& operator=(const RingBuffer& other) = default;
28  RingBuffer& operator=(RingBuffer&& other) = default;
29
30  void Append(const T& val) {
31    if (IsFull())
32      PopFront();
33    Get(size_) = val;
34    size_++;
35  }
36
37  void Append(T&& val) {
38    if (IsFull())
39      PopFront();
40    Get(size_) = std::move(val);
41    size_++;
42  }
43
44  bool IsEmpty() const { return size_ == 0; }
45
46  bool IsFull() const { return size_ == buffer_.size(); }
47
48  size_t GetSize() const { return size_; }
49
50  size_t GetCapacity() const { return buffer_.size(); }
51
52  T& Get(size_t i) { return buffer_[(start_ + i) % buffer_.size()]; }
53
54  const T& Get(size_t i) const {
55    return buffer_[(start_ + i) % buffer_.size()];
56  }
57
58  const T& Back() const { return Get(size_ - 1); }
59
60  T& Back() { return Get(size_ - 1); }
61
62  const T& Front() const { return Get(0); }
63
64  T& Front() { return Get(0); }
65
66  void PopBack() {
67    if (size_ != 0) {
68      Get(size_ - 1) = T();
69      size_--;
70    }
71  }
72
73  void PopFront() {
74    if (size_ != 0) {
75      Get(0) = T();
76      start_ = (start_ + 1) % buffer_.size();
77      size_--;
78    }
79  }
80
81  void Clear() { Reset(GetCapacity()); }
82
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