| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2010 Google Inc. All rights reserved. | 2 * Copyright (C) 2010 Google Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
| 5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
| 6 * are met: | 6 * are met: |
| 7 * | 7 * |
| 8 * 1. Redistributions of source code must retain the above copyright | 8 * 1. Redistributions of source code must retain the above copyright |
| 9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
| 10 * 2. Redistributions in binary form must reproduce the above copyright | 10 * 2. Redistributions in binary form must reproduce the above copyright |
| (...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 164 if (!arena_) | 164 if (!arena_) |
| 165 arena_ = PODFreeListArena<Node>::Create(); | 165 arena_ = PODFreeListArena<Node>::Create(); |
| 166 } | 166 } |
| 167 | 167 |
| 168 void InitIfNeeded(PODFreeListArena<Node>* arena) { | 168 void InitIfNeeded(PODFreeListArena<Node>* arena) { |
| 169 if (!arena_) | 169 if (!arena_) |
| 170 arena_ = arena; | 170 arena_ = arena; |
| 171 } | 171 } |
| 172 | 172 |
| 173 void Add(const T& data) { | 173 void Add(const T& data) { |
| 174 ASSERT(IsInitialized()); | 174 DCHECK(IsInitialized()); |
| 175 Node* node = arena_->template AllocateObject<T>(data); | 175 Node* node = arena_->template AllocateObject<T>(data); |
| 176 InsertNode(node); | 176 InsertNode(node); |
| 177 } | 177 } |
| 178 | 178 |
| 179 // Returns true if the datum was found in the tree. | 179 // Returns true if the datum was found in the tree. |
| 180 bool Remove(const T& data) { | 180 bool Remove(const T& data) { |
| 181 ASSERT(IsInitialized()); | 181 DCHECK(IsInitialized()); |
| 182 Node* node = TreeSearch(data); | 182 Node* node = TreeSearch(data); |
| 183 if (node) { | 183 if (node) { |
| 184 DeleteNode(node); | 184 DeleteNode(node); |
| 185 return true; | 185 return true; |
| 186 } | 186 } |
| 187 return false; | 187 return false; |
| 188 } | 188 } |
| 189 | 189 |
| 190 bool Contains(const T& data) const { | 190 bool Contains(const T& data) const { |
| 191 ASSERT(IsInitialized()); | 191 DCHECK(IsInitialized()); |
| 192 return TreeSearch(data); | 192 return TreeSearch(data); |
| 193 } | 193 } |
| 194 | 194 |
| 195 void VisitInorder(Visitor* visitor) const { | 195 void VisitInorder(Visitor* visitor) const { |
| 196 ASSERT(IsInitialized()); | 196 DCHECK(IsInitialized()); |
| 197 if (!root_) | 197 if (!root_) |
| 198 return; | 198 return; |
| 199 VisitInorderImpl(root_, visitor); | 199 VisitInorderImpl(root_, visitor); |
| 200 } | 200 } |
| 201 | 201 |
| 202 int size() const { | 202 int size() const { |
| 203 ASSERT(IsInitialized()); | 203 DCHECK(IsInitialized()); |
| 204 Counter counter; | 204 Counter counter; |
| 205 VisitInorder(&counter); | 205 VisitInorder(&counter); |
| 206 return counter.Count(); | 206 return counter.Count(); |
| 207 } | 207 } |
| 208 | 208 |
| 209 // See the class documentation for an explanation of this property. | 209 // See the class documentation for an explanation of this property. |
| 210 void SetNeedsFullOrderingComparisons(bool needs_full_ordering_comparisons) { | 210 void SetNeedsFullOrderingComparisons(bool needs_full_ordering_comparisons) { |
| 211 needs_full_ordering_comparisons_ = needs_full_ordering_comparisons; | 211 needs_full_ordering_comparisons_ = needs_full_ordering_comparisons; |
| 212 } | 212 } |
| 213 | 213 |
| 214 virtual bool CheckInvariants() const { | 214 virtual bool CheckInvariants() const { |
| 215 ASSERT(IsInitialized()); | 215 DCHECK(IsInitialized()); |
| 216 int black_count; | 216 int black_count; |
| 217 return CheckInvariantsFromNode(root_, &black_count); | 217 return CheckInvariantsFromNode(root_, &black_count); |
| 218 } | 218 } |
| 219 | 219 |
| 220 #ifndef NDEBUG | 220 #ifndef NDEBUG |
| 221 // Dumps the tree's contents to the logging info stream for | 221 // Dumps the tree's contents to the logging info stream for |
| 222 // debugging purposes. | 222 // debugging purposes. |
| 223 void Dump() const { | 223 void Dump() const { |
| 224 if (arena_) | 224 if (arena_) |
| 225 DumpFromNode(root_, 0); | 225 DumpFromNode(root_, 0); |
| (...skipping 311 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 537 // a node. Note that x may be null, which is why xParent must be | 537 // a node. Note that x may be null, which is why xParent must be |
| 538 // supplied. | 538 // supplied. |
| 539 void DeleteFixup(Node* x, Node* x_parent) { | 539 void DeleteFixup(Node* x, Node* x_parent) { |
| 540 while (x != root_ && (!x || x->GetColor() == kBlack)) { | 540 while (x != root_ && (!x || x->GetColor() == kBlack)) { |
| 541 if (x == x_parent->Left()) { | 541 if (x == x_parent->Left()) { |
| 542 // Note: the text points out that w can not be null. | 542 // Note: the text points out that w can not be null. |
| 543 // The reason is not obvious from simply looking at | 543 // The reason is not obvious from simply looking at |
| 544 // the code; it comes about from the properties of the | 544 // the code; it comes about from the properties of the |
| 545 // red-black tree. | 545 // red-black tree. |
| 546 Node* w = x_parent->Right(); | 546 Node* w = x_parent->Right(); |
| 547 ASSERT(w); // x's sibling should not be null. | 547 DCHECK(w); // x's sibling should not be null. |
| 548 if (w->GetColor() == kRed) { | 548 if (w->GetColor() == kRed) { |
| 549 // Case 1 | 549 // Case 1 |
| 550 w->SetColor(kBlack); | 550 w->SetColor(kBlack); |
| 551 x_parent->SetColor(kRed); | 551 x_parent->SetColor(kRed); |
| 552 LeftRotate(x_parent); | 552 LeftRotate(x_parent); |
| 553 w = x_parent->Right(); | 553 w = x_parent->Right(); |
| 554 } | 554 } |
| 555 if ((!w->Left() || w->Left()->GetColor() == kBlack) && | 555 if ((!w->Left() || w->Left()->GetColor() == kBlack) && |
| 556 (!w->Right() || w->Right()->GetColor() == kBlack)) { | 556 (!w->Right() || w->Right()->GetColor() == kBlack)) { |
| 557 // Case 2 | 557 // Case 2 |
| (...skipping 19 matching lines...) Expand all Loading... |
| 577 } | 577 } |
| 578 } else { | 578 } else { |
| 579 // Same as "then" clause with "right" and "left" | 579 // Same as "then" clause with "right" and "left" |
| 580 // exchanged. | 580 // exchanged. |
| 581 | 581 |
| 582 // Note: the text points out that w can not be null. | 582 // Note: the text points out that w can not be null. |
| 583 // The reason is not obvious from simply looking at | 583 // The reason is not obvious from simply looking at |
| 584 // the code; it comes about from the properties of the | 584 // the code; it comes about from the properties of the |
| 585 // red-black tree. | 585 // red-black tree. |
| 586 Node* w = x_parent->Left(); | 586 Node* w = x_parent->Left(); |
| 587 ASSERT(w); // x's sibling should not be null. | 587 DCHECK(w); // x's sibling should not be null. |
| 588 if (w->GetColor() == kRed) { | 588 if (w->GetColor() == kRed) { |
| 589 // Case 1 | 589 // Case 1 |
| 590 w->SetColor(kBlack); | 590 w->SetColor(kBlack); |
| 591 x_parent->SetColor(kRed); | 591 x_parent->SetColor(kRed); |
| 592 RightRotate(x_parent); | 592 RightRotate(x_parent); |
| 593 w = x_parent->Left(); | 593 w = x_parent->Left(); |
| 594 } | 594 } |
| 595 if ((!w->Right() || w->Right()->GetColor() == kBlack) && | 595 if ((!w->Right() || w->Right()->GetColor() == kBlack) && |
| 596 (!w->Left() || w->Left()->GetColor() == kBlack)) { | 596 (!w->Left() || w->Left()->GetColor() == kBlack)) { |
| 597 // Case 2 | 597 // Case 2 |
| (...skipping 188 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 786 Node* root_; | 786 Node* root_; |
| 787 bool needs_full_ordering_comparisons_; | 787 bool needs_full_ordering_comparisons_; |
| 788 #ifndef NDEBUG | 788 #ifndef NDEBUG |
| 789 bool verbose_debugging_; | 789 bool verbose_debugging_; |
| 790 #endif | 790 #endif |
| 791 }; | 791 }; |
| 792 | 792 |
| 793 } // namespace blink | 793 } // namespace blink |
| 794 | 794 |
| 795 #endif // PODRedBlackTree_h | 795 #endif // PODRedBlackTree_h |
| OLD | NEW |