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 "base/check.h" 11 #include "base/memory/raw_ref.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 RingBuffer(const RingBuffer&) = delete; 29 RingBuffer& operator=(const RingBuffer&) = delete; 30 BufferSize()31 size_t BufferSize() const { return kSize; } 32 CurrentIndex()33 size_t CurrentIndex() const { return current_index_; } 34 35 // Returns true if a value was saved to index |n|. IsFilledIndex(size_t n)36 bool IsFilledIndex(size_t n) const { 37 return IsFilledIndexByBufferIndex(BufferIndex(n)); 38 } 39 40 // Returns the element at index |n| (% |kSize|). 41 // 42 // n = 0 returns the oldest value and 43 // n = bufferSize() - 1 returns the most recent value. ReadBuffer(size_t n)44 const T& ReadBuffer(size_t n) const { 45 const size_t buffer_index = BufferIndex(n); 46 CHECK(IsFilledIndexByBufferIndex(buffer_index)); 47 return buffer_[buffer_index]; 48 } 49 MutableReadBuffer(size_t n)50 T* MutableReadBuffer(size_t n) { 51 const size_t buffer_index = BufferIndex(n); 52 CHECK(IsFilledIndexByBufferIndex(buffer_index)); 53 return &buffer_[buffer_index]; 54 } 55 SaveToBuffer(const T & value)56 void SaveToBuffer(const T& value) { 57 buffer_[BufferIndex(0)] = value; 58 current_index_++; 59 } 60 Clear()61 void Clear() { current_index_ = 0; } 62 63 // Iterator has const access to the RingBuffer it got retrieved from. 64 class Iterator { 65 public: index()66 size_t index() const { return index_; } 67 68 const T* operator->() const { return &buffer_->ReadBuffer(index_); } 69 const T* operator*() const { return &buffer_->ReadBuffer(index_); } 70 71 Iterator& operator++() { 72 index_++; 73 if (index_ == kSize) 74 out_of_range_ = true; 75 return *this; 76 } 77 78 Iterator& operator--() { 79 if (index_ == 0) 80 out_of_range_ = true; 81 index_--; 82 return *this; 83 } 84 85 operator bool() const { 86 return !out_of_range_ && buffer_->IsFilledIndex(index_); 87 } 88 89 private: Iterator(const RingBuffer<T,kSize> & buffer,size_t index)90 Iterator(const RingBuffer<T, kSize>& buffer, size_t index) 91 : buffer_(buffer), index_(index), out_of_range_(false) {} 92 93 const raw_ref<const RingBuffer<T, kSize>> buffer_; 94 size_t index_; 95 bool out_of_range_; 96 97 friend class RingBuffer<T, kSize>; 98 }; 99 100 // Returns an Iterator pointing to the oldest value in the buffer. 101 // Example usage (iterate from oldest to newest value): 102 // for (RingBuffer<T, kSize>::Iterator it = ring_buffer.Begin(); it; ++it) {} Begin()103 Iterator Begin() const { 104 if (current_index_ < kSize) 105 return Iterator(*this, kSize - current_index_); 106 return Iterator(*this, 0); 107 } 108 109 // Returns an Iterator pointing to the newest value in the buffer. 110 // Example usage (iterate backwards from newest to oldest value): 111 // for (RingBuffer<T, kSize>::Iterator it = ring_buffer.End(); it; --it) {} End()112 Iterator End() const { return Iterator(*this, kSize - 1); } 113 114 private: BufferIndex(size_t n)115 inline size_t BufferIndex(size_t n) const { 116 return (current_index_ + n) % kSize; 117 } 118 119 // This specialization of |IsFilledIndex| is a micro-optimization that enables 120 // us to do e.g. `CHECK(IsFilledIndex(n))` without calling |BufferIndex| 121 // twice. Since |BufferIndex| involves a % operation, it's not quite free at a 122 // micro-scale. IsFilledIndexByBufferIndex(size_t buffer_index)123 inline bool IsFilledIndexByBufferIndex(size_t buffer_index) const { 124 return buffer_index < current_index_; 125 } 126 127 T buffer_[kSize]; 128 size_t current_index_; 129 }; 130 131 } // namespace base 132 133 #endif // BASE_CONTAINERS_RING_BUFFER_H_ 134