| OLD | NEW |
| 1 | 1 |
| 2 /* | 2 /* |
| 3 * Copyright 2011 Google Inc. | 3 * Copyright 2011 Google Inc. |
| 4 * | 4 * |
| 5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
| 6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
| 7 */ | 7 */ |
| 8 | 8 |
| 9 | 9 |
| 10 #ifndef GrRedBlackTree_DEFINED | 10 #ifndef GrRedBlackTree_DEFINED |
| (...skipping 140 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 151 void rotateLeft(Node* n); | 151 void rotateLeft(Node* n); |
| 152 | 152 |
| 153 static Node* SuccessorNode(Node* x); | 153 static Node* SuccessorNode(Node* x); |
| 154 static Node* PredecessorNode(Node* x); | 154 static Node* PredecessorNode(Node* x); |
| 155 | 155 |
| 156 void deleteAtNode(Node* x); | 156 void deleteAtNode(Node* x); |
| 157 static void RecursiveDelete(Node* x); | 157 static void RecursiveDelete(Node* x); |
| 158 | 158 |
| 159 int onCountOf(const Node* n, const T& t) const; | 159 int onCountOf(const Node* n, const T& t) const; |
| 160 | 160 |
| 161 #if GR_DEBUG | 161 #ifdef SK_DEBUG |
| 162 void validate() const; | 162 void validate() const; |
| 163 int checkNode(Node* n, int* blackHeight) const; | 163 int checkNode(Node* n, int* blackHeight) const; |
| 164 // checks relationship between a node and its children. allowRedRed means | 164 // checks relationship between a node and its children. allowRedRed means |
| 165 // node may be in an intermediate state where a red parent has a red child. | 165 // node may be in an intermediate state where a red parent has a red child. |
| 166 bool validateChildRelations(const Node* n, bool allowRedRed) const; | 166 bool validateChildRelations(const Node* n, bool allowRedRed) const; |
| 167 // place to stick break point if validateChildRelations is failing. | 167 // place to stick break point if validateChildRelations is failing. |
| 168 bool validateChildRelationsFailed() const { return false; } | 168 bool validateChildRelationsFailed() const { return false; } |
| 169 #else | 169 #else |
| 170 void validate() const {} | 170 void validate() const {} |
| 171 #endif | 171 #endif |
| (...skipping 664 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 836 | 836 |
| 837 template <typename T, typename C> | 837 template <typename T, typename C> |
| 838 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { | 838 void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) { |
| 839 if (NULL != x) { | 839 if (NULL != x) { |
| 840 RecursiveDelete(x->fChildren[kLeft_Child]); | 840 RecursiveDelete(x->fChildren[kLeft_Child]); |
| 841 RecursiveDelete(x->fChildren[kRight_Child]); | 841 RecursiveDelete(x->fChildren[kRight_Child]); |
| 842 delete x; | 842 delete x; |
| 843 } | 843 } |
| 844 } | 844 } |
| 845 | 845 |
| 846 #if GR_DEBUG | 846 #ifdef SK_DEBUG |
| 847 template <typename T, typename C> | 847 template <typename T, typename C> |
| 848 void GrRedBlackTree<T,C>::validate() const { | 848 void GrRedBlackTree<T,C>::validate() const { |
| 849 if (fCount) { | 849 if (fCount) { |
| 850 SkASSERT(NULL == fRoot->fParent); | 850 SkASSERT(NULL == fRoot->fParent); |
| 851 SkASSERT(NULL != fFirst); | 851 SkASSERT(NULL != fFirst); |
| 852 SkASSERT(NULL != fLast); | 852 SkASSERT(NULL != fLast); |
| 853 | 853 |
| 854 SkASSERT(kBlack_Color == fRoot->fColor); | 854 SkASSERT(kBlack_Color == fRoot->fColor); |
| 855 if (1 == fCount) { | 855 if (1 == fCount) { |
| 856 SkASSERT(fFirst == fRoot); | 856 SkASSERT(fFirst == fRoot); |
| (...skipping 251 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1108 // remove all entries | 1108 // remove all entries |
| 1109 while (!tree.empty()) { | 1109 while (!tree.empty()) { |
| 1110 tree.remove(tree.begin()); | 1110 tree.remove(tree.begin()); |
| 1111 } | 1111 } |
| 1112 | 1112 |
| 1113 // test reset on empty tree. | 1113 // test reset on empty tree. |
| 1114 tree.reset(); | 1114 tree.reset(); |
| 1115 } | 1115 } |
| 1116 | 1116 |
| 1117 #endif | 1117 #endif |
| OLD | NEW |