OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef GrRedBlackTree_DEFINED | 8 #ifndef GrRedBlackTree_DEFINED |
9 #define GrRedBlackTree_DEFINED | 9 #define GrRedBlackTree_DEFINED |
10 | 10 |
(...skipping 186 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
197 return fN == i.fN && fTree == i.fTree; | 197 return fN == i.fN && fTree == i.fTree; |
198 } | 198 } |
199 bool operator !=(const Iter& i) const { return !(*this == i); } | 199 bool operator !=(const Iter& i) const { return !(*this == i); } |
200 Iter& operator ++() { | 200 Iter& operator ++() { |
201 SkASSERT(*this != fTree->end()); | 201 SkASSERT(*this != fTree->end()); |
202 fN = SuccessorNode(fN); | 202 fN = SuccessorNode(fN); |
203 return *this; | 203 return *this; |
204 } | 204 } |
205 Iter& operator --() { | 205 Iter& operator --() { |
206 SkASSERT(*this != fTree->begin()); | 206 SkASSERT(*this != fTree->begin()); |
207 if (NULL != fN) { | 207 if (fN) { |
208 fN = PredecessorNode(fN); | 208 fN = PredecessorNode(fN); |
209 } else { | 209 } else { |
210 *this = fTree->last(); | 210 *this = fTree->last(); |
211 } | 211 } |
212 return *this; | 212 return *this; |
213 } | 213 } |
214 | 214 |
215 private: | 215 private: |
216 friend class GrRedBlackTree; | 216 friend class GrRedBlackTree; |
217 explicit Iter(Node* n, GrRedBlackTree* tree) { | 217 explicit Iter(Node* n, GrRedBlackTree* tree) { |
(...skipping 29 matching lines...) Expand all Loading... |
247 } | 247 } |
248 | 248 |
249 template <typename T, typename C> | 249 template <typename T, typename C> |
250 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() { | 250 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() { |
251 return Iter(fLast, this); | 251 return Iter(fLast, this); |
252 } | 252 } |
253 | 253 |
254 template <typename T, typename C> | 254 template <typename T, typename C> |
255 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) { | 255 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) { |
256 Node* n = fRoot; | 256 Node* n = fRoot; |
257 while (NULL != n) { | 257 while (n) { |
258 if (fComp(t, n->fItem)) { | 258 if (fComp(t, n->fItem)) { |
259 n = n->fChildren[kLeft_Child]; | 259 n = n->fChildren[kLeft_Child]; |
260 } else { | 260 } else { |
261 if (!fComp(n->fItem, t)) { | 261 if (!fComp(n->fItem, t)) { |
262 return Iter(n, this); | 262 return Iter(n, this); |
263 } | 263 } |
264 n = n->fChildren[kRight_Child]; | 264 n = n->fChildren[kRight_Child]; |
265 } | 265 } |
266 } | 266 } |
267 return end(); | 267 return end(); |
268 } | 268 } |
269 | 269 |
270 template <typename T, typename C> | 270 template <typename T, typename C> |
271 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) { | 271 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) { |
272 Node* n = fRoot; | 272 Node* n = fRoot; |
273 Node* leftMost = NULL; | 273 Node* leftMost = NULL; |
274 while (NULL != n) { | 274 while (n) { |
275 if (fComp(t, n->fItem)) { | 275 if (fComp(t, n->fItem)) { |
276 n = n->fChildren[kLeft_Child]; | 276 n = n->fChildren[kLeft_Child]; |
277 } else { | 277 } else { |
278 if (!fComp(n->fItem, t)) { | 278 if (!fComp(n->fItem, t)) { |
279 // found one. check if another in left subtree. | 279 // found one. check if another in left subtree. |
280 leftMost = n; | 280 leftMost = n; |
281 n = n->fChildren[kLeft_Child]; | 281 n = n->fChildren[kLeft_Child]; |
282 } else { | 282 } else { |
283 n = n->fChildren[kRight_Child]; | 283 n = n->fChildren[kRight_Child]; |
284 } | 284 } |
285 } | 285 } |
286 } | 286 } |
287 return Iter(leftMost, this); | 287 return Iter(leftMost, this); |
288 } | 288 } |
289 | 289 |
290 template <typename T, typename C> | 290 template <typename T, typename C> |
291 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) { | 291 typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) { |
292 Node* n = fRoot; | 292 Node* n = fRoot; |
293 Node* rightMost = NULL; | 293 Node* rightMost = NULL; |
294 while (NULL != n) { | 294 while (n) { |
295 if (fComp(t, n->fItem)) { | 295 if (fComp(t, n->fItem)) { |
296 n = n->fChildren[kLeft_Child]; | 296 n = n->fChildren[kLeft_Child]; |
297 } else { | 297 } else { |
298 if (!fComp(n->fItem, t)) { | 298 if (!fComp(n->fItem, t)) { |
299 // found one. check if another in right subtree. | 299 // found one. check if another in right subtree. |
300 rightMost = n; | 300 rightMost = n; |
301 } | 301 } |
302 n = n->fChildren[kRight_Child]; | 302 n = n->fChildren[kRight_Child]; |
303 } | 303 } |
304 } | 304 } |
305 return Iter(rightMost, this); | 305 return Iter(rightMost, this); |
306 } | 306 } |
307 | 307 |
308 template <typename T, typename C> | 308 template <typename T, typename C> |
309 int GrRedBlackTree<T,C>::countOf(const T& t) const { | 309 int GrRedBlackTree<T,C>::countOf(const T& t) const { |
310 return onCountOf(fRoot, t); | 310 return onCountOf(fRoot, t); |
311 } | 311 } |
312 | 312 |
313 template <typename T, typename C> | 313 template <typename T, typename C> |
314 int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const { | 314 int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const { |
315 // this is count*log(n) :( | 315 // this is count*log(n) :( |
316 while (NULL != n) { | 316 while (n) { |
317 if (fComp(t, n->fItem)) { | 317 if (fComp(t, n->fItem)) { |
318 n = n->fChildren[kLeft_Child]; | 318 n = n->fChildren[kLeft_Child]; |
319 } else { | 319 } else { |
320 if (!fComp(n->fItem, t)) { | 320 if (!fComp(n->fItem, t)) { |
321 int count = 1; | 321 int count = 1; |
322 count += onCountOf(n->fChildren[kLeft_Child], t); | 322 count += onCountOf(n->fChildren[kLeft_Child], t); |
323 count += onCountOf(n->fChildren[kRight_Child], t); | 323 count += onCountOf(n->fChildren[kRight_Child], t); |
324 return count; | 324 return count; |
325 } | 325 } |
326 n = n->fChildren[kRight_Child]; | 326 n = n->fChildren[kRight_Child]; |
(...skipping 26 matching lines...) Expand all Loading... |
353 Node* returnNode = x; | 353 Node* returnNode = x; |
354 | 354 |
355 Node* gp = NULL; | 355 Node* gp = NULL; |
356 Node* p = NULL; | 356 Node* p = NULL; |
357 Node* n = fRoot; | 357 Node* n = fRoot; |
358 Child pc = kLeft_Child; // suppress uninit warning | 358 Child pc = kLeft_Child; // suppress uninit warning |
359 Child gpc = kLeft_Child; | 359 Child gpc = kLeft_Child; |
360 | 360 |
361 bool first = true; | 361 bool first = true; |
362 bool last = true; | 362 bool last = true; |
363 while (NULL != n) { | 363 while (n) { |
364 gpc = pc; | 364 gpc = pc; |
365 pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child; | 365 pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child; |
366 first = first && kLeft_Child == pc; | 366 first = first && kLeft_Child == pc; |
367 last = last && kRight_Child == pc; | 367 last = last && kRight_Child == pc; |
368 gp = p; | 368 gp = p; |
369 p = n; | 369 p = n; |
370 n = p->fChildren[pc]; | 370 n = p->fChildren[pc]; |
371 } | 371 } |
372 if (last) { | 372 if (last) { |
373 fLast = x; | 373 fLast = x; |
374 } | 374 } |
375 if (first) { | 375 if (first) { |
376 fFirst = x; | 376 fFirst = x; |
377 } | 377 } |
378 | 378 |
379 if (NULL == p) { | 379 if (NULL == p) { |
380 fRoot = x; | 380 fRoot = x; |
381 x->fColor = kBlack_Color; | 381 x->fColor = kBlack_Color; |
382 x->fParent = NULL; | 382 x->fParent = NULL; |
383 SkASSERT(1 == fCount); | 383 SkASSERT(1 == fCount); |
384 return Iter(returnNode, this); | 384 return Iter(returnNode, this); |
385 } | 385 } |
386 p->fChildren[pc] = x; | 386 p->fChildren[pc] = x; |
387 x->fColor = kRed_Color; | 387 x->fColor = kRed_Color; |
388 x->fParent = p; | 388 x->fParent = p; |
389 | 389 |
390 do { | 390 do { |
391 // assumptions at loop start. | 391 // assumptions at loop start. |
392 SkASSERT(NULL != x); | 392 SkASSERT(x); |
393 SkASSERT(kRed_Color == x->fColor); | 393 SkASSERT(kRed_Color == x->fColor); |
394 // can't have a grandparent but no parent. | 394 // can't have a grandparent but no parent. |
395 SkASSERT(!(NULL != gp && NULL == p)); | 395 SkASSERT(!(gp && NULL == p)); |
396 // make sure pc and gpc are correct | 396 // make sure pc and gpc are correct |
397 SkASSERT(NULL == p || p->fChildren[pc] == x); | 397 SkASSERT(NULL == p || p->fChildren[pc] == x); |
398 SkASSERT(NULL == gp || gp->fChildren[gpc] == p); | 398 SkASSERT(NULL == gp || gp->fChildren[gpc] == p); |
399 | 399 |
400 // if x's parent is black then we didn't violate any of the | 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. | 401 // red/black properties when we added x as red. |
402 if (kBlack_Color == p->fColor) { | 402 if (kBlack_Color == p->fColor) { |
403 return Iter(returnNode, this); | 403 return Iter(returnNode, this); |
404 } | 404 } |
405 // gp must be valid because if p was the root then it is black | 405 // gp must be valid because if p was the root then it is black |
406 SkASSERT(NULL != gp); | 406 SkASSERT(gp); |
407 // gp must be black since it's child, p, is red. | 407 // gp must be black since it's child, p, is red. |
408 SkASSERT(kBlack_Color == gp->fColor); | 408 SkASSERT(kBlack_Color == gp->fColor); |
409 | 409 |
410 | 410 |
411 // x and its parent are red, violating red-black property. | 411 // x and its parent are red, violating red-black property. |
412 Node* u = gp->fChildren[1-gpc]; | 412 Node* u = gp->fChildren[1-gpc]; |
413 // if x's uncle (p's sibling) is also red then we can flip | 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 | 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. | 415 // up to gp since it's parent may also be red. |
416 if (NULL != u && kRed_Color == u->fColor) { | 416 if (u && kRed_Color == u->fColor) { |
417 p->fColor = kBlack_Color; | 417 p->fColor = kBlack_Color; |
418 u->fColor = kBlack_Color; | 418 u->fColor = kBlack_Color; |
419 gp->fColor = kRed_Color; | 419 gp->fColor = kRed_Color; |
420 x = gp; | 420 x = gp; |
421 p = x->fParent; | 421 p = x->fParent; |
422 if (NULL == p) { | 422 if (NULL == p) { |
423 // x (prev gp) is the root, color it black and be done. | 423 // x (prev gp) is the root, color it black and be done. |
424 SkASSERT(fRoot == x); | 424 SkASSERT(fRoot == x); |
425 x->fColor = kBlack_Color; | 425 x->fColor = kBlack_Color; |
426 validate(); | 426 validate(); |
427 return Iter(returnNode, this); | 427 return Iter(returnNode, this); |
428 } | 428 } |
429 gp = p->fParent; | 429 gp = p->fParent; |
430 pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child : | 430 pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child : |
431 kRight_Child; | 431 kRight_Child; |
432 if (NULL != gp) { | 432 if (gp) { |
433 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child : | 433 gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child : |
434 kRight_Child; | 434 kRight_Child; |
435 } | 435 } |
436 continue; | 436 continue; |
437 } break; | 437 } break; |
438 } while (true); | 438 } while (true); |
439 // Here p is red but u is black and we still have to resolve the fact | 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. | 440 // that x and p are both red. |
441 SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc
]->fColor); | 441 SkASSERT(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc
]->fColor); |
442 SkASSERT(kRed_Color == x->fColor); | 442 SkASSERT(kRed_Color == x->fColor); |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
486 /* d? d? | 486 /* d? d? |
487 * / / | 487 * / / |
488 * n s | 488 * n s |
489 * / \ ---> / \ | 489 * / \ ---> / \ |
490 * s a? c? n | 490 * s a? c? n |
491 * / \ / \ | 491 * / \ / \ |
492 * c? b? b? a? | 492 * c? b? b? a? |
493 */ | 493 */ |
494 Node* d = n->fParent; | 494 Node* d = n->fParent; |
495 Node* s = n->fChildren[kLeft_Child]; | 495 Node* s = n->fChildren[kLeft_Child]; |
496 SkASSERT(NULL != s); | 496 SkASSERT(s); |
497 Node* b = s->fChildren[kRight_Child]; | 497 Node* b = s->fChildren[kRight_Child]; |
498 | 498 |
499 if (NULL != d) { | 499 if (d) { |
500 Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child : | 500 Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child : |
501 kRight_Child; | 501 kRight_Child; |
502 d->fChildren[c] = s; | 502 d->fChildren[c] = s; |
503 } else { | 503 } else { |
504 SkASSERT(fRoot == n); | 504 SkASSERT(fRoot == n); |
505 fRoot = s; | 505 fRoot = s; |
506 } | 506 } |
507 s->fParent = d; | 507 s->fParent = d; |
508 s->fChildren[kRight_Child] = n; | 508 s->fChildren[kRight_Child] = n; |
509 n->fParent = s; | 509 n->fParent = s; |
510 n->fChildren[kLeft_Child] = b; | 510 n->fChildren[kLeft_Child] = b; |
511 if (NULL != b) { | 511 if (b) { |
512 b->fParent = n; | 512 b->fParent = n; |
513 } | 513 } |
514 | 514 |
515 GR_DEBUGASSERT(validateChildRelations(d, true)); | 515 GR_DEBUGASSERT(validateChildRelations(d, true)); |
516 GR_DEBUGASSERT(validateChildRelations(s, true)); | 516 GR_DEBUGASSERT(validateChildRelations(s, true)); |
517 GR_DEBUGASSERT(validateChildRelations(n, false)); | 517 GR_DEBUGASSERT(validateChildRelations(n, false)); |
518 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true)); | 518 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true)); |
519 GR_DEBUGASSERT(validateChildRelations(b, true)); | 519 GR_DEBUGASSERT(validateChildRelations(b, true)); |
520 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true)); | 520 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true)); |
521 } | 521 } |
522 | 522 |
523 template <typename T, typename C> | 523 template <typename T, typename C> |
524 void GrRedBlackTree<T,C>::rotateLeft(Node* n) { | 524 void GrRedBlackTree<T,C>::rotateLeft(Node* n) { |
525 | 525 |
526 Node* d = n->fParent; | 526 Node* d = n->fParent; |
527 Node* s = n->fChildren[kRight_Child]; | 527 Node* s = n->fChildren[kRight_Child]; |
528 SkASSERT(NULL != s); | 528 SkASSERT(s); |
529 Node* b = s->fChildren[kLeft_Child]; | 529 Node* b = s->fChildren[kLeft_Child]; |
530 | 530 |
531 if (NULL != d) { | 531 if (d) { |
532 Child c = d->fChildren[kRight_Child] == n ? kRight_Child : | 532 Child c = d->fChildren[kRight_Child] == n ? kRight_Child : |
533 kLeft_Child; | 533 kLeft_Child; |
534 d->fChildren[c] = s; | 534 d->fChildren[c] = s; |
535 } else { | 535 } else { |
536 SkASSERT(fRoot == n); | 536 SkASSERT(fRoot == n); |
537 fRoot = s; | 537 fRoot = s; |
538 } | 538 } |
539 s->fParent = d; | 539 s->fParent = d; |
540 s->fChildren[kLeft_Child] = n; | 540 s->fChildren[kLeft_Child] = n; |
541 n->fParent = s; | 541 n->fParent = s; |
542 n->fChildren[kRight_Child] = b; | 542 n->fChildren[kRight_Child] = b; |
543 if (NULL != b) { | 543 if (b) { |
544 b->fParent = n; | 544 b->fParent = n; |
545 } | 545 } |
546 | 546 |
547 GR_DEBUGASSERT(validateChildRelations(d, true)); | 547 GR_DEBUGASSERT(validateChildRelations(d, true)); |
548 GR_DEBUGASSERT(validateChildRelations(s, true)); | 548 GR_DEBUGASSERT(validateChildRelations(s, true)); |
549 GR_DEBUGASSERT(validateChildRelations(n, true)); | 549 GR_DEBUGASSERT(validateChildRelations(n, true)); |
550 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true)); | 550 GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true)); |
551 GR_DEBUGASSERT(validateChildRelations(b, true)); | 551 GR_DEBUGASSERT(validateChildRelations(b, true)); |
552 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true)); | 552 GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true)); |
553 } | 553 } |
554 | 554 |
555 template <typename T, typename C> | 555 template <typename T, typename C> |
556 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x)
{ | 556 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x)
{ |
557 SkASSERT(NULL != x); | 557 SkASSERT(x); |
558 if (NULL != x->fChildren[kRight_Child]) { | 558 if (x->fChildren[kRight_Child]) { |
559 x = x->fChildren[kRight_Child]; | 559 x = x->fChildren[kRight_Child]; |
560 while (NULL != x->fChildren[kLeft_Child]) { | 560 while (x->fChildren[kLeft_Child]) { |
561 x = x->fChildren[kLeft_Child]; | 561 x = x->fChildren[kLeft_Child]; |
562 } | 562 } |
563 return x; | 563 return x; |
564 } | 564 } |
565 while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) { | 565 while (x->fParent && x == x->fParent->fChildren[kRight_Child]) { |
566 x = x->fParent; | 566 x = x->fParent; |
567 } | 567 } |
568 return x->fParent; | 568 return x->fParent; |
569 } | 569 } |
570 | 570 |
571 template <typename T, typename C> | 571 template <typename T, typename C> |
572 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x
) { | 572 typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x
) { |
573 SkASSERT(NULL != x); | 573 SkASSERT(x); |
574 if (NULL != x->fChildren[kLeft_Child]) { | 574 if (x->fChildren[kLeft_Child]) { |
575 x = x->fChildren[kLeft_Child]; | 575 x = x->fChildren[kLeft_Child]; |
576 while (NULL != x->fChildren[kRight_Child]) { | 576 while (x->fChildren[kRight_Child]) { |
577 x = x->fChildren[kRight_Child]; | 577 x = x->fChildren[kRight_Child]; |
578 } | 578 } |
579 return x; | 579 return x; |
580 } | 580 } |
581 while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) { | 581 while (x->fParent && x == x->fParent->fChildren[kLeft_Child]) { |
582 x = x->fParent; | 582 x = x->fParent; |
583 } | 583 } |
584 return x->fParent; | 584 return x->fParent; |
585 } | 585 } |
586 | 586 |
587 template <typename T, typename C> | 587 template <typename T, typename C> |
588 void GrRedBlackTree<T,C>::deleteAtNode(Node* x) { | 588 void GrRedBlackTree<T,C>::deleteAtNode(Node* x) { |
589 SkASSERT(NULL != x); | 589 SkASSERT(x); |
590 validate(); | 590 validate(); |
591 --fCount; | 591 --fCount; |
592 | 592 |
593 bool hasLeft = NULL != x->fChildren[kLeft_Child]; | 593 bool hasLeft = SkToBool(x->fChildren[kLeft_Child]); |
594 bool hasRight = NULL != x->fChildren[kRight_Child]; | 594 bool hasRight = SkToBool(x->fChildren[kRight_Child]); |
595 Child c = hasLeft ? kLeft_Child : kRight_Child; | 595 Child c = hasLeft ? kLeft_Child : kRight_Child; |
596 | 596 |
597 if (hasLeft && hasRight) { | 597 if (hasLeft && hasRight) { |
598 // first and last can't have two children. | 598 // first and last can't have two children. |
599 SkASSERT(fFirst != x); | 599 SkASSERT(fFirst != x); |
600 SkASSERT(fLast != x); | 600 SkASSERT(fLast != x); |
601 // if x is an interior node then we find it's successor | 601 // if x is an interior node then we find it's successor |
602 // and swap them. | 602 // and swap them. |
603 Node* s = x->fChildren[kRight_Child]; | 603 Node* s = x->fChildren[kRight_Child]; |
604 while (NULL != s->fChildren[kLeft_Child]) { | 604 while (s->fChildren[kLeft_Child]) { |
605 s = s->fChildren[kLeft_Child]; | 605 s = s->fChildren[kLeft_Child]; |
606 } | 606 } |
607 SkASSERT(NULL != s); | 607 SkASSERT(s); |
608 // this might be expensive relative to swapping node ptrs around. | 608 // this might be expensive relative to swapping node ptrs around. |
609 // depends on T. | 609 // depends on T. |
610 x->fItem = s->fItem; | 610 x->fItem = s->fItem; |
611 x = s; | 611 x = s; |
612 c = kRight_Child; | 612 c = kRight_Child; |
613 } else if (NULL == x->fParent) { | 613 } else if (NULL == x->fParent) { |
614 // if x was the root we just replace it with its child and make | 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. | 615 // the new root (if the tree is not empty) black. |
616 SkASSERT(fRoot == x); | 616 SkASSERT(fRoot == x); |
617 fRoot = x->fChildren[c]; | 617 fRoot = x->fChildren[c]; |
618 if (NULL != fRoot) { | 618 if (fRoot) { |
619 fRoot->fParent = NULL; | 619 fRoot->fParent = NULL; |
620 fRoot->fColor = kBlack_Color; | 620 fRoot->fColor = kBlack_Color; |
621 if (x == fLast) { | 621 if (x == fLast) { |
622 SkASSERT(c == kLeft_Child); | 622 SkASSERT(c == kLeft_Child); |
623 fLast = fRoot; | 623 fLast = fRoot; |
624 } else if (x == fFirst) { | 624 } else if (x == fFirst) { |
625 SkASSERT(c == kRight_Child); | 625 SkASSERT(c == kRight_Child); |
626 fFirst = fRoot; | 626 fFirst = fRoot; |
627 } | 627 } |
628 } else { | 628 } else { |
(...skipping 29 matching lines...) Expand all Loading... |
658 if (kRed_Color == xcolor) { | 658 if (kRed_Color == xcolor) { |
659 validate(); | 659 validate(); |
660 return; | 660 return; |
661 } | 661 } |
662 // s is p's other child (x's sibling) | 662 // s is p's other child (x's sibling) |
663 Node* s = p->fChildren[1-pc]; | 663 Node* s = p->fChildren[1-pc]; |
664 | 664 |
665 //s cannot be an implicit black node because the original | 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 | 666 // black-height at x was >= 2 and s's black-height must equal the |
667 // initial black height of x. | 667 // initial black height of x. |
668 SkASSERT(NULL != s); | 668 SkASSERT(s); |
669 SkASSERT(p == s->fParent); | 669 SkASSERT(p == s->fParent); |
670 | 670 |
671 // assigned in loop | 671 // assigned in loop |
672 Node* sl; | 672 Node* sl; |
673 Node* sr; | 673 Node* sr; |
674 bool slRed; | 674 bool slRed; |
675 bool srRed; | 675 bool srRed; |
676 | 676 |
677 do { | 677 do { |
678 // When we start this loop x may already be deleted it is/was | 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 | 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. | 680 // first time through the loop they are implict children. |
681 // On later passes we will be walking up the tree and they will | 681 // On later passes we will be walking up the tree and they will |
682 // be real nodes. | 682 // be real nodes. |
683 // The x side of p has a black-height that is one less than the | 683 // The x side of p has a black-height that is one less than the |
684 // s side. It must be rebalanced. | 684 // s side. It must be rebalanced. |
685 SkASSERT(NULL != s); | 685 SkASSERT(s); |
686 SkASSERT(p == s->fParent); | 686 SkASSERT(p == s->fParent); |
687 SkASSERT(NULL == x || x->fParent == p); | 687 SkASSERT(NULL == x || x->fParent == p); |
688 | 688 |
689 //sl and sr are s's children, which may be implicit. | 689 //sl and sr are s's children, which may be implicit. |
690 sl = s->fChildren[kLeft_Child]; | 690 sl = s->fChildren[kLeft_Child]; |
691 sr = s->fChildren[kRight_Child]; | 691 sr = s->fChildren[kRight_Child]; |
692 | 692 |
693 // if the s is red we will rotate s and p, swap their colors so | 693 // if the s is red we will rotate s and p, swap their colors so |
694 // that x's new sibling is black | 694 // that x's new sibling is black |
695 if (kRed_Color == s->fColor) { | 695 if (kRed_Color == s->fColor) { |
696 // if s is red then it's parent must be black. | 696 // if s is red then it's parent must be black. |
697 SkASSERT(kBlack_Color == p->fColor); | 697 SkASSERT(kBlack_Color == p->fColor); |
698 // s's children must also be black since s is red. They can't | 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. | 699 // be implicit since s is red and it's black-height is >= 2. |
700 SkASSERT(NULL != sl && kBlack_Color == sl->fColor); | 700 SkASSERT(sl && kBlack_Color == sl->fColor); |
701 SkASSERT(NULL != sr && kBlack_Color == sr->fColor); | 701 SkASSERT(sr && kBlack_Color == sr->fColor); |
702 p->fColor = kRed_Color; | 702 p->fColor = kRed_Color; |
703 s->fColor = kBlack_Color; | 703 s->fColor = kBlack_Color; |
704 if (kLeft_Child == pc) { | 704 if (kLeft_Child == pc) { |
705 rotateLeft(p); | 705 rotateLeft(p); |
706 s = sl; | 706 s = sl; |
707 } else { | 707 } else { |
708 rotateRight(p); | 708 rotateRight(p); |
709 s = sr; | 709 s = sr; |
710 } | 710 } |
711 sl = s->fChildren[kLeft_Child]; | 711 sl = s->fChildren[kLeft_Child]; |
712 sr = s->fChildren[kRight_Child]; | 712 sr = s->fChildren[kRight_Child]; |
713 } | 713 } |
714 // x and s are now both black. | 714 // x and s are now both black. |
715 SkASSERT(kBlack_Color == s->fColor); | 715 SkASSERT(kBlack_Color == s->fColor); |
716 SkASSERT(NULL == x || kBlack_Color == x->fColor); | 716 SkASSERT(NULL == x || kBlack_Color == x->fColor); |
717 SkASSERT(p == s->fParent); | 717 SkASSERT(p == s->fParent); |
718 SkASSERT(NULL == x || p == x->fParent); | 718 SkASSERT(NULL == x || p == x->fParent); |
719 | 719 |
720 // when x is deleted its subtree will have reduced black-height. | 720 // when x is deleted its subtree will have reduced black-height. |
721 slRed = (NULL != sl && kRed_Color == sl->fColor); | 721 slRed = (sl && kRed_Color == sl->fColor); |
722 srRed = (NULL != sr && kRed_Color == sr->fColor); | 722 srRed = (sr && kRed_Color == sr->fColor); |
723 if (!slRed && !srRed) { | 723 if (!slRed && !srRed) { |
724 // if s can be made red that will balance out x's removal | 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. | 725 // to make both subtrees of p have the same black-height. |
726 if (kBlack_Color == p->fColor) { | 726 if (kBlack_Color == p->fColor) { |
727 s->fColor = kRed_Color; | 727 s->fColor = kRed_Color; |
728 // now subtree at p has black-height of one less than | 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 | 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 | 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 | 731 // we assumed x and x's children are black, which holds |
732 // by above ifs. | 732 // by above ifs. |
733 // if p is the root there is no other subtree to balance | 733 // if p is the root there is no other subtree to balance |
734 // against. | 734 // against. |
735 x = p; | 735 x = p; |
736 p = x->fParent; | 736 p = x->fParent; |
737 if (NULL == p) { | 737 if (NULL == p) { |
738 SkASSERT(fRoot == x); | 738 SkASSERT(fRoot == x); |
739 validate(); | 739 validate(); |
740 return; | 740 return; |
741 } else { | 741 } else { |
742 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : | 742 pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : |
743 kRight_Child; | 743 kRight_Child; |
744 | 744 |
745 } | 745 } |
746 s = p->fChildren[1-pc]; | 746 s = p->fChildren[1-pc]; |
747 SkASSERT(NULL != s); | 747 SkASSERT(s); |
748 SkASSERT(p == s->fParent); | 748 SkASSERT(p == s->fParent); |
749 continue; | 749 continue; |
750 } else if (kRed_Color == p->fColor) { | 750 } else if (kRed_Color == p->fColor) { |
751 // we can make p black and s red. This balance out p's | 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 | 752 // two subtrees and keep the same black-height as it was |
753 // before the delete. | 753 // before the delete. |
754 s->fColor = kRed_Color; | 754 s->fColor = kRed_Color; |
755 p->fColor = kBlack_Color; | 755 p->fColor = kBlack_Color; |
756 validate(); | 756 validate(); |
757 return; | 757 return; |
(...skipping 24 matching lines...) Expand all Loading... |
782 // child is red. | 782 // child is red. |
783 // We rotate p towards x, pulling s up to replace p. We make | 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. | 784 // p be black and s takes p's old color. |
785 // Whether p was red or black, we've increased its pc subtree | 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 | 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 | 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. | 788 // can be balanced by making s's red child be black. |
789 s->fColor = p->fColor; | 789 s->fColor = p->fColor; |
790 p->fColor = kBlack_Color; | 790 p->fColor = kBlack_Color; |
791 if (kLeft_Child == pc) { | 791 if (kLeft_Child == pc) { |
792 SkASSERT(NULL != sr && kRed_Color == sr->fColor); | 792 SkASSERT(sr && kRed_Color == sr->fColor); |
793 sr->fColor = kBlack_Color; | 793 sr->fColor = kBlack_Color; |
794 rotateLeft(p); | 794 rotateLeft(p); |
795 } else { | 795 } else { |
796 SkASSERT(NULL != sl && kRed_Color == sl->fColor); | 796 SkASSERT(sl && kRed_Color == sl->fColor); |
797 sl->fColor = kBlack_Color; | 797 sl->fColor = kBlack_Color; |
798 rotateRight(p); | 798 rotateRight(p); |
799 } | 799 } |
800 } | 800 } |
801 else { | 801 else { |
802 // x has exactly one implicit black child. x cannot be red. | 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 | 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 | 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 | 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. | 806 // of x rooted at c0 and c1 will have different black-heights. |
807 SkASSERT(kBlack_Color == x->fColor); | 807 SkASSERT(kBlack_Color == x->fColor); |
808 // So we know x is black and has one implicit black child, c0. c1 | 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 | 809 // must be red, otherwise the subtree at c1 will have a different |
810 // black-height than the subtree rooted at c0. | 810 // black-height than the subtree rooted at c0. |
811 SkASSERT(kRed_Color == x->fChildren[c]->fColor); | 811 SkASSERT(kRed_Color == x->fChildren[c]->fColor); |
812 // replace x with c1, making c1 black, preserves all red-black tree | 812 // replace x with c1, making c1 black, preserves all red-black tree |
813 // props. | 813 // props. |
814 Node* c1 = x->fChildren[c]; | 814 Node* c1 = x->fChildren[c]; |
815 if (x == fFirst) { | 815 if (x == fFirst) { |
816 SkASSERT(c == kRight_Child); | 816 SkASSERT(c == kRight_Child); |
817 fFirst = c1; | 817 fFirst = c1; |
818 while (NULL != fFirst->fChildren[kLeft_Child]) { | 818 while (fFirst->fChildren[kLeft_Child]) { |
819 fFirst = fFirst->fChildren[kLeft_Child]; | 819 fFirst = fFirst->fChildren[kLeft_Child]; |
820 } | 820 } |
821 SkASSERT(fFirst == SuccessorNode(x)); | 821 SkASSERT(fFirst == SuccessorNode(x)); |
822 } else if (x == fLast) { | 822 } else if (x == fLast) { |
823 SkASSERT(c == kLeft_Child); | 823 SkASSERT(c == kLeft_Child); |
824 fLast = c1; | 824 fLast = c1; |
825 while (NULL != fLast->fChildren[kRight_Child]) { | 825 while (fLast->fChildren[kRight_Child]) { |
826 fLast = fLast->fChildren[kRight_Child]; | 826 fLast = fLast->fChildren[kRight_Child]; |
827 } | 827 } |
828 SkASSERT(fLast == PredecessorNode(x)); | 828 SkASSERT(fLast == PredecessorNode(x)); |
829 } | 829 } |
830 c1->fParent = p; | 830 c1->fParent = p; |
831 p->fChildren[pc] = c1; | 831 p->fChildren[pc] = c1; |
832 c1->fColor = kBlack_Color; | 832 c1->fColor = kBlack_Color; |
833 delete x; | 833 delete x; |
834 validate(); | 834 validate(); |
835 } | 835 } |
836 validate(); | 836 validate(); |
837 } | 837 } |
838 | 838 |
839 template <typename T, typename C> | 839 template <typename T, typename C> |
840 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { | 840 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { |
841 if (NULL != x) { | 841 if (x) { |
842 RecursiveDelete(x->fChildren[kLeft_Child]); | 842 RecursiveDelete(x->fChildren[kLeft_Child]); |
843 RecursiveDelete(x->fChildren[kRight_Child]); | 843 RecursiveDelete(x->fChildren[kRight_Child]); |
844 delete x; | 844 delete x; |
845 } | 845 } |
846 } | 846 } |
847 | 847 |
848 #ifdef SK_DEBUG | 848 #ifdef SK_DEBUG |
849 template <typename T, typename C> | 849 template <typename T, typename C> |
850 void GrRedBlackTree<T,C>::validate() const { | 850 void GrRedBlackTree<T,C>::validate() const { |
851 if (fCount) { | 851 if (fCount) { |
852 SkASSERT(NULL == fRoot->fParent); | 852 SkASSERT(NULL == fRoot->fParent); |
853 SkASSERT(NULL != fFirst); | 853 SkASSERT(fFirst); |
854 SkASSERT(NULL != fLast); | 854 SkASSERT(fLast); |
855 | 855 |
856 SkASSERT(kBlack_Color == fRoot->fColor); | 856 SkASSERT(kBlack_Color == fRoot->fColor); |
857 if (1 == fCount) { | 857 if (1 == fCount) { |
858 SkASSERT(fFirst == fRoot); | 858 SkASSERT(fFirst == fRoot); |
859 SkASSERT(fLast == fRoot); | 859 SkASSERT(fLast == fRoot); |
860 SkASSERT(0 == fRoot->fChildren[kLeft_Child]); | 860 SkASSERT(0 == fRoot->fChildren[kLeft_Child]); |
861 SkASSERT(0 == fRoot->fChildren[kRight_Child]); | 861 SkASSERT(0 == fRoot->fChildren[kRight_Child]); |
862 } | 862 } |
863 } else { | 863 } else { |
864 SkASSERT(NULL == fRoot); | 864 SkASSERT(NULL == fRoot); |
865 SkASSERT(NULL == fFirst); | 865 SkASSERT(NULL == fFirst); |
866 SkASSERT(NULL == fLast); | 866 SkASSERT(NULL == fLast); |
867 } | 867 } |
868 #if DEEP_VALIDATE | 868 #if DEEP_VALIDATE |
869 int bh; | 869 int bh; |
870 int count = checkNode(fRoot, &bh); | 870 int count = checkNode(fRoot, &bh); |
871 SkASSERT(count == fCount); | 871 SkASSERT(count == fCount); |
872 #endif | 872 #endif |
873 } | 873 } |
874 | 874 |
875 template <typename T, typename C> | 875 template <typename T, typename C> |
876 int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const { | 876 int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const { |
877 if (NULL != n) { | 877 if (n) { |
878 SkASSERT(validateChildRelations(n, false)); | 878 SkASSERT(validateChildRelations(n, false)); |
879 if (kBlack_Color == n->fColor) { | 879 if (kBlack_Color == n->fColor) { |
880 *bh += 1; | 880 *bh += 1; |
881 } | 881 } |
882 SkASSERT(!fComp(n->fItem, fFirst->fItem)); | 882 SkASSERT(!fComp(n->fItem, fFirst->fItem)); |
883 SkASSERT(!fComp(fLast->fItem, n->fItem)); | 883 SkASSERT(!fComp(fLast->fItem, n->fItem)); |
884 int leftBh = *bh; | 884 int leftBh = *bh; |
885 int rightBh = *bh; | 885 int rightBh = *bh; |
886 int cl = checkNode(n->fChildren[kLeft_Child], &leftBh); | 886 int cl = checkNode(n->fChildren[kLeft_Child], &leftBh); |
887 int cr = checkNode(n->fChildren[kRight_Child], &rightBh); | 887 int cr = checkNode(n->fChildren[kRight_Child], &rightBh); |
888 SkASSERT(leftBh == rightBh); | 888 SkASSERT(leftBh == rightBh); |
889 *bh = leftBh; | 889 *bh = leftBh; |
890 return 1 + cl + cr; | 890 return 1 + cl + cr; |
891 } | 891 } |
892 return 0; | 892 return 0; |
893 } | 893 } |
894 | 894 |
895 template <typename T, typename C> | 895 template <typename T, typename C> |
896 bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n, | 896 bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n, |
897 bool allowRedRed) const { | 897 bool allowRedRed) const { |
898 if (NULL != n) { | 898 if (n) { |
899 if (NULL != n->fChildren[kLeft_Child] || | 899 if (n->fChildren[kLeft_Child] || |
900 NULL != n->fChildren[kRight_Child]) { | 900 n->fChildren[kRight_Child]) { |
901 if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) { | 901 if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) { |
902 return validateChildRelationsFailed(); | 902 return validateChildRelationsFailed(); |
903 } | 903 } |
904 if (n->fChildren[kLeft_Child] == n->fParent && | 904 if (n->fChildren[kLeft_Child] == n->fParent && |
905 NULL != n->fParent) { | 905 n->fParent) { |
906 return validateChildRelationsFailed(); | 906 return validateChildRelationsFailed(); |
907 } | 907 } |
908 if (n->fChildren[kRight_Child] == n->fParent && | 908 if (n->fChildren[kRight_Child] == n->fParent && |
909 NULL != n->fParent) { | 909 n->fParent) { |
910 return validateChildRelationsFailed(); | 910 return validateChildRelationsFailed(); |
911 } | 911 } |
912 if (NULL != n->fChildren[kLeft_Child]) { | 912 if (n->fChildren[kLeft_Child]) { |
913 if (!allowRedRed && | 913 if (!allowRedRed && |
914 kRed_Color == n->fChildren[kLeft_Child]->fColor && | 914 kRed_Color == n->fChildren[kLeft_Child]->fColor && |
915 kRed_Color == n->fColor) { | 915 kRed_Color == n->fColor) { |
916 return validateChildRelationsFailed(); | 916 return validateChildRelationsFailed(); |
917 } | 917 } |
918 if (n->fChildren[kLeft_Child]->fParent != n) { | 918 if (n->fChildren[kLeft_Child]->fParent != n) { |
919 return validateChildRelationsFailed(); | 919 return validateChildRelationsFailed(); |
920 } | 920 } |
921 if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) || | 921 if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) || |
922 (!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)))) { | 923 !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) { |
924 return validateChildRelationsFailed(); | 924 return validateChildRelationsFailed(); |
925 } | 925 } |
926 } | 926 } |
927 if (NULL != n->fChildren[kRight_Child]) { | 927 if (n->fChildren[kRight_Child]) { |
928 if (!allowRedRed && | 928 if (!allowRedRed && |
929 kRed_Color == n->fChildren[kRight_Child]->fColor && | 929 kRed_Color == n->fChildren[kRight_Child]->fColor && |
930 kRed_Color == n->fColor) { | 930 kRed_Color == n->fColor) { |
931 return validateChildRelationsFailed(); | 931 return validateChildRelationsFailed(); |
932 } | 932 } |
933 if (n->fChildren[kRight_Child]->fParent != n) { | 933 if (n->fChildren[kRight_Child]->fParent != n) { |
934 return validateChildRelationsFailed(); | 934 return validateChildRelationsFailed(); |
935 } | 935 } |
936 if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) || | 936 if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) || |
937 (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) && | 937 (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) && |
938 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { | 938 !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) { |
939 return validateChildRelationsFailed(); | 939 return validateChildRelationsFailed(); |
940 } | 940 } |
941 } | 941 } |
942 } | 942 } |
943 } | 943 } |
944 return true; | 944 return true; |
945 } | 945 } |
946 #endif | 946 #endif |
947 | 947 |
948 #endif | 948 #endif |
OLD | NEW |