Fix up the AOS RingBuffer to not default construct and iterate better
This lets us put more complicated objects in it.
Change-Id: I19ef2e1934c30e5f10ecdac9d9e8af03282c97aa
diff --git a/aos/containers/BUILD b/aos/containers/BUILD
index 70d98f1..e9f8262 100644
--- a/aos/containers/BUILD
+++ b/aos/containers/BUILD
@@ -17,6 +17,7 @@
deps = [
":ring_buffer",
"//aos/testing:googletest",
+ "@com_github_google_glog//:glog",
],
)
diff --git a/aos/containers/ring_buffer.h b/aos/containers/ring_buffer.h
index cd7872e..b928354 100644
--- a/aos/containers/ring_buffer.h
+++ b/aos/containers/ring_buffer.h
@@ -10,23 +10,116 @@
// will start overwriting the oldest data.
template <typename Data, size_t buffer_size>
class RingBuffer {
+ template <typename ValueType, typename BufferType>
+ struct generic_iterator {
+ using iterator_category = ::std::random_access_iterator_tag;
+ using value_type = ValueType;
+ using difference_type = ::std::ptrdiff_t;
+ using pointer = value_type *;
+ using reference = value_type &;
+
+ explicit generic_iterator(BufferType *buffer, size_t index)
+ : buffer_(buffer), index_(index) {}
+
+ generic_iterator &operator++() {
+ ++index_;
+ return *this;
+ }
+ generic_iterator operator++(int) {
+ const generic_iterator retval = *this;
+ ++(*this);
+ return retval;
+ }
+ generic_iterator &operator--() {
+ --index_;
+ return *this;
+ }
+ generic_iterator operator--(int) {
+ const generic_iterator retval = *this;
+ --(*this);
+ return retval;
+ }
+
+ generic_iterator &operator+=(ptrdiff_t i) {
+ index_ += i;
+ return *this;
+ }
+ generic_iterator operator+(ptrdiff_t i) const {
+ generic_iterator retval = *this;
+ retval += i;
+ return retval;
+ }
+ generic_iterator &operator-=(ptrdiff_t i) {
+ index_ -= i;
+ return *this;
+ }
+ generic_iterator operator-(ptrdiff_t i) const {
+ generic_iterator retval = *this;
+ retval -= i;
+ return retval;
+ }
+
+ ptrdiff_t operator-(generic_iterator other) const {
+ return index_ - other.index_;
+ }
+
+ bool operator==(generic_iterator other) const {
+ return buffer_ == other.buffer_ && index_ == other.index_;
+ }
+ bool operator!=(generic_iterator other) const { return !(*this == other); }
+
+ bool operator<(generic_iterator other) const {
+ return buffer_ == other.buffer_ && index_ < other.index_;
+ }
+ bool operator>(generic_iterator other) const {
+ return buffer_ == other.buffer_ && index_ > other.index_;
+ }
+ bool operator<=(generic_iterator other) const {
+ return buffer_ == other.buffer_ && index_ <= other.index_;
+ }
+ bool operator>=(generic_iterator other) const {
+ return buffer_ == other.buffer_ && index_ >= other.index_;
+ }
+
+ reference operator*() const { return (*buffer_)[index_]; }
+ pointer operator->() const { return &(*buffer_)[index_]; }
+
+ reference operator[](difference_type i) const {
+ return (*buffer_)[index_ + i];
+ }
+
+ private:
+ BufferType *buffer_;
+ size_t index_;
+ };
+
public:
+ using iterator = generic_iterator<Data, RingBuffer>;
+ using const_iterator = generic_iterator<const Data, const RingBuffer>;
+
static constexpr size_t kBufferSize = buffer_size;
constexpr RingBuffer() {}
+ ~RingBuffer() { Reset(); }
- // Add an item to the RingBuffer, overwriting the oldest element if necessary
- void Push(const Data &data) {
+ // Add an item to the RingBuffer, overwriting the oldest element if necessary.
+ //
+ // Invalidates the end iterator.
+ void Push(Data data) {
if (full()) {
- data_[oldest_] = data;
+ (*this)[0] = std::move(data);
oldest_ = (oldest_ + 1) % buffer_size;
} else {
- data_[(oldest_ + size_) % buffer_size] = data;
+ new (&(*this)[size_]) Data(std::move(data));
++size_;
}
}
+ // Removes the oldest element.
+ //
+ // Invalidates all iterators.
void Shift() {
+ (*this)[0].~Data();
oldest_ = (oldest_ + 1) % buffer_size;
--size_;
}
@@ -34,11 +127,24 @@
// Return the value of the index requested, adjusted so that the RingBuffer
// contains the oldest element first and the newest last.
Data &operator[](size_t index) {
- return data_[(oldest_ + index) % buffer_size];
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+ return *std::launder(
+ reinterpret_cast<Data *>(&data_[(oldest_ + index) % buffer_size]));
+#else
+ // TODO(brian): Remove this when all our compilers are 17 or newer.
+ return *reinterpret_cast<Data *>(&data_[(oldest_ + index) % buffer_size]);
+#endif
}
const Data &operator[](size_t index) const {
- return data_[(oldest_ + index) % buffer_size];
+#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
+ return *std::launder(reinterpret_cast<const Data *>(
+ &data_[(oldest_ + index) % buffer_size]));
+#else
+ // TODO(brian): Remove this when all our compilers are 17 or newer.
+ return *reinterpret_cast<const Data *>(
+ &data_[(oldest_ + index) % buffer_size]);
+#endif
}
// Returns the capacity of the RingBuffer
@@ -53,69 +159,13 @@
bool full() const { return size_ == buffer_size; }
// Clears all the data out of the buffer.
- void Reset() { size_ = 0; }
-
- class iterator {
- public:
- using iterator_category = ::std::forward_iterator_tag;
- using value_type = Data;
- using difference_type = ::std::ptrdiff_t;
- using pointer = Data *;
- using reference = Data &;
-
- explicit iterator(RingBuffer *buffer, size_t index)
- : buffer_(buffer), index_(index) {}
-
- iterator &operator++() {
- ++index_;
- return *this;
+ //
+ // Invalidates all iterators.
+ void Reset() {
+ while (!empty()) {
+ Shift();
}
- iterator operator++(int) {
- iterator retval = *this;
- ++(*this);
- return retval;
- }
- bool operator==(iterator other) const {
- return buffer_ == other.buffer_ && index_ == other.index_;
- }
- bool operator!=(iterator other) const { return !(*this == other); }
- reference operator*() const { return (*buffer_)[index_]; }
-
- private:
- RingBuffer *buffer_;
- size_t index_;
- };
-
- class const_iterator {
- public:
- using iterator_category = ::std::forward_iterator_tag;
- using value_type = Data;
- using difference_type = ::std::ptrdiff_t;
- using pointer = Data *;
- using reference = Data &;
-
- explicit const_iterator(const RingBuffer *buffer, size_t index)
- : buffer_(buffer), index_(index) {}
-
- const_iterator &operator++() {
- ++index_;
- return *this;
- }
- const_iterator operator++(int) {
- const_iterator retval = *this;
- ++(*this);
- return retval;
- }
- bool operator==(const_iterator other) const {
- return buffer_ == other.buffer_ && index_ == other.index_;
- }
- bool operator!=(const_iterator other) const { return !(*this == other); }
- const Data &operator*() const { return (*buffer_)[index_]; }
-
- private:
- const RingBuffer *buffer_;
- size_t index_;
- };
+ }
iterator begin() { return iterator(this, 0); }
iterator end() { return iterator(this, size()); }
@@ -124,10 +174,12 @@
const_iterator end() const { return const_iterator(this, size()); }
private:
- ::std::array<Data, buffer_size> data_;
+ using DataStorage =
+ typename std::aligned_storage<sizeof(Data), alignof(Data)>::type;
+ std::array<DataStorage, buffer_size> data_;
- // Oldest contains the oldest item added to the RingBuffer which will be the
- // next one to be overwritten
+ // Oldest contains the oldest item added to the RingBuffer which will be
+ // the next one to be overwritten
size_t oldest_ = 0;
size_t size_ = 0;
};
diff --git a/aos/containers/ring_buffer_test.cc b/aos/containers/ring_buffer_test.cc
index 01e057f..b4cf1fb 100644
--- a/aos/containers/ring_buffer_test.cc
+++ b/aos/containers/ring_buffer_test.cc
@@ -1,16 +1,70 @@
#include "aos/containers/ring_buffer.h"
+#include "glog/logging.h"
#include "gtest/gtest.h"
namespace aos {
namespace testing {
+// A class which is implicitly convertible to and from int, and tracks object
+// lifetimes.
+struct TrackedInt {
+ enum class State { kNoValue, kAlive, kDestroyed };
+
+ static int instance_count;
+ int value;
+ State state;
+
+ TrackedInt(int new_value) : value(new_value), state(State::kAlive) {
+ ++instance_count;
+ }
+
+ TrackedInt(const TrackedInt &other) = delete;
+ TrackedInt(TrackedInt &&other) : value(other.value), state(other.state) {
+ CHECK(other.state != State::kDestroyed);
+ other.state = State::kNoValue;
+ ++instance_count;
+ }
+ ~TrackedInt() {
+ CHECK(state != State::kDestroyed);
+ state = State::kDestroyed;
+ --instance_count;
+ CHECK_GE(instance_count, 0);
+ }
+ TrackedInt &operator=(const TrackedInt &other) = delete;
+ TrackedInt &operator=(TrackedInt &&other) {
+ CHECK(state != State::kDestroyed);
+ CHECK(other.state != State::kDestroyed);
+ state = other.state;
+ other.state = State::kNoValue;
+ value = other.value;
+ return *this;
+ }
+
+ operator int() const {
+ CHECK(state == State::kAlive);
+ return value;
+ }
+};
+
+int TrackedInt::instance_count;
+
+struct TrackedIntTracker {
+ TrackedIntTracker() {
+ CHECK_EQ(0, TrackedInt::instance_count) << ": Instances alive before test";
+ }
+ ~TrackedIntTracker() {
+ CHECK_EQ(0, TrackedInt::instance_count) << ": Instances alive after test";
+ }
+};
+
class RingBufferTest : public ::testing::Test {
public:
RingBufferTest() {}
protected:
- RingBuffer<int, 10> buffer_;
+ TrackedIntTracker tracked_int_tracker_;
+ RingBuffer<TrackedInt, 10> buffer_;
};
// Test if the RingBuffer is empty when initialized properly
@@ -37,9 +91,8 @@
buffer_.Push(i);
// The buffer shouldn't be empty and it's size should be 1 more since we
- // just
- // added an item. Also, the last item in the buffer should equal the one we
- // just added
+ // just added an item. Also, the last item in the buffer should equal the
+ // one we just added
ASSERT_FALSE(buffer_.empty());
ASSERT_EQ(i + 1, buffer_.size());
ASSERT_EQ(i, buffer_[i]);
@@ -60,8 +113,7 @@
ASSERT_TRUE(buffer_.full());
// Since the buffer is a size of 10 and has been filled up 2.5 times, it
- // should
- // now contain the numbers 15-24
+ // should now contain the numbers 15-24
for (size_t i = 0; i < buffer_.size(); ++i) {
ASSERT_EQ(15 + i, buffer_[i]);
}
@@ -144,7 +196,7 @@
buffer_.Push(i);
}
- const RingBuffer<int, 10> &cbuffer = buffer_;
+ const RingBuffer<TrackedInt, 10> &cbuffer = buffer_;
int i = 0;
for (const int element : cbuffer) {