summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/circular-array.h41
-rw-r--r--src/test-circular-array.cc287
2 files changed, 317 insertions, 11 deletions
diff --git a/src/circular-array.h b/src/circular-array.h
index 265410e8..c14721fd 100644
--- a/src/circular-array.h
+++ b/src/circular-array.h
@@ -25,8 +25,6 @@
namespace wabt {
// TODO(karlschimpf) Complete the API
-// TODO(karlschimpf) Apply constructors/destructors on base type T
-// as collection size changes (if not POD).
// Note: Capacity must be a power of 2.
template<class T, size_t kCapacity>
class CircularArray {
@@ -37,11 +35,21 @@ class CircularArray {
typedef size_t size_type;
typedef ptrdiff_t difference_type;
- CircularArray() : size_(0), front_(0), mask_(kCapacity - 1) {
+ CircularArray() {
static_assert(kCapacity && ((kCapacity & (kCapacity - 1)) == 0),
"Capacity must be a power of 2.");
}
+ CircularArray(const CircularArray&) = default;
+ CircularArray& operator =(const CircularArray&) = default;
+
+ CircularArray(CircularArray&&) = default;
+ CircularArray& operator =(CircularArray&&) = default;
+
+ ~CircularArray() {
+ clear();
+ }
+
reference at(size_type index) {
assert(index < size_);
return (*this)[index];
@@ -82,33 +90,44 @@ class CircularArray {
void pop_back() {
assert(size_ > 0);
+ SetElement(back());
--size_;
}
void pop_front() {
assert(size_ > 0);
- front_ = (front_ + 1) & mask_;
+ SetElement(front());
+ front_ = (front_ + 1) & kMask;
--size_;
}
void push_back(const value_type& value) {
assert(size_ < kCapacity);
- contents_[position(size_++)] = value;
+ SetElement(at(size_++), value);
}
size_type size() const { return size_; }
void clear() {
- size_ = 0;
+ while (!empty()) {
+ pop_back();
+ }
}
private:
- std::array<T, kCapacity> contents_;
- size_type size_;
- size_type front_;
- size_type mask_;
+ static const size_type kMask = kCapacity - 1;
- size_t position(size_t index) const { return (front_ + index) & mask_; }
+ size_t position(size_t index) const { return (front_ + index) & kMask; }
+
+ template <typename... Args>
+ void SetElement(reference element, Args&&... args) {
+ element.~T();
+ new (&element) T(std::forward<Args>(args)...);
+ }
+
+ std::array<T, kCapacity> contents_;
+ size_type size_ = 0;
+ size_type front_ = 0;
};
}
diff --git a/src/test-circular-array.cc b/src/test-circular-array.cc
new file mode 100644
index 00000000..50c465f4
--- /dev/null
+++ b/src/test-circular-array.cc
@@ -0,0 +1,287 @@
+/*
+ * Copyright 2017 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "gtest/gtest.h"
+
+#include <memory>
+
+#include "src/circular-array.h"
+
+using namespace wabt;
+
+namespace {
+
+struct TestObject {
+ static int construct_count;
+ static int destruct_count;
+
+ TestObject(int data = 0, int data2 = 0) : data(data), data2(data2) {
+ construct_count++;
+ }
+
+ TestObject(const TestObject& other) {
+ *this = other;
+ construct_count++;
+ }
+
+ TestObject& operator=(const TestObject& other) {
+ data = other.data;
+ data2 = other.data2;
+ return *this;
+ }
+
+ TestObject(TestObject&& other) {
+ *this = std::move(other);
+ }
+
+ TestObject& operator=(TestObject&& other) {
+ data = other.data;
+ data2 = other.data2;
+ other.moved = true;
+ return *this;
+ }
+
+ ~TestObject() {
+ if (!moved) {
+ destruct_count++;
+ }
+ }
+
+ int data = 0;
+ int data2 = 0;
+ bool moved = false;
+};
+
+// static
+int TestObject::construct_count = 0;
+// static
+int TestObject::destruct_count = 0;
+
+class CircularArrayTest : public ::testing::Test {
+ protected:
+ virtual void SetUp() {
+ // Reset to 0 even if the previous test leaked objects to keep the tests
+ // independent.
+ TestObject::construct_count = 0;
+ TestObject::destruct_count = 0;
+ }
+
+ virtual void TearDown() {
+ ASSERT_EQ(0, TestObject::construct_count - TestObject::destruct_count)
+ << "construct count: " << TestObject::construct_count
+ << ", destruct_count: " << TestObject::destruct_count;
+ }
+
+ template <size_t N>
+ void AssertCircularArrayEq(const CircularArray<TestObject, N>& ca,
+ const std::vector<int>& expected) {
+ if (expected.empty()) {
+ ASSERT_EQ(0U, ca.size());
+ ASSERT_TRUE(ca.empty());
+ } else {
+ ASSERT_EQ(expected.size(), ca.size());
+ ASSERT_FALSE(ca.empty());
+
+ ASSERT_EQ(expected.front(), ca.front().data);
+ ASSERT_EQ(expected.back(), ca.back().data);
+
+ for (size_t i = 0; i < ca.size(); ++i) {
+ ASSERT_EQ(expected[i], ca.at(i).data);
+ ASSERT_EQ(expected[i], ca[i].data);
+ }
+ }
+ }
+};
+
+} // end anonymous namespace
+
+
+// Basic API tests
+
+TEST_F(CircularArrayTest, default_constructor) {
+ CircularArray<TestObject, 2> ca;
+}
+
+TEST_F(CircularArrayTest, at) {
+ CircularArray<TestObject, 2> ca;
+ ca.push_back(TestObject(1));
+ ca.push_back(TestObject(2));
+
+ ASSERT_EQ(1, ca.at(0).data);
+ ASSERT_EQ(2, ca.at(1).data);
+}
+
+TEST_F(CircularArrayTest, const_at) {
+ CircularArray<TestObject, 2> ca;
+ const auto& cca = ca;
+
+ ca.push_back(TestObject(1));
+ ca.push_back(TestObject(2));
+
+ ASSERT_EQ(1, cca.at(0).data);
+ ASSERT_EQ(2, cca.at(1).data);
+}
+
+TEST_F(CircularArrayTest, operator_brackets) {
+ CircularArray<TestObject, 2> ca;
+ ca.push_back(TestObject(1));
+ ca.push_back(TestObject(2));
+
+ ASSERT_EQ(1, ca[0].data);
+ ASSERT_EQ(2, ca[1].data);
+}
+
+TEST_F(CircularArrayTest, const_operator_brackets) {
+ CircularArray<TestObject, 2> ca;
+ const auto& cca = ca;
+
+ ca.push_back(TestObject(1));
+ ca.push_back(TestObject(2));
+
+ ASSERT_EQ(1, cca[0].data);
+ ASSERT_EQ(2, cca[1].data);
+}
+
+TEST_F(CircularArrayTest, back) {
+ CircularArray<TestObject, 2> ca;
+
+ ca.push_back(TestObject(1));
+ ASSERT_EQ(1, ca.back().data);
+
+ ca.push_back(TestObject(2));
+ ASSERT_EQ(2, ca.back().data);
+}
+
+TEST_F(CircularArrayTest, const_back) {
+ CircularArray<TestObject, 2> ca;
+ const auto& cca = ca;
+
+ ca.push_back(TestObject(1));
+ ASSERT_EQ(1, cca.back().data);
+
+ ca.push_back(TestObject(2));
+ ASSERT_EQ(2, cca.back().data);
+}
+
+TEST_F(CircularArrayTest, empty) {
+ CircularArray<TestObject, 2> ca;
+
+ ASSERT_TRUE(ca.empty());
+
+ ca.push_back(TestObject(1));
+ ASSERT_FALSE(ca.empty());
+
+ ca.push_back(TestObject(2));
+ ASSERT_FALSE(ca.empty());
+
+ ca.pop_back();
+ ASSERT_FALSE(ca.empty());
+
+ ca.pop_back();
+ ASSERT_TRUE(ca.empty());
+}
+
+TEST_F(CircularArrayTest, front) {
+ CircularArray<TestObject, 2> ca;
+
+ ca.push_back(TestObject(1));
+ ASSERT_EQ(1, ca.front().data);
+
+ ca.push_back(TestObject(2));
+ ASSERT_EQ(1, ca.front().data);
+}
+
+TEST_F(CircularArrayTest, const_front) {
+ CircularArray<TestObject, 2> ca;
+ const auto& cca = ca;
+
+ ca.push_back(TestObject(1));
+ ASSERT_EQ(1, cca.front().data);
+
+ ca.push_back(TestObject(2));
+ ASSERT_EQ(1, cca.front().data);
+}
+
+TEST_F(CircularArrayTest, size) {
+ CircularArray<TestObject, 2> ca;
+
+ ASSERT_EQ(0U, ca.size());
+
+ ca.push_back(TestObject(1));
+ ASSERT_EQ(1U, ca.size());
+
+ ca.push_back(TestObject(2));
+ ASSERT_EQ(2U, ca.size());
+
+ ca.pop_back();
+ ASSERT_EQ(1U, ca.size());
+
+ ca.pop_back();
+ ASSERT_EQ(0U, ca.size());
+}
+
+TEST_F(CircularArrayTest, clear) {
+ CircularArray<TestObject, 2> ca;
+
+ ca.push_back(TestObject(1));
+ ca.push_back(TestObject(2));
+ ASSERT_EQ(2U, ca.size());
+
+ ca.clear();
+ ASSERT_EQ(0U, ca.size());
+}
+
+// More involved tests
+
+TEST_F(CircularArrayTest, circular) {
+ CircularArray<TestObject, 4> ca;
+
+ ca.push_back(TestObject(1));
+ AssertCircularArrayEq(ca, {1});
+
+ ca.push_back(TestObject(2));
+ AssertCircularArrayEq(ca, {1, 2});
+
+ ca.push_back(TestObject(3));
+ AssertCircularArrayEq(ca, {1, 2, 3});
+
+ ca.pop_front();
+ AssertCircularArrayEq(ca, {2, 3});
+
+ ca.push_back(TestObject(4));
+ AssertCircularArrayEq(ca, {2, 3, 4});
+
+ ca.pop_front();
+ AssertCircularArrayEq(ca, {3, 4});
+
+ ca.pop_front();
+ AssertCircularArrayEq(ca, {4});
+
+ ca.push_back(TestObject(5));
+ AssertCircularArrayEq(ca, {4, 5});
+
+ ca.push_back(TestObject(6));
+ AssertCircularArrayEq(ca, {4, 5, 6});
+
+ ca.pop_back();
+ AssertCircularArrayEq(ca, {4, 5});
+
+ ca.pop_back();
+ AssertCircularArrayEq(ca, {4});
+
+ ca.pop_front();
+ AssertCircularArrayEq(ca, {});
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-29 11:57:03 +0000