blob: af3efee54a8d6e87341d4b3dd1e81b56c92e68e9 [file] [log] [blame]
// Copyright 2022 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "src/tint/utils/containers/hashmap.h"
#include <array>
#include <random>
#include <string>
#include <tuple>
#include <unordered_map>
#include "gmock/gmock.h"
namespace tint {
namespace {
constexpr std::array kPrimes{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311,
313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
};
TEST(Hashmap, Empty) {
Hashmap<std::string, int, 8> map;
EXPECT_EQ(map.Count(), 0u);
}
TEST(Hashmap, AddRemove) {
Hashmap<std::string, std::string, 8> map;
EXPECT_TRUE(map.Add("hello", "world"));
EXPECT_EQ(map.Get("hello"), "world");
EXPECT_EQ(map.Count(), 1u);
EXPECT_TRUE(map.Contains("hello"));
EXPECT_FALSE(map.Contains("world"));
EXPECT_FALSE(map.Add("hello", "cat"));
EXPECT_EQ(map.Count(), 1u);
EXPECT_TRUE(map.Remove("hello"));
EXPECT_EQ(map.Count(), 0u);
EXPECT_FALSE(map.Contains("hello"));
EXPECT_FALSE(map.Contains("world"));
}
TEST(Hashmap, ReplaceRemove) {
Hashmap<std::string, std::string, 8> map;
map.Replace("hello", "world");
EXPECT_EQ(map.Get("hello"), "world");
EXPECT_EQ(map.Count(), 1u);
EXPECT_TRUE(map.Contains("hello"));
EXPECT_FALSE(map.Contains("world"));
map.Replace("hello", "cat");
EXPECT_EQ(map.Get("hello"), "cat");
EXPECT_EQ(map.Count(), 1u);
EXPECT_TRUE(map.Remove("hello"));
EXPECT_EQ(map.Count(), 0u);
EXPECT_FALSE(map.Contains("hello"));
EXPECT_FALSE(map.Contains("world"));
}
TEST(Hashmap, Generation) {
Hashmap<int, std::string, 8> map;
EXPECT_EQ(map.Generation(), 0u);
map.Add(1, "one");
EXPECT_EQ(map.Generation(), 1u);
map.Add(1, "uno");
EXPECT_EQ(map.Generation(), 1u);
map.Replace(1, "une");
EXPECT_EQ(map.Generation(), 2u);
map.Add(2, "dos");
EXPECT_EQ(map.Generation(), 3u);
map.Remove(1);
EXPECT_EQ(map.Generation(), 4u);
map.Clear();
EXPECT_EQ(map.Generation(), 5u);
map.Find(2);
EXPECT_EQ(map.Generation(), 5u);
map.Get(2);
EXPECT_EQ(map.Generation(), 5u);
}
TEST(Hashmap, Index) {
Hashmap<int, std::string, 4> map;
auto zero = map.Find(0);
EXPECT_FALSE(zero);
map.Add(3, "three");
auto three = map.Find(3);
map.Add(2, "two");
auto two = map.Find(2);
map.Add(4, "four");
auto four = map.Find(4);
map.Add(8, "eight");
auto eight = map.Find(8);
EXPECT_FALSE(zero);
ASSERT_TRUE(three);
ASSERT_TRUE(two);
ASSERT_TRUE(four);
ASSERT_TRUE(eight);
EXPECT_EQ(*three, "three");
EXPECT_EQ(*two, "two");
EXPECT_EQ(*four, "four");
EXPECT_EQ(*eight, "eight");
map.Add(0, "zero"); // Note: Find called before Add() is okay!
map.Add(5, "five");
auto five = map.Find(5);
map.Add(6, "six");
auto six = map.Find(6);
map.Add(1, "one");
auto one = map.Find(1);
map.Add(7, "seven");
auto seven = map.Find(7);
ASSERT_TRUE(zero);
ASSERT_TRUE(three);
ASSERT_TRUE(two);
ASSERT_TRUE(four);
ASSERT_TRUE(eight);
ASSERT_TRUE(five);
ASSERT_TRUE(six);
ASSERT_TRUE(one);
ASSERT_TRUE(seven);
EXPECT_EQ(*zero, "zero");
EXPECT_EQ(*three, "three");
EXPECT_EQ(*two, "two");
EXPECT_EQ(*four, "four");
EXPECT_EQ(*eight, "eight");
EXPECT_EQ(*five, "five");
EXPECT_EQ(*six, "six");
EXPECT_EQ(*one, "one");
EXPECT_EQ(*seven, "seven");
map.Remove(2);
map.Remove(8);
map.Remove(1);
EXPECT_FALSE(two);
EXPECT_FALSE(eight);
EXPECT_FALSE(one);
}
TEST(Hashmap, StringKeys) {
Hashmap<std::string, int, 4> map;
EXPECT_FALSE(map.Find("zero"));
EXPECT_FALSE(map.Find(std::string("zero")));
EXPECT_FALSE(map.Find(std::string_view("zero")));
map.Add("three", 3);
auto three_cstr = map.Find("three");
auto three_str = map.Find(std::string("three"));
auto three_sv = map.Find(std::string_view("three"));
map.Add(std::string("two"), 2);
auto two_cstr = map.Find("two");
auto two_str = map.Find(std::string("two"));
auto two_sv = map.Find(std::string_view("two"));
map.Add("four", 4);
auto four_cstr = map.Find("four");
auto four_str = map.Find(std::string("four"));
auto four_sv = map.Find(std::string_view("four"));
map.Add(std::string("eight"), 8);
auto eight_cstr = map.Find("eight");
auto eight_str = map.Find(std::string("eight"));
auto eight_sv = map.Find(std::string_view("eight"));
ASSERT_TRUE(three_cstr);
ASSERT_TRUE(three_str);
ASSERT_TRUE(three_sv);
ASSERT_TRUE(two_cstr);
ASSERT_TRUE(two_str);
ASSERT_TRUE(two_sv);
ASSERT_TRUE(four_cstr);
ASSERT_TRUE(four_str);
ASSERT_TRUE(four_sv);
ASSERT_TRUE(eight_cstr);
ASSERT_TRUE(eight_str);
ASSERT_TRUE(eight_sv);
EXPECT_EQ(*three_cstr, 3);
EXPECT_EQ(*three_str, 3);
EXPECT_EQ(*three_sv, 3);
EXPECT_EQ(*two_cstr, 2);
EXPECT_EQ(*two_str, 2);
EXPECT_EQ(*two_sv, 2);
EXPECT_EQ(*four_cstr, 4);
EXPECT_EQ(*four_str, 4);
EXPECT_EQ(*four_sv, 4);
EXPECT_EQ(*eight_cstr, 8);
EXPECT_EQ(*eight_str, 8);
EXPECT_EQ(*eight_sv, 8);
map.Add("zero", 0); // Note: Find called before Add() is okay!
auto zero_cstr = map.Find("zero");
auto zero_str = map.Find(std::string("zero"));
auto zero_sv = map.Find(std::string_view("zero"));
map.Add(std::string("five"), 5);
auto five_cstr = map.Find("five");
auto five_str = map.Find(std::string("five"));
auto five_sv = map.Find(std::string_view("five"));
map.Add("six", 6);
auto six_cstr = map.Find("six");
auto six_str = map.Find(std::string("six"));
auto six_sv = map.Find(std::string_view("six"));
map.Add("one", 1);
auto one_cstr = map.Find("one");
auto one_str = map.Find(std::string("one"));
auto one_sv = map.Find(std::string_view("one"));
map.Add(std::string("seven"), 7);
auto seven_cstr = map.Find("seven");
auto seven_str = map.Find(std::string("seven"));
auto seven_sv = map.Find(std::string_view("seven"));
ASSERT_TRUE(zero_cstr);
ASSERT_TRUE(zero_str);
ASSERT_TRUE(zero_sv);
ASSERT_TRUE(three_cstr);
ASSERT_TRUE(three_str);
ASSERT_TRUE(three_sv);
ASSERT_TRUE(two_cstr);
ASSERT_TRUE(two_str);
ASSERT_TRUE(two_sv);
ASSERT_TRUE(four_cstr);
ASSERT_TRUE(four_str);
ASSERT_TRUE(four_sv);
ASSERT_TRUE(eight_cstr);
ASSERT_TRUE(eight_str);
ASSERT_TRUE(eight_sv);
ASSERT_TRUE(five_cstr);
ASSERT_TRUE(five_str);
ASSERT_TRUE(five_sv);
ASSERT_TRUE(six_cstr);
ASSERT_TRUE(six_str);
ASSERT_TRUE(six_sv);
ASSERT_TRUE(one_cstr);
ASSERT_TRUE(one_str);
ASSERT_TRUE(one_sv);
ASSERT_TRUE(seven_cstr);
ASSERT_TRUE(seven_str);
ASSERT_TRUE(seven_sv);
EXPECT_EQ(*zero_cstr, 0);
EXPECT_EQ(*zero_str, 0);
EXPECT_EQ(*zero_sv, 0);
EXPECT_EQ(*three_cstr, 3);
EXPECT_EQ(*three_str, 3);
EXPECT_EQ(*three_sv, 3);
EXPECT_EQ(*two_cstr, 2);
EXPECT_EQ(*two_str, 2);
EXPECT_EQ(*two_sv, 2);
EXPECT_EQ(*four_cstr, 4);
EXPECT_EQ(*four_str, 4);
EXPECT_EQ(*four_sv, 4);
EXPECT_EQ(*eight_cstr, 8);
EXPECT_EQ(*eight_str, 8);
EXPECT_EQ(*eight_sv, 8);
EXPECT_EQ(*five_cstr, 5);
EXPECT_EQ(*five_str, 5);
EXPECT_EQ(*five_sv, 5);
EXPECT_EQ(*six_cstr, 6);
EXPECT_EQ(*six_str, 6);
EXPECT_EQ(*six_sv, 6);
EXPECT_EQ(*one_cstr, 1);
EXPECT_EQ(*one_str, 1);
EXPECT_EQ(*one_sv, 1);
EXPECT_EQ(*seven_cstr, 7);
EXPECT_EQ(*seven_str, 7);
EXPECT_EQ(*seven_sv, 7);
}
TEST(Hashmap, Iterator) {
using Map = Hashmap<int, std::string, 8>;
using Entry = typename Map::Entry;
Map map;
map.Add(1, "one");
map.Add(4, "four");
map.Add(3, "three");
map.Add(2, "two");
EXPECT_THAT(map, testing::UnorderedElementsAre(Entry{1, "one"}, Entry{2, "two"},
Entry{3, "three"}, Entry{4, "four"}));
}
TEST(Hashmap, MutableIterator) {
using Map = Hashmap<int, std::string, 8>;
using Entry = typename Map::Entry;
Map map;
map.Add(1, "one");
map.Add(4, "four");
map.Add(3, "three");
map.Add(2, "two");
for (auto pair : map) {
pair.value += "!";
}
EXPECT_THAT(map, testing::UnorderedElementsAre(Entry{1, "one!"}, Entry{2, "two!"},
Entry{3, "three!"}, Entry{4, "four!"}));
}
TEST(Hashmap, KeysValues) {
using Map = Hashmap<int, std::string, 8>;
Map map;
map.Add(1, "one");
map.Add(4, "four");
map.Add(3, "three");
map.Add(2, "two");
EXPECT_THAT(map.Keys(), testing::UnorderedElementsAre(1, 2, 3, 4));
EXPECT_THAT(map.Values(), testing::UnorderedElementsAre("one", "two", "three", "four"));
}
TEST(Hashmap, AddMany) {
Hashmap<int, std::string, 8> map;
for (size_t i = 0; i < kPrimes.size(); i++) {
int prime = kPrimes[i];
ASSERT_TRUE(map.Add(prime, std::to_string(prime))) << "i: " << i;
ASSERT_FALSE(map.Add(prime, std::to_string(prime))) << "i: " << i;
ASSERT_EQ(map.Count(), i + 1);
}
ASSERT_EQ(map.Count(), kPrimes.size());
for (int prime : kPrimes) {
ASSERT_TRUE(map.Contains(prime)) << prime;
ASSERT_EQ(map.Get(prime), std::to_string(prime)) << prime;
}
}
TEST(Hashmap, GetOrCreate) {
Hashmap<int, std::string, 8> map;
std::optional<std::string> value_of_key_0_at_create;
EXPECT_EQ(map.GetOrCreate(0,
[&] {
value_of_key_0_at_create = map.Get(0);
return "zero";
}),
"zero");
EXPECT_EQ(map.Count(), 1u);
EXPECT_EQ(map.Get(0), "zero");
EXPECT_EQ(value_of_key_0_at_create, "");
bool create_called = false;
EXPECT_EQ(map.GetOrCreate(0,
[&] {
create_called = true;
return "oh noes";
}),
"zero");
EXPECT_FALSE(create_called);
EXPECT_EQ(map.Count(), 1u);
EXPECT_EQ(map.Get(0), "zero");
EXPECT_EQ(map.GetOrCreate(1, [&] { return "one"; }), "one");
EXPECT_EQ(map.Count(), 2u);
EXPECT_EQ(map.Get(1), "one");
}
TEST(Hashmap, GetOrCreate_CreateModifiesMap) {
Hashmap<int, std::string, 8> map;
EXPECT_EQ(map.GetOrCreate(0,
[&] {
map.Add(3, "three");
map.Add(1, "one");
map.Add(2, "two");
return "zero";
}),
"zero");
EXPECT_EQ(map.Count(), 4u);
EXPECT_EQ(map.Get(0), "zero");
EXPECT_EQ(map.Get(1), "one");
EXPECT_EQ(map.Get(2), "two");
EXPECT_EQ(map.Get(3), "three");
bool create_called = false;
EXPECT_EQ(map.GetOrCreate(0,
[&] {
create_called = true;
return "oh noes";
}),
"zero");
EXPECT_FALSE(create_called);
EXPECT_EQ(map.Count(), 4u);
EXPECT_EQ(map.Get(0), "zero");
EXPECT_EQ(map.Get(1), "one");
EXPECT_EQ(map.Get(2), "two");
EXPECT_EQ(map.Get(3), "three");
EXPECT_EQ(map.GetOrCreate(4,
[&] {
map.Add(6, "six");
map.Add(5, "five");
map.Add(7, "seven");
return "four";
}),
"four");
EXPECT_EQ(map.Count(), 8u);
EXPECT_EQ(map.Get(0), "zero");
EXPECT_EQ(map.Get(1), "one");
EXPECT_EQ(map.Get(2), "two");
EXPECT_EQ(map.Get(3), "three");
EXPECT_EQ(map.Get(4), "four");
EXPECT_EQ(map.Get(5), "five");
EXPECT_EQ(map.Get(6), "six");
EXPECT_EQ(map.Get(7), "seven");
}
TEST(Hashmap, GetOrCreate_CreateAddsSameKeyedValue) {
Hashmap<int, std::string, 8> map;
EXPECT_EQ(map.GetOrCreate(42,
[&] {
map.Add(42, "should-be-replaced");
return "expected-value";
}),
"expected-value");
EXPECT_EQ(map.Count(), 1u);
EXPECT_EQ(map.Get(42), "expected-value");
}
TEST(Hashmap, Soak) {
std::mt19937 rnd;
std::unordered_map<std::string, std::string> reference;
Hashmap<std::string, std::string, 8> map;
for (size_t i = 0; i < 1000000; i++) {
std::string key = std::to_string(rnd() & 64);
std::string value = "V" + key;
switch (rnd() % 7) {
case 0: { // Add
auto expected = reference.emplace(key, value).second;
EXPECT_EQ(map.Add(key, value), expected) << "i:" << i;
EXPECT_EQ(map.Get(key), value) << "i:" << i;
EXPECT_TRUE(map.Contains(key)) << "i:" << i;
break;
}
case 1: { // Replace
reference[key] = value;
map.Replace(key, value);
EXPECT_EQ(map.Get(key), value) << "i:" << i;
EXPECT_TRUE(map.Contains(key)) << "i:" << i;
break;
}
case 2: { // Remove
auto expected = reference.erase(key) != 0;
EXPECT_EQ(map.Remove(key), expected) << "i:" << i;
EXPECT_FALSE(map.Get(key).has_value()) << "i:" << i;
EXPECT_FALSE(map.Contains(key)) << "i:" << i;
break;
}
case 3: { // Contains
auto expected = reference.count(key) != 0;
EXPECT_EQ(map.Contains(key), expected) << "i:" << i;
break;
}
case 4: { // Get
if (reference.count(key) != 0) {
auto expected = reference[key];
EXPECT_EQ(map.Get(key), expected) << "i:" << i;
} else {
EXPECT_FALSE(map.Get(key).has_value()) << "i:" << i;
}
break;
}
case 5: { // Copy / Move
Hashmap<std::string, std::string, 8> tmp(map);
map = std::move(tmp);
break;
}
case 6: { // Clear
reference.clear();
map.Clear();
break;
}
}
}
}
TEST(Hashmap, EqualitySameSize) {
Hashmap<int, std::string, 8> a;
Hashmap<int, std::string, 8> b;
EXPECT_EQ(a, b);
a.Add(1, "one");
EXPECT_NE(a, b);
b.Add(2, "two");
EXPECT_NE(a, b);
a.Add(2, "two");
EXPECT_NE(a, b);
b.Add(1, "one");
EXPECT_EQ(a, b);
}
TEST(Hashmap, EqualityDifferentSize) {
Hashmap<int, std::string, 8> a;
Hashmap<int, std::string, 4> b;
EXPECT_EQ(a, b);
a.Add(1, "one");
EXPECT_NE(a, b);
b.Add(2, "two");
EXPECT_NE(a, b);
a.Add(2, "two");
EXPECT_NE(a, b);
b.Add(1, "one");
EXPECT_EQ(a, b);
}
TEST(Hashmap, HashSameSize) {
Hashmap<int, std::string, 8> a;
Hashmap<int, std::string, 8> b;
EXPECT_EQ(Hash(a), Hash(b));
a.Add(1, "one");
b.Add(2, "two");
a.Add(2, "two");
b.Add(1, "one");
EXPECT_EQ(Hash(a), Hash(b));
}
TEST(Hashmap, HashDifferentSize) {
Hashmap<int, std::string, 8> a;
Hashmap<int, std::string, 4> b;
EXPECT_EQ(Hash(a), Hash(b));
a.Add(1, "one");
b.Add(2, "two");
a.Add(2, "two");
b.Add(1, "one");
EXPECT_EQ(Hash(a), Hash(b));
}
} // namespace
} // namespace tint