| 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 25 matching lines...) Expand all Loading... |
| 36 | 36 |
| 37 template<typename Config, class Allocator> | 37 template<typename Config, class Allocator> |
| 38 SplayTree<Config, Allocator>::~SplayTree() { | 38 SplayTree<Config, Allocator>::~SplayTree() { |
| 39 NodeDeleter deleter; | 39 NodeDeleter deleter; |
| 40 ForEachNode(&deleter); | 40 ForEachNode(&deleter); |
| 41 } | 41 } |
| 42 | 42 |
| 43 | 43 |
| 44 template<typename Config, class Allocator> | 44 template<typename Config, class Allocator> |
| 45 bool SplayTree<Config, Allocator>::Insert(const Key& key, | 45 bool SplayTree<Config, Allocator>::Insert(const Key& key, |
| 46 Locator* locator, | 46 Locator* locator) { |
| 47 Allocator allocator) { | |
| 48 if (is_empty()) { | 47 if (is_empty()) { |
| 49 // If the tree is empty, insert the new node. | 48 // If the tree is empty, insert the new node. |
| 50 root_ = new(allocator) Node(key, Config::NoValue()); | 49 root_ = new(allocator_) Node(key, Config::NoValue()); |
| 51 } else { | 50 } else { |
| 52 // Splay on the key to move the last node on the search path | 51 // Splay on the key to move the last node on the search path |
| 53 // for the key to the root of the tree. | 52 // for the key to the root of the tree. |
| 54 Splay(key); | 53 Splay(key); |
| 55 // Ignore repeated insertions with the same key. | 54 // Ignore repeated insertions with the same key. |
| 56 int cmp = Config::Compare(key, root_->key_); | 55 int cmp = Config::Compare(key, root_->key_); |
| 57 if (cmp == 0) { | 56 if (cmp == 0) { |
| 58 locator->bind(root_); | 57 locator->bind(root_); |
| 59 return false; | 58 return false; |
| 60 } | 59 } |
| 61 // Insert the new node. | 60 // Insert the new node. |
| 62 Node* node = new(allocator) Node(key, Config::NoValue()); | 61 Node* node = new(allocator_) Node(key, Config::NoValue()); |
| 63 InsertInternal(cmp, node); | 62 InsertInternal(cmp, node); |
| 64 } | 63 } |
| 65 locator->bind(root_); | 64 locator->bind(root_); |
| 66 return true; | 65 return true; |
| 67 } | 66 } |
| 68 | 67 |
| 69 | 68 |
| 70 template<typename Config, class Allocator> | 69 template<typename Config, class Allocator> |
| 71 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { | 70 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { |
| 72 if (cmp > 0) { | 71 if (cmp > 0) { |
| (...skipping 213 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 286 | 285 |
| 287 | 286 |
| 288 template <typename Config, class Allocator> template <class Callback> | 287 template <typename Config, class Allocator> template <class Callback> |
| 289 void SplayTree<Config, Allocator>::ForEach(Callback* callback) { | 288 void SplayTree<Config, Allocator>::ForEach(Callback* callback) { |
| 290 NodeToPairAdaptor<Callback> callback_adaptor(callback); | 289 NodeToPairAdaptor<Callback> callback_adaptor(callback); |
| 291 ForEachNode(&callback_adaptor); | 290 ForEachNode(&callback_adaptor); |
| 292 } | 291 } |
| 293 | 292 |
| 294 | 293 |
| 295 template <typename Config, class Allocator> template <class Callback> | 294 template <typename Config, class Allocator> template <class Callback> |
| 296 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback, | 295 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) { |
| 297 Allocator allocator) { | |
| 298 // Pre-allocate some space for tiny trees. | 296 // Pre-allocate some space for tiny trees. |
| 299 List<Node*, Allocator> nodes_to_visit(10); | 297 List<Node*, Allocator> nodes_to_visit(10, allocator_); |
| 300 if (root_ != NULL) nodes_to_visit.Add(root_, allocator); | 298 if (root_ != NULL) nodes_to_visit.Add(root_, allocator_); |
| 301 int pos = 0; | 299 int pos = 0; |
| 302 while (pos < nodes_to_visit.length()) { | 300 while (pos < nodes_to_visit.length()) { |
| 303 Node* node = nodes_to_visit[pos++]; | 301 Node* node = nodes_to_visit[pos++]; |
| 304 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator); | 302 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_); |
| 305 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator); | 303 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_); |
| 306 callback->Call(node); | 304 callback->Call(node); |
| 307 } | 305 } |
| 308 } | 306 } |
| 309 | 307 |
| 310 | 308 |
| 311 } } // namespace v8::internal | 309 } } // namespace v8::internal |
| 312 | 310 |
| 313 #endif // V8_SPLAY_TREE_INL_H_ | 311 #endif // V8_SPLAY_TREE_INL_H_ |
| OLD | NEW |