blob: 1a3aa7976174c7cfa1d23c59a4f41bcdffeab00d [file] [log] [blame]
// Copyright (c) 2019 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Tests QuicheLinkedHashMap.
#include "quiche/common/quiche_linked_hash_map.h"
#include <memory>
#include <tuple>
#include <utility>
#include "quiche/common/platform/api/quiche_test.h"
using testing::Pair;
using testing::Pointee;
using testing::UnorderedElementsAre;
namespace quiche {
namespace test {
// Tests that move constructor works.
TEST(LinkedHashMapTest, Move) {
// Use unique_ptr as an example of a non-copyable type.
QuicheLinkedHashMap<int, std::unique_ptr<int>> m;
m[2] = std::make_unique<int>(12);
m[3] = std::make_unique<int>(13);
QuicheLinkedHashMap<int, std::unique_ptr<int>> n = std::move(m);
EXPECT_THAT(n,
UnorderedElementsAre(Pair(2, Pointee(12)), Pair(3, Pointee(13))));
}
TEST(LinkedHashMapTest, CanEmplaceMoveOnly) {
QuicheLinkedHashMap<int, std::unique_ptr<int>> m;
struct Data {
int k, v;
};
const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}};
for (const auto& kv : data) {
m.emplace(std::piecewise_construct, std::make_tuple(kv.k),
std::make_tuple(new int{kv.v}));
}
EXPECT_TRUE(m.contains(2));
auto found = m.find(2);
ASSERT_TRUE(found != m.end());
EXPECT_EQ(234, *found->second);
}
struct NoCopy {
explicit NoCopy(int x) : x(x) {}
NoCopy(const NoCopy&) = delete;
NoCopy& operator=(const NoCopy&) = delete;
NoCopy(NoCopy&&) = delete;
NoCopy& operator=(NoCopy&&) = delete;
int x;
};
TEST(LinkedHashMapTest, CanEmplaceNoMoveNoCopy) {
QuicheLinkedHashMap<int, NoCopy> m;
struct Data {
int k, v;
};
const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}};
for (const auto& kv : data) {
m.emplace(std::piecewise_construct, std::make_tuple(kv.k),
std::make_tuple(kv.v));
}
EXPECT_TRUE(m.contains(2));
auto found = m.find(2);
ASSERT_TRUE(found != m.end());
EXPECT_EQ(234, found->second.x);
}
TEST(LinkedHashMapTest, ConstKeys) {
QuicheLinkedHashMap<int, int> m;
m.insert(std::make_pair(1, 2));
// Test that keys are const in iteration.
std::pair<int, int>& p = *m.begin();
EXPECT_EQ(1, p.first);
}
// Tests that iteration from begin() to end() works
TEST(LinkedHashMapTest, Iteration) {
QuicheLinkedHashMap<int, int> m;
EXPECT_TRUE(m.begin() == m.end());
m.insert(std::make_pair(2, 12));
m.insert(std::make_pair(1, 11));
m.insert(std::make_pair(3, 13));
QuicheLinkedHashMap<int, int>::iterator i = m.begin();
ASSERT_TRUE(m.begin() == i);
ASSERT_TRUE(m.end() != i);
EXPECT_EQ(2, i->first);
EXPECT_EQ(12, i->second);
++i;
ASSERT_TRUE(m.end() != i);
EXPECT_EQ(1, i->first);
EXPECT_EQ(11, i->second);
++i;
ASSERT_TRUE(m.end() != i);
EXPECT_EQ(3, i->first);
EXPECT_EQ(13, i->second);
++i; // Should be the end of the line.
ASSERT_TRUE(m.end() == i);
}
// Tests that reverse iteration from rbegin() to rend() works
TEST(LinkedHashMapTest, ReverseIteration) {
QuicheLinkedHashMap<int, int> m;
EXPECT_TRUE(m.rbegin() == m.rend());
m.insert(std::make_pair(2, 12));
m.insert(std::make_pair(1, 11));
m.insert(std::make_pair(3, 13));
QuicheLinkedHashMap<int, int>::reverse_iterator i = m.rbegin();
ASSERT_TRUE(m.rbegin() == i);
ASSERT_TRUE(m.rend() != i);
EXPECT_EQ(3, i->first);
EXPECT_EQ(13, i->second);
++i;
ASSERT_TRUE(m.rend() != i);
EXPECT_EQ(1, i->first);
EXPECT_EQ(11, i->second);
++i;
ASSERT_TRUE(m.rend() != i);
EXPECT_EQ(2, i->first);
EXPECT_EQ(12, i->second);
++i; // Should be the end of the line.
ASSERT_TRUE(m.rend() == i);
}
// Tests that clear() works
TEST(LinkedHashMapTest, Clear) {
QuicheLinkedHashMap<int, int> m;
m.insert(std::make_pair(2, 12));
m.insert(std::make_pair(1, 11));
m.insert(std::make_pair(3, 13));
ASSERT_EQ(3u, m.size());
m.clear();
EXPECT_EQ(0u, m.size());
m.clear(); // Make sure we can call it on an empty map.
EXPECT_EQ(0u, m.size());
}
// Tests that size() works.
TEST(LinkedHashMapTest, Size) {
QuicheLinkedHashMap<int, int> m;
EXPECT_EQ(0u, m.size());
m.insert(std::make_pair(2, 12));
EXPECT_EQ(1u, m.size());
m.insert(std::make_pair(1, 11));
EXPECT_EQ(2u, m.size());
m.insert(std::make_pair(3, 13));
EXPECT_EQ(3u, m.size());
m.clear();
EXPECT_EQ(0u, m.size());
}
// Tests empty()
TEST(LinkedHashMapTest, Empty) {
QuicheLinkedHashMap<int, int> m;
ASSERT_TRUE(m.empty());
m.insert(std::make_pair(2, 12));
ASSERT_FALSE(m.empty());
m.clear();
ASSERT_TRUE(m.empty());
}
TEST(LinkedHashMapTest, Erase) {
QuicheLinkedHashMap<int, int> m;
ASSERT_EQ(0u, m.size());
EXPECT_EQ(0u, m.erase(2)); // Nothing to erase yet
m.insert(std::make_pair(2, 12));
ASSERT_EQ(1u, m.size());
EXPECT_EQ(1u, m.erase(2));
EXPECT_EQ(0u, m.size());
EXPECT_EQ(0u, m.erase(2)); // Make sure nothing bad happens if we repeat.
EXPECT_EQ(0u, m.size());
}
TEST(LinkedHashMapTest, Erase2) {
QuicheLinkedHashMap<int, int> m;
ASSERT_EQ(0u, m.size());
EXPECT_EQ(0u, m.erase(2)); // Nothing to erase yet
m.insert(std::make_pair(2, 12));
m.insert(std::make_pair(1, 11));
m.insert(std::make_pair(3, 13));
m.insert(std::make_pair(4, 14));
ASSERT_EQ(4u, m.size());
// Erase middle two
EXPECT_EQ(1u, m.erase(1));
EXPECT_EQ(1u, m.erase(3));
EXPECT_EQ(2u, m.size());
// Make sure we can still iterate over everything that's left.
QuicheLinkedHashMap<int, int>::iterator it = m.begin();
ASSERT_TRUE(it != m.end());
EXPECT_EQ(12, it->second);
++it;
ASSERT_TRUE(it != m.end());
EXPECT_EQ(14, it->second);
++it;
ASSERT_TRUE(it == m.end());
EXPECT_EQ(0u, m.erase(1)); // Make sure nothing bad happens if we repeat.
ASSERT_EQ(2u, m.size());
EXPECT_EQ(1u, m.erase(2));
EXPECT_EQ(1u, m.erase(4));
ASSERT_EQ(0u, m.size());
EXPECT_EQ(0u, m.erase(1)); // Make sure nothing bad happens if we repeat.
ASSERT_EQ(0u, m.size());
}
// Test that erase(iter,iter) and erase(iter) compile and work.
TEST(LinkedHashMapTest, Erase3) {
QuicheLinkedHashMap<int, int> m;
m.insert(std::make_pair(1, 11));
m.insert(std::make_pair(2, 12));
m.insert(std::make_pair(3, 13));
m.insert(std::make_pair(4, 14));
// Erase middle two
QuicheLinkedHashMap<int, int>::iterator it2 = m.find(2);
QuicheLinkedHashMap<int, int>::iterator it4 = m.find(4);
EXPECT_EQ(m.erase(it2, it4), m.find(4));
EXPECT_EQ(2u, m.size());
// Make sure we can still iterate over everything that's left.
QuicheLinkedHashMap<int, int>::iterator it = m.begin();
ASSERT_TRUE(it != m.end());
EXPECT_EQ(11, it->second);
++it;
ASSERT_TRUE(it != m.end());
EXPECT_EQ(14, it->second);
++it;
ASSERT_TRUE(it == m.end());
// Erase first one using an iterator.
EXPECT_EQ(m.erase(m.begin()), m.find(4));
// Only the last element should be left.
it = m.begin();
ASSERT_TRUE(it != m.end());
EXPECT_EQ(14, it->second);
++it;
ASSERT_TRUE(it == m.end());
}
TEST(LinkedHashMapTest, Insertion) {
QuicheLinkedHashMap<int, int> m;
ASSERT_EQ(0u, m.size());
std::pair<QuicheLinkedHashMap<int, int>::iterator, bool> result;
result = m.insert(std::make_pair(2, 12));
ASSERT_EQ(1u, m.size());
EXPECT_TRUE(result.second);
EXPECT_EQ(2, result.first->first);
EXPECT_EQ(12, result.first->second);
result = m.insert(std::make_pair(1, 11));
ASSERT_EQ(2u, m.size());
EXPECT_TRUE(result.second);
EXPECT_EQ(1, result.first->first);
EXPECT_EQ(11, result.first->second);
result = m.insert(std::make_pair(3, 13));
QuicheLinkedHashMap<int, int>::iterator result_iterator = result.first;
ASSERT_EQ(3u, m.size());
EXPECT_TRUE(result.second);
EXPECT_EQ(3, result.first->first);
EXPECT_EQ(13, result.first->second);
result = m.insert(std::make_pair(3, 13));
EXPECT_EQ(3u, m.size());
EXPECT_FALSE(result.second) << "No insertion should have occurred.";
EXPECT_TRUE(result_iterator == result.first)
<< "Duplicate insertion should have given us the original iterator.";
}
static std::pair<int, int> Pair(int i, int j) { return {i, j}; }
// Test front accessors.
TEST(LinkedHashMapTest, Front) {
QuicheLinkedHashMap<int, int> m;
m.insert(std::make_pair(2, 12));
m.insert(std::make_pair(1, 11));
m.insert(std::make_pair(3, 13));
EXPECT_EQ(3u, m.size());
EXPECT_EQ(Pair(2, 12), m.front());
m.pop_front();
EXPECT_EQ(2u, m.size());
EXPECT_EQ(Pair(1, 11), m.front());
m.pop_front();
EXPECT_EQ(1u, m.size());
EXPECT_EQ(Pair(3, 13), m.front());
m.pop_front();
EXPECT_TRUE(m.empty());
}
TEST(LinkedHashMapTest, Find) {
QuicheLinkedHashMap<int, int> m;
EXPECT_TRUE(m.end() == m.find(1))
<< "We shouldn't find anything in an empty map.";
m.insert(std::make_pair(2, 12));
EXPECT_TRUE(m.end() == m.find(1))
<< "We shouldn't find an element that doesn't exist in the map.";
std::pair<QuicheLinkedHashMap<int, int>::iterator, bool> result =
m.insert(std::make_pair(1, 11));
ASSERT_TRUE(result.second);
ASSERT_TRUE(m.end() != result.first);
EXPECT_TRUE(result.first == m.find(1))
<< "We should have found an element we know exists in the map.";
EXPECT_EQ(11, result.first->second);
// Check that a follow-up insertion doesn't affect our original
m.insert(std::make_pair(3, 13));
QuicheLinkedHashMap<int, int>::iterator it = m.find(1);
ASSERT_TRUE(m.end() != it);
EXPECT_EQ(11, it->second);
m.clear();
EXPECT_TRUE(m.end() == m.find(1))
<< "We shouldn't find anything in a map that we've cleared.";
}
TEST(LinkedHashMapTest, Contains) {
QuicheLinkedHashMap<int, int> m;
EXPECT_FALSE(m.contains(1)) << "An empty map shouldn't contain anything.";
m.insert(std::make_pair(2, 12));
EXPECT_FALSE(m.contains(1))
<< "The map shouldn't contain an element that doesn't exist.";
m.insert(std::make_pair(1, 11));
EXPECT_TRUE(m.contains(1))
<< "The map should contain an element that we know exists.";
m.clear();
EXPECT_FALSE(m.contains(1))
<< "A map that we've cleared shouldn't contain anything.";
}
TEST(LinkedHashMapTest, Swap) {
QuicheLinkedHashMap<int, int> m1;
QuicheLinkedHashMap<int, int> m2;
m1.insert(std::make_pair(1, 1));
m1.insert(std::make_pair(2, 2));
m2.insert(std::make_pair(3, 3));
ASSERT_EQ(2u, m1.size());
ASSERT_EQ(1u, m2.size());
m1.swap(m2);
ASSERT_EQ(1u, m1.size());
ASSERT_EQ(2u, m2.size());
}
TEST(LinkedHashMapTest, CustomHashAndEquality) {
struct CustomIntHash {
size_t operator()(int x) const { return x; }
};
QuicheLinkedHashMap<int, int, CustomIntHash> m;
m.insert(std::make_pair(1, 1));
EXPECT_TRUE(m.contains(1));
EXPECT_EQ(1, m[1]);
}
} // namespace test
} // namespace quiche