psemek/libs/util/tests/hash_table.cpp

#include <psemek/test/test.hpp>

#include <psemek/util/hash_table.hpp>
#include <psemek/random/generator.hpp>

#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <memory>

using namespace psemek;
using namespace psemek::util;

namespace
{

	struct lifetime_tracker
	{
		static std::size_t constructed_count;
		static std::size_t move_constructed_count;
		static std::size_t destroyed_count;

		static std::size_t alive_count()
		{
			return constructed_count + move_constructed_count - destroyed_count;
		}

		int value;

		lifetime_tracker(int value)
			: value(value)
		{
			++constructed_count;
		}

		lifetime_tracker(lifetime_tracker && other)
			: value(other.value)
		{
			++move_constructed_count;
		}

		lifetime_tracker(lifetime_tracker const &) = delete;

		lifetime_tracker & operator = (lifetime_tracker &&) = delete;
		lifetime_tracker & operator = (lifetime_tracker const &) = delete;

		~lifetime_tracker()
		{
			++destroyed_count;
		}

		friend bool operator == (lifetime_tracker const &, lifetime_tracker const &) = default;
	};

	std::size_t lifetime_tracker::constructed_count = 0;
	std::size_t lifetime_tracker::move_constructed_count = 0;
	std::size_t lifetime_tracker::destroyed_count = 0;

	struct lifetime_tracker_hash
	{
		std::size_t operator()(lifetime_tracker const & value) const noexcept
		{
			return value.value;
		}
	};

}

test_case(util_hash__set_empty)
{
	hash_set<int> set;
	expect(set.size() == 0);
	expect(set.empty());

	int call_count = 0;
	for ([[maybe_unused]] auto value : set)
		++call_count;
	expect_equal(call_count, 0);
}

test_case(util_hash__set_insert_sequential)
{
	hash_set<int> set;

	int const count = 1024 * 16;
	for (int i = 0; i < count; ++i)
		expect(set.insert(i * i).second);

	expect_equal(set.size(), count);

	for (int i = 0; i < count; ++i)
	{
		expect(set.contains(i * i));
		auto it = set.find(i * i);
		expect(it != set.end());
		expect_equal(*it, i * i);
	}

	for (int i = count; i < 2 * count; ++i)
	{
		expect(!set.contains(i * i));
		expect(set.find(i * i) == set.end());
	}
}

test_case(util_hash__set_insert_random__small)
{
	hash_set<int> set;

	random::generator rng{0x8d6ed4c8749bda57ull, 0x580a939046371825ull};

	std::uint32_t const max = 1024;

	while (set.size() < max)
	{
		set.insert(rng() % max);
	}

	expect_equal(set.size(), max);

	for (int i = 0; i < max; ++i)
	{
		expect(set.contains(i));
		auto it = set.find(i);
		expect(it != set.end());
		expect_equal(*it, i);
	}

	for (int i = max; i < 2 * max; ++i)
	{
		expect(!set.contains(i));
		expect(set.find(i) == set.end());
	}

	int const probe_count = 1024 * 16;
	for (int i = 0; i < probe_count; ++i)
	{
		auto value = rng();
		if (value < max) continue;

		expect(!set.contains(value));
		expect(set.find(value) == set.end());
	}
}

test_case(util_hash__set_insert_random)
{
	hash_set<int> set;

	random::generator rng{0x3096a19223fed1cfull, 0xf690a99db056b624ull};

	int const count = 1024 * 16;

	std::vector<int> inserted;

	while (inserted.size() < count)
	{
		int value = rng();
		if (set.insert(value).second)
			inserted.push_back(value);
	}

	expect_equal(set.size(), count);

	std::vector<int> not_inserted;

	while (not_inserted.size() < count)
	{
		int value = rng();
		if (!set.contains(value))
			not_inserted.push_back(value);
	}

	for (auto value : inserted)
	{
		expect(set.contains(value));
		auto it = set.find(value);
		expect(it != set.end());
		expect_equal(*it, value);
	}

	for (auto value : not_inserted)
	{
		expect(!set.contains(value));
		auto it = set.find(value);
		expect(it == set.end());
	}
}

