third_party/WebKit/Source/wtf/HashMapTest.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 #include "wtf/HashMap.h"
  28
  29 #include "wtf/OwnPtr.h"
  30 #include "wtf/PassOwnPtr.h"
  31 #include "wtf/PassRefPtr.h"
  32 #include "wtf/RefCounted.h"
  33 #include "wtf/Vector.h"
  34 #include <gtest/gtest.h>
  35
  36 namespace WTF {
  37
  38 namespace {
  39
  40 using IntHashMap = HashMap<int, int>;
  41
  42 TEST(HashMapTest, IteratorComparison)
  43 {
  44     IntHashMap map;
  45     map.add(1, 2);
  46     EXPECT_TRUE(map.begin() != map.end());
  47     EXPECT_FALSE(map.begin() == map.end());
  48
  49     IntHashMap::const_iterator begin = map.begin();
  50     EXPECT_TRUE(begin == map.begin());
  51     EXPECT_TRUE(map.begin() == begin);
  52     EXPECT_TRUE(begin != map.end());
  53     EXPECT_TRUE(map.end() != begin);
  54     EXPECT_FALSE(begin != map.begin());
  55     EXPECT_FALSE(map.begin() != begin);
  56     EXPECT_FALSE(begin == map.end());
  57     EXPECT_FALSE(map.end() == begin);
  58 }
  59
  60 struct TestDoubleHashTraits : HashTraits<double> {
  61     static const unsigned minimumTableSize = 8;
  62 };
  63
  64 using DoubleHashMap = HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits>;
  65
  66 int bucketForKey(double key)
  67 {
  68     return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
  69 }
  70
  71 TEST(HashMapTest, DoubleHashCollisions)
  72 {
  73     // The "clobber" key here is one that ends up stealing the bucket that the -0 key
  74     // originally wants to be in. This makes the 0 and -0 keys collide and the test then
  75     // fails unless the FloatHash::equals() implementation can distinguish them.
  76     const double clobberKey = 6;
  77     const double zeroKey = 0;
  78     const double negativeZeroKey = -zeroKey;
  79
  80     DoubleHashMap map;
  81
  82     map.add(clobberKey, 1);
  83     map.add(zeroKey, 2);
  84     map.add(negativeZeroKey, 3);
  85
  86     EXPECT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
  87     EXPECT_EQ(1, map.get(clobberKey));
  88     EXPECT_EQ(2, map.get(zeroKey));
  89     EXPECT_EQ(3, map.get(negativeZeroKey));
  90 }
  91
  92 class DestructCounter {
  93 public:
  94     explicit DestructCounter(int i, int* destructNumber)
  95         : m_i(i)
  96         , m_destructNumber(destructNumber)
  97     { }
  98
  99     ~DestructCounter() { ++(*m_destructNumber); }
 100     int get() const { return m_i; }
 101
 102 private:
 103     int m_i;
 104     int* m_destructNumber;
 105 };
 106
 107 using OwnPtrHashMap = HashMap<int, OwnPtr<DestructCounter>>;
 108
 109 TEST(HashMapTest, OwnPtrAsValue)
 110 {
 111     int destructNumber = 0;
 112     OwnPtrHashMap map;
 113     map.add(1, adoptPtr(new DestructCounter(1, &destructNumber)));
 114     map.add(2, adoptPtr(new DestructCounter(2, &destructNumber)));
 115
 116     DestructCounter* counter1 = map.get(1);
 117     EXPECT_EQ(1, counter1->get());
 118     DestructCounter* counter2 = map.get(2);
 119     EXPECT_EQ(2, counter2->get());
 120     EXPECT_EQ(0, destructNumber);
 121
 122     for (OwnPtrHashMap::iterator iter = map.begin(); iter != map.end(); ++iter) {
 123         OwnPtr<DestructCounter>& ownCounter = iter->value;
 124         EXPECT_EQ(iter->key, ownCounter->get());
 125     }
 126     ASSERT_EQ(0, destructNumber);
 127
 128     OwnPtr<DestructCounter> ownCounter1 = map.take(1);
 129     EXPECT_EQ(ownCounter1.get(), counter1);
 130     EXPECT_FALSE(map.contains(1));
 131     EXPECT_EQ(0, destructNumber);
 132
 133     map.remove(2);
 134     EXPECT_FALSE(map.contains(2));
 135     EXPECT_EQ(0UL, map.size());
 136     EXPECT_EQ(1, destructNumber);
 137
 138     ownCounter1.clear();
 139     EXPECT_EQ(2, destructNumber);
 140 }
 141
 142 class DummyRefCounted : public RefCounted<DummyRefCounted> {
 143 public:
 144     DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
 145     ~DummyRefCounted()
 146     {
 147         ASSERT(!m_isDeleted);
 148         m_isDeleted = true;
 149     }
 150
 151     void ref()
 152     {
 153         ASSERT(!m_isDeleted);
 154         WTF::RefCounted<DummyRefCounted>::ref();
 155         ++m_refInvokesCount;
 156     }
 157
 158     void deref()
 159     {
 160         ASSERT(!m_isDeleted);
 161         WTF::RefCounted<DummyRefCounted>::deref();
 162     }
 163
 164     static int m_refInvokesCount;
 165
 166 private:
 167     bool& m_isDeleted;
 168 };
 169
 170 int DummyRefCounted::m_refInvokesCount = 0;
 171
 172 TEST(HashMapTest, RefPtrAsKey)
 173 {
 174     bool isDeleted = false;
 175     DummyRefCounted::m_refInvokesCount = 0;
 176     RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
 177     EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount);
 178     HashMap<RefPtr<DummyRefCounted>, int> map;
 179     map.add(ptr, 1);
 180     // Referenced only once (to store a copy in the container).
 181     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 182     EXPECT_EQ(1, map.get(ptr));
 183
 184     DummyRefCounted* rawPtr = ptr.get();
 185
 186     EXPECT_TRUE(map.contains(rawPtr));
 187     EXPECT_NE(map.end(), map.find(rawPtr));
 188     EXPECT_TRUE(map.contains(ptr));
 189     EXPECT_NE(map.end(), map.find(ptr));
 190     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 191
 192     ptr.clear();
 193     EXPECT_FALSE(isDeleted);
 194
 195     map.remove(rawPtr);
 196     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 197     EXPECT_TRUE(isDeleted);
 198     EXPECT_TRUE(map.isEmpty());
 199 }
 200
 201 TEST(HashMaptest, RemoveAdd)
 202 {
 203     DummyRefCounted::m_refInvokesCount = 0;
 204     bool isDeleted = false;
 205
 206     typedef HashMap<int, RefPtr<DummyRefCounted>> Map;
 207     Map map;
 208
 209     RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
 210     EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount);
 211
 212     map.add(1, ptr);
 213     // Referenced only once (to store a copy in the container).
 214     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 215     EXPECT_EQ(ptr, map.get(1));
 216
 217     ptr.clear();
 218     EXPECT_FALSE(isDeleted);
 219
 220     map.remove(1);
 221     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 222     EXPECT_TRUE(isDeleted);
 223     EXPECT_TRUE(map.isEmpty());
 224
 225     // Add and remove until the deleted slot is reused.
 226     for (int i = 1; i < 100; i++) {
 227         bool isDeleted2 = false;
 228         RefPtr<DummyRefCounted> ptr2 = adoptRef(new DummyRefCounted(isDeleted2));
 229         map.add(i, ptr2);
 230         EXPECT_FALSE(isDeleted2);
 231         ptr2.clear();
 232         EXPECT_FALSE(isDeleted2);
 233         map.remove(i);
 234         EXPECT_TRUE(isDeleted2);
 235     }
 236 }
 237
 238 class SimpleClass {
 239 public:
 240     explicit SimpleClass(int v) : m_v(v) { }
 241     int v() { return m_v; }
 242
 243 private:
 244     int m_v;
 245 };
 246 using IntSimpleMap = HashMap<int, OwnPtr<SimpleClass>>;
 247
 248 TEST(HashMapTest, AddResult)
 249 {
 250     IntSimpleMap map;
 251     IntSimpleMap::AddResult result = map.add(1, nullptr);
 252     EXPECT_TRUE(result.isNewEntry);
 253     EXPECT_EQ(1, result.storedValue->key);
 254     EXPECT_EQ(0, result.storedValue->value.get());
 255
 256     SimpleClass* simple1 = new SimpleClass(1);
 257     result.storedValue->value = adoptPtr(simple1);
 258     EXPECT_EQ(simple1, map.get(1));
 259
 260     IntSimpleMap::AddResult result2 = map.add(1, adoptPtr(new SimpleClass(2)));
 261     EXPECT_FALSE(result2.isNewEntry);
 262     EXPECT_EQ(1, result.storedValue->key);
 263     EXPECT_EQ(1, result.storedValue->value->v());
 264     EXPECT_EQ(1, map.get(1)->v());
 265 }
 266
 267 TEST(HashMapTest, AddResultVectorValue)
 268 {
 269     using IntVectorMap = HashMap<int, Vector<int>>;
 270     IntVectorMap map;
 271     IntVectorMap::AddResult result = map.add(1, Vector<int>());
 272     EXPECT_TRUE(result.isNewEntry);
 273     EXPECT_EQ(1, result.storedValue->key);
 274     EXPECT_EQ(0u, result.storedValue->value.size());
 275
 276     result.storedValue->value.append(11);
 277     EXPECT_EQ(1u, map.find(1)->value.size());
 278     EXPECT_EQ(11, map.find(1)->value.first());
 279
 280     IntVectorMap::AddResult result2 = map.add(1, Vector<int>());
 281     EXPECT_FALSE(result2.isNewEntry);
 282     EXPECT_EQ(1, result.storedValue->key);
 283     EXPECT_EQ(1u, result.storedValue->value.size());
 284     EXPECT_EQ(11, result.storedValue->value.first());
 285     EXPECT_EQ(11, map.find(1)->value.first());
 286 }
 287
 288 class InstanceCounter {
 289 public:
 290     InstanceCounter() { ++counter; }
 291     InstanceCounter(const InstanceCounter& another) { ++counter; }
 292     ~InstanceCounter() { --counter; }
 293     static int counter;
 294 };
 295 int InstanceCounter::counter = 0;
 296
 297 TEST(HashMapTest, ValueTypeDestructed)
 298 {
 299     InstanceCounter::counter = 0;
 300     HashMap<int, InstanceCounter> map;
 301     map.set(1, InstanceCounter());
 302     map.clear();
 303     EXPECT_EQ(0, InstanceCounter::counter);
 304 }
 305
 306 } // anonymous namespace
 307
 308 } // namespace WTF