1 files changed, 163 insertions, 0 deletions
diff --git a/src/utils/unbounded_queue_test.cc b/src/utils/unbounded_queue_test.cc
new file mode 100644
index 0000000..b107ad0
--- /dev/null
+++ b/src/utils/unbounded_queue_test.cc
@@ -0,0 +1,163 @@
+// Copyright 2021 The libgav1 Authors
+//
+// 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 "src/utils/unbounded_queue.h"
+
+#include <new>
+#include <utility>
+
+#include "gtest/gtest.h"
+
+namespace libgav1 {
+namespace {
+
+class Integer {
+ public:
+  explicit Integer(int value) : value_(new (std::nothrow) int{value}) {}
+
+  // Move only.
+  Integer(Integer&& other) : value_(other.value_) { other.value_ = nullptr; }
+  Integer& operator=(Integer&& other) {
+    if (this != &other) {
+      delete value_;
+      value_ = other.value_;
+      other.value_ = nullptr;
+    }
+    return *this;
+  }
+
+  ~Integer() { delete value_; }
+
+  int value() const { return *value_; }
+
+ private:
+  int* value_;
+};
+
+TEST(UnboundedQueueTest, Basic) {
+  UnboundedQueue<int> queue;
+  ASSERT_TRUE(queue.Init());
+  EXPECT_TRUE(queue.Empty());
+
+  for (int i = 0; i < 8; ++i) {
+    EXPECT_TRUE(queue.GrowIfNeeded());
+    queue.Push(i);
+    EXPECT_FALSE(queue.Empty());
+  }
+
+  for (int i = 0; i < 8; ++i) {
+    EXPECT_FALSE(queue.Empty());
+    EXPECT_EQ(queue.Front(), i);
+    queue.Pop();
+  }
+  EXPECT_TRUE(queue.Empty());
+}
+
+TEST(UnboundedQueueTest, WrapAround) {
+  UnboundedQueue<int> queue;
+  ASSERT_TRUE(queue.Init());
+  EXPECT_TRUE(queue.Empty());
+
+  for (int i = 0; i < 1000; ++i) {
+    EXPECT_TRUE(queue.GrowIfNeeded());
+    queue.Push(i);
+    EXPECT_FALSE(queue.Empty());
+    EXPECT_EQ(queue.Front(), i);
+    queue.Pop();
+    EXPECT_TRUE(queue.Empty());
+  }
+}
+
+TEST(UnboundedQueueTest, EmptyBeforeInit) {
+  UnboundedQueue<int> queue;
+  EXPECT_TRUE(queue.Empty());
+}
+
+TEST(UnboundedQueueTest, LotsOfElements) {
+  UnboundedQueue<Integer> queue;
+  ASSERT_TRUE(queue.Init());
+  EXPECT_TRUE(queue.Empty());
+
+  for (int i = 0; i < 10000; ++i) {
+    Integer integer(i);
+    EXPECT_EQ(integer.value(), i);
+    EXPECT_TRUE(queue.GrowIfNeeded());
+    queue.Push(std::move(integer));
+    EXPECT_FALSE(queue.Empty());
+  }
+
+  for (int i = 0; i < 5000; ++i) {
+    EXPECT_FALSE(queue.Empty());
+    const Integer& integer = queue.Front();
+    EXPECT_EQ(integer.value(), i);
+    queue.Pop();
+  }
+  // Leave some elements in the queue to test destroying a nonempty queue.
+  EXPECT_FALSE(queue.Empty());
+}
+
+// Copy constructor and assignment are deleted, but move constructor and
+// assignment are OK.
+TEST(UnboundedQueueTest, Move) {
+  UnboundedQueue<int> ints1;
+  ASSERT_TRUE(ints1.Init());
+  EXPECT_TRUE(ints1.GrowIfNeeded());
+  ints1.Push(2);
+  EXPECT_TRUE(ints1.GrowIfNeeded());
+  ints1.Push(3);
+  EXPECT_TRUE(ints1.GrowIfNeeded());
+  ints1.Push(5);
+  EXPECT_TRUE(ints1.GrowIfNeeded());
+  ints1.Push(7);
+
+  // Move constructor.
+  UnboundedQueue<int> ints2(std::move(ints1));
+  EXPECT_EQ(ints2.Front(), 2);
+  ints2.Pop();
+  EXPECT_EQ(ints2.Front(), 3);
+  ints2.Pop();
+  EXPECT_EQ(ints2.Front(), 5);
+  ints2.Pop();
+  EXPECT_EQ(ints2.Front(), 7);
+  ints2.Pop();
+  EXPECT_TRUE(ints2.Empty());
+
+  EXPECT_TRUE(ints2.GrowIfNeeded());
+  ints2.Push(11);
+  EXPECT_TRUE(ints2.GrowIfNeeded());
+  ints2.Push(13);
+  EXPECT_TRUE(ints2.GrowIfNeeded());
+  ints2.Push(17);
+  EXPECT_TRUE(ints2.GrowIfNeeded());
+  ints2.Push(19);
+
+  // Move assignment.
+  UnboundedQueue<int> ints3;
+  ASSERT_TRUE(ints3.Init());
+  EXPECT_TRUE(ints3.GrowIfNeeded());
+  ints3.Push(23);
+  ints3 = std::move(ints2);
+  EXPECT_EQ(ints3.Front(), 11);
+  ints3.Pop();
+  EXPECT_EQ(ints3.Front(), 13);
+  ints3.Pop();
+  EXPECT_EQ(ints3.Front(), 17);
+  ints3.Pop();
+  EXPECT_EQ(ints3.Front(), 19);
+  ints3.Pop();
+  EXPECT_TRUE(ints3.Empty());
+}
+
+}  // namespace
+}  // namespace libgav1