1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef BASE_CONTAINERS_RING_BUFFER_H_
6 #define BASE_CONTAINERS_RING_BUFFER_H_
7 
8 #include <stddef.h>
9 
10 #include "base/logging.h"
11 #include "base/macros.h"
12 
13 namespace base {
14 
15 // base::RingBuffer uses a fixed-size array, unlike base::circular_deque and
16 // std::deque, and so, one can access only the last |kSize| elements. Also, you
17 // can add elements to the front and read/modify random elements, but cannot
18 // remove elements from the back. Therefore, it does not have a |Size| method,
19 // only |BufferSize|, which is a constant, and |CurrentIndex|, which is the
20 // number of elements added so far.
21 //
22 // If the above is sufficient for your use case, base::RingBuffer should be more
23 // efficient than base::circular_deque.
24 template <typename T, size_t kSize>
25 class RingBuffer {
26  public:
RingBuffer()27   RingBuffer() : current_index_(0) {}
28 
BufferSize()29   size_t BufferSize() const { return kSize; }
30 
CurrentIndex()31   size_t CurrentIndex() const { return current_index_; }
32 
33   // Returns true if a value was saved to index |n|.
IsFilledIndex(size_t n)34   bool IsFilledIndex(size_t n) const {
35     return IsFilledIndexByBufferIndex(BufferIndex(n));
36   }
37 
38   // Returns the element at index |n| (% |kSize|).
39   //
40   // n = 0 returns the oldest value and
41   // n = bufferSize() - 1 returns the most recent value.
ReadBuffer(size_t n)42   const T& ReadBuffer(size_t n) const {
43     const size_t buffer_index = BufferIndex(n);
44     CHECK(IsFilledIndexByBufferIndex(buffer_index));
45     return buffer_[buffer_index];
46   }
47 
MutableReadBuffer(size_t n)48   T* MutableReadBuffer(size_t n) {
49     const size_t buffer_index = BufferIndex(n);
50     CHECK(IsFilledIndexByBufferIndex(buffer_index));
51     return &buffer_[buffer_index];
52   }
53 
SaveToBuffer(const T & value)54   void SaveToBuffer(const T& value) {
55     buffer_[BufferIndex(0)] = value;
56     current_index_++;
57   }
58 
Clear()59   void Clear() { current_index_ = 0; }
60 
61   // Iterator has const access to the RingBuffer it got retrieved from.
62   class Iterator {
63    public:
index()64     size_t index() const { return index_; }
65 
66     const T* operator->() const { return &buffer_.ReadBuffer(index_); }
67     const T* operator*() const { return &buffer_.ReadBuffer(index_); }
68 
69     Iterator& operator++() {
70       index_++;
71       if (index_ == kSize)
72         out_of_range_ = true;
73       return *this;
74     }
75 
76     Iterator& operator--() {
77       if (index_ == 0)
78         out_of_range_ = true;
79       index_--;
80       return *this;
81     }
82 
83     operator bool() const {
84       return !out_of_range_ && buffer_.IsFilledIndex(index_);
85     }
86 
87    private:
Iterator(const RingBuffer<T,kSize> & buffer,size_t index)88     Iterator(const RingBuffer<T, kSize>& buffer, size_t index)
89         : buffer_(buffer), index_(index), out_of_range_(false) {}
90 
91     const RingBuffer<T, kSize>& buffer_;
92     size_t index_;
93     bool out_of_range_;
94 
95     friend class RingBuffer<T, kSize>;
96   };
97 
98   // Returns an Iterator pointing to the oldest value in the buffer.
99   // Example usage (iterate from oldest to newest value):
100   //  for (RingBuffer<T, kSize>::Iterator it = ring_buffer.Begin(); it; ++it) {}
Begin()101   Iterator Begin() const {
102     if (current_index_ < kSize)
103       return Iterator(*this, kSize - current_index_);
104     return Iterator(*this, 0);
105   }
106 
107   // Returns an Iterator pointing to the newest value in the buffer.
108   // Example usage (iterate backwards from newest to oldest value):
109   //  for (RingBuffer<T, kSize>::Iterator it = ring_buffer.End(); it; --it) {}
End()110   Iterator End() const { return Iterator(*this, kSize - 1); }
111 
112  private:
BufferIndex(size_t n)113   inline size_t BufferIndex(size_t n) const {
114     return (current_index_ + n) % kSize;
115   }
116 
117   // This specialization of |IsFilledIndex| is a micro-optimization that enables
118   // us to do e.g. `CHECK(IsFilledIndex(n))` without calling |BufferIndex|
119   // twice. Since |BufferIndex| involves a % operation, it's not quite free at a
120   // micro-scale.
IsFilledIndexByBufferIndex(size_t buffer_index)121   inline bool IsFilledIndexByBufferIndex(size_t buffer_index) const {
122     return buffer_index < current_index_;
123   }
124 
125   T buffer_[kSize];
126   size_t current_index_;
127 
128   DISALLOW_COPY_AND_ASSIGN(RingBuffer);
129 };
130 
131 }  // namespace base
132 
133 #endif  // BASE_CONTAINERS_RING_BUFFER_H_
134