Commit | Line | Data |
---|---|---|
252b5132 | 1 | /* A splay-tree datatype. |
e495212d | 2 | Copyright (C) 1998-2017 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 | |
34 | ||
60c64519 DD |
35 | #include <stdio.h> |
36 | ||
252b5132 RH |
37 | #include "libiberty.h" |
38 | #include "splay-tree.h" | |
39 | ||
1e45deed | 40 | static void splay_tree_delete_helper (splay_tree, splay_tree_node); |
718c0ded DD |
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); | |
1e45deed | 45 | static void splay_tree_splay (splay_tree, splay_tree_key); |
98f0b5d4 | 46 | static int splay_tree_foreach_helper (splay_tree_node, |
1e45deed | 47 | splay_tree_foreach_fn, void*); |
252b5132 RH |
48 | |
49 | /* Deallocate NODE (a member of SP), and all its sub-trees. */ | |
50 | ||
51 | static void | |
1e45deed | 52 | splay_tree_delete_helper (splay_tree sp, splay_tree_node node) |
252b5132 | 53 | { |
9923bc33 DD |
54 | splay_tree_node pending = 0; |
55 | splay_tree_node active = 0; | |
56 | ||
252b5132 RH |
57 | if (!node) |
58 | return; | |
59 | ||
9923bc33 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); | |
252b5132 | 65 | |
9923bc33 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; | |
252b5132 | 69 | |
9923bc33 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 | |
252b5132 RH |
107 | } |
108 | ||
718c0ded | 109 | /* Rotate the edge joining the left child N with its parent P. PP is the |
145f4ab5 | 110 | grandparents' pointer to P. */ |
252b5132 | 111 | |
718c0ded DD |
112 | static inline void |
113 | rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) | |
252b5132 | 114 | { |
718c0ded DD |
115 | splay_tree_node tmp; |
116 | tmp = n->right; | |
117 | n->right = p; | |
118 | p->left = tmp; | |
119 | *pp = n; | |
120 | } | |
252b5132 | 121 | |
718c0ded | 122 | /* Rotate the edge joining the right child N with its parent P. PP is the |
145f4ab5 | 123 | grandparents' pointer to P. */ |
252b5132 | 124 | |
718c0ded DD |
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; | |
252b5132 RH |
133 | } |
134 | ||
718c0ded | 135 | /* Bottom up splay of key. */ |
252b5132 RH |
136 | |
137 | static void | |
1e45deed | 138 | splay_tree_splay (splay_tree sp, splay_tree_key key) |
252b5132 RH |
139 | { |
140 | if (sp->root == 0) | |
141 | return; | |
142 | ||
718c0ded DD |
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); | |
252b5132 RH |
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 | ||
205 | static int | |
98f0b5d4 | 206 | splay_tree_foreach_helper (splay_tree_node node, |
1e45deed | 207 | splay_tree_foreach_fn fn, void *data) |
252b5132 RH |
208 | { |
209 | int val; | |
98f0b5d4 DD |
210 | splay_tree_node *stack; |
211 | int stack_ptr, stack_size; | |
252b5132 | 212 | |
98f0b5d4 DD |
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 | } | |
252b5132 | 235 | |
98f0b5d4 DD |
236 | if (stack_ptr == 0) |
237 | break; | |
252b5132 | 238 | |
98f0b5d4 | 239 | node = stack[--stack_ptr]; |
252b5132 | 240 | |
98f0b5d4 DD |
241 | val = (*fn) (node, data); |
242 | if (val) | |
243 | break; | |
252b5132 | 244 | |
98f0b5d4 DD |
245 | node = node->right; |
246 | } | |
247 | ||
248 | XDELETEVEC (stack); | |
249 | return val; | |
250 | } | |
2bbcdae9 JB |
251 | |
252 | /* An allocator and deallocator based on xmalloc. */ | |
253 | static void * | |
1e45deed | 254 | splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) |
2bbcdae9 | 255 | { |
585cc78f | 256 | return (void *) xmalloc (size); |
2bbcdae9 JB |
257 | } |
258 | ||
259 | static void | |
1e45deed | 260 | splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) |
2bbcdae9 JB |
261 | { |
262 | free (object); | |
263 | } | |
264 | ||
265 | ||
252b5132 RH |
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 | |
2bbcdae9 JB |
268 | values. Use xmalloc to allocate the splay tree structure, and any |
269 | nodes added. */ | |
252b5132 RH |
270 | |
271 | splay_tree | |
1e45deed DD |
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) | |
252b5132 | 275 | { |
2bbcdae9 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 | |
1e45deed DD |
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) | |
2bbcdae9 | 293 | { |
219a461e DD |
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 | ||
d4d868a2 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}, @ | |
219a461e DD |
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 | ||
252b5132 RH |
336 | sp->root = 0; |
337 | sp->comp = compare_fn; | |
338 | sp->delete_key = delete_key_fn; | |
339 | sp->delete_value = delete_value_fn; | |
219a461e | 340 | sp->allocate = node_allocate_fn; |
2bbcdae9 JB |
341 | sp->deallocate = deallocate_fn; |
342 | sp->allocate_data = allocate_data; | |
252b5132 RH |
343 | |
344 | return sp; | |
345 | } | |
346 | ||
347 | /* Deallocate SP. */ | |
348 | ||
349 | void | |
1e45deed | 350 | splay_tree_delete (splay_tree sp) |
252b5132 RH |
351 | { |
352 | splay_tree_delete_helper (sp, sp->root); | |
2bbcdae9 | 353 | (*sp->deallocate) ((char*) sp, sp->allocate_data); |
252b5132 RH |
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 | |
0c0a36a4 | 358 | with the new value. Returns the new node. */ |
252b5132 | 359 | |
0c0a36a4 | 360 | splay_tree_node |
1e45deed | 361 | splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) |
252b5132 | 362 | { |
af32ff69 | 363 | int comparison = 0; |
252b5132 RH |
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; | |
219a461e | 382 | |
2bbcdae9 | 383 | node = ((splay_tree_node) |
219a461e DD |
384 | (*sp->allocate) (sizeof (struct splay_tree_node_s), |
385 | sp->allocate_data)); | |
252b5132 RH |
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 | ||
74bcd529 DD |
404 | sp->root = node; |
405 | } | |
0c0a36a4 ILT |
406 | |
407 | return sp->root; | |
252b5132 RH |
408 | } |
409 | ||
afe36a78 RH |
410 | /* Remove KEY from SP. It is not an error if it did not exist. */ |
411 | ||
412 | void | |
1e45deed | 413 | splay_tree_remove (splay_tree sp, splay_tree_key key) |
afe36a78 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); | |
2bbcdae9 | 427 | (*sp->deallocate) (sp->root, sp->allocate_data); |
afe36a78 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 | ||
252b5132 RH |
449 | /* Lookup KEY in SP, returning VALUE if present, and NULL |
450 | otherwise. */ | |
451 | ||
452 | splay_tree_node | |
1e45deed | 453 | splay_tree_lookup (splay_tree sp, splay_tree_key key) |
252b5132 RH |
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 | ||
e00bc6a7 DD |
463 | /* Return the node in SP with the greatest key. */ |
464 | ||
465 | splay_tree_node | |
1e45deed | 466 | splay_tree_max (splay_tree sp) |
e00bc6a7 DD |
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 | |
1e45deed | 482 | splay_tree_min (splay_tree sp) |
e00bc6a7 DD |
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 | ||
74bcd529 DD |
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 | |
1e45deed | 499 | splay_tree_predecessor (splay_tree sp, splay_tree_key key) |
74bcd529 DD |
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 | ||
0f3538e7 | 517 | /* Otherwise, find the rightmost element of the left subtree. */ |
74bcd529 DD |
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 | |
a54ba43f | 527 | successor. KEY need not be present in the tree. */ |
74bcd529 DD |
528 | |
529 | splay_tree_node | |
1e45deed | 530 | splay_tree_successor (splay_tree sp, splay_tree_key key) |
74bcd529 DD |
531 | { |
532 | int comparison; | |
533 | splay_tree_node node; | |
534 | ||
a54ba43f | 535 | /* If the tree is empty, there is certainly no successor. */ |
74bcd529 DD |
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 | ||
0f3538e7 | 548 | /* Otherwise, find the leftmost element of the right subtree. */ |
74bcd529 DD |
549 | node = sp->root->right; |
550 | if (node) | |
551 | while (node->left) | |
552 | node = node->left; | |
553 | ||
554 | return node; | |
555 | } | |
556 | ||
252b5132 RH |
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 | |
1e45deed | 563 | splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) |
252b5132 | 564 | { |
98f0b5d4 | 565 | return splay_tree_foreach_helper (sp->root, fn, data); |
252b5132 RH |
566 | } |
567 | ||
568 | /* Splay-tree comparison function, treating the keys as ints. */ | |
569 | ||
570 | int | |
1e45deed | 571 | splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) |
252b5132 RH |
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 | } | |
580 | ||
581 | /* Splay-tree comparison function, treating the keys as pointers. */ | |
582 | ||
583 | int | |
1e45deed | 584 | splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) |
252b5132 RH |
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 | } |