third_party/WebKit/Source/platform/PODRedBlackTreeTest.cpp

   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