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
10 namespace v8 {
11 namespace internal {
12
13
14 template<typename Config, class Allocator>
~SplayTree()15 SplayTree<Config, Allocator>::~SplayTree() {
16 NodeDeleter deleter;
17 ForEachNode(&deleter);
18 }
19
20
21 template<typename Config, class Allocator>
Insert(const Key & key,Locator * locator)22 bool 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
46 template<typename Config, class Allocator>
InsertInternal(int cmp,Node * node)47 void 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
61 template<typename Config, class Allocator>
FindInternal(const Key & key)62 bool 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
70 template<typename Config, class Allocator>
Contains(const Key & key)71 bool SplayTree<Config, Allocator>::Contains(const Key& key) {
72 return FindInternal(key);
73 }
74
75
76 template<typename Config, class Allocator>
Find(const Key & key,Locator * locator)77 bool 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
87 template<typename Config, class Allocator>
FindGreatestLessThan(const Key & key,Locator * locator)88 bool 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
111 template<typename Config, class Allocator>
FindLeastGreaterThan(const Key & key,Locator * locator)112 bool 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
135 template<typename Config, class Allocator>
FindGreatest(Locator * locator)136 bool 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
147 template<typename Config, class Allocator>
FindLeast(Locator * locator)148 bool 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
159 template<typename Config, class Allocator>
Move(const Key & old_key,const Key & new_key)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>
Remove(const Key & key)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>
RemoveRootNode(const Key & key)191 void 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
209 template<typename Config, class Allocator>
Splay(const Key & key)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_ == 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
270 template <typename Config, class Allocator> template <class Callback>
ForEach(Callback * callback)271 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
272 NodeToPairAdaptor<Callback> callback_adaptor(callback);
273 ForEachNode(&callback_adaptor);
274 }
275
276
277 template <typename Config, class Allocator> template <class Callback>
ForEachNode(Callback * callback)278 void 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 internal
294 } // namespace v8
295
296 #endif // V8_SPLAY_TREE_INL_H_
297