1 // Copyright 2021 The libgav1 Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "src/utils/unbounded_queue.h"
16
17 #include <new>
18 #include <utility>
19
20 #include "gtest/gtest.h"
21
22 namespace libgav1 {
23 namespace {
24
25 class Integer {
26 public:
Integer(int value)27 explicit Integer(int value) : value_(new (std::nothrow) int{value}) {}
28
29 // Move only.
Integer(Integer && other)30 Integer(Integer&& other) : value_(other.value_) { other.value_ = nullptr; }
operator =(Integer && other)31 Integer& operator=(Integer&& other) {
32 if (this != &other) {
33 delete value_;
34 value_ = other.value_;
35 other.value_ = nullptr;
36 }
37 return *this;
38 }
39
~Integer()40 ~Integer() { delete value_; }
41
value() const42 int value() const { return *value_; }
43
44 private:
45 int* value_;
46 };
47
TEST(UnboundedQueueTest,Basic)48 TEST(UnboundedQueueTest, Basic) {
49 UnboundedQueue<int> queue;
50 ASSERT_TRUE(queue.Init());
51 EXPECT_TRUE(queue.Empty());
52
53 for (int i = 0; i < 8; ++i) {
54 EXPECT_TRUE(queue.GrowIfNeeded());
55 queue.Push(i);
56 EXPECT_FALSE(queue.Empty());
57 }
58
59 for (int i = 0; i < 8; ++i) {
60 EXPECT_FALSE(queue.Empty());
61 EXPECT_EQ(queue.Front(), i);
62 queue.Pop();
63 }
64 EXPECT_TRUE(queue.Empty());
65 }
66
TEST(UnboundedQueueTest,WrapAround)67 TEST(UnboundedQueueTest, WrapAround) {
68 UnboundedQueue<int> queue;
69 ASSERT_TRUE(queue.Init());
70 EXPECT_TRUE(queue.Empty());
71
72 for (int i = 0; i < 1000; ++i) {
73 EXPECT_TRUE(queue.GrowIfNeeded());
74 queue.Push(i);
75 EXPECT_FALSE(queue.Empty());
76 EXPECT_EQ(queue.Front(), i);
77 queue.Pop();
78 EXPECT_TRUE(queue.Empty());
79 }
80 }
81
TEST(UnboundedQueueTest,EmptyBeforeInit)82 TEST(UnboundedQueueTest, EmptyBeforeInit) {
83 UnboundedQueue<int> queue;
84 EXPECT_TRUE(queue.Empty());
85 }
86
TEST(UnboundedQueueTest,LotsOfElements)87 TEST(UnboundedQueueTest, LotsOfElements) {
88 UnboundedQueue<Integer> queue;
89 ASSERT_TRUE(queue.Init());
90 EXPECT_TRUE(queue.Empty());
91
92 for (int i = 0; i < 10000; ++i) {
93 Integer integer(i);
94 EXPECT_EQ(integer.value(), i);
95 EXPECT_TRUE(queue.GrowIfNeeded());
96 queue.Push(std::move(integer));
97 EXPECT_FALSE(queue.Empty());
98 }
99
100 for (int i = 0; i < 5000; ++i) {
101 EXPECT_FALSE(queue.Empty());
102 const Integer& integer = queue.Front();
103 EXPECT_EQ(integer.value(), i);
104 queue.Pop();
105 }
106 // Leave some elements in the queue to test destroying a nonempty queue.
107 EXPECT_FALSE(queue.Empty());
108 }
109
110 // Copy constructor and assignment are deleted, but move constructor and
111 // assignment are OK.
TEST(UnboundedQueueTest,Move)112 TEST(UnboundedQueueTest, Move) {
113 UnboundedQueue<int> ints1;
114 ASSERT_TRUE(ints1.Init());
115 EXPECT_TRUE(ints1.GrowIfNeeded());
116 ints1.Push(2);
117 EXPECT_TRUE(ints1.GrowIfNeeded());
118 ints1.Push(3);
119 EXPECT_TRUE(ints1.GrowIfNeeded());
120 ints1.Push(5);
121 EXPECT_TRUE(ints1.GrowIfNeeded());
122 ints1.Push(7);
123
124 // Move constructor.
125 UnboundedQueue<int> ints2(std::move(ints1));
126 EXPECT_EQ(ints2.Front(), 2);
127 ints2.Pop();
128 EXPECT_EQ(ints2.Front(), 3);
129 ints2.Pop();
130 EXPECT_EQ(ints2.Front(), 5);
131 ints2.Pop();
132 EXPECT_EQ(ints2.Front(), 7);
133 ints2.Pop();
134 EXPECT_TRUE(ints2.Empty());
135
136 EXPECT_TRUE(ints2.GrowIfNeeded());
137 ints2.Push(11);
138 EXPECT_TRUE(ints2.GrowIfNeeded());
139 ints2.Push(13);
140 EXPECT_TRUE(ints2.GrowIfNeeded());
141 ints2.Push(17);
142 EXPECT_TRUE(ints2.GrowIfNeeded());
143 ints2.Push(19);
144
145 // Move assignment.
146 UnboundedQueue<int> ints3;
147 ASSERT_TRUE(ints3.Init());
148 EXPECT_TRUE(ints3.GrowIfNeeded());
149 ints3.Push(23);
150 ints3 = std::move(ints2);
151 EXPECT_EQ(ints3.Front(), 11);
152 ints3.Pop();
153 EXPECT_EQ(ints3.Front(), 13);
154 ints3.Pop();
155 EXPECT_EQ(ints3.Front(), 17);
156 ints3.Pop();
157 EXPECT_EQ(ints3.Front(), 19);
158 ints3.Pop();
159 EXPECT_TRUE(ints3.Empty());
160 }
161
162 } // namespace
163 } // namespace libgav1
164