src/gpu/GrRedBlackTree.h - Issue 1226203013: Remove GrRedBlackTree

Side by Side Diff: src/gpu/GrRedBlackTree.h

Issue 1226203013: Remove GrRedBlackTree (Closed) Base URL: https://skia.googlesource.com/skia.git@master

Patch Set: rebase Created 5 years, 5 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 /*

2 * Copyright 2011 Google Inc.

3 *

4 * Use of this source code is governed by a BSD-style license that can be

5 * found in the LICENSE file.

6 */

7

8 #ifndef GrRedBlackTree_DEFINED

9 #define GrRedBlackTree_DEFINED

10

11 #include "GrConfig.h"

12 #include "SkTypes.h"

13

14 template <typename T>

15 class GrLess {

16 public:

17 bool operator()(const T& a, const T& b) const { return a < b; }

18 };

19

20 template <typename T>

21 class GrLess<T*> {

22 public:

23 bool operator()(const T* a, const T* b) const { return a < b; }

24 };

25

26 class GrStrLess {

27 public:

28 bool operator()(const char* a, const char* b) const { return strcmp(a,b) < 0 ; }

29 };

30

31 /**

32 * In debug build this will cause full traversals of the tree when the validate

33 * is called on insert and remove. Useful for debugging but very slow.

34 */

35 #define DEEP_VALIDATE 0

36

37 /**

38 * A sorted tree that uses the red-black tree algorithm. Allows duplicate

39 * entries. Data is of type T and is compared using functor C. A single C object

40 * will be created and used for all comparisons.

41 */

42 template <typename T, typename C = GrLess<T> >

43 class GrRedBlackTree : SkNoncopyable {

44 public:

45 /**

46 * Creates an empty tree.

47 */

48 GrRedBlackTree();

49 virtual ~GrRedBlackTree();

50

51 /**

52 * Class used to iterater through the tree. The valid range of the tree

53 * is given by [begin(), end()). It is legal to dereference begin() but not

54 * end(). The iterator has preincrement and predecrement operators, it is

55 * legal to decerement end() if the tree is not empty to get the last

56 * element. However, a last() helper is provided.

57 */

58 class Iter;

59

60 /**

61 * Add an element to the tree. Duplicates are allowed.

62 * @param t the item to add.

63 * @return an iterator to the item.

64 */

65 Iter insert(const T& t);

66

67 /**

68 * Removes all items in the tree.

69 */

70 void reset();

71

72 /**

73 * @return true if there are no items in the tree, false otherwise.

74 */

75 bool empty() const {return 0 == fCount;}

76

77 /**

78 * @return the number of items in the tree.

79 */

80 int count() const {return fCount;}

81

82 /**

83 * @return an iterator to the first item in sorted order, or end() if empty

84 */

85 Iter begin();

86 /**

87 * Gets the last valid iterator. This is always valid, even on an empty.

88 * However, it can never be dereferenced. Useful as a loop terminator.

89 * @return an iterator that is just beyond the last item in sorted order.

90 */

91 Iter end();

92 /**

93 * @return an iterator that to the last item in sorted order, or end() if

94 * empty.

95 */

96 Iter last();

97

98 /**

99 * Finds an occurrence of an item.

100 * @param t the item to find.

101 * @return an iterator to a tree element equal to t or end() if none exists.

102 */

103 Iter find(const T& t);

104 /**

105 * Finds the first of an item in iterator order.

106 * @param t the item to find.

107 * @return an iterator to the first element equal to t or end() if

108 * none exists.

109 */

110 Iter findFirst(const T& t);

111 /**

112 * Finds the last of an item in iterator order.

113 * @param t the item to find.

114 * @return an iterator to the last element equal to t or end() if

115 * none exists.

116 */

117 Iter findLast(const T& t);

118 /**

119 * Gets the number of items in the tree equal to t.

120 * @param t the item to count.

121 * @return number of items equal to t in the tree

122 */

123 int countOf(const T& t) const;

124

125 /**

126 * Removes the item indicated by an iterator. The iterator will not be valid

127 * afterwards.

128 *

129 * @param iter iterator of item to remove. Must be valid (not end()).

130 */

131 void remove(const Iter& iter) { deleteAtNode(iter.fN); }

132

133 private:

134 enum Color {

135 kRed_Color,

136 kBlack_Color

137 };

138

139 enum Child {

140 kLeft_Child = 0,

141 kRight_Child = 1

142 };

143

144 struct Node {

145 T fItem;

146 Color fColor;

147

148 Node* fParent;

149 Node* fChildren[2];

150 };

151

152 void rotateRight(Node* n);

153 void rotateLeft(Node* n);

154

155 static Node* SuccessorNode(Node* x);

156 static Node* PredecessorNode(Node* x);

157

158 void deleteAtNode(Node* x);

159 static void RecursiveDelete(Node* x);

160

161 int onCountOf(const Node* n, const T& t) const;

162

163 #ifdef SK_DEBUG

164 void validate() const;

165 int checkNode(Node* n, int* blackHeight) const;

166 // checks relationship between a node and its children. allowRedRed means

167 // node may be in an intermediate state where a red parent has a red child.

168 bool validateChildRelations(const Node* n, bool allowRedRed) const;

169 // place to stick break point if validateChildRelations is failing.

170 bool validateChildRelationsFailed() const { return false; }

171 #else

172 void validate() const {}

173 #endif

174

175 int fCount;

176 Node* fRoot;

177 Node* fFirst;

178 Node* fLast;

179

180 const C fComp;

181 };

