1 | /* A typesafe wrapper around libiberty's splay-tree.h. |
2 | Copyright (C) 2015-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 | #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 | 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 | 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 | |
123 | template <typename KEY_TYPE, typename VALUE_TYPE> |
124 | inline 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 | |
133 | template <typename KEY_TYPE, typename VALUE_TYPE> |
134 | inline VALUE_TYPE |
135 | typed_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 | |
144 | template <typename KEY_TYPE, typename VALUE_TYPE> |
145 | inline VALUE_TYPE |
146 | typed_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 | |
155 | template <typename KEY_TYPE, typename VALUE_TYPE> |
156 | inline VALUE_TYPE |
157 | typed_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 | |
167 | template <typename KEY_TYPE, typename VALUE_TYPE> |
168 | inline void |
169 | typed_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 | |
177 | template <typename KEY_TYPE, typename VALUE_TYPE> |
178 | inline void |
179 | typed_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 | |
186 | template <typename KEY_TYPE, typename VALUE_TYPE> |
187 | inline VALUE_TYPE |
188 | typed_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 | |
195 | template <typename KEY_TYPE, typename VALUE_TYPE> |
196 | inline VALUE_TYPE |
197 | typed_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 | |
207 | template <typename KEY_TYPE, typename VALUE_TYPE> |
208 | inline int |
209 | typed_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. */ |
217 | template <typename KEY_TYPE, typename VALUE_TYPE> |
218 | inline VALUE_TYPE |
219 | typed_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 | |
227 | template <typename KEY_TYPE, typename VALUE_TYPE> |
228 | inline void |
229 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x) |
230 | { |
231 | if (delete_key) |
232 | (*delete_key)(x); |
233 | } |
234 | |
235 | template <typename KEY_TYPE, typename VALUE_TYPE> |
236 | inline void |
237 | typed_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 | |
245 | template <typename KEY_TYPE, typename VALUE_TYPE> |
246 | void |
247 | typed_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 | |
303 | template <typename KEY_TYPE, typename VALUE_TYPE> |
304 | inline void |
305 | 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 | 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 | |
319 | template <typename KEY_TYPE, typename VALUE_TYPE> |
320 | inline void |
321 | 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 | tmp = n->left; |
327 | n->left = p; |
328 | p->right = tmp; |
329 | *pp = n; |
330 | } |
331 | |
332 | /* Bottom up splay of key. */ |
333 | |
334 | template <typename KEY_TYPE, typename VALUE_TYPE> |
335 | void |
336 | typed_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 | |
403 | template <typename KEY_TYPE, typename VALUE_TYPE> |
404 | int |
405 | 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 | 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 | |
448 | template <typename KEY_TYPE, typename VALUE_TYPE> |
449 | typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node |
450 | typed_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 | |
500 | template <typename KEY_TYPE, typename VALUE_TYPE> |
501 | void |
502 | typed_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 | |
540 | template <typename KEY_TYPE, typename VALUE_TYPE> |
541 | typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node |
542 | typed_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 | |
554 | template <typename KEY_TYPE, typename VALUE_TYPE> |
555 | typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node |
556 | typed_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 | |
571 | template <typename KEY_TYPE, typename VALUE_TYPE> |
572 | typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node |
573 | typed_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 | |
589 | template <typename KEY_TYPE, typename VALUE_TYPE> |
590 | typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node |
591 | 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 | 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 | |
622 | template <typename KEY_TYPE, typename VALUE_TYPE> |
623 | typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node |
624 | 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 | 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 | |