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 |