1/*
2 * Copyright (C) 2011 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 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of Apple Inc. ("Apple") nor the names of
14 * its contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include "config.h"
30#include <wtf/RedBlackTree.h>
31#include <wtf/Vector.h>
32
33namespace TestWebKitAPI {
34
35using namespace WTF;
36
37class TestNode : public RedBlackTree<TestNode, char>::Node {
38public:
39 TestNode(char key, unsigned value)
40 : m_key(key)
41 , m_value(value)
42 {
43 }
44
45 char key()
46 {
47 return m_key;
48 }
49
50 char m_key;
51 unsigned m_value;
52};
53
54class RedBlackTreeTest : public testing::Test {
55public:
56 unsigned m_counter;
57
58 virtual void SetUp()
59 {
60 m_counter = 0;
61 }
62
63 virtual void TearDown()
64 {
65 }
66
67 struct Pair {
68 char key;
69 unsigned value;
70
71 Pair() { }
72
73 Pair(char key, unsigned value)
74 : key(key)
75 , value(value)
76 {
77 }
78
79 bool operator==(const Pair& other) const
80 {
81 return key == other.key;
82 }
83
84 bool operator<(const Pair& other) const
85 {
86 return key < other.key;
87 }
88 };
89
90 typedef Vector<Pair, 16> PairVector;
91
92 PairVector findExact(PairVector& asVector, char key)
93 {
94 PairVector result;
95
96 for (size_t index = 0; index < asVector.size(); ++index) {
97 if (asVector.at(index).key == key)
98 result.append(asVector.at(index));
99 }
100
101 std::sort(result.begin(), result.end());
102
103 return result;
104 }
105
106 void remove(PairVector& asVector, size_t index)
107 {
108 asVector.at(index) = asVector.last();
109 asVector.removeLast();
110 }
111
112 PairVector findLeastGreaterThanOrEqual(PairVector& asVector, char key)
113 {
114 char bestKey = 0; // assignment to make gcc happy
115 bool foundKey = false;
116
117 for (size_t index = 0; index < asVector.size(); ++index) {
118 if (asVector.at(index).key >= key) {
119 if (asVector.at(index).key < bestKey || !foundKey) {
120 foundKey = true;
121 bestKey = asVector.at(index).key;
122 }
123 }
124 }
125
126 PairVector result;
127
128 if (!foundKey)
129 return result;
130
131 return findExact(asVector, bestKey);
132 }
133
134 void assertFoundAndRemove(PairVector& asVector, char key, unsigned value)
135 {
136 bool found = false;
137 size_t foundIndex = 0; // make compilers happy
138
139 for (size_t index = 0; index < asVector.size(); ++index) {
140 if (asVector.at(index).key == key
141 && asVector.at(index).value == value) {
142 EXPECT_TRUE(!found);
143
144 found = true;
145 foundIndex = index;
146 }
147 }
148
149 EXPECT_TRUE(found);
150
151 remove(asVector, foundIndex);
152 }
153
154 // This deliberately passes a copy of the vector.
155 void assertEqual(RedBlackTree<TestNode, char>& asTree, PairVector asVector)
156 {
157 for (TestNode* current = asTree.first(); current; current = current->successor())
158 assertFoundAndRemove(asVector, current->m_key, current->m_value);
159 }
160
161 void assertSameValuesForKey(RedBlackTree<TestNode, char>& asTree, TestNode* node, PairVector foundValues, char key)
162 {
163 if (node) {
164 EXPECT_EQ(node->m_key, key);
165
166 TestNode* prevNode = node;
167 do {
168 node = prevNode;
169 prevNode = prevNode->predecessor();
170 } while (prevNode && prevNode->m_key == key);
171
172 EXPECT_EQ(node->m_key, key);
173 EXPECT_TRUE(!prevNode || prevNode->m_key < key);
174
175 do {
176 assertFoundAndRemove(foundValues, node->m_key, node->m_value);
177
178 node = node->successor();
179 EXPECT_TRUE(!node || node->m_key >= key);
180 } while (node && node->m_key == key);
181 }
182
183 EXPECT_TRUE(foundValues.isEmpty());
184 }
185
186 // The control string is a null-terminated list of commands. Each
187 // command is two characters, with the first identifying the operation
188 // and the second giving a key. The commands are:
189 // +x Add x
190 // *x Find all elements equal to x
191 // @x Find all elements that have the smallest key that is greater than or equal to x
192 // !x Remove all elements equal to x
193 void testDriver(const char* controlString)
194 {
195 PairVector asVector;
196 RedBlackTree<TestNode, char> asTree;
197
198 for (const char* current = controlString; *current; current += 2) {
199 char command = current[0];
200 char key = current[1];
201 unsigned value = ++m_counter;
202
203 ASSERT(command);
204 ASSERT(key);
205
206 switch (command) {
207 case '+': {
208 TestNode* node = new TestNode(key, value);
209 asTree.insert(node);
210 asVector.append(Pair(key, value));
211 break;
212 }
213
214 case '*': {
215 TestNode* node = asTree.findExact(key);
216 if (node)
217 EXPECT_EQ(node->m_key, key);
218 assertSameValuesForKey(asTree, node, findExact(asVector, key), key);
219 break;
220 }
221
222 case '@': {
223 TestNode* node = asTree.findLeastGreaterThanOrEqual(key);
224 if (node) {
225 EXPECT_TRUE(node->m_key >= key);
226 assertSameValuesForKey(asTree, node, findLeastGreaterThanOrEqual(asVector, key), node->m_key);
227 } else
228 EXPECT_TRUE(findLeastGreaterThanOrEqual(asVector, key).isEmpty());
229 break;
230 }
231
232 case '!': {
233 while (true) {
234 TestNode* node = asTree.remove(key);
235 if (node) {
236 EXPECT_EQ(node->m_key, key);
237 assertFoundAndRemove(asVector, node->m_key, node->m_value);
238 } else {
239 EXPECT_TRUE(findExact(asVector, key).isEmpty());
240 break;
241 }
242 }
243 break;
244 }
245
246 default:
247 ASSERT_NOT_REACHED();
248 break;
249 }
250
251 EXPECT_EQ(asTree.size(), asVector.size());
252 assertEqual(asTree, asVector);
253 }
254 }
255};
256
257TEST_F(RedBlackTreeTest, Empty)
258{
259 testDriver("");
260}
261
262TEST_F(RedBlackTreeTest, EmptyGetFindRemove)
263{
264 testDriver("*x@y!z");
265}
266
267TEST_F(RedBlackTreeTest, SingleAdd)
268{
269 testDriver("+a");
270}
271
272TEST_F(RedBlackTreeTest, SingleAddGetFindRemoveNotFound)
273{
274 testDriver("+a*x@y!z");
275}
276
277TEST_F(RedBlackTreeTest, SingleAddGetFindRemove)
278{
279 testDriver("+a*a@a!a");
280}
281
282TEST_F(RedBlackTreeTest, TwoAdds)
283{
284 testDriver("+a+b");
285}
286
287TEST_F(RedBlackTreeTest, ThreeAdds)
288{
289 testDriver("+a+b+c");
290}
291
292TEST_F(RedBlackTreeTest, FourAdds)
293{
294 testDriver("+a+b+c+d");
295}
296
297TEST_F(RedBlackTreeTest, LotsOfRepeatAdds)
298{
299 testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d");
300}
301
302TEST_F(RedBlackTreeTest, LotsOfRepeatAndUniqueAdds)
303{
304 testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z");
305}
306
307TEST_F(RedBlackTreeTest, LotsOfRepeatAndUniqueAddsAndGetsAndRemoves)
308{
309 testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z");
310}
311
312TEST_F(RedBlackTreeTest, SimpleBestFitSearch)
313{
314 testDriver("+d+d+m+w@d@m@w@a@g@q");
315}
316
317TEST_F(RedBlackTreeTest, BiggerBestFitSearch)
318{
319 testDriver("+d+d+d+d+d+d+d+d+d+d+f+f+f+f+f+f+f+h+h+i+j+k+l+m+o+p+q+r+z@a@b@c@d@e@f@g@h@i@j@k@l@m@n@o@p@q@r@s@t@u@v@w@x@y@z");
320}
321
322} // namespace TestWebKitAPI
323