]>
Commit | Line | Data |
---|---|---|
ec5d0088 | 1 | /* A typesafe wrapper around libiberty's splay-tree.h. |
a5544970 | 2 | Copyright (C) 2015-2019 Free Software Foundation, Inc. |
ec5d0088 DM |
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 | ||
ec5d0088 DM |
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); | |
950f6c85 | 34 | typedef int (*foreach_fn) (key_type, value_type, void *); |
ec5d0088 DM |
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); | |
b48f2352 | 45 | void remove (key_type k); |
950f6c85 DM |
46 | value_type max (); |
47 | value_type min (); | |
48 | int foreach (foreach_fn, void *); | |
ec5d0088 DM |
49 | |
50 | private: | |
b48f2352 BE |
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; | |
950f6c85 | 65 | |
b48f2352 BE |
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 (); | |
950f6c85 | 91 | |
ec5d0088 DM |
92 | static value_type node_to_value (splay_tree_node node); |
93 | ||
b48f2352 BE |
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; | |
ec5d0088 DM |
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 | { | |
b48f2352 BE |
115 | root = NULL; |
116 | comp = compare_fn; | |
117 | delete_key = delete_key_fn; | |
118 | delete_value = delete_value_fn; | |
ec5d0088 DM |
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 | { | |
b48f2352 | 127 | splay_tree_delete_helper (root); |
ec5d0088 DM |
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 | { | |
b48f2352 | 137 | splay_tree_node node = splay_tree_lookup (key); |
ec5d0088 DM |
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 | { | |
b48f2352 | 148 | splay_tree_node node = splay_tree_predecessor (key); |
ec5d0088 DM |
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 | |
b48f2352 | 157 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key) |
ec5d0088 | 158 | { |
b48f2352 | 159 | splay_tree_node node = splay_tree_successor (key); |
ec5d0088 DM |
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 | { | |
b48f2352 BE |
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); | |
ec5d0088 DM |
182 | } |
183 | ||
950f6c85 DM |
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 | { | |
b48f2352 | 190 | return node_to_value (splay_tree_max ()); |
950f6c85 DM |
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 | { | |
b48f2352 | 199 | return node_to_value (splay_tree_min ()); |
950f6c85 DM |
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 | |
b48f2352 BE |
209 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn, |
210 | void *user_data) | |
950f6c85 | 211 | { |
b48f2352 BE |
212 | return splay_tree_foreach_helper (root, foreach_fn, user_data); |
213 | } | |
950f6c85 | 214 | |
b48f2352 BE |
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; | |
950f6c85 DM |
225 | } |
226 | ||
b48f2352 BE |
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 (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 | |
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 (&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. */ | |
950f6c85 DM |
402 | |
403 | template <typename KEY_TYPE, typename VALUE_TYPE> | |
404 | int | |
b48f2352 BE |
405 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper ( |
406 | splay_tree_node node, | |
407 | foreach_fn fn, void *data) | |
950f6c85 | 408 | { |
b48f2352 BE |
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; | |
950f6c85 | 437 | |
b48f2352 BE |
438 | node = node->right; |
439 | } | |
440 | ||
441 | return val; | |
950f6c85 DM |
442 | } |
443 | ||
b48f2352 BE |
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 | ||
ec5d0088 | 448 | template <typename KEY_TYPE, typename VALUE_TYPE> |
b48f2352 BE |
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) | |
ec5d0088 | 453 | { |
b48f2352 BE |
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 | |
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 | |
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; | |
ec5d0088 DM |
548 | else |
549 | return 0; | |
550 | } | |
551 | ||
b48f2352 BE |
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 | ||
ec5d0088 | 652 | #endif /* GCC_TYPED_SPLAY_TREE_H */ |