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