15abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick/* 25abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * Copyright (C) 2010 Google Inc. All rights reserved. 35abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 45abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * Redistribution and use in source and binary forms, with or without 55abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * modification, are permitted provided that the following conditions 65abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * are met: 75abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 85abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 1. Redistributions of source code must retain the above copyright 95abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * notice, this list of conditions and the following disclaimer. 105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 2. Redistributions in binary form must reproduce the above copyright 115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * notice, this list of conditions and the following disclaimer in the 125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * documentation and/or other materials provided with the distribution. 135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick */ 255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// A red-black tree, which is a form of a balanced binary tree. It 275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// supports efficient insertion, deletion and queries of comparable 285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// elements. The same element may be inserted multiple times. The 295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// algorithmic complexity of common operations is: 305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Insertion: O(lg(n)) 325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Deletion: O(lg(n)) 335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Querying: O(lg(n)) 345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// The data type T that is stored in this red-black tree must be only 365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Plain Old Data (POD), or bottom out into POD. It must _not_ rely on 375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// having its destructor called. This implementation internally 385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// allocates storage in large chunks and does not call the destructor 395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// on each object. 405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Type T must supply a default constructor, a copy constructor, and 425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// the "<" and "==" operators. 435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// In debug mode, printing of the data contained in the tree is 45a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch// enabled. This requires the template specialization to be available: 465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 47a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch// template<> struct WebCore::ValueToString<T> { 48a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch// static String string(const T& t); 49a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch// }; 505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// Note that when complex types are stored in this red/black tree, it 525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// is possible that single invocations of the "<" and "==" operators 535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// will be insufficient to describe the ordering of elements in the 545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// tree during queries. As a concrete example, consider the case where 555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// intervals are stored in the tree sorted by low endpoint. The "<" 565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// operator on the Interval class only compares the low endpoint, but 575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// the "==" operator takes into account the high endpoint as well. 585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// This makes the necessary logic for querying and deletion somewhat 595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// more complex. In order to properly handle such situations, the 605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// property "needsFullOrderingComparisons" must be set to true on 615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// the tree. 625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// This red-black tree is designed to be _augmented_; subclasses can 645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// add additional and summary information to each node to efficiently 655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// store and index more complex data structures. A concrete example is 665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// the IntervalTree, which extends each node with a summary statistic 675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// to efficiently store one-dimensional intervals. 685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// 695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// The design of this red-black tree comes from Cormen, Leiserson, 705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick// and Rivest, _Introduction to Algorithms_, MIT Press, 1990. 715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef PODRedBlackTree_h 735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#define PODRedBlackTree_h 745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "PODArena.h" 765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include <wtf/Assertions.h> 775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include <wtf/Noncopyable.h> 785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include <wtf/RefPtr.h> 795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef NDEBUG 805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "Logging.h" 815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include <wtf/text/CString.h> 82a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch#include <wtf/text/StringBuilder.h> 83a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch#include <wtf/text/WTFString.h> 845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merricknamespace WebCore { 875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 88a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch#ifndef NDEBUG 89a94275402997c11dd2e778633dacf4b7e630a35dBen Murdochtemplate<class T> 90a94275402997c11dd2e778633dacf4b7e630a35dBen Murdochstruct ValueToString; 91a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch#endif 92a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch 935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merricktemplate<class T> 945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickclass PODRedBlackTree { 955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickpublic: 965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Visitor interface for walking all of the tree's elements. 975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick class Visitor { 985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick public: 995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual void visit(const T& data) = 0; 1005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick protected: 1015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual ~Visitor() { } 1025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick }; 1035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Constructs a new red-black tree, allocating temporary objects 1055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // from a newly constructed PODArena. 1065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick PODRedBlackTree() 1075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick : m_arena(PODArena::create()) 1085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_root(0) 1095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_needsFullOrderingComparisons(false) 1105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef NDEBUG 1115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_verboseDebugging(false) 1125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 1135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Constructs a new red-black tree, allocating temporary objects 1175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // from the given PODArena. 1185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick explicit PODRedBlackTree(PassRefPtr<PODArena> arena) 1195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick : m_arena(arena) 1205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_root(0) 1215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_needsFullOrderingComparisons(false) 1225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef NDEBUG 1235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_verboseDebugging(false) 1245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 1255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual ~PODRedBlackTree() { } 1295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void add(const T& data) 1315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* node = m_arena->allocateObject<Node, T>(data); 1335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick insertNode(node); 1345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Returns true if the datum was found in the tree. 1375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool remove(const T& data) 1385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* node = treeSearch(data); 1405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (node) { 1415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick deleteNode(node); 1425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return true; 1435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return false; 1455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool contains(const T& data) const { return treeSearch(data); } 1485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void visitInorder(Visitor* visitor) const 1505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!m_root) 1525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return; 1535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick visitInorderImpl(m_root, visitor); 1545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int size() const 1575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Counter counter; 1595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick visitInorder(&counter); 1605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return counter.count(); 1615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // See the class documentation for an explanation of this property. 1645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons) 1655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_needsFullOrderingComparisons = needsFullOrderingComparisons; 1675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual bool checkInvariants() const 1705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int blackCount; 1725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return checkInvariantsFromNode(m_root, &blackCount); 1735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef NDEBUG 1765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Dumps the tree's contents to the logging info stream for 1775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // debugging purposes. 1785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void dump() const 1795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick dumpFromNode(m_root, 0); 1815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Turns on or off verbose debugging of the tree, causing many 1845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // messages to be logged during insertion and other operations in 1855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // debug mode. 1865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void setVerboseDebugging(bool verboseDebugging) 1875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 1885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_verboseDebugging = verboseDebugging; 1895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 1915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickprotected: 1935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick enum Color { 1945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Red = 1, 1955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Black 1965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick }; 1975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // The base Node class which is stored in the tree. Nodes are only 1995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // an internal concept; users of the tree deal only with the data 2005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // they store in it. 201ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch class Node { 202ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch WTF_MAKE_NONCOPYABLE(Node); 2035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick public: 2045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Constructor. Newly-created nodes are colored red. 2055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick explicit Node(const T& data) 2065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick : m_left(0) 2075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_right(0) 2085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_parent(0) 2095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_color(Red) 2105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick , m_data(data) 2115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 2125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 2135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual ~Node() { } 2155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Color color() const { return m_color; } 2175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void setColor(Color color) { m_color = color; } 2185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Fetches the user data. 2205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick T& data() { return m_data; } 2215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Copies all user-level fields from the source node, but not 2235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // internal fields. For example, the base implementation of this 2245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // method copies the "m_data" field, but not the child or parent 2255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // fields. Any augmentation information also does not need to be 2265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // copied, as it will be recomputed. Subclasses must call the 2275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // superclass implementation. 2285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual void copyFrom(Node* src) { m_data = src->data(); } 2295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* left() const { return m_left; } 2315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void setLeft(Node* node) { m_left = node; } 2325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* right() const { return m_right; } 2345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void setRight(Node* node) { m_right = node; } 2355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* parent() const { return m_parent; } 2375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void setParent(Node* node) { m_parent = node; } 2385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick private: 2405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* m_left; 2415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* m_right; 2425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* m_parent; 2435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Color m_color; 2445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick T m_data; 2455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick }; 2465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Returns the root of the tree, which is needed by some subclasses. 2485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* root() const { return m_root; } 2495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickprivate: 2515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // This virtual method is the hook that subclasses should use when 2525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // augmenting the red-black tree with additional per-node summary 2535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // information. For example, in the case of an interval tree, this 2545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // is used to compute the maximum endpoint of the subtree below the 2555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // given node based on the values in the left and right children. It 2565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // is guaranteed that this will be called in the correct order to 2575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // properly update such summary information based only on the values 2585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // in the left and right children. This method should return true if 2595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // the node's summary information changed. 2602bde8e466a4451c7319e3a072d118917957d6554Steve Block virtual bool updateNode(Node*) { return false; } 2615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick //---------------------------------------------------------------------- 2635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Generic binary search tree operations 2645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // 2655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Searches the tree for the given datum. 2675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* treeSearch(const T& data) const 2685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 2695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (m_needsFullOrderingComparisons) 2705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return treeSearchFullComparisons(m_root, data); 2715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return treeSearchNormal(m_root, data); 2735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 2745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Searches the tree using the normal comparison operations, 2765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // suitable for simple data types such as numbers. 2775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* treeSearchNormal(Node* current, const T& data) const 2785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 2795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (current) { 2805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (current->data() == data) 2815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return current; 2825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (data < current->data()) 2835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick current = current->left(); 2845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 2855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick current = current->right(); 2865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 2875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return 0; 2885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 2895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 2905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Searches the tree using multiple comparison operations, required 2915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // for data types with more complex behavior such as intervals. 2925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* treeSearchFullComparisons(Node* current, const T& data) const 2935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 2945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!current) 2955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return 0; 2965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (data < current->data()) 2975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return treeSearchFullComparisons(current->left(), data); 2985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (current->data() < data) 2995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return treeSearchFullComparisons(current->right(), data); 3005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (data == current->data()) 3015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return current; 3025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // We may need to traverse both the left and right subtrees. 3045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* result = treeSearchFullComparisons(current->left(), data); 3055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!result) 3065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick result = treeSearchFullComparisons(current->right(), data); 3075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return result; 3085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void treeInsert(Node* z) 3115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 3125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* y = 0; 3135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* x = m_root; 3145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (x) { 3155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y = x; 3165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (z->data() < x->data()) 3175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->left(); 3185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 3195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->right(); 3205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick z->setParent(y); 3225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!y) 3235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_root = z; 3245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else { 3255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (z->data() < y->data()) 3265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setLeft(z); 3275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 3285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setRight(z); 3295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Finds the node following the given one in sequential ordering of 3335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // their data, or null if none exists. 3345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* treeSuccessor(Node* x) 3355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 3365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x->right()) 3375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return treeMinimum(x->right()); 3385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* y = x->parent(); 3395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (y && x == y->right()) { 3405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = y; 3415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y = y->parent(); 3425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return y; 3445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Finds the minimum element in the sub-tree rooted at the given 3475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // node. 3485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* treeMinimum(Node* x) 3495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 3505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (x->left()) 3515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->left(); 3525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return x; 3535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Helper for maintaining the augmented red-black tree. 3565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void propagateUpdates(Node* start) 3575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 3585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool shouldContinue = true; 3595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (start && shouldContinue) { 3605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick shouldContinue = updateNode(start); 3615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick start = start->parent(); 3625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick //---------------------------------------------------------------------- 3665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Red-Black tree operations 3675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // 3685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Left-rotates the subtree rooted at x. 3705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Returns the new root of the subtree (x's right child). 3715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* leftRotate(Node* x) 3725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 3735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Set y. 3745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* y = x->right(); 3755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Turn y's left subtree into x's right subtree. 3775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setRight(y->left()); 3785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y->left()) 3795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->left()->setParent(x); 3805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Link x's parent to y. 3825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setParent(x->parent()); 3835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!x->parent()) 3845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_root = y; 3855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else { 3865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x == x->parent()->left()) 3875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->setLeft(y); 3885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 3895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->setRight(y); 3905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 3915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Put x on y's left. 3935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setLeft(x); 3945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setParent(y); 3955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 3965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Update nodes lowest to highest. 3975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x); 3985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(y); 3995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return y; 4005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 4015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Right-rotates the subtree rooted at y. 4035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Returns the new root of the subtree (y's left child). 4045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* rightRotate(Node* y) 4055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 4065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Set x. 4075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* x = y->left(); 4085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Turn x's right subtree into y's left subtree. 4105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setLeft(x->right()); 4115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x->right()) 4125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->right()->setParent(y); 4135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Link y's parent to x. 4155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setParent(y->parent()); 4165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!y->parent()) 4175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_root = x; 4185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else { 4195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y == y->parent()->left()) 4205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->parent()->setLeft(x); 4215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 4225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->parent()->setRight(x); 4235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 4245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Put y on x's right. 4265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setRight(y); 4275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setParent(x); 4285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Update nodes lowest to highest. 4305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(y); 4315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x); 4325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return x; 4335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 4345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Inserts the given node into the tree. 4365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void insertNode(Node* x) 4375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 4385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick treeInsert(x); 4395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setColor(Red); 4405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x); 4415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" PODRedBlackTree::InsertNode"); 4435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // The node from which to start propagating updates upwards. 4455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* updateStart = x->parent(); 4465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 4475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (x != m_root && x->parent()->color() == Red) { 4485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x->parent() == x->parent()->parent()->left()) { 4495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* y = x->parent()->parent()->right(); 4505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y && y->color() == Red) { 4515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 1 4525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" Case 1/1"); 4535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->setColor(Black); 4545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setColor(Black); 4555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->parent()->setColor(Red); 4565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x->parent()); 4575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->parent()->parent(); 4585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x); 4595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateStart = x->parent(); 4605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else { 4615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x == x->parent()->right()) { 4625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" Case 1/2"); 4635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 2 4645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->parent(); 4655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick leftRotate(x); 4665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 4675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 3 4685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" Case 1/3"); 4695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->setColor(Black); 4705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->parent()->setColor(Red); 4715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* newSubTreeRoot = rightRotate(x->parent()->parent()); 4725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateStart = newSubTreeRoot->parent(); 4735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 4745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else { 4755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Same as "then" clause with "right" and "left" exchanged. 4765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* y = x->parent()->parent()->left(); 4775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y && y->color() == Red) { 4785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 1 4795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" Case 2/1"); 4805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->setColor(Black); 4815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->setColor(Black); 4825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->parent()->setColor(Red); 4835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x->parent()); 4845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->parent()->parent(); 4855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(x); 4865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateStart = x->parent(); 4875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else { 4885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x == x->parent()->left()) { 4895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 2 4905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" Case 2/2"); 4915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = x->parent(); 4925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick rightRotate(x); 4935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 4945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 3 4955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick logIfVerbose(" Case 2/3"); 4965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->setColor(Black); 4975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->parent()->parent()->setColor(Red); 4985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* newSubTreeRoot = leftRotate(x->parent()->parent()); 4995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateStart = newSubTreeRoot->parent(); 5005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 5045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick propagateUpdates(updateStart); 5055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 5065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_root->setColor(Black); 5075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 5095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Restores the red-black property to the tree after splicing out 5105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // a node. Note that x may be null, which is why xParent must be 5115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // supplied. 5125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void deleteFixup(Node* x, Node* xParent) 5135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 5145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick while (x != m_root && (!x || x->color() == Black)) { 5155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x == xParent->left()) { 5165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Note: the text points out that w can not be null. 5175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // The reason is not obvious from simply looking at 5185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // the code; it comes about from the properties of the 5195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // red-black tree. 5205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* w = xParent->right(); 5215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT(w); // x's sibling should not be null. 5225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (w->color() == Red) { 5235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 1 5245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(Black); 5255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent->setColor(Red); 5265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick leftRotate(xParent); 5275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w = xParent->right(); 5285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if ((!w->left() || w->left()->color() == Black) 5305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick && (!w->right() || w->right()->color() == Black)) { 5315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 2 5325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(Red); 5335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = xParent; 5345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent = x->parent(); 5355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else { 5365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!w->right() || w->right()->color() == Black) { 5375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 3 5385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->left()->setColor(Black); 5395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(Red); 5405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick rightRotate(w); 5415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w = xParent->right(); 5425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 4 5445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(xParent->color()); 5455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent->setColor(Black); 5465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (w->right()) 5475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->right()->setColor(Black); 5485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick leftRotate(xParent); 5495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = m_root; 5505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent = x->parent(); 5515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else { 5535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Same as "then" clause with "right" and "left" 5545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // exchanged. 5555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 5565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Note: the text points out that w can not be null. 5575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // The reason is not obvious from simply looking at 5585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // the code; it comes about from the properties of the 5595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // red-black tree. 5605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* w = xParent->left(); 5615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick ASSERT(w); // x's sibling should not be null. 5625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (w->color() == Red) { 5635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 1 5645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(Black); 5655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent->setColor(Red); 5665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick rightRotate(xParent); 5675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w = xParent->left(); 5685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if ((!w->right() || w->right()->color() == Black) 5705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick && (!w->left() || w->left()->color() == Black)) { 5715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 2 5725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(Red); 5735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = xParent; 5745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent = x->parent(); 5755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else { 5765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!w->left() || w->left()->color() == Black) { 5775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 3 5785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->right()->setColor(Black); 5795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(Red); 5805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick leftRotate(w); 5815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w = xParent->left(); 5825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Case 4 5845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->setColor(xParent->color()); 5855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent->setColor(Black); 5865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (w->left()) 5875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick w->left()->setColor(Black); 5885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick rightRotate(xParent); 5895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = m_root; 5905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent = x->parent(); 5915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x) 5955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setColor(Black); 5965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 5975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 5985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Deletes the given node from the tree. Note that this 5995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // particular node may not actually be removed from the tree; 6005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // instead, another node might be removed and its contents 6015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // copied into z. 6025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void deleteNode(Node* z) 6035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 6045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Y is the node to be unlinked from the tree. 6055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* y; 6065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!z->left() || !z->right()) 6075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y = z; 6085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 6095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y = treeSuccessor(z); 6105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Y is guaranteed to be non-null at this point. 6125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* x; 6135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y->left()) 6145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = y->left(); 6155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 6165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x = y->right(); 6175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // X is the child of y which might potentially replace y in 6195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // the tree. X might be null at this point. 6205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* xParent; 6215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (x) { 6225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick x->setParent(y->parent()); 6235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent = x->parent(); 6245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } else 6255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick xParent = y->parent(); 6265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!y->parent()) 6275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick m_root = x; 6285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else { 6295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y == y->parent()->left()) 6305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->parent()->setLeft(x); 6315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick else 6325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick y->parent()->setRight(x); 6335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 6345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y != z) { 6355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick z->copyFrom(y); 6365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // This node has changed location in the tree and must be updated. 6375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick updateNode(z); 6385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // The parent and its parents may now be out of date. 6395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick propagateUpdates(z->parent()); 6405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 6415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // If we haven't already updated starting from xParent, do so now. 6435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (xParent && xParent != y && xParent != z) 6445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick propagateUpdates(xParent); 6455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (y->color() == Black) 6465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick deleteFixup(x, xParent); 6475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 6485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Visits the subtree rooted at the given node in order. 6505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void visitInorderImpl(Node* node, Visitor* visitor) const 6515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 6525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (node->left()) 6535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick visitInorderImpl(node->left(), visitor); 6545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick visitor->visit(node->data()); 6555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (node->right()) 6565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick visitInorderImpl(node->right(), visitor); 6575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 6585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick //---------------------------------------------------------------------- 6605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Helper class for size() 6615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // A Visitor which simply counts the number of visited elements. 663ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch class Counter : public Visitor { 664ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch WTF_MAKE_NONCOPYABLE(Counter); 6655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick public: 6665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Counter() 6675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick : m_count(0) { } 6685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick virtual void visit(const T& data) { ++m_count; } 6705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int count() const { return m_count; } 6715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick private: 6735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int m_count; 6745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick }; 6755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick //---------------------------------------------------------------------- 6775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Verification and debugging routines 6785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // 6795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Returns in the "blackCount" parameter the number of black 6815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // children along all paths to all leaves of the given node. 6825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool checkInvariantsFromNode(Node* node, int* blackCount) const 6835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 6845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Base case is a leaf node. 6855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!node) { 6865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick *blackCount = 1; 6875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return true; 6885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 6895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Each node is either red or black. 6915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!(node->color() == Red || node->color() == Black)) 6925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return false; 6935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Every leaf (or null) is black. 6955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 6965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (node->color() == Red) { 6975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Both of its children are black. 6985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!((!node->left() || node->left()->color() == Black))) 6995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return false; 7005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!((!node->right() || node->right()->color() == Black))) 7015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return false; 7025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 7035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Every simple path to a leaf node contains the same number of 7055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // black nodes. 7065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick int leftCount = 0, rightCount = 0; 7075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool leftValid = checkInvariantsFromNode(node->left(), &leftCount); 7085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool rightValid = checkInvariantsFromNode(node->right(), &rightCount); 7095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!leftValid || !rightValid) 7105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return false; 7115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick *blackCount = leftCount + (node->color() == Black ? 1 : 0); 7125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return leftCount == rightCount; 7135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 7145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifdef NDEBUG 7162bde8e466a4451c7319e3a072d118917957d6554Steve Block void logIfVerbose(const char*) const { } 7175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#else 7185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void logIfVerbose(const char* output) const 7195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 7205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (m_verboseDebugging) 7215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick LOG_ERROR("%s", output); 7225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 7235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 7245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef NDEBUG 7265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Dumps the subtree rooted at the given node. 7275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick void dumpFromNode(Node* node, int indentation) const 7285abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick { 7295abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick StringBuilder builder; 7305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick for (int i = 0; i < indentation; i++) 7315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick builder.append(" "); 7325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick builder.append("-"); 7335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (node) { 7345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick builder.append(" "); 735a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch builder.append(ValueToString<T>::string(node->data())); 7365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick builder.append((node->color() == Black) ? " (black)" : " (red)"); 7375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 7385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick LOG_ERROR("%s", builder.toString().ascii().data()); 7395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (node) { 7405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick dumpFromNode(node->left(), indentation + 2); 7415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick dumpFromNode(node->right(), indentation + 2); 7425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 7435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 7445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 7455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick //---------------------------------------------------------------------- 7475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Data members 7485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick RefPtr<PODArena> m_arena; 7505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick Node* m_root; 7515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool m_needsFullOrderingComparisons; 7525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#ifndef NDEBUG 7535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick bool m_verboseDebugging; 7545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif 7555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick}; 7565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} // namespace WebCore 7585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 7595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#endif // PODRedBlackTree_h 760