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