1e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier/* 2e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * Copyright (C) 2014 The Android Open Source Project 3e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * 4e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * Licensed under the Apache License, Version 2.0 (the "License"); 5e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * you may not use this file except in compliance with the License. 6e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * You may obtain a copy of the License at 7e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * 8e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * http://www.apache.org/licenses/LICENSE-2.0 9e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * 10e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * Unless required by applicable law or agreed to in writing, software 11e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * distributed under the License is distributed on an "AS IS" BASIS, 12e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * See the License for the specific language governing permissions and 14e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier * limitations under the License. 15e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier */ 16e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 17e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include "hash_set.h" 18e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 19e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include <map> 20e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include <sstream> 21e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include <string> 22e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include <unordered_set> 23e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 24e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include "common_runtime_test.h" 25564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier#include "hash_map.h" 26e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 27e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartiernamespace art { 28e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 29564ff985184737977aa26c485d0c1a413e530705Mathieu Chartierstruct IsEmptyFnString { 30e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier void MakeEmpty(std::string& item) const { 31e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier item.clear(); 32e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 33e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier bool IsEmpty(const std::string& item) const { 34e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier return item.empty(); 35e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 36e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier}; 37e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 38e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartierclass HashSetTest : public CommonRuntimeTest { 39e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier public: 40e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSetTest() : seed_(97421), unique_number_(0) { 41e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 42e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::string RandomString(size_t len) { 43e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::ostringstream oss; 44e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < len; ++i) { 45e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier oss << static_cast<char>('A' + PRand() % 64); 46e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 47564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier static_assert(' ' < 'A', "space must be less than a"); 48e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier oss << " " << unique_number_++; // Relies on ' ' < 'A' 49e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier return oss.str(); 50e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 51e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier void SetSeed(size_t seed) { 52e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier seed_ = seed; 53e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 54e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t PRand() { // Pseudo random. 55e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier seed_ = seed_ * 1103515245 + 12345; 56e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier return seed_; 57e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 58e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 59e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier private: 60e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t seed_; 61e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t unique_number_; 62e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier}; 63e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 64e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestSmoke) { 65e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 66e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const std::string test_string = "hello world 1234"; 67e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.Empty()); 68e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Size(), 0U); 69e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(test_string); 70e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(test_string); 71e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, test_string); 72e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto after_it = hash_set.Erase(it); 73e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(after_it == hash_set.end()); 74e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.Empty()); 75e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Size(), 0U); 76e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier it = hash_set.Find(test_string); 77e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it == hash_set.end()); 78e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 79e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 80e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestInsertAndErase) { 81e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 82e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t count = 1000; 83e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 84e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 85e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Insert a bunch of elements and make sure we can find them. 86e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 87e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(strings[i]); 88e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 89e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it != hash_set.end()); 90e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, strings[i]); 91e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 92e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(strings.size(), hash_set.Size()); 93e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Try to erase the odd strings. 94e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 1; i < count; i += 2) { 95e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 96e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it != hash_set.end()); 97e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, strings[i]); 98e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Erase(it); 99e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 100e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Test removed. 101e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 1; i < count; i += 2) { 102e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 103e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it == hash_set.end()); 104e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 105e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; i += 2) { 106e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 107e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it != hash_set.end()); 108e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, strings[i]); 109e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 110e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 111e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 112e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestIterator) { 113e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 114e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.begin() == hash_set.end()); 115e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t count = 1000; 116e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 117e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 118e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Insert a bunch of elements and make sure we can find them. 119e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 120e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(strings[i]); 121e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 122e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Make sure we visit each string exactly once. 123e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::map<std::string, size_t> found_count; 124e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (const std::string& s : hash_set) { 125e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ++found_count[s]; 126e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 127e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 128e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(found_count[strings[i]], 1U); 129e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 130e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier found_count.clear(); 131e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Remove all the elements with iterator erase. 132e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (auto it = hash_set.begin(); it != hash_set.end();) { 133e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ++found_count[*it]; 134e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier it = hash_set.Erase(it); 135e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Verify(), 0U); 136e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 137e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 138e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(found_count[strings[i]], 1U); 139e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 140e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 141e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 142e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestSwap) { 143e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_seta, hash_setb; 144e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 145e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t count = 1000; 146e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 147e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 148e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_seta.Insert(strings[i]); 149e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 150e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::swap(hash_seta, hash_setb); 151e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_seta.Insert("TEST"); 152e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_setb.Insert("TEST2"); 153e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 154e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 155e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_seta.Insert(strings[i]); 156e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 157e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 158e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 159e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestStress) { 160e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 161e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::unordered_multiset<std::string> std_set; 162e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 163e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t string_count = 2000; 164e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t operations = 100000; 165e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t target_size = 5000; 166e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < string_count; ++i) { 167e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(i % 10 + 1)); 168e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 169e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const size_t seed = time(nullptr); 170e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier SetSeed(seed); 171e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier LOG(INFO) << "Starting stress test with seed " << seed; 172e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < operations; ++i) { 173e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Size(), std_set.size()); 174e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t delta = std::abs(static_cast<ssize_t>(target_size) - 175e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static_cast<ssize_t>(hash_set.Size())); 176e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t n = PRand(); 177e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier if (n % target_size == 0) { 178e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Clear(); 179e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std_set.clear(); 180e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.Empty()); 181e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(std_set.empty()); 182e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } else if (n % target_size < delta) { 183e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Skew towards adding elements until we are at the desired size. 184e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const std::string& s = strings[PRand() % string_count]; 185e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(s); 186e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std_set.insert(s); 187e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*hash_set.Find(s), *std_set.find(s)); 188e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } else { 189e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const std::string& s = strings[PRand() % string_count]; 190e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it1 = hash_set.Find(s); 191e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it2 = std_set.find(s); 192e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(it1 == hash_set.end(), it2 == std_set.end()); 193e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier if (it1 != hash_set.end()) { 194e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it1, *it2); 195e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Erase(it1); 196e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std_set.erase(it2); 197e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 198e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 199e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 200e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 201e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 202564ff985184737977aa26c485d0c1a413e530705Mathieu Chartierstruct IsEmptyStringPair { 203564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier void MakeEmpty(std::pair<std::string, int>& pair) const { 204564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier pair.first.clear(); 205564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier } 206564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier bool IsEmpty(const std::pair<std::string, int>& pair) const { 207564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier return pair.first.empty(); 208564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier } 209564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier}; 210564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier 211564ff985184737977aa26c485d0c1a413e530705Mathieu ChartierTEST_F(HashSetTest, TestHashMap) { 212564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier HashMap<std::string, int, IsEmptyStringPair> hash_map; 213564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier hash_map.Insert(std::make_pair(std::string("abcd"), 123)); 214564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier hash_map.Insert(std::make_pair(std::string("abcd"), 124)); 215564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier hash_map.Insert(std::make_pair(std::string("bags"), 444)); 216564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier auto it = hash_map.Find(std::string("abcd")); 217564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier ASSERT_EQ(it->second, 123); 218564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier hash_map.Erase(it); 219564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier it = hash_map.Find(std::string("abcd")); 220564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier ASSERT_EQ(it->second, 124); 221564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier} 222564ff985184737977aa26c485d0c1a413e530705Mathieu Chartier 223e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} // namespace art 224