From 16b34b8c6e98ca3ae195d889edbbd310ff3b0e08 Mon Sep 17 00:00:00 2001 From: "mikhail.naganov@gmail.com" Date: Tue, 2 Mar 2010 10:03:38 +0000 Subject: [PATCH] Parametrize C++ splay tree with allocator. Thus, now there is a "generic" SplayTree and its Zone-bound specialization ZoneSplayTree. This is needed for my reimplementation of profiler tree generation in C++. As generation is performed in a separate thread, Zone can't be used, because it intentionally not thread-safe. Review URL: http://codereview.chromium.org/660280 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@3990 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/globals.h | 2 + src/heap.h | 1 + src/splay-tree-inl.h | 276 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/splay-tree.h | 191 +++++++++++++++++++++++++++++++++++ src/zone-inl.h | 227 ++---------------------------------------- src/zone.cc | 1 + src/zone.h | 96 ++---------------- 7 files changed, 483 insertions(+), 311 deletions(-) create mode 100644 src/splay-tree-inl.h create mode 100644 src/splay-tree.h diff --git a/src/globals.h b/src/globals.h index 8f6f47c..3840fee 100644 --- a/src/globals.h +++ b/src/globals.h @@ -261,6 +261,8 @@ template class ScopeInfo; class Script; class Slot; class Smi; +template + class SplayTree; class Statement; class String; class Struct; diff --git a/src/heap.h b/src/heap.h index 2494f9b..4fdd208 100644 --- a/src/heap.h +++ b/src/heap.h @@ -30,6 +30,7 @@ #include +#include "splay-tree-inl.h" #include "zone-inl.h" diff --git a/src/splay-tree-inl.h b/src/splay-tree-inl.h new file mode 100644 index 0000000..16fe25e --- /dev/null +++ b/src/splay-tree-inl.h @@ -0,0 +1,276 @@ +// Copyright 2010 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_SPLAY_TREE_INL_H_ +#define V8_SPLAY_TREE_INL_H_ + +#include "splay-tree.h" + +namespace v8 { +namespace internal { + + +template +SplayTree::~SplayTree() { + NodeDeleter deleter; + ForEachNode(&deleter); +} + + +template +bool SplayTree::Insert(const Key& key, Locator* locator) { + if (is_empty()) { + // If the tree is empty, insert the new node. + root_ = new Node(key, Config::kNoValue); + } else { + // Splay on the key to move the last node on the search path + // for the key to the root of the tree. + Splay(key); + // Ignore repeated insertions with the same key. + int cmp = Config::Compare(key, root_->key_); + if (cmp == 0) { + locator->bind(root_); + return false; + } + // Insert the new node. + Node* node = new Node(key, Config::kNoValue); + if (cmp > 0) { + node->left_ = root_; + node->right_ = root_->right_; + root_->right_ = NULL; + } else { + node->right_ = root_; + node->left_ = root_->left_; + root_->left_ = NULL; + } + root_ = node; + } + locator->bind(root_); + return true; +} + + +template +bool SplayTree::Find(const Key& key, Locator* locator) { + if (is_empty()) + return false; + Splay(key); + if (Config::Compare(key, root_->key_) == 0) { + locator->bind(root_); + return true; + } else { + return false; + } +} + + +template +bool SplayTree::FindGreatestLessThan(const Key& key, + Locator* locator) { + if (is_empty()) + return false; + // Splay on the key to move the node with the given key or the last + // node on the search path to the top of the tree. + Splay(key); + // Now the result is either the root node or the greatest node in + // the left subtree. + int cmp = Config::Compare(root_->key_, key); + if (cmp <= 0) { + locator->bind(root_); + return true; + } else { + Node* temp = root_; + root_ = root_->left_; + bool result = FindGreatest(locator); + root_ = temp; + return result; + } +} + + +template +bool SplayTree::FindLeastGreaterThan(const Key& key, + Locator* locator) { + if (is_empty()) + return false; + // Splay on the key to move the node with the given key or the last + // node on the search path to the top of the tree. + Splay(key); + // Now the result is either the root node or the least node in + // the right subtree. + int cmp = Config::Compare(root_->key_, key); + if (cmp >= 0) { + locator->bind(root_); + return true; + } else { + Node* temp = root_; + root_ = root_->right_; + bool result = FindLeast(locator); + root_ = temp; + return result; + } +} + + +template +bool SplayTree::FindGreatest(Locator* locator) { + if (is_empty()) + return false; + Node* current = root_; + while (current->right_ != NULL) + current = current->right_; + locator->bind(current); + return true; +} + + +template +bool SplayTree::FindLeast(Locator* locator) { + if (is_empty()) + return false; + Node* current = root_; + while (current->left_ != NULL) + current = current->left_; + locator->bind(current); + return true; +} + + +template +bool SplayTree::Remove(const Key& key) { + // Bail if the tree is empty + if (is_empty()) + return false; + // Splay on the key to move the node with the given key to the top. + Splay(key); + // Bail if the key is not in the tree + if (Config::Compare(key, root_->key_) != 0) + return false; + if (root_->left_ == NULL) { + // No left child, so the new tree is just the right child. + root_ = root_->right_; + } else { + // Left child exists. + Node* right = root_->right_; + // Make the original left child the new root. + root_ = root_->left_; + // Splay to make sure that the new root has an empty right child. + Splay(key); + // Insert the original right child as the right child of the new + // root. + root_->right_ = right; + } + return true; +} + + +template +void SplayTree::Splay(const Key& key) { + if (is_empty()) + return; + Node dummy_node(Config::kNoKey, Config::kNoValue); + // Create a dummy node. The use of the dummy node is a bit + // counter-intuitive: The right child of the dummy node will hold + // the L tree of the algorithm. The left child of the dummy node + // will hold the R tree of the algorithm. Using a dummy node, left + // and right will always be nodes and we avoid special cases. + Node* dummy = &dummy_node; + Node* left = dummy; + Node* right = dummy; + Node* current = root_; + while (true) { + int cmp = Config::Compare(key, current->key_); + if (cmp < 0) { + if (current->left_ == NULL) + break; + if (Config::Compare(key, current->left_->key_) < 0) { + // Rotate right. + Node* temp = current->left_; + current->left_ = temp->right_; + temp->right_ = current; + current = temp; + if (current->left_ == NULL) + break; + } + // Link right. + right->left_ = current; + right = current; + current = current->left_; + } else if (cmp > 0) { + if (current->right_ == NULL) + break; + if (Config::Compare(key, current->right_->key_) > 0) { + // Rotate left. + Node* temp = current->right_; + current->right_ = temp->left_; + temp->left_ = current; + current = temp; + if (current->right_ == NULL) + break; + } + // Link left. + left->right_ = current; + left = current; + current = current->right_; + } else { + break; + } + } + // Assemble. + left->right_ = current->left_; + right->left_ = current->right_; + current->left_ = dummy->right_; + current->right_ = dummy->left_; + root_ = current; +} + + +template template +void SplayTree::ForEach(Callback* callback) { + NodeToPairAdaptor callback_adaptor(callback); + ForEachNode(&callback_adaptor); +} + + +template template +void SplayTree::ForEachNode(Callback* callback) { + // Pre-allocate some space for tiny trees. + List nodes_to_visit(10); + if (root_ != NULL) nodes_to_visit.Add(root_); + int pos = 0; + while (pos < nodes_to_visit.length()) { + Node* node = nodes_to_visit[pos++]; + if (node->left() != NULL) nodes_to_visit.Add(node->left()); + if (node->right() != NULL) nodes_to_visit.Add(node->right()); + callback->Call(node); + } +} + + +} } // namespace v8::internal + +#endif // V8_SPLAY_TREE_INL_H_ diff --git a/src/splay-tree.h b/src/splay-tree.h new file mode 100644 index 0000000..b0f415d --- /dev/null +++ b/src/splay-tree.h @@ -0,0 +1,191 @@ +// Copyright 2010 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_SPLAY_TREE_H_ +#define V8_SPLAY_TREE_H_ + +namespace v8 { +namespace internal { + + +// A splay tree. The config type parameter encapsulates the different +// configurations of a concrete splay tree: +// +// typedef Key: the key type +// typedef Value: the value type +// static const kNoKey: the dummy key used when no key is set +// static const kNoValue: the dummy value used to initialize nodes +// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function +// +// The tree is also parameterized by an allocation policy +// (Allocator). The policy is used for allocating lists in the C free +// store or the zone; see zone.h. + +// Forward defined as +// template +// class SplayTree; +template +class SplayTree { + public: + typedef typename Config::Key Key; + typedef typename Config::Value Value; + + class Locator; + + SplayTree() : root_(NULL) { } + ~SplayTree(); + + INLINE(void* operator new(size_t size)) { + return Allocator::New(static_cast(size)); + } + INLINE(void operator delete(void* p, size_t)) { return Allocator::Delete(p); } + + // Inserts the given key in this tree with the given value. Returns + // true if a node was inserted, otherwise false. If found the locator + // is enabled and provides access to the mapping for the key. + bool Insert(const Key& key, Locator* locator); + + // Looks up the key in this tree and returns true if it was found, + // otherwise false. If the node is found the locator is enabled and + // provides access to the mapping for the key. + bool Find(const Key& key, Locator* locator); + + // Finds the mapping with the greatest key less than or equal to the + // given key. + bool FindGreatestLessThan(const Key& key, Locator* locator); + + // Find the mapping with the greatest key in this tree. + bool FindGreatest(Locator* locator); + + // Finds the mapping with the least key greater than or equal to the + // given key. + bool FindLeastGreaterThan(const Key& key, Locator* locator); + + // Find the mapping with the least key in this tree. + bool FindLeast(Locator* locator); + + // Remove the node with the given key from the tree. + bool Remove(const Key& key); + + bool is_empty() { return root_ == NULL; } + + // Perform the splay operation for the given key. Moves the node with + // the given key to the top of the tree. If no node has the given + // key, the last node on the search path is moved to the top of the + // tree. + void Splay(const Key& key); + + class Node { + public: + Node(const Key& key, const Value& value) + : key_(key), + value_(value), + left_(NULL), + right_(NULL) { } + + INLINE(void* operator new(size_t size)) { + return Allocator::New(static_cast(size)); + } + INLINE(void operator delete(void* p, size_t)) { + return Allocator::Delete(p); + } + + Key key() { return key_; } + Value value() { return value_; } + Node* left() { return left_; } + Node* right() { return right_; } + private: + + friend class SplayTree; + friend class Locator; + Key key_; + Value value_; + Node* left_; + Node* right_; + }; + + // A locator provides access to a node in the tree without actually + // exposing the node. + class Locator BASE_EMBEDDED { + public: + explicit Locator(Node* node) : node_(node) { } + Locator() : node_(NULL) { } + const Key& key() { return node_->key_; } + Value& value() { return node_->value_; } + void set_value(const Value& value) { node_->value_ = value; } + inline void bind(Node* node) { node_ = node; } + private: + Node* node_; + }; + + template + void ForEach(Callback* callback); + + protected: + + // Resets tree root. Existing nodes become unreachable. + void ResetRoot() { root_ = NULL; } + + private: + + template + class NodeToPairAdaptor BASE_EMBEDDED { + public: + explicit NodeToPairAdaptor(Callback* callback) + : callback_(callback) { } + void Call(Node* node) { + callback_->Call(node->key(), node->value()); + } + + private: + Callback* callback_; + + DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor); + }; + + class NodeDeleter BASE_EMBEDDED { + public: + NodeDeleter() { } + void Call(Node* node) { delete node; } + + private: + + DISALLOW_COPY_AND_ASSIGN(NodeDeleter); + }; + + template + void ForEachNode(Callback* callback); + + Node* root_; + + DISALLOW_COPY_AND_ASSIGN(SplayTree); +}; + + +} } // namespace v8::internal + +#endif // V8_SPLAY_TREE_H_ diff --git a/src/zone-inl.h b/src/zone-inl.h index 121ba19..5893a2f 100644 --- a/src/zone-inl.h +++ b/src/zone-inl.h @@ -68,227 +68,12 @@ void Zone::adjust_segment_bytes_allocated(int delta) { } -template -bool ZoneSplayTree::Insert(const Key& key, Locator* locator) { - if (is_empty()) { - // If the tree is empty, insert the new node. - root_ = new Node(key, C::kNoValue); - } else { - // Splay on the key to move the last node on the search path - // for the key to the root of the tree. - Splay(key); - // Ignore repeated insertions with the same key. - int cmp = C::Compare(key, root_->key_); - if (cmp == 0) { - locator->bind(root_); - return false; - } - // Insert the new node. - Node* node = new Node(key, C::kNoValue); - if (cmp > 0) { - node->left_ = root_; - node->right_ = root_->right_; - root_->right_ = NULL; - } else { - node->right_ = root_; - node->left_ = root_->left_; - root_->left_ = NULL; - } - root_ = node; - } - locator->bind(root_); - return true; -} - - -template -bool ZoneSplayTree::Find(const Key& key, Locator* locator) { - if (is_empty()) - return false; - Splay(key); - if (C::Compare(key, root_->key_) == 0) { - locator->bind(root_); - return true; - } else { - return false; - } -} - - -template -bool ZoneSplayTree::FindGreatestLessThan(const Key& key, - Locator* locator) { - if (is_empty()) - return false; - // Splay on the key to move the node with the given key or the last - // node on the search path to the top of the tree. - Splay(key); - // Now the result is either the root node or the greatest node in - // the left subtree. - int cmp = C::Compare(root_->key_, key); - if (cmp <= 0) { - locator->bind(root_); - return true; - } else { - Node* temp = root_; - root_ = root_->left_; - bool result = FindGreatest(locator); - root_ = temp; - return result; - } -} - - -template -bool ZoneSplayTree::FindLeastGreaterThan(const Key& key, - Locator* locator) { - if (is_empty()) - return false; - // Splay on the key to move the node with the given key or the last - // node on the search path to the top of the tree. - Splay(key); - // Now the result is either the root node or the least node in - // the right subtree. - int cmp = C::Compare(root_->key_, key); - if (cmp >= 0) { - locator->bind(root_); - return true; - } else { - Node* temp = root_; - root_ = root_->right_; - bool result = FindLeast(locator); - root_ = temp; - return result; - } -} - - -template -bool ZoneSplayTree::FindGreatest(Locator* locator) { - if (is_empty()) - return false; - Node* current = root_; - while (current->right_ != NULL) - current = current->right_; - locator->bind(current); - return true; -} - - -template -bool ZoneSplayTree::FindLeast(Locator* locator) { - if (is_empty()) - return false; - Node* current = root_; - while (current->left_ != NULL) - current = current->left_; - locator->bind(current); - return true; -} - - -template -bool ZoneSplayTree::Remove(const Key& key) { - // Bail if the tree is empty - if (is_empty()) - return false; - // Splay on the key to move the node with the given key to the top. - Splay(key); - // Bail if the key is not in the tree - if (C::Compare(key, root_->key_) != 0) - return false; - if (root_->left_ == NULL) { - // No left child, so the new tree is just the right child. - root_ = root_->right_; - } else { - // Left child exists. - Node* right = root_->right_; - // Make the original left child the new root. - root_ = root_->left_; - // Splay to make sure that the new root has an empty right child. - Splay(key); - // Insert the original right child as the right child of the new - // root. - root_->right_ = right; - } - return true; -} - - -template -void ZoneSplayTree::Splay(const Key& key) { - if (is_empty()) - return; - Node dummy_node(C::kNoKey, C::kNoValue); - // Create a dummy node. The use of the dummy node is a bit - // counter-intuitive: The right child of the dummy node will hold - // the L tree of the algorithm. The left child of the dummy node - // will hold the R tree of the algorithm. Using a dummy node, left - // and right will always be nodes and we avoid special cases. - Node* dummy = &dummy_node; - Node* left = dummy; - Node* right = dummy; - Node* current = root_; - while (true) { - int cmp = C::Compare(key, current->key_); - if (cmp < 0) { - if (current->left_ == NULL) - break; - if (C::Compare(key, current->left_->key_) < 0) { - // Rotate right. - Node* temp = current->left_; - current->left_ = temp->right_; - temp->right_ = current; - current = temp; - if (current->left_ == NULL) - break; - } - // Link right. - right->left_ = current; - right = current; - current = current->left_; - } else if (cmp > 0) { - if (current->right_ == NULL) - break; - if (C::Compare(key, current->right_->key_) > 0) { - // Rotate left. - Node* temp = current->right_; - current->right_ = temp->left_; - temp->left_ = current; - current = temp; - if (current->right_ == NULL) - break; - } - // Link left. - left->right_ = current; - left = current; - current = current->right_; - } else { - break; - } - } - // Assemble. - left->right_ = current->left_; - right->left_ = current->right_; - current->left_ = dummy->right_; - current->right_ = dummy->left_; - root_ = current; -} - - -template template -void ZoneSplayTree::ForEach(Callback* callback) { - // Pre-allocate some space for tiny trees. - ZoneList 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()); - } +template +ZoneSplayTree::~ZoneSplayTree() { + // Reset the root to avoid unneeded iteration over all tree nodes + // in the destructor. For a zone-allocated tree, nodes will be + // freed by the Zone. + SplayTree::ResetRoot(); } diff --git a/src/zone.cc b/src/zone.cc index 33fe557..01df450 100644 --- a/src/zone.cc +++ b/src/zone.cc @@ -28,6 +28,7 @@ #include "v8.h" #include "zone-inl.h" +#include "splay-tree-inl.h" namespace v8 { namespace internal { diff --git a/src/zone.h b/src/zone.h index 0d006dd..3397356 100644 --- a/src/zone.h +++ b/src/zone.h @@ -205,98 +205,14 @@ class ZoneScope BASE_EMBEDDED { // A zone splay tree. The config type parameter encapsulates the -// different configurations of a concrete splay tree: -// -// typedef Key: the key type -// typedef Value: the value type -// static const kNoKey: the dummy key used when no key is set -// static const kNoValue: the dummy value used to initialize nodes -// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function -// +// different configurations of a concrete splay tree (see splay-tree.h). +// The tree itself and all its elements are allocated in the Zone. template -class ZoneSplayTree : public ZoneObject { +class ZoneSplayTree: public SplayTree { public: - typedef typename Config::Key Key; - typedef typename Config::Value Value; - - class Locator; - - ZoneSplayTree() : root_(NULL) { } - - // Inserts the given key in this tree with the given value. Returns - // true if a node was inserted, otherwise false. If found the locator - // is enabled and provides access to the mapping for the key. - bool Insert(const Key& key, Locator* locator); - - // Looks up the key in this tree and returns true if it was found, - // otherwise false. If the node is found the locator is enabled and - // provides access to the mapping for the key. - bool Find(const Key& key, Locator* locator); - - // Finds the mapping with the greatest key less than or equal to the - // given key. - bool FindGreatestLessThan(const Key& key, Locator* locator); - - // Find the mapping with the greatest key in this tree. - bool FindGreatest(Locator* locator); - - // Finds the mapping with the least key greater than or equal to the - // given key. - bool FindLeastGreaterThan(const Key& key, Locator* locator); - - // Find the mapping with the least key in this tree. - bool FindLeast(Locator* locator); - - // Remove the node with the given key from the tree. - bool Remove(const Key& key); - - bool is_empty() { return root_ == NULL; } - - // Perform the splay operation for the given key. Moves the node with - // the given key to the top of the tree. If no node has the given - // key, the last node on the search path is moved to the top of the - // tree. - void Splay(const Key& key); - - class Node : public ZoneObject { - public: - Node(const Key& key, const Value& value) - : key_(key), - value_(value), - left_(NULL), - right_(NULL) { } - Key key() { return key_; } - Value value() { return value_; } - Node* left() { return left_; } - Node* right() { return right_; } - private: - friend class ZoneSplayTree; - friend class Locator; - Key key_; - Value value_; - Node* left_; - Node* right_; - }; - - // A locator provides access to a node in the tree without actually - // exposing the node. - class Locator { - public: - explicit Locator(Node* node) : node_(node) { } - Locator() : node_(NULL) { } - const Key& key() { return node_->key_; } - Value& value() { return node_->value_; } - void set_value(const Value& value) { node_->value_ = value; } - inline void bind(Node* node) { node_ = node; } - private: - Node* node_; - }; - - template - void ForEach(Callback* callback); - - private: - Node* root_; + ZoneSplayTree() + : SplayTree() {} + ~ZoneSplayTree(); }; -- 2.7.4