diff options
Diffstat (limited to 'WebKit/chromium/tests')
| -rw-r--r-- | WebKit/chromium/tests/ArenaTestHelpers.h | 78 | ||||
| -rw-r--r-- | WebKit/chromium/tests/PODArenaTest.cpp | 106 | ||||
| -rw-r--r-- | WebKit/chromium/tests/PODIntervalTreeTest.cpp | 323 | ||||
| -rw-r--r-- | WebKit/chromium/tests/PODRedBlackTreeTest.cpp | 213 | ||||
| -rw-r--r-- | WebKit/chromium/tests/TreeTestHelpers.cpp | 60 | ||||
| -rw-r--r-- | WebKit/chromium/tests/TreeTestHelpers.h | 53 |
6 files changed, 833 insertions, 0 deletions
diff --git a/WebKit/chromium/tests/ArenaTestHelpers.h b/WebKit/chromium/tests/ArenaTestHelpers.h new file mode 100644 index 0000000..87f827d --- /dev/null +++ b/WebKit/chromium/tests/ArenaTestHelpers.h @@ -0,0 +1,78 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef ArenaTestHelpers_h +#define ArenaTestHelpers_h + +#include "PODArena.h" +#include <gtest/gtest.h> +#include <wtf/Vector.h> + +namespace WebCore { +namespace ArenaTestHelpers { + +// An allocator for the PODArena which tracks the regions which have +// been allocated. +class TrackedAllocator : public PODArena::FastMallocAllocator { +public: + static PassRefPtr<TrackedAllocator> create() + { + return adoptRef(new TrackedAllocator); + } + + virtual void* allocate(size_t size) + { + void* result = PODArena::FastMallocAllocator::allocate(size); + m_allocatedRegions.append(result); + return result; + } + + virtual void free(void* ptr) + { + size_t slot = m_allocatedRegions.find(ptr); + ASSERT_GE(slot, 0); + m_allocatedRegions.remove(slot); + PODArena::FastMallocAllocator::free(ptr); + } + + bool isEmpty() const + { + return !numRegions(); + } + + int numRegions() const + { + return m_allocatedRegions.size(); + } + +private: + TrackedAllocator() { } + Vector<void*> m_allocatedRegions; +}; + +} // namespace ArenaTestHelpers +} // namespace WebCore + +#endif // ArenaTestHelpers_h diff --git a/WebKit/chromium/tests/PODArenaTest.cpp b/WebKit/chromium/tests/PODArenaTest.cpp new file mode 100644 index 0000000..c5b1ede --- /dev/null +++ b/WebKit/chromium/tests/PODArenaTest.cpp @@ -0,0 +1,106 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#include "PODArena.h" + +#include "ArenaTestHelpers.h" +#include <algorithm> +#include <gtest/gtest.h> +#include <wtf/FastMalloc.h> +#include <wtf/RefPtr.h> +#include <wtf/Vector.h> + +namespace WebCore { + +using ArenaTestHelpers::TrackedAllocator; + +namespace { + +// A couple of simple structs to allocate. +struct TestClass1 { + TestClass1() + : x(0), y(0), z(0), w(1) { } + + float x, y, z, w; +}; + +struct TestClass2 { + TestClass2() + : a(1), b(2), c(3), d(4) { } + + float a, b, c, d; +}; + +} // anonymous namespace + +class PODArenaTest : public testing::Test { +}; + +// Make sure the arena can successfully allocate from more than one +// region. +TEST_F(PODArenaTest, CanAllocateFromMoreThanOneRegion) +{ + RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); + RefPtr<PODArena> arena = PODArena::create(allocator); + int numIterations = 10 * PODArena::DefaultChunkSize / sizeof(TestClass1); + for (int i = 0; i < numIterations; ++i) + arena->allocateObject<TestClass1>(); + EXPECT_GT(allocator->numRegions(), 1); +} + +// Make sure the arena frees all allocated regions during destruction. +TEST_F(PODArenaTest, FreesAllAllocatedRegions) +{ + RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); + { + RefPtr<PODArena> arena = PODArena::create(allocator); + for (int i = 0; i < 3; i++) + arena->allocateObject<TestClass1>(); + EXPECT_GT(allocator->numRegions(), 0); + } + EXPECT_TRUE(allocator->isEmpty()); +} + +// Make sure the arena runs constructors of the objects allocated within. +TEST_F(PODArenaTest, RunsConstructors) +{ + RefPtr<PODArena> arena = PODArena::create(); + for (int i = 0; i < 10000; i++) { + TestClass1* tc1 = arena->allocateObject<TestClass1>(); + EXPECT_EQ(0, tc1->x); + EXPECT_EQ(0, tc1->y); + EXPECT_EQ(0, tc1->z); + EXPECT_EQ(1, tc1->w); + TestClass2* tc2 = arena->allocateObject<TestClass2>(); + EXPECT_EQ(1, tc2->a); + EXPECT_EQ(2, tc2->b); + EXPECT_EQ(3, tc2->c); + EXPECT_EQ(4, tc2->d); + } +} + +} // namespace WebCore diff --git a/WebKit/chromium/tests/PODIntervalTreeTest.cpp b/WebKit/chromium/tests/PODIntervalTreeTest.cpp new file mode 100644 index 0000000..3a8a245 --- /dev/null +++ b/WebKit/chromium/tests/PODIntervalTreeTest.cpp @@ -0,0 +1,323 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// Tests for the interval tree class. + +#include "config.h" + +#include "PODIntervalTree.h" + +#include "Logging.h" +#include "TreeTestHelpers.h" +#include <gtest/gtest.h> +#include <wtf/Vector.h> +#include <wtf/text/WTFString.h> + +namespace WebCore { + +using TreeTestHelpers::generateSeed; +using TreeTestHelpers::initRandom; +using TreeTestHelpers::nextRandom; + +inline String valueToString(const float& value) +{ + return String::number(value); +} + +inline String valueToString(void* const& value) +{ + return String::format("0x%p", value); +} + +TEST(PODIntervalTreeTest, TestInsertion) +{ + PODIntervalTree<float> tree; + tree.add(PODInterval<float>(2, 4)); + ASSERT_TRUE(tree.checkInvariants()); +} + +TEST(PODIntervalTreeTest, TestInsertionAndQuery) +{ + PODIntervalTree<float> tree; + tree.add(PODInterval<float>(2, 4)); + ASSERT_TRUE(tree.checkInvariants()); + Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(1, 3)); + EXPECT_EQ(1U, result.size()); + EXPECT_EQ(2, result[0].low()); + EXPECT_EQ(4, result[0].high()); +} + +TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval) +{ + PODIntervalTree<float> tree; + tree.add(PODInterval<float>(1, 2.5)); + tree.add(PODInterval<float>(3.5, 5)); + tree.add(PODInterval<float>(2, 4)); + ASSERT_TRUE(tree.checkInvariants()); + Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(3, 3)); + EXPECT_EQ(1U, result.size()); + EXPECT_EQ(2, result[0].low()); + EXPECT_EQ(4, result[0].high()); +} + +TEST(PODIntervalTreeTest, TestDuplicateElementInsertion) +{ + PODIntervalTree<float, int*> tree; + int tmp1 = 1; + int tmp2 = 2; + typedef PODIntervalTree<float, int*>::IntervalType IntervalType; + IntervalType interval1(1, 3, &tmp1); + IntervalType interval2(1, 3, &tmp2); + tree.add(interval1); + tree.add(interval2); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(interval1)); + EXPECT_TRUE(tree.contains(interval2)); + EXPECT_TRUE(tree.remove(interval1)); + EXPECT_TRUE(tree.contains(interval2)); + EXPECT_FALSE(tree.contains(interval1)); + EXPECT_TRUE(tree.remove(interval2)); + EXPECT_EQ(0, tree.size()); +} + +namespace { + +struct UserData1 { +public: + UserData1() + : a(0), b(1) { } + + float a; + int b; +}; + +inline String valueToString(const UserData1& value) +{ + return String("[UserData1 a=") + String::number(value.a) + " b=" + String::number(value.b) + "]"; +} + +} // anonymous namespace + +TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData) +{ + PODIntervalTree<float, UserData1> tree; + UserData1 data1; + data1.a = 5; + data1.b = 6; + tree.add(tree.createInterval(2, 4, data1)); + ASSERT_TRUE(tree.checkInvariants()); +} + +TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData) +{ + PODIntervalTree<float, UserData1> tree; + UserData1 data1; + data1.a = 5; + data1.b = 6; + tree.add(tree.createInterval(2, 4, data1)); + ASSERT_TRUE(tree.checkInvariants()); + Vector<PODInterval<float, UserData1> > overlaps = tree.allOverlaps(tree.createInterval(3, 5, data1)); + EXPECT_EQ(1U, overlaps.size()); + EXPECT_EQ(5, overlaps[0].data().a); + EXPECT_EQ(6, overlaps[0].data().b); +} + +namespace { + +class EndpointType1 { +public: + explicit EndpointType1(int value) + : m_value(value) { } + + int value() const { return m_value; } + + bool operator<(const EndpointType1& other) const { return m_value < other.m_value; } + bool operator==(const EndpointType1& other) const { return m_value == other.m_value; } + +private: + int m_value; + // These operators should not be called by the interval tree. + bool operator>(const EndpointType1& other); + bool operator<=(const EndpointType1& other); + bool operator>=(const EndpointType1& other); + bool operator!=(const EndpointType1& other); +}; + +inline String valueToString(const EndpointType1& value) +{ + return String("[EndpointType1 value=") + String::number(value.value()) + "]"; +} + +} // anonymous namespace + +TEST(PODIntervalTreeTest, TestTreeDoesNotRequireMostOperators) +{ + PODIntervalTree<EndpointType1> tree; + tree.add(tree.createInterval(EndpointType1(1), EndpointType1(2))); + ASSERT_TRUE(tree.checkInvariants()); +} + +// Uncomment to debug a failure of the insertion and deletion test. +// #define DEBUG_INSERTION_AND_DELETION_TEST + +namespace { + +void InsertionAndDeletionTest(int32_t seed, int treeSize) +{ + initRandom(seed); + int maximumValue = treeSize; + // Build the tree + PODIntervalTree<int> tree; + Vector<PODInterval<int> > addedElements; + Vector<PODInterval<int> > removedElements; + for (int i = 0; i < treeSize; i++) { + int left = nextRandom(maximumValue); + int length = nextRandom(maximumValue); + PODInterval<int> interval(left, left + length); + tree.add(interval); +#ifdef DEBUG_INSERTION_AND_DELETION_TEST + LOG_ERROR("*** Adding element %s", valueToString(interval).ascii().data()); +#endif + addedElements.append(interval); + } + // Churn the tree's contents. + // First remove half of the elements in random order. + for (int i = 0; i < treeSize / 2; i++) { + int index = nextRandom(addedElements.size()); +#ifdef DEBUG_INSERTION_AND_DELETION_TEST + LOG_ERROR("*** Removing element %s", valueToString(addedElements[index]).ascii().data()); +#endif + ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed; + tree.remove(addedElements[index]); + removedElements.append(addedElements[index]); + addedElements.remove(index); + ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; + } + // Now randomly add or remove elements. + for (int i = 0; i < 2 * treeSize; i++) { + bool add = false; + if (!addedElements.size()) + add = true; + else if (!removedElements.size()) + add = false; + else + add = (nextRandom(2) == 1); + if (add) { + int index = nextRandom(removedElements.size()); +#ifdef DEBUG_INSERTION_AND_DELETION_TEST + LOG_ERROR("*** Adding element %s", valueToString(removedElements[index]).ascii().data()); +#endif + tree.add(removedElements[index]); + addedElements.append(removedElements[index]); + removedElements.remove(index); + } else { + int index = nextRandom(addedElements.size()); +#ifdef DEBUG_INSERTION_AND_DELETION_TEST + LOG_ERROR("*** Removing element %s", valueToString(addedElements[index]).ascii().data()); +#endif + ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed; + ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " << seed; + removedElements.append(addedElements[index]); + addedElements.remove(index); + } + ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; + } +} + +} // anonymous namespace + +TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1) +{ + InsertionAndDeletionTest(13972, 100); +} + +TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2) +{ + InsertionAndDeletionTest(1283382113, 10); +} + +TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest3) +{ + // This is the sequence of insertions and deletions that triggered + // the failure in RandomDeletionAndInsertionRegressionTest2. + PODIntervalTree<int> tree; + tree.add(tree.createInterval(0, 5)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(4, 5)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(8, 9)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(1, 4)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(3, 5)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(4, 12)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(0, 2)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(0, 2)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(9, 13)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(0, 1)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(0, 2)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(9, 13)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(0, 2)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(0, 1)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(4, 5)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(4, 12)); + ASSERT_TRUE(tree.checkInvariants()); +} + +TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest4) +{ + // Even further reduced test case for RandomDeletionAndInsertionRegressionTest3. + PODIntervalTree<int> tree; + tree.add(tree.createInterval(0, 5)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(8, 9)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(1, 4)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(3, 5)); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(tree.createInterval(4, 12)); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(tree.createInterval(4, 12)); + ASSERT_TRUE(tree.checkInvariants()); +} + +TEST(PODIntervalTreeTest, TestRandomDeletionAndInsertion) +{ + InsertionAndDeletionTest(generateSeed(), 1000); +} + +} // namespace WebCore diff --git a/WebKit/chromium/tests/PODRedBlackTreeTest.cpp b/WebKit/chromium/tests/PODRedBlackTreeTest.cpp new file mode 100644 index 0000000..0cc10e7 --- /dev/null +++ b/WebKit/chromium/tests/PODRedBlackTreeTest.cpp @@ -0,0 +1,213 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// Tests for the red-black tree class. + +#include "config.h" + +#include "PODRedBlackTree.h" + +#include "ArenaTestHelpers.h" +#include "TreeTestHelpers.h" +#include <gtest/gtest.h> +#include <wtf/Vector.h> + +namespace WebCore { + +using ArenaTestHelpers::TrackedAllocator; +using TreeTestHelpers::generateSeed; +using TreeTestHelpers::initRandom; +using TreeTestHelpers::nextRandom; + +TEST(PODRedBlackTreeTest, TestTreeAllocatesFromArena) +{ + RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); + { + RefPtr<PODArena> arena = PODArena::create(allocator); + PODRedBlackTree<int> tree(arena); + int numAdditions = 2 * PODArena::DefaultChunkSize / sizeof(int); + for (int i = 0; i < numAdditions; ++i) + tree.add(i); + EXPECT_GT(allocator->numRegions(), 1); + } + EXPECT_EQ(allocator->numRegions(), 0); +} + +TEST(PODRedBlackTreeTest, TestSingleElementInsertion) +{ + PODRedBlackTree<int> tree; + tree.add(5); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(5)); +} + +TEST(PODRedBlackTreeTest, TestMultipleElementInsertion) +{ + PODRedBlackTree<int> tree; + tree.add(4); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(4)); + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(3)); + tree.add(5); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(5)); + EXPECT_TRUE(tree.contains(4)); + EXPECT_TRUE(tree.contains(3)); +} + +TEST(PODRedBlackTreeTest, TestDuplicateElementInsertion) +{ + PODRedBlackTree<int> tree; + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_EQ(3, tree.size()); + EXPECT_TRUE(tree.contains(3)); +} + +TEST(PODRedBlackTreeTest, TestSingleElementInsertionAndDeletion) +{ + PODRedBlackTree<int> tree; + tree.add(5); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(5)); + tree.remove(5); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_FALSE(tree.contains(5)); +} + +TEST(PODRedBlackTreeTest, TestMultipleElementInsertionAndDeletion) +{ + PODRedBlackTree<int> tree; + tree.add(4); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(4)); + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(3)); + tree.add(5); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(5)); + EXPECT_TRUE(tree.contains(4)); + EXPECT_TRUE(tree.contains(3)); + tree.remove(4); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(3)); + EXPECT_FALSE(tree.contains(4)); + EXPECT_TRUE(tree.contains(5)); + tree.remove(5); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_TRUE(tree.contains(3)); + EXPECT_FALSE(tree.contains(4)); + EXPECT_FALSE(tree.contains(5)); + EXPECT_EQ(1, tree.size()); +} + +TEST(PODRedBlackTreeTest, TestDuplicateElementInsertionAndDeletion) +{ + PODRedBlackTree<int> tree; + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(3); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_EQ(3, tree.size()); + EXPECT_TRUE(tree.contains(3)); + tree.remove(3); + ASSERT_TRUE(tree.checkInvariants()); + tree.remove(3); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_EQ(1, tree.size()); + EXPECT_TRUE(tree.contains(3)); + tree.remove(3); + ASSERT_TRUE(tree.checkInvariants()); + EXPECT_EQ(0, tree.size()); + EXPECT_FALSE(tree.contains(3)); +} + +TEST(PODRedBlackTreeTest, FailingInsertionRegressionTest1) +{ + // These numbers came from a previously-failing randomized test run. + PODRedBlackTree<int> tree; + tree.add(5113); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(4517); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(3373); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(9307); + ASSERT_TRUE(tree.checkInvariants()); + tree.add(7077); + ASSERT_TRUE(tree.checkInvariants()); +} + +namespace { +void InsertionAndDeletionTest(const int32_t seed, const int treeSize) +{ + initRandom(seed); + const int maximumValue = treeSize; + // Build the tree. + PODRedBlackTree<int> tree; + Vector<int> values; + for (int i = 0; i < treeSize; i++) { + int value = nextRandom(maximumValue); + tree.add(value); + ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; + values.append(value); + } + // Churn the tree's contents. + for (int i = 0; i < treeSize; i++) { + // Pick a random value to remove. + int index = nextRandom(treeSize); + int value = values[index]; + // Remove this value. + tree.remove(value); + ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; + // Replace it with a new one. + value = nextRandom(maximumValue); + values[index] = value; + tree.add(value); + ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; + } +} +} // anonymous namespace + +TEST(PODRedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1) +{ + InsertionAndDeletionTest(12311, 100); +} + +TEST(PODRedBlackTreeTest, TestRandomDeletionAndInsertion) +{ + InsertionAndDeletionTest(generateSeed(), 100); +} + +} // namespace WebCore diff --git a/WebKit/chromium/tests/TreeTestHelpers.cpp b/WebKit/chromium/tests/TreeTestHelpers.cpp new file mode 100644 index 0000000..103b871 --- /dev/null +++ b/WebKit/chromium/tests/TreeTestHelpers.cpp @@ -0,0 +1,60 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#include "TreeTestHelpers.h" + +#include <cstdlib> +#include <wtf/CurrentTime.h> + +namespace WebCore { +namespace TreeTestHelpers { + +int32_t generateSeed() +{ + // A seed of 1 has the special behavior of resetting the random + // number generator. Assume that if we call this routine that we + // don't want this behavior. + int32_t seed; + do { + seed = static_cast<int32_t>(currentTime()); + } while (seed <= 1); + return seed; +} + +void initRandom(const int32_t seed) +{ + srand(seed); +} + +int32_t nextRandom(const int32_t maximumValue) +{ + // rand_r is not available on Windows + return rand() % maximumValue; +} + +} // namespace TreeTestHelpers +} // namespace WebCore diff --git a/WebKit/chromium/tests/TreeTestHelpers.h b/WebKit/chromium/tests/TreeTestHelpers.h new file mode 100644 index 0000000..af07b2a --- /dev/null +++ b/WebKit/chromium/tests/TreeTestHelpers.h @@ -0,0 +1,53 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// Simple pseudorandom number generator helper functions, used by the +// red-black and interval tree tests. +// +// These are **not** thread safe! + +#ifndef TreeTestHelpers_h +#define TreeTestHelpers_h + +#include <stdint.h> + +namespace WebCore { +namespace TreeTestHelpers { + +// Generates a seed value to be passed to initRandom(). +int32_t generateSeed(); + +// Initializes the pseudo-random number generator with a specific seed. +void initRandom(const int32_t seed); + +// Produces the next pseudo-random number in the sequence, in the +// range from [0..maximumValue). Negative numbers are not allowed and will +// produce undefined results. +int32_t nextRandom(const int32_t maximumValue); + +} // namespace TreeTestHelpers +} // namespace WebCore + +#endif // TreeTestHelpers_h |