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
33 namespace v8 {
34 namespace internal {
35
36
37 template<typename Config, class Allocator>
~SplayTree()38 SplayTree<Config, Allocator>::~SplayTree() {
39 NodeDeleter deleter;
40 ForEachNode(&deleter);
41 }
42
43
44 template<typename Config, class Allocator>
Insert(const Key & key,Locator * locator)45 bool 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::kNoValue);
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::kNoValue);
61 InsertInternal(cmp, node);
62 }
63 locator->bind(root_);
64 return true;
65 }
66
67
68 template<typename Config, class Allocator>
InsertInternal(int cmp,Node * node)69 void 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
83 template<typename Config, class Allocator>
FindInternal(const Key & key)84 bool 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
92 template<typename Config, class Allocator>
Find(const Key & key,Locator * locator)93 bool 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
103 template<typename Config, class Allocator>
FindGreatestLessThan(const Key & key,Locator * locator)104 bool 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
127 template<typename Config, class Allocator>
FindLeastGreaterThan(const Key & key,Locator * locator)128 bool 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
151 template<typename Config, class Allocator>
FindGreatest(Locator * locator)152 bool 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
163 template<typename Config, class Allocator>
FindLeast(Locator * locator)164 bool 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
175 template<typename Config, class Allocator>
Move(const Key & old_key,const Key & new_key)176 bool 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
195 template<typename Config, class Allocator>
Remove(const Key & key)196 bool 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
206 template<typename Config, class Allocator>
RemoveRootNode(const Key & key)207 void 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
225 template<typename Config, class Allocator>
Splay(const Key & key)226 void SplayTree<Config, Allocator>::Splay(const Key& key) {
227 if (is_empty())
228 return;
229 Node dummy_node(Config::kNoKey, Config::kNoValue);
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
286 template <typename Config, class Allocator> template <class Callback>
ForEach(Callback * callback)287 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
288 NodeToPairAdaptor<Callback> callback_adaptor(callback);
289 ForEachNode(&callback_adaptor);
290 }
291
292
293 template <typename Config, class Allocator> template <class Callback>
ForEachNode(Callback * callback)294 void 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