summaryrefslogtreecommitdiffstats
path: root/lib/libshout/src/common/avl/avl.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libshout/src/common/avl/avl.c')
-rw-r--r--lib/libshout/src/common/avl/avl.c1194
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-10 15:48:44 +0000