1 // Splay tree utilities -*- C++ -*-
2 // Copyright (C) 2020-2025 Free Software Foundation, Inc.
4 // This file is part of GCC.
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
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
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/>.
20 // Implement splay tree node accessors for a class that stores its
21 // two child nodes in a member variable of the form:
23 // Node m_children[2];
24 template<typename Node
>
25 class default_splay_tree_accessors
28 using node_type
= Node
;
31 child (node_type node
, unsigned int index
)
32 -> decltype (node
->m_children
[index
]) &
34 return node
->m_children
[index
];
38 // Implement splay tree node accessors for a class that stores its
39 // two child nodes in a member variable of the form:
41 // Node m_children[2];
43 // and also stores its parent node in a member variable of the form:
46 template<typename Node
>
47 class default_splay_tree_accessors_with_parent
48 : public default_splay_tree_accessors
<Node
>
51 using node_type
= Node
;
54 parent (node_type node
) -> decltype (node
->m_parent
) &
56 return node
->m_parent
;
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
68 using typename
Base::node_type
;
70 static void set_parent (node_type
, node_type
) {}
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
80 using typename
Base::node_type
;
82 // Record that NODE's parent is now NEW_PARENT.
84 set_parent (node_type node
, node_type new_parent
)
86 Base::parent (node
) = new_parent
;
90 // A base class that provides some splay tree operations that are common
91 // to both rooted_splay_tree and rootless_splay_tree.
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:
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.
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
108 using typename
Accessors::node_type
;
110 // INDEX is either 0 or 1. If INDEX is 0, insert CHILD immediately
111 // before NODE, otherwise insert CHILD immediately after NODE.
114 static void insert_child (node_type node
, unsigned int index
,
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
);
123 using Accessors::set_parent
;
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
);
130 template<unsigned int N
>
131 static node_type
splay_limit (node_type
);
133 static node_type
remove_node_internal (node_type
);
135 template<typename Printer
>
136 static void print (pretty_printer
*pp
, node_type node
, Printer printer
,
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.
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
>
148 using parent
= base_splay_tree
<Accessors
>;
151 using typename
Accessors::node_type
;
154 // The root of the splay tree, or node_type () if the tree is empty.
158 rooted_splay_tree () : m_root () {}
160 // Construct a tree with the specified root node.
161 rooted_splay_tree (node_type root
) : m_root (root
) {}
163 // Return the root of the tree.
164 node_type
root () const { return m_root
; }
166 // Return true if the tree contains any nodes.
167 explicit operator bool () const { return m_root
; }
169 // Dereference the root node.
170 node_type
operator-> () { return m_root
; }
172 // Insert NEW_NODE into the splay tree, if no equivalent node already
173 // exists. For a given node N, COMPARE (N) should return:
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
179 // Return true if NEW_NODE was inserted.
181 // On return, NEW_NODE or its equivalent is the root of the tree.
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
);
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.
192 // On return, NEW_NODE is the root of the tree.
194 // For example, this can be used in the construct:
196 // int comparison = tree.lookup (...);
197 // if (comparison != 0)
198 // tree.insert_relative (comparison, create_new_node ());
201 void insert_relative (int comparison
, node_type new_node
);
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
208 void insert_max_node (node_type new_node
);
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.
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
);
218 // The root of the tree is currently the maximum node. Replace it
222 void replace_max_node_at_root (node_type new_node
);
224 // Remove the root node of the splay tree.
226 // Complexity: O(1) if removing the maximum or minimum node.
227 // Otherwise amortized O(log N), worst-cast O(N).
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.
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 ();
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 ();
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 ();
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.
249 // Complexity: amortized O(log N), worst-cast O(N).
250 bool splay_prev_node ();
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.
255 // Complexity: amortized O(log N), worst-cast O(N).
256 bool splay_next_node ();
258 // Bring the minimum node of the splay tree to the root.
260 // Complexity: amortized O(log N), worst-cast O(N).
261 void splay_min_node ();
263 // Bring the maximum node of the splay tree to the root.
265 // Complexity: amortized O(log N), worst-cast O(N).
266 void splay_max_node ();
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
272 // Complexity: amortized O(log N), worst-cast O(N).
273 node_type
min_node ();
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
279 // Complexity: amortized O(log N), worst-cast O(N).
280 node_type
max_node ();
282 // Search the splay tree. For a given node N, COMPARE (N) should return:
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
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:
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
294 // and install that node as the root instead.
296 // Return the result of COMPARE for the new root.
298 // This form of lookup is intended for cases in which both the following
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,
306 // (b) COMPARE is (or might be) relatively complex.
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.
312 // The implementation only invokes COMPARE once per node.
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
));
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
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:
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.
331 // - Install the minimum node that is bigger than the node being
332 // searched for and return -1.
334 // This form of lookup is intended for cases in which either of the
335 // following are true:
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.
343 // (b) There is no significant overhead to calling both
344 // WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER for the same node.
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
);
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
);
358 // Keep the ability to print subtrees.
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;
367 using parent::get_child
;
368 using parent::set_child
;
369 using parent::promote_child
;
371 using parent::set_parent
;
373 template<unsigned int N
>
374 bool splay_neighbor ();
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
>>;
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:
387 // Node m_children[2];
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
>>;
394 // A simple splay tree node that stores a value of type T.
396 class splay_tree_node
398 friend class default_splay_tree_accessors
<splay_tree_node
*>;
401 splay_tree_node () = default;
402 splay_tree_node (T value
) : m_value (value
), m_children () {}
404 T
&value () { return m_value
; }
405 const T
&value () const { return m_value
; }
409 splay_tree_node
*m_children
[2];
412 // A splay tree whose nodes hold values of type T.
414 using splay_tree
= default_splay_tree
<splay_tree_node
<T
> *>;
416 // Provide splay tree routines for cases in which the root of the tree
417 // is not explicitly stored.
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.
422 // The Accessors class provides the following static member functions:
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.
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
>>
435 using full_accessors
= splay_tree_accessors_with_parent
<Accessors
>;
436 using parent
= base_splay_tree
<full_accessors
>;
439 using rooted
= rooted_splay_tree
<full_accessors
>;
441 using typename
Accessors::node_type
;
443 // Remove NODE from the splay tree. Return the node that replaces it,
444 // or null if NODE had no children.
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
);
450 // Splay NODE so that it becomes the root of the splay tree.
452 // Complexity: amortized O(log N), worst-cast O(N).
453 static void splay (node_type node
);
455 // Like splay, but take advantage of the fact that NODE is known to be
456 // the minimum node in the tree.
458 // Complexity: amortized O(log N), worst-cast O(N).
459 static void splay_known_min_node (node_type node
);
461 // Like splay, but take advantage of the fact that NODE is known to be
462 // the maximum node in the tree.
464 // Complexity: amortized O(log N), worst-cast O(N).
465 static void splay_known_max_node (node_type node
);
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
473 // Note that this routine only examines nodes that happen to be ancestors
474 // of NODE. It does not search the full tree.
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
,
481 -> decltype (predicate (node
, 0));
483 // NODE1 and NODE2 are known to belong to the same splay tree. Return:
485 // -1 if NODE1 < NODE2
486 // 0 if NODE1 == NODE2
487 // 1 if NODE1 > NODE2
489 // Complexity: amortized O(log N), worst-cast O(N).
490 static int compare_nodes (node_type node1
, node_type node2
);
493 using parent::get_child
;
494 using parent::set_child
;
495 using parent::promote_child
;
497 static node_type
get_parent (node_type
);
498 using parent::set_parent
;
500 static unsigned int child_index (node_type
, node_type
);
502 static int compare_nodes_one_way (node_type
, node_type
);
504 template<unsigned int N
>
505 static void splay_known_limit (node_type
);
508 // Provide rootless splay tree routines for nodes of type Node.
509 // The child nodes are stored in a member variable:
511 // Node m_children[2];
513 // and the parent node is stored in a member variable:
516 template<typename Node
>
517 using default_rootless_splay_tree
518 = rootless_splay_tree
<default_splay_tree_accessors_with_parent
<Node
>>;
520 #include "splay-tree-utils.tcc"