1/* A typesafe wrapper around libiberty's splay-tree.h.
2 Copyright (C) 2015-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#ifndef GCC_TYPED_SPLAY_TREE_H
21#define GCC_TYPED_SPLAY_TREE_H
22
23/* Typesafe wrapper around libiberty's splay-tree.h. */
24template <typename KEY_TYPE, typename VALUE_TYPE>
25class typed_splay_tree
26{
27 public:
28 typedef KEY_TYPE key_type;
29 typedef VALUE_TYPE value_type;
30
31 typedef int (*compare_fn) (key_type, key_type);
32 typedef void (*delete_key_fn) (key_type);
33 typedef void (*delete_value_fn) (value_type);
34 typedef int (*foreach_fn) (key_type, value_type, void *);
35
36 typed_splay_tree (compare_fn,
37 delete_key_fn,
38 delete_value_fn);
39 ~typed_splay_tree ();
40
41 value_type lookup (key_type k);
42 value_type predecessor (key_type k);
43 value_type successor (key_type k);
44 void insert (key_type k, value_type v);
45 void remove (key_type k);
46 value_type max ();
47 value_type min ();
48 int foreach (foreach_fn, void *);
49
50 private:
51 /* Copy and assignment ops are not supported. */
52 typed_splay_tree (const typed_splay_tree &);
53 typed_splay_tree & operator = (const typed_splay_tree &);
54
55 typedef key_type splay_tree_key;
56 typedef value_type splay_tree_value;
57
58 /* The nodes in the splay tree. */
59 struct splay_tree_node_s {
60 /* The key. */
61 splay_tree_key key;
62
63 /* The value. */
64 splay_tree_value value;
65
66 /* The left and right children, respectively. */
67 splay_tree_node_s *left, *right;
68
69 /* Used as temporary value for tree traversals. */
70 splay_tree_node_s *back;
71 };
72 typedef splay_tree_node_s *splay_tree_node;
73
74 inline void KDEL (splay_tree_key);
75 inline void VDEL (splay_tree_value);
76 void splay_tree_delete_helper (splay_tree_node);
77 static inline void rotate_left (splay_tree_node *,
78 splay_tree_node, splay_tree_node);
79 static inline void rotate_right (splay_tree_node *,
80 splay_tree_node, splay_tree_node);
81 void splay_tree_splay (splay_tree_key);
82 static int splay_tree_foreach_helper (splay_tree_node,
83 foreach_fn, void*);
84 splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value);
85 void splay_tree_remove (splay_tree_key key);
86 splay_tree_node splay_tree_lookup (splay_tree_key key);
87 splay_tree_node splay_tree_predecessor (splay_tree_key);
88 splay_tree_node splay_tree_successor (splay_tree_key);
89 splay_tree_node splay_tree_max ();
90 splay_tree_node splay_tree_min ();
91
92 static value_type node_to_value (splay_tree_node node);
93
94 /* The root of the tree. */
95 splay_tree_node root;
96
97 /* The comparision function. */
98 compare_fn comp;
99
100 /* The deallocate-key function. NULL if no cleanup is necessary. */
101 delete_key_fn delete_key;
102
103 /* The deallocate-value function. NULL if no cleanup is necessary. */
104 delete_value_fn delete_value;
105};
106
107/* Constructor for typed_splay_tree <K, V>. */
108
109template <typename KEY_TYPE, typename VALUE_TYPE>
110inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
111 typed_splay_tree (compare_fn compare_fn,
112 delete_key_fn delete_key_fn,
113 delete_value_fn delete_value_fn)
114{
115 root = NULL;
116 comp = compare_fn;
117 delete_key = delete_key_fn;
118 delete_value = delete_value_fn;
119}
120
121/* Destructor for typed_splay_tree <K, V>. */
122
123template <typename KEY_TYPE, typename VALUE_TYPE>
124inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
125 ~typed_splay_tree ()
126{
127 splay_tree_delete_helper (root);
128}
129
130/* Lookup KEY, returning a value if present, and NULL
131 otherwise. */
132
133template <typename KEY_TYPE, typename VALUE_TYPE>
134inline VALUE_TYPE
135typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
136{
137 splay_tree_node node = splay_tree_lookup (key);
138 return node_to_value (node);
139}
140
141/* Return the immediate predecessor of KEY, or NULL if there is no
142 predecessor. KEY need not be present in the tree. */
143
144template <typename KEY_TYPE, typename VALUE_TYPE>
145inline VALUE_TYPE
146typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
147{
148 splay_tree_node node = splay_tree_predecessor (key);
149 return node_to_value (node);
150}
151
152/* Return the immediate successor of KEY, or NULL if there is no
153 successor. KEY need not be present in the tree. */
154
155template <typename KEY_TYPE, typename VALUE_TYPE>
156inline VALUE_TYPE
157typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
158{
159 splay_tree_node node = splay_tree_successor (key);
160 return node_to_value (node);
161}
162
163/* Insert a new node (associating KEY with VALUE). If a
164 previous node with the indicated KEY exists, its data is replaced
165 with the new value. */
166
167template <typename KEY_TYPE, typename VALUE_TYPE>
168inline void
169typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
170 value_type value)
171{
172 splay_tree_insert (key, value);
173}
174
175/* Remove a node (associating KEY with VALUE). */
176
177template <typename KEY_TYPE, typename VALUE_TYPE>
178inline void
179typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key)
180{
181 splay_tree_remove (key);
182}
183
184/* Get the value with maximal key. */
185
186template <typename KEY_TYPE, typename VALUE_TYPE>
187inline VALUE_TYPE
188typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
189{
190 return node_to_value (node: splay_tree_max ());
191}
192
193/* Get the value with minimal key. */
194
195template <typename KEY_TYPE, typename VALUE_TYPE>
196inline VALUE_TYPE
197typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
198{
199 return node_to_value (node: splay_tree_min ());
200}
201
202/* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node,
203 following an in-order traversal. If OUTER_CB ever returns a non-zero
204 value, the iteration ceases immediately, and the value is returned.
205 Otherwise, this function returns 0. */
206
207template <typename KEY_TYPE, typename VALUE_TYPE>
208inline int
209typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
210 void *user_data)
211{
212 return splay_tree_foreach_helper (root, foreach_fn, user_data);
213}
214
215/* Internal function for converting from splay_tree_node to
216 VALUE_TYPE. */
217template <typename KEY_TYPE, typename VALUE_TYPE>
218inline VALUE_TYPE
219typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
220{
221 if (node)
222 return node->value;
223 else
224 return 0;
225}
226
227template <typename KEY_TYPE, typename VALUE_TYPE>
228inline void
229typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
230{
231 if (delete_key)
232 (*delete_key)(x);
233}
234
235template <typename KEY_TYPE, typename VALUE_TYPE>
236inline void
237typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
238{
239 if (delete_value)
240 (*delete_value)(x);
241}
242
243/* Deallocate NODE (a member of SP), and all its sub-trees. */
244
245template <typename KEY_TYPE, typename VALUE_TYPE>
246void
247typed_splay_tree<KEY_TYPE,
248 VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
249{
250 splay_tree_node pending = NULL;
251 splay_tree_node active = NULL;
252
253 if (!node)
254 return;
255
256 KDEL (x: node->key);
257 VDEL (x: node->value);
258
259 /* We use the "back" field to hold the "next" pointer. */
260 node->back = pending;
261 pending = node;
262
263 /* Now, keep processing the pending list until there aren't any
264 more. This is a little more complicated than just recursing, but
265 it doesn't toast the stack for large trees. */
266
267 while (pending)
268 {
269 active = pending;
270 pending = NULL;
271 while (active)
272 {
273 splay_tree_node temp;
274
275 /* active points to a node which has its key and value
276 deallocated, we just need to process left and right. */
277
278 if (active->left)
279 {
280 KDEL (x: active->left->key);
281 VDEL (x: active->left->value);
282 active->left->back = pending;
283 pending = active->left;
284 }
285 if (active->right)
286 {
287 KDEL (x: active->right->key);
288 VDEL (x: active->right->value);
289 active->right->back = pending;
290 pending = active->right;
291 }
292
293 temp = active;
294 active = temp->back;
295 delete temp;
296 }
297 }
298}
299
300/* Rotate the edge joining the left child N with its parent P. PP is the
301 grandparents' pointer to P. */
302
303template <typename KEY_TYPE, typename VALUE_TYPE>
304inline void
305typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_left (splay_tree_node *pp,
306 splay_tree_node p,
307 splay_tree_node n)
308{
309 splay_tree_node tmp;
310 tmp = n->right;
311 n->right = p;
312 p->left = tmp;
313 *pp = n;
314}
315
316/* Rotate the edge joining the right child N with its parent P. PP is the
317 grandparents' pointer to P. */
318
319template <typename KEY_TYPE, typename VALUE_TYPE>
320inline void
321typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_right (splay_tree_node *pp,
322 splay_tree_node p,
323 splay_tree_node n)
324{
325 splay_tree_node tmp;
326 tmp = n->left;
327 n->left = p;
328 p->right = tmp;
329 *pp = n;
330}
331
332/* Bottom up splay of key. */
333
334template <typename KEY_TYPE, typename VALUE_TYPE>
335void
336typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
337{
338 if (root == NULL)
339 return;
340
341 do {
342 int cmp1, cmp2;
343 splay_tree_node n, c;
344
345 n = root;
346 cmp1 = (*comp) (key, n->key);
347
348 /* Found. */
349 if (cmp1 == 0)
350 return;
351
352 /* Left or right? If no child, then we're done. */
353 if (cmp1 < 0)
354 c = n->left;
355 else
356 c = n->right;
357 if (!c)
358 return;
359
360 /* Next one left or right? If found or no child, we're done
361 after one rotation. */
362 cmp2 = (*comp) (key, c->key);
363 if (cmp2 == 0
364 || (cmp2 < 0 && !c->left)
365 || (cmp2 > 0 && !c->right))
366 {
367 if (cmp1 < 0)
368 rotate_left (pp: &root, p: n, n: c);
369 else
370 rotate_right (pp: &root, p: n, n: c);
371 return;
372 }
373
374 /* Now we have the four cases of double-rotation. */
375 if (cmp1 < 0 && cmp2 < 0)
376 {
377 rotate_left (pp: &n->left, p: c, n: c->left);
378 rotate_left (pp: &root, p: n, n: n->left);
379 }
380 else if (cmp1 > 0 && cmp2 > 0)
381 {
382 rotate_right (pp: &n->right, p: c, n: c->right);
383 rotate_right (pp: &root, p: n, n: n->right);
384 }
385 else if (cmp1 < 0 && cmp2 > 0)
386 {
387 rotate_right (pp: &n->left, p: c, n: c->right);
388 rotate_left (pp: &root, p: n, n: n->left);
389 }
390 else if (cmp1 > 0 && cmp2 < 0)
391 {
392 rotate_left (pp: &n->right, p: c, n: c->left);
393 rotate_right (pp: &root, p: n, n: n->right);
394 }
395 } while (1);
396}
397
398/* Call FN, passing it the DATA, for every node below NODE, all of
399 which are from SP, following an in-order traversal. If FN every
400 returns a non-zero value, the iteration ceases immediately, and the
401 value is returned. Otherwise, this function returns 0. */
402
403template <typename KEY_TYPE, typename VALUE_TYPE>
404int
405typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper (
406 splay_tree_node node,
407 foreach_fn fn, void *data)
408{
409 int val;
410 splay_tree_node stack;
411
412 /* A non-recursive implementation is used to avoid filling the stack
413 for large trees. Splay trees are worst case O(n) in the depth of
414 the tree. */
415
416 stack = NULL;
417 val = 0;
418
419 for (;;)
420 {
421 while (node != NULL)
422 {
423 node->back = stack;
424 stack = node;
425 node = node->left;
426 }
427
428 if (stack == NULL)
429 break;
430
431 node = stack;
432 stack = stack->back;
433
434 val = (*fn) (node->key, node->value, data);
435 if (val)
436 break;
437
438 node = node->right;
439 }
440
441 return val;
442}
443
444/* Insert a new node (associating KEY with DATA) into SP. If a
445 previous node with the indicated KEY exists, its data is replaced
446 with the new value. Returns the new node. */
447
448template <typename KEY_TYPE, typename VALUE_TYPE>
449typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
450typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
451 splay_tree_key key,
452 splay_tree_value value)
453{
454 int comparison = 0;
455
456 splay_tree_splay (key);
457
458 if (root)
459 comparison = (*comp)(root->key, key);
460
461 if (root && comparison == 0)
462 {
463 /* If the root of the tree already has the indicated KEY, just
464 replace the value with VALUE. */
465 VDEL(x: root->value);
466 root->value = value;
467 }
468 else
469 {
470 /* Create a new node, and insert it at the root. */
471 splay_tree_node node;
472
473 node = new splay_tree_node_s;
474 node->key = key;
475 node->value = value;
476
477 if (!root)
478 node->left = node->right = 0;
479 else if (comparison < 0)
480 {
481 node->left = root;
482 node->right = node->left->right;
483 node->left->right = 0;
484 }
485 else
486 {
487 node->right = root;
488 node->left = node->right->left;
489 node->right->left = 0;
490 }
491
492 root = node;
493 }
494
495 return root;
496}
497
498/* Remove KEY from SP. It is not an error if it did not exist. */
499
500template <typename KEY_TYPE, typename VALUE_TYPE>
501void
502typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key)
503{
504 splay_tree_splay (key);
505
506 if (root && (*comp) (root->key, key) == 0)
507 {
508 splay_tree_node left, right;
509
510 left = root->left;
511 right = root->right;
512
513 /* Delete the root node itself. */
514 VDEL (x: root->value);
515 delete root;
516
517 /* One of the children is now the root. Doesn't matter much
518 which, so long as we preserve the properties of the tree. */
519 if (left)
520 {
521 root = left;
522
523 /* If there was a right child as well, hang it off the
524 right-most leaf of the left child. */
525 if (right)
526 {
527 while (left->right)
528 left = left->right;
529 left->right = right;
530 }
531 }
532 else
533 root = right;
534 }
535}
536
537/* Lookup KEY in SP, returning VALUE if present, and NULL
538 otherwise. */
539
540template <typename KEY_TYPE, typename VALUE_TYPE>
541typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
542typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
543{
544 splay_tree_splay (key);
545
546 if (root && (*comp)(root->key, key) == 0)
547 return root;
548 else
549 return 0;
550}
551
552/* Return the node in SP with the greatest key. */
553
554template <typename KEY_TYPE, typename VALUE_TYPE>
555typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
556typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max ()
557{
558 splay_tree_node n = root;
559
560 if (!n)
561 return NULL;
562
563 while (n->right)
564 n = n->right;
565
566 return n;
567}
568
569/* Return the node in SP with the smallest key. */
570
571template <typename KEY_TYPE, typename VALUE_TYPE>
572typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
573typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
574{
575 splay_tree_node n = root;
576
577 if (!n)
578 return NULL;
579
580 while (n->left)
581 n = n->left;
582
583 return n;
584}
585
586/* Return the immediate predecessor KEY, or NULL if there is no
587 predecessor. KEY need not be present in the tree. */
588
589template <typename KEY_TYPE, typename VALUE_TYPE>
590typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
591typed_splay_tree<KEY_TYPE,
592 VALUE_TYPE>::splay_tree_predecessor (splay_tree_key key)
593{
594 int comparison;
595 splay_tree_node node;
596
597 /* If the tree is empty, there is certainly no predecessor. */
598 if (!root)
599 return NULL;
600
601 /* Splay the tree around KEY. That will leave either the KEY
602 itself, its predecessor, or its successor at the root. */
603 splay_tree_splay (key);
604 comparison = (*comp)(root->key, key);
605
606 /* If the predecessor is at the root, just return it. */
607 if (comparison < 0)
608 return root;
609
610 /* Otherwise, find the rightmost element of the left subtree. */
611 node = root->left;
612 if (node)
613 while (node->right)
614 node = node->right;
615
616 return node;
617}
618
619/* Return the immediate successor KEY, or NULL if there is no
620 successor. KEY need not be present in the tree. */
621
622template <typename KEY_TYPE, typename VALUE_TYPE>
623typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
624typed_splay_tree<KEY_TYPE,
625 VALUE_TYPE>::splay_tree_successor (splay_tree_key key)
626{
627 int comparison;
628 splay_tree_node node;
629
630 /* If the tree is empty, there is certainly no successor. */
631 if (!root)
632 return NULL;
633
634 /* Splay the tree around KEY. That will leave either the KEY
635 itself, its predecessor, or its successor at the root. */
636 splay_tree_splay (key);
637 comparison = (*comp)(root->key, key);
638
639 /* If the successor is at the root, just return it. */
640 if (comparison > 0)
641 return root;
642
643 /* Otherwise, find the leftmost element of the right subtree. */
644 node = root->right;
645 if (node)
646 while (node->left)
647 node = node->left;
648
649 return node;
650}
651
652#endif /* GCC_TYPED_SPLAY_TREE_H */
653

source code of gcc/typed-splay-tree.h