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