1*fae548d3Szrj /* A splay-tree datatype.
2*fae548d3Szrj Copyright (C) 1998-2020 Free Software Foundation, Inc.
3*fae548d3Szrj Contributed by Mark Mitchell (mark@markmitchell.com).
4*fae548d3Szrj
5*fae548d3Szrj This file is part of GNU CC.
6*fae548d3Szrj
7*fae548d3Szrj GNU CC is free software; you can redistribute it and/or modify it
8*fae548d3Szrj under the terms of the GNU General Public License as published by
9*fae548d3Szrj the Free Software Foundation; either version 2, or (at your option)
10*fae548d3Szrj any later version.
11*fae548d3Szrj
12*fae548d3Szrj GNU CC is distributed in the hope that it will be useful, but
13*fae548d3Szrj WITHOUT ANY WARRANTY; without even the implied warranty of
14*fae548d3Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15*fae548d3Szrj General Public License for more details.
16*fae548d3Szrj
17*fae548d3Szrj You should have received a copy of the GNU General Public License
18*fae548d3Szrj along with GNU CC; see the file COPYING. If not, write to
19*fae548d3Szrj the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20*fae548d3Szrj Boston, MA 02110-1301, USA. */
21*fae548d3Szrj
22*fae548d3Szrj /* For an easily readable description of splay-trees, see:
23*fae548d3Szrj
24*fae548d3Szrj Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
25*fae548d3Szrj Algorithms. Harper-Collins, Inc. 1991. */
26*fae548d3Szrj
27*fae548d3Szrj #ifdef HAVE_CONFIG_H
28*fae548d3Szrj #include "config.h"
29*fae548d3Szrj #endif
30*fae548d3Szrj
31*fae548d3Szrj #ifdef HAVE_STDLIB_H
32*fae548d3Szrj #include <stdlib.h>
33*fae548d3Szrj #endif
34*fae548d3Szrj #ifdef HAVE_STRING_H
35*fae548d3Szrj #include <string.h>
36*fae548d3Szrj #endif
37*fae548d3Szrj
38*fae548d3Szrj #include <stdio.h>
39*fae548d3Szrj
40*fae548d3Szrj #include "libiberty.h"
41*fae548d3Szrj #include "splay-tree.h"
42*fae548d3Szrj
43*fae548d3Szrj static void splay_tree_delete_helper (splay_tree, splay_tree_node);
44*fae548d3Szrj static inline void rotate_left (splay_tree_node *,
45*fae548d3Szrj splay_tree_node, splay_tree_node);
46*fae548d3Szrj static inline void rotate_right (splay_tree_node *,
47*fae548d3Szrj splay_tree_node, splay_tree_node);
48*fae548d3Szrj static void splay_tree_splay (splay_tree, splay_tree_key);
49*fae548d3Szrj static int splay_tree_foreach_helper (splay_tree_node,
50*fae548d3Szrj splay_tree_foreach_fn, void*);
51*fae548d3Szrj
52*fae548d3Szrj /* Deallocate NODE (a member of SP), and all its sub-trees. */
53*fae548d3Szrj
54*fae548d3Szrj static void
splay_tree_delete_helper(splay_tree sp,splay_tree_node node)55*fae548d3Szrj splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
56*fae548d3Szrj {
57*fae548d3Szrj splay_tree_node pending = 0;
58*fae548d3Szrj splay_tree_node active = 0;
59*fae548d3Szrj
60*fae548d3Szrj if (!node)
61*fae548d3Szrj return;
62*fae548d3Szrj
63*fae548d3Szrj #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x);
64*fae548d3Szrj #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x);
65*fae548d3Szrj
66*fae548d3Szrj KDEL (node->key);
67*fae548d3Szrj VDEL (node->value);
68*fae548d3Szrj
69*fae548d3Szrj /* We use the "key" field to hold the "next" pointer. */
70*fae548d3Szrj node->key = (splay_tree_key)pending;
71*fae548d3Szrj pending = (splay_tree_node)node;
72*fae548d3Szrj
73*fae548d3Szrj /* Now, keep processing the pending list until there aren't any
74*fae548d3Szrj more. This is a little more complicated than just recursing, but
75*fae548d3Szrj it doesn't toast the stack for large trees. */
76*fae548d3Szrj
77*fae548d3Szrj while (pending)
78*fae548d3Szrj {
79*fae548d3Szrj active = pending;
80*fae548d3Szrj pending = 0;
81*fae548d3Szrj while (active)
82*fae548d3Szrj {
83*fae548d3Szrj splay_tree_node temp;
84*fae548d3Szrj
85*fae548d3Szrj /* active points to a node which has its key and value
86*fae548d3Szrj deallocated, we just need to process left and right. */
87*fae548d3Szrj
88*fae548d3Szrj if (active->left)
89*fae548d3Szrj {
90*fae548d3Szrj KDEL (active->left->key);
91*fae548d3Szrj VDEL (active->left->value);
92*fae548d3Szrj active->left->key = (splay_tree_key)pending;
93*fae548d3Szrj pending = (splay_tree_node)(active->left);
94*fae548d3Szrj }
95*fae548d3Szrj if (active->right)
96*fae548d3Szrj {
97*fae548d3Szrj KDEL (active->right->key);
98*fae548d3Szrj VDEL (active->right->value);
99*fae548d3Szrj active->right->key = (splay_tree_key)pending;
100*fae548d3Szrj pending = (splay_tree_node)(active->right);
101*fae548d3Szrj }
102*fae548d3Szrj
103*fae548d3Szrj temp = active;
104*fae548d3Szrj active = (splay_tree_node)(temp->key);
105*fae548d3Szrj (*sp->deallocate) ((char*) temp, sp->allocate_data);
106*fae548d3Szrj }
107*fae548d3Szrj }
108*fae548d3Szrj #undef KDEL
109*fae548d3Szrj #undef VDEL
110*fae548d3Szrj }
111*fae548d3Szrj
112*fae548d3Szrj /* Rotate the edge joining the left child N with its parent P. PP is the
113*fae548d3Szrj grandparents' pointer to P. */
114*fae548d3Szrj
115*fae548d3Szrj static inline void
rotate_left(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)116*fae548d3Szrj rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
117*fae548d3Szrj {
118*fae548d3Szrj splay_tree_node tmp;
119*fae548d3Szrj tmp = n->right;
120*fae548d3Szrj n->right = p;
121*fae548d3Szrj p->left = tmp;
122*fae548d3Szrj *pp = n;
123*fae548d3Szrj }
124*fae548d3Szrj
125*fae548d3Szrj /* Rotate the edge joining the right child N with its parent P. PP is the
126*fae548d3Szrj grandparents' pointer to P. */
127*fae548d3Szrj
128*fae548d3Szrj static inline void
rotate_right(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)129*fae548d3Szrj rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
130*fae548d3Szrj {
131*fae548d3Szrj splay_tree_node tmp;
132*fae548d3Szrj tmp = n->left;
133*fae548d3Szrj n->left = p;
134*fae548d3Szrj p->right = tmp;
135*fae548d3Szrj *pp = n;
136*fae548d3Szrj }
137*fae548d3Szrj
138*fae548d3Szrj /* Bottom up splay of key. */
139*fae548d3Szrj
140*fae548d3Szrj static void
splay_tree_splay(splay_tree sp,splay_tree_key key)141*fae548d3Szrj splay_tree_splay (splay_tree sp, splay_tree_key key)
142*fae548d3Szrj {
143*fae548d3Szrj if (sp->root == 0)
144*fae548d3Szrj return;
145*fae548d3Szrj
146*fae548d3Szrj do {
147*fae548d3Szrj int cmp1, cmp2;
148*fae548d3Szrj splay_tree_node n, c;
149*fae548d3Szrj
150*fae548d3Szrj n = sp->root;
151*fae548d3Szrj cmp1 = (*sp->comp) (key, n->key);
152*fae548d3Szrj
153*fae548d3Szrj /* Found. */
154*fae548d3Szrj if (cmp1 == 0)
155*fae548d3Szrj return;
156*fae548d3Szrj
157*fae548d3Szrj /* Left or right? If no child, then we're done. */
158*fae548d3Szrj if (cmp1 < 0)
159*fae548d3Szrj c = n->left;
160*fae548d3Szrj else
161*fae548d3Szrj c = n->right;
162*fae548d3Szrj if (!c)
163*fae548d3Szrj return;
164*fae548d3Szrj
165*fae548d3Szrj /* Next one left or right? If found or no child, we're done
166*fae548d3Szrj after one rotation. */
167*fae548d3Szrj cmp2 = (*sp->comp) (key, c->key);
168*fae548d3Szrj if (cmp2 == 0
169*fae548d3Szrj || (cmp2 < 0 && !c->left)
170*fae548d3Szrj || (cmp2 > 0 && !c->right))
171*fae548d3Szrj {
172*fae548d3Szrj if (cmp1 < 0)
173*fae548d3Szrj rotate_left (&sp->root, n, c);
174*fae548d3Szrj else
175*fae548d3Szrj rotate_right (&sp->root, n, c);
176*fae548d3Szrj return;
177*fae548d3Szrj }
178*fae548d3Szrj
179*fae548d3Szrj /* Now we have the four cases of double-rotation. */
180*fae548d3Szrj if (cmp1 < 0 && cmp2 < 0)
181*fae548d3Szrj {
182*fae548d3Szrj rotate_left (&n->left, c, c->left);
183*fae548d3Szrj rotate_left (&sp->root, n, n->left);
184*fae548d3Szrj }
185*fae548d3Szrj else if (cmp1 > 0 && cmp2 > 0)
186*fae548d3Szrj {
187*fae548d3Szrj rotate_right (&n->right, c, c->right);
188*fae548d3Szrj rotate_right (&sp->root, n, n->right);
189*fae548d3Szrj }
190*fae548d3Szrj else if (cmp1 < 0 && cmp2 > 0)
191*fae548d3Szrj {
192*fae548d3Szrj rotate_right (&n->left, c, c->right);
193*fae548d3Szrj rotate_left (&sp->root, n, n->left);
194*fae548d3Szrj }
195*fae548d3Szrj else if (cmp1 > 0 && cmp2 < 0)
196*fae548d3Szrj {
197*fae548d3Szrj rotate_left (&n->right, c, c->left);
198*fae548d3Szrj rotate_right (&sp->root, n, n->right);
199*fae548d3Szrj }
200*fae548d3Szrj } while (1);
201*fae548d3Szrj }
202*fae548d3Szrj
203*fae548d3Szrj /* Call FN, passing it the DATA, for every node below NODE, all of
204*fae548d3Szrj which are from SP, following an in-order traversal. If FN every
205*fae548d3Szrj returns a non-zero value, the iteration ceases immediately, and the
206*fae548d3Szrj value is returned. Otherwise, this function returns 0. */
207*fae548d3Szrj
208*fae548d3Szrj static int
splay_tree_foreach_helper(splay_tree_node node,splay_tree_foreach_fn fn,void * data)209*fae548d3Szrj splay_tree_foreach_helper (splay_tree_node node,
210*fae548d3Szrj splay_tree_foreach_fn fn, void *data)
211*fae548d3Szrj {
212*fae548d3Szrj int val;
213*fae548d3Szrj splay_tree_node *stack;
214*fae548d3Szrj int stack_ptr, stack_size;
215*fae548d3Szrj
216*fae548d3Szrj /* A non-recursive implementation is used to avoid filling the stack
217*fae548d3Szrj for large trees. Splay trees are worst case O(n) in the depth of
218*fae548d3Szrj the tree. */
219*fae548d3Szrj
220*fae548d3Szrj #define INITIAL_STACK_SIZE 100
221*fae548d3Szrj stack_size = INITIAL_STACK_SIZE;
222*fae548d3Szrj stack_ptr = 0;
223*fae548d3Szrj stack = XNEWVEC (splay_tree_node, stack_size);
224*fae548d3Szrj val = 0;
225*fae548d3Szrj
226*fae548d3Szrj for (;;)
227*fae548d3Szrj {
228*fae548d3Szrj while (node != NULL)
229*fae548d3Szrj {
230*fae548d3Szrj if (stack_ptr == stack_size)
231*fae548d3Szrj {
232*fae548d3Szrj stack_size *= 2;
233*fae548d3Szrj stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
234*fae548d3Szrj }
235*fae548d3Szrj stack[stack_ptr++] = node;
236*fae548d3Szrj node = node->left;
237*fae548d3Szrj }
238*fae548d3Szrj
239*fae548d3Szrj if (stack_ptr == 0)
240*fae548d3Szrj break;
241*fae548d3Szrj
242*fae548d3Szrj node = stack[--stack_ptr];
243*fae548d3Szrj
244*fae548d3Szrj val = (*fn) (node, data);
245*fae548d3Szrj if (val)
246*fae548d3Szrj break;
247*fae548d3Szrj
248*fae548d3Szrj node = node->right;
249*fae548d3Szrj }
250*fae548d3Szrj
251*fae548d3Szrj XDELETEVEC (stack);
252*fae548d3Szrj return val;
253*fae548d3Szrj }
254*fae548d3Szrj
255*fae548d3Szrj /* An allocator and deallocator based on xmalloc. */
256*fae548d3Szrj static void *
splay_tree_xmalloc_allocate(int size,void * data ATTRIBUTE_UNUSED)257*fae548d3Szrj splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
258*fae548d3Szrj {
259*fae548d3Szrj return (void *) xmalloc (size);
260*fae548d3Szrj }
261*fae548d3Szrj
262*fae548d3Szrj static void
splay_tree_xmalloc_deallocate(void * object,void * data ATTRIBUTE_UNUSED)263*fae548d3Szrj splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
264*fae548d3Szrj {
265*fae548d3Szrj free (object);
266*fae548d3Szrj }
267*fae548d3Szrj
268*fae548d3Szrj
269*fae548d3Szrj /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
270*fae548d3Szrj DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
271*fae548d3Szrj values. Use xmalloc to allocate the splay tree structure, and any
272*fae548d3Szrj nodes added. */
273*fae548d3Szrj
274*fae548d3Szrj 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)275*fae548d3Szrj splay_tree_new (splay_tree_compare_fn compare_fn,
276*fae548d3Szrj splay_tree_delete_key_fn delete_key_fn,
277*fae548d3Szrj splay_tree_delete_value_fn delete_value_fn)
278*fae548d3Szrj {
279*fae548d3Szrj return (splay_tree_new_with_allocator
280*fae548d3Szrj (compare_fn, delete_key_fn, delete_value_fn,
281*fae548d3Szrj splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
282*fae548d3Szrj }
283*fae548d3Szrj
284*fae548d3Szrj
285*fae548d3Szrj /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
286*fae548d3Szrj DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
287*fae548d3Szrj values. */
288*fae548d3Szrj
289*fae548d3Szrj 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)290*fae548d3Szrj splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
291*fae548d3Szrj splay_tree_delete_key_fn delete_key_fn,
292*fae548d3Szrj splay_tree_delete_value_fn delete_value_fn,
293*fae548d3Szrj splay_tree_allocate_fn allocate_fn,
294*fae548d3Szrj splay_tree_deallocate_fn deallocate_fn,
295*fae548d3Szrj void *allocate_data)
296*fae548d3Szrj {
297*fae548d3Szrj return
298*fae548d3Szrj splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
299*fae548d3Szrj allocate_fn, allocate_fn, deallocate_fn,
300*fae548d3Szrj allocate_data);
301*fae548d3Szrj }
302*fae548d3Szrj
303*fae548d3Szrj /*
304*fae548d3Szrj
305*fae548d3Szrj @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
306*fae548d3Szrj (splay_tree_compare_fn @var{compare_fn}, @
307*fae548d3Szrj splay_tree_delete_key_fn @var{delete_key_fn}, @
308*fae548d3Szrj splay_tree_delete_value_fn @var{delete_value_fn}, @
309*fae548d3Szrj splay_tree_allocate_fn @var{tree_allocate_fn}, @
310*fae548d3Szrj splay_tree_allocate_fn @var{node_allocate_fn}, @
311*fae548d3Szrj splay_tree_deallocate_fn @var{deallocate_fn}, @
312*fae548d3Szrj void * @var{allocate_data})
313*fae548d3Szrj
314*fae548d3Szrj This function creates a splay tree that uses two different allocators
315*fae548d3Szrj @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
316*fae548d3Szrj tree itself and its nodes respectively. This is useful when variables of
317*fae548d3Szrj different types need to be allocated with different allocators.
318*fae548d3Szrj
319*fae548d3Szrj The splay tree will use @var{compare_fn} to compare nodes,
320*fae548d3Szrj @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
321*fae548d3Szrj deallocate values. Keys and values will be deallocated when the
322*fae548d3Szrj tree is deleted using splay_tree_delete or when a node is removed
323*fae548d3Szrj using splay_tree_remove. splay_tree_insert will release the previously
324*fae548d3Szrj inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
325*fae548d3Szrj if the inserted key is already found in the tree.
326*fae548d3Szrj
327*fae548d3Szrj @end deftypefn
328*fae548d3Szrj
329*fae548d3Szrj */
330*fae548d3Szrj
331*fae548d3Szrj 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)332*fae548d3Szrj splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
333*fae548d3Szrj splay_tree_delete_key_fn delete_key_fn,
334*fae548d3Szrj splay_tree_delete_value_fn delete_value_fn,
335*fae548d3Szrj splay_tree_allocate_fn tree_allocate_fn,
336*fae548d3Szrj splay_tree_allocate_fn node_allocate_fn,
337*fae548d3Szrj splay_tree_deallocate_fn deallocate_fn,
338*fae548d3Szrj void * allocate_data)
339*fae548d3Szrj {
340*fae548d3Szrj splay_tree sp = (splay_tree) (*tree_allocate_fn)
341*fae548d3Szrj (sizeof (struct splay_tree_s), allocate_data);
342*fae548d3Szrj
343*fae548d3Szrj sp->root = 0;
344*fae548d3Szrj sp->comp = compare_fn;
345*fae548d3Szrj sp->delete_key = delete_key_fn;
346*fae548d3Szrj sp->delete_value = delete_value_fn;
347*fae548d3Szrj sp->allocate = node_allocate_fn;
348*fae548d3Szrj sp->deallocate = deallocate_fn;
349*fae548d3Szrj sp->allocate_data = allocate_data;
350*fae548d3Szrj
351*fae548d3Szrj return sp;
352*fae548d3Szrj }
353*fae548d3Szrj
354*fae548d3Szrj /* Deallocate SP. */
355*fae548d3Szrj
356*fae548d3Szrj void
splay_tree_delete(splay_tree sp)357*fae548d3Szrj splay_tree_delete (splay_tree sp)
358*fae548d3Szrj {
359*fae548d3Szrj splay_tree_delete_helper (sp, sp->root);
360*fae548d3Szrj (*sp->deallocate) ((char*) sp, sp->allocate_data);
361*fae548d3Szrj }
362*fae548d3Szrj
363*fae548d3Szrj /* Insert a new node (associating KEY with DATA) into SP. If a
364*fae548d3Szrj previous node with the indicated KEY exists, its data is replaced
365*fae548d3Szrj with the new value. Returns the new node. */
366*fae548d3Szrj
367*fae548d3Szrj splay_tree_node
splay_tree_insert(splay_tree sp,splay_tree_key key,splay_tree_value value)368*fae548d3Szrj splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
369*fae548d3Szrj {
370*fae548d3Szrj int comparison = 0;
371*fae548d3Szrj
372*fae548d3Szrj splay_tree_splay (sp, key);
373*fae548d3Szrj
374*fae548d3Szrj if (sp->root)
375*fae548d3Szrj comparison = (*sp->comp)(sp->root->key, key);
376*fae548d3Szrj
377*fae548d3Szrj if (sp->root && comparison == 0)
378*fae548d3Szrj {
379*fae548d3Szrj /* If the root of the tree already has the indicated KEY, delete
380*fae548d3Szrj the old key and old value, and replace them with KEY and VALUE. */
381*fae548d3Szrj if (sp->delete_key)
382*fae548d3Szrj (*sp->delete_key) (sp->root->key);
383*fae548d3Szrj if (sp->delete_value)
384*fae548d3Szrj (*sp->delete_value)(sp->root->value);
385*fae548d3Szrj sp->root->key = key;
386*fae548d3Szrj sp->root->value = value;
387*fae548d3Szrj }
388*fae548d3Szrj else
389*fae548d3Szrj {
390*fae548d3Szrj /* Create a new node, and insert it at the root. */
391*fae548d3Szrj splay_tree_node node;
392*fae548d3Szrj
393*fae548d3Szrj node = ((splay_tree_node)
394*fae548d3Szrj (*sp->allocate) (sizeof (struct splay_tree_node_s),
395*fae548d3Szrj sp->allocate_data));
396*fae548d3Szrj node->key = key;
397*fae548d3Szrj node->value = value;
398*fae548d3Szrj
399*fae548d3Szrj if (!sp->root)
400*fae548d3Szrj node->left = node->right = 0;
401*fae548d3Szrj else if (comparison < 0)
402*fae548d3Szrj {
403*fae548d3Szrj node->left = sp->root;
404*fae548d3Szrj node->right = node->left->right;
405*fae548d3Szrj node->left->right = 0;
406*fae548d3Szrj }
407*fae548d3Szrj else
408*fae548d3Szrj {
409*fae548d3Szrj node->right = sp->root;
410*fae548d3Szrj node->left = node->right->left;
411*fae548d3Szrj node->right->left = 0;
412*fae548d3Szrj }
413*fae548d3Szrj
414*fae548d3Szrj sp->root = node;
415*fae548d3Szrj }
416*fae548d3Szrj
417*fae548d3Szrj return sp->root;
418*fae548d3Szrj }
419*fae548d3Szrj
420*fae548d3Szrj /* Remove KEY from SP. It is not an error if it did not exist. */
421*fae548d3Szrj
422*fae548d3Szrj void
splay_tree_remove(splay_tree sp,splay_tree_key key)423*fae548d3Szrj splay_tree_remove (splay_tree sp, splay_tree_key key)
424*fae548d3Szrj {
425*fae548d3Szrj splay_tree_splay (sp, key);
426*fae548d3Szrj
427*fae548d3Szrj if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
428*fae548d3Szrj {
429*fae548d3Szrj splay_tree_node left, right;
430*fae548d3Szrj
431*fae548d3Szrj left = sp->root->left;
432*fae548d3Szrj right = sp->root->right;
433*fae548d3Szrj
434*fae548d3Szrj /* Delete the root node itself. */
435*fae548d3Szrj if (sp->delete_key)
436*fae548d3Szrj (*sp->delete_key) (sp->root->key);
437*fae548d3Szrj if (sp->delete_value)
438*fae548d3Szrj (*sp->delete_value) (sp->root->value);
439*fae548d3Szrj (*sp->deallocate) (sp->root, sp->allocate_data);
440*fae548d3Szrj
441*fae548d3Szrj /* One of the children is now the root. Doesn't matter much
442*fae548d3Szrj which, so long as we preserve the properties of the tree. */
443*fae548d3Szrj if (left)
444*fae548d3Szrj {
445*fae548d3Szrj sp->root = left;
446*fae548d3Szrj
447*fae548d3Szrj /* If there was a right child as well, hang it off the
448*fae548d3Szrj right-most leaf of the left child. */
449*fae548d3Szrj if (right)
450*fae548d3Szrj {
451*fae548d3Szrj while (left->right)
452*fae548d3Szrj left = left->right;
453*fae548d3Szrj left->right = right;
454*fae548d3Szrj }
455*fae548d3Szrj }
456*fae548d3Szrj else
457*fae548d3Szrj sp->root = right;
458*fae548d3Szrj }
459*fae548d3Szrj }
460*fae548d3Szrj
461*fae548d3Szrj /* Lookup KEY in SP, returning VALUE if present, and NULL
462*fae548d3Szrj otherwise. */
463*fae548d3Szrj
464*fae548d3Szrj splay_tree_node
splay_tree_lookup(splay_tree sp,splay_tree_key key)465*fae548d3Szrj splay_tree_lookup (splay_tree sp, splay_tree_key key)
466*fae548d3Szrj {
467*fae548d3Szrj splay_tree_splay (sp, key);
468*fae548d3Szrj
469*fae548d3Szrj if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
470*fae548d3Szrj return sp->root;
471*fae548d3Szrj else
472*fae548d3Szrj return 0;
473*fae548d3Szrj }
474*fae548d3Szrj
475*fae548d3Szrj /* Return the node in SP with the greatest key. */
476*fae548d3Szrj
477*fae548d3Szrj splay_tree_node
splay_tree_max(splay_tree sp)478*fae548d3Szrj splay_tree_max (splay_tree sp)
479*fae548d3Szrj {
480*fae548d3Szrj splay_tree_node n = sp->root;
481*fae548d3Szrj
482*fae548d3Szrj if (!n)
483*fae548d3Szrj return NULL;
484*fae548d3Szrj
485*fae548d3Szrj while (n->right)
486*fae548d3Szrj n = n->right;
487*fae548d3Szrj
488*fae548d3Szrj return n;
489*fae548d3Szrj }
490*fae548d3Szrj
491*fae548d3Szrj /* Return the node in SP with the smallest key. */
492*fae548d3Szrj
493*fae548d3Szrj splay_tree_node
splay_tree_min(splay_tree sp)494*fae548d3Szrj splay_tree_min (splay_tree sp)
495*fae548d3Szrj {
496*fae548d3Szrj splay_tree_node n = sp->root;
497*fae548d3Szrj
498*fae548d3Szrj if (!n)
499*fae548d3Szrj return NULL;
500*fae548d3Szrj
501*fae548d3Szrj while (n->left)
502*fae548d3Szrj n = n->left;
503*fae548d3Szrj
504*fae548d3Szrj return n;
505*fae548d3Szrj }
506*fae548d3Szrj
507*fae548d3Szrj /* Return the immediate predecessor KEY, or NULL if there is no
508*fae548d3Szrj predecessor. KEY need not be present in the tree. */
509*fae548d3Szrj
510*fae548d3Szrj splay_tree_node
splay_tree_predecessor(splay_tree sp,splay_tree_key key)511*fae548d3Szrj splay_tree_predecessor (splay_tree sp, splay_tree_key key)
512*fae548d3Szrj {
513*fae548d3Szrj int comparison;
514*fae548d3Szrj splay_tree_node node;
515*fae548d3Szrj
516*fae548d3Szrj /* If the tree is empty, there is certainly no predecessor. */
517*fae548d3Szrj if (!sp->root)
518*fae548d3Szrj return NULL;
519*fae548d3Szrj
520*fae548d3Szrj /* Splay the tree around KEY. That will leave either the KEY
521*fae548d3Szrj itself, its predecessor, or its successor at the root. */
522*fae548d3Szrj splay_tree_splay (sp, key);
523*fae548d3Szrj comparison = (*sp->comp)(sp->root->key, key);
524*fae548d3Szrj
525*fae548d3Szrj /* If the predecessor is at the root, just return it. */
526*fae548d3Szrj if (comparison < 0)
527*fae548d3Szrj return sp->root;
528*fae548d3Szrj
529*fae548d3Szrj /* Otherwise, find the rightmost element of the left subtree. */
530*fae548d3Szrj node = sp->root->left;
531*fae548d3Szrj if (node)
532*fae548d3Szrj while (node->right)
533*fae548d3Szrj node = node->right;
534*fae548d3Szrj
535*fae548d3Szrj return node;
536*fae548d3Szrj }
537*fae548d3Szrj
538*fae548d3Szrj /* Return the immediate successor KEY, or NULL if there is no
539*fae548d3Szrj successor. KEY need not be present in the tree. */
540*fae548d3Szrj
541*fae548d3Szrj splay_tree_node
splay_tree_successor(splay_tree sp,splay_tree_key key)542*fae548d3Szrj splay_tree_successor (splay_tree sp, splay_tree_key key)
543*fae548d3Szrj {
544*fae548d3Szrj int comparison;
545*fae548d3Szrj splay_tree_node node;
546*fae548d3Szrj
547*fae548d3Szrj /* If the tree is empty, there is certainly no successor. */
548*fae548d3Szrj if (!sp->root)
549*fae548d3Szrj return NULL;
550*fae548d3Szrj
551*fae548d3Szrj /* Splay the tree around KEY. That will leave either the KEY
552*fae548d3Szrj itself, its predecessor, or its successor at the root. */
553*fae548d3Szrj splay_tree_splay (sp, key);
554*fae548d3Szrj comparison = (*sp->comp)(sp->root->key, key);
555*fae548d3Szrj
556*fae548d3Szrj /* If the successor is at the root, just return it. */
557*fae548d3Szrj if (comparison > 0)
558*fae548d3Szrj return sp->root;
559*fae548d3Szrj
560*fae548d3Szrj /* Otherwise, find the leftmost element of the right subtree. */
561*fae548d3Szrj node = sp->root->right;
562*fae548d3Szrj if (node)
563*fae548d3Szrj while (node->left)
564*fae548d3Szrj node = node->left;
565*fae548d3Szrj
566*fae548d3Szrj return node;
567*fae548d3Szrj }
568*fae548d3Szrj
569*fae548d3Szrj /* Call FN, passing it the DATA, for every node in SP, following an
570*fae548d3Szrj in-order traversal. If FN every returns a non-zero value, the
571*fae548d3Szrj iteration ceases immediately, and the value is returned.
572*fae548d3Szrj Otherwise, this function returns 0. */
573*fae548d3Szrj
574*fae548d3Szrj int
splay_tree_foreach(splay_tree sp,splay_tree_foreach_fn fn,void * data)575*fae548d3Szrj splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
576*fae548d3Szrj {
577*fae548d3Szrj return splay_tree_foreach_helper (sp->root, fn, data);
578*fae548d3Szrj }
579*fae548d3Szrj
580*fae548d3Szrj /* Splay-tree comparison function, treating the keys as ints. */
581*fae548d3Szrj
582*fae548d3Szrj int
splay_tree_compare_ints(splay_tree_key k1,splay_tree_key k2)583*fae548d3Szrj splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
584*fae548d3Szrj {
585*fae548d3Szrj if ((int) k1 < (int) k2)
586*fae548d3Szrj return -1;
587*fae548d3Szrj else if ((int) k1 > (int) k2)
588*fae548d3Szrj return 1;
589*fae548d3Szrj else
590*fae548d3Szrj return 0;
591*fae548d3Szrj }
592*fae548d3Szrj
593*fae548d3Szrj /* Splay-tree comparison function, treating the keys as pointers. */
594*fae548d3Szrj
595*fae548d3Szrj int
splay_tree_compare_pointers(splay_tree_key k1,splay_tree_key k2)596*fae548d3Szrj splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
597*fae548d3Szrj {
598*fae548d3Szrj if ((char*) k1 < (char*) k2)
599*fae548d3Szrj return -1;
600*fae548d3Szrj else if ((char*) k1 > (char*) k2)
601*fae548d3Szrj return 1;
602*fae548d3Szrj else
603*fae548d3Szrj return 0;
604*fae548d3Szrj }
605*fae548d3Szrj
606*fae548d3Szrj /* Splay-tree comparison function, treating the keys as strings. */
607*fae548d3Szrj
608*fae548d3Szrj int
splay_tree_compare_strings(splay_tree_key k1,splay_tree_key k2)609*fae548d3Szrj splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
610*fae548d3Szrj {
611*fae548d3Szrj return strcmp ((char *) k1, (char *) k2);
612*fae548d3Szrj }
613*fae548d3Szrj
614*fae548d3Szrj /* Splay-tree delete function, simply using free. */
615*fae548d3Szrj
616*fae548d3Szrj void
splay_tree_delete_pointers(splay_tree_value value)617*fae548d3Szrj splay_tree_delete_pointers (splay_tree_value value)
618*fae548d3Szrj {
619*fae548d3Szrj free ((void *) value);
620*fae548d3Szrj }
621