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 #if 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 #if 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 |