1// Copyright (c) 2010, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4//
5// The original file can be found at:
6// https://github.com/v8/v8/blob/master/src/splay-tree-inl.h
7
8#ifndef RUNTIME_PLATFORM_SPLAY_TREE_INL_H_
9#define RUNTIME_PLATFORM_SPLAY_TREE_INL_H_
10
11#include <vector>
12
13#include "platform/splay-tree.h"
14
15namespace dart {
16
17template <typename Config, class B, class Allocator>
18SplayTree<Config, B, Allocator>::~SplayTree() {
19 NodeDeleter deleter;
20 ForEachNode(&deleter);
21}
22
23template <typename Config, class B, class Allocator>
24bool SplayTree<Config, B, Allocator>::Insert(const Key& key, Locator* locator) {
25 if (is_empty()) {
26 // If the tree is empty, insert the new node.
27 root_ = new (allocator_) Node(key, Config::NoValue());
28 } else {
29 // Splay on the key to move the last node on the search path
30 // for the key to the root of the tree.
31 Splay(key);
32 // Ignore repeated insertions with the same key.
33 int cmp = Config::Compare(key, root_->key_);
34 if (cmp == 0) {
35 locator->bind(root_);
36 return false;
37 }
38 // Insert the new node.
39 Node* node = new (allocator_) Node(key, Config::NoValue());
40 InsertInternal(cmp, node);
41 }
42 locator->bind(root_);
43 return true;
44}
45
46template <typename Config, class B, class Allocator>
47void SplayTree<Config, B, Allocator>::InsertInternal(int cmp, Node* node) {
48 if (cmp > 0) {
49 node->left_ = root_;
50 node->right_ = root_->right_;
51 root_->right_ = nullptr;
52 } else {
53 node->right_ = root_;
54 node->left_ = root_->left_;
55 root_->left_ = nullptr;
56 }
57 root_ = node;
58}
59
60template <typename Config, class B, class Allocator>
61bool SplayTree<Config, B, Allocator>::FindInternal(const Key& key) {
62 if (is_empty()) return false;
63 Splay(key);
64 return Config::Compare(key, root_->key_) == 0;
65}
66
67template <typename Config, class B, class Allocator>
68bool SplayTree<Config, B, Allocator>::Contains(const Key& key) {
69 return FindInternal(key);
70}
71
72template <typename Config, class B, class Allocator>
73bool SplayTree<Config, B, Allocator>::Find(const Key& key, Locator* locator) {
74 if (FindInternal(key)) {
75 locator->bind(root_);
76 return true;
77 } else {
78 return false;
79 }
80}
81
82template <typename Config, class B, class Allocator>
83bool SplayTree<Config, B, Allocator>::FindGreatestLessThan(const Key& key,
84 Locator* locator) {
85 if (is_empty()) return false;
86 // Splay on the key to move the node with the given key or the last
87 // node on the search path to the top of the tree.
88 Splay(key);
89 // Now the result is either the root node or the greatest node in
90 // the left subtree.
91 int cmp = Config::Compare(root_->key_, key);
92 if (cmp <= 0) {
93 locator->bind(root_);
94 return true;
95 } else {
96 Node* temp = root_;
97 root_ = root_->left_;
98 bool result = FindGreatest(locator);
99 root_ = temp;
100 return result;
101 }
102}
103
104template <typename Config, class B, class Allocator>
105bool SplayTree<Config, B, Allocator>::FindLeastGreaterThan(const Key& key,
106 Locator* locator) {
107 if (is_empty()) 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 least node in
112 // the right 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_->right_;
120 bool result = FindLeast(locator);
121 root_ = temp;
122 return result;
123 }
124}
125
126template <typename Config, class B, class Allocator>
127bool SplayTree<Config, B, Allocator>::FindGreatest(Locator* locator) {
128 if (is_empty()) return false;
129 Node* current = root_;
130 while (current->right_ != nullptr)
131 current = current->right_;
132 locator->bind(current);
133 return true;
134}
135
136template <typename Config, class B, class Allocator>
137bool SplayTree<Config, B, Allocator>::FindLeast(Locator* locator) {
138 if (is_empty()) return false;
139 Node* current = root_;
140 while (current->left_ != nullptr)
141 current = current->left_;
142 locator->bind(current);
143 return true;
144}
145
146template <typename Config, class B, class Allocator>
147bool SplayTree<Config, B, Allocator>::Move(const Key& old_key,
148 const Key& new_key) {
149 if (!FindInternal(old_key)) return false;
150 Node* node_to_move = root_;
151 RemoveRootNode(old_key);
152 Splay(new_key);
153 int cmp = Config::Compare(new_key, root_->key_);
154 if (cmp == 0) {
155 // A node with the target key already exists.
156 delete node_to_move;
157 return false;
158 }
159 node_to_move->key_ = new_key;
160 InsertInternal(cmp, node_to_move);
161 return true;
162}
163
164template <typename Config, class B, class Allocator>
165bool SplayTree<Config, B, Allocator>::Remove(const Key& key) {
166 if (!FindInternal(key)) return false;
167 Node* node_to_remove = root_;
168 RemoveRootNode(key);
169 delete node_to_remove;
170 return true;
171}
172
173template <typename Config, class B, class Allocator>
174void SplayTree<Config, B, Allocator>::RemoveRootNode(const Key& key) {
175 if (root_->left_ == nullptr) {
176 // No left child, so the new tree is just the right child.
177 root_ = root_->right_;
178 } else {
179 // Left child exists.
180 Node* right = root_->right_;
181 // Make the original left child the new root.
182 root_ = root_->left_;
183 // Splay to make sure that the new root has an empty right child.
184 Splay(key);
185 // Insert the original right child as the right child of the new
186 // root.
187 root_->right_ = right;
188 }
189}
190
191template <typename Config, class B, class Allocator>
192void SplayTree<Config, B, Allocator>::Splay(const Key& key) {
193 if (is_empty()) return;
194 Node dummy_node(Config::kNoKey, Config::NoValue());
195 // Create a dummy node. The use of the dummy node is a bit
196 // counter-intuitive: The right child of the dummy node will hold
197 // the L tree of the algorithm. The left child of the dummy node
198 // will hold the R tree of the algorithm. Using a dummy node, left
199 // and right will always be nodes and we avoid special cases.
200 Node* dummy = &dummy_node;
201 Node* left = dummy;
202 Node* right = dummy;
203 Node* current = root_;
204 while (true) {
205 int cmp = Config::Compare(key, current->key_);
206 if (cmp < 0) {
207 if (current->left_ == nullptr) break;
208 if (Config::Compare(key, current->left_->key_) < 0) {
209 // Rotate right.
210 Node* temp = current->left_;
211 current->left_ = temp->right_;
212 temp->right_ = current;
213 current = temp;
214 if (current->left_ == nullptr) break;
215 }
216 // Link right.
217 right->left_ = current;
218 right = current;
219 current = current->left_;
220 } else if (cmp > 0) {
221 if (current->right_ == nullptr) break;
222 if (Config::Compare(key, current->right_->key_) > 0) {
223 // Rotate left.
224 Node* temp = current->right_;
225 current->right_ = temp->left_;
226 temp->left_ = current;
227 current = temp;
228 if (current->right_ == nullptr) break;
229 }
230 // Link left.
231 left->right_ = current;
232 left = current;
233 current = current->right_;
234 } else {
235 break;
236 }
237 }
238 // Assemble.
239 left->right_ = current->left_;
240 right->left_ = current->right_;
241 current->left_ = dummy->right_;
242 current->right_ = dummy->left_;
243 root_ = current;
244}
245
246template <typename Config, class B, class Allocator>
247template <class Callback>
248void SplayTree<Config, B, Allocator>::ForEach(Callback* callback) {
249 NodeToPairAdaptor<Callback> callback_adaptor(callback);
250 ForEachNode(&callback_adaptor);
251}
252
253template <typename Config, class B, class Allocator>
254template <class Callback>
255void SplayTree<Config, B, Allocator>::ForEachNode(Callback* callback) {
256 if (root_ == nullptr) return;
257 // Pre-allocate some space for tiny trees.
258 std::vector<Node*> nodes_to_visit;
259 nodes_to_visit.push_back(root_);
260 size_t pos = 0;
261 while (pos < nodes_to_visit.size()) {
262 Node* node = nodes_to_visit[pos++];
263 if (node->left() != nullptr) nodes_to_visit.push_back(node->left());
264 if (node->right() != nullptr) nodes_to_visit.push_back(node->right());
265 callback->Call(node);
266 }
267}
268
269} // namespace dart
270
271#endif // RUNTIME_PLATFORM_SPLAY_TREE_INL_H_
272