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)// A red-black tree, which is a form of a balanced binary tree. It 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// supports efficient insertion, deletion and queries of comparable 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// elements. The same element may be inserted multiple times. The 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// algorithmic complexity of common operations is: 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Insertion: O(lg(n)) 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Deletion: O(lg(n)) 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Querying: O(lg(n)) 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// The data type T that is stored in this red-black tree must be only 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Plain Old Data (POD), or bottom out into POD. It must _not_ rely on 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// having its destructor called. This implementation internally 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// allocates storage in large chunks and does not call the destructor 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// on each object. 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Type T must supply a default constructor, a copy constructor, and 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// the "<" and "==" operators. 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// In debug mode, printing of the data contained in the tree is 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// enabled. This requires the template specialization to be available: 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 47e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)// template<> struct ValueToString<T> { 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// static String string(const T& t); 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// }; 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Note that when complex types are stored in this red/black tree, it 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// is possible that single invocations of the "<" and "==" operators 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// will be insufficient to describe the ordering of elements in the 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// tree during queries. As a concrete example, consider the case where 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// intervals are stored in the tree sorted by low endpoint. The "<" 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// operator on the Interval class only compares the low endpoint, but 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// the "==" operator takes into account the high endpoint as well. 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This makes the necessary logic for querying and deletion somewhat 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// more complex. In order to properly handle such situations, the 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// property "needsFullOrderingComparisons" must be set to true on 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// the tree. 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This red-black tree is designed to be _augmented_; subclasses can 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// add additional and summary information to each node to efficiently 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// store and index more complex data structures. A concrete example is 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// the IntervalTree, which extends each node with a summary statistic 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// to efficiently store one-dimensional intervals. 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// The design of this red-black tree comes from Cormen, Leiserson, 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// and Rivest, _Introduction to Algorithms_, MIT Press, 1990. 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef PODRedBlackTree_h 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define PODRedBlackTree_h 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 751e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PODFreeListArena.h" 767757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/Assertions.h" 777757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/Noncopyable.h" 787757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/RefPtr.h" 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 807757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/text/CString.h" 817757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/text/StringBuilder.h" 827757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/text/WTFString.h" 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 85c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<class T> 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct ValueToString; 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)enum UninitializedTreeEnum { 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UninitializedTree 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<class T> 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class PODRedBlackTree { 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class Node; 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Visitor interface for walking all of the tree's elements. 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class Visitor { 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual void visit(const T& data) = 0; 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) protected: 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual ~Visitor() { } 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Constructs a new red-black tree without allocating an arena. 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // isInitialized will return false in this case. initIfNeeded can be used 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // to init the structure. This constructor is usefull for creating 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // lazy initialized tree. 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) explicit PODRedBlackTree(UninitializedTreeEnum) 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_root(0) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_needsFullOrderingComparisons(false) 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_verboseDebugging(false) 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Constructs a new red-black tree, allocating temporary objects 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // from a newly constructed PODFreeListArena. 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PODRedBlackTree() 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_arena(PODFreeListArena<Node>::create()) 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_root(0) 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_needsFullOrderingComparisons(false) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_verboseDebugging(false) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Constructs a new red-black tree, allocating temporary objects 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // from the given PODArena. 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) explicit PODRedBlackTree(PassRefPtr<PODFreeListArena<Node> > arena) 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_arena(arena) 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_root(0) 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_needsFullOrderingComparisons(false) 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_verboseDebugging(false) 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual ~PODRedBlackTree() { } 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Clearing will delete the contents of the tree. After this call 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // isInitialized will return false. 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear() 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) markFree(m_root); 153d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) m_arena = nullptr; 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_root = 0; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 15602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isInitialized() const 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_arena; 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 16102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void initIfNeeded() 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_arena) 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_arena = PODFreeListArena<Node>::create(); 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void initIfNeeded(PODFreeListArena<Node>* arena) 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_arena) 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_arena = arena; 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void add(const T& data) 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(isInitialized()); 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* node = m_arena->template allocateObject<T>(data); 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) insertNode(node); 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns true if the datum was found in the tree. 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool remove(const T& data) 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(isInitialized()); 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* node = treeSearch(data); 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node) { 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deleteNode(node); 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool contains(const T& data) const 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(isInitialized()); 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return treeSearch(data); 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void visitInorder(Visitor* visitor) const 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(isInitialized()); 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_root) 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) visitInorderImpl(m_root, visitor); 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int size() const 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(isInitialized()); 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Counter counter; 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) visitInorder(&counter); 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return counter.count(); 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // See the class documentation for an explanation of this property. 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons) 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_needsFullOrderingComparisons = needsFullOrderingComparisons; 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual bool checkInvariants() const 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(isInitialized()); 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int blackCount; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return checkInvariantsFromNode(m_root, &blackCount); 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Dumps the tree's contents to the logging info stream for 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // debugging purposes. 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void dump() const 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_arena) 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dumpFromNode(m_root, 0); 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Turns on or off verbose debugging of the tree, causing many 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // messages to be logged during insertion and other operations in 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // debug mode. 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void setVerboseDebugging(bool verboseDebugging) 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_verboseDebugging = verboseDebugging; 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) enum Color { 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Red = 1, 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Black 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The base Node class which is stored in the tree. Nodes are only 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // an internal concept; users of the tree deal only with the data 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // they store in it. 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class Node { 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_NONCOPYABLE(Node); 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Constructor. Newly-created nodes are colored red. 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) explicit Node(const T& data) 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_left(0) 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_right(0) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_parent(0) 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_color(Red) 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_data(data) 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual ~Node() { } 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Color color() const { return m_color; } 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void setColor(Color color) { m_color = color; } 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Fetches the user data. 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T& data() { return m_data; } 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Copies all user-level fields from the source node, but not 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // internal fields. For example, the base implementation of this 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // method copies the "m_data" field, but not the child or parent 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // fields. Any augmentation information also does not need to be 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // copied, as it will be recomputed. Subclasses must call the 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // superclass implementation. 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual void copyFrom(Node* src) { m_data = src->data(); } 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* left() const { return m_left; } 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void setLeft(Node* node) { m_left = node; } 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* right() const { return m_right; } 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void setRight(Node* node) { m_right = node; } 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* parent() const { return m_parent; } 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void setParent(Node* node) { m_parent = node; } 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_left; 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_right; 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_parent; 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Color m_color; 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T m_data; 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)protected: 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns the root of the tree, which is needed by some subclasses. 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* root() const { return m_root; } 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This virtual method is the hook that subclasses should use when 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // augmenting the red-black tree with additional per-node summary 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // information. For example, in the case of an interval tree, this 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // is used to compute the maximum endpoint of the subtree below the 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // given node based on the values in the left and right children. It 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // is guaranteed that this will be called in the correct order to 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // properly update such summary information based only on the values 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // in the left and right children. This method should return true if 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the node's summary information changed. 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual bool updateNode(Node*) { return false; } 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) //---------------------------------------------------------------------- 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Generic binary search tree operations 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Searches the tree for the given datum. 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* treeSearch(const T& data) const 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_needsFullOrderingComparisons) 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return treeSearchFullComparisons(m_root, data); 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return treeSearchNormal(m_root, data); 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Searches the tree using the normal comparison operations, 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // suitable for simple data types such as numbers. 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* treeSearchNormal(Node* current, const T& data) const 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (current) { 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (current->data() == data) 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return current; 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (data < current->data()) 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current->left(); 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current->right(); 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Searches the tree using multiple comparison operations, required 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // for data types with more complex behavior such as intervals. 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* treeSearchFullComparisons(Node* current, const T& data) const 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current) 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (data < current->data()) 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return treeSearchFullComparisons(current->left(), data); 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (current->data() < data) 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return treeSearchFullComparisons(current->right(), data); 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (data == current->data()) 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return current; 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We may need to traverse both the left and right subtrees. 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* result = treeSearchFullComparisons(current->left(), data); 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!result) 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result = treeSearchFullComparisons(current->right(), data); 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void treeInsert(Node* z) 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* y = 0; 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* x = m_root; 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (x) { 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = x; 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (z->data() < x->data()) 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->left(); 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->right(); 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z->setParent(y); 3761e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (!y) { 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_root = z; 3781e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (z->data() < y->data()) 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setLeft(z); 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setRight(z); 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Finds the node following the given one in sequential ordering of 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // their data, or null if none exists. 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* treeSuccessor(Node* x) 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x->right()) 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return treeMinimum(x->right()); 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* y = x->parent(); 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (y && x == y->right()) { 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = y; 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = y->parent(); 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return y; 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Finds the minimum element in the sub-tree rooted at the given 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // node. 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* treeMinimum(Node* x) 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (x->left()) 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->left(); 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return x; 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Helper for maintaining the augmented red-black tree. 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void propagateUpdates(Node* start) 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool shouldContinue = true; 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (start && shouldContinue) { 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shouldContinue = updateNode(start); 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) start = start->parent(); 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) //---------------------------------------------------------------------- 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Red-Black tree operations 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Left-rotates the subtree rooted at x. 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns the new root of the subtree (x's right child). 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* leftRotate(Node* x) 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Set y. 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* y = x->right(); 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Turn y's left subtree into x's right subtree. 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setRight(y->left()); 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y->left()) 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->left()->setParent(x); 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Link x's parent to y. 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setParent(x->parent()); 4371e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (!x->parent()) { 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_root = y; 4391e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x == x->parent()->left()) 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->setLeft(y); 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->setRight(y); 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Put x on y's left. 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setLeft(x); 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setParent(y); 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Update nodes lowest to highest. 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x); 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(y); 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return y; 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Right-rotates the subtree rooted at y. 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns the new root of the subtree (y's left child). 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* rightRotate(Node* y) 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Set x. 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* x = y->left(); 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Turn x's right subtree into y's left subtree. 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setLeft(x->right()); 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x->right()) 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->right()->setParent(y); 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Link y's parent to x. 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setParent(y->parent()); 4701e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (!y->parent()) { 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_root = x; 4721e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y == y->parent()->left()) 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->parent()->setLeft(x); 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->parent()->setRight(x); 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Put y on x's right. 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setRight(y); 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setParent(x); 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Update nodes lowest to highest. 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(y); 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x); 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return x; 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Inserts the given node into the tree. 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void insertNode(Node* x) 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) treeInsert(x); 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setColor(Red); 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x); 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" PODRedBlackTree::InsertNode"); 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The node from which to start propagating updates upwards. 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* updateStart = x->parent(); 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (x != m_root && x->parent()->color() == Red) { 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x->parent() == x->parent()->parent()->left()) { 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* y = x->parent()->parent()->right(); 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y && y->color() == Red) { 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 1 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" Case 1/1"); 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->setColor(Black); 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setColor(Black); 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->parent()->setColor(Red); 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x->parent()); 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->parent()->parent(); 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x); 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateStart = x->parent(); 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x == x->parent()->right()) { 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" Case 1/2"); 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 2 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->parent(); 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) leftRotate(x); 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 3 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" Case 1/3"); 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->setColor(Black); 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->parent()->setColor(Red); 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* newSubTreeRoot = rightRotate(x->parent()->parent()); 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateStart = newSubTreeRoot->parent(); 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Same as "then" clause with "right" and "left" exchanged. 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* y = x->parent()->parent()->left(); 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y && y->color() == Red) { 5325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 1 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" Case 2/1"); 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->setColor(Black); 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->setColor(Black); 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->parent()->setColor(Red); 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x->parent()); 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->parent()->parent(); 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(x); 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateStart = x->parent(); 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x == x->parent()->left()) { 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 2 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" Case 2/2"); 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = x->parent(); 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) rightRotate(x); 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 3 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) logIfVerbose(" Case 2/3"); 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->setColor(Black); 5515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->parent()->parent()->setColor(Red); 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* newSubTreeRoot = leftRotate(x->parent()->parent()); 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateStart = newSubTreeRoot->parent(); 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) propagateUpdates(updateStart); 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_root->setColor(Black); 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Restores the red-black property to the tree after splicing out 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // a node. Note that x may be null, which is why xParent must be 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // supplied. 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void deleteFixup(Node* x, Node* xParent) 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (x != m_root && (!x || x->color() == Black)) { 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x == xParent->left()) { 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note: the text points out that w can not be null. 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The reason is not obvious from simply looking at 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the code; it comes about from the properties of the 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // red-black tree. 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* w = xParent->right(); 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(w); // x's sibling should not be null. 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (w->color() == Red) { 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 1 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(Black); 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent->setColor(Red); 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) leftRotate(xParent); 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w = xParent->right(); 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((!w->left() || w->left()->color() == Black) 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) && (!w->right() || w->right()->color() == Black)) { 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 2 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(Red); 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = xParent; 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent = x->parent(); 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!w->right() || w->right()->color() == Black) { 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 3 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->left()->setColor(Black); 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(Red); 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) rightRotate(w); 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w = xParent->right(); 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 4 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(xParent->color()); 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent->setColor(Black); 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (w->right()) 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->right()->setColor(Black); 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) leftRotate(xParent); 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = m_root; 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent = x->parent(); 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Same as "then" clause with "right" and "left" 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // exchanged. 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note: the text points out that w can not be null. 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The reason is not obvious from simply looking at 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the code; it comes about from the properties of the 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // red-black tree. 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* w = xParent->left(); 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(w); // x's sibling should not be null. 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (w->color() == Red) { 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 1 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(Black); 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent->setColor(Red); 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) rightRotate(xParent); 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w = xParent->left(); 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((!w->right() || w->right()->color() == Black) 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) && (!w->left() || w->left()->color() == Black)) { 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 2 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(Red); 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = xParent; 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent = x->parent(); 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!w->left() || w->left()->color() == Black) { 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 3 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->right()->setColor(Black); 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(Red); 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) leftRotate(w); 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w = xParent->left(); 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Case 4 6385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->setColor(xParent->color()); 6395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent->setColor(Black); 6405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (w->left()) 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) w->left()->setColor(Black); 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) rightRotate(xParent); 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = m_root; 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent = x->parent(); 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x) 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setColor(Black); 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Deletes the given node from the tree. Note that this 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // particular node may not actually be removed from the tree; 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // instead, another node might be removed and its contents 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // copied into z. 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void deleteNode(Node* z) 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Y is the node to be unlinked from the tree. 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* y; 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!z->left() || !z->right()) 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = z; 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = treeSuccessor(z); 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Y is guaranteed to be non-null at this point. 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* x; 6675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y->left()) 6685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = y->left(); 6695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 6705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = y->right(); 6715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // X is the child of y which might potentially replace y in 6735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the tree. X might be null at this point. 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* xParent; 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x) { 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x->setParent(y->parent()); 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent = x->parent(); 6781e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 6795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xParent = y->parent(); 6801e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 6811e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (!y->parent()) { 6825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_root = x; 6831e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 6845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y == y->parent()->left()) 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->parent()->setLeft(x); 6865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y->parent()->setRight(x); 6885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y != z) { 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z->copyFrom(y); 6915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This node has changed location in the tree and must be updated. 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) updateNode(z); 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The parent and its parents may now be out of date. 6945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) propagateUpdates(z->parent()); 6955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If we haven't already updated starting from xParent, do so now. 6985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (xParent && xParent != y && xParent != z) 6995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) propagateUpdates(xParent); 7005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (y->color() == Black) 7015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deleteFixup(x, xParent); 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_arena->freeObject(y); 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Visits the subtree rooted at the given node in order. 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void visitInorderImpl(Node* node, Visitor* visitor) const 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node->left()) 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) visitInorderImpl(node->left(), visitor); 7115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) visitor->visit(node->data()); 7125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node->right()) 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) visitInorderImpl(node->right(), visitor); 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void markFree(Node *node) 7175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!node) 7195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 7205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node->left()) 7225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) markFree(node->left()); 7235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node->right()) 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) markFree(node->right()); 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_arena->freeObject(node); 7265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) //---------------------------------------------------------------------- 7295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Helper class for size() 7305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // A Visitor which simply counts the number of visited elements. 7325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class Counter : public Visitor { 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_NONCOPYABLE(Counter); 7345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 7355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Counter() 7365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_count(0) { } 7375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) virtual void visit(const T&) { ++m_count; } 7395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int count() const { return m_count; } 7405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 7425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_count; 7435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 7445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) //---------------------------------------------------------------------- 7465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Verification and debugging routines 7475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 7485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns in the "blackCount" parameter the number of black 7505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // children along all paths to all leaves of the given node. 7515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool checkInvariantsFromNode(Node* node, int* blackCount) const 7525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Base case is a leaf node. 7545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!node) { 7555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *blackCount = 1; 7565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 7575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Each node is either red or black. 7605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(node->color() == Red || node->color() == Black)) 7615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 7625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Every leaf (or null) is black. 7645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node->color() == Red) { 7665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Both of its children are black. 7675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!((!node->left() || node->left()->color() == Black))) 7685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!((!node->right() || node->right()->color() == Black))) 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 7715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Every simple path to a leaf node contains the same number of 7745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // black nodes. 7755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int leftCount = 0, rightCount = 0; 7765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool leftValid = checkInvariantsFromNode(node->left(), &leftCount); 7775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool rightValid = checkInvariantsFromNode(node->right(), &rightCount); 7785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!leftValid || !rightValid) 7795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 7805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *blackCount = leftCount + (node->color() == Black ? 1 : 0); 7815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return leftCount == rightCount; 7825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef NDEBUG 7855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void logIfVerbose(const char*) const { } 7865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 7875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void logIfVerbose(const char* output) const 7885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_verboseDebugging) 790a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("%s", output); 7915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 7935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 7955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Dumps the subtree rooted at the given node. 7965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void dumpFromNode(Node* node, int indentation) const 7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) StringBuilder builder; 7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < indentation; i++) 8009e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles) builder.append(' '); 8019e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles) builder.append('-'); 8025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node) { 8039e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles) builder.append(' '); 8045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) builder.append(ValueToString<T>::string(node->data())); 8055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) builder.append((node->color() == Black) ? " (black)" : " (red)"); 8065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 807a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) WTF_LOG_ERROR("%s", builder.toString().ascii().data()); 8085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node) { 8095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dumpFromNode(node->left(), indentation + 2); 8105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dumpFromNode(node->right(), indentation + 2); 8115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 8145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) //---------------------------------------------------------------------- 8165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Data members 8175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) RefPtr<PODFreeListArena<Node> > m_arena; 8195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_root; 8205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool m_needsFullOrderingComparisons; 8215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 8225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool m_verboseDebugging; 8235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 8245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 8255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 826c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 8275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // PODRedBlackTree_h 829