hash_set_test.cc revision e05d1d5fd86867afc7513b1c546375dba11eee50
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" 25e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier#include "utils.h" 26e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 27e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartiernamespace art { 28e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 29e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartierclass IsEmptyFnString { 30e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier public: 31e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier void MakeEmpty(std::string& item) const { 32e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier item.clear(); 33e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 34e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier bool IsEmpty(const std::string& item) const { 35e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier return item.empty(); 36e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 37e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier}; 38e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 39e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartierclass HashSetTest : public CommonRuntimeTest { 40e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier public: 41e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSetTest() : seed_(97421), unique_number_(0) { 42e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 43e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::string RandomString(size_t len) { 44e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::ostringstream oss; 45e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < len; ++i) { 46e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier oss << static_cast<char>('A' + PRand() % 64); 47e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 48e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier COMPILE_ASSERT(' ' < 'A', must_be_less_than_a); 49e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier oss << " " << unique_number_++; // Relies on ' ' < 'A' 50e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier return oss.str(); 51e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 52e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier void SetSeed(size_t seed) { 53e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier seed_ = seed; 54e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 55e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t PRand() { // Pseudo random. 56e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier seed_ = seed_ * 1103515245 + 12345; 57e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier return seed_; 58e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 59e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 60e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier private: 61e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t seed_; 62e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t unique_number_; 63e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier}; 64e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 65e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestSmoke) { 66e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 67e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const std::string test_string = "hello world 1234"; 68e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.Empty()); 69e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Size(), 0U); 70e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(test_string); 71e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(test_string); 72e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, test_string); 73e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto after_it = hash_set.Erase(it); 74e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(after_it == hash_set.end()); 75e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.Empty()); 76e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Size(), 0U); 77e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier it = hash_set.Find(test_string); 78e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it == hash_set.end()); 79e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 80e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 81e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestInsertAndErase) { 82e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 83e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t count = 1000; 84e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 85e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 86e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Insert a bunch of elements and make sure we can find them. 87e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 88e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(strings[i]); 89e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 90e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it != hash_set.end()); 91e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, strings[i]); 92e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 93e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(strings.size(), hash_set.Size()); 94e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Try to erase the odd strings. 95e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 1; i < count; i += 2) { 96e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 97e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it != hash_set.end()); 98e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, strings[i]); 99e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Erase(it); 100e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 101e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Test removed. 102e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 1; i < count; i += 2) { 103e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 104e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it == hash_set.end()); 105e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 106e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; i += 2) { 107e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it = hash_set.Find(strings[i]); 108e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(it != hash_set.end()); 109e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it, strings[i]); 110e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 111e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 112e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 113e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestIterator) { 114e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 115e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.begin() == hash_set.end()); 116e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t count = 1000; 117e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 118e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 119e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Insert a bunch of elements and make sure we can find them. 120e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 121e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(strings[i]); 122e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 123e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Make sure we visit each string exactly once. 124e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::map<std::string, size_t> found_count; 125e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (const std::string& s : hash_set) { 126e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ++found_count[s]; 127e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 128e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 129e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(found_count[strings[i]], 1U); 130e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 131e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier found_count.clear(); 132e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Remove all the elements with iterator erase. 133e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (auto it = hash_set.begin(); it != hash_set.end();) { 134e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ++found_count[*it]; 135e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier it = hash_set.Erase(it); 136e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Verify(), 0U); 137e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 138e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 139e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(found_count[strings[i]], 1U); 140e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 141e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 142e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 143e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestSwap) { 144e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_seta, hash_setb; 145e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 146e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t count = 1000; 147e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 148e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 149e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_seta.Insert(strings[i]); 150e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 151e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::swap(hash_seta, hash_setb); 152e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_seta.Insert("TEST"); 153e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_setb.Insert("TEST2"); 154e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < count; ++i) { 155e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(10)); 156e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_seta.Insert(strings[i]); 157e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 158e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 159e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 160e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu ChartierTEST_F(HashSetTest, TestStress) { 161e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier HashSet<std::string, IsEmptyFnString> hash_set; 162e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::unordered_multiset<std::string> std_set; 163e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std::vector<std::string> strings; 164e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t string_count = 2000; 165e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t operations = 100000; 166e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static constexpr size_t target_size = 5000; 167e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < string_count; ++i) { 168e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier strings.push_back(RandomString(i % 10 + 1)); 169e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 170e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const size_t seed = time(nullptr); 171e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier SetSeed(seed); 172e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier LOG(INFO) << "Starting stress test with seed " << seed; 173e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier for (size_t i = 0; i < operations; ++i) { 174e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(hash_set.Size(), std_set.size()); 175e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t delta = std::abs(static_cast<ssize_t>(target_size) - 176e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier static_cast<ssize_t>(hash_set.Size())); 177e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier size_t n = PRand(); 178e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier if (n % target_size == 0) { 179e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Clear(); 180e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std_set.clear(); 181e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(hash_set.Empty()); 182e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_TRUE(std_set.empty()); 183e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } else if (n % target_size < delta) { 184e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier // Skew towards adding elements until we are at the desired size. 185e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const std::string& s = strings[PRand() % string_count]; 186e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Insert(s); 187e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std_set.insert(s); 188e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*hash_set.Find(s), *std_set.find(s)); 189e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } else { 190e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier const std::string& s = strings[PRand() % string_count]; 191e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it1 = hash_set.Find(s); 192e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier auto it2 = std_set.find(s); 193e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(it1 == hash_set.end(), it2 == std_set.end()); 194e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier if (it1 != hash_set.end()) { 195e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier ASSERT_EQ(*it1, *it2); 196e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier hash_set.Erase(it1); 197e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier std_set.erase(it2); 198e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 199e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 200e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier } 201e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} 202e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier 203e05d1d5fd86867afc7513b1c546375dba11eee50Mathieu Chartier} // namespace art 204