| OLD | NEW |
| 1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 84 template<typename Config, class Allocator> | 84 template<typename Config, class Allocator> |
| 85 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) { | 85 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) { |
| 86 if (is_empty()) | 86 if (is_empty()) |
| 87 return false; | 87 return false; |
| 88 Splay(key); | 88 Splay(key); |
| 89 return Config::Compare(key, root_->key_) == 0; | 89 return Config::Compare(key, root_->key_) == 0; |
| 90 } | 90 } |
| 91 | 91 |
| 92 | 92 |
| 93 template<typename Config, class Allocator> | 93 template<typename Config, class Allocator> |
| 94 bool SplayTree<Config, Allocator>::Contains(const Key& key) { | |
| 95 return FindInternal(key); | |
| 96 } | |
| 97 | |
| 98 | |
| 99 template<typename Config, class Allocator> | |
| 100 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) { | 94 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) { |
| 101 if (FindInternal(key)) { | 95 if (FindInternal(key)) { |
| 102 locator->bind(root_); | 96 locator->bind(root_); |
| 103 return true; | 97 return true; |
| 104 } else { | 98 } else { |
| 105 return false; | 99 return false; |
| 106 } | 100 } |
| 107 } | 101 } |
| 108 | 102 |
| 109 | 103 |
| (...skipping 182 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 292 | 286 |
| 293 template <typename Config, class Allocator> template <class Callback> | 287 template <typename Config, class Allocator> template <class Callback> |
| 294 void SplayTree<Config, Allocator>::ForEach(Callback* callback) { | 288 void SplayTree<Config, Allocator>::ForEach(Callback* callback) { |
| 295 NodeToPairAdaptor<Callback> callback_adaptor(callback); | 289 NodeToPairAdaptor<Callback> callback_adaptor(callback); |
| 296 ForEachNode(&callback_adaptor); | 290 ForEachNode(&callback_adaptor); |
| 297 } | 291 } |
| 298 | 292 |
| 299 | 293 |
| 300 template <typename Config, class Allocator> template <class Callback> | 294 template <typename Config, class Allocator> template <class Callback> |
| 301 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) { | 295 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) { |
| 302 if (root_ == NULL) return; | |
| 303 // Pre-allocate some space for tiny trees. | 296 // Pre-allocate some space for tiny trees. |
| 304 List<Node*, Allocator> nodes_to_visit(10, allocator_); | 297 List<Node*, Allocator> nodes_to_visit(10, allocator_); |
| 305 nodes_to_visit.Add(root_, allocator_); | 298 if (root_ != NULL) nodes_to_visit.Add(root_, allocator_); |
| 306 int pos = 0; | 299 int pos = 0; |
| 307 while (pos < nodes_to_visit.length()) { | 300 while (pos < nodes_to_visit.length()) { |
| 308 Node* node = nodes_to_visit[pos++]; | 301 Node* node = nodes_to_visit[pos++]; |
| 309 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_); | 302 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_); |
| 310 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_); | 303 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_); |
| 311 callback->Call(node); | 304 callback->Call(node); |
| 312 } | 305 } |
| 313 } | 306 } |
| 314 | 307 |
| 315 | 308 |
| 316 } } // namespace v8::internal | 309 } } // namespace v8::internal |
| 317 | 310 |
| 318 #endif // V8_SPLAY_TREE_INL_H_ | 311 #endif // V8_SPLAY_TREE_INL_H_ |
| OLD | NEW |