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 <gtest/gtest.h>
25 #include "hash_map.h"
26 
27 namespace art {
28 
29 struct IsEmptyFnString {
MakeEmptyart::IsEmptyFnString30   void MakeEmpty(std::string& item) const {
31     item.clear();
32   }
IsEmptyart::IsEmptyFnString33   bool IsEmpty(const std::string& item) const {
34     return item.empty();
35   }
36 };
37 
38 class HashSetTest : public testing::Test {
39  public:
HashSetTest()40   HashSetTest() : seed_(97421), unique_number_(0) {
41   }
RandomString(size_t len)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   }
SetSeed(size_t seed)51   void SetSeed(size_t seed) {
52     seed_ = seed;
53   }
PRand()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 
TEST_F(HashSetTest,TestSmoke)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 
TEST_F(HashSetTest,TestInsertAndErase)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 
TEST_F(HashSetTest,TestIterator)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 
TEST_F(HashSetTest,TestSwap)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 
TEST_F(HashSetTest,TestStress)159 TEST_F(HashSetTest, TestStress) {
160   HashSet<std::string, IsEmptyFnString> hash_set;
161   std::unordered_multiset<std::string> std_set;
162   std::vector<std::string> strings;
163   static constexpr size_t string_count = 2000;
164   static constexpr size_t operations = 100000;
165   static constexpr size_t target_size = 5000;
166   for (size_t i = 0; i < string_count; ++i) {
167     strings.push_back(RandomString(i % 10 + 1));
168   }
169   const size_t seed = time(nullptr);
170   SetSeed(seed);
171   LOG(INFO) << "Starting stress test with seed " << seed;
172   for (size_t i = 0; i < operations; ++i) {
173     ASSERT_EQ(hash_set.Size(), std_set.size());
174     size_t delta = std::abs(static_cast<ssize_t>(target_size) -
175                             static_cast<ssize_t>(hash_set.Size()));
176     size_t n = PRand();
177     if (n % target_size == 0) {
178       hash_set.Clear();
179       std_set.clear();
180       ASSERT_TRUE(hash_set.Empty());
181       ASSERT_TRUE(std_set.empty());
182     } else  if (n % target_size < delta) {
183       // Skew towards adding elements until we are at the desired size.
184       const std::string& s = strings[PRand() % string_count];
185       hash_set.Insert(s);
186       std_set.insert(s);
187       ASSERT_EQ(*hash_set.Find(s), *std_set.find(s));
188     } else {
189       const std::string& s = strings[PRand() % string_count];
190       auto it1 = hash_set.Find(s);
191       auto it2 = std_set.find(s);
192       ASSERT_EQ(it1 == hash_set.end(), it2 == std_set.end());
193       if (it1 != hash_set.end()) {
194         ASSERT_EQ(*it1, *it2);
195         hash_set.Erase(it1);
196         std_set.erase(it2);
197       }
198     }
199   }
200 }
201 
202 struct IsEmptyStringPair {
MakeEmptyart::IsEmptyStringPair203   void MakeEmpty(std::pair<std::string, int>& pair) const {
204     pair.first.clear();
205   }
IsEmptyart::IsEmptyStringPair206   bool IsEmpty(const std::pair<std::string, int>& pair) const {
207     return pair.first.empty();
208   }
209 };
210 
TEST_F(HashSetTest,TestHashMap)211 TEST_F(HashSetTest, TestHashMap) {
212   HashMap<std::string, int, IsEmptyStringPair> hash_map;
213   hash_map.Insert(std::make_pair(std::string("abcd"), 123));
214   hash_map.Insert(std::make_pair(std::string("abcd"), 124));
215   hash_map.Insert(std::make_pair(std::string("bags"), 444));
216   auto it = hash_map.Find(std::string("abcd"));
217   ASSERT_EQ(it->second, 123);
218   hash_map.Erase(it);
219   it = hash_map.Find(std::string("abcd"));
220   ASSERT_EQ(it->second, 124);
221 }
222 
223 }  // namespace art
224