| OLD | NEW |
|---|
| (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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 353553007:
Revert r37716 due to Windows compilation errors. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/