| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2011 Google Inc. All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions | |
| 6 * are met: | |
| 7 * 1. Redistributions of source code must retain the above copyright | |
| 8 * notice, this list of conditions and the following disclaimer. | |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer in the | |
| 11 * documentation and/or other materials provided with the distribution. | |
| 12 * | |
| 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' | |
| 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, | |
| 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
| 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS | |
| 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF | |
| 23 * THE POSSIBILITY OF SUCH DAMAGE. | |
| 24 */ | |
| 25 | |
| 26 #include "wtf/HashMap.h" | |
| 27 | |
| 28 #include "testing/gtest/include/gtest/gtest.h" | |
| 29 #include "wtf/PassRefPtr.h" | |
| 30 #include "wtf/PtrUtil.h" | |
| 31 #include "wtf/RefCounted.h" | |
| 32 #include "wtf/Vector.h" | |
| 33 #include <memory> | |
| 34 | |
| 35 namespace WTF { | |
| 36 | |
| 37 namespace { | |
| 38 | |
| 39 using IntHashMap = HashMap<int, int>; | |
| 40 | |
| 41 TEST(HashMapTest, IteratorComparison) { | |
| 42 IntHashMap map; | |
| 43 map.insert(1, 2); | |
| 44 EXPECT_TRUE(map.begin() != map.end()); | |
| 45 EXPECT_FALSE(map.begin() == map.end()); | |
| 46 | |
| 47 IntHashMap::const_iterator begin = map.begin(); | |
| 48 EXPECT_TRUE(begin == map.begin()); | |
| 49 EXPECT_TRUE(map.begin() == begin); | |
| 50 EXPECT_TRUE(begin != map.end()); | |
| 51 EXPECT_TRUE(map.end() != begin); | |
| 52 EXPECT_FALSE(begin != map.begin()); | |
| 53 EXPECT_FALSE(map.begin() != begin); | |
| 54 EXPECT_FALSE(begin == map.end()); | |
| 55 EXPECT_FALSE(map.end() == begin); | |
| 56 } | |
| 57 | |
| 58 struct TestDoubleHashTraits : HashTraits<double> { | |
| 59 static const unsigned minimumTableSize = 8; | |
| 60 }; | |
| 61 | |
| 62 using DoubleHashMap = | |
| 63 HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits>; | |
| 64 | |
| 65 int bucketForKey(double key) { | |
| 66 return DefaultHash<double>::Hash::hash(key) & | |
| 67 (TestDoubleHashTraits::minimumTableSize - 1); | |
| 68 } | |
| 69 | |
| 70 TEST(HashMapTest, DoubleHashCollisions) { | |
| 71 // The "clobber" key here is one that ends up stealing the bucket that the -0 | |
| 72 // key originally wants to be in. This makes the 0 and -0 keys collide and | |
| 73 // the test then fails unless the FloatHash::equals() implementation can | |
| 74 // distinguish them. | |
| 75 const double clobberKey = 6; | |
| 76 const double zeroKey = 0; | |
| 77 const double negativeZeroKey = -zeroKey; | |
| 78 | |
| 79 DoubleHashMap map; | |
| 80 | |
| 81 map.insert(clobberKey, 1); | |
| 82 map.insert(zeroKey, 2); | |
| 83 map.insert(negativeZeroKey, 3); | |
| 84 | |
| 85 EXPECT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey)); | |
| 86 EXPECT_EQ(1, map.at(clobberKey)); | |
| 87 EXPECT_EQ(2, map.at(zeroKey)); | |
| 88 EXPECT_EQ(3, map.at(negativeZeroKey)); | |
| 89 } | |
| 90 | |
| 91 class DestructCounter { | |
| 92 public: | |
| 93 explicit DestructCounter(int i, int* destructNumber) | |
| 94 : m_i(i), m_destructNumber(destructNumber) {} | |
| 95 | |
| 96 ~DestructCounter() { ++(*m_destructNumber); } | |
| 97 int get() const { return m_i; } | |
| 98 | |
| 99 private: | |
| 100 int m_i; | |
| 101 int* m_destructNumber; | |
| 102 }; | |
| 103 | |
| 104 using OwnPtrHashMap = HashMap<int, std::unique_ptr<DestructCounter>>; | |
| 105 | |
| 106 TEST(HashMapTest, OwnPtrAsValue) { | |
| 107 int destructNumber = 0; | |
| 108 OwnPtrHashMap map; | |
| 109 map.insert(1, WTF::wrapUnique(new DestructCounter(1, &destructNumber))); | |
| 110 map.insert(2, WTF::wrapUnique(new DestructCounter(2, &destructNumber))); | |
| 111 | |
| 112 DestructCounter* counter1 = map.at(1); | |
| 113 EXPECT_EQ(1, counter1->get()); | |
| 114 DestructCounter* counter2 = map.at(2); | |
| 115 EXPECT_EQ(2, counter2->get()); | |
| 116 EXPECT_EQ(0, destructNumber); | |
| 117 | |
| 118 for (OwnPtrHashMap::iterator iter = map.begin(); iter != map.end(); ++iter) { | |
| 119 std::unique_ptr<DestructCounter>& ownCounter = iter->value; | |
| 120 EXPECT_EQ(iter->key, ownCounter->get()); | |
| 121 } | |
| 122 ASSERT_EQ(0, destructNumber); | |
| 123 | |
| 124 std::unique_ptr<DestructCounter> ownCounter1 = map.take(1); | |
| 125 EXPECT_EQ(ownCounter1.get(), counter1); | |
| 126 EXPECT_FALSE(map.contains(1)); | |
| 127 EXPECT_EQ(0, destructNumber); | |
| 128 | |
| 129 map.erase(2); | |
| 130 EXPECT_FALSE(map.contains(2)); | |
| 131 EXPECT_EQ(0UL, map.size()); | |
| 132 EXPECT_EQ(1, destructNumber); | |
| 133 | |
| 134 ownCounter1.reset(); | |
| 135 EXPECT_EQ(2, destructNumber); | |
| 136 } | |
| 137 | |
| 138 class DummyRefCounted : public RefCounted<DummyRefCounted> { | |
| 139 public: | |
| 140 DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { | |
| 141 m_isDeleted = false; | |
| 142 } | |
| 143 ~DummyRefCounted() { | |
| 144 DCHECK(!m_isDeleted); | |
| 145 m_isDeleted = true; | |
| 146 } | |
| 147 | |
| 148 void ref() { | |
| 149 DCHECK(!m_isDeleted); | |
| 150 WTF::RefCounted<DummyRefCounted>::ref(); | |
| 151 ++m_refInvokesCount; | |
| 152 } | |
| 153 | |
| 154 void deref() { | |
| 155 DCHECK(!m_isDeleted); | |
| 156 WTF::RefCounted<DummyRefCounted>::deref(); | |
| 157 } | |
| 158 | |
| 159 static int m_refInvokesCount; | |
| 160 | |
| 161 private: | |
| 162 bool& m_isDeleted; | |
| 163 }; | |
| 164 | |
| 165 int DummyRefCounted::m_refInvokesCount = 0; | |
| 166 | |
| 167 TEST(HashMapTest, RefPtrAsKey) { | |
| 168 bool isDeleted = false; | |
| 169 DummyRefCounted::m_refInvokesCount = 0; | |
| 170 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted)); | |
| 171 EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount); | |
| 172 HashMap<RefPtr<DummyRefCounted>, int> map; | |
| 173 map.insert(ptr, 1); | |
| 174 // Referenced only once (to store a copy in the container). | |
| 175 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 176 EXPECT_EQ(1, map.at(ptr)); | |
| 177 | |
| 178 DummyRefCounted* rawPtr = ptr.get(); | |
| 179 | |
| 180 EXPECT_TRUE(map.contains(rawPtr)); | |
| 181 EXPECT_NE(map.end(), map.find(rawPtr)); | |
| 182 EXPECT_TRUE(map.contains(ptr)); | |
| 183 EXPECT_NE(map.end(), map.find(ptr)); | |
| 184 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 185 | |
| 186 ptr.clear(); | |
| 187 EXPECT_FALSE(isDeleted); | |
| 188 | |
| 189 map.erase(rawPtr); | |
| 190 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 191 EXPECT_TRUE(isDeleted); | |
| 192 EXPECT_TRUE(map.isEmpty()); | |
| 193 } | |
| 194 | |
| 195 TEST(HashMaptest, RemoveAdd) { | |
| 196 DummyRefCounted::m_refInvokesCount = 0; | |
| 197 bool isDeleted = false; | |
| 198 | |
| 199 typedef HashMap<int, RefPtr<DummyRefCounted>> Map; | |
| 200 Map map; | |
| 201 | |
| 202 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted)); | |
| 203 EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount); | |
| 204 | |
| 205 map.insert(1, ptr); | |
| 206 // Referenced only once (to store a copy in the container). | |
| 207 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 208 EXPECT_EQ(ptr, map.at(1)); | |
| 209 | |
| 210 ptr.clear(); | |
| 211 EXPECT_FALSE(isDeleted); | |
| 212 | |
| 213 map.erase(1); | |
| 214 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 215 EXPECT_TRUE(isDeleted); | |
| 216 EXPECT_TRUE(map.isEmpty()); | |
| 217 | |
| 218 // Add and remove until the deleted slot is reused. | |
| 219 for (int i = 1; i < 100; i++) { | |
| 220 bool isDeleted2 = false; | |
| 221 RefPtr<DummyRefCounted> ptr2 = adoptRef(new DummyRefCounted(isDeleted2)); | |
| 222 map.insert(i, ptr2); | |
| 223 EXPECT_FALSE(isDeleted2); | |
| 224 ptr2.clear(); | |
| 225 EXPECT_FALSE(isDeleted2); | |
| 226 map.erase(i); | |
| 227 EXPECT_TRUE(isDeleted2); | |
| 228 } | |
| 229 } | |
| 230 | |
| 231 class SimpleClass { | |
| 232 public: | |
| 233 explicit SimpleClass(int v) : m_v(v) {} | |
| 234 int v() { return m_v; } | |
| 235 | |
| 236 private: | |
| 237 int m_v; | |
| 238 }; | |
| 239 using IntSimpleMap = HashMap<int, std::unique_ptr<SimpleClass>>; | |
| 240 | |
| 241 TEST(HashMapTest, AddResult) { | |
| 242 IntSimpleMap map; | |
| 243 IntSimpleMap::AddResult result = map.insert(1, nullptr); | |
| 244 EXPECT_TRUE(result.isNewEntry); | |
| 245 EXPECT_EQ(1, result.storedValue->key); | |
| 246 EXPECT_EQ(0, result.storedValue->value.get()); | |
| 247 | |
| 248 SimpleClass* simple1 = new SimpleClass(1); | |
| 249 result.storedValue->value = WTF::wrapUnique(simple1); | |
| 250 EXPECT_EQ(simple1, map.at(1)); | |
| 251 | |
| 252 IntSimpleMap::AddResult result2 = | |
| 253 map.insert(1, WTF::makeUnique<SimpleClass>(2)); | |
| 254 EXPECT_FALSE(result2.isNewEntry); | |
| 255 EXPECT_EQ(1, result.storedValue->key); | |
| 256 EXPECT_EQ(1, result.storedValue->value->v()); | |
| 257 EXPECT_EQ(1, map.at(1)->v()); | |
| 258 } | |
| 259 | |
| 260 TEST(HashMapTest, AddResultVectorValue) { | |
| 261 using IntVectorMap = HashMap<int, Vector<int>>; | |
| 262 IntVectorMap map; | |
| 263 IntVectorMap::AddResult result = map.insert(1, Vector<int>()); | |
| 264 EXPECT_TRUE(result.isNewEntry); | |
| 265 EXPECT_EQ(1, result.storedValue->key); | |
| 266 EXPECT_EQ(0u, result.storedValue->value.size()); | |
| 267 | |
| 268 result.storedValue->value.push_back(11); | |
| 269 EXPECT_EQ(1u, map.find(1)->value.size()); | |
| 270 EXPECT_EQ(11, map.find(1)->value.front()); | |
| 271 | |
| 272 IntVectorMap::AddResult result2 = map.insert(1, Vector<int>()); | |
| 273 EXPECT_FALSE(result2.isNewEntry); | |
| 274 EXPECT_EQ(1, result.storedValue->key); | |
| 275 EXPECT_EQ(1u, result.storedValue->value.size()); | |
| 276 EXPECT_EQ(11, result.storedValue->value.front()); | |
| 277 EXPECT_EQ(11, map.find(1)->value.front()); | |
| 278 } | |
| 279 | |
| 280 class InstanceCounter { | |
| 281 public: | |
| 282 InstanceCounter() { ++counter; } | |
| 283 InstanceCounter(const InstanceCounter& another) { ++counter; } | |
| 284 ~InstanceCounter() { --counter; } | |
| 285 static int counter; | |
| 286 }; | |
| 287 int InstanceCounter::counter = 0; | |
| 288 | |
| 289 TEST(HashMapTest, ValueTypeDestructed) { | |
| 290 InstanceCounter::counter = 0; | |
| 291 HashMap<int, InstanceCounter> map; | |
| 292 map.set(1, InstanceCounter()); | |
| 293 map.clear(); | |
| 294 EXPECT_EQ(0, InstanceCounter::counter); | |
| 295 } | |
| 296 | |
| 297 class MoveOnly { | |
| 298 public: | |
| 299 // kEmpty and kDeleted have special meanings when MoveOnly is used as the key | |
| 300 // of a hash table. | |
| 301 enum { kEmpty = 0, kDeleted = -1, kMovedOut = -2 }; | |
| 302 | |
| 303 explicit MoveOnly(int value = kEmpty) : m_value(value) {} | |
| 304 MoveOnly(MoveOnly&& other) : m_value(other.m_value) { | |
| 305 other.m_value = kMovedOut; | |
| 306 } | |
| 307 MoveOnly& operator=(MoveOnly&& other) { | |
| 308 m_value = other.m_value; | |
| 309 other.m_value = kMovedOut; | |
| 310 return *this; | |
| 311 } | |
| 312 | |
| 313 int value() const { return m_value; } | |
| 314 | |
| 315 private: | |
| 316 MoveOnly(const MoveOnly&) = delete; | |
| 317 MoveOnly& operator=(const MoveOnly&) = delete; | |
| 318 | |
| 319 int m_value; | |
| 320 }; | |
| 321 | |
| 322 struct MoveOnlyHashTraits : public GenericHashTraits<MoveOnly> { | |
| 323 // This is actually true, but we pretend that it's false to disable the | |
| 324 // optimization. | |
| 325 static const bool emptyValueIsZero = false; | |
| 326 | |
| 327 static const bool hasIsEmptyValueFunction = true; | |
| 328 static bool isEmptyValue(const MoveOnly& value) { | |
| 329 return value.value() == MoveOnly::kEmpty; | |
| 330 } | |
| 331 static void constructDeletedValue(MoveOnly& slot, bool) { | |
| 332 slot = MoveOnly(MoveOnly::kDeleted); | |
| 333 } | |
| 334 static bool isDeletedValue(const MoveOnly& value) { | |
| 335 return value.value() == MoveOnly::kDeleted; | |
| 336 } | |
| 337 }; | |
| 338 | |
| 339 struct MoveOnlyHash { | |
| 340 static unsigned hash(const MoveOnly& value) { | |
| 341 return DefaultHash<int>::Hash::hash(value.value()); | |
| 342 } | |
| 343 static bool equal(const MoveOnly& left, const MoveOnly& right) { | |
| 344 return DefaultHash<int>::Hash::equal(left.value(), right.value()); | |
| 345 } | |
| 346 static const bool safeToCompareToEmptyOrDeleted = true; | |
| 347 }; | |
| 348 | |
| 349 } // anonymous namespace | |
| 350 | |
| 351 template <> | |
| 352 struct HashTraits<MoveOnly> : public MoveOnlyHashTraits {}; | |
| 353 | |
| 354 template <> | |
| 355 struct DefaultHash<MoveOnly> { | |
| 356 using Hash = MoveOnlyHash; | |
| 357 }; | |
| 358 | |
| 359 namespace { | |
| 360 | |
| 361 TEST(HashMapTest, MoveOnlyValueType) { | |
| 362 using TheMap = HashMap<int, MoveOnly>; | |
| 363 TheMap map; | |
| 364 { | |
| 365 TheMap::AddResult addResult = map.insert(1, MoveOnly(10)); | |
| 366 EXPECT_TRUE(addResult.isNewEntry); | |
| 367 EXPECT_EQ(1, addResult.storedValue->key); | |
| 368 EXPECT_EQ(10, addResult.storedValue->value.value()); | |
| 369 } | |
| 370 auto iter = map.find(1); | |
| 371 ASSERT_TRUE(iter != map.end()); | |
| 372 EXPECT_EQ(1, iter->key); | |
| 373 EXPECT_EQ(10, iter->value.value()); | |
| 374 | |
| 375 iter = map.find(2); | |
| 376 EXPECT_TRUE(iter == map.end()); | |
| 377 | |
| 378 // Try to add more to trigger rehashing. | |
| 379 for (int i = 2; i < 32; ++i) { | |
| 380 TheMap::AddResult addResult = map.insert(i, MoveOnly(i * 10)); | |
| 381 EXPECT_TRUE(addResult.isNewEntry); | |
| 382 EXPECT_EQ(i, addResult.storedValue->key); | |
| 383 EXPECT_EQ(i * 10, addResult.storedValue->value.value()); | |
| 384 } | |
| 385 | |
| 386 iter = map.find(1); | |
| 387 ASSERT_TRUE(iter != map.end()); | |
| 388 EXPECT_EQ(1, iter->key); | |
| 389 EXPECT_EQ(10, iter->value.value()); | |
| 390 | |
| 391 iter = map.find(7); | |
| 392 ASSERT_TRUE(iter != map.end()); | |
| 393 EXPECT_EQ(7, iter->key); | |
| 394 EXPECT_EQ(70, iter->value.value()); | |
| 395 | |
| 396 { | |
| 397 TheMap::AddResult addResult = map.set(9, MoveOnly(999)); | |
| 398 EXPECT_FALSE(addResult.isNewEntry); | |
| 399 EXPECT_EQ(9, addResult.storedValue->key); | |
| 400 EXPECT_EQ(999, addResult.storedValue->value.value()); | |
| 401 } | |
| 402 | |
| 403 map.erase(11); | |
| 404 iter = map.find(11); | |
| 405 EXPECT_TRUE(iter == map.end()); | |
| 406 | |
| 407 MoveOnly oneThirty(map.take(13)); | |
| 408 EXPECT_EQ(130, oneThirty.value()); | |
| 409 iter = map.find(13); | |
| 410 EXPECT_TRUE(iter == map.end()); | |
| 411 | |
| 412 map.clear(); | |
| 413 } | |
| 414 | |
| 415 TEST(HashMapTest, MoveOnlyKeyType) { | |
| 416 // The content of this test is similar to the test above, except that the | |
| 417 // types of key and value are swapped. | |
| 418 using TheMap = HashMap<MoveOnly, int>; | |
| 419 TheMap map; | |
| 420 { | |
| 421 TheMap::AddResult addResult = map.insert(MoveOnly(1), 10); | |
| 422 EXPECT_TRUE(addResult.isNewEntry); | |
| 423 EXPECT_EQ(1, addResult.storedValue->key.value()); | |
| 424 EXPECT_EQ(10, addResult.storedValue->value); | |
| 425 } | |
| 426 auto iter = map.find(MoveOnly(1)); | |
| 427 ASSERT_TRUE(iter != map.end()); | |
| 428 EXPECT_EQ(1, iter->key.value()); | |
| 429 EXPECT_EQ(10, iter->value); | |
| 430 | |
| 431 iter = map.find(MoveOnly(2)); | |
| 432 EXPECT_TRUE(iter == map.end()); | |
| 433 | |
| 434 for (int i = 2; i < 32; ++i) { | |
| 435 TheMap::AddResult addResult = map.insert(MoveOnly(i), i * 10); | |
| 436 EXPECT_TRUE(addResult.isNewEntry); | |
| 437 EXPECT_EQ(i, addResult.storedValue->key.value()); | |
| 438 EXPECT_EQ(i * 10, addResult.storedValue->value); | |
| 439 } | |
| 440 | |
| 441 iter = map.find(MoveOnly(1)); | |
| 442 ASSERT_TRUE(iter != map.end()); | |
| 443 EXPECT_EQ(1, iter->key.value()); | |
| 444 EXPECT_EQ(10, iter->value); | |
| 445 | |
| 446 iter = map.find(MoveOnly(7)); | |
| 447 ASSERT_TRUE(iter != map.end()); | |
| 448 EXPECT_EQ(7, iter->key.value()); | |
| 449 EXPECT_EQ(70, iter->value); | |
| 450 | |
| 451 { | |
| 452 TheMap::AddResult addResult = map.set(MoveOnly(9), 999); | |
| 453 EXPECT_FALSE(addResult.isNewEntry); | |
| 454 EXPECT_EQ(9, addResult.storedValue->key.value()); | |
| 455 EXPECT_EQ(999, addResult.storedValue->value); | |
| 456 } | |
| 457 | |
| 458 map.erase(MoveOnly(11)); | |
| 459 iter = map.find(MoveOnly(11)); | |
| 460 EXPECT_TRUE(iter == map.end()); | |
| 461 | |
| 462 int oneThirty = map.take(MoveOnly(13)); | |
| 463 EXPECT_EQ(130, oneThirty); | |
| 464 iter = map.find(MoveOnly(13)); | |
| 465 EXPECT_TRUE(iter == map.end()); | |
| 466 | |
| 467 map.clear(); | |
| 468 } | |
| 469 | |
| 470 class CountCopy final { | |
| 471 public: | |
| 472 CountCopy() : m_counter(nullptr) {} | |
| 473 explicit CountCopy(int& counter) : m_counter(&counter) {} | |
| 474 CountCopy(const CountCopy& other) : m_counter(other.m_counter) { | |
| 475 if (m_counter) | |
| 476 ++*m_counter; | |
| 477 } | |
| 478 CountCopy& operator=(const CountCopy& other) { | |
| 479 m_counter = other.m_counter; | |
| 480 if (m_counter) | |
| 481 ++*m_counter; | |
| 482 return *this; | |
| 483 } | |
| 484 | |
| 485 private: | |
| 486 int* m_counter; | |
| 487 }; | |
| 488 | |
| 489 TEST(HashMapTest, MoveShouldNotMakeCopy) { | |
| 490 HashMap<int, CountCopy> map; | |
| 491 int counter = 0; | |
| 492 map.insert(1, CountCopy(counter)); | |
| 493 | |
| 494 HashMap<int, CountCopy> other(map); | |
| 495 counter = 0; | |
| 496 map = std::move(other); | |
| 497 EXPECT_EQ(0, counter); | |
| 498 | |
| 499 counter = 0; | |
| 500 HashMap<int, CountCopy> yetAnother(std::move(map)); | |
| 501 EXPECT_EQ(0, counter); | |
| 502 } | |
| 503 | |
| 504 TEST(HashMapTest, UniquePtrAsKey) { | |
| 505 using Pointer = std::unique_ptr<int>; | |
| 506 using Map = HashMap<Pointer, int>; | |
| 507 Map map; | |
| 508 int* onePointer = new int(1); | |
| 509 { | |
| 510 Map::AddResult addResult = map.insert(Pointer(onePointer), 1); | |
| 511 EXPECT_TRUE(addResult.isNewEntry); | |
| 512 EXPECT_EQ(onePointer, addResult.storedValue->key.get()); | |
| 513 EXPECT_EQ(1, *addResult.storedValue->key); | |
| 514 EXPECT_EQ(1, addResult.storedValue->value); | |
| 515 } | |
| 516 auto iter = map.find(onePointer); | |
| 517 ASSERT_TRUE(iter != map.end()); | |
| 518 EXPECT_EQ(onePointer, iter->key.get()); | |
| 519 EXPECT_EQ(1, iter->value); | |
| 520 | |
| 521 Pointer nonexistent(new int(42)); | |
| 522 iter = map.find(nonexistent.get()); | |
| 523 EXPECT_TRUE(iter == map.end()); | |
| 524 | |
| 525 // Insert more to cause a rehash. | |
| 526 for (int i = 2; i < 32; ++i) { | |
| 527 Map::AddResult addResult = map.insert(Pointer(new int(i)), i); | |
| 528 EXPECT_TRUE(addResult.isNewEntry); | |
| 529 EXPECT_EQ(i, *addResult.storedValue->key); | |
| 530 EXPECT_EQ(i, addResult.storedValue->value); | |
| 531 } | |
| 532 | |
| 533 iter = map.find(onePointer); | |
| 534 ASSERT_TRUE(iter != map.end()); | |
| 535 EXPECT_EQ(onePointer, iter->key.get()); | |
| 536 EXPECT_EQ(1, iter->value); | |
| 537 | |
| 538 EXPECT_EQ(1, map.take(onePointer)); | |
| 539 // From now on, |onePointer| is a dangling pointer. | |
| 540 | |
| 541 iter = map.find(onePointer); | |
| 542 EXPECT_TRUE(iter == map.end()); | |
| 543 } | |
| 544 | |
| 545 TEST(HashMapTest, UniquePtrAsValue) { | |
| 546 using Pointer = std::unique_ptr<int>; | |
| 547 using Map = HashMap<int, Pointer>; | |
| 548 Map map; | |
| 549 { | |
| 550 Map::AddResult addResult = map.insert(1, Pointer(new int(1))); | |
| 551 EXPECT_TRUE(addResult.isNewEntry); | |
| 552 EXPECT_EQ(1, addResult.storedValue->key); | |
| 553 EXPECT_EQ(1, *addResult.storedValue->value); | |
| 554 } | |
| 555 auto iter = map.find(1); | |
| 556 ASSERT_TRUE(iter != map.end()); | |
| 557 EXPECT_EQ(1, iter->key); | |
| 558 EXPECT_EQ(1, *iter->value); | |
| 559 | |
| 560 int* onePointer = map.at(1); | |
| 561 EXPECT_TRUE(onePointer); | |
| 562 EXPECT_EQ(1, *onePointer); | |
| 563 | |
| 564 iter = map.find(42); | |
| 565 EXPECT_TRUE(iter == map.end()); | |
| 566 | |
| 567 for (int i = 2; i < 32; ++i) { | |
| 568 Map::AddResult addResult = map.insert(i, Pointer(new int(i))); | |
| 569 EXPECT_TRUE(addResult.isNewEntry); | |
| 570 EXPECT_EQ(i, addResult.storedValue->key); | |
| 571 EXPECT_EQ(i, *addResult.storedValue->value); | |
| 572 } | |
| 573 | |
| 574 iter = map.find(1); | |
| 575 ASSERT_TRUE(iter != map.end()); | |
| 576 EXPECT_EQ(1, iter->key); | |
| 577 EXPECT_EQ(1, *iter->value); | |
| 578 | |
| 579 Pointer one(map.take(1)); | |
| 580 ASSERT_TRUE(one); | |
| 581 EXPECT_EQ(1, *one); | |
| 582 | |
| 583 Pointer empty(map.take(42)); | |
| 584 EXPECT_TRUE(!empty); | |
| 585 | |
| 586 iter = map.find(1); | |
| 587 EXPECT_TRUE(iter == map.end()); | |
| 588 | |
| 589 { | |
| 590 Map::AddResult addResult = map.insert(1, std::move(one)); | |
| 591 EXPECT_TRUE(addResult.isNewEntry); | |
| 592 EXPECT_EQ(1, addResult.storedValue->key); | |
| 593 EXPECT_EQ(1, *addResult.storedValue->value); | |
| 594 } | |
| 595 } | |
| 596 | |
| 597 TEST(HashMapTest, MoveOnlyPairKeyType) { | |
| 598 using Pair = std::pair<MoveOnly, int>; | |
| 599 using TheMap = HashMap<Pair, int>; | |
| 600 TheMap map; | |
| 601 { | |
| 602 TheMap::AddResult addResult = map.insert(Pair(MoveOnly(1), -1), 10); | |
| 603 EXPECT_TRUE(addResult.isNewEntry); | |
| 604 EXPECT_EQ(1, addResult.storedValue->key.first.value()); | |
| 605 EXPECT_EQ(-1, addResult.storedValue->key.second); | |
| 606 EXPECT_EQ(10, addResult.storedValue->value); | |
| 607 } | |
| 608 auto iter = map.find(Pair(MoveOnly(1), -1)); | |
| 609 ASSERT_TRUE(iter != map.end()); | |
| 610 EXPECT_EQ(1, iter->key.first.value()); | |
| 611 EXPECT_EQ(-1, iter->key.second); | |
| 612 EXPECT_EQ(10, iter->value); | |
| 613 | |
| 614 iter = map.find(Pair(MoveOnly(1), 0)); | |
| 615 EXPECT_TRUE(iter == map.end()); | |
| 616 | |
| 617 for (int i = 2; i < 32; ++i) { | |
| 618 TheMap::AddResult addResult = map.insert(Pair(MoveOnly(i), -i), i * 10); | |
| 619 EXPECT_TRUE(addResult.isNewEntry); | |
| 620 EXPECT_EQ(i, addResult.storedValue->key.first.value()); | |
| 621 EXPECT_EQ(-i, addResult.storedValue->key.second); | |
| 622 EXPECT_EQ(i * 10, addResult.storedValue->value); | |
| 623 } | |
| 624 | |
| 625 iter = map.find(Pair(MoveOnly(1), -1)); | |
| 626 ASSERT_TRUE(iter != map.end()); | |
| 627 EXPECT_EQ(1, iter->key.first.value()); | |
| 628 EXPECT_EQ(-1, iter->key.second); | |
| 629 EXPECT_EQ(10, iter->value); | |
| 630 | |
| 631 iter = map.find(Pair(MoveOnly(7), -7)); | |
| 632 ASSERT_TRUE(iter != map.end()); | |
| 633 EXPECT_EQ(7, iter->key.first.value()); | |
| 634 EXPECT_EQ(-7, iter->key.second); | |
| 635 EXPECT_EQ(70, iter->value); | |
| 636 | |
| 637 { | |
| 638 TheMap::AddResult addResult = map.set(Pair(MoveOnly(9), -9), 999); | |
| 639 EXPECT_FALSE(addResult.isNewEntry); | |
| 640 EXPECT_EQ(9, addResult.storedValue->key.first.value()); | |
| 641 EXPECT_EQ(-9, addResult.storedValue->key.second); | |
| 642 EXPECT_EQ(999, addResult.storedValue->value); | |
| 643 } | |
| 644 | |
| 645 map.erase(Pair(MoveOnly(11), -11)); | |
| 646 iter = map.find(Pair(MoveOnly(11), -11)); | |
| 647 EXPECT_TRUE(iter == map.end()); | |
| 648 | |
| 649 int oneThirty = map.take(Pair(MoveOnly(13), -13)); | |
| 650 EXPECT_EQ(130, oneThirty); | |
| 651 iter = map.find(Pair(MoveOnly(13), -13)); | |
| 652 EXPECT_TRUE(iter == map.end()); | |
| 653 | |
| 654 map.clear(); | |
| 655 } | |
| 656 | |
| 657 bool isOneTwoThree(const HashMap<int, int>& map) { | |
| 658 return map.size() == 3 && map.contains(1) && map.contains(2) && | |
| 659 map.contains(3) && map.at(1) == 11 && map.at(2) == 22 && | |
| 660 map.at(3) == 33; | |
| 661 }; | |
| 662 | |
| 663 HashMap<int, int> returnOneTwoThree() { | |
| 664 return {{1, 11}, {2, 22}, {3, 33}}; | |
| 665 }; | |
| 666 | |
| 667 TEST(HashMapTest, InitializerList) { | |
| 668 HashMap<int, int> empty({}); | |
| 669 EXPECT_TRUE(empty.isEmpty()); | |
| 670 | |
| 671 HashMap<int, int> one({{1, 11}}); | |
| 672 EXPECT_EQ(one.size(), 1u); | |
| 673 EXPECT_TRUE(one.contains(1)); | |
| 674 EXPECT_EQ(one.at(1), 11); | |
| 675 | |
| 676 HashMap<int, int> oneTwoThree({{1, 11}, {2, 22}, {3, 33}}); | |
| 677 EXPECT_EQ(oneTwoThree.size(), 3u); | |
| 678 EXPECT_TRUE(oneTwoThree.contains(1)); | |
| 679 EXPECT_TRUE(oneTwoThree.contains(2)); | |
| 680 EXPECT_TRUE(oneTwoThree.contains(3)); | |
| 681 EXPECT_EQ(oneTwoThree.at(1), 11); | |
| 682 EXPECT_EQ(oneTwoThree.at(2), 22); | |
| 683 EXPECT_EQ(oneTwoThree.at(3), 33); | |
| 684 | |
| 685 // Put some jank so we can check if the assignments can clear them later. | |
| 686 empty.insert(9999, 99999); | |
| 687 one.insert(9999, 99999); | |
| 688 oneTwoThree.insert(9999, 99999); | |
| 689 | |
| 690 empty = {}; | |
| 691 EXPECT_TRUE(empty.isEmpty()); | |
| 692 | |
| 693 one = {{1, 11}}; | |
| 694 EXPECT_EQ(one.size(), 1u); | |
| 695 EXPECT_TRUE(one.contains(1)); | |
| 696 EXPECT_EQ(one.at(1), 11); | |
| 697 | |
| 698 oneTwoThree = {{1, 11}, {2, 22}, {3, 33}}; | |
| 699 EXPECT_EQ(oneTwoThree.size(), 3u); | |
| 700 EXPECT_TRUE(oneTwoThree.contains(1)); | |
| 701 EXPECT_TRUE(oneTwoThree.contains(2)); | |
| 702 EXPECT_TRUE(oneTwoThree.contains(3)); | |
| 703 EXPECT_EQ(oneTwoThree.at(1), 11); | |
| 704 EXPECT_EQ(oneTwoThree.at(2), 22); | |
| 705 EXPECT_EQ(oneTwoThree.at(3), 33); | |
| 706 | |
| 707 // Other ways of construction: as a function parameter and in a return | |
| 708 // statement. | |
| 709 EXPECT_TRUE(isOneTwoThree({{1, 11}, {2, 22}, {3, 33}})); | |
| 710 EXPECT_TRUE(isOneTwoThree(returnOneTwoThree())); | |
| 711 } | |
| 712 | |
| 713 } // anonymous namespace | |
| 714 | |
| 715 } // namespace WTF | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2771783003:
Move wtf_unittests to platform/wtf/. (Closed)
