Line data Source code
1 : /* A typesafe wrapper around libiberty's splay-tree.h.
2 : Copyright (C) 2015-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 : #ifndef GCC_TYPED_SPLAY_TREE_H
21 : #define GCC_TYPED_SPLAY_TREE_H
22 :
23 : /* Typesafe wrapper around libiberty's splay-tree.h. */
24 : template <typename KEY_TYPE, typename VALUE_TYPE>
25 : class 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 :
109 : template <typename KEY_TYPE, typename VALUE_TYPE>
110 14108 : inline 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 14108 : root = NULL;
116 14108 : comp = compare_fn;
117 14108 : delete_key = delete_key_fn;
118 14108 : delete_value = delete_value_fn;
119 : }
120 :
121 : /* Destructor for typed_splay_tree <K, V>. */
122 :
123 : template <typename KEY_TYPE, typename VALUE_TYPE>
124 5108 : inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
125 : ~typed_splay_tree ()
126 : {
127 5108 : splay_tree_delete_helper (root);
128 4 : }
129 :
130 : /* Lookup KEY, returning a value if present, and NULL
131 : otherwise. */
132 :
133 : template <typename KEY_TYPE, typename VALUE_TYPE>
134 : inline VALUE_TYPE
135 35300 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
136 : {
137 35300 : splay_tree_node node = splay_tree_lookup (key);
138 35288 : 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 :
144 : template <typename KEY_TYPE, typename VALUE_TYPE>
145 : inline VALUE_TYPE
146 94 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
147 : {
148 94 : splay_tree_node node = splay_tree_predecessor (key);
149 90 : 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 :
155 : template <typename KEY_TYPE, typename VALUE_TYPE>
156 : inline VALUE_TYPE
157 5786 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
158 : {
159 5786 : splay_tree_node node = splay_tree_successor (key);
160 8147 : 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 :
167 : template <typename KEY_TYPE, typename VALUE_TYPE>
168 : inline void
169 7548 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
170 : value_type value)
171 : {
172 7536 : splay_tree_insert (key, value);
173 : }
174 :
175 : /* Remove a node (associating KEY with VALUE). */
176 :
177 : template <typename KEY_TYPE, typename VALUE_TYPE>
178 : inline void
179 4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key)
180 : {
181 4 : splay_tree_remove (key);
182 : }
183 :
184 : /* Get the value with maximal key. */
185 :
186 : template <typename KEY_TYPE, typename VALUE_TYPE>
187 : inline VALUE_TYPE
188 4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
189 : {
190 4 : return node_to_value (splay_tree_max ());
191 : }
192 :
193 : /* Get the value with minimal key. */
194 :
195 : template <typename KEY_TYPE, typename VALUE_TYPE>
196 : inline VALUE_TYPE
197 2649 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
198 : {
199 2645 : return node_to_value (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 :
207 : template <typename KEY_TYPE, typename VALUE_TYPE>
208 : inline int
209 2721 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
210 : void *user_data)
211 : {
212 2721 : 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. */
217 : template <typename KEY_TYPE, typename VALUE_TYPE>
218 : inline VALUE_TYPE
219 43833 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
220 : {
221 41180 : if (node)
222 22421 : return node->value;
223 : else
224 : return 0;
225 : }
226 :
227 : template <typename KEY_TYPE, typename VALUE_TYPE>
228 : inline void
229 7544 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
230 : {
231 7544 : if (delete_key)
232 0 : (*delete_key)(x);
233 : }
234 :
235 : template <typename KEY_TYPE, typename VALUE_TYPE>
236 : inline void
237 7548 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
238 : {
239 7548 : if (delete_value)
240 7447 : (*delete_value)(x);
241 : }
242 :
243 : /* Deallocate NODE (a member of SP), and all its sub-trees. */
244 :
245 : template <typename KEY_TYPE, typename VALUE_TYPE>
246 : void
247 14108 : typed_splay_tree<KEY_TYPE,
248 : VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
249 : {
250 14108 : splay_tree_node pending = NULL;
251 14108 : splay_tree_node active = NULL;
252 :
253 14108 : if (!node)
254 : return;
255 :
256 7135 : KDEL (node->key);
257 7135 : VDEL (node->value);
258 :
259 : /* We use the "back" field to hold the "next" pointer. */
260 7135 : node->back = pending;
261 7135 : 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 14675 : while (pending)
268 : {
269 : active = pending;
270 : pending = NULL;
271 15084 : 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 7544 : if (active->left)
279 : {
280 385 : KDEL (active->left->key);
281 385 : VDEL (active->left->value);
282 385 : active->left->back = pending;
283 385 : pending = active->left;
284 : }
285 7544 : if (active->right)
286 : {
287 24 : KDEL (active->right->key);
288 24 : VDEL (active->right->value);
289 24 : active->right->back = pending;
290 : pending = active->right;
291 : }
292 :
293 7544 : temp = active;
294 7544 : active = temp->back;
295 7544 : 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 :
303 : template <typename KEY_TYPE, typename VALUE_TYPE>
304 : inline void
305 1876 : typed_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 1876 : tmp = n->right;
311 1876 : n->right = p;
312 1876 : p->left = tmp;
313 1876 : *pp = n;
314 1251 : }
315 :
316 : /* Rotate the edge joining the right child N with its parent P. PP is the
317 : grandparents' pointer to P. */
318 :
319 : template <typename KEY_TYPE, typename VALUE_TYPE>
320 : inline void
321 1872 : typed_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 1872 : tmp = n->left;
327 1872 : n->left = p;
328 1872 : p->right = tmp;
329 1872 : *pp = n;
330 1872 : }
331 :
332 : /* Bottom up splay of key. */
333 :
334 : template <typename KEY_TYPE, typename VALUE_TYPE>
335 : void
336 48682 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
337 : {
338 48682 : if (root == NULL)
339 : return;
340 :
341 : do {
342 : int cmp1, cmp2;
343 : splay_tree_node n, c;
344 :
345 35558 : n = root;
346 35558 : cmp1 = (*comp) (key, n->key);
347 :
348 : /* Found. */
349 35558 : if (cmp1 == 0)
350 : return;
351 :
352 : /* Left or right? If no child, then we're done. */
353 11434 : if (cmp1 < 0)
354 3586 : c = n->left;
355 : else
356 7848 : c = n->right;
357 11434 : if (!c)
358 : return;
359 :
360 : /* Next one left or right? If found or no child, we're done
361 : after one rotation. */
362 3123 : cmp2 = (*comp) (key, c->key);
363 3123 : if (cmp2 == 0
364 2250 : || (cmp2 < 0 && !c->left)
365 1637 : || (cmp2 > 0 && !c->right))
366 : {
367 1853 : if (cmp1 < 0)
368 626 : rotate_left (&root, n, c);
369 : else
370 1227 : rotate_right (&root, n, c);
371 1853 : return;
372 : }
373 :
374 : /* Now we have the four cases of double-rotation. */
375 1270 : if (cmp1 < 0 && cmp2 < 0)
376 : {
377 625 : rotate_left (&n->left, c, c->left);
378 625 : rotate_left (&root, n, n->left);
379 : }
380 645 : else if (cmp1 > 0 && cmp2 > 0)
381 : {
382 20 : rotate_right (&n->right, c, c->right);
383 20 : rotate_right (&root, n, n->right);
384 : }
385 625 : else if (cmp1 < 0 && cmp2 > 0)
386 : {
387 0 : rotate_right (&n->left, c, c->right);
388 0 : rotate_left (&root, n, n->left);
389 : }
390 625 : else if (cmp1 > 0 && cmp2 < 0)
391 : {
392 625 : rotate_left (&n->right, c, c->left);
393 625 : rotate_right (&root, 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 :
403 : template <typename KEY_TYPE, typename VALUE_TYPE>
404 : int
405 2721 : typed_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 2721 : stack = NULL;
417 2721 : val = 0;
418 :
419 2657 : for (;;)
420 : {
421 8035 : while (node != NULL)
422 : {
423 2657 : node->back = stack;
424 2657 : stack = node;
425 2657 : node = node->left;
426 : }
427 :
428 5378 : if (stack == NULL)
429 : break;
430 :
431 2657 : node = stack;
432 2657 : stack = stack->back;
433 :
434 2657 : val = (*fn) (node->key, node->value, data);
435 2657 : if (val)
436 : break;
437 :
438 2657 : node = node->right;
439 : }
440 :
441 2721 : 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 :
448 : template <typename KEY_TYPE, typename VALUE_TYPE>
449 : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
450 7548 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
451 : splay_tree_key key,
452 : splay_tree_value value)
453 : {
454 7548 : int comparison = 0;
455 :
456 7548 : splay_tree_splay (key);
457 :
458 7548 : if (root)
459 413 : comparison = (*comp)(root->key, key);
460 :
461 7548 : 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 0 : VDEL(root->value);
466 0 : 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 7548 : node = new splay_tree_node_s;
474 7548 : node->key = key;
475 7548 : node->value = value;
476 :
477 7548 : if (!root)
478 7135 : node->left = node->right = 0;
479 413 : else if (comparison < 0)
480 : {
481 393 : node->left = root;
482 393 : node->right = node->left->right;
483 393 : node->left->right = 0;
484 : }
485 : else
486 : {
487 20 : node->right = root;
488 20 : node->left = node->right->left;
489 20 : node->right->left = 0;
490 : }
491 :
492 7548 : root = node;
493 : }
494 :
495 7548 : return root;
496 : }
497 :
498 : /* Remove KEY from SP. It is not an error if it did not exist. */
499 :
500 : template <typename KEY_TYPE, typename VALUE_TYPE>
501 : void
502 4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key)
503 : {
504 4 : splay_tree_splay (key);
505 :
506 4 : if (root && (*comp) (root->key, key) == 0)
507 : {
508 : splay_tree_node left, right;
509 :
510 4 : left = root->left;
511 4 : right = root->right;
512 :
513 : /* Delete the root node itself. */
514 4 : VDEL (root->value);
515 4 : 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 4 : if (left)
520 : {
521 4 : 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 4 : if (right)
526 : {
527 0 : while (left->right)
528 : left = left->right;
529 0 : left->right = right;
530 : }
531 : }
532 : else
533 0 : root = right;
534 : }
535 4 : }
536 :
537 : /* Lookup KEY in SP, returning VALUE if present, and NULL
538 : otherwise. */
539 :
540 : template <typename KEY_TYPE, typename VALUE_TYPE>
541 : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
542 35300 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
543 : {
544 35300 : splay_tree_splay (key);
545 :
546 35300 : if (root && (*comp)(root->key, key) == 0)
547 19293 : return root;
548 : else
549 16007 : return 0;
550 : }
551 :
552 : /* Return the node in SP with the greatest key. */
553 :
554 : template <typename KEY_TYPE, typename VALUE_TYPE>
555 : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
556 4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max ()
557 : {
558 4 : splay_tree_node n = root;
559 :
560 : if (!n)
561 : return NULL;
562 :
563 8 : while (n->right)
564 : n = n->right;
565 :
566 : return n;
567 : }
568 :
569 : /* Return the node in SP with the smallest key. */
570 :
571 : template <typename KEY_TYPE, typename VALUE_TYPE>
572 : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
573 2649 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
574 : {
575 2649 : splay_tree_node n = root;
576 :
577 2649 : if (!n)
578 : return NULL;
579 :
580 2994 : 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 :
589 : template <typename KEY_TYPE, typename VALUE_TYPE>
590 : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
591 94 : typed_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 94 : 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 69 : splay_tree_splay (key);
604 69 : comparison = (*comp)(root->key, key);
605 :
606 : /* If the predecessor is at the root, just return it. */
607 69 : if (comparison < 0)
608 45 : return root;
609 :
610 : /* Otherwise, find the rightmost element of the left subtree. */
611 24 : node = root->left;
612 24 : if (node)
613 4 : 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 :
622 : template <typename KEY_TYPE, typename VALUE_TYPE>
623 : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
624 5786 : typed_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 5786 : 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 5761 : splay_tree_splay (key);
637 5761 : comparison = (*comp)(root->key, key);
638 :
639 : /* If the successor is at the root, just return it. */
640 5761 : if (comparison > 0)
641 20 : return root;
642 :
643 : /* Otherwise, find the leftmost element of the right subtree. */
644 5741 : node = root->right;
645 5741 : if (node)
646 576 : while (node->left)
647 : node = node->left;
648 :
649 : return node;
650 : }
651 :
652 : #endif /* GCC_TYPED_SPLAY_TREE_H */
|
