Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Side by Side Diff: third_party/WebKit/Source/platform/PODRedBlackTree.h

Issue 2846303002: Replace ASSERT with DCHECK in platform/ (Closed)
Patch Set: rebase Created 3 years, 7 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:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/platform/LinkHash.h ('k') | third_party/WebKit/Source/platform/PluginScriptForbiddenScope.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698