115 lines
2.3 KiB
C++
115 lines
2.3 KiB
C++
#include <psemek/test/test.hpp>
|
|
|
|
#include <psemek/util/flat_list.hpp>
|
|
|
|
#include <algorithm>
|
|
#include <vector>
|
|
#include <random>
|
|
#include <list>
|
|
|
|
using namespace psemek::util;
|
|
|
|
test_case(util_flat__list_empty)
|
|
{
|
|
flat_list<int> l;
|
|
expect(l.empty());
|
|
expect_equal(l.size(), 0);
|
|
expect_equal(l.capacity(), 0);
|
|
}
|
|
|
|
test_case(util_flat__list_sequential)
|
|
{
|
|
auto p = std::make_shared<int>(42);
|
|
flat_list<std::shared_ptr<int>> l;
|
|
|
|
std::vector<decltype(l)::handle_type> h;
|
|
|
|
for (std::size_t i = 0; i < 1024*1024; ++i)
|
|
{
|
|
h.push_back(l.insert(p));
|
|
expect_equal(*l[h.back()], *p);
|
|
expect_equal(l.size(), i + 1);
|
|
expect_gequal(l.capacity(), l.size());
|
|
expect_equal(p.use_count(), i + 2);
|
|
}
|
|
|
|
for (std::size_t i = 0; i < h.size(); ++i)
|
|
{
|
|
l.erase(h[i]);
|
|
expect_equal(l.size(), h.size() - i - 1);
|
|
expect_gequal(l.capacity(), l.size());
|
|
expect_equal(p.use_count(), h.size() - i);
|
|
}
|
|
|
|
expect(l.empty());
|
|
|
|
l.clear();
|
|
expect(l.empty());
|
|
}
|
|
|
|
test_case(util_flat__list_shuffle)
|
|
{
|
|
auto p = std::make_shared<int>(42);
|
|
flat_list<std::shared_ptr<int>> l;
|
|
|
|
std::vector<decltype(l)::handle_type> h;
|
|
|
|
for (std::size_t i = 0; i < 1024*1024; ++i)
|
|
{
|
|
h.push_back(l.insert(p));
|
|
expect_equal(l[h.back()], p);
|
|
expect_equal(l.size(), i + 1);
|
|
expect_gequal(l.capacity(), l.size());
|
|
expect_equal(p.use_count(), i + 2);
|
|
}
|
|
|
|
std::default_random_engine rng{42};
|
|
std::shuffle(h.begin(), h.end(), rng);
|
|
|
|
for (std::size_t i = 0; i < h.size(); ++i)
|
|
{
|
|
l.erase(h[i]);
|
|
expect_equal(l.size(), h.size() - i - 1);
|
|
expect_gequal(l.capacity(), l.size());
|
|
expect_equal(p.use_count(), h.size() - i);
|
|
}
|
|
|
|
expect(l.empty());
|
|
|
|
l.clear();
|
|
expect(l.empty());
|
|
}
|
|
|
|
test_case(util_flat__list_random)
|
|
{
|
|
auto p = std::make_shared<int>(42);
|
|
flat_list<std::shared_ptr<int>> l;
|
|
|
|
std::vector<decltype(l)::handle_type> h;
|
|
|
|
std::default_random_engine rng{42};
|
|
std::uniform_int_distribution<int> action{0, 1};
|
|
|
|
for (std::size_t i = 0; i < 1024*1024; ++i)
|
|
{
|
|
if (h.empty() || action(rng) == 0)
|
|
{
|
|
h.push_back(l.insert(p));
|
|
expect_equal(l[h.back()], p);
|
|
}
|
|
else
|
|
{
|
|
auto index = std::uniform_int_distribution<std::size_t>{0, h.size() - 1}(rng);
|
|
expect_equal(l[h[index]], p);
|
|
l.erase(h[index]);
|
|
h.erase(h.begin() + index);
|
|
}
|
|
|
|
expect_equal(l.size(), h.size());
|
|
expect_gequal(l.capacity(), l.size());
|
|
expect_equal(p.use_count(), h.size() + 1);
|
|
}
|
|
|
|
l.clear();
|
|
expect(l.empty());
|
|
}
|