Add RingBuffer class and test.
Change-Id: I63f66d70ccf43b5c3b49046cdfecf558ddbd6af7
diff --git a/aos/common/BUILD b/aos/common/BUILD
index 658a2e6..f4b57d5 100644
--- a/aos/common/BUILD
+++ b/aos/common/BUILD
@@ -393,3 +393,21 @@
'//aos/common/util:death_test_log_implementation',
],
)
+
+cc_library(
+ name = 'ring_buffer',
+ hdrs = [
+ 'ring_buffer.h',
+ ],
+)
+
+cc_test(
+ name = 'ring_buffer_test',
+ srcs = [
+ 'ring_buffer_test.cc',
+ ],
+ deps = [
+ ':ring_buffer',
+ '//aos/testing:googletest',
+ ],
+)
diff --git a/aos/common/ring_buffer.h b/aos/common/ring_buffer.h
new file mode 100644
index 0000000..293c817
--- /dev/null
+++ b/aos/common/ring_buffer.h
@@ -0,0 +1,59 @@
+#ifndef AOS_COMMON_RING_BUFFER_H_
+#define AOS_COMMON_RING_BUFFER_H_
+
+#include <array>
+
+namespace aos {
+
+// This is a helper to keep track of some amount of recent data. As you push
+// data into the ring buffer, it gets stored. If the buffer becomes full, it
+// will start overwriting the oldest data.
+template <typename Data, size_t buffer_size>
+class RingBuffer {
+ public:
+ RingBuffer() {}
+
+ // Add an item to the RingBuffer, overwriting the oldest element if necessary
+ void Push(const Data &data) {
+ if (full()) {
+ data_[oldest_] = data;
+ oldest_ = (oldest_ + 1) % buffer_size;
+ } else {
+ data_[(oldest_ + size_) % buffer_size] = data;
+ ++size_;
+ }
+ }
+
+ // Return the value of the index requested, adjusted so that the RingBuffer
+ // contians the oldest element first and the newest last.
+ Data &operator[](size_t index) {
+ return data_[(oldest_ + index) % buffer_size];
+ }
+
+ const Data &operator[](size_t index) const {
+ return data_[(oldest_ + index) % buffer_size];
+ }
+
+ // Returns the capacity of the RingBuffer
+ size_t capacity() const { return buffer_size; }
+
+ // Returns the number of elements stored in the RingBuffer
+ size_t size() const { return size_; }
+
+ // Is the RingBuffer empty or full?
+ bool empty() const { return size_ == 0; }
+
+ bool full() const { return size_ == buffer_size; }
+
+ private:
+ ::std::array<Data, buffer_size> data_;
+
+ // 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;
+};
+
+} // namespace aos
+
+#endif // AOS_COMMON_RING_BUFFER_H_
diff --git a/aos/common/ring_buffer_test.cc b/aos/common/ring_buffer_test.cc
new file mode 100644
index 0000000..ca3f35d
--- /dev/null
+++ b/aos/common/ring_buffer_test.cc
@@ -0,0 +1,71 @@
+#include "aos/common/ring_buffer.h"
+
+#include "gtest/gtest.h"
+
+namespace aos {
+namespace testing {
+
+class RingBufferTest : public ::testing::Test {
+ public:
+ RingBufferTest() {}
+
+ protected:
+ RingBuffer<int, 10> buffer_;
+};
+
+// Test if the RingBuffer is empty when initialized properly
+TEST_F(RingBufferTest, DefaultIsEmpty) {
+ // The RingBuffer should have a size of 0, a capacity of 10 (note that it was
+ // initialized as 10), have no items, and not be full
+ ASSERT_EQ(0u, buffer_.size());
+ ASSERT_EQ(10u, buffer_.capacity());
+ ASSERT_TRUE(buffer_.empty());
+ ASSERT_FALSE(buffer_.full());
+}
+
+// Test that the RingBuffer can fill it's entire capacity and read back the data
+TEST_F(RingBufferTest, CanAddData) {
+ ASSERT_TRUE(buffer_.empty());
+
+ // Add sequential numbers to the RingBuffer
+ // (the value of each item is it's index #)
+ for (size_t i = 0; i < buffer_.capacity(); ++i) {
+ // The buffer shouldn't be full yet, and it's size should be how many items
+ // we've added so far. Once that happens, we add another item
+ ASSERT_FALSE(buffer_.full());
+ ASSERT_EQ(i, buffer_.size());
+ 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
+ ASSERT_FALSE(buffer_.empty());
+ ASSERT_EQ(i + 1, buffer_.size());
+ ASSERT_EQ(i, buffer_[i]);
+ }
+
+ ASSERT_TRUE(buffer_.full());
+}
+
+// Tests that the RingBuffer properly loops back and starts overwriting from the
+// first element after being filled up
+TEST_F(RingBufferTest, OverfillData) {
+ // Add numbers 0-24 to the RingBuffer
+ for (int i = 0; i < 25; ++i) {
+ buffer_.Push(i);
+ }
+
+ // It should now be full
+ 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
+ for (size_t i = 0; i < buffer_.size(); ++i) {
+ ASSERT_EQ(15 + i, buffer_[i]);
+ }
+}
+
+} // namespace testing
+} // namespace aos