Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

   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 "config.h"
  27
  28 #include "Counters.h"
  29 #include "MoveOnly.h"
  30 #include <string>
  31 #include <wtf/HashMap.h>
  32 #include <wtf/text/StringHash.h>
  33 #include <wtf/OwnPtr.h>
  34 #include <wtf/PassOwnPtr.h>
  35
  36 namespace TestWebKitAPI {
  37
  38 typedef WTF::HashMap<int, int> IntHashMap;
  39
  40 TEST(WTF_HashMap, HashTableIteratorComparison)
  41 {
  42     IntHashMap map;
  43     map.add(1, 2);
  44     ASSERT_TRUE(map.begin() != map.end());
  45     ASSERT_FALSE(map.begin() == map.end());
  46
  47     IntHashMap::const_iterator begin = map.begin();
  48     ASSERT_TRUE(begin == map.begin());
  49     ASSERT_TRUE(map.begin() == begin);
  50     ASSERT_TRUE(begin != map.end());
  51     ASSERT_TRUE(map.end() != begin);
  52     ASSERT_FALSE(begin != map.begin());
  53     ASSERT_FALSE(map.begin() != begin);
  54     ASSERT_FALSE(begin == map.end());
  55     ASSERT_FALSE(map.end() == begin);
  56 }
  57
  58 struct TestDoubleHashTraits : HashTraits<double> {
  59     static const int minimumTableSize = 8;
  60 };
  61
  62 typedef HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashMap;
  63
  64 static int bucketForKey(double key)
  65 {
  66     return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
  67 }
  68
  69 TEST(WTF_HashMap, DoubleHashCollisions)
  70 {
  71     // The "clobber" key here is one that ends up stealing the bucket that the -0 key
  72     // originally wants to be in. This makes the 0 and -0 keys collide and the test then
  73     // fails unless the FloatHash::equals() implementation can distinguish them.
  74     const double clobberKey = 6;
  75     const double zeroKey = 0;
  76     const double negativeZeroKey = -zeroKey;
  77
  78     DoubleHashMap map;
  79
  80     map.add(clobberKey, 1);
  81     map.add(zeroKey, 2);
  82     map.add(negativeZeroKey, 3);
  83
  84     ASSERT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
  85     ASSERT_EQ(map.get(clobberKey), 1);
  86     ASSERT_EQ(map.get(zeroKey), 2);
  87     ASSERT_EQ(map.get(negativeZeroKey), 3);
  88 }
  89
  90 TEST(WTF_HashMap, MoveOnlyValues)
  91 {
  92     HashMap<unsigned, MoveOnly> moveOnlyValues;
  93
  94     for (size_t i = 0; i < 100; ++i) {
  95         MoveOnly moveOnly(i + 1);
  96         moveOnlyValues.set(i + 1, WTF::move(moveOnly));
  97     }
  98
  99     for (size_t i = 0; i < 100; ++i) {
 100         auto it = moveOnlyValues.find(i + 1);
 101         ASSERT_FALSE(it == moveOnlyValues.end());
 102     }
 103
 104     for (size_t i = 0; i < 50; ++i)
 105         ASSERT_EQ(moveOnlyValues.take(i + 1).value(), i + 1);
 106
 107     for (size_t i = 50; i < 100; ++i)
 108         ASSERT_TRUE(moveOnlyValues.remove(i + 1));
 109
 110     ASSERT_TRUE(moveOnlyValues.isEmpty());
 111 }
 112
 113 TEST(WTF_HashMap, MoveOnlyKeys)
 114 {
 115     HashMap<MoveOnly, unsigned> moveOnlyKeys;
 116
 117     for (size_t i = 0; i < 100; ++i) {
 118         MoveOnly moveOnly(i + 1);
 119         moveOnlyKeys.set(WTF::move(moveOnly), i + 1);
 120     }
 121
 122     for (size_t i = 0; i < 100; ++i) {
 123         auto it = moveOnlyKeys.find(MoveOnly(i + 1));
 124         ASSERT_FALSE(it == moveOnlyKeys.end());
 125     }
 126
 127     for (size_t i = 0; i < 100; ++i)
 128         ASSERT_FALSE(moveOnlyKeys.add(MoveOnly(i + 1), i + 1).isNewEntry);
 129
 130     for (size_t i = 0; i < 100; ++i)
 131         ASSERT_TRUE(moveOnlyKeys.remove(MoveOnly(i + 1)));
 132
 133     ASSERT_TRUE(moveOnlyKeys.isEmpty());
 134 }
 135
 136 TEST(WTF_HashMap, InitializerList)
 137 {
 138     HashMap<unsigned, std::string> map = {
 139         { 1, "one" },
 140         { 2, "two" },
 141         { 3, "three" },
 142         { 4, "four" },
 143     };
 144
 145     EXPECT_EQ(4, map.size());
 146
 147     EXPECT_EQ("one", map.get(1));
 148     EXPECT_EQ("two", map.get(2));
 149     EXPECT_EQ("three", map.get(3));
 150     EXPECT_EQ("four", map.get(4));
 151     EXPECT_EQ(std::string(), map.get(5));
 152 }
 153
 154 TEST(WTF_HashMap, EfficientGetter)
 155 {
 156     HashMap<unsigned, CopyMoveCounter> map;
 157     map.set(1, CopyMoveCounter());
 158
 159     {
 160         CopyMoveCounter::TestingScope scope;
 161         map.get(1);
 162         EXPECT_EQ(0U, CopyMoveCounter::constructionCount);
 163         EXPECT_EQ(1U, CopyMoveCounter::copyCount);
 164         EXPECT_EQ(0U, CopyMoveCounter::moveCount);
 165     }
 166
 167     {
 168         CopyMoveCounter::TestingScope scope;
 169         map.get(2);
 170         EXPECT_EQ(1U, CopyMoveCounter::constructionCount);
 171         EXPECT_EQ(0U, CopyMoveCounter::copyCount);
 172         EXPECT_EQ(1U, CopyMoveCounter::moveCount);
 173     }
 174 }
 175
 176 TEST(WTF_HashMap, OwnPtrKey)
 177 {
 178     ConstructorDestructorCounter::TestingScope scope;
 179
 180     HashMap<OwnPtr<ConstructorDestructorCounter>, int> map;
 181
 182     OwnPtr<ConstructorDestructorCounter> ownPtr = adoptPtr(new ConstructorDestructorCounter);
 183     map.add(WTF::move(ownPtr), 2);
 184
 185     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 186     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 187
 188     map.clear();
 189
 190     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 191     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 192 }
 193
 194 TEST(WTF_HashMap, OwnPtrKey_FindUsingRawPointer)
 195 {
 196     HashMap<OwnPtr<int>, int> map;
 197
 198     OwnPtr<int> ownPtr = adoptPtr(new int(5));
 199     int* ptr = ownPtr.get();
 200     map.add(WTF::move(ownPtr), 2);
 201
 202     auto it = map.find(ptr);
 203     ASSERT_TRUE(it != map.end());
 204     EXPECT_EQ(ptr, it->key.get());
 205     EXPECT_EQ(2, it->value);
 206 }
 207
 208 TEST(WTF_HashMap, OwnPtrKey_ContainsUsingRawPointer)
 209 {
 210     HashMap<OwnPtr<int>, int> map;
 211
 212     OwnPtr<int> ownPtr = adoptPtr(new int(5));
 213     int* ptr = ownPtr.get();
 214     map.add(WTF::move(ownPtr), 2);
 215
 216     EXPECT_EQ(true, map.contains(ptr));
 217 }
 218
 219 TEST(WTF_HashMap, OwnPtrKey_GetUsingRawPointer)
 220 {
 221     HashMap<OwnPtr<int>, int> map;
 222
 223     OwnPtr<int> ownPtr = adoptPtr(new int(5));
 224     int* ptr = ownPtr.get();
 225     map.add(WTF::move(ownPtr), 2);
 226
 227     int value = map.get(ptr);
 228     EXPECT_EQ(2, value);
 229 }
 230
 231 TEST(WTF_HashMap, OwnPtrKey_RemoveUsingRawPointer)
 232 {
 233     ConstructorDestructorCounter::TestingScope scope;
 234
 235     HashMap<OwnPtr<ConstructorDestructorCounter>, int> map;
 236
 237     OwnPtr<ConstructorDestructorCounter> ownPtr = adoptPtr(new ConstructorDestructorCounter);
 238     ConstructorDestructorCounter* ptr = ownPtr.get();
 239     map.add(WTF::move(ownPtr), 2);
 240
 241     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 242     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 243
 244     bool result = map.remove(ptr);
 245     EXPECT_EQ(true, result);
 246
 247     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 248     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 249 }
 250
 251 TEST(WTF_HashMap, OwnPtrKey_TakeUsingRawPointer)
 252 {
 253     ConstructorDestructorCounter::TestingScope scope;
 254
 255     HashMap<OwnPtr<ConstructorDestructorCounter>, int> map;
 256
 257     OwnPtr<ConstructorDestructorCounter> ownPtr = adoptPtr(new ConstructorDestructorCounter);
 258     ConstructorDestructorCounter* ptr = ownPtr.get();
 259     map.add(WTF::move(ownPtr), 2);
 260
 261     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 262     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 263
 264     int result = map.take(ptr);
 265     EXPECT_EQ(2, result);
 266
 267     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 268     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 269 }
 270
 271 TEST(WTF_HashMap, UniquePtrKey)
 272 {
 273     ConstructorDestructorCounter::TestingScope scope;
 274
 275     HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
 276
 277     auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
 278     map.add(WTF::move(uniquePtr), 2);
 279
 280     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 281     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 282
 283     map.clear();
 284
 285     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 286     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 287 }
 288
 289 TEST(WTF_HashMap, UniquePtrKey_CustomDeleter)
 290 {
 291     ConstructorDestructorCounter::TestingScope constructorDestructorCounterScope;
 292     DeleterCounter<ConstructorDestructorCounter>::TestingScope deleterCounterScope;
 293
 294     HashMap<std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>>, int> map;
 295
 296     std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>> uniquePtr(new ConstructorDestructorCounter(), DeleterCounter<ConstructorDestructorCounter>());
 297     map.add(WTF::move(uniquePtr), 2);
 298
 299     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 300     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 301
 302     EXPECT_EQ(0u, DeleterCounter<ConstructorDestructorCounter>::deleterCount);
 303
 304     map.clear();
 305
 306     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 307     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 308
 309     EXPECT_EQ(1u, DeleterCounter<ConstructorDestructorCounter>::deleterCount);
 310 }
 311
 312 TEST(WTF_HashMap, UniquePtrKey_FindUsingRawPointer)
 313 {
 314     HashMap<std::unique_ptr<int>, int> map;
 315
 316     auto uniquePtr = std::make_unique<int>(5);
 317     int* ptr = uniquePtr.get();
 318     map.add(WTF::move(uniquePtr), 2);
 319
 320     auto it = map.find(ptr);
 321     ASSERT_TRUE(it != map.end());
 322     EXPECT_EQ(ptr, it->key.get());
 323     EXPECT_EQ(2, it->value);
 324 }
 325
 326 TEST(WTF_HashMap, UniquePtrKey_ContainsUsingRawPointer)
 327 {
 328     HashMap<std::unique_ptr<int>, int> map;
 329
 330     auto uniquePtr = std::make_unique<int>(5);
 331     int* ptr = uniquePtr.get();
 332     map.add(WTF::move(uniquePtr), 2);
 333
 334     EXPECT_EQ(true, map.contains(ptr));
 335 }
 336
 337 TEST(WTF_HashMap, UniquePtrKey_GetUsingRawPointer)
 338 {
 339     HashMap<std::unique_ptr<int>, int> map;
 340
 341     auto uniquePtr = std::make_unique<int>(5);
 342     int* ptr = uniquePtr.get();
 343     map.add(WTF::move(uniquePtr), 2);
 344
 345     int value = map.get(ptr);
 346     EXPECT_EQ(2, value);
 347 }
 348
 349 TEST(WTF_HashMap, UniquePtrKey_RemoveUsingRawPointer)
 350 {
 351     ConstructorDestructorCounter::TestingScope scope;
 352
 353     HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
 354
 355     auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
 356     ConstructorDestructorCounter* ptr = uniquePtr.get();
 357     map.add(WTF::move(uniquePtr), 2);
 358
 359     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 360     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 361
 362     bool result = map.remove(ptr);
 363     EXPECT_EQ(true, result);
 364
 365     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 366     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 367 }
 368
 369 TEST(WTF_HashMap, UniquePtrKey_TakeUsingRawPointer)
 370 {
 371     ConstructorDestructorCounter::TestingScope scope;
 372
 373     HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
 374
 375     auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
 376     ConstructorDestructorCounter* ptr = uniquePtr.get();
 377     map.add(WTF::move(uniquePtr), 2);
 378
 379     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 380     EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
 381
 382     int result = map.take(ptr);
 383     EXPECT_EQ(2, result);
 384
 385     EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
 386     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 387 }
 388
 389 } // namespace TestWebKitAPI