diff options
author | Taco Hoekwater <taco@elvenkind.com> | 2009-04-16 07:36:46 +0000 |
---|---|---|
committer | Taco Hoekwater <taco@elvenkind.com> | 2009-04-16 07:36:46 +0000 |
commit | 79e9c535970a1887e1b6b2196cd90775955ea486 (patch) | |
tree | 61c8bd011c749b0d0e732630e69bb3f3f07b7219 /Build/source/texk/web2c/mplibdir/avl.c | |
parent | 9a146db3a4562660570a744a7c7471132090a537 (diff) |
This is an initial import of the current trunk state of MPlib
(version 1.110 and a few minor patches). For the moment,
the mplib.am builds the executable "newmpost", that should
be fixed soon.
git-svn-id: svn://tug.org/texlive/trunk@12732 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/web2c/mplibdir/avl.c')
-rw-r--r-- | Build/source/texk/web2c/mplibdir/avl.c | 2636 |
1 files changed, 2636 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/mplibdir/avl.c b/Build/source/texk/web2c/mplibdir/avl.c new file mode 100644 index 00000000000..a8421d4c93d --- /dev/null +++ b/Build/source/texk/web2c/mplibdir/avl.c @@ -0,0 +1,2636 @@ + +/* pyavl -- File "avl.c" */ + +/* AVL trees with RANK field and parent pointers */ + +#include "avl.h" + +#ifdef AVL_SHOW_ERROR_ON +#define AVL_SHOW_ERROR(fmt,arg) fprintf(stderr, "! avl.c: " fmt, arg) +#else +#define AVL_SHOW_ERROR(fmt,arg) (void) (fmt), (void) (arg) +#endif + +void * +avl_default_item_copy (const void *item) +{ + return (void *) item; +} + +void * +avl_default_item_dispose (void *item) +{ + return (void *) NULL; +} + +#ifndef MPW_C +typedef uint32_t rbal_t; /* integral type to encode rank and skew bits */ +#else +typedef UInt32 rbal_t; +#endif + +/* + * avl_node structure + */ + +typedef struct avl_node +{ + struct avl_node *sub[2]; + struct avl_node *up; + rbal_t rbal; + void *item; +} +avl_node; + +/* + * avl_tree structure + */ + +struct avl_tree_ +{ + avl_node *root; + avl_size_t count; /* how many nodes in tree rooted at [root] */ + avl_compare_func compare; /* compare items */ + avl_item_copy_func copy; + avl_item_dispose_func dispose; + avl_alloc_func alloc; /* to allocate memory (same signature as malloc) */ + avl_dealloc_func dealloc; /* to deallocate memory (same signature as free) */ + void *param; +}; + +#define Item_Compare(cmp, tree, item1, item2)\ + (*cmp)(tree->param, item1, item2) + +/* patches (November 2004) */ + +#if AVL_CMPERR != 0 +#define CMPERR_CHECK__FIND(param) if (avl_errcmp_occurred(param)) return NULL +#define CMPERR_CHECK__INDEX(param) if (avl_errcmp_occurred(param)) return 0 +#define CMPERR_CHECK__SPAN(param) if (avl_errcmp_occurred(param)) return -2 +#define CMPERR_CHECK__INS(param) if (avl_errcmp_occurred(param)) return -2 +#define CMPERR_CHECK__DEL(param) (avl_errcmp_occurred(param) ? -2 : 0) +#define CMPERR_CHECK__SPLIT(param) if (avl_errcmp_occurred(param)) return -2 +#define CMPERR_CHECK__VERIFY(param) && (!avl_errcmp_occurred(param)) +#else +#define CMPERR_CHECK__FIND(param) (void) param +#define CMPERR_CHECK__INDEX(param) (void) param +#define CMPERR_CHECK__SPAN(param) (void) param +#define CMPERR_CHECK__INS(param) (void) param +#define CMPERR_CHECK__DEL(param) 0 +#define CMPERR_CHECK__SPLIT(param) (void) param +#define CMPERR_CHECK__VERIFY(param) /* nothing */ +#endif + +#define sub_left(a) (a)->sub[0] +#define sub_right(a) (a)->sub[1] +#define get_item(a) (a)->item + +/* RANK(a) = size of left subtree + 1 */ + +#define rbal(a)\ + (a)->rbal +#define rzero(a)\ + ( rbal(a) & ~3 ) +#define get_bal(a)\ + ( rbal(a) & 3 ) +#define is_lskew(a)\ + ( rbal(a) & 1 ) +#define is_rskew(a)\ + ( rbal(a)>>1 & 1) +#define set_lskew(a)\ + ( rbal(a) |= 1 ) +#define set_rskew(a)\ + ( rbal(a) |= 2 ) +#define set_skew(a,d)\ + ( rbal(a) |= (1 << d) ) +#define unset_lskew(a)\ + ( rbal(a) &= ~1 ) +#define unset_rskew(a)\ + ( rbal(a) &= ~2 ) +#define get_rank(a)\ + ( rbal(a) >> 2 ) +#define set_rank(a,r)\ + ( rbal(a) = (r<<2 | get_bal(a)) ) +#define incr_rank(a,r)\ + ( rbal(a) += r<<2 ) +#define decr_rank(a,r)\ + ( rbal(a) -= r<<2 ) + +#define AVL_MIN_DEPTH 0 + +/*** Node management ***/ + +#define DETACH_FUNC 1 /* nonzero to use function not macro */ + +/* helper structure */ +typedef enum +{ + OP_BACKUP, OP_DETACH, OP_FREE +} +whichop_t; +struct ptr_handler +{ + whichop_t whichop; + void *ptr; +}; + +#define ini_ptr_handler(h,op) struct ptr_handler h = { OP_##op, NULL } +#define clear_node(a) \ + sub_left(a) = NULL; \ + sub_right(a) = NULL; \ + (a)->up = NULL; \ + rbal(a) = 4u + +/* Called by 'avl_ins', 'avl_dup', 'node_slice' */ +static avl_node * +new_node (void *item, avl_node * up, avl_tree t) +{ + avl_node *a = (*t->alloc) (sizeof (avl_node)); + + if (a != NULL) + { + sub_left (a) = NULL; + sub_right (a) = NULL; + a->up = up; + a->rbal = 4u; + a->item = (*t->copy) (item); + } + return a; +} + +static void +free_node (avl_node * a, avl_tree t) +{ + a->item = (*t->dispose) (a->item); + (*t->dealloc) (a); +} + +#define backup_item(backup,item,t) if (backup == NULL) ; else *backup = (*t->copy)(item) + +#if ! DETACH_FUNC + +/* macro to detach node [a] from tree [t] */ +#define detach_node(a,t,h) { struct ptr_handler *ch = h; \ + clear_node(a); \ + do { \ + if (ch == NULL) ; \ + else if (ch->whichop == OP_DETACH){ \ + ch->ptr = a; \ + break; \ + } else if (ch->whichop == OP_BACKUP){ \ + ch->ptr = (*t->copy)(a->item); \ + } \ + free_node(a, t); \ + } while (0);} \ + t->count-- +#else + +/* function to detach node [a] from tree [t] */ +static void +detach_node (avl_node * a, avl_tree t, struct ptr_handler *h) +{ + clear_node (a); + do + { + if (h == NULL); + else if (h->whichop == OP_DETACH) + { + h->ptr = a; + break; + } + else if (h->whichop == OP_BACKUP) + { + h->ptr = (*t->copy) (a->item); + } + free_node (a, t); + } + while (0); + t->count--; +} +#endif /* DETACH_FUNC */ + +/*** Tree methods ***/ + +avl_tree +avl_create (avl_compare_func compare, avl_item_copy_func copy, + avl_item_dispose_func dispose, avl_alloc_func alloc, + avl_dealloc_func dealloc, void *param) +{ + avl_tree t = (*alloc) (sizeof (struct avl_tree_)); + + if (t == NULL) + AVL_SHOW_ERROR ("%s\n", "couldn't create new handle in avl_create()"); + else + { + t->root = NULL; + t->count = 0; + t->param = param; + t->compare = compare; + t->copy = copy; + t->dispose = dispose; + t->alloc = alloc; + t->dealloc = dealloc; + } + return t; +} + +/* Empty the tree, using rotations */ + +static void +node_empty (avl_tree t) +{ + avl_node *a, *p; + + for (a = t->root; a != NULL;) + { + p = a; + if (sub_right (a) == NULL) + a = sub_left (a); + else + { + while (sub_left (a) != NULL) + { + /* rotR(a) */ + a = sub_left (a); + sub_left (p) = sub_right (a); + sub_right (a) = p; + p = a; + } + a = sub_right (p); + } + free_node (p, t); + t->count--; + } + t->root = NULL; +} + +/* [t] is an existing tree handle */ + +/* this function invokes node_empty() */ + +void +avl_reset (avl_tree t, + avl_compare_func compare, + avl_item_copy_func copy, + avl_item_dispose_func dispose, + avl_alloc_func alloc, avl_dealloc_func dealloc) +{ + if (t == NULL) + return; + node_empty (t); + t->compare = compare; + t->copy = copy; + t->dispose = dispose; + t->alloc = alloc; + t->dealloc = dealloc; +} + +void +avl_empty (avl_tree t) +{ + if (t != NULL) + node_empty (t); +} + +/* Destroy nodes, free handle */ + +void +avl_destroy (avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL) + return; +#endif + node_empty (t); + (*t->dealloc) (t); +} + +avl_tree +avl_dup (avl_tree t, void *param) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL) + return NULL; +#endif + { + avl_tree tt = avl_create ( + /*(avl_compare_func) */ t->compare, + /*(avl_item_copy_func) */ t->copy, + /*(avl_item_dispose_func) */ t->dispose, + /*(avl_alloc_func) */ t->alloc, + /*(avl_dealloc_func) */ t->dealloc, + param); + + if (tt == NULL) + { + AVL_SHOW_ERROR ("%s\n", "couldn't create new handle in avl_dup()"); + return NULL; + } + + tt->count = t->count; + + if (t->root == NULL) + return tt; + + { + avl_node *a, *c, *s; + + a = t->root; + tt->root = c = new_node (get_item (a), NULL, t); + if (c == NULL) + goto abort; + + sub_right (c) = NULL; /*!!! */ + rbal (c) = rbal (a); + + while (1) + { + while (sub_left (a) != NULL) + { + a = sub_left (a); + sub_left (c) = s = new_node (get_item (a), NULL, t); + if (s == NULL) + goto recover; + s->up = c; + sub_right (s) = c; + c = s; + rbal (c) = rbal (a); + } + + sub_left (c) = NULL; + + while (sub_right (a) == NULL) + { + s = sub_right (c); + sub_right (c) = NULL; + c = s; + /* Find successor of [a] in original tree */ + do + { + s = a; + a = s->up; + if (a == NULL) + return tt; + } + while (s != sub_left (a)); + } + + a = sub_right (a); + s = new_node (get_item (a), NULL, t); + if (s == NULL) + goto recover; + sub_right (s) = sub_right (c); + sub_right (c) = s; + s->up = c; + c = s; + rbal (c) = rbal (a); + } + /* recovery code */ + recover: + while (1) + { + s = sub_right (c); + sub_right (c) = NULL; + if (s == NULL) + break; + c = s; + } + node_empty (tt); + + abort: + (*t->dealloc) (tt); + AVL_SHOW_ERROR ("%s\n", "couldn't allocate node in avl_dup()"); + return NULL; + } + } +} + +avl_bool_t +avl_isempty (avl_tree t) +{ +#ifndef AVL_NULLCHECKS + return t == NULL || t->root == NULL; +#else + return t->root == NULL; +#endif +} + +avl_size_t +avl_size (avl_tree t) +{ +#ifndef AVL_NULLCHECKS + return t == NULL ? 0 : t->count; +#else + return t->count; +#endif +} + +static int +depth (avl_node * a) +{ + int h = AVL_MIN_DEPTH; + + for (; a != NULL; ++h) + a = a->sub[is_rskew (a)]; + return h; +} + +static avl_node * +node_first (avl_node * a) +{ + while (sub_left (a) != NULL) + a = sub_left (a); + return a; +} + +static avl_node * +node_last (avl_node * a) +{ + while (sub_right (a) != NULL) + a = sub_right (a); + return a; +} + +/* [a] : non-null */ + +static avl_node * +node_next (avl_node * a) +{ + if (sub_right (a) != NULL) + return node_first (sub_right (a)); + { + avl_node *p; + + do + { + p = a; + a = p->up; + } + while (a != NULL && sub_right (a) == p); + return a; + } +} + +/* [a] : non-null */ + +static avl_node * +node_prev (avl_node * a) +{ + if (sub_left (a) != NULL) + return node_last (sub_left (a)); + { + avl_node *p; + + do + { + p = a; + a = p->up; + } + while (a != NULL && sub_left (a) == p); + return a; + } +} + +static avl_node * +node_find (const void *item, avl_tree t) +{ + avl_node *a = t->root; + avl_compare_func cmp = t->compare; + int c; + + while (a != NULL) + { + c = Item_Compare (cmp, t, item, get_item (a)); + CMPERR_CHECK__FIND (t->param); + if (c < 0) + a = a->sub[0]; + else if (c) + a = a->sub[1]; + else + break; + } + return a; +} + +#if 0==1 +static avl_node ** +avl_search (const void *item, avl_tree t, int *dir) +{ + if (t->root == NULL) + return &t->root; + { + avl_node **r = &t->root; + avl_node *a = *r; + avl_compare_func cmp = t->compare; + int c; + + while (1) + { + c = Item_Compare (cmp, t, item, get_item (a)); + if (!c) + break; + r = &a->sub[c = c > 0]; + if (*r == NULL) + { + *dir = c; + break; + } + a = *r; + } + + return r; + } +} +#endif + +static avl_size_t +get_index (avl_node * a) +{ + avl_size_t n = get_rank (a); + avl_node *p; + + while ((p = a->up) != NULL) + { + if (a != sub_left (p)) + n += get_rank (p); + a = p; + } + return n; +} + +/* Find item by index */ + +static avl_node * +node_find_index (avl_size_t idx, avl_tree t) +{ + avl_node *a = t->root; + int c; + + if (idx == 0 || idx > t->count) + return NULL; + if (idx == 1) + return node_first (a); + if (idx == t->count) + return node_last (a); + + while ((c = idx - get_rank (a)) != 0) + { + if (c < 0) + a = sub_left (a); + else + { + idx = c; + a = sub_right (a); + } + } + + return a; +} + +/* Rebalance starting from node [a] where a->sub[d_] + * is deeper post-insertion + */ + +static avl_code_t +rebalance_ins (avl_node * a, int dir, avl_tree t) +{ + if (a != NULL) + { + avl_node *p; + + while (1) + { + incr_rank (a, !dir); + if (get_bal (a)) + break; + set_skew (a, dir); + p = a->up; + if (p == NULL) + return 2; + dir = a != sub_left (p); + a = p; + } + + /* Now bal(a) == -1 or +1 */ + /* Rotate if need be */ + + if (0 == dir) + { + if (is_rskew (a)) + unset_rskew (a); + + else + { + avl_node *u = a->up; + avl_node **r = + u != NULL ? &u->sub[a != sub_left (u)] : &t->root; + + p = a; + + if (is_lskew (sub_left (p))) + { + /* rotR(p) */ + a = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + unset_lskew (p); + rbal (p) -= rzero (a); + } + else + { + /* rotLR(p) */ + a = sub_right (sub_left (p)); + sub_right (sub_left (p)) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = sub_left (p); + sub_left (p)->up = a; + sub_left (a) = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_lskew (p); + unset_rskew (sub_left (a)); + break; + case 1: /* left skew */ + unset_lskew (p); + set_rskew (p); + unset_rskew (sub_left (a)); + break; + case 2: /* right skew */ + unset_lskew (p); + unset_rskew (sub_left (a)); + set_lskew (sub_left (a)); + } /* switch */ + rbal (a) += rzero (sub_left (a)); + rbal (p) -= rzero (a); + } /* which rot */ + rbal (a) &= ~3; + a->up = u; + p->up = a; + *r = a; + } /* rot or no rot ? */ + } + else + { + /* direction == 1 */ + + if (is_lskew (a)) + unset_lskew (a); + + else + { + avl_node *u = a->up; + avl_node **r = + u != NULL ? &u->sub[a != sub_left (u)] : &t->root; + + p = a; + if (is_rskew (sub_right (p))) + { + /* rotL(p) */ + a = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + unset_rskew (p); + rbal (a) += rzero (p); + } + else + { + /* rotRL(p) */ + a = sub_left (sub_right (p)); + sub_left (sub_right (p)) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = sub_right (p); + sub_right (p)->up = a; + sub_right (a) = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_rskew (p); + unset_lskew (sub_right (a)); + break; + case 1: /* left skew */ + unset_rskew (p); + unset_lskew (sub_right (a)); + set_rskew (sub_right (a)); + break; + case 2: /* right skew */ + unset_rskew (p); + set_lskew (p); + unset_lskew (sub_right (a)); + } /* switch */ + rbal (sub_right (a)) -= rzero (a); + rbal (a) += rzero (p); + + } /* which rot */ + + rbal (a) &= ~3; + a->up = u; + p->up = a; + *r = a; + } /* rot or not rot ? */ + } /* if 0==dir */ + + /* The tree rooted at 'a' is now valid */ + /* Finish adjusting ranks */ + + while ((p = a->up) != NULL) + { + incr_rank (p, (a == sub_left (p))); + a = p; + } + + return 1; + + } /* if a != 0 */ + return 2; +} + +/* detach [p] : non-null */ + +/* only the linkage is tweaked */ + +static avl_code_t +rebalance_del (avl_node * p, avl_tree t, void **backup) +{ + avl_node **r, *a, *c; + int dir, bal; + + a = p->up; + if (a == NULL) + r = &t->root; + else + r = &a->sub[dir = p != sub_left (a)]; + + c = sub_right (p); + if (c == NULL && sub_left (p) == NULL) + *r = NULL; + else if (c == NULL || sub_left (p) == NULL) + { + *r = c != NULL ? c : sub_left (p); + (*r)->up = a; + } + else + { + if (sub_left (c) == NULL) + { + a = c; + dir = 1; + } + else + { + do + c = sub_left (c); + while (sub_left (c) != NULL); + a = c->up; + dir = 0; + sub_left (a) = sub_right (c); + if (sub_right (c) != NULL) + sub_right (c)->up = a; + sub_right (c) = sub_right (p); + sub_right (c)->up = c; + } + sub_left (c) = sub_left (p); + sub_left (c)->up = c; + c->up = p->up; + rbal (c) = rbal (p); + *r = c; + } + + backup_item (backup, p->item, t); + detach_node (p, t, NULL); + + /* Start backtracking : subtree of [a] in direction [dir] is less deep */ + + for (;; a = (*r)->up) + { + if (a == NULL) + return 2; + + decr_rank (a, !dir); + bal = get_bal (a); + + if (0 == dir) + { + if (bal == 0) + { + set_rskew (a); + break; + } + if (a->up == NULL) + r = &t->root; + else + { + dir = a != sub_left (a->up); + r = &a->up->sub[dir]; + } + if (bal & 1) + unset_lskew (a); + if (get_bal (a)) + { + p = a; + bal = get_bal (sub_right (p)); + if (!(bal & 1)) + { + /* bal = 0 or +1 */ + /* rotL(p) */ + a = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + if (bal) + { + unset_rskew (p); + unset_rskew (a); + } + else + set_lskew (a); + rbal (a) += rzero (p); + } + else + { + /* rotRL(p) */ + a = sub_left (sub_right (p)); + sub_left (sub_right (p)) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = sub_right (p); + sub_right (p)->up = a; + sub_right (a) = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_rskew (p); + unset_lskew (sub_right (a)); + break; + case 1: /* left skew */ + unset_rskew (p); + unset_lskew (sub_right (a)); + set_rskew (sub_right (a)); + break; + case 2: /* right skew */ + unset_rskew (p); + set_lskew (p); + unset_lskew (sub_right (a)); + } /* switch */ + rbal (a) &= ~3; + rbal (sub_right (a)) -= rzero (a); + rbal (a) += rzero (p); + + } /* which rot */ + + a->up = p->up; + p->up = a; + /* Done with rotation */ + *r = a; + if (bal == 0) + break; + } /* if getbal(a) */ + } + else + { + /* dir == 1 */ + + if (bal == 0) + { + set_lskew (a); + break; + } + if (a->up == NULL) + r = &t->root; + else + { + dir = a != sub_left (a->up); + r = &a->up->sub[dir]; + } + if (bal & 2) + unset_rskew (a); + if (get_bal (a)) + { + p = a; + bal = get_bal (sub_left (p)); + if (!(bal & 2)) + { + /* bal = 0 or -1 */ + /* rotR(p) */ + a = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + if (bal) + { + unset_lskew (p); + unset_lskew (a); + } + else + set_rskew (a); + rbal (p) -= rzero (a); + } + else + { + /* rotLR(p) */ + a = sub_right (sub_left (p)); + sub_right (sub_left (p)) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = sub_left (p); + sub_left (p)->up = a; + sub_left (a) = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_lskew (p); + unset_rskew (sub_left (a)); + break; + case 1: /* left skew */ + unset_lskew (p); + set_rskew (p); + unset_rskew (sub_left (a)); + break; + case 2: /* right skew */ + unset_lskew (p); + unset_rskew (sub_left (a)); + set_lskew (sub_left (a)); + } /* switch */ + rbal (a) &= ~3; + rbal (a) += rzero (sub_left (a)); + rbal (p) -= rzero (a); + } /* which rot */ + + a->up = p->up; + p->up = a; + /* Done with rotation */ + *r = a; + if (bal == 0) + break; + } /* if getbal(a) */ + } /* if dir==0 else 1 */ + } /* for */ + + /* Finish adjusting ranks */ + while ((p = a->up) != NULL) + { + decr_rank (p, (a == sub_left (p))); + a = p; + } + + return 1; +} + +void * +avl_first (avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return NULL; + return get_item (node_first (t->root)); +} + +void * +avl_last (avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return NULL; + return get_item (node_last (t->root)); +} + +void * +avl_find (const void *item, avl_tree t) +{ + avl_node *a; + +#ifndef AVL_NULLCHECKS + if (t == NULL) + return NULL; +#endif + a = node_find (item, t); + return a != NULL ? get_item (a) : NULL; +} + +/* + * Return smallest index i in [1:len] s.t. tree[i] matches [item], + * or zero if not found + */ + +avl_size_t +avl_index (const void *item, avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (item == NULL || t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return 0; + + { + avl_compare_func cmp = t->compare; + avl_node *a, *p; + avl_size_t idx = 0, n = 0; + int c; + + for (a = t->root;;) + { + c = Item_Compare (cmp, t, item, get_item (a)); + CMPERR_CHECK__INDEX (t->param); + if (!c) + idx = n + get_rank (a); + else if (c > 0) + n += get_rank (a); + p = a->sub[c > 0]; + if (p == NULL) + return idx; + a = p; + } + } +} + +/* (lo,hi) where + * lo smallest index s.t. t[lo] >= lo_item, or t->count+1 and + * hi greatest index s.t. t[hi] <= hi_item, or 0 + */ +avl_code_t +avl_span (const void *lo_item, + const void *hi_item, + avl_tree t, avl_size_t * lo_idx, avl_size_t * hi_idx) +{ + *lo_idx = t->count + 1; + *hi_idx = 0; + +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return -1; + + { + avl_compare_func cmp = t->compare; + avl_node *a; + avl_size_t n = 0; + int c; + + c = Item_Compare (cmp, t, lo_item, hi_item) > 0; + CMPERR_CHECK__SPAN (t->param); + if (c > 0) + { + const void *temp = lo_item; + + lo_item = hi_item; + hi_item = temp; + } + + a = t->root; + do + { + c = Item_Compare (cmp, t, lo_item, get_item (a)); + CMPERR_CHECK__SPAN (t->param); + if (c > 0) + { + n += get_rank (a); + a = sub_right (a); + } + else + { + *lo_idx = n + get_rank (a); + a = sub_left (a); + } + } + while (a); + + a = t->root; + do + { + c = Item_Compare (cmp, t, hi_item, get_item (a)); + CMPERR_CHECK__SPAN (t->param); + if (c < 0) + { + a = sub_left (a); + } + else + { + *hi_idx += get_rank (a); + a = sub_right (a); + } + } + while (a); + return 0; + } +} + +/* + * Find the smallest item in tree [t] that is GEQ the passed item + */ + +void * +avl_find_atleast (const void *item, avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return NULL; + { + avl_compare_func cmp = t->compare; + avl_node *a = t->root; + void *p = NULL; + int c; + + do + { + c = Item_Compare (cmp, t, item, get_item (a)); + CMPERR_CHECK__FIND (t->param); + if (c > 0) + { + a = sub_right (a); + } + else + { + p = get_item (a); + a = sub_left (a); + } + } + while (a); + return p; + } +} + +/* + * Find the greatest item in tree [t] that is LEQ the passed item + */ + +void * +avl_find_atmost (const void *item, avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return NULL; + { + avl_compare_func cmp = t->compare; + avl_node *a = t->root; + void *p = NULL; + int c; + + do + { + c = Item_Compare (cmp, t, item, get_item (a)); + CMPERR_CHECK__FIND (t->param); + if (c < 0) + { + a = sub_left (a); + } + else + { + p = get_item (a); + a = sub_right (a); + } + } + while (a); + return p; + } +} + +/* Retrieve item of index [idx] in tree [t] */ + +void * +avl_find_index (avl_size_t idx, avl_tree t) +{ + avl_node *a; + +#ifndef AVL_NULLCHECKS + if (t == NULL) + return NULL; +#endif + a = node_find_index (idx, t); + return a != NULL ? get_item (a) : NULL; +} + +#define attach_node(ptr,up,t)\ + ptr = new_node(item, up, t);\ + if (ptr == NULL){\ + AVL_SHOW_ERROR("%s\n", "couldn't allocate node");\ + return -1;\ + }\ + t->count++ + +/* Iterative insertion */ + +avl_code_t +avl_ins (void *item, avl_tree t, avl_bool_t allow_duplicates) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL) + return NULL; + { +#endif + avl_compare_func cmp = t->compare; + avl_node **r, *a; + int dir; + + for (r = &t->root, a = NULL; *r != NULL; r = &a->sub[dir = dir > 0]) + { + a = *r; + dir = Item_Compare (cmp, t, item, get_item (a)); + CMPERR_CHECK__INS (t->param); + if (!dir && !allow_duplicates) + return 0; + } + + attach_node (*r, a, t); + + return rebalance_ins (a, dir, t); + +#ifndef AVL_NULLCHECKS + } /* end if non-empty tree */ +#endif +} + +avl_code_t +avl_del (void *item, avl_tree t, void **backup) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return 0; + { + avl_node *a = node_find (item, t); + + if (a == NULL) + return CMPERR_CHECK__DEL (t->param); + return rebalance_del (a, t, backup); + } +} + +/* helper function */ +static avl_code_t +node_del_first (avl_tree t, struct ptr_handler *h) +{ + avl_node *p, *a, *c; + int bal; + + p = node_first (t->root); + a = p->up; + if (sub_right (p) != NULL) + sub_right (p)->up = a; + if (a == NULL) + t->root = sub_right (p); + else + sub_left (a) = sub_right (p); + + detach_node (p, t, h); + + /* Start backtracking : subtree of [a] in direction [0] is less deep */ + + for (;; a = c) + { + if (a == NULL) + return 2; + + decr_rank (a, 1); + bal = get_bal (a); + + if (bal == 0) + { + set_rskew (a); + break; + } + if (bal & 1) + unset_lskew (a); + c = a->up; + if (get_bal (a)) + { + p = a; + bal = get_bal (sub_right (p)); + if (!(bal & 1)) + { + /* bal = 0 or +1 */ + /* rotL(p) */ + a = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + if (bal) + { + unset_rskew (p); + unset_rskew (a); + } + else + set_lskew (a); + rbal (a) += rzero (p); + } + else + { + /* rotRL(p) */ + a = sub_left (sub_right (p)); + sub_left (sub_right (p)) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = sub_right (p); + sub_right (p)->up = a; + sub_right (a) = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_rskew (p); + unset_lskew (sub_right (a)); + break; + case 1: /* left skew */ + unset_rskew (p); + unset_lskew (sub_right (a)); + set_rskew (sub_right (a)); + break; + case 2: /* right skew */ + unset_rskew (p); + set_lskew (p); + unset_lskew (sub_right (a)); + } /* switch */ + rbal (a) &= ~3; + rbal (sub_right (a)) -= rzero (a); + rbal (a) += rzero (p); + } /* which rot */ + + a->up = p->up; + p->up = a; + /* Done with rotation */ + if (c != NULL) + sub_left (c) = a; + else + t->root = a; + if (bal == 0) + break; + } /* if getbal(a) */ + } /* for */ + + /* Finish adjusting ranks */ + while ((a = a->up) != NULL) + { + decr_rank (a, 1); + } + + return 1; +} + +/* helper function */ +static avl_code_t +node_del_last (avl_tree t, struct ptr_handler *h) +{ + + avl_node *p, *a, *c; + int bal; + + p = node_last (t->root); + a = p->up; + if (sub_left (p) != NULL) + sub_left (p)->up = a; + if (a == NULL) + t->root = sub_left (p); + else + sub_right (a) = sub_left (p); + + detach_node (p, t, h); + + /* Start backtracking : subtree of [a] in direction [1] is less deep */ + + for (;; a = c) + { + if (a == NULL) + return 2; + + bal = get_bal (a); + if (bal == 0) + { + set_lskew (a); + break; + } + if (bal & 2) + unset_rskew (a); + c = a->up; + if (get_bal (a)) + { + p = a; + bal = get_bal (sub_left (p)); + if (!(bal & 2)) + { + /* bal = 0 or -1 */ + /* rotR(p) */ + a = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + if (bal) + { + unset_lskew (p); + unset_lskew (a); + } + else + set_rskew (a); + rbal (p) -= rzero (a); + } + else + { + /* rotLR(p) */ + a = sub_right (sub_left (p)); + sub_right (sub_left (p)) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = sub_left (p); + sub_left (p)->up = a; + sub_left (a) = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_lskew (p); + unset_rskew (sub_left (a)); + break; + case 1: /* left skew */ + unset_lskew (p); + set_rskew (p); + unset_rskew (sub_left (a)); + break; + case 2: /* right skew */ + unset_lskew (p); + unset_rskew (sub_left (a)); + set_lskew (sub_left (a)); + } /* switch */ + rbal (a) &= ~3; + rbal (a) += rzero (sub_left (a)); + rbal (p) -= rzero (a); + } /* which rot */ + + a->up = p->up; + p->up = a; + /* Done with rotation */ + if (c != NULL) + sub_right (c) = a; + else + t->root = a; + if (bal == 0) + break; + } /* if getbal(a) */ + } /* for */ + + return 1; +} + +/* [p] : juncture node (zeroed out) */ + +/* [n] : rank of [p] in resulting tree */ + +/* [delta] = depth_1 - depth_0 */ + +static avl_code_t +join_left (avl_node * p, avl_node ** r0, avl_node * r1, int delta, int n) +{ + avl_node *a = NULL, **r = r0; + + if (r1 == NULL) + { + while (*r != NULL) + { + a = *r; + n -= get_rank (a); + r = &sub_right (a); + } + } + else + { + while (delta < -1) + { + a = *r; + delta += is_lskew (a) + 1; + n -= get_rank (a); + r = &sub_right (a); + } + r1->up = p; + if (*r != NULL) + (*r)->up = p; + if (delta) + set_lskew (p); + } + + /* at this point bal(*r) = -1 or 0 */ + sub_left (p) = *r; + sub_right (p) = r1; + p->up = a; + set_rank (p, n); + *r = p; + + for (;;) + { + if (a == NULL) + return 2; + if (get_bal (a)) + break; + set_rskew (a); + a = a->up; + } + + /* Rotate if need be */ + /* No (+2,0) rotation to do */ + + if (is_lskew (a)) + unset_lskew (a); + + else + { + avl_node *p = a; + + if (is_rskew (sub_right (p))) + { + /* rotL(p) */ + a = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + unset_rskew (p); + rbal (a) += rzero (p); + } + else + { + /* rotRL(p) */ + a = sub_left (sub_right (p)); + sub_left (sub_right (p)) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = sub_right (p); + sub_right (p)->up = a; + sub_right (a) = sub_right (p); + sub_right (p) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = p; + sub_left (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_rskew (p); + unset_lskew (sub_right (a)); + break; + case 1: /* left skew */ + unset_rskew (p); + unset_lskew (sub_right (a)); + set_rskew (sub_right (a)); + break; + case 2: /* right skew */ + unset_rskew (p); + set_lskew (p); + unset_lskew (sub_right (a)); + } /* switch */ + rbal (sub_right (a)) -= rzero (a); + rbal (a) += rzero (p); + } /* which rot */ + + rbal (a) &= ~3; + a->up = p->up; + p->up = a; + if (a->up != NULL) + sub_right (a->up) = a; + else + *r0 = a; + } /* rot or not rot */ + + return 1; +} + +/* [p] : juncture node */ + +/* [n] : rank of [p] in resulting tree */ + +static avl_code_t +join_right (avl_node * p, avl_node * r0, avl_node ** r1, int delta, int n) +{ + avl_node *a = NULL, **r = r1; + + if (r0 == NULL) + { + while (*r != NULL) + { + a = *r; + incr_rank (a, n); + r = &sub_left (a); + } + n = 1; + } + else + { + while (delta > +1) + { + a = *r; + delta -= is_rskew (a) + 1; + incr_rank (a, n); + r = &sub_left (a); + } + r0->up = p; + if (*r != NULL) + (*r)->up = p; + if (delta) + set_rskew (p); + } + + /* at this point bal(*r) = +1 or 0 */ + sub_left (p) = r0; + sub_right (p) = *r; + set_rank (p, n); + p->up = a; + *r = p; + + for (;;) + { + if (a == NULL) + return 2; + if (get_bal (a)) + break; + set_lskew (a); + a = a->up; + } + + /* Rotate if need be */ + /* No (-2,0) rotation to do */ + + if (is_rskew (a)) + unset_rskew (a); + + else + { + avl_node *p = a; + + if (is_lskew (sub_left (p))) + { + /* rotR(p) */ + a = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + unset_lskew (p); + rbal (p) -= rzero (a); + } + else + { + /* rotLR(p) */ + a = sub_right (sub_left (p)); + sub_right (sub_left (p)) = sub_left (a); + if (sub_left (a) != NULL) + sub_left (a)->up = sub_left (p); + sub_left (p)->up = a; + sub_left (a) = sub_left (p); + sub_left (p) = sub_right (a); + if (sub_right (a) != NULL) + sub_right (a)->up = p; + sub_right (a) = p; + switch (get_bal (a)) + { + case 0: /* not skewed */ + unset_lskew (p); + unset_rskew (sub_left (a)); + break; + case 1: /* left skew */ + unset_lskew (p); + set_rskew (p); + unset_rskew (sub_left (a)); + break; + case 2: /* right skew */ + unset_lskew (p); + unset_rskew (sub_left (a)); + set_lskew (sub_left (a)); + } /* end switch */ + rbal (a) += rzero (sub_left (a)); + rbal (p) -= rzero (a); + } /* end which rot */ + + rbal (a) &= ~3; + a->up = p->up; + p->up = a; + if (a->up != NULL) + sub_left (a->up) = a; + else + *r1 = a; + } /* end rot or not rot */ + + return 1; +} + +avl_code_t +avl_del_first (avl_tree t, void **backup) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return 0; + { + avl_code_t rv; + + if (backup == NULL) + { + rv = node_del_first (t, NULL); + } + else + { + ini_ptr_handler (h, BACKUP); + rv = node_del_first (t, &h); + *backup = h.ptr; + } + return rv; + } +} + +avl_code_t +avl_del_last (avl_tree t, void **backup) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return 0; + { + avl_code_t rv; + + if (backup == NULL) + { + rv = node_del_last (t, NULL); + } + else + { + ini_ptr_handler (h, BACKUP); + rv = node_del_last (t, &h); + *backup = h.ptr; + } + return rv; + } +} + +avl_code_t +avl_ins_index (void *item, avl_size_t idx, avl_tree t) +{ + avl_node *p; + + if (idx == 0 || t == NULL || idx > t->count + 1) + return 0; + + attach_node (p, NULL, t); + /* Note: 'attach_node' macro increments t->count */ + + if (idx == 1) + { + return join_right (p, (avl_node *) NULL, &t->root, /*delta= */ 0, 1); + } + else if (idx == t->count) + { + return + join_left (p, &t->root, (avl_node *) NULL, /*delta= */ 0, t->count); + } + else + { + avl_node *a = node_find_index (idx - 1, t); + int dir; + + if (sub_right (a) != NULL) + { + a = node_first (sub_right (a)); + sub_left (a) = p; + dir = 0; + } + else + { + sub_right (a) = p; + dir = 1; + } + + p->up = a; + return rebalance_ins (a, dir, t); + } +} + +avl_code_t +avl_del_index (avl_size_t idx, avl_tree t, void **backup) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL) + return 0; +#endif + + if (idx == 0 || idx > t->count) + return 0; + if (idx == 1) + return avl_del_first (t, backup); + if (idx == t->count) + return avl_del_last (t, backup); + { + avl_node *a = node_find_index (idx, t); + + return rebalance_del (a, t, backup); + } +} + +/* + * Outcome: [t0] handles the concatenation of [t0] and [t1] + */ + +void +avl_cat (avl_tree t0, avl_tree t1) +{ +#ifndef AVL_NULLCHECKS + if (t0 == NULL || t1 == NULL || t1->root == NULL) +#else + if (t1->root == NULL) +#endif + return; + + if (t0->root == NULL) + { + t0->root = t1->root; + t0->count = t1->count; + t1->root = NULL; + t1->count = 0; + + } + else + { + int delta = depth (t1->root) - depth (t0->root); + + ini_ptr_handler (h, DETACH); + + if (delta <= 0) + { + if (node_del_first (t1, &h) == 2) + --delta; + (void) join_left ((avl_node *) h.ptr, &t0->root, t1->root, delta, + t0->count + 1); + } + else + { + if (node_del_last (t0, &h) == 2) + ++delta; + (void) join_right ((avl_node *) h.ptr, t0->root, &t1->root, delta, + t0->count + 1); + t0->root = t1->root; + } + + t1->root = NULL; + t0->count += t1->count + 1; + t1->count = 0; + } +} + +/* + * - [t0] and [t1] are existing handles + * - See Donald Knuth, TAOCP Vol.3 "Sorting and searching" + */ + +avl_code_t +avl_split (const void *item, avl_tree t, avl_tree t0, avl_tree t1) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif /* AVL_NULLCHECKS */ + return 0; + + t0->root = NULL; + t1->root = NULL; + t0->count = 0; + t1->count = 0; + + { + avl_compare_func cmp = t->compare; + avl_node *a, *p, *sn; /* sn: split node */ + int d_, k, na, an[AVL_STACK_CAPACITY]; + + /* invariant: [na]= size of tree rooted at [a] plus one */ + + for (a = t->root, na = t->count + 1, k = 0;;) + { + d_ = Item_Compare (cmp, t, item, get_item (a)); + CMPERR_CHECK__SPLIT (t->param); + if (!d_) + break; + p = a->sub[d_ = d_ > 0]; + if (p == NULL) + return 0; + an[k++] = na; + if (d_) + na -= get_rank (a); + else + na = get_rank (a); + a = p; + } + + /* record split node */ + sn = a; + + if (k == 0) + { + t0->root = sub_left (a); + t1->root = sub_right (a); + if (t0->root != NULL) + t0->root->up = NULL; + if (t1->root != NULL) + t1->root->up = NULL; + t0->count = get_rank (a) - 1; + t1->count = t->count - get_rank (a); + } + else + { + avl_node *r[2], *rr; + int h[2], ha, hh; + avl_size_t n[2], nn; + + r[0] = sub_left (a); + r[1] = sub_right (a); + if (r[0] != NULL) + r[0]->up = NULL; + if (r[1] != NULL) + r[1]->up = NULL; + ha = depth (a); + h[0] = ha - (is_rskew (a) ? 2 : 1); + h[1] = ha - (is_lskew (a) ? 2 : 1); + n[0] = get_rank (a); /* size of r[0] plus one */ + n[1] = na - n[0]; /* size of r[1] plus one */ + + for (p = a->up, d_ = a != sub_left (p);;) + { + + a = p; /* a: juncture node */ + p = a->up; + + if (d_ == 0) + { + hh = h[1]; + ha += (is_rskew (a) ? 2 : 1); + h[1] = ha - (is_lskew (a) ? 2 : 1); + nn = n[1]; + n[1] += an[k - 1] - get_rank (a); + if (p != NULL) + d_ = a != sub_left (p); + rbal (a) = 0; + + if (h[1] >= hh) + { + rr = r[1]; + r[1] = sub_right (a); + if (r[1] != NULL) + r[1]->up = NULL; + h[1] += (2 == join_right (a, rr, r + 1, h[1] - hh, nn)); + } + else + { + h[1] = + hh + (2 == + join_left (a, r + 1, sub_right (a), h[1] - hh, + nn)); + } + } + else + { + hh = h[0]; + ha += (is_lskew (a) ? 2 : 1); + h[0] = ha - (is_rskew (a) ? 2 : 1); + nn = get_rank (a); + n[0] += nn; + if (p != NULL) + d_ = a != sub_left (p); + rbal (a) = 0; + + if (h[0] >= hh) + { + rr = r[0]; + r[0] = sub_left (a); + if (r[0] != NULL) + r[0]->up = NULL; + h[0] += (2 == join_left (a, r, rr, hh - h[0], nn)); + } + else + { + h[0] = + hh + (2 == + join_right (a, sub_left (a), r, hh - h[0], nn)); + } + } + + if (--k == 0) + break; + } /* for p */ + + t0->root = r[0]; + t1->root = r[1]; + t0->count = n[0] - 1; + t1->count = n[1] - 1; + } /* if k==0 */ + + /* Detach split node */ + detach_node (sn, t, NULL); + t->root = NULL; + t->count = 0; + + return 1; + } +} + +/* Inorder traversal */ + +void +avl_walk (avl_tree t, avl_item_func proc, void *param) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL || t->root == NULL) +#else + if (t->root == NULL) +#endif + return; + + { + avl_node *a = t->root, *p; + + while (1) + { + while (sub_left (a) != NULL) + a = sub_left (a); + + while (1) + { + (*proc) (get_item (a), param); + if (sub_right (a) != NULL) + break; + do + { + p = a; + a = p->up; + if (a == NULL) + return; + } + while (p != sub_left (a)); + } + a = sub_right (a); + } + } +} + +/* recursive helper for 'avl_slice' */ +static int +node_slice (avl_node ** root, avl_node ** cur, avl_tree tree, avl_size_t len) +{ + avl_size_t mid = len / 2; + + if (mid == 0) + { + if ((*root = new_node ((*cur)->item, /*parent */ NULL, tree)) == NULL) + return -1; + sub_left (*root) = NULL; + sub_right (*root) = NULL; + rbal (*root) = 4; + *cur = node_next (*cur); + return 0; + + } + else if ((*root = new_node (NULL, /*parent */ NULL, tree)) == NULL) + { + return -1; + } + else + { + avl_node *p = *root; + int h0, h1 = -1; + + rbal (p) = (mid + 1) << 2; + + if ((h0 = node_slice (&sub_left (p), cur, tree, mid)) < 0) + return -1; + + p->item = (*tree->copy) ((*cur)->item); + sub_left (p)->up = p; + + *cur = node_next (*cur); + + if (len -= mid + 1) + { + if ((h1 = node_slice (&sub_right (p), cur, tree, len)) < 0) + return -1; + sub_right (p)->up = p; + } + + if (h0 > h1) + set_lskew (p); + else if (h0 < h1) + { + set_rskew (p); + return 1 + h1; + } + return 1 + h0; + } +} + +/* Return a slice t[lo,hi) as a new tree */ + +avl_tree +avl_slice (avl_tree t, avl_size_t lo_idx, avl_size_t hi_idx, void *param) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL) + return NULL; +#endif /* AVL_NULLCHECKS */ + + if (lo_idx > hi_idx || lo_idx > t->count) + return NULL; + if (lo_idx < 1) + lo_idx = 1; + if (hi_idx > t->count + 1) + hi_idx = t->count + 1; + + { + avl_tree tt = avl_create (t->compare, + t->copy, + t->dispose, + t->alloc, + t->dealloc, + param); + + if (tt == NULL) + { + AVL_SHOW_ERROR ("%s\n", + "couldn't allocate new handle in avl_slice()"); + return NULL; + } + + if (lo_idx < hi_idx) + { + avl_node *cur = node_find_index (lo_idx, t); + + if (node_slice (&tt->root, &cur, t, tt->count = hi_idx - lo_idx) < 0) + { + AVL_SHOW_ERROR ("%s\n", "couldn't allocate node in avl_slice()"); + node_empty (tt); + (*t->dealloc) (tt); + return NULL; + } + tt->root->up = NULL; + } + return tt; + } +} + +/* recursive helper for 'avl_xload' */ + +static int +node_load (avl_node ** root, avl_itersource cur, void **pres, avl_tree desc, + avl_size_t len) +{ + avl_size_t mid = len / 2; + + if (mid == 0) + { + if (0 != (*cur->f) (cur, pres) + || (*root = new_node (*pres, /*parent */ NULL, desc)) == NULL) + return -1; + sub_left (*root) = NULL; + sub_right (*root) = NULL; + rbal (*root) = 4; + return 0; + + } + else if ((*root = new_node (NULL, /*parent */ NULL, desc)) == NULL) + { + return -1; + } + else + { + avl_node *p = *root; + int h0, h1 = -1; + + rbal (p) = (mid + 1) << 2; + + if ((h0 = node_load (&sub_left (p), cur, pres, desc, mid)) < 0) + return -1; + + if (0 != (*cur->f) (cur, pres)) + return -1; + + p->item = (*desc->copy) (*pres); + sub_left (p)->up = p; + + if (len -= mid + 1) + { + if ((h1 = node_load (&sub_right (p), cur, pres, desc, len)) < 0) + return -1; + sub_right (p)->up = p; + } + + if (h0 > h1) + set_lskew (p); + else if (h0 < h1) + { + set_rskew (p); + return 1 + h1; + } + return 1 + h0; + } +} + +/* Load 'len' items from itersource */ + +avl_tree +avl_xload (avl_itersource src, void **pres, avl_size_t len, avl_config conf, + void *tree_param) +{ +#ifndef AVL_NULLCHECKS + if (src == NULL) + return NULL; + { +#endif /* AVL_NULLCHECKS */ + + avl_tree tt = avl_create (conf->compare, + conf->copy, + conf->dispose, + conf->alloc, + conf->dealloc, + tree_param); + + if (tt == NULL) + { + AVL_SHOW_ERROR ("%s\n", "couldn't allocate new handle in avl_load()"); + return NULL; + } + + if (len) + { + if (node_load (&tt->root, src, pres, tt, tt->count = len) < 0) + { + AVL_SHOW_ERROR ("%s\n", "couldn't allocate node in avl_load()"); + node_empty (tt); + (*tt->dealloc) (tt); + return NULL; + } + tt->root->up = NULL; + } + return tt; +#ifndef AVL_NULLCHECKS + } +#endif +} + +#ifdef HAVE_AVL_VERIFY + +/* Verification routine */ +typedef enum +{ + okay = 0, + bad_parent = 1, + bad_rank = 2, + out_of_balance = 3, + out_of_order = 4, + diff_mismatch = 5, + count_mismatch = 6 +} +avl_verify_code; + +static avl_bool_t +avl_error (avl_verify_code err) +{ + static char *errmess[] = { + "Bad parent link", + "Rank error", + "Out of balance", + "Out of order", + "Differential mismatch", + "Count mismatch" + }; + + AVL_SHOW_ERROR ("Invalid avl_tree: %s\n", errmess[err - 1]); + return avl_false; +} + +static int bals[] = { 1, 0, 2 }; + +/* + helper for recursive 'avl_verify' function + return 0 iff okay + */ + +static avl_verify_code +node_verify (avl_node * root, avl_tree tree, int *h, avl_size_t * c, + avl_node * up) +{ + avl_verify_code err = okay; + + if (root == NULL) + *h = AVL_MIN_DEPTH, *c = 0; + else + { +#define AVL_ASSERT(expr,n) if (expr) ; else { err = n; break; } +#define CHECK(err) if (err) break + + avl_node *left, *right; + avl_size_t c_[2]; + int h_[2], delta; + + left = sub_left (root); + right = sub_right (root); + do + { + AVL_ASSERT (root->up == up, bad_parent); + CHECK (err = node_verify (left, tree, h_, c_, root)); + AVL_ASSERT (get_rank (root) == *c_ + 1, bad_rank); + CHECK (err = node_verify (right, tree, h_ + 1, c_ + 1, root)); + delta = h_[1] - h_[0]; + AVL_ASSERT (delta >= -1 && delta <= +1, out_of_balance); + AVL_ASSERT (get_bal (root) == bals[delta + 1], diff_mismatch); + AVL_ASSERT (left == NULL + || (Item_Compare (tree->compare, tree, get_item (left), + get_item (root)) <= + 0 CMPERR_CHECK__VERIFY (tree->param)), + out_of_order); + AVL_ASSERT (right == NULL + || + (Item_Compare + (tree->compare, tree, get_item (root), + get_item (right)) <= + 0 CMPERR_CHECK__VERIFY (tree->param)), out_of_order); + *h = 1 + (h_[0] > h_[1] ? h_[0] : h_[1]); + *c = 1 + c_[0] + c_[1]; + } + while (0); + } + return err; +} + +avl_bool_t +avl_verify (avl_tree t) +{ +#ifndef AVL_NULLCHECKS + if (t == NULL) + return avl_false; +#endif /* AVL_NULLCHECKS */ + { + int h; + avl_size_t c; + avl_verify_code err; + + err = node_verify (t->root, t, &h, &c, (avl_node *) NULL); + if (err) + return avl_error (err); + if (c != t->count) + return avl_error (count_mismatch); + return avl_true; + } +} +#endif /* HAVE_AVL_VERIFY */ + +/**************** + * * + * ITERATORS * + * * + ****************/ + +typedef enum +{ + AVL_ITERATOR_PRE, + AVL_ITERATOR_POST, + AVL_ITERATOR_INTREE +} +avl_status_t; + +struct avl_iterator_ +{ + avl_node *pos; + avl_tree tree; + avl_status_t status; +}; + +#define get_root(i) i->tree->root +#define is_pre(i) i->status == AVL_ITERATOR_PRE +#define is_post(i) i->status == AVL_ITERATOR_POST +#define set_pre_iterator(i) i->status = AVL_ITERATOR_PRE +#define set_post_iterator(i) i->status = AVL_ITERATOR_POST +#define set_in_iterator(i) i->status = AVL_ITERATOR_INTREE + +/* Position existing iterator [iter] at node matching [item] in its own tree, + * if it exists ; otherwise do nothing + */ + +void +avl_iterator_seek (const void *item, avl_iterator iter) +{ + avl_node *p = node_find (item, iter->tree); + + if (p != NULL) + { + set_in_iterator (iter); + iter->pos = p; + } +} + +void +avl_iterator_seek_index (avl_size_t idx, avl_iterator iter) +{ + avl_node *p = node_find_index (idx, iter->tree); + + if (p != NULL) + { + set_in_iterator (iter); + iter->pos = p; + } +} + +/* Return item pointer at current position */ + +void * +avl_iterator_cur (avl_iterator iter) +{ + return iter->pos != NULL ? get_item (iter->pos) : NULL; +} + +avl_size_t +avl_iterator_count (avl_iterator iter) +{ + return iter->tree->count; +} + +avl_size_t +avl_iterator_index (avl_iterator iter) +{ + if (iter->pos != NULL) + return get_index (iter->pos); + else if (is_pre (iter)) + return 0; + else + return iter->tree->count + 1; +} + +/* Rustic: */ + +avl_iterator +avl_iterator_new (avl_tree t, avl_ini_t ini, ...) +{ + va_list args; + avl_iterator iter = NULL; + + va_start (args, ini); + + if (t == NULL) + goto finish; + + if ((iter = (*t->alloc) (sizeof (struct avl_iterator_))) == NULL) + { + AVL_SHOW_ERROR ("%s\n", "couldn't create iterator"); + goto finish; + } + + iter->pos = NULL; + iter->tree = t; + + if (ini != AVL_ITERATOR_INI_INTREE) + { + iter->status = + (ini == AVL_ITERATOR_INI_PRE) ? AVL_ITERATOR_PRE : AVL_ITERATOR_POST; + } + else + { + const void *item = NULL; + + item = va_arg (args, const void *); + + set_pre_iterator (iter); + + if (item == NULL) + AVL_SHOW_ERROR ("%s\n", "missing argument to avl_iterator_new()"); + else + avl_iterator_seek (item, iter); + } + +finish: + va_end (args); + return iter; +} + +/* + * The following used to write to memory after it was freed. + * Corrected by: David Turner <novalis@openplans.org> + */ +void +avl_iterator_kill (avl_iterator iter) +{ + if (iter != NULL) + { + avl_dealloc_func dealloc = iter->tree->dealloc; + iter->pos = NULL; + iter->tree = NULL; + (*dealloc) (iter); + } +} + +void * +avl_iterator_next (avl_iterator iter) +{ + avl_node *a = iter->pos; + + if (is_post (iter)) + return NULL; + + if (is_pre (iter)) + { + a = get_root (iter); + if (a != NULL) + { + a = node_first (a); + set_in_iterator (iter); + } + } + else + { + a = node_next (a); + if (a == NULL) + set_post_iterator (iter); + } + + iter->pos = a; + return a != NULL ? get_item (a) : NULL; +} + +void * +avl_iterator_prev (avl_iterator iter) +{ + avl_node *a = iter->pos; + + if (is_pre (iter)) + return NULL; + + if (is_post (iter)) + { + a = get_root (iter); + if (a != NULL) + { + a = node_last (a); + set_in_iterator (iter); + } + } + else + { + a = node_prev (a); + if (a == NULL) + set_pre_iterator (iter); + } + + iter->pos = a; + return a != NULL ? get_item (a) : NULL; +} + +/* Remove node at current position */ + +/* Move cursor to next position */ + +avl_code_t +avl_iterator_del (avl_iterator iter, void **backup) +{ + if (iter == NULL || iter->pos == NULL) + return 0; + { + avl_node *a = iter->pos, *p; + + p = node_next (a); + if (p == NULL) + set_post_iterator (iter); + iter->pos = p; + return rebalance_del (a, iter->tree, backup); + } +} |