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" |
492 | |