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