test_case(util_hash__set_erase_sequential)
{
	hash_set<int> set;

	int const count = 1024 * 16;
	for (int i = 0; i < count; ++i)
		expect(set.insert(i * i).second);

	expect_equal(set.size(), count);

	for (int i = count; i < 2 * count; ++i)
		expect(!set.erase(i * i));

	for (int i = 0; i < count; ++i)
	{
		expect(set.erase(i * i));
		expect(!set.contains(i * i));
		expect(set.size() == count - i - 1);
	}

	expect(set.empty());

	for (int i = 0; i < count; ++i)
		expect(!set.erase(i * i));
}

test_case(util_hash__set_erase_random)
{
	hash_set<int> set;

	random::generator rng{0xff60de1081bc862aull, 0xe0a81aad7a42f1b0ull};

	int const count = 1024 * 16;

	std::vector<int> inserted;

	while (inserted.size() < count)
	{
		int value = rng();
		if (set.insert(value).second)
			inserted.push_back(value);
	}

	expect_equal(set.size(), count);

	std::vector<int> not_inserted;

	while (not_inserted.size() < count)
	{
		int value = rng();
		if (!set.contains(value))
			not_inserted.push_back(value);
	}

	for (auto value : not_inserted)
	{
		expect(!set.erase(value));
		expect_equal(set.size(), count);
	}

	for (int i = 0; i < count; ++i)
	{
		expect(set.erase(inserted[i]));
		expect(!set.contains(inserted[i]));
		expect_equal(set.size(), count - i - 1);
	}
}

test_case(util_hash__set_insert__erase_sequential)
{
	hash_set<int> set;

	int const count = 1024 * 16;
	for (int i = 0; i < count; ++i)
		expect(set.insert(i * i).second);

	expect_equal(set.size(), count);

	for (int i = 0; i < count / 2; ++i)
	{
		expect(set.erase(i * i));
		expect(set.find(i * i) == set.end());
		expect_equal(set.size(), count - i - 1);
	}

	expect_equal(set.size(), count / 2);

	for (int i = 0; i < count / 2; ++i)
	{
		expect(!set.contains(i * i));
		expect(!set.erase(i * i));
		expect(set.find(i * i) == set.end());
	}

	for (int i = count / 2; i < count; ++i)
	{
		expect(set.contains(i * i));
		auto it = set.find(i * i);
		expect(it != set.end());
		expect_equal(*it, i * i);
	}

	for (int i = count; i < 2 * count; ++i)
	{
		expect(set.find(i * i) == set.end());
		expect(set.insert(i * i).second);
		expect_equal(set.size(), count / 2 + (i - count) + 1);
	}

	for (int i = count / 2; i < count; ++i)
	{
		expect(set.erase(i * i));
		expect(!set.contains(i * i));
		expect(set.size() == 2 * count - i - 1);
	}

	expect_equal(set.size(), count);
}

test_case(util_hash__set_clear)
{
	hash_set<int> set;

	int const count = 1024 * 1024;
	for (int i = 0; i < count; ++i)
		expect(set.insert(i).second);

	expect_equal(set.size(), count);

	set.clear();

	expect(set.empty());
	expect_equal(set.size(), 0);

	int call_count = 0;
	for ([[maybe_unused]] auto value : set)
		++call_count;
	expect_equal(call_count, 0);
}

test_case(util_hash__set_move)
{
	hash_set<int> set1;

	int const count = 1024 * 1024;
	for (int i = 0; i < count; ++i)
		expect(set1.insert(i).second);

	expect_equal(set1.size(), count);

	hash_set<int> set2 = std::move(set1);

	expect(set1.empty());
	expect_equal(set1.size(), 0);

	expect(!set2.empty());
	expect_equal(set2.size(), count);
	for (int i = 0; i < count; ++i)
	{
		expect(!set1.contains(i));
		expect(set2.contains(i));
	}
	for (int i = count; i < 2 * count; ++i)
	{
		expect(!set1.contains(i));
		expect(!set2.contains(i));
	}

	hash_set<int> set3;
	set3 = std::move(set2);

	expect(set2.empty());
	expect_equal(set2.size(), 0);

	expect(!set3.empty());
	expect_equal(set3.size(), count);
	for (int i = 0; i < count; ++i)
	{
		expect(!set2.contains(i));
		expect(set3.contains(i));
	}
	for (int i = count; i < 2 * count; ++i)
	{
		expect(!set2.contains(i));
		expect(!set3.contains(i));
	}
}

