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#include "platform/PODRedBlackTree.h"
30
31#include "platform/testing/ArenaTestHelpers.h"
32#include "platform/testing/TreeTestHelpers.h"
33#include "wtf/Vector.h"
34
35#include <gtest/gtest.h>
36
37namespace blink {
38
39using ArenaTestHelpers::TrackedAllocator;
40using TreeTestHelpers::initRandom;
41using TreeTestHelpers::nextRandom;
42
43TEST(PODRedBlackTreeTest, TestTreeAllocatesFromArena)
44{
45    RefPtr<TrackedAllocator> allocator = TrackedAllocator::create();
46    {
47        typedef PODFreeListArena<PODRedBlackTree<int>::Node> PODIntegerArena;
48        RefPtr<PODIntegerArena> arena = PODIntegerArena::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
58TEST(PODRedBlackTreeTest, TestSingleElementInsertion)
59{
60    PODRedBlackTree<int> tree;
61    tree.add(5);
62    ASSERT_TRUE(tree.checkInvariants());
63    EXPECT_TRUE(tree.contains(5));
64}
65
66TEST(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
82TEST(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
95TEST(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
106TEST(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
133TEST(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
156TEST(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
172namespace {
173void 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
203TEST(PODRedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1)
204{
205    InsertionAndDeletionTest(12311, 100);
206}
207
208} // namespace blink
209