Chromium Code Reviews| 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 18 matching lines...) Expand all Loading... | |
| 29 #define V8_SPLAY_TREE_INL_H_ | 29 #define V8_SPLAY_TREE_INL_H_ |
| 30 | 30 |
| 31 #include "splay-tree.h" | 31 #include "splay-tree.h" |
| 32 | 32 |
| 33 namespace v8 { | 33 namespace v8 { |
| 34 namespace internal { | 34 namespace internal { |
| 35 | 35 |
| 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 // Pre-allocate some space for tiny trees. Since we don't have an |
| 40 ForEachNode(&deleter); | 40 // Allocator object here, we allocate the list on the heap. |
| 41 List<Node*> nodes_to_visit(10); | |
| 42 if (root_ != NULL) nodes_to_visit.Add(root_); | |
| 43 int pos = 0; | |
| 44 while (pos < nodes_to_visit.length()) { | |
| 45 Node* node = nodes_to_visit[pos++]; | |
| 46 if (node->left() != NULL) nodes_to_visit.Add(node->left()); | |
| 47 if (node->right() != NULL) nodes_to_visit.Add(node->right()); | |
| 48 Allocator::Delete(node); | |
| 49 } | |
|
danno
2012/06/06 10:59:53
Store the allocator inside the splay tree so that
sanjoy
2012/06/06 11:43:54
Done.
| |
| 41 } | 50 } |
| 42 | 51 |
| 43 | 52 |
| 44 template<typename Config, class Allocator> | 53 template<typename Config, class Allocator> |
| 45 bool SplayTree<Config, Allocator>::Insert(const Key& key, | 54 bool SplayTree<Config, Allocator>::Insert(const Key& key, |
| 46 Locator* locator, | 55 Locator* locator, |
| 47 Allocator allocator) { | 56 Allocator allocator) { |
| 48 if (is_empty()) { | 57 if (is_empty()) { |
| 49 // If the tree is empty, insert the new node. | 58 // If the tree is empty, insert the new node. |
| 50 root_ = new(allocator) Node(key, Config::NoValue()); | 59 root_ = new(allocator) Node(key, Config::NoValue()); |
| (...skipping 228 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 279 // Assemble. | 288 // Assemble. |
| 280 left->right_ = current->left_; | 289 left->right_ = current->left_; |
| 281 right->left_ = current->right_; | 290 right->left_ = current->right_; |
| 282 current->left_ = dummy->right_; | 291 current->left_ = dummy->right_; |
| 283 current->right_ = dummy->left_; | 292 current->right_ = dummy->left_; |
| 284 root_ = current; | 293 root_ = current; |
| 285 } | 294 } |
| 286 | 295 |
| 287 | 296 |
| 288 template <typename Config, class Allocator> template <class Callback> | 297 template <typename Config, class Allocator> template <class Callback> |
| 289 void SplayTree<Config, Allocator>::ForEach(Callback* callback) { | 298 void SplayTree<Config, Allocator>::ForEach(Callback* callback, |
| 299 Allocator allocator) { | |
| 290 NodeToPairAdaptor<Callback> callback_adaptor(callback); | 300 NodeToPairAdaptor<Callback> callback_adaptor(callback); |
| 291 ForEachNode(&callback_adaptor); | 301 ForEachNode(&callback_adaptor, allocator); |
| 292 } | 302 } |
| 293 | 303 |
| 294 | 304 |
| 295 template <typename Config, class Allocator> template <class Callback> | 305 template <typename Config, class Allocator> template <class Callback> |
| 296 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback, | 306 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback, |
| 297 Allocator allocator) { | 307 Allocator allocator) { |
| 298 // Pre-allocate some space for tiny trees. | 308 // Pre-allocate some space for tiny trees. |
| 299 List<Node*, Allocator> nodes_to_visit(10); | 309 List<Node*, Allocator> nodes_to_visit(10, allocator); |
| 300 if (root_ != NULL) nodes_to_visit.Add(root_, allocator); | 310 if (root_ != NULL) nodes_to_visit.Add(root_, allocator); |
| 301 int pos = 0; | 311 int pos = 0; |
| 302 while (pos < nodes_to_visit.length()) { | 312 while (pos < nodes_to_visit.length()) { |
| 303 Node* node = nodes_to_visit[pos++]; | 313 Node* node = nodes_to_visit[pos++]; |
| 304 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator); | 314 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator); |
| 305 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator); | 315 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator); |
| 306 callback->Call(node); | 316 callback->Call(node); |
| 307 } | 317 } |
| 308 } | 318 } |
| 309 | 319 |
| 310 | 320 |
| 311 } } // namespace v8::internal | 321 } } // namespace v8::internal |
| 312 | 322 |
| 313 #endif // V8_SPLAY_TREE_INL_H_ | 323 #endif // V8_SPLAY_TREE_INL_H_ |
| OLD | NEW |