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