1// Copyright 2010 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_SPLAY_TREE_INL_H_
6#define V8_SPLAY_TREE_INL_H_
7
8#include "src/splay-tree.h"
9
10namespace v8 {
11namespace internal {
12
13
14template<typename Config, class Allocator>
15SplayTree<Config, Allocator>::~SplayTree() {
16  NodeDeleter deleter;
17  ForEachNode(&deleter);
18}
19
20
21template<typename Config, class Allocator>
22bool SplayTree<Config, Allocator>::Insert(const Key& key,
23                                          Locator* locator) {
24  if (is_empty()) {
25    // If the tree is empty, insert the new node.
26    root_ = new(allocator_) Node(key, Config::NoValue());
27  } else {
28    // Splay on the key to move the last node on the search path
29    // for the key to the root of the tree.
30    Splay(key);
31    // Ignore repeated insertions with the same key.
32    int cmp = Config::Compare(key, root_->key_);
33    if (cmp == 0) {
34      locator->bind(root_);
35      return false;
36    }
37    // Insert the new node.
38    Node* node = new(allocator_) Node(key, Config::NoValue());
39    InsertInternal(cmp, node);
40  }
41  locator->bind(root_);
42  return true;
43}
44
45
46template<typename Config, class Allocator>
47void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
48  if (cmp > 0) {
49    node->left_ = root_;
50    node->right_ = root_->right_;
51    root_->right_ = NULL;
52  } else {
53    node->right_ = root_;
54    node->left_ = root_->left_;
55    root_->left_ = NULL;
56  }
57  root_ = node;
58}
59
60
61template<typename Config, class Allocator>
62bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
63  if (is_empty())
64    return false;
65  Splay(key);
66  return Config::Compare(key, root_->key_) == 0;
67}
68
69
70template<typename Config, class Allocator>
71bool SplayTree<Config, Allocator>::Contains(const Key& key) {
72  return FindInternal(key);
73}
74
75
76template<typename Config, class Allocator>
77bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
78  if (FindInternal(key)) {
79    locator->bind(root_);
80    return true;
81  } else {
82    return false;
83  }
84}
85
86
87template<typename Config, class Allocator>
88bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
89                                                        Locator* locator) {
90  if (is_empty())
91    return false;
92  // Splay on the key to move the node with the given key or the last
93  // node on the search path to the top of the tree.
94  Splay(key);
95  // Now the result is either the root node or the greatest node in
96  // the left subtree.
97  int cmp = Config::Compare(root_->key_, key);
98  if (cmp <= 0) {
99    locator->bind(root_);
100    return true;
101  } else {
102    Node* temp = root_;
103    root_ = root_->left_;
104    bool result = FindGreatest(locator);
105    root_ = temp;
106    return result;
107  }
108}
109
110
111template<typename Config, class Allocator>
112bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
113                                                        Locator* locator) {
114  if (is_empty())
115    return false;
116  // Splay on the key to move the node with the given key or the last
117  // node on the search path to the top of the tree.
118  Splay(key);
119  // Now the result is either the root node or the least node in
120  // the right subtree.
121  int cmp = Config::Compare(root_->key_, key);
122  if (cmp >= 0) {
123    locator->bind(root_);
124    return true;
125  } else {
126    Node* temp = root_;
127    root_ = root_->right_;
128    bool result = FindLeast(locator);
129    root_ = temp;
130    return result;
131  }
132}
133
134
135template<typename Config, class Allocator>
136bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
137  if (is_empty())
138    return false;
139  Node* current = root_;
140  while (current->right_ != NULL)
141    current = current->right_;
142  locator->bind(current);
143  return true;
144}
145
146
147template<typename Config, class Allocator>
148bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
149  if (is_empty())
150    return false;
151  Node* current = root_;
152  while (current->left_ != NULL)
153    current = current->left_;
154  locator->bind(current);
155  return true;
156}
157
158
159template<typename Config, class Allocator>
160bool SplayTree<Config, Allocator>::Move(const Key& old_key,
161                                        const Key& new_key) {
162  if (!FindInternal(old_key))
163    return false;
164  Node* node_to_move = root_;
165  RemoveRootNode(old_key);
166  Splay(new_key);
167  int cmp = Config::Compare(new_key, root_->key_);
168  if (cmp == 0) {
169    // A node with the target key already exists.
170    delete node_to_move;
171    return false;
172  }
173  node_to_move->key_ = new_key;
174  InsertInternal(cmp, node_to_move);
175  return true;
176}
177
178
179template<typename Config, class Allocator>
180bool SplayTree<Config, Allocator>::Remove(const Key& key) {
181  if (!FindInternal(key))
182    return false;
183  Node* node_to_remove = root_;
184  RemoveRootNode(key);
185  delete node_to_remove;
186  return true;
187}
188
189
190template<typename Config, class Allocator>
191void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
192  if (root_->left_ == NULL) {
193    // No left child, so the new tree is just the right child.
194    root_ = root_->right_;
195  } else {
196    // Left child exists.
197    Node* right = root_->right_;
198    // Make the original left child the new root.
199    root_ = root_->left_;
200    // Splay to make sure that the new root has an empty right child.
201    Splay(key);
202    // Insert the original right child as the right child of the new
203    // root.
204    root_->right_ = right;
205  }
206}
207
208
209template<typename Config, class Allocator>
210void SplayTree<Config, Allocator>::Splay(const Key& key) {
211  if (is_empty())
212    return;
213  Node dummy_node(Config::kNoKey, Config::NoValue());
214  // Create a dummy node.  The use of the dummy node is a bit
215  // counter-intuitive: The right child of the dummy node will hold
216  // the L tree of the algorithm.  The left child of the dummy node
217  // will hold the R tree of the algorithm.  Using a dummy node, left
218  // and right will always be nodes and we avoid special cases.
219  Node* dummy = &dummy_node;
220  Node* left = dummy;
221  Node* right = dummy;
222  Node* current = root_;
223  while (true) {
224    int cmp = Config::Compare(key, current->key_);
225    if (cmp < 0) {
226      if (current->left_ == NULL)
227        break;
228      if (Config::Compare(key, current->left_->key_) < 0) {
229        // Rotate right.
230        Node* temp = current->left_;
231        current->left_ = temp->right_;
232        temp->right_ = current;
233        current = temp;
234        if (current->left_ == NULL)
235          break;
236      }
237      // Link right.
238      right->left_ = current;
239      right = current;
240      current = current->left_;
241    } else if (cmp > 0) {
242      if (current->right_ == NULL)
243        break;
244      if (Config::Compare(key, current->right_->key_) > 0) {
245        // Rotate left.
246        Node* temp = current->right_;
247        current->right_ = temp->left_;
248        temp->left_ = current;
249        current = temp;
250        if (current->right_ == NULL)
251          break;
252      }
253      // Link left.
254      left->right_ = current;
255      left = current;
256      current = current->right_;
257    } else {
258      break;
259    }
260  }
261  // Assemble.
262  left->right_ = current->left_;
263  right->left_ = current->right_;
264  current->left_ = dummy->right_;
265  current->right_ = dummy->left_;
266  root_ = current;
267}
268
269
270template <typename Config, class Allocator> template <class Callback>
271void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
272  NodeToPairAdaptor<Callback> callback_adaptor(callback);
273  ForEachNode(&callback_adaptor);
274}
275
276
277template <typename Config, class Allocator> template <class Callback>
278void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
279  if (root_ == NULL) return;
280  // Pre-allocate some space for tiny trees.
281  List<Node*, Allocator> nodes_to_visit(10, allocator_);
282  nodes_to_visit.Add(root_, allocator_);
283  int pos = 0;
284  while (pos < nodes_to_visit.length()) {
285    Node* node = nodes_to_visit[pos++];
286    if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_);
287    if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_);
288    callback->Call(node);
289  }
290}
291
292
293} }  // namespace v8::internal
294
295#endif  // V8_SPLAY_TREE_INL_H_
296