Mathieu Chartier | c2e2062 | 2014-11-03 11:41:47 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include "hash_set.h" |
| 18 | |
| 19 | #include <map> |
| 20 | #include <sstream> |
| 21 | #include <string> |
| 22 | #include <unordered_set> |
| 23 | |
Mathieu Chartier | 47f867a | 2015-03-18 10:39:00 -0700 | [diff] [blame] | 24 | #include <gtest/gtest.h> |
Mathieu Chartier | e7c9a8c | 2014-11-06 16:35:45 -0800 | [diff] [blame] | 25 | #include "hash_map.h" |
Mathieu Chartier | c2e2062 | 2014-11-03 11:41:47 -0800 | [diff] [blame] | 26 | |
| 27 | namespace art { |
| 28 | |
Mathieu Chartier | e7c9a8c | 2014-11-06 16:35:45 -0800 | [diff] [blame] | 29 | struct IsEmptyFnString { |
Mathieu Chartier | c2e2062 | 2014-11-03 11:41:47 -0800 | [diff] [blame] | 30 | void MakeEmpty(std::string& item) const { |
| 31 | item.clear(); |
| 32 | } |
| 33 | bool IsEmpty(const std::string& item) const { |
| 34 | return item.empty(); |
| 35 | } |
| 36 | }; |
| 37 | |
Mathieu Chartier | 47f867a | 2015-03-18 10:39:00 -0700 | [diff] [blame] | 38 | class HashSetTest : public testing::Test { |
Mathieu Chartier | c2e2062 | 2014-11-03 11:41:47 -0800 | [diff] [blame] | 39 | public: |
| 40 | HashSetTest() : seed_(97421), unique_number_(0) { |
| 41 | } |
| 42 | std::string RandomString(size_t len) { |
| 43 | std::ostringstream oss; |
| 44 | for (size_t i = 0; i < len; ++i) { |
| 45 | oss << static_cast<char>('A' + PRand() % 64); |
| 46 | } |
| 47 | static_assert(' ' < 'A', "space must be less than a"); |
| 48 | oss << " " << unique_number_++; // Relies on ' ' < 'A' |
| 49 | return oss.str(); |
| 50 | } |
| 51 | void SetSeed(size_t seed) { |
| 52 | seed_ = seed; |
| 53 | } |
| 54 | size_t PRand() { // Pseudo random. |
| 55 | seed_ = seed_ * 1103515245 + 12345; |
| 56 | return seed_; |
| 57 | } |
| 58 | |
| 59 | private: |
| 60 | size_t seed_; |
| 61 | size_t unique_number_; |
| 62 | }; |
| 63 | |
| 64 | TEST_F(HashSetTest, TestSmoke) { |
| 65 | HashSet<std::string, IsEmptyFnString> hash_set; |
| 66 | const std::string test_string = "hello world 1234"; |
| 67 | ASSERT_TRUE(hash_set.Empty()); |
| 68 | ASSERT_EQ(hash_set.Size(), 0U); |
| 69 | hash_set.Insert(test_string); |
| 70 | auto it = hash_set.Find(test_string); |
| 71 | ASSERT_EQ(*it, test_string); |
| 72 | auto after_it = hash_set.Erase(it); |
| 73 | ASSERT_TRUE(after_it == hash_set.end()); |
| 74 | ASSERT_TRUE(hash_set.Empty()); |
| 75 | ASSERT_EQ(hash_set.Size(), 0U); |
| 76 | it = hash_set.Find(test_string); |
| 77 | ASSERT_TRUE(it == hash_set.end()); |
| 78 | } |
| 79 | |
| 80 | TEST_F(HashSetTest, TestInsertAndErase) { |
| 81 | HashSet<std::string, IsEmptyFnString> hash_set; |
| 82 | static constexpr size_t count = 1000; |
| 83 | std::vector<std::string> strings; |
| 84 | for (size_t i = 0; i < count; ++i) { |
| 85 | // Insert a bunch of elements and make sure we can find them. |
| 86 | strings.push_back(RandomString(10)); |
| 87 | hash_set.Insert(strings[i]); |
| 88 | auto it = hash_set.Find(strings[i]); |
| 89 | ASSERT_TRUE(it != hash_set.end()); |
| 90 | ASSERT_EQ(*it, strings[i]); |
| 91 | } |
| 92 | ASSERT_EQ(strings.size(), hash_set.Size()); |
| 93 | // Try to erase the odd strings. |
| 94 | for (size_t i = 1; i < count; i += 2) { |
| 95 | auto it = hash_set.Find(strings[i]); |
| 96 | ASSERT_TRUE(it != hash_set.end()); |
| 97 | ASSERT_EQ(*it, strings[i]); |
| 98 | hash_set.Erase(it); |
| 99 | } |
| 100 | // Test removed. |
| 101 | for (size_t i = 1; i < count; i += 2) { |
| 102 | auto it = hash_set.Find(strings[i]); |
| 103 | ASSERT_TRUE(it == hash_set.end()); |
| 104 | } |
| 105 | for (size_t i = 0; i < count; i += 2) { |
| 106 | auto it = hash_set.Find(strings[i]); |
| 107 | ASSERT_TRUE(it != hash_set.end()); |
| 108 | ASSERT_EQ(*it, strings[i]); |
| 109 | } |
| 110 | } |
| 111 | |
| 112 | TEST_F(HashSetTest, TestIterator) { |
| 113 | HashSet<std::string, IsEmptyFnString> hash_set; |
| 114 | ASSERT_TRUE(hash_set.begin() == hash_set.end()); |
| 115 | static constexpr size_t count = 1000; |
| 116 | std::vector<std::string> strings; |
| 117 | for (size_t i = 0; i < count; ++i) { |
| 118 | // Insert a bunch of elements and make sure we can find them. |
| 119 | strings.push_back(RandomString(10)); |
| 120 | hash_set.Insert(strings[i]); |
| 121 | } |
| 122 | // Make sure we visit each string exactly once. |
| 123 | std::map<std::string, size_t> found_count; |
| 124 | for (const std::string& s : hash_set) { |
| 125 | ++found_count[s]; |
| 126 | } |
| 127 | for (size_t i = 0; i < count; ++i) { |
| 128 | ASSERT_EQ(found_count[strings[i]], 1U); |
| 129 | } |
| 130 | found_count.clear(); |
| 131 | // Remove all the elements with iterator erase. |
| 132 | for (auto it = hash_set.begin(); it != hash_set.end();) { |
| 133 | ++found_count[*it]; |
| 134 | it = hash_set.Erase(it); |
| 135 | ASSERT_EQ(hash_set.Verify(), 0U); |
| 136 | } |
| 137 | for (size_t i = 0; i < count; ++i) { |
| 138 | ASSERT_EQ(found_count[strings[i]], 1U); |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | TEST_F(HashSetTest, TestSwap) { |
| 143 | HashSet<std::string, IsEmptyFnString> hash_seta, hash_setb; |
| 144 | std::vector<std::string> strings; |
| 145 | static constexpr size_t count = 1000; |
| 146 | for (size_t i = 0; i < count; ++i) { |
| 147 | strings.push_back(RandomString(10)); |
| 148 | hash_seta.Insert(strings[i]); |
| 149 | } |
| 150 | std::swap(hash_seta, hash_setb); |
| 151 | hash_seta.Insert("TEST"); |
| 152 | hash_setb.Insert("TEST2"); |
| 153 | for (size_t i = 0; i < count; ++i) { |
| 154 | strings.push_back(RandomString(10)); |
| 155 | hash_seta.Insert(strings[i]); |
| 156 | } |
| 157 | } |
| 158 | |
Igor Murashkin | 3552d96 | 2015-06-22 15:57:38 -0700 | [diff] [blame] | 159 | TEST_F(HashSetTest, TestShrink) { |
| 160 | HashSet<std::string, IsEmptyFnString> hash_set; |
| 161 | std::vector<std::string> strings = {"a", "b", "c", "d", "e", "f", "g"}; |
| 162 | for (size_t i = 0; i < strings.size(); ++i) { |
| 163 | // Insert some strings into the beginning of our hash set to establish an initial size |
| 164 | hash_set.Insert(strings[i]); |
| 165 | } |
| 166 | |
| 167 | hash_set.ShrinkToMaximumLoad(); |
| 168 | const double initial_load = hash_set.CalculateLoadFactor(); |
| 169 | |
| 170 | // Insert a bunch of random strings to guarantee that we grow the capacity. |
| 171 | std::vector<std::string> random_strings; |
| 172 | static constexpr size_t count = 1000; |
| 173 | for (size_t i = 0; i < count; ++i) { |
| 174 | random_strings.push_back(RandomString(10)); |
| 175 | hash_set.Insert(random_strings[i]); |
| 176 | } |
| 177 | |
| 178 | // Erase all the extra strings which guarantees that our load factor will be really bad. |
| 179 | for (size_t i = 0; i < count; ++i) { |
| 180 | hash_set.Erase(hash_set.Find(random_strings[i])); |
| 181 | } |
| 182 | |
| 183 | const double bad_load = hash_set.CalculateLoadFactor(); |
| 184 | EXPECT_GT(initial_load, bad_load); |
| 185 | |
| 186 | // Shrink again, the load factor should be good again. |
| 187 | hash_set.ShrinkToMaximumLoad(); |
| 188 | EXPECT_DOUBLE_EQ(initial_load, hash_set.CalculateLoadFactor()); |
Igor Murashkin | e2facc5 | 2015-07-10 13:49:08 -0700 | [diff] [blame] | 189 | |
| 190 | // Make sure all the initial elements we had are still there |
| 191 | for (const std::string& initial_string : strings) { |
| 192 | EXPECT_NE(hash_set.end(), hash_set.Find(initial_string)) |
| 193 | << "expected to find " << initial_string; |
| 194 | } |
Igor Murashkin | 3552d96 | 2015-06-22 15:57:38 -0700 | [diff] [blame] | 195 | } |
| 196 | |
Mathieu Chartier | c2e2062 | 2014-11-03 11:41:47 -0800 | [diff] [blame] | 197 | TEST_F(HashSetTest, TestStress) { |
| 198 | HashSet<std::string, IsEmptyFnString> hash_set; |
| 199 | std::unordered_multiset<std::string> std_set; |
| 200 | std::vector<std::string> strings; |
| 201 | static constexpr size_t string_count = 2000; |
| 202 | static constexpr size_t operations = 100000; |
| 203 | static constexpr size_t target_size = 5000; |
| 204 | for (size_t i = 0; i < string_count; ++i) { |
| 205 | strings.push_back(RandomString(i % 10 + 1)); |
| 206 | } |
| 207 | const size_t seed = time(nullptr); |
| 208 | SetSeed(seed); |
| 209 | LOG(INFO) << "Starting stress test with seed " << seed; |
| 210 | for (size_t i = 0; i < operations; ++i) { |
| 211 | ASSERT_EQ(hash_set.Size(), std_set.size()); |
| 212 | size_t delta = std::abs(static_cast<ssize_t>(target_size) - |
| 213 | static_cast<ssize_t>(hash_set.Size())); |
| 214 | size_t n = PRand(); |
| 215 | if (n % target_size == 0) { |
| 216 | hash_set.Clear(); |
| 217 | std_set.clear(); |
| 218 | ASSERT_TRUE(hash_set.Empty()); |
| 219 | ASSERT_TRUE(std_set.empty()); |
| 220 | } else if (n % target_size < delta) { |
| 221 | // Skew towards adding elements until we are at the desired size. |
| 222 | const std::string& s = strings[PRand() % string_count]; |
| 223 | hash_set.Insert(s); |
| 224 | std_set.insert(s); |
| 225 | ASSERT_EQ(*hash_set.Find(s), *std_set.find(s)); |
| 226 | } else { |
| 227 | const std::string& s = strings[PRand() % string_count]; |
| 228 | auto it1 = hash_set.Find(s); |
| 229 | auto it2 = std_set.find(s); |
| 230 | ASSERT_EQ(it1 == hash_set.end(), it2 == std_set.end()); |
| 231 | if (it1 != hash_set.end()) { |
| 232 | ASSERT_EQ(*it1, *it2); |
| 233 | hash_set.Erase(it1); |
| 234 | std_set.erase(it2); |
| 235 | } |
| 236 | } |
| 237 | } |
| 238 | } |
| 239 | |
Mathieu Chartier | e7c9a8c | 2014-11-06 16:35:45 -0800 | [diff] [blame] | 240 | struct IsEmptyStringPair { |
| 241 | void MakeEmpty(std::pair<std::string, int>& pair) const { |
| 242 | pair.first.clear(); |
| 243 | } |
| 244 | bool IsEmpty(const std::pair<std::string, int>& pair) const { |
| 245 | return pair.first.empty(); |
| 246 | } |
| 247 | }; |
| 248 | |
| 249 | TEST_F(HashSetTest, TestHashMap) { |
| 250 | HashMap<std::string, int, IsEmptyStringPair> hash_map; |
| 251 | hash_map.Insert(std::make_pair(std::string("abcd"), 123)); |
| 252 | hash_map.Insert(std::make_pair(std::string("abcd"), 124)); |
| 253 | hash_map.Insert(std::make_pair(std::string("bags"), 444)); |
| 254 | auto it = hash_map.Find(std::string("abcd")); |
| 255 | ASSERT_EQ(it->second, 123); |
| 256 | hash_map.Erase(it); |
| 257 | it = hash_map.Find(std::string("abcd")); |
| 258 | ASSERT_EQ(it->second, 124); |
| 259 | } |
| 260 | |
Mathieu Chartier | c2e2062 | 2014-11-03 11:41:47 -0800 | [diff] [blame] | 261 | } // namespace art |