Reviewers: Kasper Lund, Message: Kasper, I know you like splay trees a lot!
Description: 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. Please review this at http://codereview.chromium.org/211024 Affected files: M src/zone-inl.h M src/zone.h Index: src/zone-inl.h diff --git a/src/zone-inl.h b/src/zone-inl.h index b3141a4810d281e76c51e000a31584c9f0784444..121ba19b12e2cf08ece1e703540d2bc4c3453171 100644 --- a/src/zone-inl.h +++ b/src/zone-inl.h @@ -276,12 +276,19 @@ void ZoneSplayTree<C>::Splay(const Key& key) { } -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()); + } } Index: src/zone.h diff --git a/src/zone.h b/src/zone.h index cdbab3282130834bd961133fa9fbd312f5e4f65c..4e4f1d7224cdea704f0308cc0f2c6fc053c6861b 100644 --- a/src/zone.h +++ b/src/zone.h @@ -204,10 +204,6 @@ class ZoneScope BASE_EMBEDDED { }; -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 @@ class ZoneSplayTree : public ZoneObject { }; 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 -~----------~----~----~----~------~----~------~--~---
