Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1119)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/splay-tree-inl.h

Issue 10448007: Split an allocation policy into an allocator and a deallocator. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Fixed the issues pointed out. Created 8 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« src/splay-tree.h ('K') | « src/splay-tree.h ('k') | src/string-stream.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/splay-tree-inl.h
diff --git a/src/splay-tree-inl.h b/src/splay-tree-inl.h
index 4640ed5b08bdda8509f01ba34ac1e2d788970b04..6abfd2dabb98d7821faa4496426c09cf2cfc7787 100644
--- a/src/splay-tree-inl.h
+++ b/src/splay-tree-inl.h
@@ -34,18 +34,20 @@ namespace v8 {
namespace internal {
-template<typename Config, class Allocator>
-SplayTree<Config, Allocator>::~SplayTree() {
- NodeDeleter deleter;
+template<typename Config, class AllocationPolicy>
+SplayTree<Config, AllocationPolicy>::~SplayTree() {
+ NodeDeleter deleter(deallocator_);
ForEachNode(&deleter);
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::Insert(const Key& key, Locator* locator) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::Insert(const Key& key,
+ Locator* locator,
+ Allocator allocator) {
if (is_empty()) {
// If the tree is empty, insert the new node.
- root_ = new Node(key, Config::NoValue());
+ root_ = new(allocator) Node(key, Config::NoValue());
} else {
// Splay on the key to move the last node on the search path
// for the key to the root of the tree.
@@ -57,7 +59,7 @@ bool SplayTree<Config, Allocator>::Insert(const Key& key, Locator* locator) {
return false;
}
// Insert the new node.
- Node* node = new Node(key, Config::NoValue());
+ Node* node = new(allocator) Node(key, Config::NoValue());
InsertInternal(cmp, node);
}
locator->bind(root_);
@@ -65,8 +67,8 @@ bool SplayTree<Config, Allocator>::Insert(const Key& key, Locator* locator) {
}
-template<typename Config, class Allocator>
-void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
+template<typename Config, class AllocationPolicy>
+void SplayTree<Config, AllocationPolicy>::InsertInternal(int cmp, Node* node) {
if (cmp > 0) {
node->left_ = root_;
node->right_ = root_->right_;
@@ -80,8 +82,8 @@ void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::FindInternal(const Key& key) {
if (is_empty())
return false;
Splay(key);
@@ -89,8 +91,9 @@ bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::Find(const Key& key,
+ Locator* locator) {
if (FindInternal(key)) {
locator->bind(root_);
return true;
@@ -100,9 +103,9 @@ bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
- Locator* locator) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::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
@@ -124,9 +127,9 @@ bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
- Locator* locator) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::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
@@ -148,8 +151,8 @@ bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::FindGreatest(Locator* locator) {
if (is_empty())
return false;
Node* current = root_;
@@ -160,8 +163,8 @@ bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::FindLeast(Locator* locator) {
if (is_empty())
return false;
Node* current = root_;
@@ -172,9 +175,9 @@ bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::Move(const Key& old_key,
- const Key& new_key) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::Move(const Key& old_key,
+ const Key& new_key) {
if (!FindInternal(old_key))
return false;
Node* node_to_move = root_;
@@ -183,7 +186,7 @@ bool SplayTree<Config, Allocator>::Move(const Key& old_key,
int cmp = Config::Compare(new_key, root_->key_);
if (cmp == 0) {
// A node with the target key already exists.
- delete node_to_move;
+ deallocator_.Delete(node_to_move);
danno 2012/05/31 11:03:36 Yikes! You never call the node's destructor this w
return false;
}
node_to_move->key_ = new_key;
@@ -192,8 +195,8 @@ bool SplayTree<Config, Allocator>::Move(const Key& old_key,
}
-template<typename Config, class Allocator>
-bool SplayTree<Config, Allocator>::Remove(const Key& key) {
+template<typename Config, class AllocationPolicy>
+bool SplayTree<Config, AllocationPolicy>::Remove(const Key& key) {
if (!FindInternal(key))
return false;
Node* node_to_remove = root_;
@@ -203,8 +206,8 @@ bool SplayTree<Config, Allocator>::Remove(const Key& key) {
}
-template<typename Config, class Allocator>
-void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
+template<typename Config, class AllocationPolicy>
+void SplayTree<Config, AllocationPolicy>::RemoveRootNode(const Key& key) {
if (root_->left_ == NULL) {
// No left child, so the new tree is just the right child.
root_ = root_->right_;
@@ -222,8 +225,8 @@ void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
}
-template<typename Config, class Allocator>
-void SplayTree<Config, Allocator>::Splay(const Key& key) {
+template<typename Config, class AllocationPolicy>
+void SplayTree<Config, AllocationPolicy>::Splay(const Key& key) {
if (is_empty())
return;
Node dummy_node(Config::kNoKey, Config::NoValue());
@@ -283,23 +286,24 @@ void SplayTree<Config, Allocator>::Splay(const Key& key) {
}
-template <typename Config, class Allocator> template <class Callback>
-void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
+template <typename Config, class AllocationPolicy> template <class Callback>
+void SplayTree<Config, AllocationPolicy>::ForEach(Callback* callback) {
NodeToPairAdaptor<Callback> callback_adaptor(callback);
ForEachNode(&callback_adaptor);
}
-template <typename Config, class Allocator> template <class Callback>
-void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
+template <typename Config, class AllocationPolicy> template <class Callback>
+void SplayTree<Config, AllocationPolicy>::ForEachNode(Callback* callback,
+ Allocator allocator) {
// Pre-allocate some space for tiny trees.
- List<Node*, Allocator> nodes_to_visit(10);
- if (root_ != NULL) nodes_to_visit.Add(root_);
+ List<Node*, AllocationPolicy> nodes_to_visit(10);
+ if (root_ != NULL) nodes_to_visit.Add(root_, allocator);
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());
+ if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator);
+ if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator);
callback->Call(node);
}
}
« src/splay-tree.h ('K') | « src/splay-tree.h ('k') | src/string-stream.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698