src/third_party/WebKit/Source/wtf/HashSetTest.cpp

   1 /*
   2  * Copyright (C) 2012 Apple 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/HashSet.h"
  29 #include "wtf/OwnPtr.h"
  30 #include "wtf/PassOwnPtr.h"
  31 #include "wtf/RefCounted.h"
  32 #include <gtest/gtest.h>
  33
  34 namespace {
  35
  36 template<int initialCapacity>
  37     struct InitialCapacityTestHashTraits : public WTF::UnsignedWithZeroKeyHashTraits<int> {
  38     static const int minimumTableSize = initialCapacity;
  39 };
  40
  41 template<unsigned size>
  42 void testInitialCapacity()
  43 {
  44     const unsigned initialCapacity = WTF::HashTableCapacityForSize<size>::value;
  45     HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity> > testSet;
  46
  47     // Initial capacity is null.
  48     EXPECT_EQ(0UL, testSet.capacity());
  49
  50     // Adding items up to size should never change the capacity.
  51     for (size_t i = 0; i < size; ++i) {
  52         testSet.add(i);
  53         EXPECT_EQ(initialCapacity, testSet.capacity());
  54     }
  55
  56     // Adding items up to less than half the capacity should not change the capacity.
  57     unsigned capacityLimit = initialCapacity / 2 - 1;
  58     for (size_t i = size; i < capacityLimit; ++i) {
  59         testSet.add(i);
  60         EXPECT_EQ(initialCapacity, testSet.capacity());
  61     }
  62
  63     // Adding one more item increase the capacity.
  64     testSet.add(initialCapacity);
  65     EXPECT_GT(testSet.capacity(), initialCapacity);
  66 }
  67
  68 template<unsigned size> void generateTestCapacityUpToSize();
  69 template<> void generateTestCapacityUpToSize<0>()
  70 {
  71 }
  72 template<unsigned size> void generateTestCapacityUpToSize()
  73 {
  74     generateTestCapacityUpToSize<size - 1>();
  75     testInitialCapacity<size>();
  76 }
  77
  78 TEST(HashSetTest, InitialCapacity)
  79 {
  80     generateTestCapacityUpToSize<128>();
  81 }
  82
  83 struct Dummy {
  84     Dummy(bool& deleted) : deleted(deleted) { }
  85
  86     ~Dummy()
  87     {
  88         deleted = true;
  89     }
  90
  91     bool& deleted;
  92 };
  93
  94 TEST(HashSetTest, HashSetOwnPtr)
  95 {
  96     bool deleted1 = false, deleted2 = false;
  97
  98     typedef HashSet<OwnPtr<Dummy> > OwnPtrSet;
  99     OwnPtrSet set;
 100
 101     Dummy* ptr1 = new Dummy(deleted1);
 102     {
 103         // AddResult in a separate scope to avoid assertion hit,
 104         // since we modify the container further.
 105         HashSet<OwnPtr<Dummy> >::AddResult res1 = set.add(adoptPtr(ptr1));
 106         EXPECT_EQ(ptr1, res1.storedValue->get());
 107     }
 108
 109     EXPECT_FALSE(deleted1);
 110     EXPECT_EQ(1UL, set.size());
 111     OwnPtrSet::iterator it1 = set.find(ptr1);
 112     EXPECT_NE(set.end(), it1);
 113     EXPECT_EQ(ptr1, (*it1));
 114
 115     Dummy* ptr2 = new Dummy(deleted2);
 116     {
 117         HashSet<OwnPtr<Dummy> >::AddResult res2 = set.add(adoptPtr(ptr2));
 118         EXPECT_EQ(res2.storedValue->get(), ptr2);
 119     }
 120
 121     EXPECT_FALSE(deleted2);
 122     EXPECT_EQ(2UL, set.size());
 123     OwnPtrSet::iterator it2 = set.find(ptr2);
 124     EXPECT_NE(set.end(), it2);
 125     EXPECT_EQ(ptr2, (*it2));
 126
 127     set.remove(ptr1);
 128     EXPECT_TRUE(deleted1);
 129
 130     set.clear();
 131     EXPECT_TRUE(deleted2);
 132     EXPECT_TRUE(set.isEmpty());
 133
 134     deleted1 = false;
 135     deleted2 = false;
 136     {
 137         OwnPtrSet set;
 138         set.add(adoptPtr(new Dummy(deleted1)));
 139         set.add(adoptPtr(new Dummy(deleted2)));
 140     }
 141     EXPECT_TRUE(deleted1);
 142     EXPECT_TRUE(deleted2);
 143 }
 144
 145 class DummyRefCounted: public WTF::RefCounted<DummyRefCounted> {
 146 public:
 147     DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
 148     ~DummyRefCounted() { m_isDeleted = true; }
 149
 150     void ref()
 151     {
 152         WTF::RefCounted<DummyRefCounted>::ref();
 153         ++s_refInvokesCount;
 154     }
 155
 156     static int s_refInvokesCount;
 157
 158 private:
 159     bool& m_isDeleted;
 160 };
 161
 162 int DummyRefCounted::s_refInvokesCount = 0;
 163
 164 TEST(HashSetTest, HashSetRefPtr)
 165 {
 166     bool isDeleted;
 167     RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
 168     EXPECT_EQ(0, DummyRefCounted::s_refInvokesCount);
 169     HashSet<RefPtr<DummyRefCounted> > set;
 170     set.add(ptr);
 171     // Referenced only once (to store a copy in the container).
 172     EXPECT_EQ(1, DummyRefCounted::s_refInvokesCount);
 173
 174     DummyRefCounted* rawPtr = ptr.get();
 175
 176     EXPECT_TRUE(set.contains(rawPtr));
 177     EXPECT_NE(set.end(), set.find(rawPtr));
 178     EXPECT_TRUE(set.contains(ptr));
 179     EXPECT_NE(set.end(), set.find(ptr));
 180
 181     ptr.clear();
 182     EXPECT_FALSE(isDeleted);
 183
 184     set.remove(rawPtr);
 185     EXPECT_TRUE(isDeleted);
 186     EXPECT_TRUE(set.isEmpty());
 187     EXPECT_EQ(1, DummyRefCounted::s_refInvokesCount);
 188 }
 189
 190
 191 } // namespace