Attachment 66464 Details for Bug 45060 – Revised patch

[patch] Revised patch

red-black-tree-and-arena-tests.patch (text/plain), 18.03 KB, created by Kenneth Russell on 2010-09-02 19:58:13 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Kenneth Russell

Created: 2010-09-02 19:58:13 PDT

Size: 18.03 KB

patch

obsolete

>Index: WebKit/chromium/ChangeLog
>===================================================================
>--- WebKit/chromium/ChangeLog	(revision 66706)
>+++ WebKit/chromium/ChangeLog	(working copy)
>@@ -1,3 +1,22 @@
>+2010-09-02  Kenneth Russell  <kbr@google.com>
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Add unit tests for red-black tree and (POD) arena
>+        https://bugs.webkit.org/show_bug.cgi?id=45060
>+
>+        * WebKit.gyp:
>+        * tests/PODArenaTest.cpp: Added.
>+        (WebCore::TestClass1::TestClass2::TestClass2):
>+        (WebCore::TEST_F):
>+        * tests/PODRedBlackTreeTest.cpp: Added.
>+        (WebCore::TEST):
>+        * tests/TreeTestHelpers.cpp: Added.
>+        (WebCore::TreeTestHelpers::generateSeed):
>+        (WebCore::TreeTestHelpers::initRandom):
>+        (WebCore::TreeTestHelpers::nextRandom):
>+        * tests/TreeTestHelpers.h: Added.
>+
> 2010-09-02  Kent Tamura  <tkent@chromium.org>
> 
>         Reviewed by Dimitri Glazkov.
>Index: WebKit/chromium/WebKit.gyp
>===================================================================
>--- WebKit/chromium/WebKit.gyp	(revision 66706)
>+++ WebKit/chromium/WebKit.gyp	(working copy)
>@@ -738,8 +738,12 @@
>                         'tests/IDBKeyPathTest.cpp',
>                         'tests/KeyboardTest.cpp',
>                         'tests/KURLTest.cpp',
>+                        'tests/PODArenaTest.cpp',
>+                        'tests/PODRedBlackTreeTest.cpp',
>                         'tests/RunAllTests.cpp',
>                         'tests/TilingDataTest.cpp',
>+                        'tests/TreeTestHelpers.cpp',
>+                        'tests/TreeTestHelpers.h',
>                     ],
>                     'conditions': [
>                         ['OS=="win"', {
>Index: WebKit/chromium/tests/PODArenaTest.cpp
>===================================================================
>--- WebKit/chromium/tests/PODArenaTest.cpp	(revision 0)
>+++ WebKit/chromium/tests/PODArenaTest.cpp	(revision 0)
>@@ -0,0 +1,151 @@
>+/*
>+ * Copyright 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:
>+ *
>+ *     * Redistributions of source code must retain the above copyright
>+ * notice, this list of conditions and the following disclaimer.
>+ *     * 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.
>+ *     * Neither the name of Google Inc. nor the names of its
>+ * contributors may be used to endorse or promote products derived from
>+ * this software without specific prior written permission.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT
>+ * OWNER OR 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 PODArena.
>+
>+#include "config.h"
>+
>+#include "PODArena.h"
>+
>+#include <algorithm>
>+#include <gtest/gtest.h>
>+#include <wtf/FastMalloc.h>
>+#include <wtf/RefPtr.h>
>+#include <wtf/Vector.h>
>+
>+namespace WebCore {
>+
>+namespace {
>+
>+// 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();
>+    }
>+
>+protected:
>+    TrackedAllocator() { }
>+
>+private:
>+    Vector<void*> m_allocatedRegions;
>+};
>+
>+// 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);
>+    for (int i = 0; i < 10000; ++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
>Index: WebKit/chromium/tests/PODRedBlackTreeTest.cpp
>===================================================================
>--- WebKit/chromium/tests/PODRedBlackTreeTest.cpp	(revision 0)
>+++ WebKit/chromium/tests/PODRedBlackTreeTest.cpp	(revision 0)
>@@ -0,0 +1,200 @@
>+/*
>+ * Copyright 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:
>+ *
>+ *     * Redistributions of source code must retain the above copyright
>+ * notice, this list of conditions and the following disclaimer.
>+ *     * 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.
>+ *     * Neither the name of Google Inc. nor the names of its
>+ * contributors may be used to endorse or promote products derived from
>+ * this software without specific prior written permission.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT
>+ * OWNER OR 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 "TreeTestHelpers.h"
>+#include <gtest/gtest.h>
>+#include <wtf/Vector.h>
>+
>+namespace WebCore {
>+
>+using namespace TreeTestHelpers;
>+
>+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)
>+{
>+    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 val = nextRandom(maximumValue);
>+        tree.add(val);
>+        ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
>+        values.append(val);
>+    }
>+    // Churn the tree's contents.
>+    for (int i = 0; i < treeSize; i++) {
>+        // Pick a random value to remove.
>+        int idx = nextRandom(treeSize);
>+        int val = values[idx];
>+        // Remove this value.
>+        tree.remove(val);
>+        ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
>+        // Replace it with a new one.
>+        val = nextRandom(maximumValue);
>+        values[idx] = val;
>+        tree.add(val);
>+        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
>Index: WebKit/chromium/tests/TreeTestHelpers.cpp
>===================================================================
>--- WebKit/chromium/tests/TreeTestHelpers.cpp	(revision 0)
>+++ WebKit/chromium/tests/TreeTestHelpers.cpp	(revision 0)
>@@ -0,0 +1,66 @@
>+/*
>+ * Copyright 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:
>+ *
>+ *     * Redistributions of source code must retain the above copyright
>+ * notice, this list of conditions and the following disclaimer.
>+ *     * 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.
>+ *     * Neither the name of Google Inc. nor the names of its
>+ * contributors may be used to endorse or promote products derived from
>+ * this software without specific prior written permission.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT
>+ * OWNER OR 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
>Index: WebKit/chromium/tests/TreeTestHelpers.h
>===================================================================
>--- WebKit/chromium/tests/TreeTestHelpers.h	(revision 0)
>+++ WebKit/chromium/tests/TreeTestHelpers.h	(revision 0)
>@@ -0,0 +1,59 @@
>+/*
>+ * Copyright 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:
>+ *
>+ *     * Redistributions of source code must retain the above copyright
>+ * notice, this list of conditions and the following disclaimer.
>+ *     * 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.
>+ *     * Neither the name of Google Inc. nor the names of its
>+ * contributors may be used to endorse or promote products derived from
>+ * this software without specific prior written permission.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT
>+ * OWNER OR 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

Flags:

fishd: review-
kbr: commit-queue-

Actions: View | Formatted Diff | Diff

Attachments on bug 45060: 66273 | 66288 | 66460 | 66464 | 66565 | 66567