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