ring_buffer.h 4.0 KB

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