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