Branch data Line data Source code
1 : : // Splay tree utilities -*- C++ -*-
2 : : // Copyright (C) 2020-2025 Free Software Foundation, Inc.
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 : 327299031 : child (node_type node, unsigned int index)
32 : : -> decltype (node->m_children[index]) &
33 : : {
34 : 53498686 : 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 : 19240 : 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 : 59481065 : set_parent (node_type node, node_type new_parent)
85 : : {
86 : 1961270 : Base::parent (node) = new_parent;
87 : 659961 : }
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 : 365480781 : rooted_splay_tree () : m_root () {}
159 : :
160 : : // Construct a tree with the specified root node.
161 : 67598312 : rooted_splay_tree (node_type root) : m_root (root) {}
162 : :
163 : : // Return the root of the tree.
164 : 7564708 : node_type root () const { return m_root; }
165 : :
166 : : // Return true if the tree contains any nodes.
167 : 434059975 : explicit operator bool () const { return m_root; }
168 : :
169 : : // Dereference the root node.
170 : 25364383 : 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. If the tree is currently non-empty,
189 : : // COMPARISON is < 0 if NEW_NODE comes immediate before the current root,
190 : : // or > 0 if NEW_NODE comes immediately after the current root.
191 : : //
192 : : // On return, NEW_NODE is the root of the tree.
193 : : //
194 : : // For example, this can be used in the construct:
195 : : //
196 : : // int comparison = tree.lookup (...);
197 : : // if (comparison != 0)
198 : : // tree.insert_relative (comparison, create_new_node ());
199 : : //
200 : : // Complexity: O(1)
201 : : void insert_relative (int comparison, node_type new_node);
202 : :
203 : : // Insert NEW_NODE into the splay tree, given that NEW_NODE is the
204 : : // maximum node of the new tree. On return, NEW_NODE is also the
205 : : // root of the tree.
206 : : //
207 : : // Complexity: O(1).
208 : : void insert_max_node (node_type new_node);
209 : :
210 : : // Splice NEXT_TREE onto this one, given that all nodes in NEXT_TREE
211 : : // are greater than the maximum node in this tree. NEXT_TREE should
212 : : // not be used afterwards.
213 : : //
214 : : // Complexity: O(1) if the root of the splay tree is already the maximum
215 : : // node. Otherwise amortized O(log N), worst-cast O(N).
216 : : void splice_next_tree (rooted_splay_tree next_tree);
217 : :
218 : : // The root of the tree is currently the maximum node. Replace it
219 : : // with NEW_NODE.
220 : : //
221 : : // Complexity: O(1).
222 : : void replace_max_node_at_root (node_type new_node);
223 : :
224 : : // Remove the root node of the splay tree.
225 : : //
226 : : // Complexity: O(1) if removing the maximum or minimum node.
227 : : // Otherwise amortized O(log N), worst-cast O(N).
228 : : void remove_root ();
229 : :
230 : : // Remove the root node of the splay tree. If the root node was not
231 : : // the maximum node, bring the next node to the root and return true.
232 : : // Return false otherwise.
233 : : //
234 : : // Complexity: O(1) if removing the maximum node. Otherwise amortized
235 : : // O(log N), worst-cast O(N).
236 : : bool remove_root_and_splay_next ();
237 : :
238 : : // Split the left child of the current root out into a separate tree
239 : : // and return the new tree.
240 : : rooted_splay_tree split_before_root ();
241 : :
242 : : // Split the right child of the current root out into a separate tree
243 : : // and return the new tree.
244 : : rooted_splay_tree split_after_root ();
245 : :
246 : : // If the root is not the minimum node of the splay tree, bring the previous
247 : : // node to the root and return true, otherwise return false.
248 : : //
249 : : // Complexity: amortized O(log N), worst-cast O(N).
250 : : bool splay_prev_node ();
251 : :
252 : : // If the root is not the maximum node of the splay tree, bring the next
253 : : // node to the root and return true, otherwise return false.
254 : : //
255 : : // Complexity: amortized O(log N), worst-cast O(N).
256 : : bool splay_next_node ();
257 : :
258 : : // Bring the minimum node of the splay tree to the root.
259 : : //
260 : : // Complexity: amortized O(log N), worst-cast O(N).
261 : : void splay_min_node ();
262 : :
263 : : // Bring the maximum node of the splay tree to the root.
264 : : //
265 : : // Complexity: amortized O(log N), worst-cast O(N).
266 : : void splay_max_node ();
267 : :
268 : : // Return the minimum node of the splay tree, or node_type () if the
269 : : // tree is empty. On return, the minimum node (if any) is also the
270 : : // root of the tree.
271 : : //
272 : : // Complexity: amortized O(log N), worst-cast O(N).
273 : : node_type min_node ();
274 : :
275 : : // Return the maximum node of the splay tree, or node_type () if the
276 : : // tree is empty. On return, the maximum node (if any) is also the
277 : : // root of the tree.
278 : : //
279 : : // Complexity: amortized O(log N), worst-cast O(N).
280 : : node_type max_node ();
281 : :
282 : : // Search the splay tree. For a given node N, COMPARE (N) should return:
283 : : //
284 : : // - a negative value if N is bigger than the node being searched for
285 : : // - zero if N is the node being searched for
286 : : // - a positive value if N is smaller than the node being searched for
287 : : //
288 : : // If the node that COMPARE is looking for exists, install it as the root
289 : : // node of the splay tree. Otherwise, arbitrarily pick either:
290 : : //
291 : : // - the maximum node that is smaller than the node being searched for or
292 : : // - the minimum node that is bigger than the node being searched for
293 : : //
294 : : // and install that node as the root instead.
295 : : //
296 : : // Return the result of COMPARE for the new root.
297 : : //
298 : : // This form of lookup is intended for cases in which both the following
299 : : // are true:
300 : : //
301 : : // (a) The work that COMPARE needs to do to detect if a node is too big
302 : : // is the same as the work that COMPARE needs to do to detect if a
303 : : // node is too small. (This is not true of range comparisons,
304 : : // for example.)
305 : : //
306 : : // (b) COMPARE is (or might be) relatively complex.
307 : : //
308 : : // This form of lookup is also useful if the items being compared naturally
309 : : // provide a <=>-style comparison result, without the result having to be
310 : : // forced by the equivalent of a ?: expression.
311 : : //
312 : : // The implementation only invokes COMPARE once per node.
313 : : //
314 : : // Complexity: amortized O(C log N), worst-cast O(C N), where C is
315 : : // the complexity of the comparison.
316 : : template<typename Comparator>
317 : : auto lookup (Comparator compare) -> decltype (compare (m_root));
318 : :
319 : : // Search the splay tree. For a given node N, WANT_SOMETHING_SMALLER (N)
320 : : // is true if N is too big and WANT_SOMETHING_BIGGER (N) is true if N
321 : : // is too small. Both functions return false if N is the node being
322 : : // searched for.
323 : : //
324 : : // If the node that is being searched for exists, install it as the root
325 : : // node of the splay tree and return 0. Otherwise, arbitrarily choose
326 : : // between these two options:
327 : : //
328 : : // - Install the maximum node that is smaller than the node being
329 : : // searched for as the root of the splay tree and return 1.
330 : : //
331 : : // - Install the minimum node that is bigger than the node being
332 : : // searched for and return -1.
333 : : //
334 : : // This form of lookup is intended for cases in which either of the
335 : : // following are true:
336 : : //
337 : : // (a) WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER test different
338 : : // parts of the node's data. For example, when comparing ranges,
339 : : // WANT_SOMETHING_SMALLER would test the lower limit of the given
340 : : // node's range while WANT_SOMETHING_BIGGER would test the upper
341 : : // limit of the given node's range.
342 : : //
343 : : // (b) There is no significant overhead to calling both
344 : : // WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER for the same node.
345 : : //
346 : : // Complexity: amortized O(C log N), worst-cast O(C N), where C is
347 : : // the complexity of the comparisons.
348 : : template<typename LeftPredicate, typename RightPredicate>
349 : : int lookup (LeftPredicate want_something_smaller,
350 : : RightPredicate want_something_bigger);
351 : :
352 : : // Like lookup, but always pick a node that is no bigger than the one
353 : : // being searched for, if such a node exists.
354 : : template<typename LeftPredicate, typename RightPredicate>
355 : : int lookup_le (LeftPredicate want_something_smaller,
356 : : RightPredicate want_something_bigger);
357 : :
358 : : // Keep the ability to print subtrees.
359 : : using parent::print;
360 : :
361 : : // Print the tree to PP for debugging purposes, using PRINTER (PP, N)
362 : : // to print the data for node N.
363 : : template<typename Printer>
364 : : void print (pretty_printer *pp, Printer printer) const;
365 : :
366 : : protected:
367 : : using parent::get_child;
368 : : using parent::set_child;
369 : : using parent::promote_child;
370 : :
371 : : using parent::set_parent;
372 : :
373 : : template<unsigned int N>
374 : : bool splay_neighbor ();
375 : : };
376 : :
377 : : // Provide splay tree routines for nodes of type Accessors::node_type,
378 : : // which doesn't have a parent field. Use Accessors::child to access
379 : : // the children of a node.
380 : : template<typename Accessors>
381 : : using splay_tree_without_parent
382 : : = rooted_splay_tree<splay_tree_accessors_without_parent<Accessors>>;
383 : :
384 : : // A splay tree for nodes of type Node, which is usually a pointer type.
385 : : // The child nodes are stored in a member variable:
386 : : //
387 : : // Node m_children[2];
388 : : //
389 : : // Node does not have a parent field.
390 : : template<typename Node>
391 : : using default_splay_tree
392 : : = splay_tree_without_parent<default_splay_tree_accessors<Node>>;
393 : :
394 : : // A simple splay tree node that stores a value of type T.
395 : : template<typename T>
396 : : class splay_tree_node
397 : : {
398 : : friend class default_splay_tree_accessors<splay_tree_node *>;
399 : :
400 : : public:
401 : : splay_tree_node () = default;
402 : 101138154 : splay_tree_node (T value) : m_value (value), m_children () {}
403 : :
404 : : T &value () { return m_value; }
405 : : const T &value () const { return m_value; }
406 : :
407 : : private:
408 : : T m_value;
409 : : splay_tree_node *m_children[2];
410 : : };
411 : :
412 : : // A splay tree whose nodes hold values of type T.
413 : : template<typename T>
414 : : using splay_tree = default_splay_tree<splay_tree_node<T> *>;
415 : :
416 : : // Provide splay tree routines for cases in which the root of the tree
417 : : // is not explicitly stored.
418 : : //
419 : : // The nodes of the tree have type Accessors::node_type, which is usually
420 : : // a pointer type. The nodes have a link back to their parent.
421 : : //
422 : : // The Accessors class provides the following static member functions:
423 : : //
424 : : // - Accessors::child (NODE, INDEX)
425 : : // INDEX is guaranteed to be 0 or 1. If INDEX is 0, return a reference
426 : : // to where NODE's left child is stored, otherwise return a reference
427 : : // to where NODE's right child is stored.
428 : : //
429 : : // - Accessors::parent (NODE)
430 : : // Return a reference to where NODE's parent is stored.
431 : : template<typename Accessors>
432 : : class rootless_splay_tree
433 : : : public base_splay_tree<splay_tree_accessors_with_parent<Accessors>>
434 : : {
435 : : using full_accessors = splay_tree_accessors_with_parent<Accessors>;
436 : : using parent = base_splay_tree<full_accessors>;
437 : :
438 : : public:
439 : : using rooted = rooted_splay_tree<full_accessors>;
440 : :
441 : : using typename Accessors::node_type;
442 : :
443 : : // Remove NODE from the splay tree. Return the node that replaces it,
444 : : // or null if NODE had no children.
445 : : //
446 : : // Complexity: O(1) if removing the maximum or minimum node.
447 : : // Otherwise amortized O(log N), worst-cast O(N).
448 : : static node_type remove_node (node_type node);
449 : :
450 : : // Splay NODE so that it becomes the root of the splay tree.
451 : : //
452 : : // Complexity: amortized O(log N), worst-cast O(N).
453 : : static void splay (node_type node);
454 : :
455 : : // Like splay, but take advantage of the fact that NODE is known to be
456 : : // the minimum node in the tree.
457 : : //
458 : : // Complexity: amortized O(log N), worst-cast O(N).
459 : : static void splay_known_min_node (node_type node);
460 : :
461 : : // Like splay, but take advantage of the fact that NODE is known to be
462 : : // the maximum node in the tree.
463 : : //
464 : : // Complexity: amortized O(log N), worst-cast O(N).
465 : : static void splay_known_max_node (node_type node);
466 : :
467 : : // Splay NODE while looking for an ancestor node N for which PREDICATE (N)
468 : : // is true. If such an ancestor node exists, stop the splay operation
469 : : // early and return PREDICATE (N). Otherwise, complete the splay operation
470 : : // and return DEFAULT_RESULT. In the latter case, NODE is now the root of
471 : : // the splay tree.
472 : : //
473 : : // Note that this routine only examines nodes that happen to be ancestors
474 : : // of NODE. It does not search the full tree.
475 : : //
476 : : // Complexity: amortized O(P log N), worst-cast O(P N), where P is the
477 : : // complexity of the predicate.
478 : : template<typename DefaultResult, typename Predicate>
479 : : static auto splay_and_search (node_type node, DefaultResult default_result,
480 : : Predicate predicate)
481 : : -> decltype (predicate (node, 0));
482 : :
483 : : // NODE1 and NODE2 are known to belong to the same splay tree. Return:
484 : : //
485 : : // -1 if NODE1 < NODE2
486 : : // 0 if NODE1 == NODE2
487 : : // 1 if NODE1 > NODE2
488 : : //
489 : : // Complexity: amortized O(log N), worst-cast O(N).
490 : : static int compare_nodes (node_type node1, node_type node2);
491 : :
492 : : protected:
493 : : using parent::get_child;
494 : : using parent::set_child;
495 : : using parent::promote_child;
496 : :
497 : : static node_type get_parent (node_type);
498 : : using parent::set_parent;
499 : :
500 : : static unsigned int child_index (node_type, node_type);
501 : :
502 : : static int compare_nodes_one_way (node_type, node_type);
503 : :
504 : : template<unsigned int N>
505 : : static void splay_known_limit (node_type);
506 : : };
507 : :
508 : : // Provide rootless splay tree routines for nodes of type Node.
509 : : // The child nodes are stored in a member variable:
510 : : //
511 : : // Node m_children[2];
512 : : //
513 : : // and the parent node is stored in a member variable:
514 : : //
515 : : // Node m_parent;
516 : : template<typename Node>
517 : : using default_rootless_splay_tree
518 : : = rootless_splay_tree<default_splay_tree_accessors_with_parent<Node>>;
519 : :
520 : : #include "splay-tree-utils.tcc"
|
