Branch data Line data Source code
1 : : // Splay tree utilities -*- C++ -*-
2 : : // Copyright (C) 2020-2024 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 : 168589665 : child (node_type node, unsigned int index)
32 : : -> decltype (node->m_children[index]) &
33 : : {
34 : 26550113 : 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 : 2274 : 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 : 30356718 : set_parent (node_type node, node_type new_parent)
85 : : {
86 : 826600 : Base::parent (node) = new_parent;
87 : 242741 : }
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 : 154973400 : rooted_splay_tree () : m_root () {}
159 : :
160 : : // Construct a tree with the specified root node.
161 : 32332927 : rooted_splay_tree (node_type root) : m_root (root) {}
162 : :
163 : : // Return the root of the tree.
164 : 3311674 : node_type root () const { return m_root; }
165 : :
166 : : // Return true if the tree contains any nodes.
167 : 197543530 : explicit operator bool () const { return m_root; }
168 : :
169 : : // Dereference the root node.
170 : 15797759 : 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 : 30473640 : 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"
|