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