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
12namespace v8 {
13namespace internal {
14
15
16template<typename Config, class Allocator>
17SplayTree<Config, Allocator>::~SplayTree() {
18 NodeDeleter deleter;
19 ForEachNode(&deleter);
20}
21
22
23template<typename Config, class Allocator>
24bool 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
48template<typename Config, class Allocator>
49void 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
63template<typename Config, class Allocator>
64bool 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
72template<typename Config, class Allocator>
73bool SplayTree<Config, Allocator>::Contains(const Key& key) {
74 return FindInternal(key);
75}
76
77
78template<typename Config, class Allocator>
79bool 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
89template<typename Config, class Allocator>
90bool 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
113template<typename Config, class Allocator>
114bool 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
137template<typename Config, class Allocator>
138bool 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
148template<typename Config, class Allocator>
149bool 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
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_ == 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
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_ == 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
266template <typename Config, class Allocator> template <class Callback>
267void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
268 NodeToPairAdaptor<Callback> callback_adaptor(callback);
269 ForEachNode(&callback_adaptor);
270}
271
272
273template <typename Config, class Allocator> template <class Callback>
274void 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_
293