V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
splay-tree-inl.h
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 <vector>
9 
10 #include "src/splay-tree.h"
11 
12 namespace v8 {
13 namespace internal {
14 
15 
16 template<typename Config, class Allocator>
17 SplayTree<Config, Allocator>::~SplayTree() {
18  NodeDeleter deleter;
19  ForEachNode(&deleter);
20 }
21 
22 
23 template<typename Config, class Allocator>
24 bool SplayTree<Config, Allocator>::Insert(const Key& key,
25  Locator* locator) {
26  if (is_empty()) {
27  // If the tree is empty, insert the new node.
28  root_ = new(allocator_) Node(key, Config::NoValue());
29  } else {
30  // Splay on the key to move the last node on the search path
31  // for the key to the root of the tree.
32  Splay(key);
33  // Ignore repeated insertions with the same key.
34  int cmp = Config::Compare(key, root_->key_);
35  if (cmp == 0) {
36  locator->bind(root_);
37  return false;
38  }
39  // Insert the new node.
40  Node* node = new(allocator_) Node(key, Config::NoValue());
41  InsertInternal(cmp, node);
42  }
43  locator->bind(root_);
44  return true;
45 }
46 
47 
48 template<typename Config, class Allocator>
49 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
50  if (cmp > 0) {
51  node->left_ = root_;
52  node->right_ = root_->right_;
53  root_->right_ = nullptr;
54  } else {
55  node->right_ = root_;
56  node->left_ = root_->left_;
57  root_->left_ = nullptr;
58  }
59  root_ = node;
60 }
61 
62 
63 template<typename Config, class Allocator>
64 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
65  if (is_empty())
66  return false;
67  Splay(key);
68  return Config::Compare(key, root_->key_) == 0;
69 }
70 
71 
72 template<typename Config, class Allocator>
73 bool SplayTree<Config, Allocator>::Contains(const Key& key) {
74  return FindInternal(key);
75 }
76 
77 
78 template<typename Config, class Allocator>
79 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
80  if (FindInternal(key)) {
81  locator->bind(root_);
82  return true;
83  } else {
84  return false;
85  }
86 }
87 
88 
89 template<typename Config, class Allocator>
90 bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
91  Locator* locator) {
92  if (is_empty())
93  return false;
94  // Splay on the key to move the node with the given key or the last
95  // node on the search path to the top of the tree.
96  Splay(key);
97  // Now the result is either the root node or the greatest node in
98  // the left subtree.
99  int cmp = Config::Compare(root_->key_, key);
100  if (cmp <= 0) {
101  locator->bind(root_);
102  return true;
103  } else {
104  Node* temp = root_;
105  root_ = root_->left_;
106  bool result = FindGreatest(locator);
107  root_ = temp;
108  return result;
109  }
110 }
111 
112 
113 template<typename Config, class Allocator>
114 bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
115  Locator* locator) {
116  if (is_empty())
117  return false;
118  // Splay on the key to move the node with the given key or the last
119  // node on the search path to the top of the tree.
120  Splay(key);
121  // Now the result is either the root node or the least node in
122  // the right subtree.
123  int cmp = Config::Compare(root_->key_, key);
124  if (cmp >= 0) {
125  locator->bind(root_);
126  return true;
127  } else {
128  Node* temp = root_;
129  root_ = root_->right_;
130  bool result = FindLeast(locator);
131  root_ = temp;
132  return result;
133  }
134 }
135 
136 
137 template<typename Config, class Allocator>
138 bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
139  if (is_empty())
140  return false;
141  Node* current = root_;
142  while (current->right_ != nullptr) current = current->right_;
143  locator->bind(current);
144  return true;
145 }
146 
147 
148 template<typename Config, class Allocator>
149 bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
150  if (is_empty())
151  return false;
152  Node* current = root_;
153  while (current->left_ != nullptr) current = current->left_;
154  locator->bind(current);
155  return true;
156 }
157 
158 
159 template<typename Config, class Allocator>
160 bool 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 
179 template<typename Config, class Allocator>
180 bool 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 
190 template<typename Config, class Allocator>
191 void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
192  if (root_->left_ == nullptr) {
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 
209 template<typename Config, class Allocator>
210 void 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_ == nullptr) break;
227  if (Config::Compare(key, current->left_->key_) < 0) {
228  // Rotate right.
229  Node* temp = current->left_;
230  current->left_ = temp->right_;
231  temp->right_ = current;
232  current = temp;
233  if (current->left_ == nullptr) break;
234  }
235  // Link right.
236  right->left_ = current;
237  right = current;
238  current = current->left_;
239  } else if (cmp > 0) {
240  if (current->right_ == nullptr) break;
241  if (Config::Compare(key, current->right_->key_) > 0) {
242  // Rotate left.
243  Node* temp = current->right_;
244  current->right_ = temp->left_;
245  temp->left_ = current;
246  current = temp;
247  if (current->right_ == nullptr) break;
248  }
249  // Link left.
250  left->right_ = current;
251  left = current;
252  current = current->right_;
253  } else {
254  break;
255  }
256  }
257  // Assemble.
258  left->right_ = current->left_;
259  right->left_ = current->right_;
260  current->left_ = dummy->right_;
261  current->right_ = dummy->left_;
262  root_ = current;
263 }
264 
265 
266 template <typename Config, class Allocator> template <class Callback>
267 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
268  NodeToPairAdaptor<Callback> callback_adaptor(callback);
269  ForEachNode(&callback_adaptor);
270 }
271 
272 
273 template <typename Config, class Allocator> template <class Callback>
274 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
275  if (root_ == nullptr) return;
276  // Pre-allocate some space for tiny trees.
277  std::vector<Node*> nodes_to_visit;
278  nodes_to_visit.push_back(root_);
279  size_t pos = 0;
280  while (pos < nodes_to_visit.size()) {
281  Node* node = nodes_to_visit[pos++];
282  if (node->left() != nullptr) nodes_to_visit.push_back(node->left());
283  if (node->right() != nullptr) nodes_to_visit.push_back(node->right());
284  callback->Call(node);
285  }
286 }
287 
288 
289 } // namespace internal
290 } // namespace v8
291 
292 #endif // V8_SPLAY_TREE_INL_H_
Definition: libplatform.h:13