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 <vector>
9 :
10 : #include "src/splay-tree.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 :
16 : template<typename Config, class Allocator>
17 : SplayTree<Config, Allocator>::~SplayTree() {
18 : NodeDeleter deleter;
19 2652 : ForEachNode(&deleter);
20 2652 : }
21 :
22 :
23 : template<typename Config, class Allocator>
24 163721 : bool SplayTree<Config, Allocator>::Insert(const Key& key,
25 : Locator* locator) {
26 163721 : if (is_empty()) {
27 : // If the tree is empty, insert the new node.
28 5304 : 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 161069 : Splay(key);
33 : // Ignore repeated insertions with the same key.
34 161069 : int cmp = Config::Compare(key, root_->key_);
35 161069 : if (cmp == 0) {
36 : locator->bind(root_);
37 0 : return false;
38 : }
39 : // Insert the new node.
40 161069 : Node* node = new(allocator_) Node(key, Config::NoValue());
41 : InsertInternal(cmp, node);
42 : }
43 163721 : locator->bind(root_);
44 163721 : return true;
45 : }
46 :
47 :
48 : template<typename Config, class Allocator>
49 : void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
50 161069 : if (cmp > 0) {
51 153677 : node->left_ = root_;
52 153677 : node->right_ = root_->right_;
53 153677 : root_->right_ = nullptr;
54 : } else {
55 7392 : node->right_ = root_;
56 7392 : node->left_ = root_->left_;
57 7392 : root_->left_ = nullptr;
58 : }
59 161069 : root_ = node;
60 : }
61 :
62 :
63 : template<typename Config, class Allocator>
64 1066150 : bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
65 1066150 : if (is_empty())
66 : return false;
67 1066145 : Splay(key);
68 2132290 : return Config::Compare(key, root_->key_) == 0;
69 : }
70 :
71 :
72 : template<typename Config, class Allocator>
73 : bool SplayTree<Config, Allocator>::Contains(const Key& key) {
74 : return FindInternal(key);
75 : }
76 :
77 :
78 : template<typename Config, class Allocator>
79 : bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
80 1066065 : if (FindInternal(key)) {
81 90190 : locator->bind(root_);
82 : return true;
83 : } else {
84 : return false;
85 : }
86 : }
87 :
88 :
89 : template<typename Config, class Allocator>
90 141901 : bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
91 : Locator* locator) {
92 141901 : 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 141901 : Splay(key);
97 : // Now the result is either the root node or the greatest node in
98 : // the left subtree.
99 141901 : int cmp = Config::Compare(root_->key_, key);
100 141901 : if (cmp <= 0) {
101 : locator->bind(root_);
102 111319 : return true;
103 : } else {
104 : Node* temp = root_;
105 30582 : root_ = root_->left_;
106 : bool result = FindGreatest(locator);
107 30582 : root_ = temp;
108 30582 : return result;
109 : }
110 : }
111 :
112 :
113 : template<typename Config, class Allocator>
114 163169 : bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
115 : Locator* locator) {
116 163169 : 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 163169 : Splay(key);
121 : // Now the result is either the root node or the least node in
122 : // the right subtree.
123 163169 : int cmp = Config::Compare(root_->key_, key);
124 163169 : if (cmp >= 0) {
125 : locator->bind(root_);
126 82248 : return true;
127 : } else {
128 : Node* temp = root_;
129 80921 : root_ = root_->right_;
130 : bool result = FindLeast(locator);
131 80921 : root_ = temp;
132 80921 : return result;
133 : }
134 : }
135 :
136 :
137 : template<typename Config, class Allocator>
138 : bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
139 30582 : if (is_empty())
140 : return false;
141 : Node* current = root_;
142 29130 : while (current->right_ != nullptr) current = current->right_;
143 : locator->bind(current);
144 : return true;
145 : }
146 :
147 :
148 : template<typename Config, class Allocator>
149 : bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
150 80921 : if (is_empty())
151 : return false;
152 : Node* current = root_;
153 2900 : while (current->left_ != nullptr) 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 85 : bool SplayTree<Config, Allocator>::Remove(const Key& key) {
181 85 : if (!FindInternal(key))
182 : return false;
183 0 : Node* node_to_remove = root_;
184 85 : RemoveRootNode(key);
185 : delete node_to_remove;
186 85 : return true;
187 : }
188 :
189 :
190 : template<typename Config, class Allocator>
191 85 : void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
192 85 : if (root_->left_ == nullptr) {
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 85 : Node* right = root_->right_;
198 : // Make the original left child the new root.
199 85 : root_ = root_->left_;
200 : // Splay to make sure that the new root has an empty right child.
201 85 : Splay(key);
202 : // Insert the original right child as the right child of the new
203 : // root.
204 85 : root_->right_ = right;
205 : }
206 85 : }
207 :
208 :
209 : template<typename Config, class Allocator>
210 1532369 : void SplayTree<Config, Allocator>::Splay(const Key& key) {
211 1532369 : 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 2984501 : int cmp = Config::Compare(key, current->key_);
225 2984501 : if (cmp < 0) {
226 1395108 : if (current->left_ == nullptr) break;
227 1702664 : if (Config::Compare(key, current->left_->key_) < 0) {
228 : // Rotate right.
229 : Node* temp = current->left_;
230 284681 : current->left_ = temp->right_;
231 284681 : temp->right_ = current;
232 : current = temp;
233 284681 : if (current->left_ == nullptr) break;
234 : }
235 : // Link right.
236 786321 : right->left_ = current;
237 : right = current;
238 786321 : current = current->left_;
239 1589393 : } else if (cmp > 0) {
240 1474508 : if (current->right_ == nullptr) break;
241 1335656 : if (Config::Compare(key, current->right_->key_) > 0) {
242 : // Rotate left.
243 : Node* temp = current->right_;
244 74323 : current->right_ = temp->left_;
245 74323 : temp->left_ = current;
246 : current = temp;
247 74323 : if (current->right_ == nullptr) break;
248 : }
249 : // Link left.
250 665811 : left->right_ = current;
251 : left = current;
252 665811 : current = current->right_;
253 : } else {
254 : break;
255 : }
256 : }
257 : // Assemble.
258 1532369 : left->right_ = current->left_;
259 1532369 : right->left_ = current->right_;
260 1532369 : current->left_ = dummy->right_;
261 1532369 : current->right_ = dummy->left_;
262 1532369 : root_ = current;
263 : }
264 :
265 :
266 : template <typename Config, class Allocator> template <class Callback>
267 : void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
268 : NodeToPairAdaptor<Callback> callback_adaptor(callback);
269 2587 : ForEachNode(&callback_adaptor);
270 : }
271 :
272 :
273 : template <typename Config, class Allocator> template <class Callback>
274 5239 : void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
275 7891 : if (root_ == nullptr) return;
276 : // Pre-allocate some space for tiny trees.
277 : std::vector<Node*> nodes_to_visit;
278 2587 : nodes_to_visit.push_back(root_);
279 : size_t pos = 0;
280 324669 : while (pos < nodes_to_visit.size()) {
281 322082 : Node* node = nodes_to_visit[pos++];
282 319120 : if (node->left() != nullptr) nodes_to_visit.push_back(node->left());
283 161416 : if (node->right() != nullptr) nodes_to_visit.push_back(node->right());
284 161041 : callback->Call(node);
285 : }
286 : }
287 :
288 :
289 : } // namespace internal
290 : } // namespace v8
291 :
292 : #endif // V8_SPLAY_TREE_INL_H_
|
