15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010 Google Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Tests for the interval tree class. 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 291e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PODIntervalTree.h" 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 311e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/Logging.h" 321e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/testing/TreeTestHelpers.h" 33591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/Vector.h" 34f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)#include "wtf/text/WTFString.h" 35f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) 36f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)#include <gtest/gtest.h> 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WebCore { 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using TreeTestHelpers::initRandom; 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using TreeTestHelpers::nextRandom; 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<> 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<float> { 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(const float& value) { return String::number(value); } 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<> 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<void*> { 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(void* const& value) 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return String::format("0x%p", value); 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestInsertion) 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<float> tree; 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(PODInterval<float>(2, 4)); 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestInsertionAndQuery) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<float> tree; 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(PODInterval<float>(2, 4)); 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(1, 3)); 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(1U, result.size()); 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(2, result[0].low()); 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(4, result[0].high()); 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<float> tree; 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(PODInterval<float>(1, 2.5)); 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(PODInterval<float>(3.5, 5)); 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(PODInterval<float>(2, 4)); 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(3, 3)); 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(1U, result.size()); 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(2, result[0].low()); 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(4, result[0].high()); 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<> 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<int*> { 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(int* const& value) 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return String::format("0x%p", value); 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestDuplicateElementInsertion) 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<float, int*> tree; 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp1 = 1; 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp2 = 2; 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef PODIntervalTree<float, int*>::IntervalType IntervalType; 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalType interval1(1, 3, &tmp1); 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IntervalType interval2(1, 3, &tmp2); 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(interval1); 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(interval2); 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_TRUE(tree.contains(interval1)); 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_TRUE(tree.contains(interval2)); 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_TRUE(tree.remove(interval1)); 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_TRUE(tree.contains(interval2)); 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_FALSE(tree.contains(interval1)); 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_TRUE(tree.remove(interval2)); 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(0, tree.size()); 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace { 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct UserData1 { 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UserData1() 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : a(0), b(1) { } 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) float a; 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int b; 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // anonymous namespace 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<> 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<UserData1> { 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(const UserData1& value) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return String("[UserData1 a=") + String::number(value.a) + " b=" + String::number(value.b) + "]"; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData) 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<float, UserData1> tree; 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UserData1 data1; 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data1.a = 5; 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data1.b = 6; 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(2, 4, data1)); 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData) 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<float, UserData1> tree; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UserData1 data1; 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data1.a = 5; 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) data1.b = 6; 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(2, 4, data1)); 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<PODInterval<float, UserData1> > overlaps = tree.allOverlaps(tree.createInterval(3, 5, data1)); 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(1U, overlaps.size()); 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(5, overlaps[0].data().a); 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(6, overlaps[0].data().b); 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace { 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class EndpointType1 { 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) explicit EndpointType1(int value) 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_value(value) { } 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int value() const { return m_value; } 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator<(const EndpointType1& other) const { return m_value < other.m_value; } 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const EndpointType1& other) const { return m_value == other.m_value; } 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_value; 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These operators should not be called by the interval tree. 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator>(const EndpointType1& other); 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator<=(const EndpointType1& other); 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator>=(const EndpointType1& other); 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const EndpointType1& other); 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // anonymous namespace 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<> 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<EndpointType1> { 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(const EndpointType1& value) 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return String("[EndpointType1 value=") + String::number(value.value()) + "]"; 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, TestTreeDoesNotRequireMostOperators) 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<EndpointType1> tree; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(EndpointType1(1), EndpointType1(2))); 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Uncomment to debug a failure of the insertion and deletion test. Won't work 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// in release builds. 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// #define DEBUG_INSERTION_AND_DELETION_TEST 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<> 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString<int> { 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static String string(const int& value) { return String::number(value); } 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace { 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void InsertionAndDeletionTest(int32_t seed, int treeSize) 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) initRandom(seed); 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maximumValue = treeSize; 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Build the tree 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<int> tree; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<PODInterval<int> > addedElements; 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<PODInterval<int> > removedElements; 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < treeSize; i++) { 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int left = nextRandom(maximumValue); 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int length = nextRandom(maximumValue); 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODInterval<int> interval(left, left + length); 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(interval); 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef DEBUG_INSERTION_AND_DELETION_TEST 233a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >::string(interval).ascii().data()); 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) addedElements.append(interval); 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Churn the tree's contents. 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // First remove half of the elements in random order. 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < treeSize / 2; i++) { 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int index = nextRandom(addedElements.size()); 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef DEBUG_INSERTION_AND_DELETION_TEST 242a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int> >::string(addedElements[index]).ascii().data()); 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed; 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(addedElements[index]); 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) removedElements.append(addedElements[index]); 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) addedElements.remove(index); 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Now randomly add or remove elements. 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < 2 * treeSize; i++) { 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool add = false; 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!addedElements.size()) 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) add = true; 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (!removedElements.size()) 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) add = false; 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) add = (nextRandom(2) == 1); 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (add) { 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int index = nextRandom(removedElements.size()); 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef DEBUG_INSERTION_AND_DELETION_TEST 262a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >::string(removedElements[index]).ascii().data()); 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(removedElements[index]); 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) addedElements.append(removedElements[index]); 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) removedElements.remove(index); 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int index = nextRandom(addedElements.size()); 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef DEBUG_INSERTION_AND_DELETION_TEST 270a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int> >::string(addedElements[index]).ascii().data()); 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed; 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " << seed; 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) removedElements.append(addedElements[index]); 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) addedElements.remove(index); 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // anonymous namespace 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1) 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) InsertionAndDeletionTest(13972, 100); 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2) 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) InsertionAndDeletionTest(1283382113, 10); 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest3) 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is the sequence of insertions and deletions that triggered 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the failure in RandomDeletionAndInsertionRegressionTest2. 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<int> tree; 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(0, 5)); 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(4, 5)); 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(8, 9)); 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(1, 4)); 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(3, 5)); 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(4, 12)); 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(0, 2)); 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(0, 2)); 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(9, 13)); 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(0, 1)); 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(0, 2)); 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(9, 13)); 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(0, 2)); 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(0, 1)); 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(4, 5)); 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(4, 12)); 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest4) 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Even further reduced test case for RandomDeletionAndInsertionRegressionTest3. 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODIntervalTree<int> tree; 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(0, 5)); 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(8, 9)); 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(1, 4)); 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(3, 5)); 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.add(tree.createInterval(4, 12)); 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tree.remove(tree.createInterval(4, 12)); 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_TRUE(tree.checkInvariants()); 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WebCore 351