test_case(util_hash__set_movable)
{
	hash_set<std::unique_ptr<int>> set;

	int const count = 1024 * 16;
	for (int i = 0; i < count; ++i)
	{
		expect(set.insert(std::make_unique<int>(i)).second);
		expect_equal(set.size(), i + 1);
	}

	expect_equal(set.size(), count);
}

test_case(util_hash__set_lifetime)
{
	hash_set<lifetime_tracker, lifetime_tracker_hash> set;

	int const count = 1024 * 16;
	for (int i = 0; i < count; ++i)
	{
		expect(set.insert(lifetime_tracker(i)).second);
		expect_equal(set.size(), i + 1);
		expect_equal(lifetime_tracker::alive_count(), i + 1);
	}

	for (int i = 0; i < count; ++i)
	{
		expect(set.contains(lifetime_tracker(i)));
		auto it = set.find(lifetime_tracker(i));
		expect(it != set.end());
		expect(*it == lifetime_tracker(i));
	}

	for (int i = 0; i < count; ++i)
	{
		expect(set.erase(lifetime_tracker(i)));
		expect(!set.contains(lifetime_tracker(i)));
		expect(set.find(lifetime_tracker(i)) == set.end());
		expect_equal(lifetime_tracker::alive_count(), count - i - 1);
	}
}

test_case(util_hash__set_benchmark)
{
	random::generator rng;
	std::vector<int> values;
	int const count = 1024 * 1024;
	for (int i = 0; i < count; ++i)
		values.push_back(i);
	std::shuffle(values.begin(), values.end(), rng);

	test_profile(hash_set_total)
	{
		hash_set<int> set;

		test_profile(hash_set_insert)
		{
			for (auto value : values)
				set.insert(value);
			expect_equal(set.size(), count);
		}

		test_profile(hash_set_iterate)
		{
			int size = 0;
			for (auto value : set)
			{
				expect(0 <= value && value < count);
				++size;
			}
			expect_equal(size, count);
		}

		test_profile(hash_set_find)
		{
			for (auto value : values)
			{
				auto it = set.find(value);
				expect(it != set.end());
				expect_equal(*it, value);
			}
		}

		test_profile(hash_set_clear)
		{
			set.clear();
		}
	}

	test_profile(unordered_set_total)
	{
		std::unordered_set<int> set;

		test_profile(unordered_set_insert)
		{
			for (auto value : values)
				set.insert(value);
			expect_equal(set.size(), count);
		}

		test_profile(unordered_set_iterate)
		{
			int size = 0;
			for (auto value : set)
			{
				expect(0 <= value && value < count);
				++size;
			}
			expect_equal(size, count);
		}

		test_profile(unordered_set_find)
		{
			for (auto value : values)
			{
				auto it = set.find(value);
				expect(it != set.end());
				expect_equal(*it, value);
			}
		}

		test_profile(unordered_set_clear)
		{
			set.clear();
		}
	}
}

test_case(util_hash__map_empty)
{
	hash_map<int, int> map;
	expect(map.size() == 0);
	expect(map.empty());

	int call_count = 0;
	for ([[maybe_unused]] auto const & pair : map)
		++call_count;
	expect_equal(call_count, 0);
}

