15abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick/* 25abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * Copyright (C) 2010 Google Inc. All rights reserved. 35abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 45abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * Redistribution and use in source and binary forms, with or without 55abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * modification, are permitted provided that the following conditions 65abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * are met: 75abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 85abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 1. Redistributions of source code must retain the above copyright 95abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * notice, this list of conditions and the following disclaimer. 105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 2. Redistributions in binary form must reproduce the above copyright 115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * notice, this list of conditions and the following disclaimer in the 125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * documentation and/or other materials provided with the distribution. 135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick */ 255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Tests for the red-black tree class. 275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "config.h" 295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "PODRedBlackTree.h" 315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "ArenaTestHelpers.h" 335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "TreeTestHelpers.h" 345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include <gtest/gtest.h> 355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include <wtf/Vector.h> 365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merricknamespace WebCore { 385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickusing ArenaTestHelpers::TrackedAllocator; 405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickusing TreeTestHelpers::generateSeed; 415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickusing TreeTestHelpers::initRandom; 425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickusing TreeTestHelpers::nextRandom; 435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestTreeAllocatesFromArena) 455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); 475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick RefPtr<PODArena> arena = PODArena::create(allocator); 495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree(arena); 505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int numAdditions = 2 * PODArena::DefaultChunkSize / sizeof(int); 515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick for (int i = 0; i < numAdditions; ++i) 525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(i); 535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_GT(allocator->numRegions(), 1); 545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_EQ(allocator->numRegions(), 0); 565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestSingleElementInsertion) 595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(5); 625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(5)); 645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestMultipleElementInsertion) 675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(4); 705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(4)); 725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(5); 765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(5)); 785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(4)); 795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestDuplicateElementInsertion) 835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_EQ(3, tree.size()); 925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestSingleElementInsertionAndDeletion) 965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(5); 995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(5)); 1015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(5); 1025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_FALSE(tree.contains(5)); 1045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 1055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestMultipleElementInsertionAndDeletion) 1075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 1085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 1095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(4); 1105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(4)); 1125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 1135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 1155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(5); 1165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(5)); 1185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(4)); 1195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 1205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(4); 1215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 1235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_FALSE(tree.contains(4)); 1245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(5)); 1255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(5); 1265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 1285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_FALSE(tree.contains(4)); 1295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_FALSE(tree.contains(5)); 1305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_EQ(1, tree.size()); 1315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 1325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestDuplicateElementInsertionAndDeletion) 1345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 1355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 1365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 1375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 1395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3); 1415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_EQ(3, tree.size()); 1435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 1445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(3); 1455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(3); 1475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_EQ(1, tree.size()); 1495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_TRUE(tree.contains(3)); 1505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(3); 1515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_EQ(0, tree.size()); 1535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick EXPECT_FALSE(tree.contains(3)); 1545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 1555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, FailingInsertionRegressionTest1) 1575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 1585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // These numbers came from a previously-failing randomized test run. 1595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 1605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(5113); 1615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(4517); 1635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(3373); 1655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(9307); 1675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(7077); 1695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()); 1705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 1715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merricknamespace { 1735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickvoid InsertionAndDeletionTest(const int32_t seed, const int treeSize) 1745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 1755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick initRandom(seed); 1765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick const int maximumValue = treeSize; 1775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Build the tree. 1785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree<int> tree; 1795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Vector<int> values; 1805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick for (int i = 0; i < treeSize; i++) { 1815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int value = nextRandom(maximumValue); 1825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(value); 1835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 1845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick values.append(value); 1855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Churn the tree's contents. 1875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick for (int i = 0; i < treeSize; i++) { 1885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Pick a random value to remove. 1895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int index = nextRandom(treeSize); 1905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int value = values[index]; 1915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Remove this value. 1925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.remove(value); 1935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 1945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Replace it with a new one. 1955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick value = nextRandom(maximumValue); 1965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick values[index] = value; 1975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick tree.add(value); 1985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 1995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 2005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 2015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} // anonymous namespace 2025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1) 2045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 2055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick InsertionAndDeletionTest(12311, 100); 2065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 2075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickTEST(PODRedBlackTreeTest, TestRandomDeletionAndInsertion) 2095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 2105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick InsertionAndDeletionTest(generateSeed(), 100); 2115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 2125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} // namespace WebCore 214