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