src/third_party/skia/src/gpu/GrRedBlackTree.h

   1 /*
   2  * Copyright 2011 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #ifndef GrRedBlackTree_DEFINED
   9 #define GrRedBlackTree_DEFINED
  10
  11 #include "GrConfig.h"
  12 #include "SkTypes.h"
  13
  14 template <typename T>
  15 class GrLess {
  16 public:
  17     bool operator()(const T& a, const T& b) const { return a < b; }
  18 };
  19
  20 template <typename T>
  21 class GrLess<T*> {
  22 public:
  23     bool operator()(const T* a, const T* b) const { return *a < *b; }
  24 };
  25
  26 class GrStrLess {
  27 public:
  28     bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0; }
  29 };
  30
  31 /**
  32  * In debug build this will cause full traversals of the tree when the validate
  33  * is called on insert and remove. Useful for debugging but very slow.
  34  */
  35 #define DEEP_VALIDATE 0
  36
  37 /**
  38  * A sorted tree that uses the red-black tree algorithm. Allows duplicate
  39  * entries. Data is of type T and is compared using functor C. A single C object
  40  * will be created and used for all comparisons.
  41  */
  42 template <typename T, typename C = GrLess<T> >
  43 class GrRedBlackTree : SkNoncopyable {
  44 public:
  45     /**
  46      * Creates an empty tree.
  47      */
  48     GrRedBlackTree();
  49     virtual ~GrRedBlackTree();
  50
  51     /**
  52      * Class used to iterater through the tree. The valid range of the tree
  53      * is given by [begin(), end()). It is legal to dereference begin() but not
  54      * end(). The iterator has preincrement and predecrement operators, it is
  55      * legal to decerement end() if the tree is not empty to get the last
  56      * element. However, a last() helper is provided.
  57      */
  58     class Iter;
  59
  60     /**
  61      * Add an element to the tree. Duplicates are allowed.
  62      * @param t     the item to add.
  63      * @return  an iterator to the item.
  64      */
  65     Iter insert(const T& t);
  66
  67     /**
  68      * Removes all items in the tree.
  69      */
  70     void reset();
  71
  72     /**
  73      * @return true if there are no items in the tree, false otherwise.
  74      */
  75     bool empty() const {return 0 == fCount;}
  76
  77     /**
  78      * @return the number of items in the tree.
  79      */
  80     int  count() const {return fCount;}
  81
  82     /**
  83      * @return  an iterator to the first item in sorted order, or end() if empty
  84      */
  85     Iter begin();
  86     /**
  87      * Gets the last valid iterator. This is always valid, even on an empty.
  88      * However, it can never be dereferenced. Useful as a loop terminator.
  89      * @return  an iterator that is just beyond the last item in sorted order.
  90      */
  91     Iter end();
  92     /**
  93      * @return  an iterator that to the last item in sorted order, or end() if
  94      * empty.
  95      */
  96     Iter last();
  97
  98     /**
  99      * Finds an occurrence of an item.
 100      * @param t     the item to find.
 101      * @return an iterator to a tree element equal to t or end() if none exists.
 102      */
 103     Iter find(const T& t);
 104     /**
 105      * Finds the first of an item in iterator order.
 106      * @param t     the item to find.
 107      * @return  an iterator to the first element equal to t or end() if
 108      *          none exists.
 109      */
 110     Iter findFirst(const T& t);
 111     /**
 112      * Finds the last of an item in iterator order.
 113      * @param t     the item to find.
 114      * @return  an iterator to the last element equal to t or end() if
 115      *          none exists.
 116      */
 117     Iter findLast(const T& t);
 118     /**
 119      * Gets the number of items in the tree equal to t.
 120      * @param t     the item to count.
 121      * @return  number of items equal to t in the tree
 122      */
 123     int countOf(const T& t) const;
 124
 125     /**
 126      * Removes the item indicated by an iterator. The iterator will not be valid
 127      * afterwards.
 128      *
 129      * @param iter      iterator of item to remove. Must be valid (not end()).
 130      */
 131     void remove(const Iter& iter) { deleteAtNode(iter.fN); }
 132
 133 private:
 134     enum Color {
 135         kRed_Color,
 136         kBlack_Color
 137     };
 138
 139     enum Child {
 140         kLeft_Child  = 0,
 141         kRight_Child = 1
 142     };
 143
 144     struct Node {
 145         T       fItem;
 146         Color   fColor;
 147
 148         Node*   fParent;
 149         Node*   fChildren[2];
 150     };
 151
 152     void rotateRight(Node* n);
 153     void rotateLeft(Node* n);
 154
 155     static Node* SuccessorNode(Node* x);
 156     static Node* PredecessorNode(Node* x);
 157
 158     void deleteAtNode(Node* x);
 159     static void RecursiveDelete(Node* x);
 160
 161     int onCountOf(const Node* n, const T& t) const;
 162
 163 #ifdef SK_DEBUG
 164     void validate() const;
 165     int checkNode(Node* n, int* blackHeight) const;
 166     // checks relationship between a node and its children. allowRedRed means
 167     // node may be in an intermediate state where a red parent has a red child.
 168     bool validateChildRelations(const Node* n, bool allowRedRed) const;
 169     // place to stick break point if validateChildRelations is failing.
 170     bool validateChildRelationsFailed() const { return false; }
 171 #else
 172     void validate() const {}
 173 #endif
 174
 175     int     fCount;
 176     Node*   fRoot;
 177     Node*   fFirst;
 178     Node*   fLast;
 179
 180     const C fComp;
 181 };
 182
 183 template <typename T, typename C>
 184 class GrRedBlackTree<T,C>::Iter {
 185 public:
 186     Iter() {};
 187     Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;}
 188     Iter& operator =(const Iter& i) {
 189         fN = i.fN;
 190         fTree = i.fTree;
 191         return *this;
 192     }
 193     // altering the sort value of the item using this method will cause
 194     // errors.
 195     T& operator *() const { return fN->fItem; }
 196     bool operator ==(const Iter& i) const {
 197         return fN == i.fN && fTree == i.fTree;
 198     }
 199     bool operator !=(const Iter& i) const { return !(*this == i); }
 200     Iter& operator ++() {
 201         SkASSERT(*this != fTree->end());
 202         fN = SuccessorNode(fN);
 203         return *this;
 204     }
 205     Iter& operator --() {
 206         SkASSERT(*this != fTree->begin());
 207         if (NULL != fN) {
 208             fN = PredecessorNode(fN);
 209         } else {
 210             *this = fTree->last();
 211         }
 212         return *this;
 213     }
 214
 215 private:
 216     friend class GrRedBlackTree;
 217     explicit Iter(Node* n, GrRedBlackTree* tree) {
 218         fN = n;
 219         fTree = tree;
 220     }
 221     Node* fN;
 222     GrRedBlackTree* fTree;
 223 };
 224
 225 template <typename T, typename C>
 226 GrRedBlackTree<T,C>::GrRedBlackTree() : fComp() {
 227     fRoot = NULL;
 228     fFirst = NULL;
 229     fLast = NULL;
 230     fCount = 0;
 231     validate();
 232 }
 233
 234 template <typename T, typename C>
 235 GrRedBlackTree<T,C>::~GrRedBlackTree() {
 236     RecursiveDelete(fRoot);
 237 }
 238
 239 template <typename T, typename C>
 240 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() {
 241     return Iter(fFirst, this);
 242 }
 243
 244 template <typename T, typename C>
 245 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() {
 246     return Iter(NULL, this);
 247 }
 248
 249 template <typename T, typename C>
 250 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() {
 251     return Iter(fLast, this);
 252 }
 253
 254 template <typename T, typename C>
 255 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) {
 256     Node* n = fRoot;
 257     while (NULL != n) {
 258         if (fComp(t, n->fItem)) {
 259             n = n->fChildren[kLeft_Child];
 260         } else {
 261             if (!fComp(n->fItem, t)) {
 262                 return Iter(n, this);
 263             }
 264             n = n->fChildren[kRight_Child];
 265         }
 266     }
 267     return end();
 268 }
 269
 270 template <typename T, typename C>
 271 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) {
 272     Node* n = fRoot;
 273     Node* leftMost = NULL;
 274     while (NULL != n) {
 275         if (fComp(t, n->fItem)) {
 276             n = n->fChildren[kLeft_Child];
 277         } else {
 278             if (!fComp(n->fItem, t)) {
 279                 // found one. check if another in left subtree.
 280                 leftMost = n;
 281                 n = n->fChildren[kLeft_Child];
 282             } else {
 283                 n = n->fChildren[kRight_Child];
 284             }
 285         }
 286     }
 287     return Iter(leftMost, this);
 288 }
 289
 290 template <typename T, typename C>
 291 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) {
 292     Node* n = fRoot;
 293     Node* rightMost = NULL;
 294     while (NULL != n) {
 295         if (fComp(t, n->fItem)) {
 296             n = n->fChildren[kLeft_Child];
 297         } else {
 298             if (!fComp(n->fItem, t)) {
 299                 // found one. check if another in right subtree.
 300                 rightMost = n;
 301             }
 302             n = n->fChildren[kRight_Child];
 303         }
 304     }
 305     return Iter(rightMost, this);
 306 }
 307
 308 template <typename T, typename C>
 309 int GrRedBlackTree<T,C>::countOf(const T& t) const {
 310     return onCountOf(fRoot, t);
 311 }
 312
 313 template <typename T, typename C>
 314 int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const {
 315     // this is count*log(n) :(
 316     while (NULL != n) {
 317         if (fComp(t, n->fItem)) {
 318             n = n->fChildren[kLeft_Child];
 319         } else {
 320             if (!fComp(n->fItem, t)) {
 321                 int count = 1;
 322                 count += onCountOf(n->fChildren[kLeft_Child], t);
 323                 count += onCountOf(n->fChildren[kRight_Child], t);
 324                 return count;
 325             }
 326             n = n->fChildren[kRight_Child];
 327         }
 328     }
 329     return 0;
 330
 331 }
 332
 333 template <typename T, typename C>
 334 void GrRedBlackTree<T,C>::reset() {
 335     RecursiveDelete(fRoot);
 336     fRoot = NULL;
 337     fFirst = NULL;
 338     fLast = NULL;
 339     fCount = 0;
 340 }
 341
 342 template <typename T, typename C>
 343 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) {
 344     validate();
 345
 346     ++fCount;
 347
 348     Node* x = SkNEW(Node);
 349     x->fChildren[kLeft_Child] = NULL;
 350     x->fChildren[kRight_Child] = NULL;
 351     x->fItem = t;
 352
 353     Node* returnNode = x;
 354
 355     Node* gp = NULL;
 356     Node* p = NULL;
 357     Node* n = fRoot;
 358     Child pc = kLeft_Child; // suppress uninit warning
 359     Child gpc = kLeft_Child;
 360
 361     bool first = true;
 362     bool last = true;
 363     while (NULL != n) {
 364         gpc = pc;
 365         pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child;
 366         first = first && kLeft_Child == pc;
 367         last = last && kRight_Child == pc;
 368         gp = p;
 369         p = n;
 370         n = p->fChildren[pc];
 371     }
 372     if (last) {
 373         fLast = x;
 374     }
 375     if (first) {
 376         fFirst = x;
 377     }
 378
 379     if (NULL == p) {
 380         fRoot = x;
 381         x->fColor = kBlack_Color;
 382         x->fParent = NULL;
 383         SkASSERT(1 == fCount);
 384         return Iter(returnNode, this);
 385     }
 386     p->fChildren[pc] = x;
 387     x->fColor = kRed_Color;
 388     x->fParent = p;
 389
 390     do {
 391         // assumptions at loop start.
 392         SkASSERT(NULL != x);
 393         SkASSERT(kRed_Color == x->fColor);
 394         // can't have a grandparent but no parent.
 395         SkASSERT(!(NULL != gp && NULL == p));
 396         // make sure pc and gpc are correct
 397         SkASSERT(NULL == p  || p->fChildren[pc] == x);
 398         SkASSERT(NULL == gp || gp->fChildren[gpc] == p);
 399
 400         // if x's parent is black then we didn't violate any of the
 401         // red/black properties when we added x as red.
 402         if (kBlack_Color == p->fColor) {
 403             return Iter(returnNode, this);
 404         }
 405         // gp must be valid because if p was the root then it is black
 406         SkASSERT(NULL != gp);
 407         // gp must be black since it's child, p, is red.
 408         SkASSERT(kBlack_Color == gp->fColor);
 409
 410
 411         // x and its parent are red, violating red-black property.
 412         Node* u = gp->fChildren[1-gpc];
 413         // if x's uncle (p's sibling) is also red then we can flip
 414         // p and u to black and make gp red. But then we have to recurse
 415         // up to gp since it's parent may also be red.
 416         if (NULL != u && kRed_Color == u->fColor) {
 417             p->fColor = kBlack_Color;
 418             u->fColor = kBlack_Color;
 419             gp->fColor = kRed_Color;
 420             x = gp;
 421             p = x->fParent;
 422             if (NULL == p) {
 423                 // x (prev gp) is the root, color it black and be done.
 424                 SkASSERT(fRoot == x);
 425                 x->fColor = kBlack_Color;
 426                 validate();
 427                 return Iter(returnNode, this);
 428             }
 429             gp = p->fParent;
 430             pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child :
 431                                                     kRight_Child;
 432             if (NULL != gp) {
 433                 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child :
 434                                                           kRight_Child;
 435             }
 436             continue;
 437         } break;
 438     } while (true);
 439     // Here p is red but u is black and we still have to resolve the fact
 440     // that x and p are both red.
 441     SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc]->fColor);
 442     SkASSERT(kRed_Color == x->fColor);
 443     SkASSERT(kRed_Color == p->fColor);
 444     SkASSERT(kBlack_Color == gp->fColor);
 445
 446     // make x be on the same side of p as p is of gp. If it isn't already
 447     // the case then rotate x up to p and swap their labels.
 448     if (pc != gpc) {
 449         if (kRight_Child == pc) {
 450             rotateLeft(p);
 451             Node* temp = p;
 452             p = x;
 453             x = temp;
 454             pc = kLeft_Child;
 455         } else {
 456             rotateRight(p);
 457             Node* temp = p;
 458             p = x;
 459             x = temp;
 460             pc = kRight_Child;
 461         }
 462     }
 463     // we now rotate gp down, pulling up p to be it's new parent.
 464     // gp's child, u, that is not affected we know to be black. gp's new
 465     // child is p's previous child (x's pre-rotation sibling) which must be
 466     // black since p is red.
 467     SkASSERT(NULL == p->fChildren[1-pc] ||
 468              kBlack_Color == p->fChildren[1-pc]->fColor);
 469     // Since gp's two children are black it can become red if p is made
 470     // black. This leaves the black-height of both of p's new subtrees
 471     // preserved and removes the red/red parent child relationship.
 472     p->fColor = kBlack_Color;
 473     gp->fColor = kRed_Color;
 474     if (kLeft_Child == pc) {
 475         rotateRight(gp);
 476     } else {
 477         rotateLeft(gp);
 478     }
 479     validate();
 480     return Iter(returnNode, this);
 481 }
 482
 483
 484 template <typename T, typename C>
 485 void GrRedBlackTree<T,C>::rotateRight(Node* n) {
 486     /*            d?              d?
 487      *           /               /
 488      *          n               s
 489      *         / \     --->    / \
 490      *        s   a?          c?  n
 491      *       / \                 / \
 492      *      c?  b?              b?  a?
 493      */
 494     Node* d = n->fParent;
 495     Node* s = n->fChildren[kLeft_Child];
 496     SkASSERT(NULL != s);
 497     Node* b = s->fChildren[kRight_Child];
 498
 499     if (NULL != d) {
 500         Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child :
 501                                              kRight_Child;
 502         d->fChildren[c] = s;
 503     } else {
 504         SkASSERT(fRoot == n);
 505         fRoot = s;
 506     }
 507     s->fParent = d;
 508     s->fChildren[kRight_Child] = n;
 509     n->fParent = s;
 510     n->fChildren[kLeft_Child] = b;
 511     if (NULL != b) {
 512         b->fParent = n;
 513     }
 514
 515     GR_DEBUGASSERT(validateChildRelations(d, true));
 516     GR_DEBUGASSERT(validateChildRelations(s, true));
 517     GR_DEBUGASSERT(validateChildRelations(n, false));
 518     GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true));
 519     GR_DEBUGASSERT(validateChildRelations(b, true));
 520     GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true));
 521 }
 522
 523 template <typename T, typename C>
 524 void GrRedBlackTree<T,C>::rotateLeft(Node* n) {
 525
 526     Node* d = n->fParent;
 527     Node* s = n->fChildren[kRight_Child];
 528     SkASSERT(NULL != s);
 529     Node* b = s->fChildren[kLeft_Child];
 530
 531     if (NULL != d) {
 532         Child c = d->fChildren[kRight_Child] == n ? kRight_Child :
 533                                                    kLeft_Child;
 534         d->fChildren[c] = s;
 535     } else {
 536         SkASSERT(fRoot == n);
 537         fRoot = s;
 538     }
 539     s->fParent = d;
 540     s->fChildren[kLeft_Child] = n;
 541     n->fParent = s;
 542     n->fChildren[kRight_Child] = b;
 543     if (NULL != b) {
 544         b->fParent = n;
 545     }
 546
 547     GR_DEBUGASSERT(validateChildRelations(d, true));
 548     GR_DEBUGASSERT(validateChildRelations(s, true));
 549     GR_DEBUGASSERT(validateChildRelations(n, true));
 550     GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true));
 551     GR_DEBUGASSERT(validateChildRelations(b, true));
 552     GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true));
 553 }
 554
 555 template <typename T, typename C>
 556 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) {
 557     SkASSERT(NULL != x);
 558     if (NULL != x->fChildren[kRight_Child]) {
 559         x = x->fChildren[kRight_Child];
 560         while (NULL != x->fChildren[kLeft_Child]) {
 561             x = x->fChildren[kLeft_Child];
 562         }
 563         return x;
 564     }
 565     while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) {
 566         x = x->fParent;
 567     }
 568     return x->fParent;
 569 }
 570
 571 template <typename T, typename C>
 572 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x) {
 573     SkASSERT(NULL != x);
 574     if (NULL != x->fChildren[kLeft_Child]) {
 575         x = x->fChildren[kLeft_Child];
 576         while (NULL != x->fChildren[kRight_Child]) {
 577             x = x->fChildren[kRight_Child];
 578         }
 579         return x;
 580     }
 581     while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) {
 582         x = x->fParent;
 583     }
 584     return x->fParent;
 585 }
 586
 587 template <typename T, typename C>
 588 void GrRedBlackTree<T,C>::deleteAtNode(Node* x) {
 589     SkASSERT(NULL != x);
 590     validate();
 591     --fCount;
 592
 593     bool hasLeft =  NULL != x->fChildren[kLeft_Child];
 594     bool hasRight = NULL != x->fChildren[kRight_Child];
 595     Child c = hasLeft ? kLeft_Child : kRight_Child;
 596
 597     if (hasLeft && hasRight) {
 598         // first and last can't have two children.
 599         SkASSERT(fFirst != x);
 600         SkASSERT(fLast != x);
 601         // if x is an interior node then we find it's successor
 602         // and swap them.
 603         Node* s = x->fChildren[kRight_Child];
 604         while (NULL != s->fChildren[kLeft_Child]) {
 605             s = s->fChildren[kLeft_Child];
 606         }
 607         SkASSERT(NULL != s);
 608         // this might be expensive relative to swapping node ptrs around.
 609         // depends on T.
 610         x->fItem = s->fItem;
 611         x = s;
 612         c = kRight_Child;
 613     } else if (NULL == x->fParent) {
 614         // if x was the root we just replace it with its child and make
 615         // the new root (if the tree is not empty) black.
 616         SkASSERT(fRoot == x);
 617         fRoot = x->fChildren[c];
 618         if (NULL != fRoot) {
 619             fRoot->fParent = NULL;
 620             fRoot->fColor = kBlack_Color;
 621             if (x == fLast) {
 622                 SkASSERT(c == kLeft_Child);
 623                 fLast = fRoot;
 624             } else if (x == fFirst) {
 625                 SkASSERT(c == kRight_Child);
 626                 fFirst = fRoot;
 627             }
 628         } else {
 629             SkASSERT(fFirst == fLast && x == fFirst);
 630             fFirst = NULL;
 631             fLast = NULL;
 632             SkASSERT(0 == fCount);
 633         }
 634         delete x;
 635         validate();
 636         return;
 637     }
 638
 639     Child pc;
 640     Node* p = x->fParent;
 641     pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child;
 642
 643     if (NULL == x->fChildren[c]) {
 644         if (fLast == x) {
 645             fLast = p;
 646             SkASSERT(p == PredecessorNode(x));
 647         } else if (fFirst == x) {
 648             fFirst = p;
 649             SkASSERT(p == SuccessorNode(x));
 650         }
 651         // x has two implicit black children.
 652         Color xcolor = x->fColor;
 653         p->fChildren[pc] = NULL;
 654         delete x;
 655         x = NULL;
 656         // when x is red it can be with an implicit black leaf without
 657         // violating any of the red-black tree properties.
 658         if (kRed_Color == xcolor) {
 659             validate();
 660             return;
 661         }
 662         // s is p's other child (x's sibling)
 663         Node* s = p->fChildren[1-pc];
 664
 665         //s cannot be an implicit black node because the original
 666         // black-height at x was >= 2 and s's black-height must equal the
 667         // initial black height of x.
 668         SkASSERT(NULL != s);
 669         SkASSERT(p == s->fParent);
 670
 671         // assigned in loop
 672         Node* sl;
 673         Node* sr;
 674         bool slRed;
 675         bool srRed;
 676
 677         do {
 678             // When we start this loop x may already be deleted it is/was
 679             // p's child on its pc side. x's children are/were black. The
 680             // first time through the loop they are implict children.
 681             // On later passes we will be walking up the tree and they will
 682             // be real nodes.
 683             // The x side of p has a black-height that is one less than the
 684             // s side. It must be rebalanced.
 685             SkASSERT(NULL != s);
 686             SkASSERT(p == s->fParent);
 687             SkASSERT(NULL == x || x->fParent == p);
 688
 689             //sl and sr are s's children, which may be implicit.
 690             sl = s->fChildren[kLeft_Child];
 691             sr = s->fChildren[kRight_Child];
 692
 693             // if the s is red we will rotate s and p, swap their colors so
 694             // that x's new sibling is black
 695             if (kRed_Color == s->fColor) {
 696                 // if s is red then it's parent must be black.
 697                 SkASSERT(kBlack_Color == p->fColor);
 698                 // s's children must also be black since s is red. They can't
 699                 // be implicit since s is red and it's black-height is >= 2.
 700                 SkASSERT(NULL != sl && kBlack_Color == sl->fColor);
 701                 SkASSERT(NULL != sr && kBlack_Color == sr->fColor);
 702                 p->fColor = kRed_Color;
 703                 s->fColor = kBlack_Color;
 704                 if (kLeft_Child == pc) {
 705                     rotateLeft(p);
 706                     s = sl;
 707                 } else {
 708                     rotateRight(p);
 709                     s = sr;
 710                 }
 711                 sl = s->fChildren[kLeft_Child];
 712                 sr = s->fChildren[kRight_Child];
 713             }
 714             // x and s are now both black.
 715             SkASSERT(kBlack_Color == s->fColor);
 716             SkASSERT(NULL == x || kBlack_Color == x->fColor);
 717             SkASSERT(p == s->fParent);
 718             SkASSERT(NULL == x || p == x->fParent);
 719
 720             // when x is deleted its subtree will have reduced black-height.
 721             slRed = (NULL != sl && kRed_Color == sl->fColor);
 722             srRed = (NULL != sr && kRed_Color == sr->fColor);
 723             if (!slRed && !srRed) {
 724                 // if s can be made red that will balance out x's removal
 725                 // to make both subtrees of p have the same black-height.
 726                 if (kBlack_Color == p->fColor) {
 727                     s->fColor = kRed_Color;
 728                     // now subtree at p has black-height of one less than
 729                     // p's parent's other child's subtree. We move x up to
 730                     // p and go through the loop again. At the top of loop
 731                     // we assumed x and x's children are black, which holds
 732                     // by above ifs.
 733                     // if p is the root there is no other subtree to balance
 734                     // against.
 735                     x = p;
 736                     p = x->fParent;
 737                     if (NULL == p) {
 738                         SkASSERT(fRoot == x);
 739                         validate();
 740                         return;
 741                     } else {
 742                         pc = p->fChildren[kLeft_Child] == x ? kLeft_Child :
 743                                                               kRight_Child;
 744
 745                     }
 746                     s = p->fChildren[1-pc];
 747                     SkASSERT(NULL != s);
 748                     SkASSERT(p == s->fParent);
 749                     continue;
 750                 } else if (kRed_Color == p->fColor) {
 751                     // we can make p black and s red. This balance out p's
 752                     // two subtrees and keep the same black-height as it was
 753                     // before the delete.
 754                     s->fColor = kRed_Color;
 755                     p->fColor = kBlack_Color;
 756                     validate();
 757                     return;
 758                 }
 759             }
 760             break;
 761         } while (true);
 762         // if we made it here one or both of sl and sr is red.
 763         // s and x are black. We make sure that a red child is on
 764         // the same side of s as s is of p.
 765         SkASSERT(slRed || srRed);
 766         if (kLeft_Child == pc && !srRed) {
 767             s->fColor = kRed_Color;
 768             sl->fColor = kBlack_Color;
 769             rotateRight(s);
 770             sr = s;
 771             s = sl;
 772             //sl = s->fChildren[kLeft_Child]; don't need this
 773         } else if (kRight_Child == pc && !slRed) {
 774             s->fColor = kRed_Color;
 775             sr->fColor = kBlack_Color;
 776             rotateLeft(s);
 777             sl = s;
 778             s = sr;
 779             //sr = s->fChildren[kRight_Child]; don't need this
 780         }
 781         // now p is either red or black, x and s are red and s's 1-pc
 782         // child is red.
 783         // We rotate p towards x, pulling s up to replace p. We make
 784         // p be black and s takes p's old color.
 785         // Whether p was red or black, we've increased its pc subtree
 786         // rooted at x by 1 (balancing the imbalance at the start) and
 787         // we've also its subtree rooted at s's black-height by 1. This
 788         // can be balanced by making s's red child be black.
 789         s->fColor = p->fColor;
 790         p->fColor = kBlack_Color;
 791         if (kLeft_Child == pc) {
 792             SkASSERT(NULL != sr && kRed_Color == sr->fColor);
 793             sr->fColor = kBlack_Color;
 794             rotateLeft(p);
 795         } else {
 796             SkASSERT(NULL != sl && kRed_Color == sl->fColor);
 797             sl->fColor = kBlack_Color;
 798             rotateRight(p);
 799         }
 800     }
 801     else {
 802         // x has exactly one implicit black child. x cannot be red.
 803         // Proof by contradiction: Assume X is red. Let c0 be x's implicit
 804         // child and c1 be its non-implicit child. c1 must be black because
 805         // red nodes always have two black children. Then the two subtrees
 806         // of x rooted at c0 and c1 will have different black-heights.
 807         SkASSERT(kBlack_Color == x->fColor);
 808         // So we know x is black and has one implicit black child, c0. c1
 809         // must be red, otherwise the subtree at c1 will have a different
 810         // black-height than the subtree rooted at c0.
 811         SkASSERT(kRed_Color == x->fChildren[c]->fColor);
 812         // replace x with c1, making c1 black, preserves all red-black tree
 813         // props.
 814         Node* c1 = x->fChildren[c];
 815         if (x == fFirst) {
 816             SkASSERT(c == kRight_Child);
 817             fFirst = c1;
 818             while (NULL != fFirst->fChildren[kLeft_Child]) {
 819                 fFirst = fFirst->fChildren[kLeft_Child];
 820             }
 821             SkASSERT(fFirst == SuccessorNode(x));
 822         } else if (x == fLast) {
 823             SkASSERT(c == kLeft_Child);
 824             fLast = c1;
 825             while (NULL != fLast->fChildren[kRight_Child]) {
 826                 fLast = fLast->fChildren[kRight_Child];
 827             }
 828             SkASSERT(fLast == PredecessorNode(x));
 829         }
 830         c1->fParent = p;
 831         p->fChildren[pc] = c1;
 832         c1->fColor = kBlack_Color;
 833         delete x;
 834         validate();
 835     }
 836     validate();
 837 }
 838
 839 template <typename T, typename C>
 840 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) {
 841     if (NULL != x) {
 842         RecursiveDelete(x->fChildren[kLeft_Child]);
 843         RecursiveDelete(x->fChildren[kRight_Child]);
 844         delete x;
 845     }
 846 }
 847
 848 #ifdef SK_DEBUG
 849 template <typename T, typename C>
 850 void GrRedBlackTree<T,C>::validate() const {
 851     if (fCount) {
 852         SkASSERT(NULL == fRoot->fParent);
 853         SkASSERT(NULL != fFirst);
 854         SkASSERT(NULL != fLast);
 855
 856         SkASSERT(kBlack_Color == fRoot->fColor);
 857         if (1 == fCount) {
 858             SkASSERT(fFirst == fRoot);
 859             SkASSERT(fLast == fRoot);
 860             SkASSERT(0 == fRoot->fChildren[kLeft_Child]);
 861             SkASSERT(0 == fRoot->fChildren[kRight_Child]);
 862         }
 863     } else {
 864         SkASSERT(NULL == fRoot);
 865         SkASSERT(NULL == fFirst);
 866         SkASSERT(NULL == fLast);
 867     }
 868 #if DEEP_VALIDATE
 869     int bh;
 870     int count = checkNode(fRoot, &bh);
 871     SkASSERT(count == fCount);
 872 #endif
 873 }
 874
 875 template <typename T, typename C>
 876 int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const {
 877     if (NULL != n) {
 878         SkASSERT(validateChildRelations(n, false));
 879         if (kBlack_Color == n->fColor) {
 880             *bh += 1;
 881         }
 882         SkASSERT(!fComp(n->fItem, fFirst->fItem));
 883         SkASSERT(!fComp(fLast->fItem, n->fItem));
 884         int leftBh = *bh;
 885         int rightBh = *bh;
 886         int cl = checkNode(n->fChildren[kLeft_Child], &leftBh);
 887         int cr = checkNode(n->fChildren[kRight_Child], &rightBh);
 888         SkASSERT(leftBh == rightBh);
 889         *bh = leftBh;
 890         return 1 + cl + cr;
 891     }
 892     return 0;
 893 }
 894
 895 template <typename T, typename C>
 896 bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,
 897                                                  bool allowRedRed) const {
 898     if (NULL != n) {
 899         if (NULL != n->fChildren[kLeft_Child] ||
 900             NULL != n->fChildren[kRight_Child]) {
 901             if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) {
 902                 return validateChildRelationsFailed();
 903             }
 904             if (n->fChildren[kLeft_Child] == n->fParent &&
 905                 NULL != n->fParent) {
 906                 return validateChildRelationsFailed();
 907             }
 908             if (n->fChildren[kRight_Child] == n->fParent &&
 909                 NULL != n->fParent) {
 910                 return validateChildRelationsFailed();
 911             }
 912             if (NULL != n->fChildren[kLeft_Child]) {
 913                 if (!allowRedRed &&
 914                     kRed_Color == n->fChildren[kLeft_Child]->fColor &&
 915                     kRed_Color == n->fColor) {
 916                     return validateChildRelationsFailed();
 917                 }
 918                 if (n->fChildren[kLeft_Child]->fParent != n) {
 919                     return validateChildRelationsFailed();
 920                 }
 921                 if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) ||
 922                       (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) &&
 923                        !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) {
 924                     return validateChildRelationsFailed();
 925                 }
 926             }
 927             if (NULL != n->fChildren[kRight_Child]) {
 928                 if (!allowRedRed &&
 929                     kRed_Color == n->fChildren[kRight_Child]->fColor &&
 930                     kRed_Color == n->fColor) {
 931                     return validateChildRelationsFailed();
 932                 }
 933                 if (n->fChildren[kRight_Child]->fParent != n) {
 934                     return validateChildRelationsFailed();
 935                 }
 936                 if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) ||
 937                       (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) &&
 938                        !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) {
 939                     return validateChildRelationsFailed();
 940                 }
 941             }
 942         }
 943     }
 944     return true;
 945 }
 946 #endif
 947
 948 #endif