diff options
Diffstat (limited to 'V8Binding/v8/src/zone-inl.h')
| -rw-r--r-- | V8Binding/v8/src/zone-inl.h | 217 |
1 files changed, 217 insertions, 0 deletions
diff --git a/V8Binding/v8/src/zone-inl.h b/V8Binding/v8/src/zone-inl.h index 9af6251..b3141a4 100644 --- a/V8Binding/v8/src/zone-inl.h +++ b/V8Binding/v8/src/zone-inl.h @@ -68,6 +68,223 @@ void Zone::adjust_segment_bytes_allocated(int delta) { } +template <typename C> +bool ZoneSplayTree<C>::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 <typename C> +bool ZoneSplayTree<C>::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 <typename C> +bool ZoneSplayTree<C>::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 <typename C> +bool ZoneSplayTree<C>::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 <typename C> +bool ZoneSplayTree<C>::FindGreatest(Locator* locator) { + if (is_empty()) + return false; + Node* current = root_; + while (current->right_ != NULL) + current = current->right_; + locator->bind(current); + return true; +} + + +template <typename C> +bool ZoneSplayTree<C>::FindLeast(Locator* locator) { + if (is_empty()) + return false; + Node* current = root_; + while (current->left_ != NULL) + current = current->left_; + locator->bind(current); + return true; +} + + +template <typename C> +bool ZoneSplayTree<C>::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 <typename C> +void ZoneSplayTree<C>::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 <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); +} + + } } // namespace v8::internal #endif // V8_ZONE_INL_H_ |