Line data Source code
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>
15 : SplayTree<Config, Allocator>::~SplayTree() {
16 : NodeDeleter deleter;
17 3156 : ForEachNode(&deleter);
18 : }
19 :
20 :
21 : template<typename Config, class Allocator>
22 2018781 : bool SplayTree<Config, Allocator>::Insert(const Key& key,
23 0 : Locator* locator) {
24 2018781 : if (is_empty()) {
25 : // If the tree is empty, insert the new node.
26 945822 : 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 1545870 : Splay(key);
31 : // Ignore repeated insertions with the same key.
32 1545870 : int cmp = Config::Compare(key, root_->key_);
33 1545870 : if (cmp == 0) {
34 : locator->bind(root_);
35 783650 : return false;
36 : }
37 : // Insert the new node.
38 762220 : Node* node = new(allocator_) Node(key, Config::NoValue());
39 : InsertInternal(cmp, node);
40 : }
41 1235131 : locator->bind(root_);
42 1235131 : return true;
43 : }
44 :
45 :
46 : template<typename Config, class Allocator>
47 : void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
48 762220 : if (cmp > 0) {
49 390084 : node->left_ = root_;
50 390084 : node->right_ = root_->right_;
51 390084 : root_->right_ = NULL;
52 : } else {
53 372136 : node->right_ = root_;
54 372136 : node->left_ = root_->left_;
55 372136 : root_->left_ = NULL;
56 : }
57 762220 : root_ = node;
58 : }
59 :
60 :
61 : template<typename Config, class Allocator>
62 0 : bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
63 4512254 : if (is_empty())
64 : return false;
65 2075096 : Splay(key);
66 2075096 : return Config::Compare(key, root_->key_) == 0;
67 : }
68 :
69 :
70 : template<typename Config, class Allocator>
71 : bool SplayTree<Config, Allocator>::Contains(const Key& key) {
72 : return FindInternal(key);
73 : }
74 :
75 :
76 : template<typename Config, class Allocator>
77 4366399 : bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
78 4366399 : if (FindInternal(key)) {
79 1012603 : locator->bind(root_);
80 1012603 : return true;
81 : } else {
82 : return false;
83 : }
84 : }
85 :
86 :
87 : template<typename Config, class Allocator>
88 176139 : bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
89 0 : Locator* locator) {
90 176139 : 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 176139 : Splay(key);
95 : // Now the result is either the root node or the greatest node in
96 : // the left subtree.
97 176139 : int cmp = Config::Compare(root_->key_, key);
98 176139 : if (cmp <= 0) {
99 : locator->bind(root_);
100 133866 : return true;
101 : } else {
102 : Node* temp = root_;
103 42273 : root_ = root_->left_;
104 : bool result = FindGreatest(locator);
105 42273 : root_ = temp;
106 42273 : return result;
107 : }
108 : }
109 :
110 :
111 : template<typename Config, class Allocator>
112 185523 : bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
113 0 : Locator* locator) {
114 185523 : 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 185523 : Splay(key);
119 : // Now the result is either the root node or the least node in
120 : // the right subtree.
121 185523 : int cmp = Config::Compare(root_->key_, key);
122 185523 : if (cmp >= 0) {
123 : locator->bind(root_);
124 94140 : return true;
125 : } else {
126 : Node* temp = root_;
127 91383 : root_ = root_->right_;
128 : bool result = FindLeast(locator);
129 91383 : root_ = temp;
130 91383 : return result;
131 : }
132 : }
133 :
134 :
135 : template<typename Config, class Allocator>
136 : bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
137 42273 : if (is_empty())
138 : return false;
139 : Node* current = root_;
140 40626 : while (current->right_ != NULL)
141 : current = current->right_;
142 : locator->bind(current);
143 : return true;
144 : }
145 :
146 :
147 : template<typename Config, class Allocator>
148 0 : bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
149 91383 : if (is_empty())
150 : return false;
151 : Node* current = root_;
152 3904 : while (current->left_ != NULL)
153 : 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 0 : bool SplayTree<Config, Allocator>::Remove(const Key& key) {
181 0 : if (!FindInternal(key))
182 : return false;
183 0 : Node* node_to_remove = root_;
184 0 : RemoveRootNode(key);
185 : delete node_to_remove;
186 0 : return true;
187 : }
188 :
189 :
190 : template<typename Config, class Allocator>
191 0 : void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
192 0 : if (root_->left_ == NULL) {
193 : // No left child, so the new tree is just the right child.
194 0 : root_ = root_->right_;
195 : } else {
196 : // Left child exists.
197 0 : Node* right = root_->right_;
198 : // Make the original left child the new root.
199 0 : root_ = root_->left_;
200 : // Splay to make sure that the new root has an empty right child.
201 0 : Splay(key);
202 : // Insert the original right child as the right child of the new
203 : // root.
204 0 : root_->right_ = right;
205 : }
206 0 : }
207 :
208 :
209 : template<typename Config, class Allocator>
210 3982628 : void SplayTree<Config, Allocator>::Splay(const Key& key) {
211 3982628 : if (is_empty())
212 0 : 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 6253809 : int cmp = Config::Compare(key, current->key_);
225 6253809 : if (cmp < 0) {
226 1850180 : if (current->left_ == NULL)
227 : break;
228 2397244 : if (Config::Compare(key, current->left_->key_) < 0) {
229 : // Rotate right.
230 : Node* temp = current->left_;
231 472974 : current->left_ = temp->right_;
232 472974 : temp->right_ = current;
233 : current = temp;
234 472974 : if (current->left_ == NULL)
235 : break;
236 : }
237 : // Link right.
238 1132599 : right->left_ = current;
239 : right = current;
240 1132599 : current = current->left_;
241 4403629 : } else if (cmp > 0) {
242 2571787 : if (current->right_ == NULL)
243 : break;
244 2466244 : if (Config::Compare(key, current->right_->key_) > 0) {
245 : // Rotate left.
246 : Node* temp = current->right_;
247 633021 : current->right_ = temp->left_;
248 633021 : temp->left_ = current;
249 : current = temp;
250 633021 : if (current->right_ == NULL)
251 : break;
252 : }
253 : // Link left.
254 1138582 : left->right_ = current;
255 : left = current;
256 1138582 : current = current->right_;
257 : } else {
258 : break;
259 : }
260 : }
261 : // Assemble.
262 3982628 : left->right_ = current->left_;
263 3982628 : right->left_ = current->right_;
264 3982628 : current->left_ = dummy->right_;
265 3982628 : current->right_ = dummy->left_;
266 3982628 : root_ = current;
267 : }
268 :
269 :
270 : template <typename Config, class Allocator> template <class Callback>
271 : void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
272 : NodeToPairAdaptor<Callback> callback_adaptor(callback);
273 2041144 : ForEachNode(&callback_adaptor);
274 : }
275 :
276 :
277 : template <typename Config, class Allocator> template <class Callback>
278 2044300 : void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
279 3601270 : if (root_ == NULL) return;
280 : // Pre-allocate some space for tiny trees.
281 : List<Node*, Allocator> nodes_to_visit(10, allocator_);
282 487330 : nodes_to_visit.Add(root_, allocator_);
283 : int pos = 0;
284 2467104 : while (pos < nodes_to_visit.length()) {
285 4477332 : Node* node = nodes_to_visit[pos++];
286 1492444 : if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_);
287 1492444 : if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_);
288 978299 : callback->Call(node);
289 : }
290 : }
291 :
292 :
293 : } // namespace internal
294 : } // namespace v8
295 :
296 : #endif // V8_SPLAY_TREE_INL_H_
|
