1287b74fc676a3c8101c17b2b94b01f67cbe1f17
[WebKit-https.git] / Tools / TestWebKitAPI / Tests / WTF / HashSet.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 "MoveOnly.h"
29 #include <wtf/HashSet.h>
30
31
32 namespace TestWebKitAPI {
33
34 template<int initialCapacity>
35     struct InitialCapacityTestHashTraits : public WTF::UnsignedWithZeroKeyHashTraits<int> {
36     static const int minimumTableSize = initialCapacity;
37 };
38
39 template<unsigned size>
40 void testInitialCapacity()
41 {
42     const unsigned initialCapacity = WTF::HashTableCapacityForSize<size>::value;
43     HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity> > testSet;
44
45     // Initial capacity is null.
46     ASSERT_EQ(0, testSet.capacity());
47
48     // Adding items up to size should never change the capacity.
49     for (size_t i = 0; i < size; ++i) {
50         testSet.add(i);
51         ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
52     }
53
54     // Adding items up to less than half the capacity should not change the capacity.
55     unsigned capacityLimit = initialCapacity / 2 - 1;
56     for (size_t i = size; i < capacityLimit; ++i) {
57         testSet.add(i);
58         ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
59     }
60
61     // Adding one more item increase the capacity.
62     testSet.add(initialCapacity);
63     EXPECT_GT(static_cast<unsigned>(testSet.capacity()), initialCapacity);
64 }
65
66 template<unsigned size> void generateTestCapacityUpToSize();
67 template<> void generateTestCapacityUpToSize<0>()
68 {
69 }
70 template<unsigned size> void generateTestCapacityUpToSize()
71 {
72     generateTestCapacityUpToSize<size - 1>();
73     testInitialCapacity<size>();
74 }
75
76 TEST(WTF_HashSet, InitialCapacity)
77 {
78     generateTestCapacityUpToSize<128>();
79 }
80
81 TEST(WTF_HashSet, MoveOnly)
82 {
83     HashSet<MoveOnly> hashSet;
84
85     for (size_t i = 0; i < 100; ++i) {
86         MoveOnly moveOnly(i + 1);
87         hashSet.add(WTF::move(moveOnly));
88     }
89
90     for (size_t i = 0; i < 100; ++i)
91         EXPECT_TRUE(hashSet.contains(MoveOnly(i + 1)));
92
93     for (size_t i = 0; i < 100; ++i)
94         EXPECT_TRUE(hashSet.remove(MoveOnly(i + 1)));
95
96     EXPECT_TRUE(hashSet.isEmpty());
97
98     for (size_t i = 0; i < 100; ++i)
99         hashSet.add(MoveOnly(i + 1));
100
101     for (size_t i = 0; i < 100; ++i)
102         EXPECT_TRUE(hashSet.take(MoveOnly(i + 1)) == MoveOnly(i + 1));
103
104     EXPECT_TRUE(hashSet.isEmpty());
105
106     for (size_t i = 0; i < 100; ++i)
107         hashSet.add(MoveOnly(i + 1));
108
109     HashSet<MoveOnly> secondSet;
110
111     for (size_t i = 0; i < 100; ++i)
112         secondSet.add(hashSet.takeAny());
113
114     EXPECT_TRUE(hashSet.isEmpty());
115
116     for (size_t i = 0; i < 100; ++i)
117         EXPECT_TRUE(secondSet.contains(MoveOnly(i + 1)));
118 }
119
120 } // namespace TestWebKitAPI