Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(438)

Side by Side Diff: runtime/vm/hash_table_test.cc

Issue 348313005: Resubmit r37716: Hash tables templates, wrapping Array. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « runtime/vm/hash_table.h ('k') | runtime/vm/object.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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/unit_test.h"
15 #include "vm/hash_table.h"
16
17 namespace dart {
18
19 // Various ways to look up strings. Uses length as the hash code to make it
20 // easy to engineer collisions.
21 class TestTraits {
22 public:
23 static bool IsMatch(const char* key, const Object& obj) {
24 return String::Cast(obj).Equals(key);
25 }
26 static uword Hash(const char* key) {
27 return static_cast<uword>(strlen(key));
28 }
29 static bool IsMatch(const Object& a, const Object& b) {
30 return a.IsString() && b.IsString() &&
31 String::Cast(a).Equals(String::Cast(b));
32 }
33 static uword Hash(const Object& obj) {
34 return String::Cast(obj).Length();
35 }
36 };
37
38
39 template<typename Table>
40 void Validate(const Table& table) {
41 // Verify consistency of entry state tracking.
42 intptr_t num_entries = table.NumEntries();
43 intptr_t num_unused = table.NumUnused();
44 intptr_t num_occupied = table.NumOccupied();
45 intptr_t num_deleted = table.NumDeleted();
46 for (intptr_t i = 0; i < num_entries; ++i) {
47 EXPECT_EQ(1, table.IsUnused(i) + table.IsOccupied(i) + table.IsDeleted(i));
48 num_unused -= table.IsUnused(i);
49 num_occupied -= table.IsOccupied(i);
50 num_deleted -= table.IsDeleted(i);
51 }
52 EXPECT_EQ(0, num_unused);
53 EXPECT_EQ(0, num_occupied);
54 EXPECT_EQ(0, num_deleted);
55 }
56
57
58 TEST_CASE(HashTable) {
59 typedef HashTable<TestTraits, 2, 1> Table;
60 Table table(Array::Handle(HashTables::New<Table>(5)));
61 // Ensure that we did get at least 5 entries.
62 EXPECT_LE(5, table.NumEntries());
63 EXPECT_EQ(0, table.NumOccupied());
64 Validate(table);
65 EXPECT_EQ(-1, table.FindKey("a"));
66
67 // Insertion and lookup.
68 intptr_t a_entry = -1;
69 EXPECT(!table.FindKeyOrDeletedOrUnused("a", &a_entry));
70 EXPECT_NE(-1, a_entry);
71 String& a = String::Handle(String::New("a"));
72 table.InsertKey(a_entry, a);
73 EXPECT_EQ(1, table.NumOccupied());
74 Validate(table);
75 EXPECT_EQ(a_entry, table.FindKey("a"));
76 EXPECT_EQ(-1, table.FindKey("b"));
77 intptr_t a_entry_again = -1;
78 EXPECT(table.FindKeyOrDeletedOrUnused("a", &a_entry_again));
79 EXPECT_EQ(a_entry, a_entry_again);
80 intptr_t b_entry = -1;
81 EXPECT(!table.FindKeyOrDeletedOrUnused("b", &b_entry));
82 String& b = String::Handle(String::New("b"));
83 table.InsertKey(b_entry, b);
84 EXPECT_EQ(2, table.NumOccupied());
85 Validate(table);
86
87 // Deletion.
88 table.DeleteEntry(a_entry);
89 EXPECT_EQ(1, table.NumOccupied());
90 Validate(table);
91 EXPECT_EQ(-1, table.FindKey("a"));
92 EXPECT_EQ(b_entry, table.FindKey("b"));
93 intptr_t c_entry = -1;
94 EXPECT(!table.FindKeyOrDeletedOrUnused("c", &c_entry));
95 String& c = String::Handle(String::New("c"));
96 table.InsertKey(c_entry, c);
97 EXPECT_EQ(2, table.NumOccupied());
98 Validate(table);
99 EXPECT_EQ(c_entry, table.FindKey("c"));
100
101 // Ensure we can actually reach 5 occupied entries (without expansion).
102 {
103 intptr_t entry = -1;
104 EXPECT(!table.FindKeyOrDeletedOrUnused("d", &entry));
105 String& k = String::Handle(String::New("d"));
106 table.InsertKey(entry, k);
107 EXPECT(!table.FindKeyOrDeletedOrUnused("e", &entry));
108 k = String::New("e");
109 table.InsertKey(entry, k);
110 EXPECT(!table.FindKeyOrDeletedOrUnused("f", &entry));
111 k = String::New("f");
112 table.InsertKey(entry, k);
113 EXPECT_EQ(5, table.NumOccupied());
114 }
115 table.Release();
116 }
117
118
119 TEST_CASE(EnumIndexHashMap) {
120 typedef EnumIndexHashMap<TestTraits> Table;
121 Table table(Array::Handle(HashTables::New<Table>(5)));
122 table.UpdateOrInsert(String::Handle(String::New("a")),
123 String::Handle(String::New("A")));
124 EXPECT(table.ContainsKey("a"));
125 table.UpdateValue("a", String::Handle(String::New("AAA")));
126 String& a_value = String::Handle();
127 a_value ^= table.GetOrNull("a");
128 EXPECT(a_value.Equals("AAA"));
129 Object& null_value = Object::Handle(table.GetOrNull("0"));
130 EXPECT(null_value.IsNull());
131 table.Release();
132 }
133
134
135 std::string ToStdString(const String& str) {
136 EXPECT(str.IsOneByteString());
137 std::string result;
138 for (intptr_t i = 0; i < str.Length(); ++i) {
139 result += static_cast<char>(str.CharAt(i));
140 }
141 return result;
142 }
143
144
145 // Checks that 'expected' and 'actual' are equal sets. If 'ordered' is true,
146 // it also verifies that their iteration orders match, i.e., that actual's
147 // insertion order coincides with lexicographic order.
148 template<typename Set>
149 void VerifyStringSetsEqual(const std::set<std::string>& expected,
150 const Set& actual,
151 bool ordered) {
152 // Get actual keys in iteration order.
153 Array& keys = Array::Handle(HashTables::ToArray(actual, true));
154 // Cardinality must match.
155 EXPECT_EQ(static_cast<intptr_t>(expected.size()), keys.Length());
156 std::vector<std::string> expected_vec(expected.begin(), expected.end());
157 // Check containment.
158 for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
159 EXPECT(actual.ContainsKey(expected_vec[i].c_str()));
160 }
161 // Equality, including order, if requested.
162 std::vector<std::string> actual_vec;
163 String& key = String::Handle();
164 for (int i = 0; i < keys.Length(); ++i) {
165 key ^= keys.At(i);
166 actual_vec.push_back(ToStdString(key));
167 }
168 if (!ordered) {
169 std::sort(actual_vec.begin(), actual_vec.end());
170 }
171 EXPECT(std::equal(actual_vec.begin(), actual_vec.end(),
172 expected_vec.begin()));
173 }
174
175
176 // Checks that 'expected' and 'actual' are equal maps. If 'ordered' is true,
177 // it also verifies that their iteration orders match, i.e., that actual's
178 // insertion order coincides with lexicographic order.
179 template<typename Map>
180 void VerifyStringMapsEqual(const std::map<std::string, int>& expected,
181 const Map& actual,
182 bool ordered) {
183 intptr_t expected_size = expected.size();
184 // Get actual concatenated (key, value) pairs in iteration order.
185 Array& entries = Array::Handle(HashTables::ToArray(actual, true));
186 // Cardinality must match.
187 EXPECT_EQ(expected_size * 2, entries.Length());
188 std::vector<std::pair<std::string, int> > expected_vec(expected.begin(),
189 expected.end());
190 // Check containment.
191 Smi& value = Smi::Handle();
192 for (uintptr_t i = 0; i < expected_vec.size(); ++i) {
193 std::string key = expected_vec[i].first;
194 EXPECT(actual.ContainsKey(key.c_str()));
195 value ^= actual.GetOrNull(key.c_str());
196 EXPECT_EQ(expected_vec[i].second, value.Value());
197 }
198 if (!ordered) {
199 return;
200 }
201 // Equality including order.
202 std::vector<std::string> actual_vec;
203 String& key = String::Handle();
204 for (int i = 0; i < expected_size; ++i) {
205 key ^= entries.At(2 * i);
206 value ^= entries.At(2 * i + 1);
207 EXPECT(expected_vec[i].first == ToStdString(key));
208 EXPECT_EQ(expected_vec[i].second, value.Value());
209 }
210 }
211
212
213 template<typename Set>
214 void TestSet(intptr_t initial_capacity, bool ordered) {
215 std::set<std::string> expected;
216 Set actual(Array::Handle(HashTables::New<Set>(initial_capacity)));
217 // Insert the following strings twice:
218 // aaa...aaa (length 26)
219 // bbb..bbb
220 // ...
221 // yy
222 // z
223 for (int i = 0; i < 2; ++i) {
224 for (char ch = 'a'; ch <= 'z'; ++ch) {
225 std::string key('z' - ch + 1, ch);
226 expected.insert(key);
227 bool present = actual.Insert(String::Handle(String::New(key.c_str())));
228 EXPECT_EQ((i != 0), present);
229 Validate(actual);
230 VerifyStringSetsEqual(expected, actual, ordered);
231 }
232 }
233 // TODO(koda): Delete all entries.
234 actual.Release();
235 }
236
237
238 template<typename Map>
239 void TestMap(intptr_t initial_capacity, bool ordered) {
240 std::map<std::string, int> expected;
241 Map actual(Array::Handle(HashTables::New<Map>(initial_capacity)));
242 // Insert the following (strings, int) mapping:
243 // aaa...aaa -> 26
244 // bbb..bbb -> 25
245 // ...
246 // yy -> 2
247 // z -> 1
248 for (int i = 0; i < 2; ++i) {
249 for (char ch = 'a'; ch <= 'z'; ++ch) {
250 int length = 'z' - ch + 1;
251 std::string key(length, ch);
252 // Map everything to zero initially, then update to their final values.
253 int value = length * i;
254 expected[key] = value;
255 bool present =
256 actual.UpdateOrInsert(String::Handle(String::New(key.c_str())),
257 Smi::Handle(Smi::New(value)));
258 EXPECT_EQ((i != 0), present);
259 Validate(actual);
260 VerifyStringMapsEqual(expected, actual, ordered);
261 }
262 }
263 // TODO(koda): Delete all entries.
264 actual.Release();
265 }
266
267
268 TEST_CASE(Sets) {
269 for (intptr_t initial_capacity = 0;
270 initial_capacity < 32;
271 ++initial_capacity) {
272 TestSet<UnorderedHashSet<TestTraits> >(initial_capacity, false);
273 TestSet<EnumIndexHashSet<TestTraits> >(initial_capacity, true);
274 }
275 }
276
277
278 TEST_CASE(Maps) {
279 for (intptr_t initial_capacity = 0;
280 initial_capacity < 32;
281 ++initial_capacity) {
282 TestMap<UnorderedHashMap<TestTraits> >(initial_capacity, false);
283 TestMap<EnumIndexHashMap<TestTraits> >(initial_capacity, true);
284 }
285 }
286
287 } // namespace dart
OLDNEW
« no previous file with comments | « runtime/vm/hash_table.h ('k') | runtime/vm/object.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698