Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / WebKit / Source / wtf / HashSetTest.cpp
blob824df7ddad5f9542d7afae6d01084d51b0757809
1 /*
2 * Copyright (C) 2012 Apple Inc. All rights reserved.
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.
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.
26 #include "config.h"
27 #include "wtf/HashSet.h"
29 #include "wtf/OwnPtr.h"
30 #include "wtf/PassOwnPtr.h"
31 #include "wtf/RefCounted.h"
32 #include <gtest/gtest.h>
34 namespace WTF {
36 template<int initialCapacity>
37 struct InitialCapacityTestHashTraits : public UnsignedWithZeroKeyHashTraits<int> {
38 static const int minimumTableSize = initialCapacity;
41 namespace {
43 template<unsigned size>
44 void testInitialCapacity()
46 const unsigned initialCapacity = HashTableCapacityForSize<size>::value;
47 HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity>> testSet;
49 // Initial capacity is null.
50 EXPECT_EQ(0UL, testSet.capacity());
52 // Adding items up to size should never change the capacity.
53 for (size_t i = 0; i < size; ++i) {
54 testSet.add(i);
55 EXPECT_EQ(initialCapacity, testSet.capacity());
58 // Adding items up to less than half the capacity should not change the capacity.
59 unsigned capacityLimit = initialCapacity / 2 - 1;
60 for (size_t i = size; i < capacityLimit; ++i) {
61 testSet.add(i);
62 EXPECT_EQ(initialCapacity, testSet.capacity());
65 // Adding one more item increase the capacity.
66 testSet.add(initialCapacity);
67 EXPECT_GT(testSet.capacity(), initialCapacity);
70 template<unsigned size> void generateTestCapacityUpToSize();
71 template<> void generateTestCapacityUpToSize<0>()
74 template<unsigned size> void generateTestCapacityUpToSize()
76 generateTestCapacityUpToSize<size - 1>();
77 testInitialCapacity<size>();
80 TEST(HashSetTest, InitialCapacity)
82 generateTestCapacityUpToSize<128>();
85 template<unsigned size> void testReserveCapacity();
86 template<> void testReserveCapacity<0>() {}
87 template<unsigned size> void testReserveCapacity()
89 const unsigned expectedInitialCapacity = HashTableCapacityForSize<size>::value;
90 HashSet<int> testSet;
92 // Initial capacity is null.
93 EXPECT_EQ(0UL, testSet.capacity());
95 testSet.reserveCapacityForSize(size);
96 EXPECT_EQ(expectedInitialCapacity, testSet.capacity());
98 // Adding items up to size should never change the capacity.
99 for (size_t i = 0; i < size; ++i) {
100 testSet.add(i + 1); // Avoid adding '0'.
101 EXPECT_EQ(expectedInitialCapacity, testSet.capacity());
104 // Adding items up to less than half the capacity should not change the capacity.
105 unsigned capacityLimit = expectedInitialCapacity / 2 - 1;
106 for (size_t i = size; i < capacityLimit; ++i) {
107 testSet.add(i + 1);
108 EXPECT_EQ(expectedInitialCapacity, testSet.capacity());
111 // Adding one more item increase the capacity.
112 testSet.add(expectedInitialCapacity);
113 EXPECT_GT(testSet.capacity(), expectedInitialCapacity);
115 testReserveCapacity<size-1>();
118 TEST(HashSetTest, ReserveCapacity)
120 testReserveCapacity<128>();
123 struct Dummy {
124 Dummy(bool& deleted) : deleted(deleted) { }
126 ~Dummy()
128 deleted = true;
131 bool& deleted;
134 TEST(HashSetTest, HashSetOwnPtr)
136 bool deleted1 = false, deleted2 = false;
138 typedef HashSet<OwnPtr<Dummy>> OwnPtrSet;
139 OwnPtrSet set;
141 Dummy* ptr1 = new Dummy(deleted1);
143 // AddResult in a separate scope to avoid assertion hit,
144 // since we modify the container further.
145 HashSet<OwnPtr<Dummy>>::AddResult res1 = set.add(adoptPtr(ptr1));
146 EXPECT_EQ(ptr1, res1.storedValue->get());
149 EXPECT_FALSE(deleted1);
150 EXPECT_EQ(1UL, set.size());
151 OwnPtrSet::iterator it1 = set.find(ptr1);
152 EXPECT_NE(set.end(), it1);
153 EXPECT_EQ(ptr1, (*it1));
155 Dummy* ptr2 = new Dummy(deleted2);
157 HashSet<OwnPtr<Dummy>>::AddResult res2 = set.add(adoptPtr(ptr2));
158 EXPECT_EQ(res2.storedValue->get(), ptr2);
161 EXPECT_FALSE(deleted2);
162 EXPECT_EQ(2UL, set.size());
163 OwnPtrSet::iterator it2 = set.find(ptr2);
164 EXPECT_NE(set.end(), it2);
165 EXPECT_EQ(ptr2, (*it2));
167 set.remove(ptr1);
168 EXPECT_TRUE(deleted1);
170 set.clear();
171 EXPECT_TRUE(deleted2);
172 EXPECT_TRUE(set.isEmpty());
174 deleted1 = false;
175 deleted2 = false;
177 OwnPtrSet set;
178 set.add(adoptPtr(new Dummy(deleted1)));
179 set.add(adoptPtr(new Dummy(deleted2)));
181 EXPECT_TRUE(deleted1);
182 EXPECT_TRUE(deleted2);
184 deleted1 = false;
185 deleted2 = false;
186 OwnPtr<Dummy> ownPtr1;
187 OwnPtr<Dummy> ownPtr2;
188 ptr1 = new Dummy(deleted1);
189 ptr2 = new Dummy(deleted2);
191 OwnPtrSet set;
192 set.add(adoptPtr(ptr1));
193 set.add(adoptPtr(ptr2));
194 ownPtr1 = set.take(ptr1);
195 EXPECT_EQ(1UL, set.size());
196 ownPtr2 = set.takeAny();
197 EXPECT_TRUE(set.isEmpty());
199 EXPECT_FALSE(deleted1);
200 EXPECT_FALSE(deleted2);
202 EXPECT_EQ(ptr1, ownPtr1);
203 EXPECT_EQ(ptr2, ownPtr2);
206 class DummyRefCounted : public RefCounted<DummyRefCounted> {
207 public:
208 DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
209 ~DummyRefCounted() { m_isDeleted = true; }
211 void ref()
213 WTF::RefCounted<DummyRefCounted>::ref();
214 ++s_refInvokesCount;
217 static int s_refInvokesCount;
219 private:
220 bool& m_isDeleted;
223 int DummyRefCounted::s_refInvokesCount = 0;
225 TEST(HashSetTest, HashSetRefPtr)
227 bool isDeleted = false;
228 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
229 EXPECT_EQ(0, DummyRefCounted::s_refInvokesCount);
230 HashSet<RefPtr<DummyRefCounted>> set;
231 set.add(ptr);
232 // Referenced only once (to store a copy in the container).
233 EXPECT_EQ(1, DummyRefCounted::s_refInvokesCount);
235 DummyRefCounted* rawPtr = ptr.get();
237 EXPECT_TRUE(set.contains(rawPtr));
238 EXPECT_NE(set.end(), set.find(rawPtr));
239 EXPECT_TRUE(set.contains(ptr));
240 EXPECT_NE(set.end(), set.find(ptr));
242 ptr.clear();
243 EXPECT_FALSE(isDeleted);
245 set.remove(rawPtr);
246 EXPECT_TRUE(isDeleted);
247 EXPECT_TRUE(set.isEmpty());
248 EXPECT_EQ(1, DummyRefCounted::s_refInvokesCount);
251 } // anonymous namespace
253 } // namespace WTF