Branch data Line data Source code
1 : : /* A typesafe wrapper around libiberty's splay-tree.h.
2 : : Copyright (C) 2015-2024 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 : 85618 : 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 : 85618 : root = NULL;
116 : 85618 : comp = compare_fn;
117 : 85618 : delete_key = delete_key_fn;
118 : 85618 : 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 : 13618 : inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
125 : : ~typed_splay_tree ()
126 : : {
127 : 13618 : 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 : 88864 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
136 : : {
137 : 88864 : splay_tree_node node = splay_tree_lookup (key);
138 : 88852 : 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 : 18028 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
158 : : {
159 : 18028 : splay_tree_node node = splay_tree_successor (key);
160 : 26510 : 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 : 24174 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
170 : : value_type value)
171 : : {
172 : 24162 : 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 : 8770 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
198 : : {
199 : 8766 : 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 : 8770 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
210 : : void *user_data)
211 : : {
212 : 8770 : 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 : 115760 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
220 : : {
221 : 106986 : if (node)
222 : 59147 : return node->value;
223 : : else
224 : : return 0;
225 : : }
226 : :
227 : : template <typename KEY_TYPE, typename VALUE_TYPE>
228 : : inline void
229 : 24170 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
230 : : {
231 : 24170 : if (delete_key)
232 : 0 : (*delete_key)(x);
233 : : }
234 : :
235 : : template <typename KEY_TYPE, typename VALUE_TYPE>
236 : : inline void
237 : 24174 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
238 : : {
239 : 24174 : if (delete_value)
240 : 24073 : (*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 : 85618 : typed_splay_tree<KEY_TYPE,
248 : : VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
249 : : {
250 : 85618 : splay_tree_node pending = NULL;
251 : 85618 : splay_tree_node active = NULL;
252 : :
253 : 85618 : if (!node)
254 : : return;
255 : :
256 : 23761 : KDEL (node->key);
257 : 23761 : VDEL (node->value);
258 : :
259 : : /* We use the "back" field to hold the "next" pointer. */
260 : 23761 : node->back = pending;
261 : 23761 : 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 : 47927 : while (pending)
268 : : {
269 : : active = pending;
270 : : pending = NULL;
271 : 48336 : 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 : 24170 : 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 : 24170 : if (active->right)
286 : : {
287 : 24 : KDEL (active->right->key);
288 : 24 : VDEL (active->right->value);
289 : 24 : active->right->back = pending;
290 : 24 : pending = active->right;
291 : : }
292 : :
293 : 24170 : temp = active;
294 : 24170 : active = temp->back;
295 : 24170 : 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 : 131114 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
337 : : {
338 : 131114 : if (root == NULL)
339 : : return;
340 : :
341 : : do {
342 : : int cmp1, cmp2;
343 : : splay_tree_node n, c;
344 : :
345 : 84138 : n = root;
346 : 84138 : cmp1 = (*comp) (key, n->key);
347 : :
348 : : /* Found. */
349 : 84138 : if (cmp1 == 0)
350 : : return;
351 : :
352 : : /* Left or right? If no child, then we're done. */
353 : 17167 : if (cmp1 < 0)
354 : 3388 : c = n->left;
355 : : else
356 : 13779 : c = n->right;
357 : 17167 : 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 : 8770 : 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 : 8770 : stack = NULL;
417 : 8770 : val = 0;
418 : :
419 : 8778 : for (;;)
420 : : {
421 : 26326 : while (node != NULL)
422 : : {
423 : 8778 : node->back = stack;
424 : 8778 : stack = node;
425 : 8778 : node = node->left;
426 : : }
427 : :
428 : 17548 : if (stack == NULL)
429 : : break;
430 : :
431 : 8778 : node = stack;
432 : 8778 : stack = stack->back;
433 : :
434 : 8778 : val = (*fn) (node->key, node->value, data);
435 : 8778 : if (val)
436 : : break;
437 : :
438 : 8778 : node = node->right;
439 : : }
440 : :
441 : 8770 : 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 : 24174 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
451 : : splay_tree_key key,
452 : : splay_tree_value value)
453 : : {
454 : 24174 : int comparison = 0;
455 : :
456 : 24174 : splay_tree_splay (key);
457 : :
458 : 24174 : if (root)
459 : 413 : comparison = (*comp)(root->key, key);
460 : :
461 : 24174 : 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 : 24174 : node = new splay_tree_node_s;
474 : 24174 : node->key = key;
475 : 24174 : node->value = value;
476 : :
477 : 24174 : if (!root)
478 : 23761 : 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 : 24174 : root = node;
493 : : }
494 : :
495 : 24174 : 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 : 88864 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
543 : : {
544 : 88864 : splay_tree_splay (key);
545 : :
546 : 88864 : if (root && (*comp)(root->key, key) == 0)
547 : 49898 : return root;
548 : : else
549 : 38966 : 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 : 8770 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
574 : : {
575 : 8770 : splay_tree_node n = root;
576 : :
577 : 8770 : if (!n)
578 : : return NULL;
579 : :
580 : 9115 : 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 : 18028 : 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 : 18028 : 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 : 18003 : splay_tree_splay (key);
637 : 18003 : comparison = (*comp)(root->key, key);
638 : :
639 : : /* If the successor is at the root, just return it. */
640 : 18003 : if (comparison > 0)
641 : 20 : return root;
642 : :
643 : : /* Otherwise, find the leftmost element of the right subtree. */
644 : 17983 : node = root->right;
645 : 17983 : if (node)
646 : 576 : while (node->left)
647 : : node = node->left;
648 : :
649 : : return node;
650 : : }
651 : :
652 : : #endif /* GCC_TYPED_SPLAY_TREE_H */
|
