1 /* A typesafe wrapper around libiberty's splay-tree.h.
2 Copyright (C) 2015-2020 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>::
typed_splay_tree(compare_fn compare_fn,delete_key_fn delete_key_fn,delete_value_fn delete_value_fn)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>::
~typed_splay_tree()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
lookup(key_type key)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
predecessor(key_type key)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
successor(key_type key)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
insert(key_type key,value_type value)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
remove(key_type key)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
max()188 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
189 {
190 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
min()197 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
198 {
199 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
foreach(foreach_fn foreach_fn,void * user_data)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
node_to_value(splay_tree_node node)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
KDEL(splay_tree_key x)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
VDEL(splay_tree_value x)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,
splay_tree_delete_helper(splay_tree_node node)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 (node->key);
257 VDEL (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 (active->left->key);
281 VDEL (active->left->value);
282 active->left->back = pending;
283 pending = active->left;
284 }
285 if (active->right)
286 {
287 KDEL (active->right->key);
288 VDEL (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
rotate_left(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)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
rotate_right(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)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
splay_tree_splay(splay_tree_key key)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 (&root, n, c);
369 else
370 rotate_right (&root, 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 (&n->left, c, c->left);
378 rotate_left (&root, n, n->left);
379 }
380 else if (cmp1 > 0 && cmp2 > 0)
381 {
382 rotate_right (&n->right, c, c->right);
383 rotate_right (&root, n, n->right);
384 }
385 else if (cmp1 < 0 && cmp2 > 0)
386 {
387 rotate_right (&n->left, c, c->right);
388 rotate_left (&root, n, n->left);
389 }
390 else if (cmp1 > 0 && cmp2 < 0)
391 {
392 rotate_left (&n->right, c, c->left);
393 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
splay_tree_foreach_helper(splay_tree_node node,foreach_fn fn,void * data)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
splay_tree_insert(splay_tree_key key,splay_tree_value value)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(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
splay_tree_remove(splay_tree_key key)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 (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
splay_tree_lookup(splay_tree_key key)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
splay_tree_max()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
splay_tree_min()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,
splay_tree_predecessor(splay_tree_key key)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,
splay_tree_successor(splay_tree_key key)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