Add SizedArray
We have enough places where we want something really simple that can
hold a small (fixed maximum) number of trivially default-constructible
types (like integers), that it's time to actually write a container to
hold them nicely.
Change-Id: I8514e5285cbebe65582d0e817d883c2a05e38ea4
diff --git a/aos/containers/BUILD b/aos/containers/BUILD
index ff0b600..c139195 100644
--- a/aos/containers/BUILD
+++ b/aos/containers/BUILD
@@ -35,3 +35,21 @@
"//aos/testing:googletest",
],
)
+
+cc_library(
+ name = "sized_array",
+ hdrs = [
+ "sized_array.h",
+ ],
+)
+
+cc_test(
+ name = "sized_array_test",
+ srcs = [
+ "sized_array_test.cc",
+ ],
+ deps = [
+ ":sized_array",
+ "//aos/testing:googletest",
+ ],
+)
diff --git a/aos/containers/sized_array.h b/aos/containers/sized_array.h
new file mode 100644
index 0000000..264d466
--- /dev/null
+++ b/aos/containers/sized_array.h
@@ -0,0 +1,108 @@
+#ifndef AOS_CONTAINERS_SIZED_ARRAY_H_
+#define AOS_CONTAINERS_SIZED_ARRAY_H_
+
+#include <array>
+
+namespace aos {
+
+// An array along with a variable size. This is a simple variable-size container
+// with a fixed maximum size.
+//
+// Note that it default-constructs N T instances at construction time. This
+// simplifies the internal bookkeeping a lot (I believe this can be
+// all-constexpr in C++17), but makes it a poor choice for complex T.
+template <typename T, size_t N>
+class SizedArray {
+ private:
+ using array = std::array<T, N>;
+
+ public:
+ using value_type = typename array::value_type;
+ using size_type = typename array::size_type;
+ using difference_type = typename array::difference_type;
+ using reference = typename array::reference;
+ using const_reference = typename array::const_reference;
+ using pointer = typename array::pointer;
+ using const_pointer = typename array::const_pointer;
+ using iterator = typename array::iterator;
+ using const_iterator = typename array::const_iterator;
+ using reverse_iterator = typename array::reverse_iterator;
+ using const_reverse_iterator = typename array::const_reverse_iterator;
+
+ constexpr SizedArray() = default;
+ SizedArray &operator=(const SizedArray &) = default;
+ SizedArray &operator=(SizedArray &&) = default;
+
+ reference at(size_t i) {
+ check_index(i);
+ return array_.at(i);
+ }
+ const_reference at(size_t i) const {
+ check_index(i);
+ return array_.at(i);
+ }
+
+ reference operator[](size_t i) { return array_[i]; }
+ const_reference operator[](size_t i) const { return array_[i]; }
+
+ reference front() { return array_.front(); }
+ const_reference front() const { return array_.front(); }
+
+ reference back() { return array_[size_ - 1]; }
+ const_reference back() const { return array_[size_ - 1]; }
+
+ T *data() { return array_.data(); }
+ const T *data() const { return array_.data(); }
+
+ iterator begin() { return array_.begin(); }
+ const_iterator begin() const { return array_.begin(); }
+ const_iterator cbegin() const { return array_.cbegin(); }
+
+ iterator end() { return array_.begin() + size_; }
+ const_iterator end() const { return array_.begin() + size_; }
+ const_iterator cend() const { return array_.cbegin() + size_; }
+
+ reverse_iterator rbegin() { return array_.rend() - size_; }
+ const_reverse_iterator rbegin() const { return array_.rend() - size_; }
+ const_reverse_iterator crbegin() const { return array_.crend() - size_; }
+
+ reverse_iterator rend() { return array_.rend(); }
+ const_reverse_iterator rend() const { return array_.rend(); }
+ const_reverse_iterator crend() const { return array_.crend(); }
+
+ bool empty() const { return size_ == 0; }
+ bool full() const { return size() == max_size(); }
+
+ size_t size() const { return size_; }
+ constexpr size_t max_size() const { return array_.max_size(); }
+
+ void push_back(const T &t) {
+ array_.at(size_) = t;
+ ++size_;
+ }
+ void push_back(T &&t) {
+ array_.at(size_) = std::move(t);
+ ++size_;
+ }
+
+ void pop_back() {
+ if (empty()) {
+ __builtin_trap();
+ }
+ --size_;
+ }
+
+ private:
+ void check_index(size_t i) const {
+ if (i >= size_) {
+ __builtin_trap();
+ }
+ }
+
+ array array_;
+ size_t size_ = 0;
+};
+
+} // namespace aos
+
+#endif // AOS_CONTAINERS_SIZED_ARRAY_H_
diff --git a/aos/containers/sized_array_test.cc b/aos/containers/sized_array_test.cc
new file mode 100644
index 0000000..04a8e41
--- /dev/null
+++ b/aos/containers/sized_array_test.cc
@@ -0,0 +1,139 @@
+#include "aos/containers/sized_array.h"
+
+#include "gtest/gtest.h"
+
+namespace aos {
+namespace testing {
+
+// Tests the various ways of accessing elements.
+TEST(SizedArrayTest, ElementAccess) {
+ SizedArray<int, 5> a;
+ a.push_back(9);
+ a.push_back(7);
+ a.push_back(1);
+ EXPECT_EQ(9, a[0]);
+ EXPECT_EQ(7, a[1]);
+ EXPECT_EQ(1, a[2]);
+ EXPECT_EQ(9, a.data()[0]);
+ EXPECT_EQ(7, a.data()[1]);
+ EXPECT_EQ(1, a.data()[2]);
+ EXPECT_EQ(9, a.at(0));
+ EXPECT_EQ(7, a.at(1));
+ EXPECT_EQ(1, a.at(2));
+ EXPECT_EQ(9, a.front());
+ EXPECT_EQ(1, a.back());
+
+ a.pop_back();
+ EXPECT_EQ(9, a.front());
+ EXPECT_EQ(7, a.back());
+}
+
+// Tests the accessors that don't access data.
+TEST(SizedArrayTest, Accessors) {
+ SizedArray<int, 5> a;
+ EXPECT_TRUE(a.empty());
+ EXPECT_FALSE(a.full());
+ EXPECT_EQ(0u, a.size());
+ EXPECT_EQ(5u, a.max_size());
+
+ a.push_back(9);
+ EXPECT_FALSE(a.empty());
+ EXPECT_FALSE(a.full());
+ EXPECT_EQ(1u, a.size());
+ EXPECT_EQ(5u, a.max_size());
+
+ a.push_back(9);
+ EXPECT_FALSE(a.empty());
+ EXPECT_FALSE(a.full());
+ EXPECT_EQ(2u, a.size());
+ EXPECT_EQ(5u, a.max_size());
+
+ a.push_back(9);
+ EXPECT_FALSE(a.empty());
+ EXPECT_FALSE(a.full());
+ EXPECT_EQ(3u, a.size());
+ EXPECT_EQ(5u, a.max_size());
+
+ a.push_back(9);
+ EXPECT_FALSE(a.empty());
+ EXPECT_FALSE(a.full());
+ EXPECT_EQ(4u, a.size());
+ EXPECT_EQ(5u, a.max_size());
+
+ a.push_back(9);
+ EXPECT_FALSE(a.empty());
+ EXPECT_TRUE(a.full());
+ EXPECT_EQ(5u, a.size());
+ EXPECT_EQ(5u, a.max_size());
+}
+
+// Tests the various kinds of iterator.
+TEST(SizedArrayTest, Iterators) {
+ SizedArray<int, 5> a;
+ EXPECT_EQ(a.begin(), a.end());
+ EXPECT_EQ(a.cbegin(), a.cend());
+ EXPECT_EQ(a.rbegin(), a.rend());
+ EXPECT_EQ(a.crbegin(), a.crend());
+ a.push_back(9);
+ a.push_back(7);
+ a.push_back(1);
+
+ {
+ auto iterator = a.begin();
+ ASSERT_NE(iterator, a.end());
+ EXPECT_EQ(9, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.end());
+ EXPECT_EQ(7, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.end());
+ EXPECT_EQ(1, *iterator);
+ ++iterator;
+ EXPECT_EQ(iterator, a.end());
+ }
+
+ {
+ auto iterator = a.cbegin();
+ ASSERT_NE(iterator, a.cend());
+ EXPECT_EQ(9, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.cend());
+ EXPECT_EQ(7, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.cend());
+ EXPECT_EQ(1, *iterator);
+ ++iterator;
+ EXPECT_EQ(iterator, a.cend());
+ }
+
+ {
+ auto iterator = a.rbegin();
+ ASSERT_NE(iterator, a.rend());
+ EXPECT_EQ(1, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.rend());
+ EXPECT_EQ(7, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.rend());
+ EXPECT_EQ(9, *iterator);
+ ++iterator;
+ EXPECT_EQ(iterator, a.rend());
+ }
+
+ {
+ auto iterator = a.crbegin();
+ ASSERT_NE(iterator, a.crend());
+ EXPECT_EQ(1, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.crend());
+ EXPECT_EQ(7, *iterator);
+ ++iterator;
+ ASSERT_NE(iterator, a.crend());
+ EXPECT_EQ(9, *iterator);
+ ++iterator;
+ EXPECT_EQ(iterator, a.crend());
+ }
+}
+
+} // namespace testing
+} // namespace aos