test_case(util_hash__map_insert)
{
	hash_map<int, int> map;

	int const count = 1024 * 16;
	for (int i = 0; i < count; ++i)
		expect(map.insert({i * i, i}).second);

	expect_equal(map.size(), count);

	for (int i = 0; i < count; ++i)
	{
		expect(map.contains(i * i));
		auto it = map.find(i * i);
		expect(it != map.end());
		expect_equal(it->first, i * i);
		expect_equal(it->second, i);
	}

	for (int i = count; i < 2 * count; ++i)
	{
		expect(!map.contains(i * i));
		expect(map.find(i * i) == map.end());
	}
}

test_case(util_hash__map_clear)
{
	hash_map<int, int> map;

	int const count = 1024 * 1024;
	for (int i = 0; i < count; ++i)
		expect(map.insert({i, (i * 19) % count}).second);

	expect_equal(map.size(), count);

	map.clear();

	expect(map.empty());
	expect_equal(map.size(), 0);

	int call_count = 0;
	for ([[maybe_unused]] auto value : map)
		++call_count;
	expect_equal(call_count, 0);
}

test_case(util_hash__map_move)
{
	hash_map<int, int> map1;

	int const count = 1024 * 1024;
	for (int i = 0; i < count; ++i)
		expect(map1.insert({i, (i * 19) % count}).second);

	expect_equal(map1.size(), count);

	hash_map<int, int> map2 = std::move(map1);

	expect(map1.empty());
	expect_equal(map1.size(), 0);

	expect(!map2.empty());
	expect_equal(map2.size(), count);
	for (int i = 0; i < count; ++i)
	{
		expect(!map1.contains(i));
		auto it = map2.find(i);
		expect(it != map2.end());
		expect_equal(it->first, i);
		expect_equal(it->second, (i * 19) % count);
	}
	for (int i = count; i < 2 * count; ++i)
	{
		expect(!map1.contains(i));
		expect(!map2.contains(i));
	}

	hash_map<int, int> map3;
	map3 = std::move(map2);

	expect(map2.empty());
	expect_equal(map2.size(), 0);

	expect(!map3.empty());
	expect_equal(map3.size(), count);
	for (int i = 0; i < count; ++i)
	{
		expect(!map2.contains(i));
		auto it = map3.find(i);
		expect(it != map3.end());
		expect_equal(it->first, i);
		expect_equal(it->second, (i * 19) % count);
	}
	for (int i = count; i < 2 * count; ++i)
	{
		expect(!map2.contains(i));
		expect(!map3.contains(i));
	}
}

test_case(util_hash__map_benchmark)
{
	random::generator rng;
	std::vector<int> keys;
	int const count = 1024 * 1024;
	for (int i = 0; i < count; ++i)
		keys.push_back(i);
	std::shuffle(keys.begin(), keys.end(), rng);

	test_profile(hash_map_total)
	{
		hash_map<int, int> map;

		test_profile(hash_map_insert)
		{
			for (auto key : keys)
				map.insert({key, -key});
			expect_equal(map.size(), count);
		}

		test_profile(hash_map_iterate)
		{
			int size = 0;
			for (auto const & pair : map)
			{
				expect(0 <= pair.first && pair.first < count);
				expect_equal(pair.second, -pair.first);
				++size;
			}
			expect_equal(size, count);
		}

		test_profile(hash_map_find)
		{
			for (auto key : keys)
			{
				auto it = map.find(key);
				expect(map.find(key) != map.end());
				expect_equal(it->second, -key);
			}
		}

		test_profile(hash_map_clear)
		{
			map.clear();
		}
	}

	test_profile(unordered_map_total)
	{
		std::unordered_map<int, int> map;

		test_profile(unordered_map_insert)
		{
			for (auto key : keys)
				map.insert({key, -key});
		}

		test_profile(unordered_map_iterate)
		{
			int size = 0;
			for (auto const & pair : map)
			{
				expect(0 <= pair.first && pair.first < count);
				expect_equal(pair.second, -pair.first);
				++size;
			}
			expect_equal(size, count);
		}

		test_profile(unordered_map_find)
		{
			for (auto key : keys)
			{
				auto it = map.find(key);
				expect(map.find(key) != map.end());
				expect_equal(it->second, -key);
			}
		}

		test_profile(unordered_map_clear)
		{
			map.clear();
		}
	}
}