1// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include <algorithm>
6#include <cstring>
7#include <map>
8#include <set>
9#include <string>
10#include <utility>
11#include <vector>
12
13#include "platform/assert.h"
14#include "vm/hash_table.h"
15#include "vm/unit_test.h"
16
17namespace dart {
18
19// Various ways to look up strings. Uses length as the hash code to make it
20// easy to engineer collisions.
21class TestTraits {
22 public:
23 static const char* Name() { return "TestTraits"; }
24 static bool ReportStats() { return false; }
25
26 static bool IsMatch(const char* key, const Object& obj) {
27 return String::Cast(obj).Equals(key);
28 }
29 static uword Hash(const char* key) { return static_cast<uword>(strlen(key)); }
30 static bool IsMatch(const Object& a, const Object& b) {
31 return a.IsString() && b.IsString() &&
32 String::Cast(a).Equals(String::Cast(b));
33 }
34 static uword Hash(const Object& obj) { return String::Cast(obj).Length(); }
35 static ObjectPtr NewKey(const char* key) { return String::New(key); }
36};
37
38template <typename Table>
39void Validate(const Table& table) {
40 // Verify consistency of entry state tracking.
41 intptr_t num_entries = table.NumEntries();
42 intptr_t num_unused = table.NumUnused();
43 intptr_t num_occupied = table.NumOccupied();
44 intptr_t num_deleted = table.NumDeleted();
45 for (intptr_t i = 0; i < num_entries; ++i) {
46 EXPECT_EQ(1, table.IsUnused(i) + table.IsOccupied(i) + table.IsDeleted(i));
47 num_unused -= table.IsUnused(i);
48 num_occupied -= table.IsOccupied(i);
49 num_deleted -= table.IsDeleted(i);
50 }
51 EXPECT_EQ(0, num_unused);
52 EXPECT_EQ(0, num_occupied);
53 EXPECT_EQ(0, num_deleted);
54}
55
56ISOLATE_UNIT_TEST_CASE(HashTable) {
57 typedef HashTable<TestTraits, 2, 1> Table;
58 Table table(Thread::Current()->zone(), HashTables::New<Table>(5));
59 // Ensure that we did get at least 5 entries.
60 EXPECT_LE(5, table.NumEntries());
61 EXPECT_EQ(0, table.NumOccupied());
62 Validate(table);
63 EXPECT_EQ(-1, table.FindKey("a"));
64
65 // Insertion and lookup.
66 intptr_t a_entry = -1;
67 EXPECT(!table.FindKeyOrDeletedOrUnused("a", &a_entry));
68 EXPECT_NE(-1, a_entry);
69 String& a = String::Handle(String::New("a"));
70 table.InsertKey(a_entry, a);
71 EXPECT_EQ(1, table.NumOccupied());
72 Validate(table);
73 EXPECT_EQ(a_entry, table.FindKey("a"));
74 EXPECT_EQ(-1, table.FindKey("b"));
75 intptr_t a_entry_again = -1;
76 EXPECT(table.FindKeyOrDeletedOrUnused("a", &a_entry_again));
77 EXPECT_EQ(a_entry, a_entry_again);
78 intptr_t b_entry = -1;
79 EXPECT(!table.FindKeyOrDeletedOrUnused("b", &b_entry));
80 String& b = String::Handle(String::New("b"));
81 table.InsertKey(b_entry, b);
82 EXPECT_EQ(2, table.NumOccupied());
83 Validate(table);
84
85 // Deletion.
86 table.DeleteEntry(a_entry);
87 EXPECT_EQ(1, table.NumOccupied());
88 Validate(table);
89 EXPECT_EQ(-1, table.FindKey("a"));
90 EXPECT_EQ(b_entry, table.FindKey("b"));
91 intptr_t c_entry = -1;
92 EXPECT(!table.FindKeyOrDeletedOrUnused("c", &c_entry));
93 String& c = String::Handle(String::New("c"));
94 table.InsertKey(c_entry, c);
95 EXPECT_EQ(2, table.NumOccupied());
96 Validate(table);
97 EXPECT_EQ(c_entry, table.FindKey("c"));
98
99 // Ensure we can actually reach 5 occupied entries (without expansion).
100 {
101 intptr_t entry = -1;
102 EXPECT(!table.FindKeyOrDeletedOrUnused("d", &entry));
103 String& k = String::Handle(String::New("d"));
104 table.InsertKey(entry, k);
105 EXPECT(!table.FindKeyOrDeletedOrUnused("e", &entry));
106 k = String::New("e");
107 table.InsertKey(entry, k);
108 EXPECT(!table.FindKeyOrDeletedOrUnused("f", &entry));
109 k = String::New("f");
110 table.InsertKey(entry, k);
111 EXPECT_EQ(5, table.NumOccupied());
112 }
113 table.Release();
114}
115
116std::string ToStdString(const String& str) {
117 EXPECT(str.IsOneByteString());
118 std::string result;
119 for (intptr_t i = 0; i < str.Length(); ++i) {
120 result += static_cast<char>(str.CharAt(i));
121 }
122 return result;
123}
124
125// Checks that 'expected' and 'actual' are equal sets. If 'ordered' is true,
126// it also verifies that their iteration orders match, i.e., that actual's
127// insertion order coincides with lexicographic order.
128template <typename Set>
129void VerifyStringSetsEqual(const std::set<std::string>& expected,
130 const Set& actual,
131 bool ordered) {
132 // Get actual keys in iteration order.
133 Array& keys = Array::Handle(HashTables::ToArray(actual, true));
134 // Cardinality must match.
135 EXPECT_EQ(static_cast<intptr_t>(expected.size()), keys.Length());
136 std::vector<std::string> expected_vec(expected.begin(), expected.end());
137 // Check containment.
138 for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
139 EXPECT(actual.ContainsKey(expected_vec[i].c_str()));
140 }
141 // Equality, including order, if requested.
142 std::vector<std::string> actual_vec;
143 String& key = String::Handle();
144 for (int i = 0; i < keys.Length(); ++i) {
145 key ^= keys.At(i);
146 actual_vec.push_back(ToStdString(key));
147 }
148 if (!ordered) {
149 std::sort(actual_vec.begin(), actual_vec.end());
150 }
151 EXPECT(
152 std::equal(actual_vec.begin(), actual_vec.end(), expected_vec.begin()));
153}
154
155// Checks that 'expected' and 'actual' are equal maps. If 'ordered' is true,
156// it also verifies that their iteration orders match, i.e., that actual's
157// insertion order coincides with lexicographic order.
158template <typename Map>
159void VerifyStringMapsEqual(const std::map<std::string, int>& expected,
160 const Map& actual,
161 bool ordered) {
162 intptr_t expected_size = expected.size();
163 // Get actual concatenated (key, value) pairs in iteration order.
164 Array& entries = Array::Handle(HashTables::ToArray(actual, true));
165 // Cardinality must match.
166 EXPECT_EQ(expected_size * 2, entries.Length());
167 std::vector<std::pair<std::string, int> > expected_vec(expected.begin(),
168 expected.end());
169 // Check containment.
170 Smi& value = Smi::Handle();
171 for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
172 std::string key = expected_vec[i].first;
173 EXPECT(actual.ContainsKey(key.c_str()));
174 value ^= actual.GetOrNull(key.c_str());
175 EXPECT_EQ(expected_vec[i].second, value.Value());
176 }
177 if (!ordered) {
178 return;
179 }
180 // Equality including order.
181 std::vector<std::string> actual_vec;
182 String& key = String::Handle();
183 for (int i = 0; i < expected_size; ++i) {
184 key ^= entries.At(2 * i);
185 value ^= entries.At(2 * i + 1);
186 EXPECT(expected_vec[i].first == ToStdString(key));
187 EXPECT_EQ(expected_vec[i].second, value.Value());
188 }
189}
190
191template <typename Set>
192void TestSet(intptr_t initial_capacity, bool ordered) {
193 std::set<std::string> expected;
194 Set actual(HashTables::New<Set>(initial_capacity));
195 // Insert the following strings twice:
196 // aaa...aaa (length 26)
197 // bbb..bbb
198 // ...
199 // yy
200 // z
201 for (int i = 0; i < 2; ++i) {
202 for (char ch = 'a'; ch <= 'z'; ++ch) {
203 std::string key('z' - ch + 1, ch);
204 expected.insert(key);
205 bool present = actual.Insert(String::Handle(String::New(key.c_str())));
206 EXPECT_EQ((i != 0), present);
207 Validate(actual);
208 VerifyStringSetsEqual(expected, actual, ordered);
209 }
210 }
211 actual.Clear();
212 EXPECT_EQ(0, actual.NumOccupied());
213 actual.Release();
214}
215
216template <typename Map>
217void TestMap(intptr_t initial_capacity, bool ordered) {
218 std::map<std::string, int> expected;
219 Map actual(HashTables::New<Map>(initial_capacity));
220 // Insert the following (strings, int) mapping:
221 // aaa...aaa -> 26
222 // bbb..bbb -> 25
223 // ...
224 // yy -> 2
225 // z -> 1
226 for (int i = 0; i < 2; ++i) {
227 for (char ch = 'a'; ch <= 'z'; ++ch) {
228 int length = 'z' - ch + 1;
229 std::string key(length, ch);
230 // Map everything to zero initially, then update to their final values.
231 int value = length * i;
232 expected[key] = value;
233 bool present =
234 actual.UpdateOrInsert(String::Handle(String::New(key.c_str())),
235 Smi::Handle(Smi::New(value)));
236 EXPECT_EQ((i != 0), present);
237 Validate(actual);
238 VerifyStringMapsEqual(expected, actual, ordered);
239 }
240 }
241 actual.Clear();
242 EXPECT_EQ(0, actual.NumOccupied());
243 actual.Release();
244}
245
246ISOLATE_UNIT_TEST_CASE(Sets) {
247 for (intptr_t initial_capacity = 0; initial_capacity < 32;
248 ++initial_capacity) {
249 TestSet<UnorderedHashSet<TestTraits> >(initial_capacity, false);
250 }
251}
252
253ISOLATE_UNIT_TEST_CASE(Maps) {
254 for (intptr_t initial_capacity = 0; initial_capacity < 32;
255 ++initial_capacity) {
256 TestMap<UnorderedHashMap<TestTraits> >(initial_capacity, false);
257 }
258}
259
260} // namespace dart
261