?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
beta-0.89.2
[luatex.git] / source / texk / web2c / mplibdir / avl.c
blobde3c63322ad91de8e5ff282508fd6ae3b0a3cf0c
1
2 /* pyavl -- File "avl.c" */
3
4 /* AVL trees with RANK field and parent pointers */
5
6 #include "avl.h"
7
8 #ifdef AVL_SHOW_ERROR_ON
9 #define AVL_SHOW_ERROR(fmt,arg) fprintf(stderr, "! avl.c: " fmt, arg)
10 #else
11 #define AVL_SHOW_ERROR(fmt,arg) (void) (fmt), (void) (arg)
12 #endif
13
14 const void *
15 avl_default_item_copy (const void *item)
16 {
17 return (const void *) item;
18 }
19
20 void *
21 avl_default_item_dispose (void *item)
22 {
23 (void)item; /* for -Wall */
24 return (void *) NULL;
25 }
26
27 #ifndef MPW_C
28 typedef uint32_t rbal_t; /* integral type to encode rank and skew bits */
29 #else
30 typedef UInt32 rbal_t;
31 #endif
32
33 /*
34 * avl_node structure
35 */
36
37 typedef struct avl_node
38 {
39 struct avl_node *sub[2];
40 struct avl_node *up;
41 rbal_t rbal;
42 void *item;
43 }
44 avl_node;
45
46 /*
47 * avl_tree structure
48 */
49
50 struct avl_tree_
51 {
52 avl_node *root;
53 avl_size_t count; /* how many nodes in tree rooted at [root] */
54 avl_compare_func compare; /* compare items */
55 avl_item_copy_func copy;
56 avl_item_dispose_func dispose;
57 avl_alloc_func alloc; /* to allocate memory (same signature as malloc) */
58 avl_dealloc_func dealloc; /* to deallocate memory (same signature as free) */
59 void *param;
60 };
61
62 #define Item_Compare(cmp, tree, item1, item2)\
63 (*cmp)(tree->param, item1, item2)
64
65 /* patches (November 2004) */
66
67 #if AVL_CMPERR != 0
68 #define CMPERR_CHECK__FIND(param) if (avl_errcmp_occurred(param)) return NULL
69 #define CMPERR_CHECK__INDEX(param) if (avl_errcmp_occurred(param)) return 0
70 #define CMPERR_CHECK__SPAN(param) if (avl_errcmp_occurred(param)) return -2
71 #define CMPERR_CHECK__INS(param) if (avl_errcmp_occurred(param)) return -2
72 #define CMPERR_CHECK__DEL(param) (avl_errcmp_occurred(param) ? -2 : 0)
73 #define CMPERR_CHECK__SPLIT(param) if (avl_errcmp_occurred(param)) return -2
74 #define CMPERR_CHECK__VERIFY(param) && (!avl_errcmp_occurred(param))
75 #else
76 #define CMPERR_CHECK__FIND(param) (void) param
77 #define CMPERR_CHECK__INDEX(param) (void) param
78 #define CMPERR_CHECK__SPAN(param) (void) param
79 #define CMPERR_CHECK__INS(param) (void) param
80 #define CMPERR_CHECK__DEL(param) 0
81 #define CMPERR_CHECK__SPLIT(param) (void) param
82 #define CMPERR_CHECK__VERIFY(param) /* nothing */
83 #endif
84
85 #define sub_left(a) (a)->sub[0]
86 #define sub_right(a) (a)->sub[1]
87 #define get_item(a) (a)->item
88
89 /* RANK(a) = size of left subtree + 1 */
90
91 #define rbal(a)\
92 (a)->rbal
93 #define rzero(a)\
94 ( rbal(a) & ~3 )
95 #define get_bal(a)\
96 ( rbal(a) & 3 )
97 #define is_lskew(a)\
98 ( rbal(a) & 1 )
99 #define is_rskew(a)\
100 ( rbal(a)>>1 & 1)
101 #define set_lskew(a)\
102 ( rbal(a) |= 1 )
103 #define set_rskew(a)\
104 ( rbal(a) |= 2 )
105 #define set_skew(a,d)\
106 ( rbal(a) |= (1 << d) )
107 #define unset_lskew(a)\
108 ( rbal(a) &= ~1 )
109 #define unset_rskew(a)\
110 ( rbal(a) &= ~2 )
111 #define get_rank(a)\
112 ( rbal(a) >> 2 )
113 #define set_rank(a,r)\
114 ( rbal(a) = (r<<2 | get_bal(a)) )
115 #define incr_rank(a,r)\
116 ( rbal(a) += r<<2 )
117 #define decr_rank(a,r)\
118 ( rbal(a) -= r<<2 )
119
120 #define AVL_MIN_DEPTH 0
121
122 /*** Node management ***/
123
124 #define DETACH_FUNC 1 /* nonzero to use function not macro */
125
126 /* helper structure */
127 typedef enum
128 {
129 OP_BACKUP, OP_DETACH, OP_FREE
130 }
131 whichop_t;
132 struct ptr_handler
133 {
134 whichop_t whichop;
135 void *ptr;
136 };
137
138 #define ini_ptr_handler(h,op) struct ptr_handler h = { OP_##op, NULL }
139 #define clear_node(a) \
140 sub_left(a) = NULL; \
141 sub_right(a) = NULL; \
142 (a)->up = NULL; \
143 rbal(a) = 4u
144
145 /* Called by 'avl_ins', 'avl_dup', 'node_slice' */
146 static avl_node *
147 new_node (void *item, avl_node * up, avl_tree t)
148 {
149 avl_node *a = (*t->alloc) (sizeof (avl_node));
150
151 if (a != NULL)
152 {
153 sub_left (a) = NULL;
154 sub_right (a) = NULL;
155 a->up = up;
156 a->rbal = 4u;
157 a->item = (*t->copy) (item);
158 }
159 return a;
160 }
161
162 static void
163 free_node (avl_node * a, avl_tree t)
164 {
165 a->item = (*t->dispose) (a->item);
166 (*t->dealloc) (a);
167 }
168
169 #define backup_item(backup,item,t) if (backup == NULL) ; else *backup = (*t->copy)(item)
170
171 #if ! DETACH_FUNC
172
173 /* macro to detach node [a] from tree [t] */
174 #define detach_node(a,t,h) { struct ptr_handler *ch = h; \
175 clear_node(a); \
176 do { \
177 if (ch == NULL) ; \
178 else if (ch->whichop == OP_DETACH){ \
179 ch->ptr = a; \
180 break; \
181 } else if (ch->whichop == OP_BACKUP){ \
182 ch->ptr = (*t->copy)(a->item); \
183 } \
184 free_node(a, t); \
185 } while (0);} \
186 t->count--
187 #else
188
189 /* function to detach node [a] from tree [t] */
190 static void
191 detach_node (avl_node * a, avl_tree t, struct ptr_handler *h)
192 {
193 clear_node (a);
194 do
195 {
196 if (h == NULL);
197 else if (h->whichop == OP_DETACH)
198 {
199 h->ptr = a;
200 break;
201 }
202 else if (h->whichop == OP_BACKUP)
203 {
204 h->ptr = (*t->copy) (a->item);
205 }
206 free_node (a, t);
207 }
208 while (0);
209 t->count--;
210 }
211 #endif /* DETACH_FUNC */
212
213 /*** Tree methods ***/
214
215 avl_tree
216 avl_create (avl_compare_func compare, avl_item_copy_func copy,
217 avl_item_dispose_func dispose, avl_alloc_func alloc,
218 avl_dealloc_func dealloc, void *param)
219 {
220 avl_tree t = (*alloc) (sizeof (struct avl_tree_));
221
222 if (t == NULL)
223 AVL_SHOW_ERROR ("%s\n", "couldn't create new handle in avl_create()");
224 else
225 {
226 t->root = NULL;
227 t->count = 0;
228 t->param = param;
229 t->compare = compare;
230 t->copy = copy;
231 t->dispose = dispose;
232 t->alloc = alloc;
233 t->dealloc = dealloc;
234 }
235 return t;
236 }
237
238 /* Empty the tree, using rotations */
239
240 static void
241 node_empty (avl_tree t)
242 {
243 avl_node *a, *p;
244
245 for (a = t->root; a != NULL;)
246 {
247 p = a;
248 if (sub_right (a) == NULL)
249 a = sub_left (a);
250 else
251 {
252 while (sub_left (a) != NULL)
253 {
254 /* rotR(a) */
255 a = sub_left (a);
256 sub_left (p) = sub_right (a);
257 sub_right (a) = p;
258 p = a;
259 }
260 a = sub_right (p);
261 }
262 free_node (p, t);
263 t->count--;
264 }
265 t->root = NULL;
266 }
267
268 /* [t] is an existing tree handle */
269
270 /* this function invokes node_empty() */
271
272 void
273 avl_reset (avl_tree t,
274 avl_compare_func compare,
275 avl_item_copy_func copy,
276 avl_item_dispose_func dispose,
277 avl_alloc_func alloc, avl_dealloc_func dealloc)
278 {
279 if (t == NULL)
280 return;
281 node_empty (t);
282 t->compare = compare;
283 t->copy = copy;
284 t->dispose = dispose;
285 t->alloc = alloc;
286 t->dealloc = dealloc;
287 }
288
289 void
290 avl_empty (avl_tree t)
291 {
292 if (t != NULL)
293 node_empty (t);
294 }
295
296 /* Destroy nodes, free handle */
297
298 void
299 avl_destroy (avl_tree t)
300 {
301 #ifndef AVL_NULLCHECKS
302 if (t == NULL)
303 return;
304 #endif
305 node_empty (t);
306 (*t->dealloc) (t);
307 }
308
309 avl_tree
310 avl_dup (avl_tree t, void *param)
311 {
312 #ifndef AVL_NULLCHECKS
313 if (t == NULL)
314 return NULL;
315 #endif
316 {
317 avl_tree tt = avl_create (
318 /*(avl_compare_func) */ t->compare,
319 /*(avl_item_copy_func) */ t->copy,
320 /*(avl_item_dispose_func) */ t->dispose,
321 /*(avl_alloc_func) */ t->alloc,
322 /*(avl_dealloc_func) */ t->dealloc,
323 param);
324
325 if (tt == NULL)
326 {
327 AVL_SHOW_ERROR ("%s\n", "couldn't create new handle in avl_dup()");
328 return NULL;
329 }
330
331 tt->count = t->count;
332
333 if (t->root == NULL)
334 return tt;
335
336 {
337 avl_node *a, *c, *s;
338
339 a = t->root;
340 tt->root = c = new_node (get_item (a), NULL, t);
341 if (c == NULL)
342 goto abort;
343
344 sub_right (c) = NULL; /*!!! */
345 rbal (c) = rbal (a);
346
347 while (1)
348 {
349 while (sub_left (a) != NULL)
350 {
351 a = sub_left (a);
352 sub_left (c) = s = new_node (get_item (a), NULL, t);
353 if (s == NULL)
354 goto recover;
355 s->up = c;
356 sub_right (s) = c;
357 c = s;
358 rbal (c) = rbal (a);
359 }
360
361 sub_left (c) = NULL;
362
363 while (sub_right (a) == NULL)
364 {
365 s = sub_right (c);
366 sub_right (c) = NULL;
367 c = s;
368 /* Find successor of [a] in original tree */
369 do
370 {
371 s = a;
372 a = s->up;
373 if (a == NULL)
374 return tt;
375 }
376 while (s != sub_left (a));
377 }
378
379 a = sub_right (a);
380 s = new_node (get_item (a), NULL, t);
381 if (s == NULL)
382 goto recover;
383 sub_right (s) = sub_right (c);
384 sub_right (c) = s;
385 s->up = c;
386 c = s;
387 rbal (c) = rbal (a);
388 }
389 /* recovery code */
390 recover:
391 while (1)
392 {
393 s = sub_right (c);
394 sub_right (c) = NULL;
395 if (s == NULL)
396 break;
397 c = s;
398 }
399 node_empty (tt);
400
401 abort:
402 (*t->dealloc) (tt);
403 AVL_SHOW_ERROR ("%s\n", "couldn't allocate node in avl_dup()");
404 return NULL;
405 }
406 }
407 }
408
409 avl_bool_t
410 avl_isempty (avl_tree t)
411 {
412 #ifndef AVL_NULLCHECKS
413 return t == NULL || t->root == NULL;
414 #else
415 return t->root == NULL;
416 #endif
417 }
418
419 avl_size_t
420 avl_size (avl_tree t)
421 {
422 #ifndef AVL_NULLCHECKS
423 return t == NULL ? 0 : t->count;
424 #else
425 return t->count;
426 #endif
427 }
428
429 static int
430 depth (avl_node * a)
431 {
432 int h = AVL_MIN_DEPTH;
433
434 for (; a != NULL; ++h)
435 a = a->sub[is_rskew (a)];
436 return h;
437 }
438
439 static avl_node *
440 node_first (avl_node * a)
441 {
442 while (sub_left (a) != NULL)
443 a = sub_left (a);
444 return a;
445 }
446
447 static avl_node *
448 node_last (avl_node * a)
449 {
450 while (sub_right (a) != NULL)
451 a = sub_right (a);
452 return a;
453 }
454
455 /* [a] : non-null */
456
457 static avl_node *
458 node_next (avl_node * a)
459 {
460 if (sub_right (a) != NULL)
461 return node_first (sub_right (a));
462 {
463 avl_node *p;
464
465 do
466 {
467 p = a;
468 a = p->up;
469 }
470 while (a != NULL && sub_right (a) == p);
471 return a;
472 }
473 }
474
475 /* [a] : non-null */
476
477 static avl_node *
478 node_prev (avl_node * a)
479 {
480 if (sub_left (a) != NULL)
481 return node_last (sub_left (a));
482 {
483 avl_node *p;
484
485 do
486 {
487 p = a;
488 a = p->up;
489 }
490 while (a != NULL && sub_left (a) == p);
491 return a;
492 }
493 }
494
495 static avl_node *
496 node_find (const void *item, avl_tree t)
497 {
498 avl_node *a = t->root;
499 avl_compare_func cmp = t->compare;
500 int c;
501
502 while (a != NULL)
503 {
504 c = Item_Compare (cmp, t, item, get_item (a));
505 CMPERR_CHECK__FIND (t->param);
506 if (c < 0)
507 a = a->sub[0];
508 else if (c)
509 a = a->sub[1];
510 else
511 break;
512 }
513 return a;
514 }
515
516 #if 0==1
517 static avl_node **
518 avl_search (const void *item, avl_tree t, int *dir)
519 {
520 if (t->root == NULL)
521 return &t->root;
522 {
523 avl_node **r = &t->root;
524 avl_node *a = *r;
525 avl_compare_func cmp = t->compare;
526 int c;
527
528 while (1)
529 {
530 c = Item_Compare (cmp, t, item, get_item (a));
531 if (!c)
532 break;
533 r = &a->sub[c = c > 0];
534 if (*r == NULL)
535 {
536 *dir = c;
537 break;
538 }
539 a = *r;
540 }
541
542 return r;
543 }
544 }
545 #endif
546
547 static avl_size_t
548 get_index (avl_node * a)
549 {
550 avl_size_t n = get_rank (a);
551 avl_node *p;
552
553 while ((p = a->up) != NULL)
554 {
555 if (a != sub_left (p))
556 n += get_rank (p);
557 a = p;
558 }
559 return n;
560 }
561
562 /* Find item by index */
563
564 static avl_node *
565 node_find_index (avl_size_t idx, avl_tree t)
566 {
567 avl_node *a = t->root;
568 int c;
569
570 if (idx == 0 || idx > t->count)
571 return NULL;
572 if (idx == 1)
573 return node_first (a);
574 if (idx == t->count)
575 return node_last (a);
576
577 while ((c = (int)(idx - get_rank (a))) != 0)
578 {
579 if (c < 0)
580 a = sub_left (a);
581 else
582 {
583 idx = (avl_size_t)c;
584 a = sub_right (a);
585 }
586 }
587
588 return a;
589 }
590
591 /* Rebalance starting from node [a] where a->sub[d_]
592 * is deeper post-insertion
593 */
594
595 static avl_code_t
596 rebalance_ins (avl_node * a, int dir, avl_tree t)
597 {
598 if (a != NULL)
599 {
600 avl_node *p;
601
602 while (1)
603 {
604 incr_rank (a, (rbal_t)(!dir));
605 if (get_bal (a))
606 break;
607 set_skew (a, dir);
608 p = a->up;
609 if (p == NULL)
610 return 2;
611 dir = a != sub_left (p);
612 a = p;
613 }
614
615 /* Now bal(a) == -1 or +1 */
616 /* Rotate if need be */
617
618 if (0 == dir)
619 {
620 if (is_rskew (a))
621 unset_rskew (a);
622
623 else
624 {
625 avl_node *u = a->up;
626 avl_node **r =
627 u != NULL ? &u->sub[a != sub_left (u)] : &t->root;
628
629 p = a;
630
631 if (is_lskew (sub_left (p)))
632 {
633 /* rotR(p) */
634 a = sub_left (p);
635 sub_left (p) = sub_right (a);
636 if (sub_right (a) != NULL)
637 sub_right (a)->up = p;
638 sub_right (a) = p;
639 unset_lskew (p);
640 rbal (p) -= rzero (a);
641 }
642 else
643 {
644 /* rotLR(p) */
645 a = sub_right (sub_left (p));
646 sub_right (sub_left (p)) = sub_left (a);
647 if (sub_left (a) != NULL)
648 sub_left (a)->up = sub_left (p);
649 sub_left (p)->up = a;
650 sub_left (a) = sub_left (p);
651 sub_left (p) = sub_right (a);
652 if (sub_right (a) != NULL)
653 sub_right (a)->up = p;
654 sub_right (a) = p;
655 switch (get_bal (a))
656 {
657 case 0: /* not skewed */
658 unset_lskew (p);
659 unset_rskew (sub_left (a));
660 break;
661 case 1: /* left skew */
662 unset_lskew (p);
663 set_rskew (p);
664 unset_rskew (sub_left (a));
665 break;
666 case 2: /* right skew */
667 unset_lskew (p);
668 unset_rskew (sub_left (a));
669 set_lskew (sub_left (a));
670 } /* switch */
671 rbal (a) += rzero (sub_left (a));
672 rbal (p) -= rzero (a);
673 } /* which rot */
674 rbal (a) &= ~3;
675 a->up = u;
676 p->up = a;
677 *r = a;
678 } /* rot or no rot ? */
679 }
680 else
681 {
682 /* direction == 1 */
683
684 if (is_lskew (a))
685 unset_lskew (a);
686
687 else
688 {
689 avl_node *u = a->up;
690 avl_node **r =
691 u != NULL ? &u->sub[a != sub_left (u)] : &t->root;
692
693 p = a;
694 if (is_rskew (sub_right (p)))
695 {
696 /* rotL(p) */
697 a = sub_right (p);
698 sub_right (p) = sub_left (a);
699 if (sub_left (a) != NULL)
700 sub_left (a)->up = p;
701 sub_left (a) = p;
702 unset_rskew (p);
703 rbal (a) += rzero (p);
704 }
705 else
706 {
707 /* rotRL(p) */
708 a = sub_left (sub_right (p));
709 sub_left (sub_right (p)) = sub_right (a);
710 if (sub_right (a) != NULL)
711 sub_right (a)->up = sub_right (p);
712 sub_right (p)->up = a;
713 sub_right (a) = sub_right (p);
714 sub_right (p) = sub_left (a);
715 if (sub_left (a) != NULL)
716 sub_left (a)->up = p;
717 sub_left (a) = p;
718 switch (get_bal (a))
719 {
720 case 0: /* not skewed */
721 unset_rskew (p);
722 unset_lskew (sub_right (a));
723 break;
724 case 1: /* left skew */
725 unset_rskew (p);
726 unset_lskew (sub_right (a));
727 set_rskew (sub_right (a));
728 break;
729 case 2: /* right skew */
730 unset_rskew (p);
731 set_lskew (p);
732 unset_lskew (sub_right (a));
733 } /* switch */
734 rbal (sub_right (a)) -= rzero (a);
735 rbal (a) += rzero (p);
736
737 } /* which rot */
738
739 rbal (a) &= ~3;
740 a->up = u;
741 p->up = a;
742 *r = a;
743 } /* rot or not rot ? */
744 } /* if 0==dir */
745
746 /* The tree rooted at 'a' is now valid */
747 /* Finish adjusting ranks */
748
749 while ((p = a->up) != NULL)
750 {
751 incr_rank (p, (rbal_t)(a == sub_left (p)));
752 a = p;
753 }
754
755 return 1;
756
757 } /* if a != 0 */
758 return 2;
759 }
760
761 /* detach [p] : non-null */
762
763 /* only the linkage is tweaked */
764
765 static avl_code_t
766 rebalance_del (avl_node * p, avl_tree t, void **backup)
767 {
768 avl_node **r, *a, *c;
769 rbal_t bal;
770 int dir = 0;
771
772 a = p->up;
773 if (a == NULL)
774 r = &t->root;
775 else
776 r = &a->sub[dir = p != sub_left (a)];
777
778 c = sub_right (p);
779 if (c == NULL && sub_left (p) == NULL)
780 *r = NULL;
781 else if (c == NULL || sub_left (p) == NULL)
782 {
783 *r = c != NULL ? c : sub_left (p);
784 (*r)->up = a;
785 }
786 else
787 {
788 if (sub_left (c) == NULL)
789 {
790 a = c;
791 dir = 1;
792 }
793 else
794 {
795 do
796 c = sub_left (c);
797 while (sub_left (c) != NULL);
798 a = c->up;
799 dir = 0;
800 sub_left (a) = sub_right (c);
801 if (sub_right (c) != NULL)
802 sub_right (c)->up = a;
803 sub_right (c) = sub_right (p);
804 sub_right (c)->up = c;
805 }
806 sub_left (c) = sub_left (p);
807 sub_left (c)->up = c;
808 c->up = p->up;
809 rbal (c) = rbal (p);
810 *r = c;
811 }
812
813 backup_item (backup, p->item, t);
814 detach_node (p, t, NULL);
815
816 /* Start backtracking : subtree of [a] in direction [dir] is less deep */
817
818 for (;; a = (*r)->up)
819 {
820 if (a == NULL)
821 return 2;
822
823 decr_rank (a, (rbal_t)(!dir));
824 bal = get_bal (a);
825
826 if (0 == dir)
827 {
828 if (bal == 0)
829 {
830 set_rskew (a);
831 break;
832 }
833 if (a->up == NULL)
834 r = &t->root;
835 else
836 {
837 dir = a != sub_left (a->up);
838 r = &a->up->sub[dir];
839 }
840 if (bal & 1)
841 unset_lskew (a);
842 if (get_bal (a))
843 {
844 p = a;
845 bal = get_bal (sub_right (p));
846 if (!(bal & 1))
847 {
848 /* bal = 0 or +1 */
849 /* rotL(p) */
850 a = sub_right (p);
851 sub_right (p) = sub_left (a);
852 if (sub_left (a) != NULL)
853 sub_left (a)->up = p;
854 sub_left (a) = p;
855 if (bal)
856 {
857 unset_rskew (p);
858 unset_rskew (a);
859 }
860 else
861 set_lskew (a);
862 rbal (a) += rzero (p);
863 }
864 else
865 {
866 /* rotRL(p) */
867 a = sub_left (sub_right (p));
868 sub_left (sub_right (p)) = sub_right (a);
869 if (sub_right (a) != NULL)
870 sub_right (a)->up = sub_right (p);
871 sub_right (p)->up = a;
872 sub_right (a) = sub_right (p);
873 sub_right (p) = sub_left (a);
874 if (sub_left (a) != NULL)
875 sub_left (a)->up = p;
876 sub_left (a) = p;
877 switch (get_bal (a))
878 {
879 case 0: /* not skewed */
880 unset_rskew (p);
881 unset_lskew (sub_right (a));
882 break;
883 case 1: /* left skew */
884 unset_rskew (p);
885 unset_lskew (sub_right (a));
886 set_rskew (sub_right (a));
887 break;
888 case 2: /* right skew */
889 unset_rskew (p);
890 set_lskew (p);
891 unset_lskew (sub_right (a));
892 } /* switch */
893 rbal (a) &= ~3;
894 rbal (sub_right (a)) -= rzero (a);
895 rbal (a) += rzero (p);
896
897 } /* which rot */
898
899 a->up = p->up;
900 p->up = a;
901 /* Done with rotation */
902 *r = a;
903 if (bal == 0)
904 break;
905 } /* if getbal(a) */
906 }
907 else
908 {
909 /* dir == 1 */
910
911 if (bal == 0)
912 {
913 set_lskew (a);
914 break;
915 }
916 if (a->up == NULL)
917 r = &t->root;
918 else
919 {
920 dir = a != sub_left (a->up);
921 r = &a->up->sub[dir];
922 }
923 if (bal & 2)
924 unset_rskew (a);
925 if (get_bal (a))
926 {
927 p = a;
928 bal = get_bal (sub_left (p));
929 if (!(bal & 2))
930 {
931 /* bal = 0 or -1 */
932 /* rotR(p) */
933 a = sub_left (p);
934 sub_left (p) = sub_right (a);
935 if (sub_right (a) != NULL)
936 sub_right (a)->up = p;
937 sub_right (a) = p;
938 if (bal)
939 {
940 unset_lskew (p);
941 unset_lskew (a);
942 }
943 else
944 set_rskew (a);
945 rbal (p) -= rzero (a);
946 }
947 else
948 {
949 /* rotLR(p) */
950 a = sub_right (sub_left (p));
951 sub_right (sub_left (p)) = sub_left (a);
952 if (sub_left (a) != NULL)
953 sub_left (a)->up = sub_left (p);
954 sub_left (p)->up = a;
955 sub_left (a) = sub_left (p);
956 sub_left (p) = sub_right (a);
957 if (sub_right (a) != NULL)
958 sub_right (a)->up = p;
959 sub_right (a) = p;
960 switch (get_bal (a))
961 {
962 case 0: /* not skewed */
963 unset_lskew (p);
964 unset_rskew (sub_left (a));
965 break;
966 case 1: /* left skew */
967 unset_lskew (p);
968 set_rskew (p);
969 unset_rskew (sub_left (a));
970 break;
971 case 2: /* right skew */
972 unset_lskew (p);
973 unset_rskew (sub_left (a));
974 set_lskew (sub_left (a));
975 } /* switch */
976 rbal (a) &= ~3;
977 rbal (a) += rzero (sub_left (a));
978 rbal (p) -= rzero (a);
979 } /* which rot */
980
981 a->up = p->up;
982 p->up = a;
983 /* Done with rotation */
984 *r = a;
985 if (bal == 0)
986 break;
987 } /* if getbal(a) */
988 } /* if dir==0 else 1 */
989 } /* for */
990
991 /* Finish adjusting ranks */
992 while ((p = a->up) != NULL)
993 {
994 decr_rank (p, (rbal_t)(a == sub_left (p)));
995 a = p;
996 }
997
998 return 1;
999 }
1000
1001 void *
1002 avl_first (avl_tree t)
1003 {
1004 #ifndef AVL_NULLCHECKS
1005 if (t == NULL || t->root == NULL)
1006 #else
1007 if (t->root == NULL)
1008 #endif
1009 return NULL;
1010 return get_item (node_first (t->root));
1011 }
1012
1013 void *
1014 avl_last (avl_tree t)
1015 {
1016 #ifndef AVL_NULLCHECKS
1017 if (t == NULL || t->root == NULL)
1018 #else
1019 if (t->root == NULL)
1020 #endif
1021 return NULL;
1022 return get_item (node_last (t->root));
1023 }
1024
1025 void *
1026 avl_find (const void *item, avl_tree t)
1027 {
1028 avl_node *a;
1029
1030 #ifndef AVL_NULLCHECKS
1031 if (t == NULL)
1032 return NULL;
1033 #endif
1034 a = node_find (item, t);
1035 return a != NULL ? get_item (a) : NULL;
1036 }
1037
1038 /*
1039 * Return smallest index i in [1:len] s.t. tree[i] matches [item],
1040 * or zero if not found
1041 */
1042
1043 avl_size_t
1044 avl_index (const void *item, avl_tree t)
1045 {
1046 #ifndef AVL_NULLCHECKS
1047 if (item == NULL || t == NULL || t->root == NULL)
1048 #else
1049 if (t->root == NULL)
1050 #endif
1051 return 0;
1052
1053 {
1054 avl_compare_func cmp = t->compare;
1055 avl_node *a, *p;
1056 avl_size_t idx = 0, n = 0;
1057 int c;
1058
1059 for (a = t->root;;)
1060 {
1061 c = Item_Compare (cmp, t, item, get_item (a));
1062 CMPERR_CHECK__INDEX (t->param);
1063 if (!c)
1064 idx = n + get_rank (a);
1065 else if (c > 0)
1066 n += get_rank (a);
1067 p = a->sub[c > 0];
1068 if (p == NULL)
1069 return idx;
1070 a = p;
1071 }
1072 }
1073 }
1074
1075 /* (lo,hi) where
1076 * lo smallest index s.t. t[lo] >= lo_item, or t->count+1 and
1077 * hi greatest index s.t. t[hi] <= hi_item, or 0
1078 */
1079 avl_code_t
1080 avl_span (const void *lo_item,
1081 const void *hi_item,
1082 avl_tree t, avl_size_t * lo_idx, avl_size_t * hi_idx)
1083 {
1084 *lo_idx = t->count + 1;
1085 *hi_idx = 0;
1086
1087 #ifndef AVL_NULLCHECKS
1088 if (t == NULL || t->root == NULL)
1089 #else
1090 if (t->root == NULL)
1091 #endif
1092 return -1;
1093
1094 {
1095 avl_compare_func cmp = t->compare;
1096 avl_node *a;
1097 avl_size_t n = 0;
1098 int c;
1099
1100 c = Item_Compare (cmp, t, lo_item, hi_item) > 0;
1101 CMPERR_CHECK__SPAN (t->param);
1102 if (c > 0)
1103 {
1104 const void *temp = lo_item;
1105
1106 lo_item = hi_item;
1107 hi_item = temp;
1108 }
1109
1110 a = t->root;
1111 do
1112 {
1113 c = Item_Compare (cmp, t, lo_item, get_item (a));
1114 CMPERR_CHECK__SPAN (t->param);
1115 if (c > 0)
1116 {
1117 n += get_rank (a);
1118 a = sub_right (a);
1119 }
1120 else
1121 {
1122 *lo_idx = n + get_rank (a);
1123 a = sub_left (a);
1124 }
1125 }
1126 while (a);
1127
1128 a = t->root;
1129 do
1130 {
1131 c = Item_Compare (cmp, t, hi_item, get_item (a));
1132 CMPERR_CHECK__SPAN (t->param);
1133 if (c < 0)
1134 {
1135 a = sub_left (a);
1136 }
1137 else
1138 {
1139 *hi_idx += get_rank (a);
1140 a = sub_right (a);
1141 }
1142 }
1143 while (a);
1144 return 0;
1145 }
1146 }
1147
1148 /*
1149 * Find the smallest item in tree [t] that is GEQ the passed item
1150 */
1151
1152 void *
1153 avl_find_atleast (const void *item, avl_tree t)
1154 {
1155 #ifndef AVL_NULLCHECKS
1156 if (t == NULL || t->root == NULL)
1157 #else
1158 if (t->root == NULL)
1159 #endif
1160 return NULL;
1161 {
1162 avl_compare_func cmp = t->compare;
1163 avl_node *a = t->root;
1164 void *p = NULL;
1165 int c;
1166
1167 do
1168 {
1169 c = Item_Compare (cmp, t, item, get_item (a));
1170 CMPERR_CHECK__FIND (t->param);
1171 if (c > 0)
1172 {
1173 a = sub_right (a);
1174 }
1175 else
1176 {
1177 p = get_item (a);
1178 a = sub_left (a);
1179 }
1180 }
1181 while (a);
1182 return p;
1183 }
1184 }
1185
1186 /*
1187 * Find the greatest item in tree [t] that is LEQ the passed item
1188 */
1189
1190 void *
1191 avl_find_atmost (const void *item, avl_tree t)
1192 {
1193 #ifndef AVL_NULLCHECKS
1194 if (t == NULL || t->root == NULL)
1195 #else
1196 if (t->root == NULL)
1197 #endif
1198 return NULL;
1199 {
1200 avl_compare_func cmp = t->compare;
1201 avl_node *a = t->root;
1202 void *p = NULL;
1203 int c;
1204
1205 do
1206 {
1207 c = Item_Compare (cmp, t, item, get_item (a));
1208 CMPERR_CHECK__FIND (t->param);
1209 if (c < 0)
1210 {
1211 a = sub_left (a);
1212 }
1213 else
1214 {
1215 p = get_item (a);
1216 a = sub_right (a);
1217 }
1218 }
1219 while (a);
1220 return p;
1221 }
1222 }
1223
1224 /* Retrieve item of index [idx] in tree [t] */
1225
1226 void *
1227 avl_find_index (avl_size_t idx, avl_tree t)
1228 {
1229 avl_node *a;
1230
1231 #ifndef AVL_NULLCHECKS
1232 if (t == NULL)
1233 return NULL;
1234 #endif
1235 a = node_find_index (idx, t);
1236 return a != NULL ? get_item (a) : NULL;
1237 }
1238
1239 #define attach_node(ptr,up,t)\
1240 ptr = new_node(item, up, t);\
1241 if (ptr == NULL){\
1242 AVL_SHOW_ERROR("%s\n", "couldn't allocate node");\
1243 return -1;\
1244 }\
1245 t->count++
1246
1247 /* Iterative insertion */
1248
1249 avl_code_t
1250 avl_ins (void *item, avl_tree t, avl_bool_t allow_duplicates)
1251 {
1252 #ifndef AVL_NULLCHECKS
1253 if (t == NULL)
1254 return NULL;
1255 {
1256 #endif
1257 avl_compare_func cmp = t->compare;
1258 avl_node **r, *a;
1259 int dir = 0;
1260
1261 for (r = &t->root, a = NULL; *r != NULL; r = &a->sub[dir = dir > 0])
1262 {
1263 a = *r;
1264 dir = Item_Compare (cmp, t, item, get_item (a));
1265 CMPERR_CHECK__INS (t->param);
1266 if (!dir && !allow_duplicates)
1267 return 0;
1268 }
1269
1270 attach_node (*r, a, t);
1271
1272 return rebalance_ins (a, dir, t);
1273
1274 #ifndef AVL_NULLCHECKS
1275 } /* end if non-empty tree */
1276 #endif
1277 }
1278
1279 avl_code_t
1280 avl_del (void *item, avl_tree t, void **backup)
1281 {
1282 #ifndef AVL_NULLCHECKS
1283 if (t == NULL || t->root == NULL)
1284 #else
1285 if (t->root == NULL)
1286 #endif
1287 return 0;
1288 {
1289 avl_node *a = node_find (item, t);
1290
1291 if (a == NULL)
1292 return CMPERR_CHECK__DEL (t->param);
1293 return rebalance_del (a, t, backup);
1294 }
1295 }
1296
1297 /* helper function */
1298 static avl_code_t
1299 node_del_first (avl_tree t, struct ptr_handler *h)
1300 {
1301 avl_node *p, *a, *c;
1302 rbal_t bal;
1303
1304 p = node_first (t->root);
1305 a = p->up;
1306 if (sub_right (p) != NULL)
1307 sub_right (p)->up = a;
1308 if (a == NULL)
1309 t->root = sub_right (p);
1310 else
1311 sub_left (a) = sub_right (p);
1312
1313 detach_node (p, t, h);
1314
1315 /* Start backtracking : subtree of [a] in direction [0] is less deep */
1316
1317 for (;; a = c)
1318 {
1319 if (a == NULL)
1320 return 2;
1321
1322 decr_rank (a, 1);
1323 bal = get_bal (a);
1324
1325 if (bal == 0)
1326 {
1327 set_rskew (a);
1328 break;
1329 }
1330 if (bal & 1)
1331 unset_lskew (a);
1332 c = a->up;
1333 if (get_bal (a))
1334 {
1335 p = a;
1336 bal = get_bal (sub_right (p));
1337 if (!(bal & 1))
1338 {
1339 /* bal = 0 or +1 */
1340 /* rotL(p) */
1341 a = sub_right (p);
1342 sub_right (p) = sub_left (a);
1343 if (sub_left (a) != NULL)
1344 sub_left (a)->up = p;
1345 sub_left (a) = p;
1346 if (bal)
1347 {
1348 unset_rskew (p);
1349 unset_rskew (a);
1350 }
1351 else
1352 set_lskew (a);
1353 rbal (a) += rzero (p);
1354 }
1355 else
1356 {
1357 /* rotRL(p) */
1358 a = sub_left (sub_right (p));
1359 sub_left (sub_right (p)) = sub_right (a);
1360 if (sub_right (a) != NULL)
1361 sub_right (a)->up = sub_right (p);
1362 sub_right (p)->up = a;
1363 sub_right (a) = sub_right (p);
1364 sub_right (p) = sub_left (a);
1365 if (sub_left (a) != NULL)
1366 sub_left (a)->up = p;
1367 sub_left (a) = p;
1368 switch (get_bal (a))
1369 {
1370 case 0: /* not skewed */
1371 unset_rskew (p);
1372 unset_lskew (sub_right (a));
1373 break;
1374 case 1: /* left skew */
1375 unset_rskew (p);
1376 unset_lskew (sub_right (a));
1377 set_rskew (sub_right (a));
1378 break;
1379 case 2: /* right skew */
1380 unset_rskew (p);
1381 set_lskew (p);
1382 unset_lskew (sub_right (a));
1383 } /* switch */
1384 rbal (a) &= ~3;
1385 rbal (sub_right (a)) -= rzero (a);
1386 rbal (a) += rzero (p);
1387 } /* which rot */
1388
1389 a->up = p->up;
1390 p->up = a;
1391 /* Done with rotation */
1392 if (c != NULL)
1393 sub_left (c) = a;
1394 else
1395 t->root = a;
1396 if (bal == 0)
1397 break;
1398 } /* if getbal(a) */
1399 } /* for */
1400
1401 /* Finish adjusting ranks */
1402 while ((a = a->up) != NULL)
1403 {
1404 decr_rank (a, 1);
1405 }
1406
1407 return 1;
1408 }
1409
1410 /* helper function */
1411 static avl_code_t
1412 node_del_last (avl_tree t, struct ptr_handler *h)
1413 {
1414
1415 avl_node *p, *a, *c;
1416 rbal_t bal;
1417
1418 p = node_last (t->root);
1419 a = p->up;
1420 if (sub_left (p) != NULL)
1421 sub_left (p)->up = a;
1422 if (a == NULL)
1423 t->root = sub_left (p);
1424 else
1425 sub_right (a) = sub_left (p);
1426
1427 detach_node (p, t, h);
1428
1429 /* Start backtracking : subtree of [a] in direction [1] is less deep */
1430
1431 for (;; a = c)
1432 {
1433 if (a == NULL)
1434 return 2;
1435
1436 bal = get_bal (a);
1437 if (bal == 0)
1438 {
1439 set_lskew (a);
1440 break;
1441 }
1442 if (bal & 2)
1443 unset_rskew (a);
1444 c = a->up;
1445 if (get_bal (a))
1446 {
1447 p = a;
1448 bal = get_bal (sub_left (p));
1449 if (!(bal & 2))
1450 {
1451 /* bal = 0 or -1 */
1452 /* rotR(p) */
1453 a = sub_left (p);
1454 sub_left (p) = sub_right (a);
1455 if (sub_right (a) != NULL)
1456 sub_right (a)->up = p;
1457 sub_right (a) = p;
1458 if (bal)
1459 {
1460 unset_lskew (p);
1461 unset_lskew (a);
1462 }
1463 else
1464 set_rskew (a);
1465 rbal (p) -= rzero (a);
1466 }
1467 else
1468 {
1469 /* rotLR(p) */
1470 a = sub_right (sub_left (p));
1471 sub_right (sub_left (p)) = sub_left (a);
1472 if (sub_left (a) != NULL)
1473 sub_left (a)->up = sub_left (p);
1474 sub_left (p)->up = a;
1475 sub_left (a) = sub_left (p);
1476 sub_left (p) = sub_right (a);
1477 if (sub_right (a) != NULL)
1478 sub_right (a)->up = p;
1479 sub_right (a) = p;
1480 switch (get_bal (a))
1481 {
1482 case 0: /* not skewed */
1483 unset_lskew (p);
1484 unset_rskew (sub_left (a));
1485 break;
1486 case 1: /* left skew */
1487 unset_lskew (p);
1488 set_rskew (p);
1489 unset_rskew (sub_left (a));
1490 break;
1491 case 2: /* right skew */
1492 unset_lskew (p);
1493 unset_rskew (sub_left (a));
1494 set_lskew (sub_left (a));
1495 } /* switch */
1496 rbal (a) &= ~3;
1497 rbal (a) += rzero (sub_left (a));
1498 rbal (p) -= rzero (a);
1499 } /* which rot */
1500
1501 a->up = p->up;
1502 p->up = a;
1503 /* Done with rotation */
1504 if (c != NULL)
1505 sub_right (c) = a;
1506 else
1507 t->root = a;
1508 if (bal == 0)
1509 break;
1510 } /* if getbal(a) */
1511 } /* for */
1512
1513 return 1;
1514 }
1515
1516 /* [p] : juncture node (zeroed out) */
1517
1518 /* [n] : rank of [p] in resulting tree */
1519
1520 /* [delta] = depth_1 - depth_0 */
1521
1522 static avl_code_t
1523 join_left (avl_node * p, avl_node ** r0, avl_node * r1, int delta, int n)
1524 {
1525 avl_node *a = NULL, **r = r0;
1526
1527 if (r1 == NULL)
1528 {
1529 while (*r != NULL)
1530 {
1531 a = *r;
1532 n -= (int)get_rank (a);
1533 r = &sub_right (a);
1534 }
1535 }
1536 else
1537 {
1538 while (delta < -1)
1539 {
1540 a = *r;
1541 delta += (int)(is_lskew (a) + 1);
1542 n -= (int)get_rank (a);
1543 r = &sub_right (a);
1544 }
1545 r1->up = p;
1546 if (*r != NULL)
1547 (*r)->up = p;
1548 if (delta)
1549 set_lskew (p);
1550 }
1551
1552 /* at this point bal(*r) = -1 or 0 */
1553 sub_left (p) = *r;
1554 sub_right (p) = r1;
1555 p->up = a;
1556 set_rank (p, n);
1557 *r = p;
1558
1559 for (;;)
1560 {
1561 if (a == NULL)
1562 return 2;
1563 if (get_bal (a))
1564 break;
1565 set_rskew (a);
1566 a = a->up;
1567 }
1568
1569 /* Rotate if need be */
1570 /* No (+2,0) rotation to do */
1571
1572 if (is_lskew (a))
1573 unset_lskew (a);
1574
1575 else
1576 {
1577 avl_node *p = a;
1578
1579 if (is_rskew (sub_right (p)))
1580 {
1581 /* rotL(p) */
1582 a = sub_right (p);
1583 sub_right (p) = sub_left (a);
1584 if (sub_left (a) != NULL)
1585 sub_left (a)->up = p;
1586 sub_left (a) = p;
1587 unset_rskew (p);
1588 rbal (a) += rzero (p);
1589 }
1590 else
1591 {
1592 /* rotRL(p) */
1593 a = sub_left (sub_right (p));
1594 sub_left (sub_right (p)) = sub_right (a);
1595 if (sub_right (a) != NULL)
1596 sub_right (a)->up = sub_right (p);
1597 sub_right (p)->up = a;
1598 sub_right (a) = sub_right (p);
1599 sub_right (p) = sub_left (a);
1600 if (sub_left (a) != NULL)
1601 sub_left (a)->up = p;
1602 sub_left (a) = p;
1603 switch (get_bal (a))
1604 {
1605 case 0: /* not skewed */
1606 unset_rskew (p);
1607 unset_lskew (sub_right (a));
1608 break;
1609 case 1: /* left skew */
1610 unset_rskew (p);
1611 unset_lskew (sub_right (a));
1612 set_rskew (sub_right (a));
1613 break;
1614 case 2: /* right skew */
1615 unset_rskew (p);
1616 set_lskew (p);
1617 unset_lskew (sub_right (a));
1618 } /* switch */
1619 rbal (sub_right (a)) -= rzero (a);
1620 rbal (a) += rzero (p);
1621 } /* which rot */
1622
1623 rbal (a) &= ~3;
1624 a->up = p->up;
1625 p->up = a;
1626 if (a->up != NULL)
1627 sub_right (a->up) = a;
1628 else
1629 *r0 = a;
1630 } /* rot or not rot */
1631
1632 return 1;
1633 }
1634
1635 /* [p] : juncture node */
1636
1637 /* [n] : rank of [p] in resulting tree */
1638
1639 static avl_code_t
1640 join_right (avl_node * p, avl_node * r0, avl_node ** r1, int delta, int n)
1641 {
1642 avl_node *a = NULL, **r = r1;
1643
1644 if (r0 == NULL)
1645 {
1646 while (*r != NULL)
1647 {
1648 a = *r;
1649 incr_rank (a, (rbal_t)n);
1650 r = &sub_left (a);
1651 }
1652 n = 1;
1653 }
1654 else
1655 {
1656 while (delta > +1)
1657 {
1658 a = *r;
1659 delta -= (int)(is_rskew (a) + 1);
1660 incr_rank (a, (rbal_t)n);
1661 r = &sub_left (a);
1662 }
1663 r0->up = p;
1664 if (*r != NULL)
1665 (*r)->up = p;
1666 if (delta)
1667 set_rskew (p);
1668 }
1669
1670 /* at this point bal(*r) = +1 or 0 */
1671 sub_left (p) = r0;
1672 sub_right (p) = *r;
1673 set_rank (p, n);
1674 p->up = a;
1675 *r = p;
1676
1677 for (;;)
1678 {
1679 if (a == NULL)
1680 return 2;
1681 if (get_bal (a))
1682 break;
1683 set_lskew (a);
1684 a = a->up;
1685 }
1686
1687 /* Rotate if need be */
1688 /* No (-2,0) rotation to do */
1689
1690 if (is_rskew (a))
1691 unset_rskew (a);
1692
1693 else
1694 {
1695 avl_node *p = a;
1696
1697 if (is_lskew (sub_left (p)))
1698 {
1699 /* rotR(p) */
1700 a = sub_left (p);
1701 sub_left (p) = sub_right (a);
1702 if (sub_right (a) != NULL)
1703 sub_right (a)->up = p;
1704 sub_right (a) = p;
1705 unset_lskew (p);
1706 rbal (p) -= rzero (a);
1707 }
1708 else
1709 {
1710 /* rotLR(p) */
1711 a = sub_right (sub_left (p));
1712 sub_right (sub_left (p)) = sub_left (a);
1713 if (sub_left (a) != NULL)
1714 sub_left (a)->up = sub_left (p);
1715 sub_left (p)->up = a;
1716 sub_left (a) = sub_left (p);
1717 sub_left (p) = sub_right (a);
1718 if (sub_right (a) != NULL)
1719 sub_right (a)->up = p;
1720 sub_right (a) = p;
1721 switch (get_bal (a))
1722 {
1723 case 0: /* not skewed */
1724 unset_lskew (p);
1725 unset_rskew (sub_left (a));
1726 break;
1727 case 1: /* left skew */
1728 unset_lskew (p);
1729 set_rskew (p);
1730 unset_rskew (sub_left (a));
1731 break;
1732 case 2: /* right skew */
1733 unset_lskew (p);
1734 unset_rskew (sub_left (a));
1735 set_lskew (sub_left (a));
1736 } /* end switch */
1737 rbal (a) += rzero (sub_left (a));
1738 rbal (p) -= rzero (a);
1739 } /* end which rot */
1740
1741 rbal (a) &= ~3;
1742 a->up = p->up;
1743 p->up = a;
1744 if (a->up != NULL)
1745 sub_left (a->up) = a;
1746 else
1747 *r1 = a;
1748 } /* end rot or not rot */
1749
1750 return 1;
1751 }
1752
1753 avl_code_t
1754 avl_del_first (avl_tree t, void **backup)
1755 {
1756 #ifndef AVL_NULLCHECKS
1757 if (t == NULL || t->root == NULL)
1758 #else
1759 if (t->root == NULL)
1760 #endif
1761 return 0;
1762 {
1763 avl_code_t rv;
1764
1765 if (backup == NULL)
1766 {
1767 rv = node_del_first (t, NULL);
1768 }
1769 else
1770 {
1771 ini_ptr_handler (h, BACKUP);
1772 rv = node_del_first (t, &h);
1773 *backup = h.ptr;
1774 }
1775 return rv;
1776 }
1777 }
1778
1779 avl_code_t
1780 avl_del_last (avl_tree t, void **backup)
1781 {
1782 #ifndef AVL_NULLCHECKS
1783 if (t == NULL || t->root == NULL)
1784 #else
1785 if (t->root == NULL)
1786 #endif
1787 return 0;
1788 {
1789 avl_code_t rv;
1790
1791 if (backup == NULL)
1792 {
1793 rv = node_del_last (t, NULL);
1794 }
1795 else
1796 {
1797 ini_ptr_handler (h, BACKUP);
1798 rv = node_del_last (t, &h);
1799 *backup = h.ptr;
1800 }
1801 return rv;
1802 }
1803 }
1804
1805 avl_code_t
1806 avl_ins_index (void *item, avl_size_t idx, avl_tree t)
1807 {
1808 avl_node *p;
1809
1810 if (idx == 0 || t == NULL || idx > t->count + 1)
1811 return 0;
1812
1813 attach_node (p, NULL, t);
1814 /* Note: 'attach_node' macro increments t->count */
1815
1816 if (idx == 1)
1817 {
1818 return join_right (p, (avl_node *) NULL, &t->root, /*delta= */ 0, 1);
1819 }
1820 else if (idx == t->count)
1821 {
1822 return
1823 join_left (p, &t->root, (avl_node *) NULL, /*delta= */ 0, (int)t->count);
1824 }
1825 else
1826 {
1827 avl_node *a = node_find_index (idx - 1, t);
1828 int dir;
1829
1830 if (sub_right (a) != NULL)
1831 {
1832 a = node_first (sub_right (a));
1833 sub_left (a) = p;
1834 dir = 0;
1835 }
1836 else
1837 {
1838 sub_right (a) = p;
1839 dir = 1;
1840 }
1841
1842 p->up = a;
1843 return rebalance_ins (a, dir, t);
1844 }
1845 }
1846
1847 avl_code_t
1848 avl_del_index (avl_size_t idx, avl_tree t, void **backup)
1849 {
1850 #ifndef AVL_NULLCHECKS
1851 if (t == NULL)
1852 return 0;
1853 #endif
1854
1855 if (idx == 0 || idx > t->count)
1856 return 0;
1857 if (idx == 1)
1858 return avl_del_first (t, backup);
1859 if (idx == t->count)
1860 return avl_del_last (t, backup);
1861 {
1862 avl_node *a = node_find_index (idx, t);
1863
1864 return rebalance_del (a, t, backup);
1865 }
1866 }
1867
1868 /*
1869 * Outcome: [t0] handles the concatenation of [t0] and [t1]
1870 */
1871
1872 void
1873 avl_cat (avl_tree t0, avl_tree t1)
1874 {
1875 #ifndef AVL_NULLCHECKS
1876 if (t0 == NULL || t1 == NULL || t1->root == NULL)
1877 #else
1878 if (t1->root == NULL)
1879 #endif
1880 return;
1881
1882 if (t0->root == NULL)
1883 {
1884 t0->root = t1->root;
1885 t0->count = t1->count;
1886 t1->root = NULL;
1887 t1->count = 0;
1888
1889 }
1890 else
1891 {
1892 int delta = depth (t1->root) - depth (t0->root);
1893
1894 ini_ptr_handler (h, DETACH);
1895
1896 if (delta <= 0)
1897 {
1898 if (node_del_first (t1, &h) == 2)
1899 --delta;
1900 (void) join_left ((avl_node *) h.ptr, &t0->root, t1->root, delta,
1901 (int)(t0->count + 1));
1902 }
1903 else
1904 {
1905 if (node_del_last (t0, &h) == 2)
1906 ++delta;
1907 (void) join_right ((avl_node *) h.ptr, t0->root, &t1->root, delta,
1908 (int)(t0->count + 1));
1909 t0->root = t1->root;
1910 }
1911
1912 t1->root = NULL;
1913 t0->count += t1->count + 1;
1914 t1->count = 0;
1915 }
1916 }
1917
1918 /*
1919 * - [t0] and [t1] are existing handles
1920 * - See Donald Knuth, TAOCP Vol.3 "Sorting and searching"
1921 */
1922
1923 avl_code_t
1924 avl_split (const void *item, avl_tree t, avl_tree t0, avl_tree t1)
1925 {
1926 #ifndef AVL_NULLCHECKS
1927 if (t == NULL || t->root == NULL)
1928 #else
1929 if (t->root == NULL)
1930 #endif /* AVL_NULLCHECKS */
1931 return 0;
1932
1933 t0->root = NULL;
1934 t1->root = NULL;
1935 t0->count = 0;
1936 t1->count = 0;
1937
1938 {
1939 avl_compare_func cmp = t->compare;
1940 avl_node *a, *p, *sn; /* sn: split node */
1941 int d_, k, na, an[AVL_STACK_CAPACITY];
1942
1943 /* invariant: [na]= size of tree rooted at [a] plus one */
1944
1945 for (a = t->root, na = (int)(t->count + 1), k = 0;;)
1946 {
1947 d_ = Item_Compare (cmp, t, item, get_item (a));
1948 CMPERR_CHECK__SPLIT (t->param);
1949 if (!d_)
1950 break;
1951 p = a->sub[d_ = d_ > 0];
1952 if (p == NULL)
1953 return 0;
1954 an[k++] = na;
1955 if (d_)
1956 na -= (int)get_rank (a);
1957 else
1958 na = (int)get_rank (a);
1959 a = p;
1960 }
1961
1962 /* record split node */
1963 sn = a;
1964
1965 if (k == 0)
1966 {
1967 t0->root = sub_left (a);
1968 t1->root = sub_right (a);
1969 if (t0->root != NULL)
1970 t0->root->up = NULL;
1971 if (t1->root != NULL)
1972 t1->root->up = NULL;
1973 t0->count = get_rank (a) - 1;
1974 t1->count = t->count - get_rank (a);
1975 }
1976 else
1977 {
1978 avl_node *r[2], *rr;
1979 int h[2], ha, hh;
1980 avl_size_t n[2], nn;
1981
1982 r[0] = sub_left (a);
1983 r[1] = sub_right (a);
1984 if (r[0] != NULL)
1985 r[0]->up = NULL;
1986 if (r[1] != NULL)
1987 r[1]->up = NULL;
1988 ha = depth (a);
1989 h[0] = ha - (is_rskew (a) ? 2 : 1);
1990 h[1] = ha - (is_lskew (a) ? 2 : 1);
1991 n[0] = get_rank (a); /* size of r[0] plus one */
1992 n[1] = (avl_size_t)na - n[0]; /* size of r[1] plus one */
1993
1994 for (p = a->up, d_ = a != sub_left (p);;)
1995 {
1996
1997 a = p; /* a: juncture node */
1998 p = a->up;
1999
2000 if (d_ == 0)
2001 {
2002 hh = h[1];
2003 ha += (is_rskew (a) ? 2 : 1);
2004 h[1] = ha - (is_lskew (a) ? 2 : 1);
2005 nn = n[1];
2006 n[1] += (avl_size_t)(an[k - 1] - (int)get_rank (a));
2007 if (p != NULL)
2008 d_ = a != sub_left (p);
2009 rbal (a) = 0;
2010
2011 if (h[1] >= hh)
2012 {
2013 rr = r[1];
2014 r[1] = sub_right (a);
2015 if (r[1] != NULL)
2016 r[1]->up = NULL;
2017 h[1] += (2 == join_right (a, rr, r + 1, h[1] - hh, (int)nn));
2018 }
2019 else
2020 {
2021 h[1] =
2022 hh + (2 ==
2023 join_left (a, r + 1, sub_right (a), h[1] - hh,
2024 (int)nn));
2025 }
2026 }
2027 else
2028 {
2029 hh = h[0];
2030 ha += (is_lskew (a) ? 2 : 1);
2031 h[0] = ha - (is_rskew (a) ? 2 : 1);
2032 nn = get_rank (a);
2033 n[0] += nn;
2034 if (p != NULL)
2035 d_ = a != sub_left (p);
2036 rbal (a) = 0;
2037
2038 if (h[0] >= hh)
2039 {
2040 rr = r[0];
2041 r[0] = sub_left (a);
2042 if (r[0] != NULL)
2043 r[0]->up = NULL;
2044 h[0] += (2 == join_left (a, r, rr, hh - h[0], (int)nn));
2045 }
2046 else
2047 {
2048 h[0] =
2049 hh + (2 ==
2050 join_right (a, sub_left (a), r, hh - h[0], (int)nn));
2051 }
2052 }
2053
2054 if (--k == 0)
2055 break;
2056 } /* for p */
2057
2058 t0->root = r[0];
2059 t1->root = r[1];
2060 t0->count = n[0] - 1;
2061 t1->count = n[1] - 1;
2062 } /* if k==0 */
2063
2064 /* Detach split node */
2065 detach_node (sn, t, NULL);
2066 t->root = NULL;
2067 t->count = 0;
2068
2069 return 1;
2070 }
2071 }
2072
2073 /* Inorder traversal */
2074
2075 void
2076 avl_walk (avl_tree t, avl_item_func proc, void *param)
2077 {
2078 #ifndef AVL_NULLCHECKS
2079 if (t == NULL || t->root == NULL)
2080 #else
2081 if (t->root == NULL)
2082 #endif
2083 return;
2084
2085 {
2086 avl_node *a = t->root, *p;
2087
2088 while (1)
2089 {
2090 while (sub_left (a) != NULL)
2091 a = sub_left (a);
2092
2093 while (1)
2094 {
2095 (*proc) (get_item (a), param);
2096 if (sub_right (a) != NULL)
2097 break;
2098 do
2099 {
2100 p = a;
2101 a = p->up;
2102 if (a == NULL)
2103 return;
2104 }
2105 while (p != sub_left (a));
2106 }
2107 a = sub_right (a);
2108 }
2109 }
2110 }
2111
2112 /* recursive helper for 'avl_slice' */
2113 static int
2114 node_slice (avl_node ** root, avl_node ** cur, avl_tree tree, avl_size_t len)
2115 {
2116 avl_size_t mid = len / 2;
2117
2118 if (mid == 0)
2119 {
2120 if ((*root = new_node ((*cur)->item, /*parent */ NULL, tree)) == NULL)
2121 return -1;
2122 sub_left (*root) = NULL;
2123 sub_right (*root) = NULL;
2124 rbal (*root) = 4;
2125 *cur = node_next (*cur);
2126 return 0;
2127
2128 }
2129 else if ((*root = new_node (NULL, /*parent */ NULL, tree)) == NULL)
2130 {
2131 return -1;
2132 }
2133 else
2134 {
2135 avl_node *p = *root;
2136 int h0, h1 = -1;
2137
2138 rbal (p) = (mid + 1) << 2;
2139
2140 if ((h0 = node_slice (&sub_left (p), cur, tree, mid)) < 0)
2141 return -1;
2142
2143 p->item = (*tree->copy) ((*cur)->item);
2144 sub_left (p)->up = p;
2145
2146 *cur = node_next (*cur);
2147
2148 if (len -= mid + 1)
2149 {
2150 if ((h1 = node_slice (&sub_right (p), cur, tree, len)) < 0)
2151 return -1;
2152 sub_right (p)->up = p;
2153 }
2154
2155 if (h0 > h1)
2156 set_lskew (p);
2157 else if (h0 < h1)
2158 {
2159 set_rskew (p);
2160 return 1 + h1;
2161 }
2162 return 1 + h0;
2163 }
2164 }
2165
2166 /* Return a slice t[lo,hi) as a new tree */
2167
2168 avl_tree
2169 avl_slice (avl_tree t, avl_size_t lo_idx, avl_size_t hi_idx, void *param)
2170 {
2171 #ifndef AVL_NULLCHECKS
2172 if (t == NULL)
2173 return NULL;
2174 #endif /* AVL_NULLCHECKS */
2175
2176 if (lo_idx > hi_idx || lo_idx > t->count)
2177 return NULL;
2178 if (lo_idx < 1)
2179 lo_idx = 1;
2180 if (hi_idx > t->count + 1)
2181 hi_idx = t->count + 1;
2182
2183 {
2184 avl_tree tt = avl_create (t->compare,
2185 t->copy,
2186 t->dispose,
2187 t->alloc,
2188 t->dealloc,
2189 param);
2190
2191 if (tt == NULL)
2192 {
2193 AVL_SHOW_ERROR ("%s\n",
2194 "couldn't allocate new handle in avl_slice()");
2195 return NULL;
2196 }
2197
2198 if (lo_idx < hi_idx)
2199 {
2200 avl_node *cur = node_find_index (lo_idx, t);
2201
2202 if (node_slice (&tt->root, &cur, t, tt->count = hi_idx - lo_idx) < 0)
2203 {
2204 AVL_SHOW_ERROR ("%s\n", "couldn't allocate node in avl_slice()");
2205 node_empty (tt);
2206 (*t->dealloc) (tt);
2207 return NULL;
2208 }
2209 tt->root->up = NULL;
2210 }
2211 return tt;
2212 }
2213 }
2214
2215 /* recursive helper for 'avl_xload' */
2216
2217 static int
2218 node_load (avl_node ** root, avl_itersource cur, void **pres, avl_tree desc,
2219 avl_size_t len)
2220 {
2221 avl_size_t mid = len / 2;
2222
2223 if (mid == 0)
2224 {
2225 if (0 != (*cur->f) (cur, pres)
2226 || (*root = new_node (*pres, /*parent */ NULL, desc)) == NULL)
2227 return -1;
2228 sub_left (*root) = NULL;
2229 sub_right (*root) = NULL;
2230 rbal (*root) = 4;
2231 return 0;
2232
2233 }
2234 else if ((*root = new_node (NULL, /*parent */ NULL, desc)) == NULL)
2235 {
2236 return -1;
2237 }
2238 else
2239 {
2240 avl_node *p = *root;
2241 int h0, h1 = -1;
2242
2243 rbal (p) = (mid + 1) << 2;
2244
2245 if ((h0 = node_load (&sub_left (p), cur, pres, desc, mid)) < 0)
2246 return -1;
2247
2248 if (0 != (*cur->f) (cur, pres))
2249 return -1;
2250
2251 p->item = (*desc->copy) (*pres);
2252 sub_left (p)->up = p;
2253
2254 if (len -= mid + 1)
2255 {
2256 if ((h1 = node_load (&sub_right (p), cur, pres, desc, len)) < 0)
2257 return -1;
2258 sub_right (p)->up = p;
2259 }
2260
2261 if (h0 > h1)
2262 set_lskew (p);
2263 else if (h0 < h1)
2264 {
2265 set_rskew (p);
2266 return 1 + h1;
2267 }
2268 return 1 + h0;
2269 }
2270 }
2271
2272 /* Load 'len' items from itersource */
2273
2274 avl_tree
2275 avl_xload (avl_itersource src, void **pres, avl_size_t len, avl_config conf,
2276 void *tree_param)
2277 {
2278 #ifndef AVL_NULLCHECKS
2279 if (src == NULL)
2280 return NULL;
2281 {
2282 #endif /* AVL_NULLCHECKS */
2283
2284 avl_tree tt = avl_create (conf->compare,
2285 conf->copy,
2286 conf->dispose,
2287 conf->alloc,
2288 conf->dealloc,
2289 tree_param);
2290
2291 if (tt == NULL)
2292 {
2293 AVL_SHOW_ERROR ("%s\n", "couldn't allocate new handle in avl_load()");
2294 return NULL;
2295 }
2296
2297 if (len)
2298 {
2299 if (node_load (&tt->root, src, pres, tt, tt->count = len) < 0)
2300 {
2301 AVL_SHOW_ERROR ("%s\n", "couldn't allocate node in avl_load()");
2302 node_empty (tt);
2303 (*tt->dealloc) (tt);
2304 return NULL;
2305 }
2306 tt->root->up = NULL;
2307 }
2308 return tt;
2309 #ifndef AVL_NULLCHECKS
2310 }
2311 #endif
2312 }
2313
2314 #ifdef HAVE_AVL_VERIFY
2315
2316 /* Verification routine */
2317 typedef enum
2318 {
2319 okay = 0,
2320 bad_parent = 1,
2321 bad_rank = 2,
2322 out_of_balance = 3,
2323 out_of_order = 4,
2324 diff_mismatch = 5,
2325 count_mismatch = 6
2326 }
2327 avl_verify_code;
2328
2329 static avl_bool_t
2330 avl_error (avl_verify_code err)
2331 {
2332 static char *errmess[] = {
2333 "Bad parent link",
2334 "Rank error",
2335 "Out of balance",
2336 "Out of order",
2337 "Differential mismatch",
2338 "Count mismatch"
2339 };
2340
2341 AVL_SHOW_ERROR ("Invalid avl_tree: %s\n", errmess[err - 1]);
2342 return avl_false;
2343 }
2344
2345 static int bals[] = { 1, 0, 2 };
2346
2347 /*
2348 helper for recursive 'avl_verify' function
2349 return 0 iff okay
2350 */
2351
2352 static avl_verify_code
2353 node_verify (avl_node * root, avl_tree tree, int *h, avl_size_t * c,
2354 avl_node * up)
2355 {
2356 avl_verify_code err = okay;
2357
2358 if (root == NULL)
2359 *h = AVL_MIN_DEPTH, *c = 0;
2360 else
2361 {
2362 #define AVL_ASSERT(expr,n) if (expr) ; else { err = n; break; }
2363 #define CHECK(err) if (err) break
2364
2365 avl_node *left, *right;
2366 avl_size_t c_[2];
2367 int h_[2], delta;
2368
2369 left = sub_left (root);
2370 right = sub_right (root);
2371 do
2372 {
2373 AVL_ASSERT (root->up == up, bad_parent);
2374 CHECK (err = node_verify (left, tree, h_, c_, root));
2375 AVL_ASSERT (get_rank (root) == *c_ + 1, bad_rank);
2376 CHECK (err = node_verify (right, tree, h_ + 1, c_ + 1, root));
2377 delta = h_[1] - h_[0];
2378 AVL_ASSERT (delta >= -1 && delta <= +1, out_of_balance);
2379 AVL_ASSERT (get_bal (root) == bals[delta + 1], diff_mismatch);
2380 AVL_ASSERT (left == NULL
2381 || (Item_Compare (tree->compare, tree, get_item (left),
2382 get_item (root)) <=
2383 0 CMPERR_CHECK__VERIFY (tree->param)),
2384 out_of_order);
2385 AVL_ASSERT (right == NULL
2386 ||
2387 (Item_Compare
2388 (tree->compare, tree, get_item (root),
2389 get_item (right)) <=
2390 0 CMPERR_CHECK__VERIFY (tree->param)), out_of_order);
2391 *h = 1 + (h_[0] > h_[1] ? h_[0] : h_[1]);
2392 *c = 1 + c_[0] + c_[1];
2393 }
2394 while (0);
2395 }
2396 return err;
2397 }
2398
2399 avl_bool_t
2400 avl_verify (avl_tree t)
2401 {
2402 #ifndef AVL_NULLCHECKS
2403 if (t == NULL)
2404 return avl_false;
2405 #endif /* AVL_NULLCHECKS */
2406 {
2407 int h;
2408 avl_size_t c;
2409 avl_verify_code err;
2410
2411 err = node_verify (t->root, t, &h, &c, (avl_node *) NULL);
2412 if (err)
2413 return avl_error (err);
2414 if (c != t->count)
2415 return avl_error (count_mismatch);
2416 return avl_true;
2417 }
2418 }
2419 #endif /* HAVE_AVL_VERIFY */
2420
2421 /****************
2422 * *
2423 * ITERATORS *
2424 * *
2425 ****************/
2426
2427 typedef enum
2428 {
2429 AVL_ITERATOR_PRE,
2430 AVL_ITERATOR_POST,
2431 AVL_ITERATOR_INTREE
2432 }
2433 avl_status_t;
2434
2435 struct avl_iterator_
2436 {
2437 avl_node *pos;
2438 avl_tree tree;
2439 avl_status_t status;
2440 };
2441
2442 #define get_root(i) i->tree->root
2443 #define is_pre(i) i->status == AVL_ITERATOR_PRE
2444 #define is_post(i) i->status == AVL_ITERATOR_POST
2445 #define set_pre_iterator(i) i->status = AVL_ITERATOR_PRE
2446 #define set_post_iterator(i) i->status = AVL_ITERATOR_POST
2447 #define set_in_iterator(i) i->status = AVL_ITERATOR_INTREE
2448
2449 /* Position existing iterator [iter] at node matching [item] in its own tree,
2450 * if it exists ; otherwise do nothing
2451 */
2452
2453 void
2454 avl_iterator_seek (const void *item, avl_iterator iter)
2455 {
2456 avl_node *p = node_find (item, iter->tree);
2457
2458 if (p != NULL)
2459 {
2460 set_in_iterator (iter);
2461 iter->pos = p;
2462 }
2463 }
2464
2465 void
2466 avl_iterator_seek_index (avl_size_t idx, avl_iterator iter)
2467 {
2468 avl_node *p = node_find_index (idx, iter->tree);
2469
2470 if (p != NULL)
2471 {
2472 set_in_iterator (iter);
2473 iter->pos = p;
2474 }
2475 }
2476
2477 /* Return item pointer at current position */
2478
2479 void *
2480 avl_iterator_cur (avl_iterator iter)
2481 {
2482 return iter->pos != NULL ? get_item (iter->pos) : NULL;
2483 }
2484
2485 avl_size_t
2486 avl_iterator_count (avl_iterator iter)
2487 {
2488 return iter->tree->count;
2489 }
2490
2491 avl_size_t
2492 avl_iterator_index (avl_iterator iter)
2493 {
2494 if (iter->pos != NULL)
2495 return get_index (iter->pos);
2496 else if (is_pre (iter))
2497 return 0;
2498 else
2499 return iter->tree->count + 1;
2500 }
2501
2502 /* Rustic: */
2503
2504 avl_iterator
2505 avl_iterator_new (avl_tree t, avl_ini_t ini, ...)
2506 {
2507 va_list args;
2508 avl_iterator iter = NULL;
2509
2510 va_start (args, ini);
2511
2512 if (t == NULL)
2513 goto finish;
2514
2515 if ((iter = (*t->alloc) (sizeof (struct avl_iterator_))) == NULL)
2516 {
2517 AVL_SHOW_ERROR ("%s\n", "couldn't create iterator");
2518 goto finish;
2519 }
2520
2521 iter->pos = NULL;
2522 iter->tree = t;
2523
2524 if (ini != AVL_ITERATOR_INI_INTREE)
2525 {
2526 iter->status =
2527 (ini == AVL_ITERATOR_INI_PRE) ? AVL_ITERATOR_PRE : AVL_ITERATOR_POST;
2528 }
2529 else
2530 {
2531 const void *item = NULL;
2532
2533 item = va_arg (args, const void *);
2534
2535 set_pre_iterator (iter);
2536
2537 if (item == NULL)
2538 AVL_SHOW_ERROR ("%s\n", "missing argument to avl_iterator_new()");
2539 else
2540 avl_iterator_seek (item, iter);
2541 }
2542
2543 finish:
2544 va_end (args);
2545 return iter;
2546 }
2547
2548 /*
2549 * The following used to write to memory after it was freed.
2550 * Corrected by: David Turner <novalis@openplans.org>
2551 */
2552 void
2553 avl_iterator_kill (avl_iterator iter)
2554 {
2555 if (iter != NULL)
2556 {
2557 avl_dealloc_func dealloc = iter->tree->dealloc;
2558 iter->pos = NULL;
2559 iter->tree = NULL;
2560 (*dealloc) (iter);
2561 }
2562 }
2563
2564 void *
2565 avl_iterator_next (avl_iterator iter)
2566 {
2567 avl_node *a = iter->pos;
2568
2569 if (is_post (iter))
2570 return NULL;
2571
2572 if (is_pre (iter))
2573 {
2574 a = get_root (iter);
2575 if (a != NULL)
2576 {
2577 a = node_first (a);
2578 set_in_iterator (iter);
2579 }
2580 }
2581 else
2582 {
2583 a = node_next (a);
2584 if (a == NULL)
2585 set_post_iterator (iter);
2586 }
2587
2588 iter->pos = a;
2589 return a != NULL ? get_item (a) : NULL;
2590 }
2591
2592 void *
2593 avl_iterator_prev (avl_iterator iter)
2594 {
2595 avl_node *a = iter->pos;
2596
2597 if (is_pre (iter))
2598 return NULL;
2599
2600 if (is_post (iter))
2601 {
2602 a = get_root (iter);
2603 if (a != NULL)
2604 {
2605 a = node_last (a);
2606 set_in_iterator (iter);
2607 }
2608 }
2609 else
2610 {
2611 a = node_prev (a);
2612 if (a == NULL)
2613 set_pre_iterator (iter);
2614 }
2615
2616 iter->pos = a;
2617 return a != NULL ? get_item (a) : NULL;
2618 }
2619
2620 /* Remove node at current position */
2621
2622 /* Move cursor to next position */
2623
2624 avl_code_t
2625 avl_iterator_del (avl_iterator iter, void **backup)
2626 {
2627 if (iter == NULL || iter->pos == NULL)
2628 return 0;
2629 {
2630 avl_node *a = iter->pos, *p;
2631
2632 p = node_next (a);
2633 if (p == NULL)
2634 set_post_iterator (iter);
2635 iter->pos = p;
2636 return rebalance_del (a, iter->tree, backup);
2637 }
2638 }
LuaTeX git mirror