1 // Splay tree utilities -*- C++ -*-
2 // Copyright (C) 2020-2023 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 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"