182

183 template <typename T, typename C>

184 class GrRedBlackTree<T,C>::Iter {

185 public:

186 Iter() {};

187 Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;}

188 Iter& operator =(const Iter& i) {

189 fN = i.fN;

190 fTree = i.fTree;

191 return *this;

192 }

193 // altering the sort value of the item using this method will cause

194 // errors.

195 T& operator *() const { return fN->fItem; }

196 bool operator ==(const Iter& i) const {

197 return fN == i.fN && fTree == i.fTree;

198 }

199 bool operator !=(const Iter& i) const { return !(*this == i); }

200 Iter& operator ++() {

201 SkASSERT(*this != fTree->end());

202 fN = SuccessorNode(fN);

203 return *this;

204 }

205 Iter& operator --() {

206 SkASSERT(*this != fTree->begin());

207 if (fN) {

208 fN = PredecessorNode(fN);

209 } else {

210 *this = fTree->last();

211 }

212 return *this;

213 }

214

215 private:

216 friend class GrRedBlackTree;

217 explicit Iter(Node* n, GrRedBlackTree* tree) {

218 fN = n;

219 fTree = tree;

220 }

221 Node* fN;

222 GrRedBlackTree* fTree;

223 };

224

225 template <typename T, typename C>

226 GrRedBlackTree<T,C>::GrRedBlackTree() : fComp() {

227 fRoot = NULL;

228 fFirst = NULL;

229 fLast = NULL;

230 fCount = 0;

231 validate();

232 }

233

234 template <typename T, typename C>

235 GrRedBlackTree<T,C>::~GrRedBlackTree() {

236 RecursiveDelete(fRoot);

237 }

238

239 template <typename T, typename C>

240 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() {

241 return Iter(fFirst, this);

242 }

243

244 template <typename T, typename C>

245 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() {

246 return Iter(NULL, this);

247 }

248

249 template <typename T, typename C>

250 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() {

251 return Iter(fLast, this);

252 }

253

254 template <typename T, typename C>

255 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) {

256 Node* n = fRoot;

257 while (n) {

258 if (fComp(t, n->fItem)) {

259 n = n->fChildren[kLeft_Child];

260 } else {

261 if (!fComp(n->fItem, t)) {

262 return Iter(n, this);

263 }

264 n = n->fChildren[kRight_Child];

265 }

266 }

267 return end();

268 }

