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