blob: af1d433d62a3fc56d10a81b49e36c599655ed438 [file] [log] [blame]
// Copyright 2020 The Pigweed 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
//
// https://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 "pw_containers/intrusive_list.h"
#include <array>
#include <cstddef>
#include <cstdint>
#include "gtest/gtest.h"
#include "pw_preprocessor/util.h"
namespace pw {
namespace {
class TestItem : public IntrusiveList<TestItem>::Item {
public:
TestItem() : number_(0) {}
TestItem(int number) : number_(number) {}
int GetNumber() const { return number_; }
void SetNumber(int num) { number_ = num; }
// Add equality comparison to ensure comparisons are done by identity rather
// than equality for the remove function.
bool operator==(const TestItem& other) const {
return number_ == other.number_;
}
private:
int number_;
};
TEST(IntrusiveList, Construct_InitializerList_Empty) {
IntrusiveList<TestItem> list({});
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Construct_InitializerList_One) {
TestItem one(1);
IntrusiveList<TestItem> list({&one});
EXPECT_EQ(&one, &list.front());
}
TEST(IntrusiveList, Construct_InitializerList_Multiple) {
TestItem one(1);
TestItem two(2);
TestItem thr(3);
IntrusiveList<TestItem> list({&one, &two, &thr});
auto it = list.begin();
EXPECT_EQ(&one, &(*it++));
EXPECT_EQ(&two, &(*it++));
EXPECT_EQ(&thr, &(*it++));
EXPECT_EQ(list.end(), it);
}
TEST(IntrusiveList, Construct_ObjectIterator_Empty) {
std::array<TestItem, 0> array;
IntrusiveList<TestItem> list(array.begin(), array.end());
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Construct_ObjectIterator_One) {
std::array<TestItem, 1> array{{{1}}};
IntrusiveList<TestItem> list(array.begin(), array.end());
EXPECT_EQ(&array.front(), &list.front());
}
TEST(IntrusiveList, Construct_ObjectIterator_Multiple) {
std::array<TestItem, 3> array{{{1}, {2}, {3}}};
IntrusiveList<TestItem> list(array.begin(), array.end());
auto it = list.begin();
EXPECT_EQ(&array[0], &(*it++));
EXPECT_EQ(&array[1], &(*it++));
EXPECT_EQ(&array[2], &(*it++));
EXPECT_EQ(list.end(), it);
}
TEST(IntrusiveList, Construct_PointerIterator_Empty) {
std::array<TestItem*, 0> array;
IntrusiveList<TestItem> list(array.begin(), array.end());
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Construct_PointerIterator_One) {
std::array<TestItem, 1> array{{{1}}};
std::array<TestItem*, 1> ptrs{{&array[0]}};
IntrusiveList<TestItem> list(ptrs.begin(), ptrs.end());
EXPECT_EQ(ptrs[0], &list.front());
}
TEST(IntrusiveList, Construct_PointerIterator_Multiple) {
std::array<TestItem, 3> array{{{1}, {2}, {3}}};
std::array<TestItem*, 3> ptrs{{&array[0], &array[1], &array[2]}};
IntrusiveList<TestItem> list(ptrs.begin(), ptrs.end());
auto it = list.begin();
EXPECT_EQ(ptrs[0], &(*it++));
EXPECT_EQ(ptrs[1], &(*it++));
EXPECT_EQ(ptrs[2], &(*it++));
EXPECT_EQ(list.end(), it);
}
TEST(IntrusiveList, Assign_ReplacesPriorContents) {
std::array<TestItem, 3> array{{{0}, {100}, {200}}};
IntrusiveList<TestItem> list(array.begin(), array.end());
list.assign(array.begin() + 1, array.begin() + 2);
auto it = list.begin();
EXPECT_EQ(&array[1], &(*it++));
EXPECT_EQ(list.end(), it);
}
TEST(IntrusiveList, Assign_EmptyRange) {
std::array<TestItem, 3> array{{{0}, {100}, {200}}};
IntrusiveList<TestItem> list(array.begin(), array.end());
list.assign(array.begin() + 1, array.begin() + 1);
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, PushOne) {
constexpr int kMagicValue = 31;
TestItem item1(kMagicValue);
IntrusiveList<TestItem> list;
list.push_back(item1);
EXPECT_FALSE(list.empty());
EXPECT_EQ(list.front().GetNumber(), kMagicValue);
}
TEST(IntrusiveList, PushThree) {
TestItem item1(1);
TestItem item2(2);
TestItem item3(3);
IntrusiveList<TestItem> list;
list.push_back(item1);
list.push_back(item2);
list.push_back(item3);
int loop_count = 0;
for (auto& test_item : list) {
loop_count++;
EXPECT_EQ(loop_count, test_item.GetNumber());
}
EXPECT_EQ(loop_count, 3);
}
TEST(IntrusiveList, IsEmpty) {
TestItem item1(1);
IntrusiveList<TestItem> list;
EXPECT_TRUE(list.empty());
list.push_back(item1);
EXPECT_FALSE(list.empty());
}
TEST(IntrusiveList, InsertAfter) {
// Create a test item to insert midway through the list.
constexpr int kMagicValue = 42;
TestItem inserted_item(kMagicValue);
// Create initial values to fill in the start/end.
TestItem item_array[20];
IntrusiveList<TestItem> list;
// Fill the list with TestItem objects that have a value of zero.
for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
item_array[i].SetNumber(0);
list.push_back(item_array[i]);
}
// Move an iterator to the middle of the list, and then insert the magic item.
auto it = list.begin();
size_t expected_index = 1; // Expected index is iterator index + 1.
for (size_t i = 0; i < PW_ARRAY_SIZE(item_array) / 2; ++i) {
it++;
expected_index++;
}
it = list.insert_after(it, inserted_item);
// Ensure the returned iterator from insert_after is the newly inserted
// element.
EXPECT_EQ(it->GetNumber(), kMagicValue);
// Ensure the value is in the expected location (index of the iterator + 1).
size_t i = 0;
for (TestItem& item : list) {
if (item.GetNumber() == kMagicValue) {
EXPECT_EQ(i, expected_index);
} else {
EXPECT_EQ(item.GetNumber(), 0);
}
i++;
}
// Ensure the list didn't break and change sizes.
EXPECT_EQ(i, PW_ARRAY_SIZE(item_array) + 1);
}
TEST(IntrusiveList, PushFront) {
constexpr int kMagicValue = 42;
TestItem pushed_item(kMagicValue);
TestItem item_array[20];
IntrusiveList<TestItem> list;
// Fill the list with TestItem objects that have a value of zero.
for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
item_array[i].SetNumber(0);
list.push_back(item_array[i]);
}
// Create a test item to push to the front of the list.
list.push_front(pushed_item);
EXPECT_EQ(list.front().GetNumber(), kMagicValue);
}
TEST(IntrusiveList, Clear_Empty) {
IntrusiveList<TestItem> list;
EXPECT_TRUE(list.empty());
list.clear();
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Clear_OneItem) {
TestItem item(42);
IntrusiveList<TestItem> list;
list.push_back(item);
EXPECT_FALSE(list.empty());
list.clear();
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Clear_TwoItems) {
TestItem item1(42);
TestItem item2(42);
IntrusiveList<TestItem> list;
list.push_back(item1);
list.push_back(item2);
EXPECT_FALSE(list.empty());
list.clear();
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Clear_ReinsertClearedItems) {
std::array<TestItem, 20> item_array;
IntrusiveList<TestItem> list;
EXPECT_TRUE(list.empty());
list.clear();
EXPECT_TRUE(list.empty());
// Fill the list with TestItem objects.
for (size_t i = 0; i < item_array.size(); ++i) {
item_array[i].SetNumber(0);
list.push_back(item_array[i]);
}
// Remove everything.
list.clear();
EXPECT_TRUE(list.empty());
// Ensure all the removed elements can still be added back to a list.
for (size_t i = 0; i < item_array.size(); ++i) {
item_array[i].SetNumber(0);
list.push_back(item_array[i]);
}
}
TEST(IntrusiveList, PopFront) {
constexpr int kValue1 = 32;
constexpr int kValue2 = 4083;
TestItem item1(kValue1);
TestItem item2(kValue2);
IntrusiveList<TestItem> list;
EXPECT_TRUE(list.empty());
list.push_front(item2);
list.push_front(item1);
list.pop_front();
EXPECT_EQ(list.front().GetNumber(), kValue2);
EXPECT_FALSE(list.empty());
list.pop_front();
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, PopFrontAndReinsert) {
constexpr int kValue1 = 32;
constexpr int kValue2 = 4083;
TestItem item1(kValue1);
TestItem item2(kValue2);
IntrusiveList<TestItem> list;
EXPECT_TRUE(list.empty());
list.push_front(item2);
list.push_front(item1);
list.pop_front();
list.push_front(item1);
EXPECT_EQ(list.front().GetNumber(), kValue1);
}
TEST(IntrusiveList, ListFront) {
TestItem item1(1);
TestItem item2(0);
TestItem item3(0xffff);
IntrusiveList<TestItem> list;
list.push_back(item1);
list.push_back(item2);
list.push_back(item3);
EXPECT_EQ(&item1, &list.front());
EXPECT_EQ(&item1, &(*list.begin()));
}
TEST(IntrusiveList, IteratorIncrement) {
TestItem item_array[20];
IntrusiveList<TestItem> list;
for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
item_array[i].SetNumber(i);
list.push_back(item_array[i]);
}
auto it = list.begin();
int i = 0;
while (it != list.end()) {
if (i == 0) {
// Test pre-incrementing on the first element.
EXPECT_EQ((++it)->GetNumber(), item_array[++i].GetNumber());
} else {
EXPECT_EQ((it++)->GetNumber(), item_array[i++].GetNumber());
}
}
}
TEST(IntrusiveList, ConstIteratorRead) {
// For this test, items are checked to be non-zero.
TestItem item1(1);
TestItem item2(99);
IntrusiveList<TestItem> list;
const IntrusiveList<TestItem>* const_list = &list;
list.push_back(item1);
list.push_back(item2);
auto it = const_list->begin();
while (it != const_list->end()) {
EXPECT_NE(it->GetNumber(), 0);
it++;
}
}
#if NO_COMPILE_TESTS
// TODO(pwbug/47): These tests should fail to compile, enable when no-compile
// tests are set up in Pigweed.
TEST(IntrusiveList, ConstIteratorModify) {
TestItem item1(1);
TestItem item2(99);
IntrusiveList<TestItem> list;
const IntrusiveList<TestItem>* const_list = &list;
list.push_back(item1);
list.push_back(item2);
auto it = const_list->begin();
while (it != const_list->end()) {
it->SetNumber(0);
it++;
}
}
#endif // NO_COMPILE_TESTS
// TODO(pwbug/88): These tests should trigger a CHECK failure. This requires
// using a testing version of pw_assert.
#if TESTING_CHECK_FAILURES_IS_SUPPORTED
TEST(IntrusiveList, Construct_DuplicateItems) {
TestItem item(1);
IntrusiveList<TestItem> list({&item, &item});
}
TEST(IntrusiveList, InsertAfter_SameItem) {
TestItem item(1);
IntrusiveList<TestItem> list({&item});
list.insert_after(list.begin(), item);
}
TEST(IntrusiveList, InsertAfter_SameItemAfterEnd) {
TestItem item(1);
IntrusiveList<TestItem> list({&item});
list.insert_after(list.end(), item);
}
TEST(IntrusiveList, PushBack_SameItem) {
TestItem item(1);
IntrusiveList<TestItem> list({&item});
list.push_back(item);
}
TEST(IntrusiveList, PushFront_SameItem) {
TestItem item(1);
IntrusiveList<TestItem> list({&item});
list.push_front(item);
}
#endif // TESTING_CHECK_FAILURES_IS_SUPPORTED
TEST(IntrusiveList, EraseAfter_FirstItem) {
std::array<TestItem, 3> items{{{0}, {1}, {2}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
auto it = list.erase_after(list.before_begin());
EXPECT_EQ(list.begin(), it);
EXPECT_EQ(&items[1], &list.front());
}
TEST(IntrusiveList, EraseAfter_LastItem) {
std::array<TestItem, 3> items{{{0}, {1}, {2}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
auto it = list.begin();
++it;
it = list.erase_after(it);
EXPECT_EQ(list.end(), it);
it = list.begin();
++it;
EXPECT_EQ(&items[1], &(*it));
}
TEST(IntrusiveList, EraseAfter_AllItems) {
std::array<TestItem, 3> items{{{0}, {1}, {2}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
list.erase_after(list.begin());
list.erase_after(list.begin());
auto it = list.erase_after(list.before_begin());
EXPECT_EQ(list.end(), it);
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Remove_EmptyList) {
std::array<TestItem, 1> items{{{3}}};
IntrusiveList<TestItem> list(items.begin(), items.begin()); // Add nothing!
EXPECT_TRUE(list.empty());
EXPECT_FALSE(list.remove(items[0]));
}
TEST(IntrusiveList, Remove_SingleItem_NotPresent) {
std::array<TestItem, 1> items{{{1}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
EXPECT_FALSE(list.remove(TestItem(1)));
EXPECT_EQ(&items.front(), &list.front());
}
TEST(IntrusiveList, Remove_SingleItem_Removed) {
std::array<TestItem, 1> items{{{1}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
EXPECT_TRUE(list.remove(items[0]));
EXPECT_TRUE(list.empty());
}
TEST(IntrusiveList, Remove_MultipleItems_NotPresent) {
std::array<TestItem, 5> items{{{1}, {1}, {2}, {3}, {4}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
EXPECT_FALSE(list.remove(TestItem(1)));
}
TEST(IntrusiveList, Remove_MultipleItems_RemoveAndPushBack) {
std::array<TestItem, 5> items{{{1}, {1}, {2}, {3}, {4}}};
IntrusiveList<TestItem> list(items.begin(), items.end());
EXPECT_TRUE(list.remove(items[0]));
EXPECT_TRUE(list.remove(items[3]));
list.push_back(items[0]); // Make sure can add the item after removing it.
auto it = list.begin();
EXPECT_EQ(&items[1], &(*it++));
EXPECT_EQ(&items[2], &(*it++));
EXPECT_EQ(&items[4], &(*it++));
EXPECT_EQ(&items[0], &(*it++));
EXPECT_EQ(list.end(), it);
}
TEST(IntrusiveList, ItemsRemoveThemselvesFromListsWhenDestructed) {
// Create a list with some items it.
TestItem a, b, c, d;
IntrusiveList<TestItem> list;
list.push_back(a);
list.push_back(b);
list.push_back(c);
list.push_back(d);
// Insert items that will be destructed before the list.
{
TestItem x, y, z, w;
list.push_back(x);
list.push_back(z);
list.push_front(y);
list.push_front(w);
auto it = list.begin();
EXPECT_EQ(&w, &(*it++));
EXPECT_EQ(&y, &(*it++));
EXPECT_EQ(&a, &(*it++));
EXPECT_EQ(&b, &(*it++));
EXPECT_EQ(&c, &(*it++));
EXPECT_EQ(&d, &(*it++));
EXPECT_EQ(&x, &(*it++));
EXPECT_EQ(&z, &(*it++));
EXPECT_EQ(list.end(), it);
// Here, x, y, z, w are removed from the list for the destructor.
}
// Ensure we get back our original list.
auto it = list.begin();
EXPECT_EQ(&a, &(*it++));
EXPECT_EQ(&b, &(*it++));
EXPECT_EQ(&c, &(*it++));
EXPECT_EQ(&d, &(*it++));
EXPECT_EQ(list.end(), it);
}
TEST(IntrusiveList, SizeBasic) {
IntrusiveList<TestItem> list;
EXPECT_EQ(list.size(), 0u);
TestItem one(55);
list.push_front(one);
EXPECT_EQ(list.size(), static_cast<size_t>(1));
TestItem two(66);
list.push_back(two);
EXPECT_EQ(list.size(), static_cast<size_t>(2));
TestItem thr(77);
list.push_back(thr);
EXPECT_EQ(list.size(), static_cast<size_t>(3));
}
TEST(IntrusiveList, SizeScoped) {
IntrusiveList<TestItem> list;
EXPECT_EQ(list.size(), 0u);
// Add elements in new scopes; verify size on the way in and on the way out.
{
TestItem one(55);
list.push_back(one);
EXPECT_EQ(list.size(), static_cast<size_t>(1));
{
TestItem two(66);
list.push_back(two);
EXPECT_EQ(list.size(), static_cast<size_t>(2));
{
TestItem thr(77);
list.push_back(thr);
EXPECT_EQ(list.size(), static_cast<size_t>(3));
}
EXPECT_EQ(list.size(), static_cast<size_t>(2));
}
EXPECT_EQ(list.size(), static_cast<size_t>(1));
}
EXPECT_EQ(list.size(), static_cast<size_t>(0));
}
} // namespace
} // namespace pw