269

270 template <typename T, typename C>

271 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) {

272 Node* n = fRoot;

273 Node* leftMost = NULL;

274 while (n) {

275 if (fComp(t, n->fItem)) {

276 n = n->fChildren[kLeft_Child];

277 } else {

278 if (!fComp(n->fItem, t)) {

279 // found one. check if another in left subtree.

280 leftMost = n;

281 n = n->fChildren[kLeft_Child];

282 } else {

283 n = n->fChildren[kRight_Child];

284 }

285 }

286 }

287 return Iter(leftMost, this);

288 }

289

290 template <typename T, typename C>

291 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) {

292 Node* n = fRoot;

293 Node* rightMost = NULL;

294 while (n) {

295 if (fComp(t, n->fItem)) {

296 n = n->fChildren[kLeft_Child];

297 } else {

298 if (!fComp(n->fItem, t)) {

299 // found one. check if another in right subtree.

300 rightMost = n;

301 }

302 n = n->fChildren[kRight_Child];

303 }

304 }

305 return Iter(rightMost, this);

306 }

307

308 template <typename T, typename C>

309 int GrRedBlackTree<T,C>::countOf(const T& t) const {

310 return onCountOf(fRoot, t);

311 }

312

313 template <typename T, typename C>

314 int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const {

315 // this is count*log(n) :(

316 while (n) {

317 if (fComp(t, n->fItem)) {

318 n = n->fChildren[kLeft_Child];

319 } else {

320 if (!fComp(n->fItem, t)) {

321 int count = 1;

322 count += onCountOf(n->fChildren[kLeft_Child], t);

323 count += onCountOf(n->fChildren[kRight_Child], t);

324 return count;

325 }

326 n = n->fChildren[kRight_Child];

327 }

328 }

329 return 0;

330

331 }

332

333 template <typename T, typename C>

334 void GrRedBlackTree<T,C>::reset() {

335 RecursiveDelete(fRoot);

336 fRoot = NULL;

337 fFirst = NULL;

338 fLast = NULL;

339 fCount = 0;

340 }

341

342 template <typename T, typename C>

