diff options
Diffstat (limited to 'lib/libshout/src/common/avl/avl.c')
-rw-r--r-- | lib/libshout/src/common/avl/avl.c | 1194 |
1 files changed, 1194 insertions, 0 deletions
diff --git a/lib/libshout/src/common/avl/avl.c b/lib/libshout/src/common/avl/avl.c new file mode 100644 index 0000000000..5653440e01 --- /dev/null +++ b/lib/libshout/src/common/avl/avl.c @@ -0,0 +1,1194 @@ +/* + * Copyright (C) 1995-1997 by Sam Rushing <rushing@nightmare.com> + * + * All Rights Reserved + * + * Permission to use, copy, modify, and distribute this software and + * its documentation for any purpose and without fee is hereby + * granted, provided that the above copyright notice appear in all + * copies and that both that copyright notice and this permission + * notice appear in supporting documentation, and that the name of Sam + * Rushing not be used in advertising or publicity pertaining to + * distribution of the software without specific, written prior + * permission. + * + * SAM RUSHING DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN + * NO EVENT SHALL SAM RUSHING BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS + * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, + * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +/* $Id: avl.c,v 1.11 2004/01/27 02:16:25 karl Exp $ */ + +/* + * This is a fairly straightfoward translation of a prototype + * written in python, 'avl_tree.py'. Read that file first. + */ + +#ifdef HAVE_CONFIG_H + #include <config.h> +#endif + +#include <stdio.h> +#include <stdlib.h> + +#include "avl.h" + +avl_node * +avl_node_new (void * key, + avl_node * parent) +{ + avl_node * node = (avl_node *) malloc (sizeof (avl_node)); + + if (!node) { + return NULL; + } else { + node->parent = parent; + node->key = key; + node->left = NULL; + node->right = NULL; + node->rank_and_balance = 0; + AVL_SET_BALANCE (node, 0); + AVL_SET_RANK (node, 1); +#ifdef HAVE_AVL_NODE_LOCK + thread_rwlock_create(&node->rwlock); +#endif + return node; + } +} + +avl_tree * +avl_tree_new (avl_key_compare_fun_type compare_fun, + void * compare_arg) +{ + avl_tree * t = (avl_tree *) malloc (sizeof (avl_tree)); + + if (!t) { + return NULL; + } else { + avl_node * root = avl_node_new((void *)NULL, (avl_node *) NULL); + if (!root) { + free (t); + return NULL; + } else { + t->root = root; + t->height = 0; + t->length = 0; + t->compare_fun = compare_fun; + t->compare_arg = compare_arg; + thread_rwlock_create(&t->rwlock); + return t; + } + } +} + +static void +avl_tree_free_helper (avl_node * node, avl_free_key_fun_type free_key_fun) +{ + if (node->left) { + avl_tree_free_helper (node->left, free_key_fun); + } + if (free_key_fun) + free_key_fun (node->key); + if (node->right) { + avl_tree_free_helper (node->right, free_key_fun); + } +#ifdef HAVE_AVL_NODE_LOCK + thread_rwlock_destroy (&node->rwlock); +#endif + free (node); +} + +void +avl_tree_free (avl_tree * tree, avl_free_key_fun_type free_key_fun) +{ + if (tree->length) { + avl_tree_free_helper (tree->root->right, free_key_fun); + } + if (tree->root) { +#ifdef HAVE_AVL_NODE_LOCK + thread_rwlock_destroy(&tree->root->rwlock); +#endif + free (tree->root); + } + thread_rwlock_destroy(&tree->rwlock); + free (tree); +} + +int +avl_insert (avl_tree * ob, + void * key) +{ + if (!(ob->root->right)) { + avl_node * node = avl_node_new (key, ob->root); + if (!node) { + return -1; + } else { + ob->root->right = node; + ob->length = ob->length + 1; + return 0; + } + } else { /* not self.right == None */ + avl_node *t, *p, *s, *q, *r; + int a; + + t = ob->root; + s = p = t->right; + + while (1) { + if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) { + /* move left */ + AVL_SET_RANK (p, (AVL_GET_RANK (p) + 1)); + q = p->left; + if (!q) { + /* insert */ + avl_node * q_node = avl_node_new (key, p); + if (!q_node) { + return (-1); + } else { + q = q_node; + p->left = q; + break; + } + } else if (AVL_GET_BALANCE(q)) { + t = p; + s = q; + } + p = q; + } else { + /* move right */ + q = p->right; + if (!q) { + /* insert */ + avl_node * q_node = avl_node_new (key, p); + if (!q_node) { + return -1; + } else { + q = q_node; + p->right = q; + break; + } + } else if (AVL_GET_BALANCE(q)) { + t = p; + s = q; + } + p = q; + } + } + + ob->length = ob->length + 1; + + /* adjust balance factors */ + if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) { + r = p = s->left; + } else { + r = p = s->right; + } + while (p != q) { + if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) { + AVL_SET_BALANCE (p, -1); + p = p->left; + } else { + AVL_SET_BALANCE (p, +1); + p = p->right; + } + } + + /* balancing act */ + + if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) { + a = -1; + } else { + a = +1; + } + + if (AVL_GET_BALANCE (s) == 0) { + AVL_SET_BALANCE (s, a); + ob->height = ob->height + 1; + return 0; + } else if (AVL_GET_BALANCE (s) == -a) { + AVL_SET_BALANCE (s, 0); + return 0; + } else if (AVL_GET_BALANCE(s) == a) { + if (AVL_GET_BALANCE (r) == a) { + /* single rotation */ + p = r; + if (a == -1) { + s->left = r->right; + if (r->right) { + r->right->parent = s; + } + r->right = s; + s->parent = r; + AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (r))); + } else { + s->right = r->left; + if (r->left) { + r->left->parent = s; + } + r->left = s; + s->parent = r; + AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (s))); + } + AVL_SET_BALANCE (s, 0); + AVL_SET_BALANCE (r, 0); + } else if (AVL_GET_BALANCE (r) == -a) { + /* double rotation */ + if (a == -1) { + p = r->right; + r->right = p->left; + if (p->left) { + p->left->parent = r; + } + p->left = r; + r->parent = p; + s->left = p->right; + if (p->right) { + p->right->parent = s; + } + p->right = s; + s->parent = p; + AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (r))); + AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (p))); + } else { + p = r->left; + r->left = p->right; + if (p->right) { + p->right->parent = r; + } + p->right = r; + r->parent = p; + s->right = p->left; + if (p->left) { + p->left->parent = s; + } + p->left = s; + s->parent = p; + AVL_SET_RANK (r, (AVL_GET_RANK (r) - AVL_GET_RANK (p))); + AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (s))); + } + if (AVL_GET_BALANCE (p) == a) { + AVL_SET_BALANCE (s, -a); + AVL_SET_BALANCE (r, 0); + } else if (AVL_GET_BALANCE (p) == -a) { + AVL_SET_BALANCE (s, 0); + AVL_SET_BALANCE (r, a); + } else { + AVL_SET_BALANCE (s, 0); + AVL_SET_BALANCE (r, 0); + } + AVL_SET_BALANCE (p, 0); + } + /* finishing touch */ + if (s == t->right) { + t->right = p; + } else { + t->left = p; + } + p->parent = t; + } + } + return 0; +} + +int +avl_get_by_index (avl_tree * tree, + unsigned long index, + void ** value_address) +{ + avl_node * p = tree->root->right; + unsigned long m = index + 1; + while (1) { + if (!p) { + return -1; + } + if (m < AVL_GET_RANK(p)) { + p = p->left; + } else if (m > AVL_GET_RANK(p)) { + m = m - AVL_GET_RANK(p); + p = p->right; + } else { + *value_address = p->key; + return 0; + } + } +} + +int +avl_get_by_key (avl_tree * tree, + void * key, + void **value_address) +{ + avl_node * x = tree->root->right; + if (!x) { + return -1; + } + while (1) { + int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); + if (compare_result < 0) { + if (x->left) { + x = x->left; + } else { + return -1; + } + } else if (compare_result > 0) { + if (x->right) { + x = x->right; + } else { + return -1; + } + } else { + *value_address = x->key; + return 0; + } + } +} + +int avl_delete(avl_tree *tree, void *key, avl_free_key_fun_type free_key_fun) +{ + avl_node *x, *y, *p, *q, *r, *top, *x_child; + int shortened_side, shorter; + + x = tree->root->right; + if (!x) { + return -1; + } + while (1) { + int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); + if (compare_result < 0) { + /* move left + * We will be deleting from the left, adjust this node's + * rank accordingly + */ + AVL_SET_RANK (x, (AVL_GET_RANK(x) - 1)); + if (x->left) { + x = x->left; + } else { + /* Oops! now we have to undo the rank changes + * all the way up the tree + */ + AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1)); + while (x != tree->root->right) { + if (x->parent->left == x) { + AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1)); + } + x = x->parent; + } + return -1; /* key not in tree */ + } + } else if (compare_result > 0) { + /* move right */ + if (x->right) { + x = x->right; + } else { + AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1)); + while (x != tree->root->right) { + if (x->parent->left == x) { + AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1)); + } + x = x->parent; + } + return -1; /* key not in tree */ + } + } else { + break; + } + } + + if (x->left && x->right) { + void * temp_key; + + /* The complicated case. + * reduce this to the simple case where we are deleting + * a node with at most one child. + */ + + /* find the immediate predecessor <y> */ + y = x->left; + while (y->right) { + y = y->right; + } + /* swap <x> with <y> */ + temp_key = x->key; + x->key = y->key; + y->key = temp_key; + /* we know <x>'s left subtree lost a node because that's + * where we took it from + */ + AVL_SET_RANK (x, (AVL_GET_RANK (x) - 1)); + x = y; + } + /* now <x> has at most one child + * scoot this child into the place of <x> + */ + if (x->left) { + x_child = x->left; + x_child->parent = x->parent; + } else if (x->right) { + x_child = x->right; + x_child->parent = x->parent; + } else { + x_child = NULL; + } + + /* now tell <x>'s parent that a grandchild became a child */ + if (x == x->parent->left) { + x->parent->left = x_child; + shortened_side = -1; + } else { + x->parent->right = x_child; + shortened_side = +1; + } + + /* + * the height of the subtree <x> + * has now been shortened. climb back up + * the tree, rotating when necessary to adjust + * for the change. + */ + shorter = 1; + p = x->parent; + + /* return the key and node to storage */ + if (free_key_fun) + free_key_fun (x->key); +#ifdef HAVE_AVL_NODE_LOCK + thread_rwlock_destroy (&x->rwlock); +#endif + free (x); + + while (shorter && p->parent) { + + /* case 1: height unchanged */ + if (AVL_GET_BALANCE(p) == 0) { + if (shortened_side == -1) { + /* we removed a left child, the tree is now heavier + * on the right + */ + AVL_SET_BALANCE (p, +1); + } else { + /* we removed a right child, the tree is now heavier + * on the left + */ + AVL_SET_BALANCE (p, -1); + } + shorter = 0; + + } else if (AVL_GET_BALANCE (p) == shortened_side) { + /* case 2: taller subtree shortened, height reduced */ + AVL_SET_BALANCE (p, 0); + } else { + /* case 3: shorter subtree shortened */ + top = p->parent; + /* set <q> to the taller of the two subtrees of <p> */ + if (shortened_side == 1) { + q = p->left; + } else { + q = p->right; + } + if (AVL_GET_BALANCE (q) == 0) { + /* case 3a: height unchanged */ + if (shortened_side == -1) { + /* single rotate left */ + q->parent = p->parent; + p->right = q->left; + if (q->left) { + q->left->parent = p; + } + q->left = p; + p->parent = q; + AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p))); + } else { + /* single rotate right */ + q->parent = p->parent; + p->left = q->right; + if (q->right) { + q->right->parent = p; + } + q->right = p; + p->parent = q; + AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q))); + } + shorter = 0; + AVL_SET_BALANCE (q, shortened_side); + AVL_SET_BALANCE (p, (- shortened_side)); + } else if (AVL_GET_BALANCE (q) == AVL_GET_BALANCE (p)) { + /* case 3b: height reduced */ + if (shortened_side == -1) { + /* single rotate left */ + q->parent = p->parent; + p->right = q->left; + if (q->left) { + q->left->parent = p; + } + q->left = p; + p->parent = q; + AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p))); + } else { + /* single rotate right */ + q->parent = p->parent; + p->left = q->right; + if (q->right) { + q->right->parent = p; + } + q->right = p; + p->parent = q; + AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q))); + } + shorter = 1; + AVL_SET_BALANCE (q, 0); + AVL_SET_BALANCE (p, 0); + } else { + /* case 3c: height reduced, balance factors opposite */ + if (shortened_side == 1) { + /* double rotate right */ + /* first, a left rotation around q */ + r = q->right; + r->parent = p->parent; + q->right = r->left; + if (r->left) { + r->left->parent = q; + } + r->left = q; + q->parent = r; + /* now, a right rotation around p */ + p->left = r->right; + if (r->right) { + r->right->parent = p; + } + r->right = p; + p->parent = r; + AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (q))); + AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (r))); + } else { + /* double rotate left */ + /* first, a right rotation around q */ + r = q->left; + r->parent = p->parent; + q->left = r->right; + if (r->right) { + r->right->parent = q; + } + r->right = q; + q->parent = r; + /* now a left rotation around p */ + p->right = r->left; + if (r->left) { + r->left->parent = p; + } + r->left = p; + p->parent = r; + AVL_SET_RANK (q, (AVL_GET_RANK (q) - AVL_GET_RANK (r))); + AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (p))); + } + if (AVL_GET_BALANCE (r) == shortened_side) { + AVL_SET_BALANCE (q, (- shortened_side)); + AVL_SET_BALANCE (p, 0); + } else if (AVL_GET_BALANCE (r) == (- shortened_side)) { + AVL_SET_BALANCE (q, 0); + AVL_SET_BALANCE (p, shortened_side); + } else { + AVL_SET_BALANCE (q, 0); + AVL_SET_BALANCE (p, 0); + } + AVL_SET_BALANCE (r, 0); + q = r; + } + /* a rotation has caused <q> (or <r> in case 3c) to become + * the root. let <p>'s former parent know this. + */ + if (top->left == p) { + top->left = q; + } else { + top->right = q; + } + /* end case 3 */ + p = q; + } + x = p; + p = x->parent; + /* shortened_side tells us which side we came up from */ + if (x == p->left) { + shortened_side = -1; + } else { + shortened_side = +1; + } + } /* end while(shorter) */ + /* when we're all done, we're one shorter */ + tree->length = tree->length - 1; + return (0); +} + +static int +avl_iterate_inorder_helper (avl_node * node, + avl_iter_fun_type iter_fun, + void * iter_arg) +{ + int result; + if (node->left) { + result = avl_iterate_inorder_helper (node->left, iter_fun, iter_arg); + if (result != 0) { + return result; + } + } + result = (iter_fun (node->key, iter_arg)); + if (result != 0) { + return result; + } + if (node->right) { + result = avl_iterate_inorder_helper (node->right, iter_fun, iter_arg); + if (result != 0) { + return result; + } + } + return 0; +} + +int +avl_iterate_inorder (avl_tree * tree, + avl_iter_fun_type iter_fun, + void * iter_arg) +{ + int result; + + if (tree->length) { + result = avl_iterate_inorder_helper (tree->root->right, iter_fun, iter_arg); + return (result); + } else { + return 0; + } +} + +avl_node *avl_get_first(avl_tree *tree) +{ + avl_node *node; + + node = tree->root->right; + if (node == NULL || node->key == NULL) return NULL; + + while (node->left) + node = node->left; + + return node; +} + +avl_node *avl_get_prev(avl_node *node) +{ + if (node->left) { + node = node->left; + while (node->right) { + node = node->right; + } + + return node; + } else { + avl_node *child = node; + while (node->parent && node->parent->key) { + node = node->parent; + if (child == node->right) { + return node; + } + child = node; + } + + return NULL; + } +} + +avl_node *avl_get_next(avl_node *node) +{ + if (node->right) { + node = node->right; + while (node->left) { + node = node->left; + } + + return node; + } else { + avl_node *child = node; + while (node->parent && node->parent->key) { + node = node->parent; + if (child == node->left) { + return node; + } + child = node; + } + + return NULL; + } +} + +/* iterate a function over a range of indices, using get_predecessor */ + +int +avl_iterate_index_range (avl_tree * tree, + avl_iter_index_fun_type iter_fun, + unsigned long low, + unsigned long high, + void * iter_arg) +{ + unsigned long m; + unsigned long num_left; + avl_node * node; + + if (high > tree->length) { + return -1; + } + num_left = (high - low); + /* find the <high-1>th node */ + m = high; + node = tree->root->right; + while (1) { + if (m < AVL_GET_RANK (node)) { + node = node->left; + } else if (m > AVL_GET_RANK (node)) { + m = m - AVL_GET_RANK (node); + node = node->right; + } else { + break; + } + } + /* call <iter_fun> on <node>, <get_pred(node)>, ... */ + while (num_left) { + num_left = num_left - 1; + if (iter_fun (num_left, node->key, iter_arg) != 0) { + return -1; + } + node = avl_get_prev (node); + } + return 0; +} + +/* If <key> is present in the tree, return that key's node, and set <*index> + * appropriately. If not, return NULL, and set <*index> to the position + * representing the closest preceding value. + */ + +static avl_node * +avl_get_index_by_key (avl_tree * tree, + void * key, + unsigned long * index) +{ + avl_node * x = tree->root->right; + unsigned long m; + + if (!x) { + return NULL; + } + m = AVL_GET_RANK (x); + + while (1) { + int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); + if (compare_result < 0) { + if (x->left) { + m = m - AVL_GET_RANK(x); + x = x->left; + m = m + AVL_GET_RANK(x); + } else { + *index = m - 2; + return NULL; + } + } else if (compare_result > 0) { + if (x->right) { + x = x->right; + m = m + AVL_GET_RANK(x); + } else { + *index = m - 1; + return NULL; + } + } else { + *index = m - 1; + return x; + } + } +} + +/* return the (low index, high index) pair that spans the given key */ + +int +avl_get_span_by_key (avl_tree * tree, + void * key, + unsigned long * low, + unsigned long * high) +{ + unsigned long m, i, j; + avl_node * node; + + node = avl_get_index_by_key (tree, key, &m); + + /* did we find an exact match? + * if so, we have to search left and right + * to find the span, since we know nothing about + * the arrangement of like keys. + */ + if (node) { + avl_node * left, * right; + /* search left */ + left = avl_get_prev (node); + i = m; + while (left && (i > 0) && (tree->compare_fun (tree->compare_arg, key, left->key) == 0)) { + left = avl_get_prev (left); + i = i - 1; + } + /* search right */ + right = avl_get_next (node); + j = m; + while (right && (j <= tree->length) && (tree->compare_fun (tree->compare_arg, key, right->key) == 0)) { + right = avl_get_next (right); + j = j + 1; + } + *low = i; + *high = j + 1; + return 0; + } else { + *low = *high = m; + } + return 0; +} + +/* return the (low index, high index) pair that spans the given key */ + +int +avl_get_span_by_two_keys (avl_tree * tree, + void * low_key, + void * high_key, + unsigned long * low, + unsigned long * high) +{ + unsigned long i, j; + avl_node * low_node, * high_node; + int order; + + /* we may need to swap them */ + order = tree->compare_fun (tree->compare_arg, low_key, high_key); + if (order > 0) { + void * temp = low_key; + low_key = high_key; + high_key = temp; + } + + low_node = avl_get_index_by_key (tree, low_key, &i); + high_node = avl_get_index_by_key (tree, high_key, &j); + + if (low_node) { + avl_node * left; + /* search left */ + left = avl_get_prev (low_node); + while (left && (i > 0) && (tree->compare_fun (tree->compare_arg, low_key, left->key) == 0)) { + left = avl_get_prev (left); + i = i - 1; + } + } else { + i = i + 1; + } + if (high_node) { + avl_node * right; + /* search right */ + right = avl_get_next (high_node); + while (right && (j <= tree->length) && (tree->compare_fun (tree->compare_arg, high_key, right->key) == 0)) { + right = avl_get_next (right); + j = j + 1; + } + } else { + j = j + 1; + } + + *low = i; + *high = j; + return 0; +} + + +int +avl_get_item_by_key_most (avl_tree * tree, + void * key, + void **value_address) +{ + avl_node * x = tree->root->right; + *value_address = NULL; + + if (!x) { + return -1; + } + while (1) { + int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); + + if (compare_result == 0) { + *value_address = x->key; + return 0; + } else if (compare_result < 0) { + /* the given key is less than the current key */ + if (x->left) { + x = x->left; + } else { + if (*value_address) + return 0; + else + return -1; + } + } else { + /* the given key is more than the current key */ + /* save this value, it might end up being the right one! */ + *value_address = x->key; + if (x->right) { + /* there is a bigger entry */ + x = x->right; + } else { + if (*value_address) + return 0; + else + return -1; + } + } + } +} + +int +avl_get_item_by_key_least (avl_tree * tree, + void * key, + void **value_address) +{ + avl_node * x = tree->root->right; + *value_address = NULL; + + if (!x) { + return -1; + } + while (1) { + int compare_result = tree->compare_fun (tree->compare_arg, key, x->key); + if (compare_result == 0) { + *value_address = x->key; + return 0; /* exact match */ + } else if (compare_result < 0) { + /* the given key is less than the current key */ + /* save this value, it might end up being the right one! */ + *value_address = x->key; + if (x->left) { + x = x->left; + } else { + if (*value_address) /* we have found a valid entry */ + return 0; + else + return -1; + } + } else { + if (x->right) { + /* there is a bigger entry */ + x = x->right; + } else { + if (*value_address) /* we have found a valid entry */ + return 0; + else + return -1; + } + } + } +} + +#define AVL_MAX(X, Y) ((X) > (Y) ? (X) : (Y)) + +static long +avl_verify_balance (avl_node * node) +{ + if (!node) { + return 0; + } else { + long lh = avl_verify_balance (node->left); + long rh = avl_verify_balance (node->right); + if ((rh - lh) != AVL_GET_BALANCE(node)) { + return 0; + } + if (((lh - rh) > 1) || ((lh - rh) < -1)) { + return 0; + } + return (1 + AVL_MAX (lh, rh)); + } +} + +static void +avl_verify_parent (avl_node * node, avl_node * parent) +{ + if (node->parent != parent) { + return; + } + if (node->left) { + avl_verify_parent (node->left, node); + } + if (node->right) { + avl_verify_parent (node->right, node); + } +} + +static long +avl_verify_rank (avl_node * node) +{ + if (!node) { + return 0; + } else { + unsigned long num_left=0, num_right=0; + if (node->left) { + num_left = avl_verify_rank (node->left); + } + if (node->right) { + num_right = avl_verify_rank (node->right); + } + if (AVL_GET_RANK (node) != num_left + 1) { + fprintf (stderr, "invalid rank at node %ld\n", (long) node->key); + exit (1); + } + return (num_left + num_right + 1); + } +} + +/* sanity-check the tree */ + +int +avl_verify (avl_tree * tree) +{ + if (tree->length) { + avl_verify_balance (tree->root->right); + avl_verify_parent (tree->root->right, tree->root); + avl_verify_rank (tree->root->right); + } + return (0); +} + +/* + * These structures are accumulated on the stack during print_tree + * and are used to keep track of the width and direction of each + * branch in the history of a particular line <node>. + */ + +typedef struct _link_node { + struct _link_node * parent; + char direction; + int width; +} link_node; + +static char balance_chars[3] = {'\\', '-', '/'}; + +static int +default_key_printer (char * buffer, void * key) +{ + return snprintf (buffer, AVL_KEY_PRINTER_BUFLEN, "%p", key); +} + +/* + * When traveling the family tree, a change in direction + * indicates when to print a connector. This is kinda crazy, + * we use the stack to build a linked list, and then travel + * it backwards using recursion. + */ + +static void +print_connectors (link_node * link) +{ + if (link->parent) { + print_connectors (link->parent); + } + if (link->parent && (link->parent->direction != link->direction) && (link->parent->parent)) { + int i; + fprintf (stdout, "|"); + for (i=0; i < (link->width - 1); i++) { + fprintf (stdout, " "); + } + } else { + int i; + for (i=0; i < (link->width); i++) { + fprintf (stdout, " "); + } + } +} + +/* + * The <key_printer> function writes a representation of the + * key into <buffer> (which is conveniently fixed in size to add + * the spice of danger). It should return the size of the + * representation. + */ + +static void +print_node (avl_key_printer_fun_type key_printer, + avl_node * node, + link_node * link) +{ + char buffer[AVL_KEY_PRINTER_BUFLEN]; + unsigned int width; + width = key_printer (buffer, node->key); + + if (node->right) { + link_node here; + here.parent = link; + here.direction = 1; + here.width = width + 11; + print_node (key_printer, node->right, &here); + } + print_connectors (link); + fprintf (stdout, "+-[%c %s %03d]", + balance_chars[AVL_GET_BALANCE(node)+1], + buffer, + (int)AVL_GET_RANK(node)); + if (node->left || node->right) { + fprintf (stdout, "-|\n"); + } else { + fprintf (stdout, "\n"); + } + if (node->left) { + link_node here; + here.parent = link; + here.direction = -1; + here.width = width + 11; + print_node (key_printer, node->left, &here); + } +} + +void +avl_print_tree (avl_tree * tree, avl_key_printer_fun_type key_printer) +{ + link_node top = {NULL, 0, 0}; + if (!key_printer) { + key_printer = default_key_printer; + } + if (tree->length) { + print_node (key_printer, tree->root->right, &top); + } else { + fprintf (stdout, "<empty tree>\n"); + } +} + + +void avl_tree_rlock(avl_tree *tree) +{ + thread_rwlock_rlock(&tree->rwlock); +} + +void avl_tree_wlock(avl_tree *tree) +{ + thread_rwlock_wlock(&tree->rwlock); +} + +void avl_tree_unlock(avl_tree *tree) +{ + thread_rwlock_unlock(&tree->rwlock); +} + +#ifdef HAVE_AVL_NODE_LOCK +void avl_node_rlock(avl_node *node) +{ + thread_rwlock_rlock(&node->rwlock); +} + +void avl_node_wlock(avl_node *node) +{ + thread_rwlock_wlock(&node->rwlock); +} + +void avl_node_unlock(avl_node *node) +{ + thread_rwlock_unlock(&node->rwlock); +} +#endif |