| // Copyright 2010 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef V8_SPLAY_TREE_INL_H_ |
| #define V8_SPLAY_TREE_INL_H_ |
| |
| #include <vector> |
| |
| #include "src/splay-tree.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| |
| template<typename Config, class Allocator> |
| SplayTree<Config, Allocator>::~SplayTree() { |
| NodeDeleter deleter; |
| ForEachNode(&deleter); |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::Insert(const Key& key, |
| Locator* locator) { |
| if (is_empty()) { |
| // If the tree is empty, insert the new node. |
| 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. |
| 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(allocator_) Node(key, Config::NoValue()); |
| InsertInternal(cmp, node); |
| } |
| locator->bind(root_); |
| return true; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { |
| if (cmp > 0) { |
| node->left_ = root_; |
| node->right_ = root_->right_; |
| root_->right_ = nullptr; |
| } else { |
| node->right_ = root_; |
| node->left_ = root_->left_; |
| root_->left_ = nullptr; |
| } |
| root_ = node; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::FindInternal(const Key& key) { |
| if (is_empty()) |
| return false; |
| Splay(key); |
| return Config::Compare(key, root_->key_) == 0; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::Contains(const Key& key) { |
| return FindInternal(key); |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) { |
| if (FindInternal(key)) { |
| locator->bind(root_); |
| return true; |
| } else { |
| return false; |
| } |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::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<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::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<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) { |
| if (is_empty()) |
| return false; |
| Node* current = root_; |
| while (current->right_ != nullptr) current = current->right_; |
| locator->bind(current); |
| return true; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) { |
| if (is_empty()) |
| return false; |
| Node* current = root_; |
| while (current->left_ != nullptr) current = current->left_; |
| locator->bind(current); |
| return true; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::Move(const Key& old_key, |
| const Key& new_key) { |
| if (!FindInternal(old_key)) |
| return false; |
| Node* node_to_move = root_; |
| RemoveRootNode(old_key); |
| Splay(new_key); |
| int cmp = Config::Compare(new_key, root_->key_); |
| if (cmp == 0) { |
| // A node with the target key already exists. |
| delete node_to_move; |
| return false; |
| } |
| node_to_move->key_ = new_key; |
| InsertInternal(cmp, node_to_move); |
| return true; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| bool SplayTree<Config, Allocator>::Remove(const Key& key) { |
| if (!FindInternal(key)) |
| return false; |
| Node* node_to_remove = root_; |
| RemoveRootNode(key); |
| delete node_to_remove; |
| return true; |
| } |
| |
| |
| template<typename Config, class Allocator> |
| void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) { |
| if (root_->left_ == nullptr) { |
| // 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; |
| } |
| } |
| |
| |
| template<typename Config, class Allocator> |
| void SplayTree<Config, Allocator>::Splay(const Key& key) { |
| if (is_empty()) |
| return; |
| Node dummy_node(Config::kNoKey, Config::NoValue()); |
| // 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_ == nullptr) 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_ == nullptr) break; |
| } |
| // Link right. |
| right->left_ = current; |
| right = current; |
| current = current->left_; |
| } else if (cmp > 0) { |
| if (current->right_ == nullptr) 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_ == nullptr) 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 <typename Config, class Allocator> template <class Callback> |
| void SplayTree<Config, Allocator>::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) { |
| if (root_ == nullptr) return; |
| // Pre-allocate some space for tiny trees. |
| std::vector<Node*> nodes_to_visit; |
| nodes_to_visit.push_back(root_); |
| size_t pos = 0; |
| while (pos < nodes_to_visit.size()) { |
| Node* node = nodes_to_visit[pos++]; |
| if (node->left() != nullptr) nodes_to_visit.push_back(node->left()); |
| if (node->right() != nullptr) nodes_to_visit.push_back(node->right()); |
| callback->Call(node); |
| } |
| } |
| |
| |
| } // namespace internal |
| } // namespace v8 |
| |
| #endif // V8_SPLAY_TREE_INL_H_ |