343 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) {

344 validate();

345

346 ++fCount;

347

348 Node* x = SkNEW(Node);

349 x->fChildren[kLeft_Child] = NULL;

350 x->fChildren[kRight_Child] = NULL;

351 x->fItem = t;

352

353 Node* returnNode = x;

354

355 Node* gp = NULL;

356 Node* p = NULL;

357 Node* n = fRoot;

358 Child pc = kLeft_Child; // suppress uninit warning

359 Child gpc = kLeft_Child;

360

361 bool first = true;

362 bool last = true;

363 while (n) {

364 gpc = pc;

365 pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child;

366 first = first && kLeft_Child == pc;

367 last = last && kRight_Child == pc;

368 gp = p;

369 p = n;

370 n = p->fChildren[pc];

371 }

372 if (last) {

373 fLast = x;

374 }

375 if (first) {

376 fFirst = x;

377 }

378

379 if (NULL == p) {

380 fRoot = x;

381 x->fColor = kBlack_Color;

382 x->fParent = NULL;

383 SkASSERT(1 == fCount);

384 return Iter(returnNode, this);

385 }

386 p->fChildren[pc] = x;

387 x->fColor = kRed_Color;

388 x->fParent = p;

389

390 do {

391 // assumptions at loop start.

392 SkASSERT(x);

393 SkASSERT(kRed_Color == x->fColor);

394 // can't have a grandparent but no parent.

395 SkASSERT(!(gp && NULL == p));

396 // make sure pc and gpc are correct

397 SkASSERT(NULL == p \|\| p->fChildren[pc] == x);

398 SkASSERT(NULL == gp \|\| gp->fChildren[gpc] == p);

399

400 // if x's parent is black then we didn't violate any of the

401 // red/black properties when we added x as red.

402 if (kBlack_Color == p->fColor) {

403 return Iter(returnNode, this);

404 }

405 // gp must be valid because if p was the root then it is black

406 SkASSERT(gp);

407 // gp must be black since it's child, p, is red.

408 SkASSERT(kBlack_Color == gp->fColor);

409

410

411 // x and its parent are red, violating red-black property.

412 Node* u = gp->fChildren[1-gpc];

413 // if x's uncle (p's sibling) is also red then we can flip

414 // p and u to black and make gp red. But then we have to recurse

415 // up to gp since it's parent may also be red.

416 if (u && kRed_Color == u->fColor) {

417 p->fColor = kBlack_Color;

418 u->fColor = kBlack_Color;

419 gp->fColor = kRed_Color;

420 x = gp;

421 p = x->fParent;

422 if (NULL == p) {

423 // x (prev gp) is the root, color it black and be done.

424 SkASSERT(fRoot == x);

425 x->fColor = kBlack_Color;

426 validate();

427 return Iter(returnNode, this);

428 }

429 gp = p->fParent;

430 pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child :

431 kRight_Child;

432 if (gp) {

433 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child :

434 kRight_Child;

435 }

436 continue;

437 } break;

438 } while (true);

439 // Here p is red but u is black and we still have to resolve the fact

440 // that x and p are both red.

441 SkASSERT(NULL == gp->fChildren[1-gpc] \|\| kBlack_Color == gp->fChildren[1-gpc ]->fColor);

442 SkASSERT(kRed_Color == x->fColor);

443 SkASSERT(kRed_Color == p->fColor);

444 SkASSERT(kBlack_Color == gp->fColor);

445

446 // make x be on the same side of p as p is of gp. If it isn't already

447 // the case then rotate x up to p and swap their labels.

448 if (pc != gpc) {

449 if (kRight_Child == pc) {

450 rotateLeft(p);

451 Node* temp = p;

452 p = x;

453 x = temp;

454 pc = kLeft_Child;

455 } else {

456 rotateRight(p);

457 Node* temp = p;

458 p = x;

459 x = temp;

460 pc = kRight_Child;

461 }

462 }

463 // we now rotate gp down, pulling up p to be it's new parent.

464 // gp's child, u, that is not affected we know to be black. gp's new

465 // child is p's previous child (x's pre-rotation sibling) which must be

466 // black since p is red.

467 SkASSERT(NULL == p->fChildren[1-pc] \|\|

468 kBlack_Color == p->fChildren[1-pc]->fColor);

469 // Since gp's two children are black it can become red if p is made

470 // black. This leaves the black-height of both of p's new subtrees

471 // preserved and removes the red/red parent child relationship.

472 p->fColor = kBlack_Color;

473 gp->fColor = kRed_Color;

474 if (kLeft_Child == pc) {

475 rotateRight(gp);

476 } else {

477 rotateLeft(gp);

478 }

479 validate();

480 return Iter(returnNode, this);

481 }

482

483

484 template <typename T, typename C>

485 void GrRedBlackTree<T,C>::rotateRight(Node* n) {

486 /* d? d?

487 * / /

488 * n s

489 * / \ ---> / \

490 * s a? c? n

491 * / \ / \

492 * c? b? b? a?

493 */

494 Node* d = n->fParent;

495 Node* s = n->fChildren[kLeft_Child];

496 SkASSERT(s);

497 Node* b = s->fChildren[kRight_Child];

498

499 if (d) {

500 Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child :

501 kRight_Child;

502 d->fChildren[c] = s;

503 } else {

504 SkASSERT(fRoot == n);

505 fRoot = s;

506 }

507 s->fParent = d;

508 s->fChildren[kRight_Child] = n;

509 n->fParent = s;

510 n->fChildren[kLeft_Child] = b;

511 if (b) {

512 b->fParent = n;

513 }

514

515 GR_DEBUGASSERT(validateChildRelations(d, true));

516 GR_DEBUGASSERT(validateChildRelations(s, true));

517 GR_DEBUGASSERT(validateChildRelations(n, false));

518 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true));

