/* 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 const void * avl_default_item_copy (const void *item) { return (const void *) item; } void * avl_default_item_dispose (void *item) { (void)item; /* for -Wall */ 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 = (int)(idx - get_rank (a))) != 0) { if (c < 0) a = sub_left (a); else { idx = (avl_size_t)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, (rbal_t)(!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, (rbal_t)(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; rbal_t bal; int dir = 0; 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, (rbal_t)(!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, (rbal_t)(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 = 0; 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; rbal_t 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; rbal_t 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 -= (int)get_rank (a); r = &sub_right (a); } } else { while (delta < -1) { a = *r; delta += (int)(is_lskew (a) + 1); n -= (int)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, (rbal_t)n); r = &sub_left (a); } n = 1; } else { while (delta > +1) { a = *r; delta -= (int)(is_rskew (a) + 1); incr_rank (a, (rbal_t)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, (int)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, (int)(t0->count + 1)); } else { if (node_del_last (t0, &h) == 2) ++delta; (void) join_right ((avl_node *) h.ptr, t0->root, &t1->root, delta, (int)(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 = (int)(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 -= (int)get_rank (a); else na = (int)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] = (avl_size_t)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] += (avl_size_t)(an[k - 1] - (int)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, (int)nn)); } else { h[1] = hh + (2 == join_left (a, r + 1, sub_right (a), h[1] - hh, (int)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], (int)nn)); } else { h[0] = hh + (2 == join_right (a, sub_left (a), r, hh - h[0], (int)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 */ 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); } }