src/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
  28 #include "wtf/HashMap.h"
  29 #include "wtf/OwnPtr.h"
  30 #include "wtf/PassOwnPtr.h"
  31 #include "wtf/PassRefPtr.h"
  32 #include "wtf/RefCounted.h"
  33 #include <gtest/gtest.h>
  34
  35 namespace {
  36
  37 typedef WTF::HashMap<int, int> IntHashMap;
  38
  39 TEST(HashMapTest, IteratorComparison)
  40 {
  41     IntHashMap map;
  42     map.add(1, 2);
  43     EXPECT_TRUE(map.begin() != map.end());
  44     EXPECT_FALSE(map.begin() == map.end());
  45
  46     IntHashMap::const_iterator begin = map.begin();
  47     EXPECT_TRUE(begin == map.begin());
  48     EXPECT_TRUE(map.begin() == begin);
  49     EXPECT_TRUE(begin != map.end());
  50     EXPECT_TRUE(map.end() != begin);
  51     EXPECT_FALSE(begin != map.begin());
  52     EXPECT_FALSE(map.begin() != begin);
  53     EXPECT_FALSE(begin == map.end());
  54     EXPECT_FALSE(map.end() == begin);
  55 }
  56
  57 struct TestDoubleHashTraits : HashTraits<double> {
  58     static const unsigned minimumTableSize = 8;
  59 };
  60
  61 typedef HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashMap;
  62
  63 static int bucketForKey(double key)
  64 {
  65     return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
  66 }
  67
  68 TEST(HashMapTest, DoubleHashCollisions)
  69 {
  70     // The "clobber" key here is one that ends up stealing the bucket that the -0 key
  71     // originally wants to be in. This makes the 0 and -0 keys collide and the test then
  72     // fails unless the FloatHash::equals() implementation can distinguish them.
  73     const double clobberKey = 6;
  74     const double zeroKey = 0;
  75     const double negativeZeroKey = -zeroKey;
  76
  77     DoubleHashMap map;
  78
  79     map.add(clobberKey, 1);
  80     map.add(zeroKey, 2);
  81     map.add(negativeZeroKey, 3);
  82
  83     EXPECT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
  84     EXPECT_EQ(1, map.get(clobberKey));
  85     EXPECT_EQ(2, map.get(zeroKey));
  86     EXPECT_EQ(3, map.get(negativeZeroKey));
  87 }
  88
  89 class DestructCounter {
  90 public:
  91     explicit DestructCounter(int i, int* destructNumber)
  92         : m_i(i)
  93         , m_destructNumber(destructNumber)
  94     { }
  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 typedef WTF::HashMap<int, OwnPtr<DestructCounter> > OwnPtrHashMap;
 105
 106 TEST(HashMapTest, OwnPtrAsValue)
 107 {
 108     int destructNumber = 0;
 109     OwnPtrHashMap map;
 110     map.add(1, adoptPtr(new DestructCounter(1, &destructNumber)));
 111     map.add(2, adoptPtr(new DestructCounter(2, &destructNumber)));
 112
 113     DestructCounter* counter1 = map.get(1);
 114     EXPECT_EQ(1, counter1->get());
 115     DestructCounter* counter2 = map.get(2);
 116     EXPECT_EQ(2, counter2->get());
 117     EXPECT_EQ(0, destructNumber);
 118
 119     for (OwnPtrHashMap::iterator iter = map.begin(); iter != map.end(); ++iter) {
 120         OwnPtr<DestructCounter>& ownCounter = iter->value;
 121         EXPECT_EQ(iter->key, ownCounter->get());
 122     }
 123     ASSERT_EQ(0, destructNumber);
 124
 125     OwnPtr<DestructCounter> ownCounter1 = map.take(1);
 126     EXPECT_EQ(ownCounter1.get(), counter1);
 127     EXPECT_FALSE(map.contains(1));
 128     EXPECT_EQ(0, destructNumber);
 129
 130     map.remove(2);
 131     EXPECT_FALSE(map.contains(2));
 132     EXPECT_EQ(0UL, map.size());
 133     EXPECT_EQ(1, destructNumber);
 134
 135     ownCounter1.clear();
 136     EXPECT_EQ(2, destructNumber);
 137 }
 138
 139
 140 class DummyRefCounted: public WTF::RefCounted<DummyRefCounted> {
 141 public:
 142     DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
 143     ~DummyRefCounted() { m_isDeleted = true; }
 144
 145     void ref()
 146     {
 147         WTF::RefCounted<DummyRefCounted>::ref();
 148         ++m_refInvokesCount;
 149     }
 150
 151     static int m_refInvokesCount;
 152
 153 private:
 154     bool& m_isDeleted;
 155 };
 156
 157 int DummyRefCounted::m_refInvokesCount = 0;
 158
 159 TEST(HashMapTest, RefPtrAsKey)
 160 {
 161     bool isDeleted;
 162     RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
 163     EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount);
 164     HashMap<RefPtr<DummyRefCounted>, int> map;
 165     map.add(ptr, 1);
 166     // Referenced only once (to store a copy in the container).
 167     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 168     EXPECT_EQ(1, map.get(ptr));
 169
 170     DummyRefCounted* rawPtr = ptr.get();
 171
 172     EXPECT_TRUE(map.contains(rawPtr));
 173     EXPECT_NE(map.end(), map.find(rawPtr));
 174     EXPECT_TRUE(map.contains(ptr));
 175     EXPECT_NE(map.end(), map.find(ptr));
 176     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 177
 178     ptr.clear();
 179     EXPECT_FALSE(isDeleted);
 180
 181     map.remove(rawPtr);
 182     EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 183     EXPECT_TRUE(isDeleted);
 184     EXPECT_TRUE(map.isEmpty());
 185 }
 186
 187 class SimpleClass {
 188 public:
 189     explicit SimpleClass(int v) : m_v(v) { }
 190     int v() { return m_v; }
 191
 192 private:
 193     int m_v;
 194 };
 195 typedef HashMap<int, OwnPtr<SimpleClass> > IntSimpleMap;
 196
 197 TEST(HashMapTest, AddResult)
 198 {
 199     IntSimpleMap map;
 200     IntSimpleMap::AddResult result = map.add(1, nullptr);
 201     EXPECT_TRUE(result.isNewEntry);
 202     EXPECT_EQ(1, result.storedValue->key);
 203     EXPECT_EQ(0, result.storedValue->value.get());
 204
 205     SimpleClass* simple1 = new SimpleClass(1);
 206     result.storedValue->value = adoptPtr(simple1);
 207     EXPECT_EQ(simple1, map.get(1));
 208
 209     IntSimpleMap::AddResult result2 = map.add(1, adoptPtr(new SimpleClass(2)));
 210     EXPECT_FALSE(result2.isNewEntry);
 211     EXPECT_EQ(1, map.get(1)->v());
 212 }
 213
 214 } // namespace