12a6b7db3Sskrll /* A splay-tree datatype.
2*f22f0ef4Schristos Copyright (C) 1998-2022 Free Software Foundation, Inc.
32a6b7db3Sskrll Contributed by Mark Mitchell (mark@markmitchell.com).
42a6b7db3Sskrll
52a6b7db3Sskrll This file is part of GNU CC.
62a6b7db3Sskrll
72a6b7db3Sskrll GNU CC is free software; you can redistribute it and/or modify it
82a6b7db3Sskrll under the terms of the GNU General Public License as published by
92a6b7db3Sskrll the Free Software Foundation; either version 2, or (at your option)
102a6b7db3Sskrll any later version.
112a6b7db3Sskrll
122a6b7db3Sskrll GNU CC is distributed in the hope that it will be useful, but
132a6b7db3Sskrll WITHOUT ANY WARRANTY; without even the implied warranty of
142a6b7db3Sskrll MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
152a6b7db3Sskrll General Public License for more details.
162a6b7db3Sskrll
172a6b7db3Sskrll You should have received a copy of the GNU General Public License
182a6b7db3Sskrll along with GNU CC; see the file COPYING. If not, write to
192a6b7db3Sskrll the Free Software Foundation, 51 Franklin Street - Fifth Floor,
202a6b7db3Sskrll Boston, MA 02110-1301, USA. */
212a6b7db3Sskrll
222a6b7db3Sskrll /* For an easily readable description of splay-trees, see:
232a6b7db3Sskrll
242a6b7db3Sskrll Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
252a6b7db3Sskrll Algorithms. Harper-Collins, Inc. 1991. */
262a6b7db3Sskrll
272a6b7db3Sskrll #ifdef HAVE_CONFIG_H
282a6b7db3Sskrll #include "config.h"
292a6b7db3Sskrll #endif
302a6b7db3Sskrll
312a6b7db3Sskrll #ifdef HAVE_STDLIB_H
322a6b7db3Sskrll #include <stdlib.h>
332a6b7db3Sskrll #endif
34fa2c2dd3Schristos #ifdef HAVE_STRING_H
35fa2c2dd3Schristos #include <string.h>
36fa2c2dd3Schristos #endif
372a6b7db3Sskrll
382a6b7db3Sskrll #include <stdio.h>
392a6b7db3Sskrll
402a6b7db3Sskrll #include "libiberty.h"
412a6b7db3Sskrll #include "splay-tree.h"
422a6b7db3Sskrll
432a6b7db3Sskrll static void splay_tree_delete_helper (splay_tree, splay_tree_node);
442a6b7db3Sskrll static inline void rotate_left (splay_tree_node *,
452a6b7db3Sskrll splay_tree_node, splay_tree_node);
462a6b7db3Sskrll static inline void rotate_right (splay_tree_node *,
472a6b7db3Sskrll splay_tree_node, splay_tree_node);
482a6b7db3Sskrll static void splay_tree_splay (splay_tree, splay_tree_key);
4905caefcfSchristos static int splay_tree_foreach_helper (splay_tree_node,
502a6b7db3Sskrll splay_tree_foreach_fn, void*);
512a6b7db3Sskrll
522a6b7db3Sskrll /* Deallocate NODE (a member of SP), and all its sub-trees. */
532a6b7db3Sskrll
542a6b7db3Sskrll static void
splay_tree_delete_helper(splay_tree sp,splay_tree_node node)552a6b7db3Sskrll splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
562a6b7db3Sskrll {
572a6b7db3Sskrll splay_tree_node pending = 0;
582a6b7db3Sskrll splay_tree_node active = 0;
592a6b7db3Sskrll
602a6b7db3Sskrll if (!node)
612a6b7db3Sskrll return;
622a6b7db3Sskrll
632a6b7db3Sskrll #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x);
642a6b7db3Sskrll #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x);
652a6b7db3Sskrll
662a6b7db3Sskrll KDEL (node->key);
672a6b7db3Sskrll VDEL (node->value);
682a6b7db3Sskrll
692a6b7db3Sskrll /* We use the "key" field to hold the "next" pointer. */
702a6b7db3Sskrll node->key = (splay_tree_key)pending;
712a6b7db3Sskrll pending = (splay_tree_node)node;
722a6b7db3Sskrll
732a6b7db3Sskrll /* Now, keep processing the pending list until there aren't any
742a6b7db3Sskrll more. This is a little more complicated than just recursing, but
752a6b7db3Sskrll it doesn't toast the stack for large trees. */
762a6b7db3Sskrll
772a6b7db3Sskrll while (pending)
782a6b7db3Sskrll {
792a6b7db3Sskrll active = pending;
802a6b7db3Sskrll pending = 0;
812a6b7db3Sskrll while (active)
822a6b7db3Sskrll {
832a6b7db3Sskrll splay_tree_node temp;
842a6b7db3Sskrll
852a6b7db3Sskrll /* active points to a node which has its key and value
862a6b7db3Sskrll deallocated, we just need to process left and right. */
872a6b7db3Sskrll
882a6b7db3Sskrll if (active->left)
892a6b7db3Sskrll {
902a6b7db3Sskrll KDEL (active->left->key);
912a6b7db3Sskrll VDEL (active->left->value);
922a6b7db3Sskrll active->left->key = (splay_tree_key)pending;
932a6b7db3Sskrll pending = (splay_tree_node)(active->left);
942a6b7db3Sskrll }
952a6b7db3Sskrll if (active->right)
962a6b7db3Sskrll {
972a6b7db3Sskrll KDEL (active->right->key);
982a6b7db3Sskrll VDEL (active->right->value);
992a6b7db3Sskrll active->right->key = (splay_tree_key)pending;
1002a6b7db3Sskrll pending = (splay_tree_node)(active->right);
1012a6b7db3Sskrll }
1022a6b7db3Sskrll
1032a6b7db3Sskrll temp = active;
1042a6b7db3Sskrll active = (splay_tree_node)(temp->key);
1052a6b7db3Sskrll (*sp->deallocate) ((char*) temp, sp->allocate_data);
1062a6b7db3Sskrll }
1072a6b7db3Sskrll }
1082a6b7db3Sskrll #undef KDEL
1092a6b7db3Sskrll #undef VDEL
1102a6b7db3Sskrll }
1112a6b7db3Sskrll
1122a6b7db3Sskrll /* Rotate the edge joining the left child N with its parent P. PP is the
1132a6b7db3Sskrll grandparents' pointer to P. */
1142a6b7db3Sskrll
1152a6b7db3Sskrll static inline void
rotate_left(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)1162a6b7db3Sskrll rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
1172a6b7db3Sskrll {
1182a6b7db3Sskrll splay_tree_node tmp;
1192a6b7db3Sskrll tmp = n->right;
1202a6b7db3Sskrll n->right = p;
1212a6b7db3Sskrll p->left = tmp;
1222a6b7db3Sskrll *pp = n;
1232a6b7db3Sskrll }
1242a6b7db3Sskrll
1252a6b7db3Sskrll /* Rotate the edge joining the right child N with its parent P. PP is the
1262a6b7db3Sskrll grandparents' pointer to P. */
1272a6b7db3Sskrll
1282a6b7db3Sskrll static inline void
rotate_right(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)1292a6b7db3Sskrll rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
1302a6b7db3Sskrll {
1312a6b7db3Sskrll splay_tree_node tmp;
1322a6b7db3Sskrll tmp = n->left;
1332a6b7db3Sskrll n->left = p;
1342a6b7db3Sskrll p->right = tmp;
1352a6b7db3Sskrll *pp = n;
1362a6b7db3Sskrll }
1372a6b7db3Sskrll
1382a6b7db3Sskrll /* Bottom up splay of key. */
1392a6b7db3Sskrll
1402a6b7db3Sskrll static void
splay_tree_splay(splay_tree sp,splay_tree_key key)1412a6b7db3Sskrll splay_tree_splay (splay_tree sp, splay_tree_key key)
1422a6b7db3Sskrll {
1432a6b7db3Sskrll if (sp->root == 0)
1442a6b7db3Sskrll return;
1452a6b7db3Sskrll
1462a6b7db3Sskrll do {
1472a6b7db3Sskrll int cmp1, cmp2;
1482a6b7db3Sskrll splay_tree_node n, c;
1492a6b7db3Sskrll
1502a6b7db3Sskrll n = sp->root;
1512a6b7db3Sskrll cmp1 = (*sp->comp) (key, n->key);
1522a6b7db3Sskrll
1532a6b7db3Sskrll /* Found. */
1542a6b7db3Sskrll if (cmp1 == 0)
1552a6b7db3Sskrll return;
1562a6b7db3Sskrll
1572a6b7db3Sskrll /* Left or right? If no child, then we're done. */
1582a6b7db3Sskrll if (cmp1 < 0)
1592a6b7db3Sskrll c = n->left;
1602a6b7db3Sskrll else
1612a6b7db3Sskrll c = n->right;
1622a6b7db3Sskrll if (!c)
1632a6b7db3Sskrll return;
1642a6b7db3Sskrll
1652a6b7db3Sskrll /* Next one left or right? If found or no child, we're done
1662a6b7db3Sskrll after one rotation. */
1672a6b7db3Sskrll cmp2 = (*sp->comp) (key, c->key);
1682a6b7db3Sskrll if (cmp2 == 0
1692a6b7db3Sskrll || (cmp2 < 0 && !c->left)
1702a6b7db3Sskrll || (cmp2 > 0 && !c->right))
1712a6b7db3Sskrll {
1722a6b7db3Sskrll if (cmp1 < 0)
1732a6b7db3Sskrll rotate_left (&sp->root, n, c);
1742a6b7db3Sskrll else
1752a6b7db3Sskrll rotate_right (&sp->root, n, c);
1762a6b7db3Sskrll return;
1772a6b7db3Sskrll }
1782a6b7db3Sskrll
1792a6b7db3Sskrll /* Now we have the four cases of double-rotation. */
1802a6b7db3Sskrll if (cmp1 < 0 && cmp2 < 0)
1812a6b7db3Sskrll {
1822a6b7db3Sskrll rotate_left (&n->left, c, c->left);
1832a6b7db3Sskrll rotate_left (&sp->root, n, n->left);
1842a6b7db3Sskrll }
1852a6b7db3Sskrll else if (cmp1 > 0 && cmp2 > 0)
1862a6b7db3Sskrll {
1872a6b7db3Sskrll rotate_right (&n->right, c, c->right);
1882a6b7db3Sskrll rotate_right (&sp->root, n, n->right);
1892a6b7db3Sskrll }
1902a6b7db3Sskrll else if (cmp1 < 0 && cmp2 > 0)
1912a6b7db3Sskrll {
1922a6b7db3Sskrll rotate_right (&n->left, c, c->right);
1932a6b7db3Sskrll rotate_left (&sp->root, n, n->left);
1942a6b7db3Sskrll }
1952a6b7db3Sskrll else if (cmp1 > 0 && cmp2 < 0)
1962a6b7db3Sskrll {
1972a6b7db3Sskrll rotate_left (&n->right, c, c->left);
1982a6b7db3Sskrll rotate_right (&sp->root, n, n->right);
1992a6b7db3Sskrll }
2002a6b7db3Sskrll } while (1);
2012a6b7db3Sskrll }
2022a6b7db3Sskrll
2032a6b7db3Sskrll /* Call FN, passing it the DATA, for every node below NODE, all of
2042a6b7db3Sskrll which are from SP, following an in-order traversal. If FN every
2052a6b7db3Sskrll returns a non-zero value, the iteration ceases immediately, and the
2062a6b7db3Sskrll value is returned. Otherwise, this function returns 0. */
2072a6b7db3Sskrll
2082a6b7db3Sskrll static int
splay_tree_foreach_helper(splay_tree_node node,splay_tree_foreach_fn fn,void * data)20905caefcfSchristos splay_tree_foreach_helper (splay_tree_node node,
2102a6b7db3Sskrll splay_tree_foreach_fn fn, void *data)
2112a6b7db3Sskrll {
2122a6b7db3Sskrll int val;
21305caefcfSchristos splay_tree_node *stack;
21405caefcfSchristos int stack_ptr, stack_size;
2152a6b7db3Sskrll
21605caefcfSchristos /* A non-recursive implementation is used to avoid filling the stack
21705caefcfSchristos for large trees. Splay trees are worst case O(n) in the depth of
21805caefcfSchristos the tree. */
2192a6b7db3Sskrll
22005caefcfSchristos #define INITIAL_STACK_SIZE 100
22105caefcfSchristos stack_size = INITIAL_STACK_SIZE;
22205caefcfSchristos stack_ptr = 0;
22305caefcfSchristos stack = XNEWVEC (splay_tree_node, stack_size);
22405caefcfSchristos val = 0;
22505caefcfSchristos
22605caefcfSchristos for (;;)
22705caefcfSchristos {
22805caefcfSchristos while (node != NULL)
22905caefcfSchristos {
23005caefcfSchristos if (stack_ptr == stack_size)
23105caefcfSchristos {
23205caefcfSchristos stack_size *= 2;
23305caefcfSchristos stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
23405caefcfSchristos }
23505caefcfSchristos stack[stack_ptr++] = node;
23605caefcfSchristos node = node->left;
23705caefcfSchristos }
23805caefcfSchristos
23905caefcfSchristos if (stack_ptr == 0)
24005caefcfSchristos break;
24105caefcfSchristos
24205caefcfSchristos node = stack[--stack_ptr];
2432a6b7db3Sskrll
2442a6b7db3Sskrll val = (*fn) (node, data);
2452a6b7db3Sskrll if (val)
24605caefcfSchristos break;
2472a6b7db3Sskrll
24805caefcfSchristos node = node->right;
2492a6b7db3Sskrll }
2502a6b7db3Sskrll
25105caefcfSchristos XDELETEVEC (stack);
25205caefcfSchristos return val;
25305caefcfSchristos }
2542a6b7db3Sskrll
2552a6b7db3Sskrll /* An allocator and deallocator based on xmalloc. */
2562a6b7db3Sskrll static void *
splay_tree_xmalloc_allocate(int size,void * data ATTRIBUTE_UNUSED)2572a6b7db3Sskrll splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
2582a6b7db3Sskrll {
2592a6b7db3Sskrll return (void *) xmalloc (size);
2602a6b7db3Sskrll }
2612a6b7db3Sskrll
2622a6b7db3Sskrll static void
splay_tree_xmalloc_deallocate(void * object,void * data ATTRIBUTE_UNUSED)2632a6b7db3Sskrll splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
2642a6b7db3Sskrll {
2652a6b7db3Sskrll free (object);
2662a6b7db3Sskrll }
2672a6b7db3Sskrll
2682a6b7db3Sskrll
2692a6b7db3Sskrll /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
2702a6b7db3Sskrll DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
2712a6b7db3Sskrll values. Use xmalloc to allocate the splay tree structure, and any
2722a6b7db3Sskrll nodes added. */
2732a6b7db3Sskrll
2742a6b7db3Sskrll splay_tree
splay_tree_new(splay_tree_compare_fn compare_fn,splay_tree_delete_key_fn delete_key_fn,splay_tree_delete_value_fn delete_value_fn)2752a6b7db3Sskrll splay_tree_new (splay_tree_compare_fn compare_fn,
2762a6b7db3Sskrll splay_tree_delete_key_fn delete_key_fn,
2772a6b7db3Sskrll splay_tree_delete_value_fn delete_value_fn)
2782a6b7db3Sskrll {
2792a6b7db3Sskrll return (splay_tree_new_with_allocator
2802a6b7db3Sskrll (compare_fn, delete_key_fn, delete_value_fn,
2812a6b7db3Sskrll splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
2822a6b7db3Sskrll }
2832a6b7db3Sskrll
2842a6b7db3Sskrll
2852a6b7db3Sskrll /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
2862a6b7db3Sskrll DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
2872a6b7db3Sskrll values. */
2882a6b7db3Sskrll
2892a6b7db3Sskrll splay_tree
splay_tree_new_with_allocator(splay_tree_compare_fn compare_fn,splay_tree_delete_key_fn delete_key_fn,splay_tree_delete_value_fn delete_value_fn,splay_tree_allocate_fn allocate_fn,splay_tree_deallocate_fn deallocate_fn,void * allocate_data)2902a6b7db3Sskrll splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
2912a6b7db3Sskrll splay_tree_delete_key_fn delete_key_fn,
2922a6b7db3Sskrll splay_tree_delete_value_fn delete_value_fn,
2932a6b7db3Sskrll splay_tree_allocate_fn allocate_fn,
2942a6b7db3Sskrll splay_tree_deallocate_fn deallocate_fn,
2952a6b7db3Sskrll void *allocate_data)
2962a6b7db3Sskrll {
297b3ac4aedSchristos return
298b3ac4aedSchristos splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
299b3ac4aedSchristos allocate_fn, allocate_fn, deallocate_fn,
3002a6b7db3Sskrll allocate_data);
301b3ac4aedSchristos }
302b3ac4aedSchristos
303b3ac4aedSchristos /*
304b3ac4aedSchristos
30505caefcfSchristos @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
30605caefcfSchristos (splay_tree_compare_fn @var{compare_fn}, @
30705caefcfSchristos splay_tree_delete_key_fn @var{delete_key_fn}, @
30805caefcfSchristos splay_tree_delete_value_fn @var{delete_value_fn}, @
30905caefcfSchristos splay_tree_allocate_fn @var{tree_allocate_fn}, @
31005caefcfSchristos splay_tree_allocate_fn @var{node_allocate_fn}, @
31105caefcfSchristos splay_tree_deallocate_fn @var{deallocate_fn}, @
312b3ac4aedSchristos void * @var{allocate_data})
313b3ac4aedSchristos
314b3ac4aedSchristos This function creates a splay tree that uses two different allocators
315b3ac4aedSchristos @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
316b3ac4aedSchristos tree itself and its nodes respectively. This is useful when variables of
317b3ac4aedSchristos different types need to be allocated with different allocators.
318b3ac4aedSchristos
319b3ac4aedSchristos The splay tree will use @var{compare_fn} to compare nodes,
320b3ac4aedSchristos @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
321f7172901Schristos deallocate values. Keys and values will be deallocated when the
322f7172901Schristos tree is deleted using splay_tree_delete or when a node is removed
323f7172901Schristos using splay_tree_remove. splay_tree_insert will release the previously
324f7172901Schristos inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
325f7172901Schristos if the inserted key is already found in the tree.
326b3ac4aedSchristos
327b3ac4aedSchristos @end deftypefn
328b3ac4aedSchristos
329b3ac4aedSchristos */
330b3ac4aedSchristos
331b3ac4aedSchristos splay_tree
splay_tree_new_typed_alloc(splay_tree_compare_fn compare_fn,splay_tree_delete_key_fn delete_key_fn,splay_tree_delete_value_fn delete_value_fn,splay_tree_allocate_fn tree_allocate_fn,splay_tree_allocate_fn node_allocate_fn,splay_tree_deallocate_fn deallocate_fn,void * allocate_data)332b3ac4aedSchristos splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
333b3ac4aedSchristos splay_tree_delete_key_fn delete_key_fn,
334b3ac4aedSchristos splay_tree_delete_value_fn delete_value_fn,
335b3ac4aedSchristos splay_tree_allocate_fn tree_allocate_fn,
336b3ac4aedSchristos splay_tree_allocate_fn node_allocate_fn,
337b3ac4aedSchristos splay_tree_deallocate_fn deallocate_fn,
338b3ac4aedSchristos void * allocate_data)
339b3ac4aedSchristos {
340b3ac4aedSchristos splay_tree sp = (splay_tree) (*tree_allocate_fn)
341b3ac4aedSchristos (sizeof (struct splay_tree_s), allocate_data);
342b3ac4aedSchristos
3432a6b7db3Sskrll sp->root = 0;
3442a6b7db3Sskrll sp->comp = compare_fn;
3452a6b7db3Sskrll sp->delete_key = delete_key_fn;
3462a6b7db3Sskrll sp->delete_value = delete_value_fn;
347b3ac4aedSchristos sp->allocate = node_allocate_fn;
3482a6b7db3Sskrll sp->deallocate = deallocate_fn;
3492a6b7db3Sskrll sp->allocate_data = allocate_data;
3502a6b7db3Sskrll
3512a6b7db3Sskrll return sp;
3522a6b7db3Sskrll }
3532a6b7db3Sskrll
3542a6b7db3Sskrll /* Deallocate SP. */
3552a6b7db3Sskrll
3562a6b7db3Sskrll void
splay_tree_delete(splay_tree sp)3572a6b7db3Sskrll splay_tree_delete (splay_tree sp)
3582a6b7db3Sskrll {
3592a6b7db3Sskrll splay_tree_delete_helper (sp, sp->root);
3602a6b7db3Sskrll (*sp->deallocate) ((char*) sp, sp->allocate_data);
3612a6b7db3Sskrll }
3622a6b7db3Sskrll
3632a6b7db3Sskrll /* Insert a new node (associating KEY with DATA) into SP. If a
3642a6b7db3Sskrll previous node with the indicated KEY exists, its data is replaced
3652a6b7db3Sskrll with the new value. Returns the new node. */
3662a6b7db3Sskrll
3672a6b7db3Sskrll splay_tree_node
splay_tree_insert(splay_tree sp,splay_tree_key key,splay_tree_value value)3682a6b7db3Sskrll splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
3692a6b7db3Sskrll {
3702a6b7db3Sskrll int comparison = 0;
3712a6b7db3Sskrll
3722a6b7db3Sskrll splay_tree_splay (sp, key);
3732a6b7db3Sskrll
3742a6b7db3Sskrll if (sp->root)
3752a6b7db3Sskrll comparison = (*sp->comp)(sp->root->key, key);
3762a6b7db3Sskrll
3772a6b7db3Sskrll if (sp->root && comparison == 0)
3782a6b7db3Sskrll {
379f7172901Schristos /* If the root of the tree already has the indicated KEY, delete
380f7172901Schristos the old key and old value, and replace them with KEY and VALUE. */
381f7172901Schristos if (sp->delete_key)
382f7172901Schristos (*sp->delete_key) (sp->root->key);
3832a6b7db3Sskrll if (sp->delete_value)
3842a6b7db3Sskrll (*sp->delete_value)(sp->root->value);
385f7172901Schristos sp->root->key = key;
3862a6b7db3Sskrll sp->root->value = value;
3872a6b7db3Sskrll }
3882a6b7db3Sskrll else
3892a6b7db3Sskrll {
3902a6b7db3Sskrll /* Create a new node, and insert it at the root. */
3912a6b7db3Sskrll splay_tree_node node;
3922a6b7db3Sskrll
3932a6b7db3Sskrll node = ((splay_tree_node)
3942a6b7db3Sskrll (*sp->allocate) (sizeof (struct splay_tree_node_s),
3952a6b7db3Sskrll sp->allocate_data));
3962a6b7db3Sskrll node->key = key;
3972a6b7db3Sskrll node->value = value;
3982a6b7db3Sskrll
3992a6b7db3Sskrll if (!sp->root)
4002a6b7db3Sskrll node->left = node->right = 0;
4012a6b7db3Sskrll else if (comparison < 0)
4022a6b7db3Sskrll {
4032a6b7db3Sskrll node->left = sp->root;
4042a6b7db3Sskrll node->right = node->left->right;
4052a6b7db3Sskrll node->left->right = 0;
4062a6b7db3Sskrll }
4072a6b7db3Sskrll else
4082a6b7db3Sskrll {
4092a6b7db3Sskrll node->right = sp->root;
4102a6b7db3Sskrll node->left = node->right->left;
4112a6b7db3Sskrll node->right->left = 0;
4122a6b7db3Sskrll }
4132a6b7db3Sskrll
4142a6b7db3Sskrll sp->root = node;
4152a6b7db3Sskrll }
4162a6b7db3Sskrll
4172a6b7db3Sskrll return sp->root;
4182a6b7db3Sskrll }
4192a6b7db3Sskrll
4202a6b7db3Sskrll /* Remove KEY from SP. It is not an error if it did not exist. */
4212a6b7db3Sskrll
4222a6b7db3Sskrll void
splay_tree_remove(splay_tree sp,splay_tree_key key)4232a6b7db3Sskrll splay_tree_remove (splay_tree sp, splay_tree_key key)
4242a6b7db3Sskrll {
4252a6b7db3Sskrll splay_tree_splay (sp, key);
4262a6b7db3Sskrll
4272a6b7db3Sskrll if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
4282a6b7db3Sskrll {
4292a6b7db3Sskrll splay_tree_node left, right;
4302a6b7db3Sskrll
4312a6b7db3Sskrll left = sp->root->left;
4322a6b7db3Sskrll right = sp->root->right;
4332a6b7db3Sskrll
4342a6b7db3Sskrll /* Delete the root node itself. */
435f7172901Schristos if (sp->delete_key)
436f7172901Schristos (*sp->delete_key) (sp->root->key);
4372a6b7db3Sskrll if (sp->delete_value)
4382a6b7db3Sskrll (*sp->delete_value) (sp->root->value);
4392a6b7db3Sskrll (*sp->deallocate) (sp->root, sp->allocate_data);
4402a6b7db3Sskrll
4412a6b7db3Sskrll /* One of the children is now the root. Doesn't matter much
4422a6b7db3Sskrll which, so long as we preserve the properties of the tree. */
4432a6b7db3Sskrll if (left)
4442a6b7db3Sskrll {
4452a6b7db3Sskrll sp->root = left;
4462a6b7db3Sskrll
4472a6b7db3Sskrll /* If there was a right child as well, hang it off the
4482a6b7db3Sskrll right-most leaf of the left child. */
4492a6b7db3Sskrll if (right)
4502a6b7db3Sskrll {
4512a6b7db3Sskrll while (left->right)
4522a6b7db3Sskrll left = left->right;
4532a6b7db3Sskrll left->right = right;
4542a6b7db3Sskrll }
4552a6b7db3Sskrll }
4562a6b7db3Sskrll else
4572a6b7db3Sskrll sp->root = right;
4582a6b7db3Sskrll }
4592a6b7db3Sskrll }
4602a6b7db3Sskrll
4612a6b7db3Sskrll /* Lookup KEY in SP, returning VALUE if present, and NULL
4622a6b7db3Sskrll otherwise. */
4632a6b7db3Sskrll
4642a6b7db3Sskrll splay_tree_node
splay_tree_lookup(splay_tree sp,splay_tree_key key)4652a6b7db3Sskrll splay_tree_lookup (splay_tree sp, splay_tree_key key)
4662a6b7db3Sskrll {
4672a6b7db3Sskrll splay_tree_splay (sp, key);
4682a6b7db3Sskrll
4692a6b7db3Sskrll if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
4702a6b7db3Sskrll return sp->root;
4712a6b7db3Sskrll else
4722a6b7db3Sskrll return 0;
4732a6b7db3Sskrll }
4742a6b7db3Sskrll
4752a6b7db3Sskrll /* Return the node in SP with the greatest key. */
4762a6b7db3Sskrll
4772a6b7db3Sskrll splay_tree_node
splay_tree_max(splay_tree sp)4782a6b7db3Sskrll splay_tree_max (splay_tree sp)
4792a6b7db3Sskrll {
4802a6b7db3Sskrll splay_tree_node n = sp->root;
4812a6b7db3Sskrll
4822a6b7db3Sskrll if (!n)
4832a6b7db3Sskrll return NULL;
4842a6b7db3Sskrll
4852a6b7db3Sskrll while (n->right)
4862a6b7db3Sskrll n = n->right;
4872a6b7db3Sskrll
4882a6b7db3Sskrll return n;
4892a6b7db3Sskrll }
4902a6b7db3Sskrll
4912a6b7db3Sskrll /* Return the node in SP with the smallest key. */
4922a6b7db3Sskrll
4932a6b7db3Sskrll splay_tree_node
splay_tree_min(splay_tree sp)4942a6b7db3Sskrll splay_tree_min (splay_tree sp)
4952a6b7db3Sskrll {
4962a6b7db3Sskrll splay_tree_node n = sp->root;
4972a6b7db3Sskrll
4982a6b7db3Sskrll if (!n)
4992a6b7db3Sskrll return NULL;
5002a6b7db3Sskrll
5012a6b7db3Sskrll while (n->left)
5022a6b7db3Sskrll n = n->left;
5032a6b7db3Sskrll
5042a6b7db3Sskrll return n;
5052a6b7db3Sskrll }
5062a6b7db3Sskrll
5072a6b7db3Sskrll /* Return the immediate predecessor KEY, or NULL if there is no
5082a6b7db3Sskrll predecessor. KEY need not be present in the tree. */
5092a6b7db3Sskrll
5102a6b7db3Sskrll splay_tree_node
splay_tree_predecessor(splay_tree sp,splay_tree_key key)5112a6b7db3Sskrll splay_tree_predecessor (splay_tree sp, splay_tree_key key)
5122a6b7db3Sskrll {
5132a6b7db3Sskrll int comparison;
5142a6b7db3Sskrll splay_tree_node node;
5152a6b7db3Sskrll
5162a6b7db3Sskrll /* If the tree is empty, there is certainly no predecessor. */
5172a6b7db3Sskrll if (!sp->root)
5182a6b7db3Sskrll return NULL;
5192a6b7db3Sskrll
5202a6b7db3Sskrll /* Splay the tree around KEY. That will leave either the KEY
5212a6b7db3Sskrll itself, its predecessor, or its successor at the root. */
5222a6b7db3Sskrll splay_tree_splay (sp, key);
5232a6b7db3Sskrll comparison = (*sp->comp)(sp->root->key, key);
5242a6b7db3Sskrll
5252a6b7db3Sskrll /* If the predecessor is at the root, just return it. */
5262a6b7db3Sskrll if (comparison < 0)
5272a6b7db3Sskrll return sp->root;
5282a6b7db3Sskrll
5292a6b7db3Sskrll /* Otherwise, find the rightmost element of the left subtree. */
5302a6b7db3Sskrll node = sp->root->left;
5312a6b7db3Sskrll if (node)
5322a6b7db3Sskrll while (node->right)
5332a6b7db3Sskrll node = node->right;
5342a6b7db3Sskrll
5352a6b7db3Sskrll return node;
5362a6b7db3Sskrll }
5372a6b7db3Sskrll
5382a6b7db3Sskrll /* Return the immediate successor KEY, or NULL if there is no
5392a6b7db3Sskrll successor. KEY need not be present in the tree. */
5402a6b7db3Sskrll
5412a6b7db3Sskrll splay_tree_node
splay_tree_successor(splay_tree sp,splay_tree_key key)5422a6b7db3Sskrll splay_tree_successor (splay_tree sp, splay_tree_key key)
5432a6b7db3Sskrll {
5442a6b7db3Sskrll int comparison;
5452a6b7db3Sskrll splay_tree_node node;
5462a6b7db3Sskrll
5472a6b7db3Sskrll /* If the tree is empty, there is certainly no successor. */
5482a6b7db3Sskrll if (!sp->root)
5492a6b7db3Sskrll return NULL;
5502a6b7db3Sskrll
5512a6b7db3Sskrll /* Splay the tree around KEY. That will leave either the KEY
5522a6b7db3Sskrll itself, its predecessor, or its successor at the root. */
5532a6b7db3Sskrll splay_tree_splay (sp, key);
5542a6b7db3Sskrll comparison = (*sp->comp)(sp->root->key, key);
5552a6b7db3Sskrll
5562a6b7db3Sskrll /* If the successor is at the root, just return it. */
5572a6b7db3Sskrll if (comparison > 0)
5582a6b7db3Sskrll return sp->root;
5592a6b7db3Sskrll
5602a6b7db3Sskrll /* Otherwise, find the leftmost element of the right subtree. */
5612a6b7db3Sskrll node = sp->root->right;
5622a6b7db3Sskrll if (node)
5632a6b7db3Sskrll while (node->left)
5642a6b7db3Sskrll node = node->left;
5652a6b7db3Sskrll
5662a6b7db3Sskrll return node;
5672a6b7db3Sskrll }
5682a6b7db3Sskrll
5692a6b7db3Sskrll /* Call FN, passing it the DATA, for every node in SP, following an
5702a6b7db3Sskrll in-order traversal. If FN every returns a non-zero value, the
5712a6b7db3Sskrll iteration ceases immediately, and the value is returned.
5722a6b7db3Sskrll Otherwise, this function returns 0. */
5732a6b7db3Sskrll
5742a6b7db3Sskrll int
splay_tree_foreach(splay_tree sp,splay_tree_foreach_fn fn,void * data)5752a6b7db3Sskrll splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
5762a6b7db3Sskrll {
57705caefcfSchristos return splay_tree_foreach_helper (sp->root, fn, data);
5782a6b7db3Sskrll }
5792a6b7db3Sskrll
5802a6b7db3Sskrll /* Splay-tree comparison function, treating the keys as ints. */
5812a6b7db3Sskrll
5822a6b7db3Sskrll int
splay_tree_compare_ints(splay_tree_key k1,splay_tree_key k2)5832a6b7db3Sskrll splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
5842a6b7db3Sskrll {
5852a6b7db3Sskrll if ((int) k1 < (int) k2)
5862a6b7db3Sskrll return -1;
5872a6b7db3Sskrll else if ((int) k1 > (int) k2)
5882a6b7db3Sskrll return 1;
5892a6b7db3Sskrll else
5902a6b7db3Sskrll return 0;
5912a6b7db3Sskrll }
5922a6b7db3Sskrll
5932a6b7db3Sskrll /* Splay-tree comparison function, treating the keys as pointers. */
5942a6b7db3Sskrll
5952a6b7db3Sskrll int
splay_tree_compare_pointers(splay_tree_key k1,splay_tree_key k2)5962a6b7db3Sskrll splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
5972a6b7db3Sskrll {
5982a6b7db3Sskrll if ((char*) k1 < (char*) k2)
5992a6b7db3Sskrll return -1;
6002a6b7db3Sskrll else if ((char*) k1 > (char*) k2)
6012a6b7db3Sskrll return 1;
6022a6b7db3Sskrll else
6032a6b7db3Sskrll return 0;
6042a6b7db3Sskrll }
605fa2c2dd3Schristos
606fa2c2dd3Schristos /* Splay-tree comparison function, treating the keys as strings. */
607fa2c2dd3Schristos
608fa2c2dd3Schristos int
splay_tree_compare_strings(splay_tree_key k1,splay_tree_key k2)609fa2c2dd3Schristos splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
610fa2c2dd3Schristos {
611fa2c2dd3Schristos return strcmp ((char *) k1, (char *) k2);
612fa2c2dd3Schristos }
613fa2c2dd3Schristos
614fa2c2dd3Schristos /* Splay-tree delete function, simply using free. */
615fa2c2dd3Schristos
616fa2c2dd3Schristos void
splay_tree_delete_pointers(splay_tree_value value)617fa2c2dd3Schristos splay_tree_delete_pointers (splay_tree_value value)
618fa2c2dd3Schristos {
619fa2c2dd3Schristos free ((void *) value);
620fa2c2dd3Schristos }
621