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