1 /*
2 * splay tree routines
3 * By Matthew Luckie
4 * U of Waikato 0657.317b 1999
5 *
6 * Copyright (C) 1999-2018 Matthew Luckie. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY Matthew Luckie ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL Matthew Luckie BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 */
30
31 #include <stdlib.h>
32 #include <assert.h>
33
34 #if defined(DMALLOC)
35 #include <dmalloc.h>
36 #endif
37
38 #include "mjl_splaytree.h"
39
40 /*
41 * the splay tree algorithm needs a simple stack to do the work.
42 * the implementations of these functions is found at the bottom of this
43 * file.
44 */
45 typedef struct splaytree_stack
46 {
47 splaytree_node_t **nodes;
48 int i;
49 int c;
50 } splaytree_stack_t;
51
52 /*
53 * splay tree node data structure
54 * conveniently hidden from users of the splay tree.
55 */
56 struct splaytree_node
57 {
58 void *item;
59 splaytree_node_t *left;
60 splaytree_node_t *right;
61 };
62
63 struct splaytree
64 {
65 splaytree_node_t *head;
66 int size;
67 splaytree_cmp_t cmp;
68 splaytree_stack_t *stack;
69 splaytree_onremove_t onremove;
70 };
71
72 static splaytree_stack_t *stack_create(void);
73 static splaytree_node_t *stack_pop(splaytree_stack_t *stack);
74 static void stack_destroy(splaytree_stack_t *stack);
75 static int stack_push(splaytree_stack_t *stack, splaytree_node_t *node);
76 static void stack_clean(splaytree_stack_t *stack);
77
78 #if !defined(NDEBUG) && defined(MJLSPLAYTREE_DEBUG)
splaytree_assert2(const splaytree_t * tree,const splaytree_node_t * node)79 static void splaytree_assert2(const splaytree_t *tree,
80 const splaytree_node_t *node)
81 {
82 int i;
83
84 if(node != NULL)
85 {
86 if(node->left != NULL)
87 {
88 i = tree->cmp(node->left->item, node->item);
89 assert(i < 0);
90 splaytree_assert2(tree, node->left);
91 }
92
93 if(node->right != NULL)
94 {
95 i = tree->cmp(node->right->item, node->item);
96 assert(i > 0);
97 splaytree_assert2(tree, node->right);
98 }
99 }
100 return;
101 }
102
splaytree_assert(const splaytree_t * tree)103 static void splaytree_assert(const splaytree_t *tree)
104 {
105 splaytree_assert2(tree, tree->head);
106 return;
107 }
108 #else
109 #define splaytree_assert(tree)((void)0)
110 #endif
111
112 /*
113 * splaytree_rotate
114 *
115 * perform the generic treenode-rotate algorithm.
116 */
splaytree_rotate(splaytree_node_t * above,splaytree_node_t * below)117 static void splaytree_rotate(splaytree_node_t *above, splaytree_node_t *below)
118 {
119 splaytree_node_t *temp;
120
121 /*
122 * above and below must be valid treenode pointers.
123 * above must point to the below node
124 */
125 assert(above != NULL);
126 assert(below != NULL);
127 assert(above->left == below || above->right == below);
128
129 /*
130 * check to see if the below node is to the left of the above or to
131 * the right
132 */
133 if(above->left == below)
134 {
135 temp = below->right;
136 below->right = above;
137 above->left = temp;
138 }
139 else
140 {
141 temp = below->left;
142 below->left = above;
143 above->right = temp;
144 }
145
146 return;
147 }
148
149 /*
150 * splaytree_splay2
151 *
152 * appropriately splay the treenodes passed in so that the child is moved
153 * higher than the other nodes passed in
154 */
splaytree_splay2(splaytree_node_t * child,splaytree_node_t * parent,splaytree_node_t * grandparent)155 static void splaytree_splay2(splaytree_node_t *child,
156 splaytree_node_t *parent,
157 splaytree_node_t *grandparent)
158 {
159 /* pre-condition: grandparent points to parent, parent points to child */
160 assert(child != NULL);
161 assert(parent == NULL || (parent->left == child || parent->right == child));
162 assert(grandparent == NULL ||
163 (grandparent->left == parent || grandparent->right == parent));
164
165 /* case 0: access node is root */
166 if(parent == NULL)
167 {
168 return;
169 }
170
171 /* case 1: parent is root */
172 else if(grandparent == NULL)
173 {
174 splaytree_rotate(parent, child);
175 }
176
177 /*
178 * case 2: zig zig - p is not the root and the child and the parent are both
179 * left (right) children
180 */
181 else if((parent->left == child && grandparent->left == parent) ||
182 (parent->right == child && grandparent->right == parent))
183 {
184 splaytree_rotate(grandparent, parent);
185 splaytree_rotate(parent, child);
186 }
187
188 /*
189 * case 3: zig zag - p is not the root and the child is a left(right) child
190 * and parent is a right(left) child
191 */
192 else if((parent->left == child && grandparent->right == parent) ||
193 (parent->right == child && grandparent->left == parent))
194 {
195 if(grandparent->left == parent)
196 {
197 splaytree_rotate(parent, child);
198 grandparent->left = child;
199 splaytree_rotate(grandparent, child);
200 }
201 else
202 {
203 splaytree_rotate(parent, child);
204 grandparent->right = child;
205 splaytree_rotate(grandparent, child);
206 }
207 }
208
209 return;
210 }
211
212 /*
213 * splaytree_splay
214 *
215 * coordinate the calls to splaytree_splay2.
216 * the stack contains, in order, the path to the child so that the nodes can
217 * be splayed.
218 */
splaytree_splay(splaytree_t * tree)219 static void splaytree_splay(splaytree_t *tree)
220 {
221 splaytree_node_t *child, *parent, *grandparent, *keep;
222
223 child = stack_pop(tree->stack);
224 parent = stack_pop(tree->stack);
225 grandparent = stack_pop(tree->stack);
226
227 /* there has to be at least one entry in the stack */
228 assert(child != NULL);
229
230 /* is there only one node in the tree */
231 if(parent == NULL)
232 {
233 tree->head = child;
234 return;
235 }
236
237 /* splay the node */
238 splaytree_splay2(child, parent, grandparent);
239
240 /* it was a simple swap at the root */
241 if(grandparent == NULL)
242 {
243 tree->head = child;
244 return;
245 }
246
247 /*
248 * remember the grandparent so that we can figure out where to relink the
249 * splayed child to
250 */
251 keep = grandparent;
252
253 /* just loop and we will break out when we need to */
254 for(;;)
255 {
256 /* get the parent nodes to the child */
257 parent = stack_pop(tree->stack);
258 grandparent = stack_pop(tree->stack);
259
260 /*
261 * if the child node is now at the root, break out as the splay is
262 * complete
263 */
264 if(parent == NULL)
265 {
266 break;
267 }
268
269 assert(parent->left == keep || parent->right == keep);
270
271 /*
272 * figure out where to relink the child to
273 * (as the grandparent in keep is now down the tree)
274 */
275 if(parent->left == keep)
276 {
277 parent->left = child;
278 }
279 else
280 {
281 parent->right = child;
282 }
283
284 /* splay now */
285 splaytree_splay2(child, parent, grandparent);
286
287 if(grandparent == NULL)
288 {
289 break;
290 }
291
292 keep = grandparent;
293 }
294
295 /* return the new root of the tree */
296 tree->head = child;
297 return;
298 }
299
300 /*
301 * splaytree_node_alloc
302 *
303 * creates/mallocs a node and initialises the contents of the node ready to
304 * insert to the tree
305 */
306 #ifndef DMALLOC
splaytree_node_alloc(const void * item)307 static splaytree_node_t *splaytree_node_alloc(const void *item)
308 #else
309 static splaytree_node_t *splaytree_node_alloc(const void *item,
310 const char *file, const int line)
311 #endif
312 {
313 splaytree_node_t *node;
314 size_t len = sizeof(splaytree_node_t);
315
316 #ifndef DMALLOC
317 node = (splaytree_node_t *)malloc(len);
318 #else
319 node = (splaytree_node_t *)dmalloc_malloc(file, line, len,
320 DMALLOC_FUNC_MALLOC, 0, 0);
321 #endif
322
323 if(node != NULL)
324 {
325 node->left = NULL;
326 node->right = NULL;
327 node->item = (void *)item;
328 }
329
330 return node;
331 }
332
333 /*
334 * splaytree_insert2
335 *
336 * insert the item into the tree.
337 * returns 0 if inserted, -1 on error.
338 */
339 #ifndef DMALLOC
splaytree_insert2(splaytree_t * tree,const void * item)340 static int splaytree_insert2(splaytree_t *tree, const void *item)
341 #else
342 static int splaytree_insert2(splaytree_t *tree, const void *item,
343 const char *file, const int line)
344 #endif
345 {
346 splaytree_node_t *tn, *node;
347 int i;
348
349 tn = tree->head;
350
351 for(;;)
352 {
353 /* put the node into the insert path and try the next level */
354 if(stack_push(tree->stack, tn) != 0)
355 return -1;
356
357 /* see whether the data belongs to the left, right, or is a duplicate */
358 i = tree->cmp(item, tn->item);
359 if(i < 0)
360 {
361 if(tn->left != NULL)
362 {
363 tn = tn->left;
364 continue;
365 }
366
367 /* insert the item into the tree here */
368 #ifndef DMALLOC
369 if((node = splaytree_node_alloc(item)) == NULL)
370 #else
371 if((node = splaytree_node_alloc(item, file, line)) == NULL)
372 #endif
373 return -1;
374
375 if(stack_push(tree->stack, node) != 0)
376 {
377 free(node);
378 return -1;
379 }
380
381 tn->left = node;
382 break;
383 }
384 else if(i > 0)
385 {
386 if(tn->right != NULL)
387 {
388 tn = tn->right;
389 continue;
390 }
391
392 #ifndef DMALLOC
393 if((node = splaytree_node_alloc(item)) == NULL)
394 #else
395 if((node = splaytree_node_alloc(item, file, line)) == NULL)
396 #endif
397 return -1;
398
399 if(stack_push(tree->stack, node) != 0)
400 {
401 free(node);
402 return -1;
403 }
404
405 tn->right = node;
406 break;
407 }
408 else
409 {
410 /* the data already exists in the tree: do not add it */
411 return -1;
412 }
413 }
414
415 return 0;
416 }
417
418 /*
419 * splaytree_insert
420 *
421 * insert a value into the splay tree, and return with the tree splayed on
422 * that value. return the node of the item.
423 *
424 */
425 #ifndef DMALLOC
splaytree_insert(splaytree_t * tree,const void * item)426 splaytree_node_t *splaytree_insert(splaytree_t *tree, const void *item)
427 #else
428 splaytree_node_t *splaytree_insert_dm(splaytree_t *tree, const void *item,
429 const char *file, const int line)
430 #endif
431 {
432 assert(tree != NULL);
433
434 splaytree_assert(tree);
435
436 /*
437 * if the tree actually has something in it, then we need to
438 * find the place to insert the node and splay on that.
439 */
440 if(tree->head != NULL)
441 {
442 stack_clean(tree->stack);
443
444 /*
445 * try and insert the item. can't insert it if an item matching this
446 * one is already there
447 */
448 #ifndef DMALLOC
449 if(splaytree_insert2(tree, item) != 0)
450 #else
451 if(splaytree_insert2(tree, item, file, line) != 0)
452 #endif
453 {
454 return NULL;
455 }
456
457 splaytree_splay(tree);
458 }
459 else
460 {
461 #ifndef DMALLOC
462 if((tree->head = splaytree_node_alloc(item)) == NULL)
463 #else
464 if((tree->head = splaytree_node_alloc(item, file, line)) == NULL)
465 #endif
466 {
467 return NULL;
468 }
469 }
470
471 tree->size++;
472
473 splaytree_assert(tree);
474
475 return tree->head;
476 }
477
478 /*
479 * splaytree_find2
480 *
481 * find the node with the data item matching. returns the node, if found.
482 */
splaytree_find2(splaytree_t * tree,const void * item)483 static splaytree_node_t *splaytree_find2(splaytree_t *tree, const void *item)
484 {
485 splaytree_node_t *tn;
486 int i;
487
488 stack_clean(tree->stack);
489
490 tn = tree->head;
491 while(tn != NULL)
492 {
493 /*
494 * try and push the node onto the stack.
495 * if we don't then we can't splay the node to the top of the tree, so
496 * we fail.
497 */
498 if(stack_push(tree->stack, tn) != 0)
499 return NULL;
500
501 /* determine the next node to visit */
502 i = tree->cmp(item, tn->item);
503 if(i < 0)
504 tn = tn->left;
505 else if(i > 0)
506 tn = tn->right;
507 else
508 break;
509 }
510
511 /* we found it ! */
512 return tn;
513 }
514
515 /*
516 * splaytree_find
517 *
518 * finds an item in the tree, and then splays the tree on that value
519 */
splaytree_find(splaytree_t * tree,const void * item)520 void *splaytree_find(splaytree_t *tree, const void *item)
521 {
522 if(tree == NULL || tree->head == NULL)
523 {
524 return NULL;
525 }
526
527 splaytree_assert(tree);
528 if(splaytree_find2(tree, item) == NULL)
529 {
530 return NULL;
531 }
532
533 splaytree_splay(tree);
534 splaytree_assert(tree);
535 return tree->head->item;
536 }
537
538 /*
539 * splaytree_find_ro
540 *
541 * a read-only version of splaytree_find, which finds an item in the
542 * tree, and returns it without splaying the tree.
543 */
splaytree_find_ro(const splaytree_t * tree,const void * item)544 void *splaytree_find_ro(const splaytree_t *tree, const void *item)
545 {
546 splaytree_node_t *tn;
547 int i;
548
549 if(tree == NULL)
550 return NULL;
551 splaytree_assert(tree);
552
553 tn = tree->head;
554 while(tn != NULL)
555 {
556 i = tree->cmp(item, tn->item);
557 if(i < 0)
558 tn = tn->left;
559 else if(i > 0)
560 tn = tn->right;
561 else
562 return tn->item;
563 }
564
565 return NULL;
566 }
567
568 /*
569 * splaytree_remove
570 *
571 * remove the first item in the splaytree
572 */
splaytree_remove(splaytree_t * tree)573 static int splaytree_remove(splaytree_t *tree)
574 {
575 splaytree_node_t *node;
576 splaytree_node_t *l, *r;
577 splaytree_node_t *temp;
578
579 node = tree->head;
580 l = node->left;
581 r = node->right;
582
583 /*
584 * search for the right most node in the left tree
585 * if there are no nodes on the left hand side of the tree, then we just
586 * need to shift the head of the tree to whatever is there on the right
587 * of it.
588 */
589 if(l != NULL)
590 {
591 stack_clean(tree->stack);
592 if(stack_push(tree->stack, l) != 0)
593 {
594 return -1;
595 }
596
597 temp = l;
598 while(temp->right != NULL)
599 {
600 if(stack_push(tree->stack, temp->right) != 0)
601 {
602 return -1;
603 }
604 temp = temp->right;
605 }
606
607 /* bring this node to the top of the tree with a splay operation */
608 splaytree_splay(tree);
609
610 /*
611 * as the right most node on the left branch has no nodes on the right
612 * branch, we connect the right hand branch to it
613 */
614 tree->head->right = r;
615 }
616 else
617 {
618 tree->head = r;
619 }
620
621 tree->size--;
622
623 if(tree->onremove != NULL)
624 tree->onremove(node->item);
625
626 free(node);
627 return 0;
628 }
629
630 /*
631 * splaytree_remove_item
632 *
633 * remove an item from the tree that matches the particular key
634 */
splaytree_remove_item(splaytree_t * tree,const void * item)635 int splaytree_remove_item(splaytree_t *tree, const void *item)
636 {
637 /*
638 * find the node that we are supposed to delete.
639 * if we can't find it, then the remove operation has failed.
640 */
641 if(splaytree_find2(tree, item) == NULL)
642 {
643 return -1;
644 }
645
646 /*
647 * now that we've found it, splay the tree to bring the node we are to
648 * delete to the top of the tree and then delete it.
649 */
650 splaytree_splay(tree);
651 return splaytree_remove(tree);
652 }
653
654 /*
655 * splaytree_remove_node
656 *
657 * remove a specific node from the splay tree
658 */
splaytree_remove_node(splaytree_t * tree,splaytree_node_t * node)659 int splaytree_remove_node(splaytree_t *tree, splaytree_node_t *node)
660 {
661 /*
662 * find the path to the node that we are supposed to delete. the node
663 * that we find has to match what was passed in
664 */
665 if(splaytree_find2(tree, node->item) != node)
666 {
667 return -1;
668 }
669
670 /*
671 * now that we've found it, splay the tree to bring the node we are to
672 * delete to the top of the tree and then delete it.
673 */
674 splaytree_splay(tree);
675 return splaytree_remove(tree);
676 }
677
678 /*
679 * splaytree_findclosest
680 *
681 * find a value in the tree as close to the specified one as possible
682 */
splaytree_findclosest(splaytree_t * tree,const void * item,splaytree_diff_t diff)683 void *splaytree_findclosest(splaytree_t *tree, const void *item,
684 splaytree_diff_t diff)
685 {
686 splaytree_node_t *ret;
687 splaytree_node_t *first, *second;
688 int first_diff, second_diff;
689
690 if(tree == NULL || tree->head == NULL) return NULL;
691
692 /* wow, the value we are looking for is actually in the tree! */
693 if((ret = splaytree_find2(tree, item)) != NULL)
694 {
695 splaytree_splay(tree);
696 assert(ret == tree->head);
697 return tree->head->item;
698 }
699
700 /*
701 * we need to get the last two items off the stack and figure out which
702 * one of the two is the closest to the one we are looking for
703 */
704 first = stack_pop(tree->stack);
705 second = stack_pop(tree->stack);
706
707 /* need at least one item in the stack if tree->head != NULL */
708 assert(first != NULL);
709
710 /* if there is only one item in the stack, splay? on it and return it */
711 if(second == NULL)
712 {
713 if(stack_push(tree->stack, first) != 0)
714 {
715 return NULL;
716 }
717 splaytree_splay(tree);
718 return tree->head->item;
719 }
720
721 /* work out which one is closer to the value we are looking for */
722 first_diff = abs(diff(first->item, item));
723 second_diff = abs(diff(second->item, item));
724
725 /*
726 * if the first item is closer than the second, put the first back on the
727 * stack and the splay on that
728 * else put them both back on and splay on that
729 */
730 if(second_diff > first_diff)
731 {
732 if(stack_push(tree->stack, second) != 0)
733 {
734 return NULL;
735 }
736 }
737 else
738 {
739 if(stack_push(tree->stack, second) != 0 ||
740 stack_push(tree->stack, first) != 0)
741 {
742 return NULL;
743 }
744 }
745
746 splaytree_splay(tree);
747 return tree->head->item;
748 }
749
750 /*
751 * splaytree_depth2
752 *
753 * recursive function to return the depth of the splay tree.
754 */
splaytree_depth2(splaytree_node_t * tn)755 static int splaytree_depth2(splaytree_node_t *tn)
756 {
757 int left = 0;
758 int right = 0;
759
760 if(tn == NULL) return 0;
761
762 if(tn->left != NULL)
763 {
764 left = splaytree_depth2(tn->left) + 1;
765 }
766 if(tn->right != NULL)
767 {
768 right = splaytree_depth2(tn->right) + 1;
769 }
770
771 return (left > right) ? left : right;
772 }
773
774 /*
775 * splaytree_depth
776 *
777 * returns the longest path (the depth) of the splay tree
778 */
splaytree_depth(splaytree_t * tree)779 int splaytree_depth(splaytree_t *tree)
780 {
781 if(tree == NULL) return -1;
782 if(tree->head == NULL) return 0;
783 return splaytree_depth2(tree->head) + 1;
784 }
785
786 /*
787 * splaytree_free2
788 *
789 * iterative function used to free a splaytree's nodes.
790 */
splaytree_free2(splaytree_t * tree,splaytree_free_t free_ptr)791 static void splaytree_free2(splaytree_t *tree, splaytree_free_t free_ptr)
792 {
793 splaytree_node_t *tn = tree->head, *tn2;
794
795 stack_clean(tree->stack);
796
797 while(tn != NULL)
798 {
799 if(tn->left != NULL)
800 {
801 tn2 = tn->left; tn->left = NULL;
802 stack_push(tree->stack, tn);
803 tn = tn2;
804 continue;
805 }
806
807 if(tn->right != NULL)
808 {
809 tn2 = tn->right; tn->right = NULL;
810 stack_push(tree->stack, tn);
811 tn = tn2;
812 continue;
813 }
814
815 if(tree->onremove != NULL) tree->onremove(tn->item);
816 if(free_ptr != NULL) free_ptr(tn->item);
817 free(tn);
818
819 tn = stack_pop(tree->stack);
820 }
821
822 return;
823 }
824
825 /*
826 * splaytree_free
827 *
828 * dellocate the splaytree
829 */
splaytree_free(splaytree_t * tree,splaytree_free_t free_ptr)830 void splaytree_free(splaytree_t *tree, splaytree_free_t free_ptr)
831 {
832 if(tree == NULL) return;
833 splaytree_free2(tree, free_ptr);
834 stack_destroy(tree->stack);
835 free(tree);
836 return;
837 }
838
splaytree_empty(splaytree_t * tree,splaytree_free_t free_ptr)839 void splaytree_empty(splaytree_t *tree, splaytree_free_t free_ptr)
840 {
841 if(tree == NULL) return;
842 splaytree_free2(tree, free_ptr);
843 tree->head = NULL;
844 tree->size = 0;
845 return;
846 }
847
splaytree_onremove(splaytree_t * tree,splaytree_onremove_t onremove)848 void splaytree_onremove(splaytree_t *tree, splaytree_onremove_t onremove)
849 {
850 tree->onremove = onremove;
851 return;
852 }
853
splaytree_gethead(splaytree_t * tree)854 void *splaytree_gethead(splaytree_t *tree)
855 {
856 if(tree == NULL || tree->head == NULL)
857 {
858 return NULL;
859 }
860
861 return tree->head->item;
862 }
863
splaytree_pophead(splaytree_t * tree)864 void *splaytree_pophead(splaytree_t *tree)
865 {
866 void *item;
867 if(tree->head == NULL)
868 return NULL;
869
870 item = tree->head->item;
871 if(splaytree_remove(tree) != 0)
872 return NULL;
873
874 return item;
875 }
876
877 /*
878 * splaytree_getrmlb
879 *
880 * return the right-most item on the left branch of the tree
881 */
splaytree_getrmlb(splaytree_t * tree)882 void *splaytree_getrmlb(splaytree_t *tree)
883 {
884 splaytree_node_t *tn;
885
886 if(tree == NULL || tree->head == NULL || tree->head->left == NULL)
887 {
888 return NULL;
889 }
890
891 tn = tree->head->left;
892 while(tn->right != NULL)
893 {
894 tn = tn->right;
895 }
896
897 return tn->item;
898 }
899
900 /*
901 * splaytree_getlmrb
902 *
903 * return the left-most item on the right branch of the tree
904 */
splaytree_getlmrb(splaytree_t * tree)905 void *splaytree_getlmrb(splaytree_t *tree)
906 {
907 splaytree_node_t *tn;
908
909 if(tree == NULL || tree->head == NULL || tree->head->right == NULL)
910 {
911 return NULL;
912 }
913
914 tn = tree->head->right;
915 while(tn->left != NULL)
916 {
917 tn = tn->left;
918 }
919
920 return tn->item;
921 }
922
923 /*
924 * splaytree_display2
925 *
926 * recursive function to print the contents of the splaytree, ascii-like.
927 */
splaytree_display2(splaytree_node_t * tn,splaytree_display_t disp,int pad)928 static void splaytree_display2(splaytree_node_t *tn, splaytree_display_t disp,
929 int pad)
930 {
931 if(tn != NULL)
932 {
933 splaytree_display2(tn->left, disp, pad+1);
934 disp(tn->item, pad);
935 splaytree_display2(tn->right, disp, pad+1);
936 }
937
938 return;
939 }
940
941 /*
942 * splaytree_display
943 *
944 * print the contents of the splaytree.
945 */
splaytree_display(splaytree_t * tree,splaytree_display_t disp)946 void splaytree_display(splaytree_t *tree, splaytree_display_t disp)
947 {
948 if(tree != NULL && disp != NULL)
949 {
950 splaytree_display2(tree->head, disp, 1);
951 }
952 return;
953 }
954
955 /*
956 * splaytree_inorder
957 *
958 * call a user-provided function on all items in the splay tree in order
959 */
splaytree_inorder(splaytree_t * tree,splaytree_inorder_t func,void * in)960 void splaytree_inorder(splaytree_t *tree, splaytree_inorder_t func, void *in)
961 {
962 splaytree_node_t *tn;
963
964 if(tree == NULL || func == NULL)
965 return;
966
967 stack_clean(tree->stack);
968 tn = tree->head;
969
970 for(;;)
971 {
972 if(tn != NULL)
973 {
974 stack_push(tree->stack, tn);
975 tn = tn->left;
976 }
977 else if((tn = stack_pop(tree->stack)) != NULL)
978 {
979 func(in, tn->item);
980 tn = tn->right;
981 }
982 else break;
983 }
984
985 return;
986 }
987
988 /*
989 * splaytree_alloc
990 *
991 * allocate a splaytree
992 */
993 #ifndef DMALLOC
splaytree_alloc(splaytree_cmp_t cmp)994 splaytree_t *splaytree_alloc(splaytree_cmp_t cmp)
995 #else
996 splaytree_t *splaytree_alloc_dm(splaytree_cmp_t cmp,
997 const char *file, const int line)
998 #endif
999 {
1000 splaytree_t *tree;
1001 size_t len = sizeof(splaytree_t);
1002
1003 #ifndef DMALLOC
1004 tree = (splaytree_t *)malloc(len);
1005 #else
1006 tree = (splaytree_t *)dmalloc_malloc(file,line,len,DMALLOC_FUNC_MALLOC,0,0);
1007 #endif
1008
1009 if(tree == NULL || (tree->stack = stack_create()) == NULL)
1010 goto err;
1011
1012 tree->head = NULL;
1013 tree->onremove = NULL;
1014 tree->size = 0;
1015 tree->cmp = cmp;
1016 return tree;
1017
1018 err:
1019 if(tree != NULL)
1020 free(tree);
1021 return NULL;
1022 }
1023
1024 /*
1025 * splaytree_count
1026 *
1027 * return the number of items in the splaytree.
1028 */
splaytree_count(splaytree_t * tree)1029 int splaytree_count(splaytree_t *tree)
1030 {
1031 if(tree == NULL) return -1;
1032 return tree->size;
1033 }
1034
1035 /*
1036 * stack_create
1037 *
1038 * create a stack that is optimised for dealing with splaytree processing
1039 */
stack_create(void)1040 static splaytree_stack_t *stack_create(void)
1041 {
1042 splaytree_stack_t *s;
1043
1044 if((s = (splaytree_stack_t *)malloc(sizeof(splaytree_stack_t))) == NULL)
1045 {
1046 return NULL;
1047 }
1048
1049 s->i = -1;
1050 s->c = 128;
1051 if((s->nodes = malloc(sizeof(splaytree_node_t *) * s->c)) == NULL)
1052 {
1053 free(s);
1054 return NULL;
1055 }
1056
1057 return s;
1058 }
1059
1060 /*
1061 * stack_clean
1062 *
1063 * reset the splaytree stack so it is emptied.
1064 */
stack_clean(splaytree_stack_t * s)1065 static void stack_clean(splaytree_stack_t *s)
1066 {
1067 s->i = -1;
1068 return;
1069 }
1070
1071 /*
1072 * stack_destroy
1073 *
1074 * free the memory allocated to the splaytree stack.
1075 */
stack_destroy(splaytree_stack_t * s)1076 static void stack_destroy(splaytree_stack_t *s)
1077 {
1078 free(s->nodes);
1079 free(s);
1080 return;
1081 }
1082
1083 /*
1084 * stack_push
1085 *
1086 * put the node on the splaytree stack, growing the array if necessary.
1087 */
stack_push(splaytree_stack_t * s,splaytree_node_t * node)1088 static int stack_push(splaytree_stack_t *s, splaytree_node_t *node)
1089 {
1090 splaytree_node_t **nodes;
1091 size_t size;
1092
1093 if(s->i+1 == s->c)
1094 {
1095 size = sizeof(splaytree_node_t *) * (s->c + 128);
1096 if((nodes = (splaytree_node_t **)realloc(s->nodes, size)) == NULL)
1097 {
1098 return -1;
1099 }
1100
1101 s->c += 128;
1102 s->nodes = nodes;
1103 }
1104
1105 s->nodes[++s->i] = node;
1106 return 0;
1107 }
1108
1109 /*
1110 * stack_pop
1111 *
1112 * remove the splaytree node at the top of the stack.
1113 */
stack_pop(splaytree_stack_t * s)1114 static splaytree_node_t *stack_pop(splaytree_stack_t *s)
1115 {
1116 if(s->i == -1) return NULL;
1117 return s->nodes[s->i--];
1118 }
1119