| 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 27 matching lines...) Expand all Loading... |
| 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, Locator* locator) { | 45 bool SplayTree<Config, Allocator>::Insert(const Key& key, Locator* locator) { |
| 46 if (is_empty()) { | 46 if (is_empty()) { |
| 47 // If the tree is empty, insert the new node. | 47 // If the tree is empty, insert the new node. |
| 48 root_ = new Node(key, Config::kNoValue); | 48 root_ = new Node(key, Config::NoValue()); |
| 49 } else { | 49 } else { |
| 50 // Splay on the key to move the last node on the search path | 50 // Splay on the key to move the last node on the search path |
| 51 // for the key to the root of the tree. | 51 // for the key to the root of the tree. |
| 52 Splay(key); | 52 Splay(key); |
| 53 // Ignore repeated insertions with the same key. | 53 // Ignore repeated insertions with the same key. |
| 54 int cmp = Config::Compare(key, root_->key_); | 54 int cmp = Config::Compare(key, root_->key_); |
| 55 if (cmp == 0) { | 55 if (cmp == 0) { |
| 56 locator->bind(root_); | 56 locator->bind(root_); |
| 57 return false; | 57 return false; |
| 58 } | 58 } |
| 59 // Insert the new node. | 59 // Insert the new node. |
| 60 Node* node = new Node(key, Config::kNoValue); | 60 Node* node = new Node(key, Config::NoValue()); |
| 61 InsertInternal(cmp, node); | 61 InsertInternal(cmp, node); |
| 62 } | 62 } |
| 63 locator->bind(root_); | 63 locator->bind(root_); |
| 64 return true; | 64 return true; |
| 65 } | 65 } |
| 66 | 66 |
| 67 | 67 |
| 68 template<typename Config, class Allocator> | 68 template<typename Config, class Allocator> |
| 69 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { | 69 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { |
| 70 if (cmp > 0) { | 70 if (cmp > 0) { |
| (...skipping 148 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 219 // root. | 219 // root. |
| 220 root_->right_ = right; | 220 root_->right_ = right; |
| 221 } | 221 } |
| 222 } | 222 } |
| 223 | 223 |
| 224 | 224 |
| 225 template<typename Config, class Allocator> | 225 template<typename Config, class Allocator> |
| 226 void SplayTree<Config, Allocator>::Splay(const Key& key) { | 226 void SplayTree<Config, Allocator>::Splay(const Key& key) { |
| 227 if (is_empty()) | 227 if (is_empty()) |
| 228 return; | 228 return; |
| 229 Node dummy_node(Config::kNoKey, Config::kNoValue); | 229 Node dummy_node(Config::kNoKey, Config::NoValue()); |
| 230 // Create a dummy node. The use of the dummy node is a bit | 230 // Create a dummy node. The use of the dummy node is a bit |
| 231 // counter-intuitive: The right child of the dummy node will hold | 231 // counter-intuitive: The right child of the dummy node will hold |
| 232 // the L tree of the algorithm. The left child of the dummy node | 232 // the L tree of the algorithm. The left child of the dummy node |
| 233 // will hold the R tree of the algorithm. Using a dummy node, left | 233 // will hold the R tree of the algorithm. Using a dummy node, left |
| 234 // and right will always be nodes and we avoid special cases. | 234 // and right will always be nodes and we avoid special cases. |
| 235 Node* dummy = &dummy_node; | 235 Node* dummy = &dummy_node; |
| 236 Node* left = dummy; | 236 Node* left = dummy; |
| 237 Node* right = dummy; | 237 Node* right = dummy; |
| 238 Node* current = root_; | 238 Node* current = root_; |
| 239 while (true) { | 239 while (true) { |
| (...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 301 if (node->left() != NULL) nodes_to_visit.Add(node->left()); | 301 if (node->left() != NULL) nodes_to_visit.Add(node->left()); |
| 302 if (node->right() != NULL) nodes_to_visit.Add(node->right()); | 302 if (node->right() != NULL) nodes_to_visit.Add(node->right()); |
| 303 callback->Call(node); | 303 callback->Call(node); |
| 304 } | 304 } |
| 305 } | 305 } |
| 306 | 306 |
| 307 | 307 |
| 308 } } // namespace v8::internal | 308 } } // namespace v8::internal |
| 309 | 309 |
| 310 #endif // V8_SPLAY_TREE_INL_H_ | 310 #endif // V8_SPLAY_TREE_INL_H_ |
| OLD | NEW |