1 /*
2 * Copyright (C) 2010 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 *
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 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 // Tests for the red-black tree class.
27
28 #include "config.h"
29
30 #include "PODRedBlackTree.h"
31
32 #include "ArenaTestHelpers.h"
33 #include "TreeTestHelpers.h"
34 #include <gtest/gtest.h>
35 #include <wtf/Vector.h>
36
37 namespace WebCore {
38
39 using ArenaTestHelpers::TrackedAllocator;
40 using TreeTestHelpers::generateSeed;
41 using TreeTestHelpers::initRandom;
42 using TreeTestHelpers::nextRandom;
43
TEST(PODRedBlackTreeTest,TestTreeAllocatesFromArena)44 TEST(PODRedBlackTreeTest, TestTreeAllocatesFromArena)
45 {
46 RefPtr<TrackedAllocator> allocator = TrackedAllocator::create();
47 {
48 RefPtr<PODArena> arena = PODArena::create(allocator);
49 PODRedBlackTree<int> tree(arena);
50 int numAdditions = 2 * PODArena::DefaultChunkSize / sizeof(int);
51 for (int i = 0; i < numAdditions; ++i)
52 tree.add(i);
53 EXPECT_GT(allocator->numRegions(), 1);
54 }
55 EXPECT_EQ(allocator->numRegions(), 0);
56 }
57
TEST(PODRedBlackTreeTest,TestSingleElementInsertion)58 TEST(PODRedBlackTreeTest, TestSingleElementInsertion)
59 {
60 PODRedBlackTree<int> tree;
61 tree.add(5);
62 ASSERT_TRUE(tree.checkInvariants());
63 EXPECT_TRUE(tree.contains(5));
64 }
65
TEST(PODRedBlackTreeTest,TestMultipleElementInsertion)66 TEST(PODRedBlackTreeTest, TestMultipleElementInsertion)
67 {
68 PODRedBlackTree<int> tree;
69 tree.add(4);
70 ASSERT_TRUE(tree.checkInvariants());
71 EXPECT_TRUE(tree.contains(4));
72 tree.add(3);
73 ASSERT_TRUE(tree.checkInvariants());
74 EXPECT_TRUE(tree.contains(3));
75 tree.add(5);
76 ASSERT_TRUE(tree.checkInvariants());
77 EXPECT_TRUE(tree.contains(5));
78 EXPECT_TRUE(tree.contains(4));
79 EXPECT_TRUE(tree.contains(3));
80 }
81
TEST(PODRedBlackTreeTest,TestDuplicateElementInsertion)82 TEST(PODRedBlackTreeTest, TestDuplicateElementInsertion)
83 {
84 PODRedBlackTree<int> tree;
85 tree.add(3);
86 ASSERT_TRUE(tree.checkInvariants());
87 tree.add(3);
88 ASSERT_TRUE(tree.checkInvariants());
89 tree.add(3);
90 ASSERT_TRUE(tree.checkInvariants());
91 EXPECT_EQ(3, tree.size());
92 EXPECT_TRUE(tree.contains(3));
93 }
94
TEST(PODRedBlackTreeTest,TestSingleElementInsertionAndDeletion)95 TEST(PODRedBlackTreeTest, TestSingleElementInsertionAndDeletion)
96 {
97 PODRedBlackTree<int> tree;
98 tree.add(5);
99 ASSERT_TRUE(tree.checkInvariants());
100 EXPECT_TRUE(tree.contains(5));
101 tree.remove(5);
102 ASSERT_TRUE(tree.checkInvariants());
103 EXPECT_FALSE(tree.contains(5));
104 }
105
TEST(PODRedBlackTreeTest,TestMultipleElementInsertionAndDeletion)106 TEST(PODRedBlackTreeTest, TestMultipleElementInsertionAndDeletion)
107 {
108 PODRedBlackTree<int> tree;
109 tree.add(4);
110 ASSERT_TRUE(tree.checkInvariants());
111 EXPECT_TRUE(tree.contains(4));
112 tree.add(3);
113 ASSERT_TRUE(tree.checkInvariants());
114 EXPECT_TRUE(tree.contains(3));
115 tree.add(5);
116 ASSERT_TRUE(tree.checkInvariants());
117 EXPECT_TRUE(tree.contains(5));
118 EXPECT_TRUE(tree.contains(4));
119 EXPECT_TRUE(tree.contains(3));
120 tree.remove(4);
121 ASSERT_TRUE(tree.checkInvariants());
122 EXPECT_TRUE(tree.contains(3));
123 EXPECT_FALSE(tree.contains(4));
124 EXPECT_TRUE(tree.contains(5));
125 tree.remove(5);
126 ASSERT_TRUE(tree.checkInvariants());
127 EXPECT_TRUE(tree.contains(3));
128 EXPECT_FALSE(tree.contains(4));
129 EXPECT_FALSE(tree.contains(5));
130 EXPECT_EQ(1, tree.size());
131 }
132
TEST(PODRedBlackTreeTest,TestDuplicateElementInsertionAndDeletion)133 TEST(PODRedBlackTreeTest, TestDuplicateElementInsertionAndDeletion)
134 {
135 PODRedBlackTree<int> tree;
136 tree.add(3);
137 ASSERT_TRUE(tree.checkInvariants());
138 tree.add(3);
139 ASSERT_TRUE(tree.checkInvariants());
140 tree.add(3);
141 ASSERT_TRUE(tree.checkInvariants());
142 EXPECT_EQ(3, tree.size());
143 EXPECT_TRUE(tree.contains(3));
144 tree.remove(3);
145 ASSERT_TRUE(tree.checkInvariants());
146 tree.remove(3);
147 ASSERT_TRUE(tree.checkInvariants());
148 EXPECT_EQ(1, tree.size());
149 EXPECT_TRUE(tree.contains(3));
150 tree.remove(3);
151 ASSERT_TRUE(tree.checkInvariants());
152 EXPECT_EQ(0, tree.size());
153 EXPECT_FALSE(tree.contains(3));
154 }
155
TEST(PODRedBlackTreeTest,FailingInsertionRegressionTest1)156 TEST(PODRedBlackTreeTest, FailingInsertionRegressionTest1)
157 {
158 // These numbers came from a previously-failing randomized test run.
159 PODRedBlackTree<int> tree;
160 tree.add(5113);
161 ASSERT_TRUE(tree.checkInvariants());
162 tree.add(4517);
163 ASSERT_TRUE(tree.checkInvariants());
164 tree.add(3373);
165 ASSERT_TRUE(tree.checkInvariants());
166 tree.add(9307);
167 ASSERT_TRUE(tree.checkInvariants());
168 tree.add(7077);
169 ASSERT_TRUE(tree.checkInvariants());
170 }
171
172 namespace {
InsertionAndDeletionTest(const int32_t seed,const int treeSize)173 void InsertionAndDeletionTest(const int32_t seed, const int treeSize)
174 {
175 initRandom(seed);
176 const int maximumValue = treeSize;
177 // Build the tree.
178 PODRedBlackTree<int> tree;
179 Vector<int> values;
180 for (int i = 0; i < treeSize; i++) {
181 int value = nextRandom(maximumValue);
182 tree.add(value);
183 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
184 values.append(value);
185 }
186 // Churn the tree's contents.
187 for (int i = 0; i < treeSize; i++) {
188 // Pick a random value to remove.
189 int index = nextRandom(treeSize);
190 int value = values[index];
191 // Remove this value.
192 tree.remove(value);
193 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
194 // Replace it with a new one.
195 value = nextRandom(maximumValue);
196 values[index] = value;
197 tree.add(value);
198 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
199 }
200 }
201 } // anonymous namespace
202
TEST(PODRedBlackTreeTest,RandomDeletionAndInsertionRegressionTest1)203 TEST(PODRedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1)
204 {
205 InsertionAndDeletionTest(12311, 100);
206 }
207
TEST(PODRedBlackTreeTest,TestRandomDeletionAndInsertion)208 TEST(PODRedBlackTreeTest, TestRandomDeletionAndInsertion)
209 {
210 InsertionAndDeletionTest(generateSeed(), 100);
211 }
212
213 } // namespace WebCore
214