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 37 namespace blink { 38 39 using ArenaTestHelpers::TrackedAllocator; 40 using TreeTestHelpers::initRandom; 41 using TreeTestHelpers::nextRandom; 42 43 TEST(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 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 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 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 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 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 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 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 { 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 203 TEST(PODRedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1) 204 { 205 InsertionAndDeletionTest(12311, 100); 206 } 207 208 } // namespace blink 209