519 GR_DEBUGASSERT(validateChildRelations(b, true));

520 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true));

521 }

522

523 template <typename T, typename C>

524 void GrRedBlackTree<T,C>::rotateLeft(Node* n) {

525

526 Node* d = n->fParent;

527 Node* s = n->fChildren[kRight_Child];

528 SkASSERT(s);

529 Node* b = s->fChildren[kLeft_Child];

530

531 if (d) {

532 Child c = d->fChildren[kRight_Child] == n ? kRight_Child :

533 kLeft_Child;

534 d->fChildren[c] = s;

535 } else {

536 SkASSERT(fRoot == n);

537 fRoot = s;

538 }

539 s->fParent = d;

540 s->fChildren[kLeft_Child] = n;

541 n->fParent = s;

542 n->fChildren[kRight_Child] = b;

543 if (b) {

544 b->fParent = n;

545 }

546

547 GR_DEBUGASSERT(validateChildRelations(d, true));

548 GR_DEBUGASSERT(validateChildRelations(s, true));

549 GR_DEBUGASSERT(validateChildRelations(n, true));

550 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true));

551 GR_DEBUGASSERT(validateChildRelations(b, true));

552 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true));

553 }

554

555 template <typename T, typename C>

556 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) {

557 SkASSERT(x);

558 if (x->fChildren[kRight_Child]) {

559 x = x->fChildren[kRight_Child];

560 while (x->fChildren[kLeft_Child]) {

561 x = x->fChildren[kLeft_Child];

562 }

563 return x;

564 }

565 while (x->fParent && x == x->fParent->fChildren[kRight_Child]) {

566 x = x->fParent;

567 }

568 return x->fParent;

569 }

570

571 template <typename T, typename C>

572 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x ) {

573 SkASSERT(x);

574 if (x->fChildren[kLeft_Child]) {

575 x = x->fChildren[kLeft_Child];

576 while (x->fChildren[kRight_Child]) {

577 x = x->fChildren[kRight_Child];

578 }

579 return x;

580 }

581 while (x->fParent && x == x->fParent->fChildren[kLeft_Child]) {

582 x = x->fParent;

583 }

584 return x->fParent;

585 }

586

587 template <typename T, typename C>

