Revision: 2939 Author: [email protected] Date: Mon Sep 21 00:12:38 2009 Log: Eliminate recursion in ZoneSplayTree traversal.
Convert the code to be similar with JS version. Recursive traversal is dangerous as it can cause stack exhaustion on deep trees. Review URL: http://codereview.chromium.org/211024 http://code.google.com/p/v8/source/detail?r=2939 Modified: /branches/bleeding_edge/src/zone-inl.h /branches/bleeding_edge/src/zone.h ======================================= --- /branches/bleeding_edge/src/zone-inl.h Wed Jul 29 01:10:19 2009 +++ /branches/bleeding_edge/src/zone-inl.h Mon Sep 21 00:12:38 2009 @@ -276,12 +276,19 @@ } -template <typename Node, class Callback> -static void DoForEach(Node* node, Callback* callback) { - if (node == NULL) return; - DoForEach<Node, Callback>(node->left(), callback); - callback->Call(node->key(), node->value()); - DoForEach<Node, Callback>(node->right(), callback); +template <typename Config> template <class Callback> +void ZoneSplayTree<Config>::ForEach(Callback* callback) { + // Pre-allocate some space for tiny trees. + ZoneList<Node*> nodes_to_visit(10); + nodes_to_visit.Add(root_); + int pos = 0; + while (pos < nodes_to_visit.length()) { + Node* node = nodes_to_visit[pos++]; + if (node == NULL) continue; + callback->Call(node->key(), node->value()); + nodes_to_visit.Add(node->left()); + nodes_to_visit.Add(node->right()); + } } ======================================= --- /branches/bleeding_edge/src/zone.h Wed Jul 29 01:10:19 2009 +++ /branches/bleeding_edge/src/zone.h Mon Sep 21 00:12:38 2009 @@ -204,10 +204,6 @@ }; -template <typename Node, class Callback> -static void DoForEach(Node* node, Callback* callback); - - // A zone splay tree. The config type parameter encapsulates the // different configurations of a concrete splay tree: // @@ -297,9 +293,7 @@ }; template <class Callback> - void ForEach(Callback* c) { - DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c); - } + void ForEach(Callback* callback); private: Node* root_; --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
