Line data Source code
1 : // Splay tree utilities -*- C++ -*-
2 : // Copyright (C) 2020-2026 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 428235329 : child (node_type node, unsigned int index)
32 : -> decltype (node->m_children[index]) &
33 : {
34 66586128 : 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 22071 : 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 86359769 : set_parent (node_type node, node_type new_parent)
85 : {
86 1978047 : Base::parent (node) = new_parent;
87 676599 : }
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 555355056 : rooted_splay_tree () : m_root () {}
159 :
160 : // Construct a tree with the specified root node.
161 115319960 : rooted_splay_tree (node_type root) : m_root (root) {}
162 :
163 : // Return the root of the tree.
164 14050418 : node_type root () const { return m_root; }
165 :
166 : // Return true if the tree contains any nodes.
167 637904266 : explicit operator bool () const { return m_root; }
168 :
169 : // Dereference the root node.
170 29380907 : 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 45954082 : 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"
|
