13d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick/* 23d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * Copyright (C) 2010 Google Inc. All rights reserved. 33d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * 43d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * Redistribution and use in source and binary forms, with or without 53d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * modification, are permitted provided that the following conditions 63d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * are met: 73d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * 83d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * 1. Redistributions of source code must retain the above copyright 93d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * notice, this list of conditions and the following disclaimer. 103d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * 2. Redistributions in binary form must reproduce the above copyright 113d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * notice, this list of conditions and the following disclaimer in the 123d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * documentation and/or other materials provided with the distribution. 133d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * 143d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 153d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 163d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 173d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 183d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 193d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 203d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 213d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 223d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 233d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 243d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick */ 253d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 263d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick// Tests for the red-black tree class. 273d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 283d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick#include "config.h" 293d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick#include "platform/PODRedBlackTree.h" 303d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 313d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick#include "platform/testing/ArenaTestHelpers.h" 323d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick#include "platform/testing/TreeTestHelpers.h" 333d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick#include "wtf/Vector.h" 343d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 353d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick#include <gtest/gtest.h> 363d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 373d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanicknamespace blink { 383d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 393d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanickusing ArenaTestHelpers::TrackedAllocator; 403d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanickusing TreeTestHelpers::initRandom; 413d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanickusing TreeTestHelpers::nextRandom; 423d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 433d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestTreeAllocatesFromArena) 443d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 453d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); 463d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick { 473d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick typedef PODFreeListArena<PODRedBlackTree<int>::Node> PODIntegerArena; 483d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick RefPtr<PODIntegerArena> arena = PODIntegerArena::create(allocator); 493d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree(arena); 503d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick int numAdditions = 2 * PODArena::DefaultChunkSize / sizeof(int); 513d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick for (int i = 0; i < numAdditions; ++i) 523d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(i); 533d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_GT(allocator->numRegions(), 1); 543d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick } 553d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_EQ(allocator->numRegions(), 0); 563d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 573d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 583d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestSingleElementInsertion) 593d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 603d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 613d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(5); 623d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 633d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(5)); 643d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 653d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 663d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestMultipleElementInsertion) 673d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 683d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 693d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(4); 703d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 713d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(4)); 723d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 733d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 743d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 753d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(5); 763d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 773d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(5)); 783d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(4)); 793d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 803d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 813d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 823d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestDuplicateElementInsertion) 833d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 843d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 853d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 863d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 873d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 883d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 893d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 903d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 913d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_EQ(3, tree.size()); 923d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 933d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 943d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 953d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestSingleElementInsertionAndDeletion) 963d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 973d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 983d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(5); 993d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1003d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(5)); 1013d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(5); 1023d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1033d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_FALSE(tree.contains(5)); 1043d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 1053d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 1063d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestMultipleElementInsertionAndDeletion) 1073d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 1083d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 1093d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(4); 1103d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1113d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(4)); 1123d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 1133d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1143d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 1153d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(5); 1163d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1173d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(5)); 1183d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(4)); 1193d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 1203d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(4); 1213d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1223d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 1233d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_FALSE(tree.contains(4)); 1243d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(5)); 1253d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(5); 1263d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1273d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 1283d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_FALSE(tree.contains(4)); 1293d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_FALSE(tree.contains(5)); 1303d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_EQ(1, tree.size()); 1313d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 1323d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 1333d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, TestDuplicateElementInsertionAndDeletion) 1343d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 1353d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 1363d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 1373d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1383d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 1393d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1403d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3); 1413d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1423d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_EQ(3, tree.size()); 1433d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 1443d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(3); 1453d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1463d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(3); 1473d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1483d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_EQ(1, tree.size()); 1493d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_TRUE(tree.contains(3)); 1503d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(3); 1513d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1523d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_EQ(0, tree.size()); 1533d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick EXPECT_FALSE(tree.contains(3)); 1543d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 1553d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 1563d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, FailingInsertionRegressionTest1) 1573d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 1583d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick // These numbers came from a previously-failing randomized test run. 1593d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 1603d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(5113); 1613d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1623d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(4517); 1633d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1643d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(3373); 1653d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1663d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(9307); 1673d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1683d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(7077); 1693d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()); 1703d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 1713d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 1723d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanicknamespace { 1733d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanickvoid InsertionAndDeletionTest(const int32_t seed, const int treeSize) 1743d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 1753d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick initRandom(seed); 1763d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick const int maximumValue = treeSize; 1773d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick // Build the tree. 1783d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick PODRedBlackTree<int> tree; 1793d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick Vector<int> values; 1803d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick for (int i = 0; i < treeSize; i++) { 1813d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick int value = nextRandom(maximumValue); 1823d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(value); 1833d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 1843d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick values.append(value); 1853d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick } 1863d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick // Churn the tree's contents. 1873d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick for (int i = 0; i < treeSize; i++) { 1883d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick // Pick a random value to remove. 1893d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick int index = nextRandom(treeSize); 1903d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick int value = values[index]; 1913d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick // Remove this value. 1923d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.remove(value); 1933d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 1943d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick // Replace it with a new one. 1953d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick value = nextRandom(maximumValue); 1963d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick values[index] = value; 1973d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick tree.add(value); 1983d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 1993d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick } 2003d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 2013d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} // anonymous namespace 2023d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 2033d000e7dd14c3185b9e27a6c38a67288b4d10431Ian RomanickTEST(PODRedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1) 2043d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick{ 2053d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick InsertionAndDeletionTest(12311, 100); 2063d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} 2073d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick 2083d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick} // namespace blink 2093d000e7dd14c3185b9e27a6c38a67288b4d10431Ian Romanick