588 void GrRedBlackTree<T,C>::deleteAtNode(Node* x) {

589 SkASSERT(x);

590 validate();

591 --fCount;

592

593 bool hasLeft = SkToBool(x->fChildren[kLeft_Child]);

594 bool hasRight = SkToBool(x->fChildren[kRight_Child]);

595 Child c = hasLeft ? kLeft_Child : kRight_Child;

596

597 if (hasLeft && hasRight) {

598 // first and last can't have two children.

599 SkASSERT(fFirst != x);

600 SkASSERT(fLast != x);

601 // if x is an interior node then we find it's successor

602 // and swap them.

603 Node* s = x->fChildren[kRight_Child];

604 while (s->fChildren[kLeft_Child]) {

605 s = s->fChildren[kLeft_Child];

606 }

607 SkASSERT(s);

608 // this might be expensive relative to swapping node ptrs around.

609 // depends on T.

610 x->fItem = s->fItem;

611 x = s;

612 c = kRight_Child;

613 } else if (NULL == x->fParent) {

614 // if x was the root we just replace it with its child and make

615 // the new root (if the tree is not empty) black.

616 SkASSERT(fRoot == x);

617 fRoot = x->fChildren[c];

618 if (fRoot) {

619 fRoot->fParent = NULL;

620 fRoot->fColor = kBlack_Color;

621 if (x == fLast) {

622 SkASSERT(c == kLeft_Child);

623 fLast = fRoot;

624 } else if (x == fFirst) {

625 SkASSERT(c == kRight_Child);

626 fFirst = fRoot;

627 }

628 } else {

629 SkASSERT(fFirst == fLast && x == fFirst);

630 fFirst = NULL;

631 fLast = NULL;

632 SkASSERT(0 == fCount);

633 }

634 delete x;

635 validate();

636 return;

637 }

638

639 Child pc;

640 Node* p = x->fParent;

641 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child;

642

643 if (NULL == x->fChildren[c]) {

644 if (fLast == x) {

645 fLast = p;

646 SkASSERT(p == PredecessorNode(x));

647 } else if (fFirst == x) {

648 fFirst = p;

649 SkASSERT(p == SuccessorNode(x));

650 }

651 // x has two implicit black children.

652 Color xcolor = x->fColor;

653 p->fChildren[pc] = NULL;

654 delete x;

655 x = NULL;

656 // when x is red it can be with an implicit black leaf without

657 // violating any of the red-black tree properties.

658 if (kRed_Color == xcolor) {

659 validate();

660 return;

661 }

662 // s is p's other child (x's sibling)

663 Node* s = p->fChildren[1-pc];

664

665 //s cannot be an implicit black node because the original

666 // black-height at x was >= 2 and s's black-height must equal the

667 // initial black height of x.

668 SkASSERT(s);

669 SkASSERT(p == s->fParent);

670

671 // assigned in loop

672 Node* sl;

673 Node* sr;

674 bool slRed;

675 bool srRed;

676

677 do {

678 // When we start this loop x may already be deleted it is/was

679 // p's child on its pc side. x's children are/were black. The

680 // first time through the loop they are implict children.

681 // On later passes we will be walking up the tree and they will

682 // be real nodes.

683 // The x side of p has a black-height that is one less than the

684 // s side. It must be rebalanced.

685 SkASSERT(s);

686 SkASSERT(p == s->fParent);

687 SkASSERT(NULL == x \|\| x->fParent == p);

688

689 //sl and sr are s's children, which may be implicit.

690 sl = s->fChildren[kLeft_Child];

691 sr = s->fChildren[kRight_Child];

692

693 // if the s is red we will rotate s and p, swap their colors so

694 // that x's new sibling is black

695 if (kRed_Color == s->fColor) {

696 // if s is red then it's parent must be black.

697 SkASSERT(kBlack_Color == p->fColor);

698 // s's children must also be black since s is red. They can't

699 // be implicit since s is red and it's black-height is >= 2.

700 SkASSERT(sl && kBlack_Color == sl->fColor);

701 SkASSERT(sr && kBlack_Color == sr->fColor);

702 p->fColor = kRed_Color;

703 s->fColor = kBlack_Color;

704 if (kLeft_Child == pc) {

705 rotateLeft(p);

706 s = sl;

707 } else {

708 rotateRight(p);

709 s = sr;

710 }

711 sl = s->fChildren[kLeft_Child];

712 sr = s->fChildren[kRight_Child];

713 }

714 // x and s are now both black.

715 SkASSERT(kBlack_Color == s->fColor);

716 SkASSERT(NULL == x \|\| kBlack_Color == x->fColor);

717 SkASSERT(p == s->fParent);

718 SkASSERT(NULL == x \|\| p == x->fParent);

719

720 // when x is deleted its subtree will have reduced black-height.

721 slRed = (sl && kRed_Color == sl->fColor);

722 srRed = (sr && kRed_Color == sr->fColor);

723 if (!slRed && !srRed) {

724 // if s can be made red that will balance out x's removal

725 // to make both subtrees of p have the same black-height.

726 if (kBlack_Color == p->fColor) {

727 s->fColor = kRed_Color;

728 // now subtree at p has black-height of one less than

729 // p's parent's other child's subtree. We move x up to

730 // p and go through the loop again. At the top of loop

731 // we assumed x and x's children are black, which holds

732 // by above ifs.

733 // if p is the root there is no other subtree to balance

734 // against.

735 x = p;

736 p = x->fParent;

737 if (NULL == p) {

738 SkASSERT(fRoot == x);

739 validate();

740 return;

741 } else {

742 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child :

743 kRight_Child;

744

745 }

746 s = p->fChildren[1-pc];

747 SkASSERT(s);

748 SkASSERT(p == s->fParent);

749 continue;

750 } else if (kRed_Color == p->fColor) {

751 // we can make p black and s red. This balance out p's

752 // two subtrees and keep the same black-height as it was

753 // before the delete.

754 s->fColor = kRed_Color;

755 p->fColor = kBlack_Color;

756 validate();

757 return;

758 }

759 }

760 break;

761 } while (true);

762 // if we made it here one or both of sl and sr is red.

763 // s and x are black. We make sure that a red child is on

764 // the same side of s as s is of p.

765 SkASSERT(slRed \|\| srRed);

766 if (kLeft_Child == pc && !srRed) {

767 s->fColor = kRed_Color;

768 sl->fColor = kBlack_Color;

769 rotateRight(s);

770 sr = s;

771 s = sl;

772 //sl = s->fChildren[kLeft_Child]; don't need this

773 } else if (kRight_Child == pc && !slRed) {

774 s->fColor = kRed_Color;

775 sr->fColor = kBlack_Color;

776 rotateLeft(s);

777 sl = s;

778 s = sr;

779 //sr = s->fChildren[kRight_Child]; don't need this

780 }

781 // now p is either red or black, x and s are red and s's 1-pc

782 // child is red.

783 // We rotate p towards x, pulling s up to replace p. We make

784 // p be black and s takes p's old color.

785 // Whether p was red or black, we've increased its pc subtree

786 // rooted at x by 1 (balancing the imbalance at the start) and

787 // we've also its subtree rooted at s's black-height by 1. This

788 // can be balanced by making s's red child be black.

789 s->fColor = p->fColor;

790 p->fColor = kBlack_Color;

791 if (kLeft_Child == pc) {

792 SkASSERT(sr && kRed_Color == sr->fColor);

793 sr->fColor = kBlack_Color;

794 rotateLeft(p);

795 } else {

796 SkASSERT(sl && kRed_Color == sl->fColor);

797 sl->fColor = kBlack_Color;

798 rotateRight(p);

799 }

800 }

801 else {

802 // x has exactly one implicit black child. x cannot be red.

803 // Proof by contradiction: Assume X is red. Let c0 be x's implicit

804 // child and c1 be its non-implicit child. c1 must be black because

805 // red nodes always have two black children. Then the two subtrees

806 // of x rooted at c0 and c1 will have different black-heights.

807 SkASSERT(kBlack_Color == x->fColor);

808 // So we know x is black and has one implicit black child, c0. c1

809 // must be red, otherwise the subtree at c1 will have a different

810 // black-height than the subtree rooted at c0.

811 SkASSERT(kRed_Color == x->fChildren[c]->fColor);

812 // replace x with c1, making c1 black, preserves all red-black tree

813 // props.

814 Node* c1 = x->fChildren[c];

815 if (x == fFirst) {

816 SkASSERT(c == kRight_Child);

817 fFirst = c1;

818 while (fFirst->fChildren[kLeft_Child]) {

819 fFirst = fFirst->fChildren[kLeft_Child];

820 }

821 SkASSERT(fFirst == SuccessorNode(x));

822 } else if (x == fLast) {

823 SkASSERT(c == kLeft_Child);

824 fLast = c1;

825 while (fLast->fChildren[kRight_Child]) {

826 fLast = fLast->fChildren[kRight_Child];

827 }

828 SkASSERT(fLast == PredecessorNode(x));

829 }

830 c1->fParent = p;

831 p->fChildren[pc] = c1;

832 c1->fColor = kBlack_Color;

833 delete x;

834 validate();

835 }

836 validate();

837 }

