1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 66034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 76034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 86034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#ifndef GrRedBlackTree_DEFINED 96034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#define GrRedBlackTree_DEFINED 106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org#include "GrConfig.h" 12a0b40280a49a8a43af7929ead3b3489951c58501commit-bot@chromium.org#include "SkTypes.h" 136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T> 156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comclass GrLess { 166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator()(const T& a, const T& b) const { return a < b; } 186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T> 216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comclass GrLess<T*> { 226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator()(const T* a, const T* b) const { return *a < *b; } 246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 264fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgclass GrStrLess { 274fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgpublic: 284fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0; } 294fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org}; 304fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com/** 326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * In debug build this will cause full traversals of the tree when the validate 336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * is called on insert and remove. Useful for debugging but very slow. 346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#define DEEP_VALIDATE 0 366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com/** 386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * A sorted tree that uses the red-black tree algorithm. Allows duplicate 396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * entries. Data is of type T and is compared using functor C. A single C object 406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * will be created and used for all comparisons. 416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C = GrLess<T> > 43e3beb6bd7de7fa211681abbb0be58e80b19885e0commit-bot@chromium.orgclass GrRedBlackTree : SkNoncopyable { 446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Creates an empty tree. 476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GrRedBlackTree(); 496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com virtual ~GrRedBlackTree(); 506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Class used to iterater through the tree. The valid range of the tree 536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * is given by [begin(), end()). It is legal to dereference begin() but not 546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * end(). The iterator has preincrement and predecrement operators, it is 556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * legal to decerement end() if the tree is not empty to get the last 566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * element. However, a last() helper is provided. 576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com class Iter; 596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Add an element to the tree. Duplicates are allowed. 626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to add. 636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the item. 646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter insert(const T& t); 666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Removes all items in the tree. 696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void reset(); 716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return true if there are no items in the tree, false otherwise. 746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool empty() const {return 0 == fCount;} 766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return the number of items in the tree. 796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count() const {return fCount;} 816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the first item in sorted order, or end() if empty 846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter begin(); 866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Gets the last valid iterator. This is always valid, even on an empty. 886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * However, it can never be dereferenced. Useful as a loop terminator. 896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator that is just beyond the last item in sorted order. 906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter end(); 926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator that to the last item in sorted order, or end() if 946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * empty. 956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter last(); 976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Finds an occurrence of an item. 1006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to find. 1016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to a tree element equal to t or end() if none exists. 1026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter find(const T& t); 1046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Finds the first of an item in iterator order. 1066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to find. 1076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the first element equal to t or end() if 1086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * none exists. 1096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter findFirst(const T& t); 1116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Finds the last of an item in iterator order. 1136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to find. 1146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return an iterator to the last element equal to t or end() if 1156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * none exists. 1166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter findLast(const T& t); 1186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Gets the number of items in the tree equal to t. 1206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param t the item to count. 1216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @return number of items equal to t in the tree 1226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int countOf(const T& t) const; 1246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /** 1266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * Removes the item indicated by an iterator. The iterator will not be valid 1276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * afterwards. 1286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * 1296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * @param iter iterator of item to remove. Must be valid (not end()). 1306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 1316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void remove(const Iter& iter) { deleteAtNode(iter.fN); } 1326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comprivate: 1346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com enum Color { 1356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color, 1366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kBlack_Color 1376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com }; 1386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com enum Child { 1406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kLeft_Child = 0, 1416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child = 1 1426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com }; 1436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com struct Node { 1456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com T fItem; 1466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Color fColor; 1476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fParent; 1496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fChildren[2]; 1506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com }; 1516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void rotateRight(Node* n); 1536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void rotateLeft(Node* n); 1546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static Node* SuccessorNode(Node* x); 1566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static Node* PredecessorNode(Node* x); 1576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void deleteAtNode(Node* x); 1596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com static void RecursiveDelete(Node* x); 1606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 161bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com int onCountOf(const Node* n, const T& t) const; 1626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 163515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org#ifdef SK_DEBUG 1646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void validate() const; 1656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int checkNode(Node* n, int* blackHeight) const; 1666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // checks relationship between a node and its children. allowRedRed means 1676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // node may be in an intermediate state where a red parent has a red child. 1686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool validateChildRelations(const Node* n, bool allowRedRed) const; 1696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // place to stick break point if validateChildRelations is failing. 1706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool validateChildRelationsFailed() const { return false; } 1716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#else 1726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com void validate() const {} 1736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 1746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int fCount; 1766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fRoot; 1776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fFirst; 1786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fLast; 1796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com const C fComp; 1816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 1826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 1836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 1846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comclass GrRedBlackTree<T,C>::Iter { 1856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.compublic: 1866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter() {}; 1876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;} 1886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter& operator =(const Iter& i) { 1896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = i.fN; 1906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fTree = i.fTree; 1916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return *this; 1926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // altering the sort value of the item using this method will cause 1946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // errors. 1956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com T& operator *() const { return fN->fItem; } 1966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator ==(const Iter& i) const { 1976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return fN == i.fN && fTree == i.fTree; 1986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 1996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool operator !=(const Iter& i) const { return !(*this == i); } 2006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter& operator ++() { 201f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*this != fTree->end()); 2026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = SuccessorNode(fN); 2036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return *this; 2046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Iter& operator --() { 206f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(*this != fTree->begin()); 2076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != fN) { 2086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = PredecessorNode(fN); 2096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com *this = fTree->last(); 2116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return *this; 2136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comprivate: 2166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com friend class GrRedBlackTree; 2176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com explicit Iter(Node* n, GrRedBlackTree* tree) { 2186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fN = n; 2196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fTree = tree; 2206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* fN; 2226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GrRedBlackTree* fTree; 2236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com}; 2246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comGrRedBlackTree<T,C>::GrRedBlackTree() : fComp() { 2276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = NULL; 2286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = NULL; 2296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = NULL; 2306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fCount = 0; 2316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 2326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comGrRedBlackTree<T,C>::~GrRedBlackTree() { 2366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(fRoot); 2376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() { 2416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(fFirst, this); 2426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() { 2466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(NULL, this); 2476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() { 2516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(fLast, this); 2526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) { 2566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 2576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 2586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 2596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 2626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(n, this); 2636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 2656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return end(); 2686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) { 2726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 2736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* leftMost = NULL; 2746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 2756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 2766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 2796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // found one. check if another in left subtree. 2806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com leftMost = n; 2816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 2846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 2876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(leftMost, this); 2886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 2896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 2906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 2916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) { 2926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 2936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* rightMost = NULL; 2946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 2956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 2966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 2976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 2986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 2996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // found one. check if another in right subtree. 3006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rightMost = n; 3016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 3036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return Iter(rightMost, this); 3066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 3096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comint GrRedBlackTree<T,C>::countOf(const T& t) const { 310bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com return onCountOf(fRoot, t); 3116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 314bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.comint GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const { 3156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // this is count*log(n) :( 3166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 3176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fComp(t, n->fItem)) { 3186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kLeft_Child]; 3196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 3206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!fComp(n->fItem, t)) { 3216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count = 1; 322bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com count += onCountOf(n->fChildren[kLeft_Child], t); 323bcdbbe61e1a3f89545b2c1461164f0f8bf5f0797bsalomon@google.com count += onCountOf(n->fChildren[kRight_Child], t); 3246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return count; 3256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = n->fChildren[kRight_Child]; 3276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return 0; 3306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 3346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::reset() { 3356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(fRoot); 3366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = NULL; 3376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = NULL; 3386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = NULL; 3396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fCount = 0; 3406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 3416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 3436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) { 3446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 3456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com ++fCount; 3476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 348c377baf406996aed18d82d328029c82dbc3b8ddatomhudson@google.com Node* x = SkNEW(Node); 3496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fChildren[kLeft_Child] = NULL; 3506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fChildren[kRight_Child] = NULL; 3516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fItem = t; 3526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3535aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com Node* returnNode = x; 3545aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com 3556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* gp = NULL; 3566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* p = NULL; 3576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* n = fRoot; 358ba9d628b1b7aa13ddd59499624f672c6443b5f74bsalomon@google.com Child pc = kLeft_Child; // suppress uninit warning 3592c2508d2ede7e6a8eb43dba0ef2419905ccbb3d8tomhudson@google.com Child gpc = kLeft_Child; 3606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool first = true; 3626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool last = true; 3636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != n) { 3646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gpc = pc; 3656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child; 3666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com first = first && kLeft_Child == pc; 3676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com last = last && kRight_Child == pc; 3686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp = p; 3696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = n; 3706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n = p->fChildren[pc]; 3716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (last) { 3736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = x; 3746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (first) { 3766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = x; 3776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == p) { 3806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = x; 3816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fColor = kBlack_Color; 3826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fParent = NULL; 383f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(1 == fCount); 3845aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 3856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 3866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fChildren[pc] = x; 3876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fColor = kRed_Color; 3886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fParent = p; 3896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 3906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com do { 3916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // assumptions at loop start. 392f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 393f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == x->fColor); 3946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // can't have a grandparent but no parent. 395f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(!(NULL != gp && NULL == p)); 3966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // make sure pc and gpc are correct 397f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == p || p->fChildren[pc] == x); 398f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == gp || gp->fChildren[gpc] == p); 3996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x's parent is black then we didn't violate any of the 4016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // red/black properties when we added x as red. 4026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kBlack_Color == p->fColor) { 4035aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 4046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // gp must be valid because if p was the root then it is black 406f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != gp); 4076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // gp must be black since it's child, p, is red. 408f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == gp->fColor); 4096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x and its parent are red, violating red-black property. 4126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* u = gp->fChildren[1-gpc]; 4136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x's uncle (p's sibling) is also red then we can flip 4146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p and u to black and make gp red. But then we have to recurse 4156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // up to gp since it's parent may also be red. 4166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != u && kRed_Color == u->fColor) { 4176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 4186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com u->fColor = kBlack_Color; 4196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp->fColor = kRed_Color; 4206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = gp; 4216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x->fParent; 4226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == p) { 4236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x (prev gp) is the root, color it black and be done. 424f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == x); 4256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fColor = kBlack_Color; 4266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 4275aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 4286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp = p->fParent; 4306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child : 4316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 4326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != gp) { 4336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child : 4346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 4356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com continue; 4376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } break; 4386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } while (true); 4396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Here p is red but u is black and we still have to resolve the fact 4406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // that x and p are both red. 441f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc]->fColor); 442f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == x->fColor); 443f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == p->fColor); 444f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == gp->fColor); 4456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // make x be on the same side of p as p is of gp. If it isn't already 4476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the case then rotate x up to p and swap their labels. 4486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (pc != gpc) { 4496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kRight_Child == pc) { 4506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(p); 4516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* temp = p; 4526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x; 4536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = temp; 4546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = kLeft_Child; 4556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 4566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(p); 4576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* temp = p; 4586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x; 4596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = temp; 4606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = kRight_Child; 4616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we now rotate gp down, pulling up p to be it's new parent. 4646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // gp's child, u, that is not affected we know to be black. gp's new 4656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // child is p's previous child (x's pre-rotation sibling) which must be 4666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black since p is red. 467f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == p->fChildren[1-pc] || 4686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kBlack_Color == p->fChildren[1-pc]->fColor); 4696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Since gp's two children are black it can become red if p is made 4706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black. This leaves the black-height of both of p's new subtrees 4716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // preserved and removes the red/red parent child relationship. 4726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 4736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com gp->fColor = kRed_Color; 4746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc) { 4756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(gp); 4766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 4776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(gp); 4786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 4796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 4805aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com return Iter(returnNode, this); 4816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 4826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 4856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::rotateRight(Node* n) { 4866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com /* d? d? 4876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * / / 4886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * n s 4896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * / \ ---> / \ 4906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * s a? c? n 4916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * / \ / \ 4926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com * c? b? b? a? 4936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com */ 4946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* d = n->fParent; 4956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = n->fChildren[kLeft_Child]; 496f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 4976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* b = s->fChildren[kRight_Child]; 4986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 4996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != d) { 5006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child : 5016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 5026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com d->fChildren[c] = s; 5036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 504f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == n); 5056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = s; 5066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fParent = d; 5086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fChildren[kRight_Child] = n; 5096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fParent = s; 5106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fChildren[kLeft_Child] = b; 5116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != b) { 5126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com b->fParent = n; 5136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(d, true)); 5166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s, true)); 5176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n, false)); 5186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true)); 5196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(b, true)); 5206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true)); 5216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::rotateLeft(Node* n) { 5256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* d = n->fParent; 5276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = n->fChildren[kRight_Child]; 528f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 5296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* b = s->fChildren[kLeft_Child]; 5306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != d) { 5326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child c = d->fChildren[kRight_Child] == n ? kRight_Child : 5336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kLeft_Child; 5346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com d->fChildren[c] = s; 5356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 536f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == n); 5376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = s; 5386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fParent = d; 5406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fChildren[kLeft_Child] = n; 5416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fParent = s; 5426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com n->fChildren[kRight_Child] = b; 5436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != b) { 5446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com b->fParent = n; 5456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(d, true)); 5486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s, true)); 5496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n, true)); 5506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true)); 5516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(b, true)); 5526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true)); 5536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) { 557f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 5586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != x->fChildren[kRight_Child]) { 5596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kRight_Child]; 5606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fChildren[kLeft_Child]) { 5616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kLeft_Child]; 5626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x; 5646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) { 5666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fParent; 5676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x->fParent; 5696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtypename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x) { 573f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 5746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != x->fChildren[kLeft_Child]) { 5756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kLeft_Child]; 5766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fChildren[kRight_Child]) { 5776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fChildren[kRight_Child]; 5786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x; 5806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) { 5826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = x->fParent; 5836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 5846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return x->fParent; 5856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 5866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 5886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::deleteAtNode(Node* x) { 589f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != x); 5906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 5916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com --fCount; 5926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool hasLeft = NULL != x->fChildren[kLeft_Child]; 5946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool hasRight = NULL != x->fChildren[kRight_Child]; 5956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child c = hasLeft ? kLeft_Child : kRight_Child; 5966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 5976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (hasLeft && hasRight) { 5986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // first and last can't have two children. 599f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst != x); 600f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fLast != x); 6016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x is an interior node then we find it's successor 6026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // and swap them. 6036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = x->fChildren[kRight_Child]; 6046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != s->fChildren[kLeft_Child]) { 6056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = s->fChildren[kLeft_Child]; 6066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 607f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 6086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // this might be expensive relative to swapping node ptrs around. 6096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // depends on T. 6106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x->fItem = s->fItem; 6116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = s; 6126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c = kRight_Child; 6136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (NULL == x->fParent) { 6146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if x was the root we just replace it with its child and make 6156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the new root (if the tree is not empty) black. 616f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == x); 6176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot = x->fChildren[c]; 6186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != fRoot) { 6196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot->fParent = NULL; 6206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fRoot->fColor = kBlack_Color; 6216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (x == fLast) { 622f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kLeft_Child); 6236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = fRoot; 6246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (x == fFirst) { 625f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kRight_Child); 6266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = fRoot; 6276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 629f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst == fLast && x == fFirst); 6306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = NULL; 6316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = NULL; 632f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == fCount); 6336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 6356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 6366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 6376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Child pc; 6406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* p = x->fParent; 6416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child; 6426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == x->fChildren[c]) { 6446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fLast == x) { 6456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = p; 646f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == PredecessorNode(x)); 6476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (fFirst == x) { 6486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = p; 649f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == SuccessorNode(x)); 6506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x has two implicit black children. 6526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Color xcolor = x->fColor; 6536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fChildren[pc] = NULL; 6546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 6555aaa69e4339e229adfb05e96084a8ec0a590238bbsalomon@google.com x = NULL; 6566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // when x is red it can be with an implicit black leaf without 6576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // violating any of the red-black tree properties. 6586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kRed_Color == xcolor) { 6596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 6606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 6616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 6626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s is p's other child (x's sibling) 6636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* s = p->fChildren[1-pc]; 6646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6656034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //s cannot be an implicit black node because the original 6666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black-height at x was >= 2 and s's black-height must equal the 6676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // initial black height of x. 668f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 669f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 6706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // assigned in loop 6726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* sl; 6736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* sr; 6746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool slRed; 6756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool srRed; 6766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com do { 6786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // When we start this loop x may already be deleted it is/was 6796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p's child on its pc side. x's children are/were black. The 6806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // first time through the loop they are implict children. 6816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // On later passes we will be walking up the tree and they will 6826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // be real nodes. 6836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // The x side of p has a black-height that is one less than the 6846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s side. It must be rebalanced. 685f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 686f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 687f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == x || x->fParent == p); 6886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //sl and sr are s's children, which may be implicit. 6906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl = s->fChildren[kLeft_Child]; 6916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr = s->fChildren[kRight_Child]; 6926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 6936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if the s is red we will rotate s and p, swap their colors so 6946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // that x's new sibling is black 6956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kRed_Color == s->fColor) { 6966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if s is red then it's parent must be black. 697f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == p->fColor); 6986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s's children must also be black since s is red. They can't 6996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // be implicit since s is red and it's black-height is >= 2. 700f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sl && kBlack_Color == sl->fColor); 701f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sr && kBlack_Color == sr->fColor); 7026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kRed_Color; 7036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kBlack_Color; 7046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc) { 7056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(p); 7066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sl; 7076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 7086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(p); 7096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sr; 7106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl = s->fChildren[kLeft_Child]; 7126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr = s->fChildren[kRight_Child]; 7136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x and s are now both black. 715f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == s->fColor); 716f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == x || kBlack_Color == x->fColor); 717f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 718f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == x || p == x->fParent); 7196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 7206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // when x is deleted its subtree will have reduced black-height. 7216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com slRed = (NULL != sl && kRed_Color == sl->fColor); 7226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com srRed = (NULL != sr && kRed_Color == sr->fColor); 7236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!slRed && !srRed) { 7246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if s can be made red that will balance out x's removal 7256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // to make both subtrees of p have the same black-height. 7266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kBlack_Color == p->fColor) { 7276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // now subtree at p has black-height of one less than 7296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p's parent's other child's subtree. We move x up to 7306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p and go through the loop again. At the top of loop 7316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we assumed x and x's children are black, which holds 7326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // by above ifs. 7336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if p is the root there is no other subtree to balance 7346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // against. 7356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com x = p; 7366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p = x->fParent; 7376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL == p) { 738f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fRoot == x); 7396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 7406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 7416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 7426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : 7436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRight_Child; 7446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 7456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = p->fChildren[1-pc]; 747f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != s); 748f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(p == s->fParent); 7496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com continue; 7506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (kRed_Color == p->fColor) { 7516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we can make p black and s red. This balance out p's 7526034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // two subtrees and keep the same black-height as it was 7536034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // before the delete. 7546034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 7566034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 7576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return; 7586034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7596034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7606034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com break; 7616034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } while (true); 7626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // if we made it here one or both of sl and sr is red. 7636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // s and x are black. We make sure that a red child is on 7646034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // the same side of s as s is of p. 765f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(slRed || srRed); 7666034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc && !srRed) { 7676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl->fColor = kBlack_Color; 7696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(s); 7706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr = s; 7716034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sl; 7726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //sl = s->fChildren[kLeft_Child]; don't need this 7736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (kRight_Child == pc && !slRed) { 7746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = kRed_Color; 7756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr->fColor = kBlack_Color; 7766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(s); 7776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl = s; 7786034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s = sr; 7796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com //sr = s->fChildren[kRight_Child]; don't need this 7806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 7816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // now p is either red or black, x and s are red and s's 1-pc 7826034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // child is red. 7836034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // We rotate p towards x, pulling s up to replace p. We make 7846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // p be black and s takes p's old color. 7856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Whether p was red or black, we've increased its pc subtree 7866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // rooted at x by 1 (balancing the imbalance at the start) and 7876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // we've also its subtree rooted at s's black-height by 1. This 7886034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // can be balanced by making s's red child be black. 7896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com s->fColor = p->fColor; 7906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fColor = kBlack_Color; 7916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kLeft_Child == pc) { 792f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sr && kRed_Color == sr->fColor); 7936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sr->fColor = kBlack_Color; 7946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateLeft(p); 7956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 796f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != sl && kRed_Color == sl->fColor); 7976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com sl->fColor = kBlack_Color; 7986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com rotateRight(p); 7996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com else { 8026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // x has exactly one implicit black child. x cannot be red. 8036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // Proof by contradiction: Assume X is red. Let c0 be x's implicit 8046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // child and c1 be its non-implicit child. c1 must be black because 8056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // red nodes always have two black children. Then the two subtrees 8066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // of x rooted at c0 and c1 will have different black-heights. 807f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == x->fColor); 8086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // So we know x is black and has one implicit black child, c0. c1 8096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // must be red, otherwise the subtree at c1 will have a different 8106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // black-height than the subtree rooted at c0. 811f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kRed_Color == x->fChildren[c]->fColor); 8126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // replace x with c1, making c1 black, preserves all red-black tree 8136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com // props. 8146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com Node* c1 = x->fChildren[c]; 8156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (x == fFirst) { 816f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kRight_Child); 8176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = c1; 8186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != fFirst->fChildren[kLeft_Child]) { 8196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fFirst = fFirst->fChildren[kLeft_Child]; 8206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 821f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst == SuccessorNode(x)); 8226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else if (x == fLast) { 823f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(c == kLeft_Child); 8246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = c1; 8256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com while (NULL != fLast->fChildren[kRight_Child]) { 8266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com fLast = fLast->fChildren[kRight_Child]; 8276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 828f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fLast == PredecessorNode(x)); 8296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c1->fParent = p; 8316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com p->fChildren[pc] = c1; 8326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com c1->fColor = kBlack_Color; 8336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 8346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 8356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com validate(); 8376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 8396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { 8416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != x) { 8426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(x->fChildren[kLeft_Child]); 8436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com RecursiveDelete(x->fChildren[kRight_Child]); 8446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com delete x; 8456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 848515dcd36032997ce335daa0163c6d67e851bcad1commit-bot@chromium.org#ifdef SK_DEBUG 8496034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8506034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comvoid GrRedBlackTree<T,C>::validate() const { 8516034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (fCount) { 852f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fRoot->fParent); 853f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != fFirst); 854f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL != fLast); 8556034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 856f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(kBlack_Color == fRoot->fColor); 8576034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (1 == fCount) { 858f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fFirst == fRoot); 859f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(fLast == fRoot); 860f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == fRoot->fChildren[kLeft_Child]); 861f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(0 == fRoot->fChildren[kRight_Child]); 8626034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8636034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } else { 864f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fRoot); 865f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fFirst); 866f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(NULL == fLast); 8676034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8686034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#if DEEP_VALIDATE 8696034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int bh; 8706034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int count = checkNode(fRoot, &bh); 871f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(count == fCount); 8726034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 8736034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8746034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 8756034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8766034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comint GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const { 8776034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n) { 878f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(validateChildRelations(n, false)); 8796034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (kBlack_Color == n->fColor) { 8806034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com *bh += 1; 8816034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 882f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(!fComp(n->fItem, fFirst->fItem)); 883f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(!fComp(fLast->fItem, n->fItem)); 8846034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int leftBh = *bh; 8856034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int rightBh = *bh; 8866034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int cl = checkNode(n->fChildren[kLeft_Child], &leftBh); 8876034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com int cr = checkNode(n->fChildren[kRight_Child], &rightBh); 888f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(leftBh == rightBh); 8896034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com *bh = leftBh; 8906034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return 1 + cl + cr; 8916034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 8926034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return 0; 8936034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 8946034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 8956034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.comtemplate <typename T, typename C> 8966034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.combool GrRedBlackTree<T,C>::validateChildRelations(const Node* n, 8976034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com bool allowRedRed) const { 8986034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n) { 8996034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n->fChildren[kLeft_Child] || 9006034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com NULL != n->fChildren[kRight_Child]) { 9016034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) { 9026034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9036034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9046034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kLeft_Child] == n->fParent && 9056034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com NULL != n->fParent) { 9066034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9076034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9086034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kRight_Child] == n->fParent && 9096034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com NULL != n->fParent) { 9106034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9116034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9126034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n->fChildren[kLeft_Child]) { 9136034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!allowRedRed && 9146034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fChildren[kLeft_Child]->fColor && 9156034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fColor) { 9166034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9176034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9186034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kLeft_Child]->fParent != n) { 9196034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9206034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9216034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) || 9226034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) && 9236034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) { 9246034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9256034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9266034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9276034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (NULL != n->fChildren[kRight_Child]) { 9286034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!allowRedRed && 9296034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fChildren[kRight_Child]->fColor && 9306034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com kRed_Color == n->fColor) { 9316034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9326034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9336034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (n->fChildren[kRight_Child]->fParent != n) { 9346034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9356034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9366034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) || 9376034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) && 9386034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { 9396034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return validateChildRelationsFailed(); 9406034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9416034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9426034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9436034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com } 9446034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com return true; 9456034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com} 9466034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 9476034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com 9486034c506bd94ca01e4aeedfb522b06cb7900a367bsalomon@google.com#endif 949