]>
Commit | Line | Data |
---|---|---|
9a0882ef | 1 | // Splay tree utilities -*- C++ -*- |
a945c346 | 2 | // Copyright (C) 2020-2024 Free Software Foundation, Inc. |
9a0882ef RS |
3 | // |
4 | // This file is part of GCC. | |
5 | // | |
6 | // GCC is free software; you can redistribute it and/or modify it under | |
7 | // the terms of the GNU General Public License as published by the Free | |
8 | // Software Foundation; either version 3, or (at your option) any later | |
9 | // version. | |
10 | // | |
11 | // GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | // WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | // for more details. | |
15 | // | |
16 | // You should have received a copy of the GNU General Public License | |
17 | // along with GCC; see the file COPYING3. If not see | |
18 | // <http://www.gnu.org/licenses/>. | |
19 | ||
20 | // Implement splay tree node accessors for a class that stores its | |
21 | // two child nodes in a member variable of the form: | |
22 | // | |
23 | // Node m_children[2]; | |
24 | template<typename Node> | |
25 | class default_splay_tree_accessors | |
26 | { | |
27 | public: | |
28 | using node_type = Node; | |
29 | ||
30 | static auto | |
31 | child (node_type node, unsigned int index) | |
32 | -> decltype (node->m_children[index]) & | |
33 | { | |
34 | return node->m_children[index]; | |
35 | } | |
36 | }; | |
37 | ||
38 | // Implement splay tree node accessors for a class that stores its | |
39 | // two child nodes in a member variable of the form: | |
40 | // | |
41 | // Node m_children[2]; | |
42 | // | |
43 | // and also stores its parent node in a member variable of the form: | |
44 | // | |
45 | // Node m_parent; | |
46 | template<typename Node> | |
47 | class default_splay_tree_accessors_with_parent | |
48 | : public default_splay_tree_accessors<Node> | |
49 | { | |
50 | public: | |
51 | using node_type = Node; | |
52 | ||
53 | static auto | |
54 | parent (node_type node) -> decltype (node->m_parent) & | |
55 | { | |
56 | return node->m_parent; | |
57 | } | |
58 | }; | |
59 | ||
60 | // Base is a splay tree accessor class for nodes that have no parent field. | |
61 | // Base therefore provides a Base::child method but does not provide a | |
62 | // Base::parent method. Extend Base with dummy routines for setting the | |
63 | // parent, which is a no-op when the parent is not stored. | |
64 | template<typename Base> | |
65 | class splay_tree_accessors_without_parent : public Base | |
66 | { | |
67 | public: | |
68 | using typename Base::node_type; | |
69 | ||
70 | static void set_parent (node_type, node_type) {} | |
71 | }; | |
72 | ||
73 | // Base is splay tree accessor class for nodes that have a parent field. | |
74 | // Base therefore provides both Base::child and Base::parent methods. | |
75 | // Extend Base with routines for setting the parent. | |
76 | template<typename Base> | |
77 | class splay_tree_accessors_with_parent : public Base | |
78 | { | |
79 | public: | |
80 | using typename Base::node_type; | |
81 | ||
82 | // Record that NODE's parent is now NEW_PARENT. | |
83 | static void | |
84 | set_parent (node_type node, node_type new_parent) | |
85 | { | |
86 | Base::parent (node) = new_parent; | |
87 | } | |
88 | }; | |
89 | ||
90 | // A base class that provides some splay tree operations that are common | |
91 | // to both rooted_splay_tree and rootless_splay_tree. | |
92 | // | |
93 | // Nodes in the splay tree have type Accessors::node_type; this is | |
94 | // usually a pointer type. The Accessors class provides the following | |
95 | // static member functions for accessing nodes: | |
96 | // | |
97 | // - Accessors::child (NODE, INDEX) | |
98 | // INDEX is guaranteed to be 0 or 1. If INDEX is 0, return a reference | |
99 | // to where NODE's left child is stored, otherwise return a reference | |
100 | // to where NODE's right child is stored. | |
101 | // | |
102 | // - Accessors::set_parent (NODE, PARENT) | |
103 | // Record that NODE's parent node is now PARENT. | |
104 | template<typename Accessors> | |
105 | class base_splay_tree : protected Accessors | |
106 | { | |
107 | public: | |
108 | using typename Accessors::node_type; | |
109 | ||
110 | // INDEX is either 0 or 1. If INDEX is 0, insert CHILD immediately | |
111 | // before NODE, otherwise insert CHILD immediately after NODE. | |
112 | // | |
113 | // Complexity: O(1). | |
114 | static void insert_child (node_type node, unsigned int index, | |
115 | node_type child); | |
116 | ||
117 | // Print NODE and its child nodes to PP for debugging purposes, | |
118 | // using PRINTER (PP, N) to print the data for node N. | |
119 | template<typename Printer> | |
120 | static void print (pretty_printer *pp, node_type node, Printer printer); | |
121 | ||
122 | protected: | |
123 | using Accessors::set_parent; | |
124 | ||
125 | static node_type get_child (node_type, unsigned int); | |
126 | static void set_child (node_type, unsigned int, node_type); | |
127 | static node_type promote_child (node_type, unsigned int); | |
128 | static void promote_child (node_type, unsigned int, node_type); | |
129 | ||
130 | template<unsigned int N> | |
131 | static node_type splay_limit (node_type); | |
132 | ||
133 | static node_type remove_node_internal (node_type); | |
134 | ||
135 | template<typename Printer> | |
136 | static void print (pretty_printer *pp, node_type node, Printer printer, | |
137 | char, vec<char> &); | |
138 | }; | |
139 | ||
140 | // This class provides splay tree routines for cases in which the root | |
141 | // of the splay tree is known. It works with both nodes that store | |
142 | // their parent node and nodes that don't. | |
143 | // | |
144 | // The class is lightweight: it only contains a single root node. | |
145 | template<typename Accessors> | |
146 | class rooted_splay_tree : public base_splay_tree<Accessors> | |
147 | { | |
148 | using parent = base_splay_tree<Accessors>; | |
149 | ||
150 | public: | |
151 | using typename Accessors::node_type; | |
152 | ||
153 | protected: | |
154 | // The root of the splay tree, or node_type () if the tree is empty. | |
155 | node_type m_root; | |
156 | ||
157 | public: | |
158 | rooted_splay_tree () : m_root () {} | |
159 | ||
160 | // Construct a tree with the specified root node. | |
161 | rooted_splay_tree (node_type root) : m_root (root) {} | |
162 | ||
163 | // Return the root of the tree. | |
164 | node_type root () const { return m_root; } | |
165 | ||
166 | // Return true if the tree contains any nodes. | |
167 | explicit operator bool () const { return m_root; } | |
168 | ||
169 | // Dereference the root node. | |
170 | node_type operator-> () { return m_root; } | |
171 | ||
172 | // Insert NEW_NODE into the splay tree, if no equivalent node already | |
173 | // exists. For a given node N, COMPARE (N) should return: | |
174 | // | |
175 | // - a negative value if NEW_NODE should come before N | |
176 | // - zero if NEW_NODE and N are the same | |
177 | // - a positive value if NEW_NODE should come after N | |
178 | // | |
179 | // Return true if NEW_NODE was inserted. | |
180 | // | |
181 | // On return, NEW_NODE or its equivalent is the root of the tree. | |
182 | // | |
183 | // Complexity: amortized O(C log N), worst-cast O(C N), where C is | |
184 | // the complexity of the comparison. | |
185 | template<typename Comparator> | |
186 | bool insert (node_type new_node, Comparator compare); | |
187 | ||
188 | // Insert NEW_NODE into the splay tree, given that NEW_NODE is the | |
189 | // maximum node of the new tree. On return, NEW_NODE is also the | |
190 | // root of the tree. | |
191 | // | |
192 | // Complexity: O(1). | |
193 | void insert_max_node (node_type new_node); | |
194 | ||
195 | // Splice NEXT_TREE onto this one, given that all nodes in NEXT_TREE | |
196 | // are greater than the maximum node in this tree. NEXT_TREE should | |
197 | // not be used afterwards. | |
198 | // | |
199 | // Complexity: O(1) if the root of the splay tree is already the maximum | |
200 | // node. Otherwise amortized O(log N), worst-cast O(N). | |
201 | void splice_next_tree (rooted_splay_tree next_tree); | |
202 | ||
203 | // The root of the tree is currently the maximum node. Replace it | |
204 | // with NEW_NODE. | |
205 | // | |
206 | // Complexity: O(1). | |
207 | void replace_max_node_at_root (node_type new_node); | |
208 | ||
209 | // Remove the root node of the splay tree. | |
210 | // | |
211 | // Complexity: O(1) if removing the maximum or minimum node. | |
212 | // Otherwise amortized O(log N), worst-cast O(N). | |
213 | void remove_root (); | |
214 | ||
215 | // Split the left child of the current root out into a separate tree | |
216 | // and return the new tree. | |
217 | rooted_splay_tree split_before_root (); | |
218 | ||
219 | // Split the right child of the current root out into a separate tree | |
220 | // and return the new tree. | |
221 | rooted_splay_tree split_after_root (); | |
222 | ||
223 | // If the root is not the minimum node of the splay tree, bring the previous | |
224 | // node to the root and return true, otherwise return false. | |
225 | // | |
226 | // Complexity: amortized O(log N), worst-cast O(N). | |
227 | bool splay_prev_node (); | |
228 | ||
229 | // If the root is not the maximum node of the splay tree, bring the next | |
230 | // node to the root and return true, otherwise return false. | |
231 | // | |
232 | // Complexity: amortized O(log N), worst-cast O(N). | |
233 | bool splay_next_node (); | |
234 | ||
235 | // Bring the minimum node of the splay tree to the root. | |
236 | // | |
237 | // Complexity: amortized O(log N), worst-cast O(N). | |
238 | void splay_min_node (); | |
239 | ||
240 | // Bring the maximum node of the splay tree to the root. | |
241 | // | |
242 | // Complexity: amortized O(log N), worst-cast O(N). | |
243 | void splay_max_node (); | |
244 | ||
245 | // Return the minimum node of the splay tree, or node_type () if the | |
246 | // tree is empty. On return, the minimum node (if any) is also the | |
247 | // root of the tree. | |
248 | // | |
249 | // Complexity: amortized O(log N), worst-cast O(N). | |
250 | node_type min_node (); | |
251 | ||
252 | // Return the maximum node of the splay tree, or node_type () if the | |
253 | // tree is empty. On return, the maximum node (if any) is also the | |
254 | // root of the tree. | |
255 | // | |
256 | // Complexity: amortized O(log N), worst-cast O(N). | |
257 | node_type max_node (); | |
258 | ||
259 | // Search the splay tree. For a given node N, COMPARE (N) should return: | |
260 | // | |
261 | // - a negative value if N is bigger than the node being searched for | |
262 | // - zero if N is the node being searched for | |
263 | // - a positive value if N is smaller than the node being searched for | |
264 | // | |
265 | // If the node that COMPARE is looking for exists, install it as the root | |
266 | // node of the splay tree. Otherwise, arbitrarily pick either: | |
267 | // | |
268 | // - the maximum node that is smaller than the node being searched for or | |
269 | // - the minimum node that is bigger than the node being searched for | |
270 | // | |
271 | // and install that node as the root instead. | |
272 | // | |
273 | // Return the result of COMPARE for the new root. | |
274 | // | |
275 | // This form of lookup is intended for cases in which both the following | |
276 | // are true: | |
277 | // | |
278 | // (a) The work that COMPARE needs to do to detect if a node is too big | |
279 | // is the same as the work that COMPARE needs to do to detect if a | |
280 | // node is too small. (This is not true of range comparisons, | |
281 | // for example.) | |
282 | // | |
283 | // (b) COMPARE is (or might be) relatively complex. | |
284 | // | |
285 | // This form of lookup is also useful if the items being compared naturally | |
286 | // provide a <=>-style comparison result, without the result having to be | |
287 | // forced by the equivalent of a ?: expression. | |
288 | // | |
289 | // The implementation only invokes COMPARE once per node. | |
290 | // | |
291 | // Complexity: amortized O(C log N), worst-cast O(C N), where C is | |
292 | // the complexity of the comparison. | |
293 | template<typename Comparator> | |
294 | auto lookup (Comparator compare) -> decltype (compare (m_root)); | |
295 | ||
296 | // Search the splay tree. For a given node N, WANT_SOMETHING_SMALLER (N) | |
297 | // is true if N is too big and WANT_SOMETHING_BIGGER (N) is true if N | |
298 | // is too small. Both functions return false if N is the node being | |
299 | // searched for. | |
300 | // | |
301 | // If the node that is being searched for exists, install it as the root | |
302 | // node of the splay tree and return 0. Otherwise, arbitrarily choose | |
303 | // between these two options: | |
304 | // | |
305 | // - Install the maximum node that is smaller than the node being | |
306 | // searched for as the root of the splay tree and return 1. | |
307 | // | |
308 | // - Install the minimum node that is bigger than the node being | |
309 | // searched for and return -1. | |
310 | // | |
311 | // This form of lookup is intended for cases in which either of the | |
312 | // following are true: | |
313 | // | |
314 | // (a) WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER test different | |
315 | // parts of the node's data. For example, when comparing ranges, | |
316 | // WANT_SOMETHING_SMALLER would test the lower limit of the given | |
317 | // node's range while WANT_SOMETHING_BIGGER would test the upper | |
318 | // limit of the given node's range. | |
319 | // | |
320 | // (b) There is no significant overhead to calling both | |
321 | // WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER for the same node. | |
322 | // | |
323 | // Complexity: amortized O(C log N), worst-cast O(C N), where C is | |
324 | // the complexity of the comparisons. | |
325 | template<typename LeftPredicate, typename RightPredicate> | |
326 | int lookup (LeftPredicate want_something_smaller, | |
327 | RightPredicate want_something_bigger); | |
328 | ||
329 | // Keep the ability to print subtrees. | |
330 | using parent::print; | |
331 | ||
332 | // Print the tree to PP for debugging purposes, using PRINTER (PP, N) | |
333 | // to print the data for node N. | |
334 | template<typename Printer> | |
335 | void print (pretty_printer *pp, Printer printer) const; | |
336 | ||
337 | protected: | |
338 | using parent::get_child; | |
339 | using parent::set_child; | |
340 | using parent::promote_child; | |
341 | ||
342 | using parent::set_parent; | |
343 | ||
344 | template<unsigned int N> | |
345 | bool splay_neighbor (); | |
346 | }; | |
347 | ||
348 | // Provide splay tree routines for nodes of type Accessors::node_type, | |
349 | // which doesn't have a parent field. Use Accessors::child to access | |
350 | // the children of a node. | |
351 | template<typename Accessors> | |
352 | using splay_tree_without_parent | |
353 | = rooted_splay_tree<splay_tree_accessors_without_parent<Accessors>>; | |
354 | ||
355 | // A splay tree for nodes of type Node, which is usually a pointer type. | |
356 | // The child nodes are stored in a member variable: | |
357 | // | |
358 | // Node m_children[2]; | |
359 | // | |
360 | // Node does not have a parent field. | |
361 | template<typename Node> | |
362 | using default_splay_tree | |
363 | = splay_tree_without_parent<default_splay_tree_accessors<Node>>; | |
364 | ||
365 | // A simple splay tree node that stores a value of type T. | |
366 | template<typename T> | |
367 | class splay_tree_node | |
368 | { | |
369 | friend class default_splay_tree_accessors<splay_tree_node *>; | |
370 | ||
371 | public: | |
372 | splay_tree_node () = default; | |
373 | splay_tree_node (T value) : m_value (value), m_children () {} | |
374 | ||
375 | T &value () { return m_value; } | |
376 | const T &value () const { return m_value; } | |
377 | ||
378 | private: | |
379 | T m_value; | |
380 | splay_tree_node *m_children[2]; | |
381 | }; | |
382 | ||
383 | // A splay tree whose nodes hold values of type T. | |
384 | template<typename T> | |
385 | using splay_tree = default_splay_tree<splay_tree_node<T> *>; | |
386 | ||
387 | // Provide splay tree routines for cases in which the root of the tree | |
388 | // is not explicitly stored. | |
389 | // | |
390 | // The nodes of the tree have type Accessors::node_type, which is usually | |
391 | // a pointer type. The nodes have a link back to their parent. | |
392 | // | |
393 | // The Accessors class provides the following static member functions: | |
394 | // | |
395 | // - Accessors::child (NODE, INDEX) | |
396 | // INDEX is guaranteed to be 0 or 1. If INDEX is 0, return a reference | |
397 | // to where NODE's left child is stored, otherwise return a reference | |
398 | // to where NODE's right child is stored. | |
399 | // | |
400 | // - Accessors::parent (NODE) | |
401 | // Return a reference to where NODE's parent is stored. | |
402 | template<typename Accessors> | |
403 | class rootless_splay_tree | |
404 | : public base_splay_tree<splay_tree_accessors_with_parent<Accessors>> | |
405 | { | |
406 | using full_accessors = splay_tree_accessors_with_parent<Accessors>; | |
407 | using parent = base_splay_tree<full_accessors>; | |
408 | ||
409 | public: | |
410 | using rooted = rooted_splay_tree<full_accessors>; | |
411 | ||
412 | using typename Accessors::node_type; | |
413 | ||
414 | // Remove NODE from the splay tree. Return the node that replaces it, | |
415 | // or null if NODE had no children. | |
416 | // | |
417 | // Complexity: O(1) if removing the maximum or minimum node. | |
418 | // Otherwise amortized O(log N), worst-cast O(N). | |
419 | static node_type remove_node (node_type node); | |
420 | ||
421 | // Splay NODE so that it becomes the root of the splay tree. | |
422 | // | |
423 | // Complexity: amortized O(log N), worst-cast O(N). | |
424 | static void splay (node_type node); | |
425 | ||
426 | // Like splay, but take advantage of the fact that NODE is known to be | |
427 | // the minimum node in the tree. | |
428 | // | |
429 | // Complexity: amortized O(log N), worst-cast O(N). | |
430 | static void splay_known_min_node (node_type node); | |
431 | ||
432 | // Like splay, but take advantage of the fact that NODE is known to be | |
433 | // the maximum node in the tree. | |
434 | // | |
435 | // Complexity: amortized O(log N), worst-cast O(N). | |
436 | static void splay_known_max_node (node_type node); | |
437 | ||
438 | // Splay NODE while looking for an ancestor node N for which PREDICATE (N) | |
439 | // is true. If such an ancestor node exists, stop the splay operation | |
440 | // early and return PREDICATE (N). Otherwise, complete the splay operation | |
441 | // and return DEFAULT_RESULT. In the latter case, NODE is now the root of | |
442 | // the splay tree. | |
443 | // | |
444 | // Note that this routine only examines nodes that happen to be ancestors | |
445 | // of NODE. It does not search the full tree. | |
446 | // | |
447 | // Complexity: amortized O(P log N), worst-cast O(P N), where P is the | |
448 | // complexity of the predicate. | |
449 | template<typename DefaultResult, typename Predicate> | |
450 | static auto splay_and_search (node_type node, DefaultResult default_result, | |
451 | Predicate predicate) | |
452 | -> decltype (predicate (node, 0)); | |
453 | ||
454 | // NODE1 and NODE2 are known to belong to the same splay tree. Return: | |
455 | // | |
456 | // -1 if NODE1 < NODE2 | |
457 | // 0 if NODE1 == NODE2 | |
458 | // 1 if NODE1 > NODE2 | |
459 | // | |
460 | // Complexity: amortized O(log N), worst-cast O(N). | |
461 | static int compare_nodes (node_type node1, node_type node2); | |
462 | ||
463 | protected: | |
464 | using parent::get_child; | |
465 | using parent::set_child; | |
466 | using parent::promote_child; | |
467 | ||
468 | static node_type get_parent (node_type); | |
469 | using parent::set_parent; | |
470 | ||
471 | static unsigned int child_index (node_type, node_type); | |
472 | ||
473 | static int compare_nodes_one_way (node_type, node_type); | |
474 | ||
475 | template<unsigned int N> | |
476 | static void splay_known_limit (node_type); | |
477 | }; | |
478 | ||
479 | // Provide rootless splay tree routines for nodes of type Node. | |
480 | // The child nodes are stored in a member variable: | |
481 | // | |
482 | // Node m_children[2]; | |
483 | // | |
484 | // and the parent node is stored in a member variable: | |
485 | // | |
486 | // Node m_parent; | |
487 | template<typename Node> | |
488 | using default_rootless_splay_tree | |
489 | = rootless_splay_tree<default_splay_tree_accessors_with_parent<Node>>; | |
490 | ||
491 | #include "splay-tree-utils.tcc" |