838

839 template <typename T, typename C>

840 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) {

841 if (x) {

842 RecursiveDelete(x->fChildren[kLeft_Child]);

843 RecursiveDelete(x->fChildren[kRight_Child]);

844 delete x;

845 }

846 }

847

848 #ifdef SK_DEBUG

849 template <typename T, typename C>

850 void GrRedBlackTree<T,C>::validate() const {

851 if (fCount) {

852 SkASSERT(NULL == fRoot->fParent);

853 SkASSERT(fFirst);

854 SkASSERT(fLast);

855

856 SkASSERT(kBlack_Color == fRoot->fColor);

857 if (1 == fCount) {

858 SkASSERT(fFirst == fRoot);

859 SkASSERT(fLast == fRoot);

860 SkASSERT(0 == fRoot->fChildren[kLeft_Child]);

861 SkASSERT(0 == fRoot->fChildren[kRight_Child]);

862 }

863 } else {

864 SkASSERT(NULL == fRoot);

865 SkASSERT(NULL == fFirst);

866 SkASSERT(NULL == fLast);

867 }

868 #if DEEP_VALIDATE

869 int bh;

870 int count = checkNode(fRoot, &bh);

871 SkASSERT(count == fCount);

872 #endif

873 }

874

875 template <typename T, typename C>

