blob: 021ca9ffdb9505e88e71ca3fd09957bbf94b3626 [file] [log] [blame]
// 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_