1// Copyright 2010 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_SPLAY_TREE_INL_H_
29#define V8_SPLAY_TREE_INL_H_
30
31#include "splay-tree.h"
32
33namespace v8 {
34namespace internal {
35
36
37template<typename Config, class Allocator>
38SplayTree<Config, Allocator>::~SplayTree() {
39  NodeDeleter deleter;
40  ForEachNode(&deleter);
41}
42
43
44template<typename Config, class Allocator>
45bool SplayTree<Config, Allocator>::Insert(const Key& key,
46                                          Locator* locator) {
47  if (is_empty()) {
48    // If the tree is empty, insert the new node.
49    root_ = new(allocator_) Node(key, Config::NoValue());
50  } else {
51    // Splay on the key to move the last node on the search path
52    // for the key to the root of the tree.
53    Splay(key);
54    // Ignore repeated insertions with the same key.
55    int cmp = Config::Compare(key, root_->key_);
56    if (cmp == 0) {
57      locator->bind(root_);
58      return false;
59    }
60    // Insert the new node.
61    Node* node = new(allocator_) Node(key, Config::NoValue());
62    InsertInternal(cmp, node);
63  }
64  locator->bind(root_);
65  return true;
66}
67
68
69template<typename Config, class Allocator>
70void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
71  if (cmp > 0) {
72    node->left_ = root_;
73    node->right_ = root_->right_;
74    root_->right_ = NULL;
75  } else {
76    node->right_ = root_;
77    node->left_ = root_->left_;
78    root_->left_ = NULL;
79  }
80  root_ = node;
81}
82
83
84template<typename Config, class Allocator>
85bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
86  if (is_empty())
87    return false;
88  Splay(key);
89  return Config::Compare(key, root_->key_) == 0;
90}
91
92
93template<typename Config, class Allocator>
94bool SplayTree<Config, Allocator>::Contains(const Key& key) {
95  return FindInternal(key);
96}
97
98
99template<typename Config, class Allocator>
100bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
101  if (FindInternal(key)) {
102    locator->bind(root_);
103    return true;
104  } else {
105    return false;
106  }
107}
108
109
110template<typename Config, class Allocator>
111bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
112                                                        Locator* locator) {
113  if (is_empty())
114    return false;
115  // Splay on the key to move the node with the given key or the last
116  // node on the search path to the top of the tree.
117  Splay(key);
118  // Now the result is either the root node or the greatest node in
119  // the left subtree.
120  int cmp = Config::Compare(root_->key_, key);
121  if (cmp <= 0) {
122    locator->bind(root_);
123    return true;
124  } else {
125    Node* temp = root_;
126    root_ = root_->left_;
127    bool result = FindGreatest(locator);
128    root_ = temp;
129    return result;
130  }
131}
132
133
134template<typename Config, class Allocator>
135bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
136                                                        Locator* locator) {
137  if (is_empty())
138    return false;
139  // Splay on the key to move the node with the given key or the last
140  // node on the search path to the top of the tree.
141  Splay(key);
142  // Now the result is either the root node or the least node in
143  // the right subtree.
144  int cmp = Config::Compare(root_->key_, key);
145  if (cmp >= 0) {
146    locator->bind(root_);
147    return true;
148  } else {
149    Node* temp = root_;
150    root_ = root_->right_;
151    bool result = FindLeast(locator);
152    root_ = temp;
153    return result;
154  }
155}
156
157
158template<typename Config, class Allocator>
159bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
160  if (is_empty())
161    return false;
162  Node* current = root_;
163  while (current->right_ != NULL)
164    current = current->right_;
165  locator->bind(current);
166  return true;
167}
168
169
170template<typename Config, class Allocator>
171bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
172  if (is_empty())
173    return false;
174  Node* current = root_;
175  while (current->left_ != NULL)
176    current = current->left_;
177  locator->bind(current);
178  return true;
179}
180
181
182template<typename Config, class Allocator>
183bool SplayTree<Config, Allocator>::Move(const Key& old_key,
184                                        const Key& new_key) {
185  if (!FindInternal(old_key))
186    return false;
187  Node* node_to_move = root_;
188  RemoveRootNode(old_key);
189  Splay(new_key);
190  int cmp = Config::Compare(new_key, root_->key_);
191  if (cmp == 0) {
192    // A node with the target key already exists.
193    delete node_to_move;
194    return false;
195  }
196  node_to_move->key_ = new_key;
197  InsertInternal(cmp, node_to_move);
198  return true;
199}
200
201
202template<typename Config, class Allocator>
203bool SplayTree<Config, Allocator>::Remove(const Key& key) {
204  if (!FindInternal(key))
205    return false;
206  Node* node_to_remove = root_;
207  RemoveRootNode(key);
208  delete node_to_remove;
209  return true;
210}
211
212
213template<typename Config, class Allocator>
214void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
215  if (root_->left_ == NULL) {
216    // No left child, so the new tree is just the right child.
217    root_ = root_->right_;
218  } else {
219    // Left child exists.
220    Node* right = root_->right_;
221    // Make the original left child the new root.
222    root_ = root_->left_;
223    // Splay to make sure that the new root has an empty right child.
224    Splay(key);
225    // Insert the original right child as the right child of the new
226    // root.
227    root_->right_ = right;
228  }
229}
230
231
232template<typename Config, class Allocator>
233void SplayTree<Config, Allocator>::Splay(const Key& key) {
234  if (is_empty())
235    return;
236  Node dummy_node(Config::kNoKey, Config::NoValue());
237  // Create a dummy node.  The use of the dummy node is a bit
238  // counter-intuitive: The right child of the dummy node will hold
239  // the L tree of the algorithm.  The left child of the dummy node
240  // will hold the R tree of the algorithm.  Using a dummy node, left
241  // and right will always be nodes and we avoid special cases.
242  Node* dummy = &dummy_node;
243  Node* left = dummy;
244  Node* right = dummy;
245  Node* current = root_;
246  while (true) {
247    int cmp = Config::Compare(key, current->key_);
248    if (cmp < 0) {
249      if (current->left_ == NULL)
250        break;
251      if (Config::Compare(key, current->left_->key_) < 0) {
252        // Rotate right.
253        Node* temp = current->left_;
254        current->left_ = temp->right_;
255        temp->right_ = current;
256        current = temp;
257        if (current->left_ == NULL)
258          break;
259      }
260      // Link right.
261      right->left_ = current;
262      right = current;
263      current = current->left_;
264    } else if (cmp > 0) {
265      if (current->right_ == NULL)
266        break;
267      if (Config::Compare(key, current->right_->key_) > 0) {
268        // Rotate left.
269        Node* temp = current->right_;
270        current->right_ = temp->left_;
271        temp->left_ = current;
272        current = temp;
273        if (current->right_ == NULL)
274          break;
275      }
276      // Link left.
277      left->right_ = current;
278      left = current;
279      current = current->right_;
280    } else {
281      break;
282    }
283  }
284  // Assemble.
285  left->right_ = current->left_;
286  right->left_ = current->right_;
287  current->left_ = dummy->right_;
288  current->right_ = dummy->left_;
289  root_ = current;
290}
291
292
293template <typename Config, class Allocator> template <class Callback>
294void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
295  NodeToPairAdaptor<Callback> callback_adaptor(callback);
296  ForEachNode(&callback_adaptor);
297}
298
299
300template <typename Config, class Allocator> template <class Callback>
301void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
302  if (root_ == NULL) return;
303  // Pre-allocate some space for tiny trees.
304  List<Node*, Allocator> nodes_to_visit(10, allocator_);
305  nodes_to_visit.Add(root_, allocator_);
306  int pos = 0;
307  while (pos < nodes_to_visit.length()) {
308    Node* node = nodes_to_visit[pos++];
309    if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_);
310    if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_);
311    callback->Call(node);
312  }
313}
314
315
316} }  // namespace v8::internal
317
318#endif  // V8_SPLAY_TREE_INL_H_
319