876 int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const {

877 if (n) {

878 SkASSERT(validateChildRelations(n, false));

879 if (kBlack_Color == n->fColor) {

880 *bh += 1;

881 }

882 SkASSERT(!fComp(n->fItem, fFirst->fItem));

883 SkASSERT(!fComp(fLast->fItem, n->fItem));

884 int leftBh = *bh;

885 int rightBh = *bh;

886 int cl = checkNode(n->fChildren[kLeft_Child], &leftBh);

887 int cr = checkNode(n->fChildren[kRight_Child], &rightBh);

888 SkASSERT(leftBh == rightBh);

889 *bh = leftBh;

890 return 1 + cl + cr;

891 }

892 return 0;

893 }

894

895 template <typename T, typename C>

896 bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,

897 bool allowRedRed) const {

898 if (n) {

899 if (n->fChildren[kLeft_Child] \|\|

900 n->fChildren[kRight_Child]) {

901 if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) {

902 return validateChildRelationsFailed();

903 }

904 if (n->fChildren[kLeft_Child] == n->fParent &&

905 n->fParent) {

906 return validateChildRelationsFailed();

907 }

908 if (n->fChildren[kRight_Child] == n->fParent &&

909 n->fParent) {

910 return validateChildRelationsFailed();

911 }

912 if (n->fChildren[kLeft_Child]) {

913 if (!allowRedRed &&

914 kRed_Color == n->fChildren[kLeft_Child]->fColor &&

915 kRed_Color == n->fColor) {

916 return validateChildRelationsFailed();

917 }

918 if (n->fChildren[kLeft_Child]->fParent != n) {

919 return validateChildRelationsFailed();

920 }

921 if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) \|\|

922 (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) &&

923 !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) {

924 return validateChildRelationsFailed();

925 }

926 }

927 if (n->fChildren[kRight_Child]) {

928 if (!allowRedRed &&

929 kRed_Color == n->fChildren[kRight_Child]->fColor &&

930 kRed_Color == n->fColor) {

931 return validateChildRelationsFailed();

932 }

933 if (n->fChildren[kRight_Child]->fParent != n) {

934 return validateChildRelationsFailed();

935 }

936 if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) \|\|

937 (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) &&

938 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) {

939 return validateChildRelationsFailed();

940 }

941 }

942 }

943 }

944 return true;

945 }

946 #endif

947

948 #endif

OLD	NEW

« no previous file with comments | « src/gpu/GrOrderedSet.h ('k') | tests/GrOrderedSetTest.cpp » ('j') | no next file with comments »