gfe-relnote: n/a(new class type not in use) Add SimpleLinkedHashMap which is forked from chromium linked_hash_map.h. This class is not used in google3, but used by other platform, i.e. chromium, envoy, etc. PiperOrigin-RevId: 245234098 Change-Id: Id453c101c9d191ae509ceb4f92c85a7486802e60
diff --git a/common/platform/api/quiche_ptr_util.h b/common/platform/api/quiche_ptr_util.h new file mode 100644 index 0000000..26b152b --- /dev/null +++ b/common/platform/api/quiche_ptr_util.h
@@ -0,0 +1,21 @@ +// 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. + +#ifndef QUICHE_COMMON_PLATFORM_API_QUICHE_PTR_UTIL_H_ +#define QUICHE_COMMON_PLATFORM_API_QUICHE_PTR_UTIL_H_ + +#include <memory> + +#include "net/quiche/common/platform/impl/quiche_ptr_util_impl.h" + +namespace quiche { + +template <typename T, typename... Args> +std::unique_ptr<T> QuicheMakeUnique(Args&&... args) { + return QuicheMakeUniqueImpl<T>(std::forward<Args>(args)...); +} + +} // namespace quiche + +#endif // QUICHE_COMMON_PLATFORM_API_QUICHE_PTR_UTIL_H_
diff --git a/common/platform/api/quiche_test.h b/common/platform/api/quiche_test.h new file mode 100644 index 0000000..f51c85e --- /dev/null +++ b/common/platform/api/quiche_test.h
@@ -0,0 +1,10 @@ +// 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. + +#ifndef QUICHE_COMMON_PLATFORM_API_QUICHE_TEST_H_ +#define QUICHE_COMMON_PLATFORM_API_QUICHE_TEST_H_ + +#include "net/quiche/common/platform/impl/quiche_test_impl.h" + +#endif // QUICHE_COMMON_PLATFORM_API_QUICHE_TEST_H_
diff --git a/common/platform/api/quiche_unordered_containers.h b/common/platform/api/quiche_unordered_containers.h new file mode 100644 index 0000000..583f97e --- /dev/null +++ b/common/platform/api/quiche_unordered_containers.h
@@ -0,0 +1,24 @@ +// 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. + +#ifndef QUICHE_COMMON_PLATFORM_API_QUICHE_UNORDERED_CONTAINERS_H_ +#define QUICHE_COMMON_PLATFORM_API_QUICHE_UNORDERED_CONTAINERS_H_ + +#include "net/quiche/common/platform/impl/quiche_unordered_containers_impl.h" + +namespace quiche { + +// The default hasher used by hash tables. +template <typename Key> +using QuicheDefaultHasher = QuicheDefaultHasherImpl<Key>; + +// A general-purpose unordered map. +template <typename Key, + typename Value, + typename Hash = QuicheDefaultHasher<Key>> +using QuicheUnorderedMap = QuicheUnorderedMapImpl<Key, Value, Hash>; + +} // namespace quiche + +#endif // QUICHE_COMMON_PLATFORM_API_QUICHE_UNORDERED_CONTAINERS_H_
diff --git a/common/simple_linked_hash_map.h b/common/simple_linked_hash_map.h new file mode 100644 index 0000000..8ff1a2b --- /dev/null +++ b/common/simple_linked_hash_map.h
@@ -0,0 +1,245 @@ +// 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. + +// This is a simplistic insertion-ordered map. It behaves similarly to an STL +// map, but only implements a small subset of the map's methods. Internally, we +// just keep a map and a list going in parallel. +// +// This class provides no thread safety guarantees, beyond what you would +// normally see with std::list. +// +// Iterators point into the list and should be stable in the face of +// mutations, except for an iterator pointing to an element that was just +// deleted. + +#ifndef QUICHE_COMMON_SIMPLE_LINKED_HASH_MAP_H_ +#define QUICHE_COMMON_SIMPLE_LINKED_HASH_MAP_H_ + +#include <list> +#include <tuple> +#include <type_traits> +#include <utility> + +#include "net/third_party/quiche/src/common/platform/api/quiche_unordered_containers.h" + +namespace quiche { + +// This holds a list of pair<Key, Value> items. This list is what gets +// traversed, and it's iterators from this list that we return from +// begin/end/find. +// +// We also keep a set<list::iterator> for find. Since std::list is a +// doubly-linked list, the iterators should remain stable. + +template <class Key, class Value, class Hash = std::hash<Key>> +class SimpleLinkedHashMap { + private: + typedef std::list<std::pair<Key, Value>> ListType; + typedef QuicheUnorderedMap<Key, typename ListType::iterator, Hash> MapType; + + public: + typedef typename ListType::iterator iterator; + typedef typename ListType::reverse_iterator reverse_iterator; + typedef typename ListType::const_iterator const_iterator; + typedef typename ListType::const_reverse_iterator const_reverse_iterator; + typedef typename MapType::key_type key_type; + typedef typename ListType::value_type value_type; + typedef typename ListType::size_type size_type; + + SimpleLinkedHashMap() = default; + explicit SimpleLinkedHashMap(size_type bucket_count) : map_(bucket_count) {} + + SimpleLinkedHashMap(const SimpleLinkedHashMap& other) = delete; + SimpleLinkedHashMap& operator=(const SimpleLinkedHashMap& other) = delete; + SimpleLinkedHashMap(SimpleLinkedHashMap&& other) = default; + SimpleLinkedHashMap& operator=(SimpleLinkedHashMap&& other) = default; + + // Returns an iterator to the first (insertion-ordered) element. Like a map, + // this can be dereferenced to a pair<Key, Value>. + iterator begin() { return list_.begin(); } + const_iterator begin() const { return list_.begin(); } + + // Returns an iterator beyond the last element. + iterator end() { return list_.end(); } + const_iterator end() const { return list_.end(); } + + // Returns an iterator to the last (insertion-ordered) element. Like a map, + // this can be dereferenced to a pair<Key, Value>. + reverse_iterator rbegin() { return list_.rbegin(); } + const_reverse_iterator rbegin() const { return list_.rbegin(); } + + // Returns an iterator beyond the first element. + reverse_iterator rend() { return list_.rend(); } + const_reverse_iterator rend() const { return list_.rend(); } + + // Front and back accessors common to many stl containers. + + // Returns the earliest-inserted element + const value_type& front() const { return list_.front(); } + + // Returns the earliest-inserted element. + value_type& front() { return list_.front(); } + + // Returns the most-recently-inserted element. + const value_type& back() const { return list_.back(); } + + // Returns the most-recently-inserted element. + value_type& back() { return list_.back(); } + + // Clears the map of all values. + void clear() { + map_.clear(); + list_.clear(); + } + + // Returns true iff the map is empty. + bool empty() const { return list_.empty(); } + + // Removes the first element from the list. + void pop_front() { erase(begin()); } + + // Erases values with the provided key. Returns the number of elements + // erased. In this implementation, this will be 0 or 1. + size_type erase(const Key& key) { + typename MapType::iterator found = map_.find(key); + if (found == map_.end()) { + return 0; + } + + list_.erase(found->second); + map_.erase(found); + + return 1; + } + + // Erases the item that 'position' points to. Returns an iterator that points + // to the item that comes immediately after the deleted item in the list, or + // end(). + // If the provided iterator is invalid or there is inconsistency between the + // map and list, a CHECK() error will occur. + iterator erase(iterator position) { + typename MapType::iterator found = map_.find(position->first); + CHECK(found->second == position) + << "Inconsisent iterator for map and list, or the iterator is invalid."; + + map_.erase(found); + return list_.erase(position); + } + + // Erases all the items in the range [first, last). Returns an iterator that + // points to the item that comes immediately after the last deleted item in + // the list, or end(). + iterator erase(iterator first, iterator last) { + while (first != last && first != end()) { + first = erase(first); + } + return first; + } + + // Finds the element with the given key. Returns an iterator to the + // value found, or to end() if the value was not found. Like a map, this + // iterator points to a pair<Key, Value>. + iterator find(const Key& key) { + typename MapType::iterator found = map_.find(key); + if (found == map_.end()) { + return end(); + } + return found->second; + } + + const_iterator find(const Key& key) const { + typename MapType::const_iterator found = map_.find(key); + if (found == map_.end()) { + return end(); + } + return found->second; + } + + bool contains(const Key& key) const { return find(key) != end(); } + + // Returns the value mapped to key, or an inserted iterator to that position + // in the map. + Value& operator[](const key_type& key) { + return (*((this->insert(std::make_pair(key, Value()))).first)).second; + } + + // Inserts an element into the map + std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { + // First make sure the map doesn't have a key with this value. If it does, + // return a pair with an iterator to it, and false indicating that we + // didn't insert anything. + typename MapType::iterator found = map_.find(pair.first); + if (found != map_.end()) { + return std::make_pair(found->second, false); + } + + // Otherwise, insert into the list first. + list_.push_back(pair); + + // Obtain an iterator to the newly added element. We do -- instead of - + // since list::iterator doesn't implement operator-(). + typename ListType::iterator last = list_.end(); + --last; + + CHECK(map_.insert(std::make_pair(pair.first, last)).second) + << "Map and list are inconsistent"; + + return std::make_pair(last, true); + } + + // Inserts an element into the map + std::pair<iterator, bool> insert(std::pair<Key, Value>&& pair) { + // First make sure the map doesn't have a key with this value. If it does, + // return a pair with an iterator to it, and false indicating that we + // didn't insert anything. + typename MapType::iterator found = map_.find(pair.first); + if (found != map_.end()) { + return std::make_pair(found->second, false); + } + + // Otherwise, insert into the list first. + list_.push_back(std::move(pair)); + + // Obtain an iterator to the newly added element. We do -- instead of - + // since list::iterator doesn't implement operator-(). + typename ListType::iterator last = list_.end(); + --last; + + CHECK(map_.insert(std::make_pair(pair.first, last)).second) + << "Map and list are inconsistent"; + return std::make_pair(last, true); + } + + size_type size() const { return list_.size(); } + + template <typename... Args> + std::pair<iterator, bool> emplace(Args&&... args) { + ListType node_donor; + auto node_pos = + node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); + const auto& k = node_pos->first; + auto ins = map_.insert({k, node_pos}); + if (!ins.second) { + return {ins.first->second, false}; + } + list_.splice(list_.end(), node_donor, node_pos); + return {ins.first->second, true}; + } + + void swap(SimpleLinkedHashMap& other) { + map_.swap(other.map_); + list_.swap(other.list_); + } + + private: + // The map component, used for speedy lookups + MapType map_; + + // The list component, used for maintaining insertion order + ListType list_; +}; + +} // namespace quiche + +#endif // QUICHE_COMMON_SIMPLE_LINKED_HASH_MAP_H_
diff --git a/common/simple_linked_hash_map_test.cc b/common/simple_linked_hash_map_test.cc new file mode 100644 index 0000000..00179b3 --- /dev/null +++ b/common/simple_linked_hash_map_test.cc
@@ -0,0 +1,396 @@ +// 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 SimpleLinkedHashMap. + +#include "net/third_party/quiche/src/common/simple_linked_hash_map.h" + +#include <memory> +#include <utility> + +#include "net/third_party/quiche/src/common/platform/api/quiche_ptr_util.h" +#include "net/third_party/quiche/src/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. + SimpleLinkedHashMap<int, std::unique_ptr<int>> m; + m[2] = QuicheMakeUnique<int>(12); + m[3] = QuicheMakeUnique<int>(13); + SimpleLinkedHashMap<int, std::unique_ptr<int>> n = std::move(m); + EXPECT_THAT(n, + UnorderedElementsAre(Pair(2, Pointee(12)), Pair(3, Pointee(13)))); +} + +TEST(LinkedHashMapTest, CanEmplaceMoveOnly) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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)); + + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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)); + + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<int, int> m; + ASSERT_EQ(0u, m.size()); + EXPECT_EQ(0, m.erase(2)); // Nothing to erase yet + + m.insert(std::make_pair(2, 12)); + ASSERT_EQ(1u, m.size()); + EXPECT_EQ(1, m.erase(2)); + EXPECT_EQ(0u, m.size()); + + EXPECT_EQ(0, m.erase(2)); // Make sure nothing bad happens if we repeat. + EXPECT_EQ(0u, m.size()); +} + +TEST(LinkedHashMapTest, Erase2) { + SimpleLinkedHashMap<int, int> m; + ASSERT_EQ(0u, m.size()); + EXPECT_EQ(0, 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(1, m.erase(1)); + EXPECT_EQ(1, m.erase(3)); + + EXPECT_EQ(2u, m.size()); + + // Make sure we can still iterate over everything that's left. + SimpleLinkedHashMap<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(0, m.erase(1)); // Make sure nothing bad happens if we repeat. + ASSERT_EQ(2u, m.size()); + + EXPECT_EQ(1, m.erase(2)); + EXPECT_EQ(1, m.erase(4)); + ASSERT_EQ(0u, m.size()); + + EXPECT_EQ(0, 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) { + SimpleLinkedHashMap<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 + SimpleLinkedHashMap<int, int>::iterator it2 = m.find(2); + SimpleLinkedHashMap<int, int>::iterator it4 = m.find(4); + EXPECT_EQ(m.erase(it2, it4), m.find(4)); + EXPECT_EQ(2, m.size()); + + // Make sure we can still iterate over everything that's left. + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<int, int> m; + ASSERT_EQ(0u, m.size()); + std::pair<SimpleLinkedHashMap<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)); + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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<SimpleLinkedHashMap<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)); + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<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) { + SimpleLinkedHashMap<int, int> m1; + SimpleLinkedHashMap<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; } + }; + SimpleLinkedHashMap<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