| /* |
| * Copyright (C) 2016 The Android Open Source Project |
| * |
| * 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 "chre/util/array_queue.h" |
| #include "gtest/gtest.h" |
| |
| #include <algorithm> |
| #include <type_traits> |
| #include <vector> |
| |
| using chre::ArrayQueue; |
| using chre::ArrayQueueExt; |
| |
| namespace { |
| constexpr int kMaxTestCapacity = 10; |
| int destructor_count[kMaxTestCapacity]; |
| int constructor_count; |
| int total_destructor_count; |
| |
| class FakeElement { |
| public: |
| FakeElement() { |
| constructor_count++; |
| }; |
| FakeElement(int i) { |
| val_ = i; |
| constructor_count++; |
| }; |
| ~FakeElement() { |
| total_destructor_count++; |
| if (val_ >= 0 && val_ < kMaxTestCapacity) { |
| destructor_count[val_]++; |
| } |
| }; |
| void setValue(int i) { |
| val_ = i; |
| } |
| |
| private: |
| int val_ = kMaxTestCapacity - 1; |
| }; |
| } // namespace |
| |
| TEST(ArrayQueueTest, IsEmptyInitially) { |
| ArrayQueue<int, 4> q; |
| EXPECT_TRUE(q.empty()); |
| EXPECT_EQ(0, q.size()); |
| } |
| |
| TEST(ArrayQueueTest, SimplePushPop) { |
| ArrayQueue<int, 3> q; |
| EXPECT_TRUE(q.push(1)); |
| EXPECT_TRUE(q.push(2)); |
| q.pop(); |
| EXPECT_TRUE(q.push(3)); |
| } |
| |
| TEST(ArrayQueueTest, SimplePushPopBackPush) { |
| ArrayQueue<int, 3> q; |
| EXPECT_TRUE(q.push(0)); |
| EXPECT_TRUE(q.push(1)); |
| EXPECT_TRUE(q.push(2)); |
| q.pop_back(); |
| EXPECT_EQ(2, q.size()); |
| EXPECT_EQ(0, q[0]); |
| EXPECT_EQ(1, q[1]); |
| |
| EXPECT_TRUE(q.push(3)); |
| EXPECT_EQ(3, q.size()); |
| EXPECT_EQ(0, q[0]); |
| EXPECT_EQ(1, q[1]); |
| EXPECT_EQ(3, q[2]); |
| |
| q.pop_back(); |
| q.pop_back(); |
| q.pop_back(); |
| |
| EXPECT_EQ(0, q.size()); |
| EXPECT_TRUE(q.push(4)); |
| EXPECT_TRUE(q.push(5)); |
| EXPECT_TRUE(q.push(6)); |
| EXPECT_EQ(3, q.size()); |
| EXPECT_EQ(4, q[0]); |
| EXPECT_EQ(5, q[1]); |
| EXPECT_EQ(6, q[2]); |
| |
| q.pop(); |
| |
| EXPECT_TRUE(q.push(7)); |
| EXPECT_EQ(5, q[0]); |
| EXPECT_EQ(6, q[1]); |
| EXPECT_EQ(7, q[2]); |
| } |
| |
| TEST(ArrayQueueTest, TestSize) { |
| ArrayQueue<int, 2> q; |
| q.push(1); |
| EXPECT_EQ(1, q.size()); |
| q.push(2); |
| EXPECT_EQ(2, q.size()); |
| q.pop(); |
| EXPECT_EQ(1, q.size()); |
| q.pop(); |
| } |
| |
| TEST(ArrayQueueTest, TestEmpty) { |
| ArrayQueue<int, 2> q; |
| q.push(1); |
| EXPECT_FALSE(q.empty()); |
| q.push(2); |
| EXPECT_FALSE(q.empty()); |
| q.pop(); |
| EXPECT_FALSE(q.empty()); |
| q.pop(); |
| EXPECT_TRUE(q.empty()); |
| } |
| |
| TEST(ArrayQueueTest, KickPushWhenNotFull) { |
| ArrayQueue<int, 2> q; |
| q.kick_push(1); |
| EXPECT_EQ(1, q.size()); |
| EXPECT_EQ(1, q[0]); |
| q.kick_push(2); |
| EXPECT_EQ(2, q.size()); |
| EXPECT_EQ(2, q[1]); |
| } |
| |
| TEST(ArrayQueueTest, KickPushWhenFull) { |
| ArrayQueue<int, 2> q; |
| q.kick_push(1); |
| q.push(2); |
| EXPECT_EQ(2, q.size()); |
| q.kick_push(3); |
| EXPECT_EQ(2, q.size()); |
| EXPECT_EQ(2, q[0]); |
| EXPECT_EQ(3, q[1]); |
| } |
| |
| TEST(ArrayQueueTest, PopWhenEmpty) { |
| ArrayQueue<int, 4> q; |
| q.pop(); |
| EXPECT_EQ(0, q.size()); |
| } |
| |
| TEST(ArrayQueueTest, PopBackWhenEmpty) { |
| ArrayQueue<int, 4> q; |
| q.pop_back(); |
| EXPECT_EQ(0, q.size()); |
| } |
| |
| TEST(ArrayQueueTest, PushWhenFull) { |
| ArrayQueue<int, 2> q; |
| q.push(1); |
| q.push(2); |
| EXPECT_FALSE(q.push(3)); |
| } |
| |
| TEST(ArrayQueueDeathTest, FrontWhenEmpty) { |
| ArrayQueue<int, 4> q; |
| EXPECT_DEATH(q.front(), ""); |
| } |
| |
| TEST(ArrayQueueDeathTest, BackWhenEmpty) { |
| ArrayQueue<int, 4> q; |
| EXPECT_DEATH(q.back(), ""); |
| } |
| |
| TEST(ArrayQueueTest, TestFront) { |
| ArrayQueue<int, 3> q; |
| q.push(1); |
| EXPECT_EQ(1, q.front()); |
| q.pop(); |
| q.push(2); |
| EXPECT_EQ(2, q.front()); |
| q.push(3); |
| EXPECT_EQ(2, q.front()); |
| } |
| |
| TEST(ArrayQueueTest, TestBack) { |
| ArrayQueue<int, 3> q; |
| q.push(1); |
| EXPECT_EQ(1, q.back()); |
| q.pop(); |
| q.push(2); |
| EXPECT_EQ(2, q.back()); |
| q.push(3); |
| EXPECT_EQ(3, q.back()); |
| } |
| |
| TEST(ArrayQueueDeathTest, InvalidSubscript) { |
| ArrayQueue<int, 2> q; |
| EXPECT_DEATH(q[0], ""); |
| } |
| |
| TEST(ArrayQueueTest, Subscript) { |
| ArrayQueue<int, 2> q; |
| q.push(1); |
| q.push(2); |
| EXPECT_EQ(1, q[0]); |
| EXPECT_EQ(2, q[1]); |
| q.pop(); |
| EXPECT_EQ(2, q[0]); |
| } |
| |
| TEST(ArrayQueueTest, RemoveWithInvalidIndex) { |
| ArrayQueue<int, 3> q; |
| EXPECT_FALSE(q.remove(0)); |
| } |
| |
| TEST(ArrayQueueTest, RemoveWithIndex) { |
| ArrayQueue<int, 3> q; |
| q.push(1); |
| q.push(2); |
| q.remove(0); |
| EXPECT_EQ(2, q.front()); |
| EXPECT_EQ(1, q.size()); |
| q.push(3); |
| q.remove(1); |
| EXPECT_EQ(2, q.front()); |
| EXPECT_EQ(1, q.size()); |
| } |
| |
| TEST(ArrayQueueTest, DestructorCalledOnPop) { |
| for (size_t i = 0; i < kMaxTestCapacity; ++i) { |
| destructor_count[i] = 0; |
| } |
| |
| ArrayQueue<FakeElement, 3> q; |
| FakeElement e; |
| q.push(e); |
| q.push(e); |
| |
| q.front().setValue(0); |
| q.pop(); |
| EXPECT_EQ(1, destructor_count[0]); |
| |
| q.front().setValue(1); |
| q.pop(); |
| EXPECT_EQ(1, destructor_count[1]); |
| } |
| |
| TEST(ArrayQueueTest, ElementsDestructedWhenQueueDestructed) { |
| for (size_t i = 0; i < kMaxTestCapacity; ++i) { |
| destructor_count[i] = 0; |
| } |
| |
| // Put q and e in the scope so their destructor will be called going |
| // out of scope. |
| { |
| ArrayQueue<FakeElement, 4> q; |
| FakeElement e; |
| |
| for (size_t i = 0; i < 3; ++i) { |
| q.push(e); |
| q[i].setValue(i); |
| } |
| } |
| |
| // q should now be destroyed - check destructor count. |
| for (size_t i = 0; i < 3; ++i) { |
| EXPECT_EQ(1, destructor_count[i]); |
| } |
| EXPECT_EQ(0, destructor_count[3]); |
| EXPECT_EQ(1, destructor_count[kMaxTestCapacity - 1]); |
| } |
| |
| TEST(ArrayQueueTest, EmplaceTest) { |
| constructor_count = 0; |
| ArrayQueue<FakeElement, 2> q; |
| |
| EXPECT_TRUE(q.emplace(0)); |
| EXPECT_EQ(1, constructor_count); |
| EXPECT_EQ(1, q.size()); |
| |
| EXPECT_TRUE(q.emplace(1)); |
| EXPECT_EQ(2, constructor_count); |
| EXPECT_EQ(2, q.size()); |
| |
| EXPECT_FALSE(q.emplace(2)); |
| EXPECT_EQ(2, constructor_count); |
| EXPECT_EQ(2, q.size()); |
| } |
| |
| TEST(ArrayQueueTest, EmptyQueueIterator) { |
| ArrayQueue<int, 4> q; |
| |
| ArrayQueue<int, 4>::iterator it = q.begin(); |
| EXPECT_TRUE(it == q.end()); |
| EXPECT_FALSE(it != q.end()); |
| } |
| |
| TEST(ArrayQueueTest, SimpleIterator) { |
| ArrayQueue<int, 4> q; |
| for (size_t i = 0; i < 3; ++i) { |
| q.push(i); |
| } |
| EXPECT_NE(q.begin(), q.end()); |
| |
| size_t index = 0; |
| for (ArrayQueue<int, 4>::iterator it = q.begin(); it != q.end(); ++it) { |
| EXPECT_EQ(q[index++], *it); |
| } |
| index = 0; |
| for (ArrayQueue<int, 4>::iterator it = q.begin(); it != q.end(); it++) { |
| EXPECT_EQ(q[index++], *it); |
| } |
| |
| index = 0; |
| ArrayQueue<int, 4>::iterator it = q.begin(); |
| while (it != q.end()) { |
| EXPECT_EQ(q[index++], *it++); |
| } |
| |
| for (size_t i = 0; i < 3; ++i) { |
| q.pop(); |
| q.push(i + 3); |
| } |
| |
| index = 0; |
| it = q.begin(); |
| while (it != q.end()) { |
| EXPECT_EQ(q[index++], *it++); |
| } |
| |
| // Iterator concept checks: default constructible, copy assignable, copy |
| // constructible |
| ArrayQueue<int, 4>::iterator it2; |
| it2 = it; |
| EXPECT_EQ(it, it2); |
| |
| ArrayQueue<int, 4>::iterator it3(it); |
| EXPECT_EQ(it, it3); |
| } |
| |
| TEST(ArrayQueueTest, IteratorSwap) { |
| ArrayQueue<int, 2> q; |
| q.push(1); |
| q.push(2); |
| |
| auto it1 = q.begin(), it2 = q.end(); |
| std::swap(it1, it2); |
| EXPECT_EQ(it1, q.end()); |
| EXPECT_EQ(it2, q.begin()); |
| } |
| |
| TEST(ArrayQueueTest, IteratorAndPush) { |
| ArrayQueue<int, 4> q; |
| for (size_t i = 0; i < 2; ++i) { |
| q.push(i); |
| } |
| |
| ArrayQueue<int, 4>::iterator it_b = q.begin(); |
| ArrayQueue<int, 4>::iterator it_e = q.end(); |
| q.push(3); |
| |
| size_t index = 0; |
| while (it_b != it_e) { |
| EXPECT_EQ(q[index++], *it_b++); |
| } |
| } |
| |
| TEST(ArrayQueueTest, IteratorAndPop) { |
| ArrayQueue<int, 4> q; |
| for (size_t i = 0; i < 3; ++i) { |
| q.push(i); |
| } |
| |
| ArrayQueue<int, 4>::iterator it_b = q.begin(); |
| q.pop(); |
| it_b++; |
| |
| for (size_t i = 0; i < 2; ++i) { |
| EXPECT_EQ(q[i], *it_b++); |
| } |
| } |
| |
| TEST(ArrayQueueTest, IteratorAndRemove) { |
| ArrayQueue<int, 4> q; |
| for (size_t i = 0; i < 2; ++i) { |
| q.push(i); |
| } |
| |
| ArrayQueue<int, 4>::iterator it_b = q.begin(); |
| q.remove(1); |
| |
| EXPECT_EQ(q[0], *it_b); |
| } |
| |
| TEST(ArrayQueueTest, IteratorAndEmplace) { |
| ArrayQueue<int, 4> q; |
| for (size_t i = 0; i < 2; ++i) { |
| q.push(i); |
| } |
| |
| ArrayQueue<int, 4>::iterator it_b = q.begin(); |
| ArrayQueue<int, 4>::iterator it_e = q.end(); |
| q.emplace(3); |
| |
| size_t index = 0; |
| while (it_b != it_e) { |
| EXPECT_EQ(q[index++], *it_b++); |
| } |
| } |
| |
| TEST(ArrayQueueTest, SimpleConstIterator) { |
| ArrayQueue<int, 4> q; |
| for (size_t i = 0; i < 3; ++i) { |
| q.push(i); |
| } |
| |
| size_t index = 0; |
| for (ArrayQueue<int, 4>::const_iterator cit = q.cbegin(); cit != q.cend(); |
| ++cit) { |
| EXPECT_EQ(q[index++], *cit); |
| } |
| |
| index = 0; |
| ArrayQueue<int, 4>::const_iterator cit = q.cbegin(); |
| while (cit != q.cend()) { |
| EXPECT_EQ(q[index++], *cit++); |
| } |
| |
| for (size_t i = 0; i < 3; ++i) { |
| q.pop(); |
| q.push(i + 3); |
| } |
| |
| index = 0; |
| cit = q.cbegin(); |
| while (cit != q.cend()) { |
| EXPECT_EQ(q[index++], *cit++); |
| } |
| } |
| |
| TEST(ArrayQueueTest, Full) { |
| ArrayQueue<size_t, 4> q; |
| for (size_t i = 0; i < 4; i++) { |
| EXPECT_FALSE(q.full()); |
| q.push(i); |
| } |
| |
| EXPECT_TRUE(q.full()); |
| } |
| |
| TEST(ArrayQueueTest, ArrayCopy) { |
| constexpr size_t kSize = 8; |
| ArrayQueue<size_t, kSize> q; |
| std::vector<size_t> v; |
| v.resize(kSize); |
| |
| for (size_t i = 0; i < kSize; i++) { |
| q.push(i); |
| |
| v.assign(kSize, 0xdeadbeef); |
| std::copy(q.begin(), q.end(), v.begin()); |
| |
| for (size_t j = 0; j < i; j++) { |
| EXPECT_EQ(q[j], v[j]); |
| EXPECT_EQ(*std::next(q.begin(), j), v[j]); |
| } |
| } |
| } |
| |
| TEST(ArrayQueueTest, IteratorTraits) { |
| ArrayQueue<int, 2> q; |
| q.push(1234); |
| q.push(5678); |
| |
| using traits = std::iterator_traits<decltype(q)::iterator>; |
| typename traits::difference_type diff = std::distance(q.begin(), q.end()); |
| EXPECT_EQ(diff, q.size()); |
| |
| typename traits::value_type v = *q.begin(); |
| EXPECT_EQ(v, q[0]); |
| |
| typename traits::reference r = *q.begin(); |
| r = 999; |
| EXPECT_EQ(r, q[0]); |
| |
| typename traits::pointer p = &r; |
| EXPECT_EQ(*p, q[0]); |
| |
| // Note: if the implementation is upgraded to another category like random |
| // access, then this static assert should be updated. It exists primarily to |
| // confirm that we are declaring an iterator_category |
| static_assert( |
| std::is_same<traits::iterator_category, std::forward_iterator_tag>::value, |
| "ArrayQueueIterator should be a forward iterator"); |
| } |
| |
| TEST(ArrayQueueTest, ArrayClear) { |
| ArrayQueue<size_t, 4> q; |
| |
| q.clear(); |
| EXPECT_TRUE(q.empty()); |
| |
| for (size_t i = 0; i < 4; i++) { |
| q.push(i); |
| } |
| |
| q.clear(); |
| EXPECT_TRUE(q.empty()); |
| |
| // Make sure that insertion/access still work after a clear. |
| for (size_t i = 0; i < 4; i++) { |
| q.push(i); |
| } |
| for (size_t i = 0; i < 4; i++) { |
| EXPECT_EQ(q[i], i); |
| } |
| } |
| |
| TEST(ArrayQueueTest, ElementsDestructedArrayClear) { |
| for (size_t i = 0; i < kMaxTestCapacity; ++i) { |
| destructor_count[i] = 0; |
| } |
| total_destructor_count = 0; |
| |
| ArrayQueue<FakeElement, 4> q; |
| for (size_t i = 0; i < 3; ++i) { |
| q.emplace(i); |
| } |
| |
| q.clear(); |
| |
| for (size_t i = 0; i < 3; ++i) { |
| EXPECT_EQ(1, destructor_count[i]); |
| } |
| EXPECT_EQ(3, total_destructor_count); |
| } |
| |
| TEST(ArrayQueueExtTest, BasicTest) { |
| constexpr size_t kNumElements = 32; |
| int32_t array[kNumElements]; |
| ArrayQueueExt<int32_t> q(array, kNumElements); |
| |
| ASSERT_EQ(q.data(), array); |
| EXPECT_EQ(q.capacity(), kNumElements); |
| |
| for (int i = 0; i < kNumElements; i++) { |
| q.push(i); |
| } |
| |
| for (int i = 0; i < kNumElements; i++) { |
| EXPECT_EQ(array[i], q[i]); |
| } |
| } |