1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrRedBlackTree.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,948 @@
1.4 +/*
1.5 + * Copyright 2011 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef GrRedBlackTree_DEFINED
1.12 +#define GrRedBlackTree_DEFINED
1.13 +
1.14 +#include "GrConfig.h"
1.15 +#include "SkTypes.h"
1.16 +
1.17 +template <typename T>
1.18 +class GrLess {
1.19 +public:
1.20 + bool operator()(const T& a, const T& b) const { return a < b; }
1.21 +};
1.22 +
1.23 +template <typename T>
1.24 +class GrLess<T*> {
1.25 +public:
1.26 + bool operator()(const T* a, const T* b) const { return *a < *b; }
1.27 +};
1.28 +
1.29 +class GrStrLess {
1.30 +public:
1.31 + bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0; }
1.32 +};
1.33 +
1.34 +/**
1.35 + * In debug build this will cause full traversals of the tree when the validate
1.36 + * is called on insert and remove. Useful for debugging but very slow.
1.37 + */
1.38 +#define DEEP_VALIDATE 0
1.39 +
1.40 +/**
1.41 + * A sorted tree that uses the red-black tree algorithm. Allows duplicate
1.42 + * entries. Data is of type T and is compared using functor C. A single C object
1.43 + * will be created and used for all comparisons.
1.44 + */
1.45 +template <typename T, typename C = GrLess<T> >
1.46 +class GrRedBlackTree : public SkNoncopyable {
1.47 +public:
1.48 + /**
1.49 + * Creates an empty tree.
1.50 + */
1.51 + GrRedBlackTree();
1.52 + virtual ~GrRedBlackTree();
1.53 +
1.54 + /**
1.55 + * Class used to iterater through the tree. The valid range of the tree
1.56 + * is given by [begin(), end()). It is legal to dereference begin() but not
1.57 + * end(). The iterator has preincrement and predecrement operators, it is
1.58 + * legal to decerement end() if the tree is not empty to get the last
1.59 + * element. However, a last() helper is provided.
1.60 + */
1.61 + class Iter;
1.62 +
1.63 + /**
1.64 + * Add an element to the tree. Duplicates are allowed.
1.65 + * @param t the item to add.
1.66 + * @return an iterator to the item.
1.67 + */
1.68 + Iter insert(const T& t);
1.69 +
1.70 + /**
1.71 + * Removes all items in the tree.
1.72 + */
1.73 + void reset();
1.74 +
1.75 + /**
1.76 + * @return true if there are no items in the tree, false otherwise.
1.77 + */
1.78 + bool empty() const {return 0 == fCount;}
1.79 +
1.80 + /**
1.81 + * @return the number of items in the tree.
1.82 + */
1.83 + int count() const {return fCount;}
1.84 +
1.85 + /**
1.86 + * @return an iterator to the first item in sorted order, or end() if empty
1.87 + */
1.88 + Iter begin();
1.89 + /**
1.90 + * Gets the last valid iterator. This is always valid, even on an empty.
1.91 + * However, it can never be dereferenced. Useful as a loop terminator.
1.92 + * @return an iterator that is just beyond the last item in sorted order.
1.93 + */
1.94 + Iter end();
1.95 + /**
1.96 + * @return an iterator that to the last item in sorted order, or end() if
1.97 + * empty.
1.98 + */
1.99 + Iter last();
1.100 +
1.101 + /**
1.102 + * Finds an occurrence of an item.
1.103 + * @param t the item to find.
1.104 + * @return an iterator to a tree element equal to t or end() if none exists.
1.105 + */
1.106 + Iter find(const T& t);
1.107 + /**
1.108 + * Finds the first of an item in iterator order.
1.109 + * @param t the item to find.
1.110 + * @return an iterator to the first element equal to t or end() if
1.111 + * none exists.
1.112 + */
1.113 + Iter findFirst(const T& t);
1.114 + /**
1.115 + * Finds the last of an item in iterator order.
1.116 + * @param t the item to find.
1.117 + * @return an iterator to the last element equal to t or end() if
1.118 + * none exists.
1.119 + */
1.120 + Iter findLast(const T& t);
1.121 + /**
1.122 + * Gets the number of items in the tree equal to t.
1.123 + * @param t the item to count.
1.124 + * @return number of items equal to t in the tree
1.125 + */
1.126 + int countOf(const T& t) const;
1.127 +
1.128 + /**
1.129 + * Removes the item indicated by an iterator. The iterator will not be valid
1.130 + * afterwards.
1.131 + *
1.132 + * @param iter iterator of item to remove. Must be valid (not end()).
1.133 + */
1.134 + void remove(const Iter& iter) { deleteAtNode(iter.fN); }
1.135 +
1.136 +private:
1.137 + enum Color {
1.138 + kRed_Color,
1.139 + kBlack_Color
1.140 + };
1.141 +
1.142 + enum Child {
1.143 + kLeft_Child = 0,
1.144 + kRight_Child = 1
1.145 + };
1.146 +
1.147 + struct Node {
1.148 + T fItem;
1.149 + Color fColor;
1.150 +
1.151 + Node* fParent;
1.152 + Node* fChildren[2];
1.153 + };
1.154 +
1.155 + void rotateRight(Node* n);
1.156 + void rotateLeft(Node* n);
1.157 +
1.158 + static Node* SuccessorNode(Node* x);
1.159 + static Node* PredecessorNode(Node* x);
1.160 +
1.161 + void deleteAtNode(Node* x);
1.162 + static void RecursiveDelete(Node* x);
1.163 +
1.164 + int onCountOf(const Node* n, const T& t) const;
1.165 +
1.166 +#ifdef SK_DEBUG
1.167 + void validate() const;
1.168 + int checkNode(Node* n, int* blackHeight) const;
1.169 + // checks relationship between a node and its children. allowRedRed means
1.170 + // node may be in an intermediate state where a red parent has a red child.
1.171 + bool validateChildRelations(const Node* n, bool allowRedRed) const;
1.172 + // place to stick break point if validateChildRelations is failing.
1.173 + bool validateChildRelationsFailed() const { return false; }
1.174 +#else
1.175 + void validate() const {}
1.176 +#endif
1.177 +
1.178 + int fCount;
1.179 + Node* fRoot;
1.180 + Node* fFirst;
1.181 + Node* fLast;
1.182 +
1.183 + const C fComp;
1.184 +};
1.185 +
1.186 +template <typename T, typename C>
1.187 +class GrRedBlackTree<T,C>::Iter {
1.188 +public:
1.189 + Iter() {};
1.190 + Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;}
1.191 + Iter& operator =(const Iter& i) {
1.192 + fN = i.fN;
1.193 + fTree = i.fTree;
1.194 + return *this;
1.195 + }
1.196 + // altering the sort value of the item using this method will cause
1.197 + // errors.
1.198 + T& operator *() const { return fN->fItem; }
1.199 + bool operator ==(const Iter& i) const {
1.200 + return fN == i.fN && fTree == i.fTree;
1.201 + }
1.202 + bool operator !=(const Iter& i) const { return !(*this == i); }
1.203 + Iter& operator ++() {
1.204 + SkASSERT(*this != fTree->end());
1.205 + fN = SuccessorNode(fN);
1.206 + return *this;
1.207 + }
1.208 + Iter& operator --() {
1.209 + SkASSERT(*this != fTree->begin());
1.210 + if (NULL != fN) {
1.211 + fN = PredecessorNode(fN);
1.212 + } else {
1.213 + *this = fTree->last();
1.214 + }
1.215 + return *this;
1.216 + }
1.217 +
1.218 +private:
1.219 + friend class GrRedBlackTree;
1.220 + explicit Iter(Node* n, GrRedBlackTree* tree) {
1.221 + fN = n;
1.222 + fTree = tree;
1.223 + }
1.224 + Node* fN;
1.225 + GrRedBlackTree* fTree;
1.226 +};
1.227 +
1.228 +template <typename T, typename C>
1.229 +GrRedBlackTree<T,C>::GrRedBlackTree() : fComp() {
1.230 + fRoot = NULL;
1.231 + fFirst = NULL;
1.232 + fLast = NULL;
1.233 + fCount = 0;
1.234 + validate();
1.235 +}
1.236 +
1.237 +template <typename T, typename C>
1.238 +GrRedBlackTree<T,C>::~GrRedBlackTree() {
1.239 + RecursiveDelete(fRoot);
1.240 +}
1.241 +
1.242 +template <typename T, typename C>
1.243 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() {
1.244 + return Iter(fFirst, this);
1.245 +}
1.246 +
1.247 +template <typename T, typename C>
1.248 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() {
1.249 + return Iter(NULL, this);
1.250 +}
1.251 +
1.252 +template <typename T, typename C>
1.253 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() {
1.254 + return Iter(fLast, this);
1.255 +}
1.256 +
1.257 +template <typename T, typename C>
1.258 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) {
1.259 + Node* n = fRoot;
1.260 + while (NULL != n) {
1.261 + if (fComp(t, n->fItem)) {
1.262 + n = n->fChildren[kLeft_Child];
1.263 + } else {
1.264 + if (!fComp(n->fItem, t)) {
1.265 + return Iter(n, this);
1.266 + }
1.267 + n = n->fChildren[kRight_Child];
1.268 + }
1.269 + }
1.270 + return end();
1.271 +}
1.272 +
1.273 +template <typename T, typename C>
1.274 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) {
1.275 + Node* n = fRoot;
1.276 + Node* leftMost = NULL;
1.277 + while (NULL != n) {
1.278 + if (fComp(t, n->fItem)) {
1.279 + n = n->fChildren[kLeft_Child];
1.280 + } else {
1.281 + if (!fComp(n->fItem, t)) {
1.282 + // found one. check if another in left subtree.
1.283 + leftMost = n;
1.284 + n = n->fChildren[kLeft_Child];
1.285 + } else {
1.286 + n = n->fChildren[kRight_Child];
1.287 + }
1.288 + }
1.289 + }
1.290 + return Iter(leftMost, this);
1.291 +}
1.292 +
1.293 +template <typename T, typename C>
1.294 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) {
1.295 + Node* n = fRoot;
1.296 + Node* rightMost = NULL;
1.297 + while (NULL != n) {
1.298 + if (fComp(t, n->fItem)) {
1.299 + n = n->fChildren[kLeft_Child];
1.300 + } else {
1.301 + if (!fComp(n->fItem, t)) {
1.302 + // found one. check if another in right subtree.
1.303 + rightMost = n;
1.304 + }
1.305 + n = n->fChildren[kRight_Child];
1.306 + }
1.307 + }
1.308 + return Iter(rightMost, this);
1.309 +}
1.310 +
1.311 +template <typename T, typename C>
1.312 +int GrRedBlackTree<T,C>::countOf(const T& t) const {
1.313 + return onCountOf(fRoot, t);
1.314 +}
1.315 +
1.316 +template <typename T, typename C>
1.317 +int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const {
1.318 + // this is count*log(n) :(
1.319 + while (NULL != n) {
1.320 + if (fComp(t, n->fItem)) {
1.321 + n = n->fChildren[kLeft_Child];
1.322 + } else {
1.323 + if (!fComp(n->fItem, t)) {
1.324 + int count = 1;
1.325 + count += onCountOf(n->fChildren[kLeft_Child], t);
1.326 + count += onCountOf(n->fChildren[kRight_Child], t);
1.327 + return count;
1.328 + }
1.329 + n = n->fChildren[kRight_Child];
1.330 + }
1.331 + }
1.332 + return 0;
1.333 +
1.334 +}
1.335 +
1.336 +template <typename T, typename C>
1.337 +void GrRedBlackTree<T,C>::reset() {
1.338 + RecursiveDelete(fRoot);
1.339 + fRoot = NULL;
1.340 + fFirst = NULL;
1.341 + fLast = NULL;
1.342 + fCount = 0;
1.343 +}
1.344 +
1.345 +template <typename T, typename C>
1.346 +typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) {
1.347 + validate();
1.348 +
1.349 + ++fCount;
1.350 +
1.351 + Node* x = SkNEW(Node);
1.352 + x->fChildren[kLeft_Child] = NULL;
1.353 + x->fChildren[kRight_Child] = NULL;
1.354 + x->fItem = t;
1.355 +
1.356 + Node* returnNode = x;
1.357 +
1.358 + Node* gp = NULL;
1.359 + Node* p = NULL;
1.360 + Node* n = fRoot;
1.361 + Child pc = kLeft_Child; // suppress uninit warning
1.362 + Child gpc = kLeft_Child;
1.363 +
1.364 + bool first = true;
1.365 + bool last = true;
1.366 + while (NULL != n) {
1.367 + gpc = pc;
1.368 + pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child;
1.369 + first = first && kLeft_Child == pc;
1.370 + last = last && kRight_Child == pc;
1.371 + gp = p;
1.372 + p = n;
1.373 + n = p->fChildren[pc];
1.374 + }
1.375 + if (last) {
1.376 + fLast = x;
1.377 + }
1.378 + if (first) {
1.379 + fFirst = x;
1.380 + }
1.381 +
1.382 + if (NULL == p) {
1.383 + fRoot = x;
1.384 + x->fColor = kBlack_Color;
1.385 + x->fParent = NULL;
1.386 + SkASSERT(1 == fCount);
1.387 + return Iter(returnNode, this);
1.388 + }
1.389 + p->fChildren[pc] = x;
1.390 + x->fColor = kRed_Color;
1.391 + x->fParent = p;
1.392 +
1.393 + do {
1.394 + // assumptions at loop start.
1.395 + SkASSERT(NULL != x);
1.396 + SkASSERT(kRed_Color == x->fColor);
1.397 + // can't have a grandparent but no parent.
1.398 + SkASSERT(!(NULL != gp && NULL == p));
1.399 + // make sure pc and gpc are correct
1.400 + SkASSERT(NULL == p || p->fChildren[pc] == x);
1.401 + SkASSERT(NULL == gp || gp->fChildren[gpc] == p);
1.402 +
1.403 + // if x's parent is black then we didn't violate any of the
1.404 + // red/black properties when we added x as red.
1.405 + if (kBlack_Color == p->fColor) {
1.406 + return Iter(returnNode, this);
1.407 + }
1.408 + // gp must be valid because if p was the root then it is black
1.409 + SkASSERT(NULL != gp);
1.410 + // gp must be black since it's child, p, is red.
1.411 + SkASSERT(kBlack_Color == gp->fColor);
1.412 +
1.413 +
1.414 + // x and its parent are red, violating red-black property.
1.415 + Node* u = gp->fChildren[1-gpc];
1.416 + // if x's uncle (p's sibling) is also red then we can flip
1.417 + // p and u to black and make gp red. But then we have to recurse
1.418 + // up to gp since it's parent may also be red.
1.419 + if (NULL != u && kRed_Color == u->fColor) {
1.420 + p->fColor = kBlack_Color;
1.421 + u->fColor = kBlack_Color;
1.422 + gp->fColor = kRed_Color;
1.423 + x = gp;
1.424 + p = x->fParent;
1.425 + if (NULL == p) {
1.426 + // x (prev gp) is the root, color it black and be done.
1.427 + SkASSERT(fRoot == x);
1.428 + x->fColor = kBlack_Color;
1.429 + validate();
1.430 + return Iter(returnNode, this);
1.431 + }
1.432 + gp = p->fParent;
1.433 + pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child :
1.434 + kRight_Child;
1.435 + if (NULL != gp) {
1.436 + gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child :
1.437 + kRight_Child;
1.438 + }
1.439 + continue;
1.440 + } break;
1.441 + } while (true);
1.442 + // Here p is red but u is black and we still have to resolve the fact
1.443 + // that x and p are both red.
1.444 + SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc]->fColor);
1.445 + SkASSERT(kRed_Color == x->fColor);
1.446 + SkASSERT(kRed_Color == p->fColor);
1.447 + SkASSERT(kBlack_Color == gp->fColor);
1.448 +
1.449 + // make x be on the same side of p as p is of gp. If it isn't already
1.450 + // the case then rotate x up to p and swap their labels.
1.451 + if (pc != gpc) {
1.452 + if (kRight_Child == pc) {
1.453 + rotateLeft(p);
1.454 + Node* temp = p;
1.455 + p = x;
1.456 + x = temp;
1.457 + pc = kLeft_Child;
1.458 + } else {
1.459 + rotateRight(p);
1.460 + Node* temp = p;
1.461 + p = x;
1.462 + x = temp;
1.463 + pc = kRight_Child;
1.464 + }
1.465 + }
1.466 + // we now rotate gp down, pulling up p to be it's new parent.
1.467 + // gp's child, u, that is not affected we know to be black. gp's new
1.468 + // child is p's previous child (x's pre-rotation sibling) which must be
1.469 + // black since p is red.
1.470 + SkASSERT(NULL == p->fChildren[1-pc] ||
1.471 + kBlack_Color == p->fChildren[1-pc]->fColor);
1.472 + // Since gp's two children are black it can become red if p is made
1.473 + // black. This leaves the black-height of both of p's new subtrees
1.474 + // preserved and removes the red/red parent child relationship.
1.475 + p->fColor = kBlack_Color;
1.476 + gp->fColor = kRed_Color;
1.477 + if (kLeft_Child == pc) {
1.478 + rotateRight(gp);
1.479 + } else {
1.480 + rotateLeft(gp);
1.481 + }
1.482 + validate();
1.483 + return Iter(returnNode, this);
1.484 +}
1.485 +
1.486 +
1.487 +template <typename T, typename C>
1.488 +void GrRedBlackTree<T,C>::rotateRight(Node* n) {
1.489 + /* d? d?
1.490 + * / /
1.491 + * n s
1.492 + * / \ ---> / \
1.493 + * s a? c? n
1.494 + * / \ / \
1.495 + * c? b? b? a?
1.496 + */
1.497 + Node* d = n->fParent;
1.498 + Node* s = n->fChildren[kLeft_Child];
1.499 + SkASSERT(NULL != s);
1.500 + Node* b = s->fChildren[kRight_Child];
1.501 +
1.502 + if (NULL != d) {
1.503 + Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child :
1.504 + kRight_Child;
1.505 + d->fChildren[c] = s;
1.506 + } else {
1.507 + SkASSERT(fRoot == n);
1.508 + fRoot = s;
1.509 + }
1.510 + s->fParent = d;
1.511 + s->fChildren[kRight_Child] = n;
1.512 + n->fParent = s;
1.513 + n->fChildren[kLeft_Child] = b;
1.514 + if (NULL != b) {
1.515 + b->fParent = n;
1.516 + }
1.517 +
1.518 + GR_DEBUGASSERT(validateChildRelations(d, true));
1.519 + GR_DEBUGASSERT(validateChildRelations(s, true));
1.520 + GR_DEBUGASSERT(validateChildRelations(n, false));
1.521 + GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true));
1.522 + GR_DEBUGASSERT(validateChildRelations(b, true));
1.523 + GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true));
1.524 +}
1.525 +
1.526 +template <typename T, typename C>
1.527 +void GrRedBlackTree<T,C>::rotateLeft(Node* n) {
1.528 +
1.529 + Node* d = n->fParent;
1.530 + Node* s = n->fChildren[kRight_Child];
1.531 + SkASSERT(NULL != s);
1.532 + Node* b = s->fChildren[kLeft_Child];
1.533 +
1.534 + if (NULL != d) {
1.535 + Child c = d->fChildren[kRight_Child] == n ? kRight_Child :
1.536 + kLeft_Child;
1.537 + d->fChildren[c] = s;
1.538 + } else {
1.539 + SkASSERT(fRoot == n);
1.540 + fRoot = s;
1.541 + }
1.542 + s->fParent = d;
1.543 + s->fChildren[kLeft_Child] = n;
1.544 + n->fParent = s;
1.545 + n->fChildren[kRight_Child] = b;
1.546 + if (NULL != b) {
1.547 + b->fParent = n;
1.548 + }
1.549 +
1.550 + GR_DEBUGASSERT(validateChildRelations(d, true));
1.551 + GR_DEBUGASSERT(validateChildRelations(s, true));
1.552 + GR_DEBUGASSERT(validateChildRelations(n, true));
1.553 + GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true));
1.554 + GR_DEBUGASSERT(validateChildRelations(b, true));
1.555 + GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true));
1.556 +}
1.557 +
1.558 +template <typename T, typename C>
1.559 +typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) {
1.560 + SkASSERT(NULL != x);
1.561 + if (NULL != x->fChildren[kRight_Child]) {
1.562 + x = x->fChildren[kRight_Child];
1.563 + while (NULL != x->fChildren[kLeft_Child]) {
1.564 + x = x->fChildren[kLeft_Child];
1.565 + }
1.566 + return x;
1.567 + }
1.568 + while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) {
1.569 + x = x->fParent;
1.570 + }
1.571 + return x->fParent;
1.572 +}
1.573 +
1.574 +template <typename T, typename C>
1.575 +typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x) {
1.576 + SkASSERT(NULL != x);
1.577 + if (NULL != x->fChildren[kLeft_Child]) {
1.578 + x = x->fChildren[kLeft_Child];
1.579 + while (NULL != x->fChildren[kRight_Child]) {
1.580 + x = x->fChildren[kRight_Child];
1.581 + }
1.582 + return x;
1.583 + }
1.584 + while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) {
1.585 + x = x->fParent;
1.586 + }
1.587 + return x->fParent;
1.588 +}
1.589 +
1.590 +template <typename T, typename C>
1.591 +void GrRedBlackTree<T,C>::deleteAtNode(Node* x) {
1.592 + SkASSERT(NULL != x);
1.593 + validate();
1.594 + --fCount;
1.595 +
1.596 + bool hasLeft = NULL != x->fChildren[kLeft_Child];
1.597 + bool hasRight = NULL != x->fChildren[kRight_Child];
1.598 + Child c = hasLeft ? kLeft_Child : kRight_Child;
1.599 +
1.600 + if (hasLeft && hasRight) {
1.601 + // first and last can't have two children.
1.602 + SkASSERT(fFirst != x);
1.603 + SkASSERT(fLast != x);
1.604 + // if x is an interior node then we find it's successor
1.605 + // and swap them.
1.606 + Node* s = x->fChildren[kRight_Child];
1.607 + while (NULL != s->fChildren[kLeft_Child]) {
1.608 + s = s->fChildren[kLeft_Child];
1.609 + }
1.610 + SkASSERT(NULL != s);
1.611 + // this might be expensive relative to swapping node ptrs around.
1.612 + // depends on T.
1.613 + x->fItem = s->fItem;
1.614 + x = s;
1.615 + c = kRight_Child;
1.616 + } else if (NULL == x->fParent) {
1.617 + // if x was the root we just replace it with its child and make
1.618 + // the new root (if the tree is not empty) black.
1.619 + SkASSERT(fRoot == x);
1.620 + fRoot = x->fChildren[c];
1.621 + if (NULL != fRoot) {
1.622 + fRoot->fParent = NULL;
1.623 + fRoot->fColor = kBlack_Color;
1.624 + if (x == fLast) {
1.625 + SkASSERT(c == kLeft_Child);
1.626 + fLast = fRoot;
1.627 + } else if (x == fFirst) {
1.628 + SkASSERT(c == kRight_Child);
1.629 + fFirst = fRoot;
1.630 + }
1.631 + } else {
1.632 + SkASSERT(fFirst == fLast && x == fFirst);
1.633 + fFirst = NULL;
1.634 + fLast = NULL;
1.635 + SkASSERT(0 == fCount);
1.636 + }
1.637 + delete x;
1.638 + validate();
1.639 + return;
1.640 + }
1.641 +
1.642 + Child pc;
1.643 + Node* p = x->fParent;
1.644 + pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child;
1.645 +
1.646 + if (NULL == x->fChildren[c]) {
1.647 + if (fLast == x) {
1.648 + fLast = p;
1.649 + SkASSERT(p == PredecessorNode(x));
1.650 + } else if (fFirst == x) {
1.651 + fFirst = p;
1.652 + SkASSERT(p == SuccessorNode(x));
1.653 + }
1.654 + // x has two implicit black children.
1.655 + Color xcolor = x->fColor;
1.656 + p->fChildren[pc] = NULL;
1.657 + delete x;
1.658 + x = NULL;
1.659 + // when x is red it can be with an implicit black leaf without
1.660 + // violating any of the red-black tree properties.
1.661 + if (kRed_Color == xcolor) {
1.662 + validate();
1.663 + return;
1.664 + }
1.665 + // s is p's other child (x's sibling)
1.666 + Node* s = p->fChildren[1-pc];
1.667 +
1.668 + //s cannot be an implicit black node because the original
1.669 + // black-height at x was >= 2 and s's black-height must equal the
1.670 + // initial black height of x.
1.671 + SkASSERT(NULL != s);
1.672 + SkASSERT(p == s->fParent);
1.673 +
1.674 + // assigned in loop
1.675 + Node* sl;
1.676 + Node* sr;
1.677 + bool slRed;
1.678 + bool srRed;
1.679 +
1.680 + do {
1.681 + // When we start this loop x may already be deleted it is/was
1.682 + // p's child on its pc side. x's children are/were black. The
1.683 + // first time through the loop they are implict children.
1.684 + // On later passes we will be walking up the tree and they will
1.685 + // be real nodes.
1.686 + // The x side of p has a black-height that is one less than the
1.687 + // s side. It must be rebalanced.
1.688 + SkASSERT(NULL != s);
1.689 + SkASSERT(p == s->fParent);
1.690 + SkASSERT(NULL == x || x->fParent == p);
1.691 +
1.692 + //sl and sr are s's children, which may be implicit.
1.693 + sl = s->fChildren[kLeft_Child];
1.694 + sr = s->fChildren[kRight_Child];
1.695 +
1.696 + // if the s is red we will rotate s and p, swap their colors so
1.697 + // that x's new sibling is black
1.698 + if (kRed_Color == s->fColor) {
1.699 + // if s is red then it's parent must be black.
1.700 + SkASSERT(kBlack_Color == p->fColor);
1.701 + // s's children must also be black since s is red. They can't
1.702 + // be implicit since s is red and it's black-height is >= 2.
1.703 + SkASSERT(NULL != sl && kBlack_Color == sl->fColor);
1.704 + SkASSERT(NULL != sr && kBlack_Color == sr->fColor);
1.705 + p->fColor = kRed_Color;
1.706 + s->fColor = kBlack_Color;
1.707 + if (kLeft_Child == pc) {
1.708 + rotateLeft(p);
1.709 + s = sl;
1.710 + } else {
1.711 + rotateRight(p);
1.712 + s = sr;
1.713 + }
1.714 + sl = s->fChildren[kLeft_Child];
1.715 + sr = s->fChildren[kRight_Child];
1.716 + }
1.717 + // x and s are now both black.
1.718 + SkASSERT(kBlack_Color == s->fColor);
1.719 + SkASSERT(NULL == x || kBlack_Color == x->fColor);
1.720 + SkASSERT(p == s->fParent);
1.721 + SkASSERT(NULL == x || p == x->fParent);
1.722 +
1.723 + // when x is deleted its subtree will have reduced black-height.
1.724 + slRed = (NULL != sl && kRed_Color == sl->fColor);
1.725 + srRed = (NULL != sr && kRed_Color == sr->fColor);
1.726 + if (!slRed && !srRed) {
1.727 + // if s can be made red that will balance out x's removal
1.728 + // to make both subtrees of p have the same black-height.
1.729 + if (kBlack_Color == p->fColor) {
1.730 + s->fColor = kRed_Color;
1.731 + // now subtree at p has black-height of one less than
1.732 + // p's parent's other child's subtree. We move x up to
1.733 + // p and go through the loop again. At the top of loop
1.734 + // we assumed x and x's children are black, which holds
1.735 + // by above ifs.
1.736 + // if p is the root there is no other subtree to balance
1.737 + // against.
1.738 + x = p;
1.739 + p = x->fParent;
1.740 + if (NULL == p) {
1.741 + SkASSERT(fRoot == x);
1.742 + validate();
1.743 + return;
1.744 + } else {
1.745 + pc = p->fChildren[kLeft_Child] == x ? kLeft_Child :
1.746 + kRight_Child;
1.747 +
1.748 + }
1.749 + s = p->fChildren[1-pc];
1.750 + SkASSERT(NULL != s);
1.751 + SkASSERT(p == s->fParent);
1.752 + continue;
1.753 + } else if (kRed_Color == p->fColor) {
1.754 + // we can make p black and s red. This balance out p's
1.755 + // two subtrees and keep the same black-height as it was
1.756 + // before the delete.
1.757 + s->fColor = kRed_Color;
1.758 + p->fColor = kBlack_Color;
1.759 + validate();
1.760 + return;
1.761 + }
1.762 + }
1.763 + break;
1.764 + } while (true);
1.765 + // if we made it here one or both of sl and sr is red.
1.766 + // s and x are black. We make sure that a red child is on
1.767 + // the same side of s as s is of p.
1.768 + SkASSERT(slRed || srRed);
1.769 + if (kLeft_Child == pc && !srRed) {
1.770 + s->fColor = kRed_Color;
1.771 + sl->fColor = kBlack_Color;
1.772 + rotateRight(s);
1.773 + sr = s;
1.774 + s = sl;
1.775 + //sl = s->fChildren[kLeft_Child]; don't need this
1.776 + } else if (kRight_Child == pc && !slRed) {
1.777 + s->fColor = kRed_Color;
1.778 + sr->fColor = kBlack_Color;
1.779 + rotateLeft(s);
1.780 + sl = s;
1.781 + s = sr;
1.782 + //sr = s->fChildren[kRight_Child]; don't need this
1.783 + }
1.784 + // now p is either red or black, x and s are red and s's 1-pc
1.785 + // child is red.
1.786 + // We rotate p towards x, pulling s up to replace p. We make
1.787 + // p be black and s takes p's old color.
1.788 + // Whether p was red or black, we've increased its pc subtree
1.789 + // rooted at x by 1 (balancing the imbalance at the start) and
1.790 + // we've also its subtree rooted at s's black-height by 1. This
1.791 + // can be balanced by making s's red child be black.
1.792 + s->fColor = p->fColor;
1.793 + p->fColor = kBlack_Color;
1.794 + if (kLeft_Child == pc) {
1.795 + SkASSERT(NULL != sr && kRed_Color == sr->fColor);
1.796 + sr->fColor = kBlack_Color;
1.797 + rotateLeft(p);
1.798 + } else {
1.799 + SkASSERT(NULL != sl && kRed_Color == sl->fColor);
1.800 + sl->fColor = kBlack_Color;
1.801 + rotateRight(p);
1.802 + }
1.803 + }
1.804 + else {
1.805 + // x has exactly one implicit black child. x cannot be red.
1.806 + // Proof by contradiction: Assume X is red. Let c0 be x's implicit
1.807 + // child and c1 be its non-implicit child. c1 must be black because
1.808 + // red nodes always have two black children. Then the two subtrees
1.809 + // of x rooted at c0 and c1 will have different black-heights.
1.810 + SkASSERT(kBlack_Color == x->fColor);
1.811 + // So we know x is black and has one implicit black child, c0. c1
1.812 + // must be red, otherwise the subtree at c1 will have a different
1.813 + // black-height than the subtree rooted at c0.
1.814 + SkASSERT(kRed_Color == x->fChildren[c]->fColor);
1.815 + // replace x with c1, making c1 black, preserves all red-black tree
1.816 + // props.
1.817 + Node* c1 = x->fChildren[c];
1.818 + if (x == fFirst) {
1.819 + SkASSERT(c == kRight_Child);
1.820 + fFirst = c1;
1.821 + while (NULL != fFirst->fChildren[kLeft_Child]) {
1.822 + fFirst = fFirst->fChildren[kLeft_Child];
1.823 + }
1.824 + SkASSERT(fFirst == SuccessorNode(x));
1.825 + } else if (x == fLast) {
1.826 + SkASSERT(c == kLeft_Child);
1.827 + fLast = c1;
1.828 + while (NULL != fLast->fChildren[kRight_Child]) {
1.829 + fLast = fLast->fChildren[kRight_Child];
1.830 + }
1.831 + SkASSERT(fLast == PredecessorNode(x));
1.832 + }
1.833 + c1->fParent = p;
1.834 + p->fChildren[pc] = c1;
1.835 + c1->fColor = kBlack_Color;
1.836 + delete x;
1.837 + validate();
1.838 + }
1.839 + validate();
1.840 +}
1.841 +
1.842 +template <typename T, typename C>
1.843 +void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) {
1.844 + if (NULL != x) {
1.845 + RecursiveDelete(x->fChildren[kLeft_Child]);
1.846 + RecursiveDelete(x->fChildren[kRight_Child]);
1.847 + delete x;
1.848 + }
1.849 +}
1.850 +
1.851 +#ifdef SK_DEBUG
1.852 +template <typename T, typename C>
1.853 +void GrRedBlackTree<T,C>::validate() const {
1.854 + if (fCount) {
1.855 + SkASSERT(NULL == fRoot->fParent);
1.856 + SkASSERT(NULL != fFirst);
1.857 + SkASSERT(NULL != fLast);
1.858 +
1.859 + SkASSERT(kBlack_Color == fRoot->fColor);
1.860 + if (1 == fCount) {
1.861 + SkASSERT(fFirst == fRoot);
1.862 + SkASSERT(fLast == fRoot);
1.863 + SkASSERT(0 == fRoot->fChildren[kLeft_Child]);
1.864 + SkASSERT(0 == fRoot->fChildren[kRight_Child]);
1.865 + }
1.866 + } else {
1.867 + SkASSERT(NULL == fRoot);
1.868 + SkASSERT(NULL == fFirst);
1.869 + SkASSERT(NULL == fLast);
1.870 + }
1.871 +#if DEEP_VALIDATE
1.872 + int bh;
1.873 + int count = checkNode(fRoot, &bh);
1.874 + SkASSERT(count == fCount);
1.875 +#endif
1.876 +}
1.877 +
1.878 +template <typename T, typename C>
1.879 +int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const {
1.880 + if (NULL != n) {
1.881 + SkASSERT(validateChildRelations(n, false));
1.882 + if (kBlack_Color == n->fColor) {
1.883 + *bh += 1;
1.884 + }
1.885 + SkASSERT(!fComp(n->fItem, fFirst->fItem));
1.886 + SkASSERT(!fComp(fLast->fItem, n->fItem));
1.887 + int leftBh = *bh;
1.888 + int rightBh = *bh;
1.889 + int cl = checkNode(n->fChildren[kLeft_Child], &leftBh);
1.890 + int cr = checkNode(n->fChildren[kRight_Child], &rightBh);
1.891 + SkASSERT(leftBh == rightBh);
1.892 + *bh = leftBh;
1.893 + return 1 + cl + cr;
1.894 + }
1.895 + return 0;
1.896 +}
1.897 +
1.898 +template <typename T, typename C>
1.899 +bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,
1.900 + bool allowRedRed) const {
1.901 + if (NULL != n) {
1.902 + if (NULL != n->fChildren[kLeft_Child] ||
1.903 + NULL != n->fChildren[kRight_Child]) {
1.904 + if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) {
1.905 + return validateChildRelationsFailed();
1.906 + }
1.907 + if (n->fChildren[kLeft_Child] == n->fParent &&
1.908 + NULL != n->fParent) {
1.909 + return validateChildRelationsFailed();
1.910 + }
1.911 + if (n->fChildren[kRight_Child] == n->fParent &&
1.912 + NULL != n->fParent) {
1.913 + return validateChildRelationsFailed();
1.914 + }
1.915 + if (NULL != n->fChildren[kLeft_Child]) {
1.916 + if (!allowRedRed &&
1.917 + kRed_Color == n->fChildren[kLeft_Child]->fColor &&
1.918 + kRed_Color == n->fColor) {
1.919 + return validateChildRelationsFailed();
1.920 + }
1.921 + if (n->fChildren[kLeft_Child]->fParent != n) {
1.922 + return validateChildRelationsFailed();
1.923 + }
1.924 + if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) ||
1.925 + (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) &&
1.926 + !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) {
1.927 + return validateChildRelationsFailed();
1.928 + }
1.929 + }
1.930 + if (NULL != n->fChildren[kRight_Child]) {
1.931 + if (!allowRedRed &&
1.932 + kRed_Color == n->fChildren[kRight_Child]->fColor &&
1.933 + kRed_Color == n->fColor) {
1.934 + return validateChildRelationsFailed();
1.935 + }
1.936 + if (n->fChildren[kRight_Child]->fParent != n) {
1.937 + return validateChildRelationsFailed();
1.938 + }
1.939 + if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) ||
1.940 + (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) &&
1.941 + !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) {
1.942 + return validateChildRelationsFailed();
1.943 + }
1.944 + }
1.945 + }
1.946 + }
1.947 + return true;
1.948 +}
1.949 +#endif
1.950 +
1.951 +#endif
