1 // Copyright 2016 The Android Open Source Project
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #pragma once
16 
17 #include <vector>
18 #include <utility>
19 #include <type_traits>
20 #include <cassert>
21 
22 namespace android {
23 namespace base {
24 
25 // A CircularBuffer<T> is a wrapper over std::vector<T> of fixed size
26 // that has the following properties:
27 // 1. Only allows adding new elements via |push_back|
28 // 2. Items can be removed either from the front or from the back.
29 // 3. When at maximum capacity, the oldest element is removed to make
30 //    space for the new one.
31 template <class T, class A = std::allocator<T>>
32 class CircularBuffer {
33 public:
34     using value_type = T;
35 
36     // Create a new circular buffer with the given |capacity|.
CircularBuffer(int capacity)37     explicit CircularBuffer(int capacity) :
38         mBuf(capacity), mSize(0), mFrontIdx(0), mBackIdx(0) {
39         assert(capacity > 0);
40     }
41 
42     // Adds a new element at the end of the container. If the container
43     // is at maximum capacity, the oldest element will be removed to make
44     // space for the new one.
45     template <class U>
46     typename std::enable_if<std::is_convertible<U, T>::value>::type
push_back(U && value)47     push_back(U&& value) {
48         mBuf[mBackIdx] = std::forward<U>(value);
49         incrementBackIdx();
50     }
51 
52     // Returns the first element in the container.
53     // Undefined behavior if called on an empty container.
front()54     T& front() {
55         assert(!empty());
56         return mBuf[mFrontIdx];
57     }
58 
59     // Same as above, const version.
front()60     const T& front() const {
61         assert(!empty());
62         return mBuf[mFrontIdx];
63     }
64 
65     // Returns the last element in the container.
66     // Undefined behavior if called on an empty container.
back()67     T& back() {
68         assert(!empty());
69         return mBuf[(mFrontIdx + mSize - 1) % mBuf.size()];
70     }
71 
72     // Same as above, const version.
back()73     const T& back() const {
74         assert(!empty());
75         return mBuf[(mFrontIdx + mSize - 1) % mBuf.size()];
76     }
77 
78     // Removes the first element in the container.
79     // Undefined behavior if called on an empty container.
pop_front()80     void pop_front() {
81         assert(!empty());
82         mSize--;
83         mFrontIdx = (mFrontIdx + 1) % mBuf.size();
84     }
85 
86     // Removes the last element in the container.
87     // Undefined behavior if called on an empty container.
pop_back()88     void pop_back() {
89         assert(!empty());
90         mSize--;
91         mBackIdx -= 1;
92         if (mBackIdx < 0) mBackIdx = mBuf.size() - 1;
93     }
94 
95     // Returns true if the container is empty, false otherwise.
empty()96     bool empty() const {
97         return mSize == 0;
98     }
99 
100     // Returns the number of elements in the buffer
size()101     int size() const {
102         return mSize;
103     }
104 
105     // Get a specific element from the buffer.
106     // |idx| must be between 0 and |size|.
107     T& operator[](int idx) {
108         return mBuf[(mFrontIdx + idx) % mBuf.size()];
109     }
110 
111     // Same as above, const version.
112     const T& operator[](int idx) const {
113         return mBuf[(mFrontIdx + idx) % mBuf.size()];
114     }
115 
116 private:
incrementBackIdx()117     void incrementBackIdx() {
118         if (mSize < static_cast<int>(mBuf.size())) {
119             mSize++;
120         } else {
121            // Buffer is at full capacity, erase first
122            // element.
123            mFrontIdx = (mFrontIdx + 1) % mBuf.size();
124         }
125         mBackIdx = (mBackIdx + 1) % mBuf.size();
126     }
127 
128     // Buffer containing the data.
129     std::vector<T, A> mBuf;
130 
131     // Number of elements in the circular buffer.
132     int mSize;
133 
134     // Index, at which the first (oldest) element of
135     // the circular buffer is stored in mBuf.
136     int mFrontIdx;
137 
138     // Index at which the next element will be placed
139     // in mBuf.
140     int mBackIdx;
141 };
142 
143 }
144 }
145