Select Git revision
avl.cpp 12.11 KiB
// $Id: avl.cpp,v 1.6 2001-10-31 16:33:46 remacle Exp $
/*
* This is a modified version for Gmsh (for c++, 64-bit architectures, etc.)
*/
/*
* avl package
*
* Copyright (c) 1988-1993, The Regents of the University of California.
*
* 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 the University of California not
* be used in advertising or publicity pertaining to distribution of
* the software without specific, written prior permission. The University
* of California makes no representations about the suitability of this
* software for any purpose. It is provided "as is" without express or
* implied warranty.
*
* THE UNIVERSITY OF CALIFORNIA DISCLAIMS ALL WARRANTIES WITH REGARD TO
* THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS, IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA 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.
*/
#include <stdio.h>
#include "avl.h"
#include "Malloc.h"
#define ALLOC(type, number) (type *) Malloc((unsigned) sizeof(type) * number)
#define FREE(item) (void) Free(item)
#define XRNMAX(a,b) ((a) > (b) ? (a) : (b))
#define HEIGHT(node) (node == NIL(avl_node) ? -1 : (node)->height)
#define BALANCE(node) (HEIGHT((node)->right) - HEIGHT((node)->left))
#define compute_height(node) { \
int x=HEIGHT(node->left), y=HEIGHT(node->right); \
(node)->height = XRNMAX(x,y) + 1; \
}
#define COMPARE(key, nodekey, compare) \
((compare == avl_numcmp) ? \
(long int) key - (long int) nodekey : \
(*compare)(key, nodekey))
static void avl_record_gen_forward(avl_node *node, avl_generator *gen);
static void avl_record_gen_backward(avl_node *node, avl_generator *gen);
static avl_node *find_rightmost(avl_node **node_p);
static void do_rebalance(avl_node ***stack_nodep, int stack_n);
static void rotate_left(avl_node **node_p);
static void rotate_right(avl_node **node_p);
static void free_entry(avl_node *node, void (*key_free)(void *key),
void (*value_free)(void *value));
static avl_node *new_node(void *key, void *value);
static int do_check_tree(avl_node *node, int (*compar)(const void *key1, const void *key2),
int *error);
avl_tree *avl_init_table(int (*compar)(const void *key1, const void *key2))
{
avl_tree *tree;
tree = ALLOC(avl_tree, 1); tree->root = NIL(avl_node);
tree->compar = compar;
tree->num_entries = 0;
return tree;
}
int avl_lookup(avl_tree *tree, void *key, void **value_p)
{
register avl_node *node;
register int (*compare)(const void*, const void *) = tree->compar, diff;
node = tree->root;
while (node != NIL(avl_node)) {
diff = COMPARE(key, node->key, compare);
if (diff == 0) {
/* got a match, give the user a 'value' only if non-null */
if (value_p != NIL(void *)) *value_p = node->value;
return 1;
}
node = (diff < 0) ? node->left : node->right;
}
return 0;
}
int avl_insert(avl_tree *tree, void *key, void *value)
{
register avl_node **node_p, *node;
register int stack_n = 0;
register int (*compare)(const void*, const void *) = tree->compar;
avl_node **stack_nodep[32];
int diff, status;
node_p = &tree->root;
/* walk down the tree (saving the path); stop at insertion point */
status = 0;
while ((node = *node_p) != NIL(avl_node)) {
stack_nodep[stack_n++] = node_p;
diff = COMPARE(key, node->key, compare);
if (diff == 0) status = 1;
node_p = (diff < 0) ? &node->left : &node->right;
}
/* insert the item and re-balance the tree */
*node_p = new_node(key, value);
do_rebalance(stack_nodep, stack_n);
tree->num_entries++;
tree->modified = 1;
return status;
}
int avl_delete(avl_tree *tree, void **key_p, void **value_p)
{
register avl_node **node_p, *node, *rightmost;
register int stack_n = 0;
void *key = *key_p;
int (*compare)(const void*, const void*) = tree->compar, diff;
avl_node **stack_nodep[32];
node_p = &tree->root;
/* Walk down the tree saving the path; return if not found */
while ((node = *node_p) != NIL(avl_node)) {
diff = COMPARE(key, node->key, compare);
if (diff == 0) goto delete_item;
stack_nodep[stack_n++] = node_p;
node_p = (diff < 0) ? &node->left : &node->right;
}
return 0; /* not found */
/* prepare to delete node and replace it with rightmost of left tree */
delete_item:
*key_p = node->key;
if (value_p != 0) *value_p = node->value;
if (node->left == NIL(avl_node)) {
*node_p = node->right;
} else {
rightmost = find_rightmost(&node->left);
rightmost->left = node->left;
rightmost->right = node->right;
rightmost->height = -2; /* mark bogus height for do_rebal */
*node_p = rightmost;
stack_nodep[stack_n++] = node_p;
}
FREE(node);
/* work our way back up, re-balancing the tree */
do_rebalance(stack_nodep, stack_n);
tree->num_entries--;
tree->modified = 1;
return 1;
}
static void avl_record_gen_forward(avl_node *node, avl_generator *gen)
{
if (node != NIL(avl_node)) {
avl_record_gen_forward(node->left, gen);
gen->nodelist[gen->count++] = node;
avl_record_gen_forward(node->right, gen);
}
}
static void avl_record_gen_backward(avl_node *node, avl_generator *gen)
{
if (node != NIL(avl_node)) {
avl_record_gen_backward(node->right, gen);
gen->nodelist[gen->count++] = node;
avl_record_gen_backward(node->left, gen);
}
}
avl_generator *avl_init_gen(avl_tree *tree, int dir)
{
avl_generator *gen;
/* what a hack */
gen = ALLOC(avl_generator, 1);
gen->tree = tree;
gen->nodelist = ALLOC(avl_node *, avl_count(tree));
gen->count = 0;
if (dir == AVL_FORWARD) {
avl_record_gen_forward(tree->root, gen);
} else {
avl_record_gen_backward(tree->root, gen);
}
gen->count = 0;
/* catch any attempt to modify the tree while we generate */
tree->modified = 0;
return gen;
}
int avl_gen(avl_generator *gen, void **key_p, void **value_p)
{
avl_node *node;
if (gen->count == gen->tree->num_entries) {
return 0;
} else {
node = gen->nodelist[gen->count++]; if (key_p != NIL(void *)) *key_p = node->key;
if (value_p != NIL(void *)) *value_p = node->value;
return 1;
}
}
void avl_free_gen(avl_generator *gen)
{
FREE(gen->nodelist);
FREE(gen);
}
static avl_node *find_rightmost(avl_node **node_p)
{
register avl_node *node;
register int stack_n = 0;
avl_node **stack_nodep[32];
node = *node_p;
while (node->right != NIL(avl_node)) {
stack_nodep[stack_n++] = node_p;
node_p = &node->right;
node = *node_p;
}
*node_p = node->left;
do_rebalance(stack_nodep, stack_n);
return node;
}
static void do_rebalance(avl_node ***stack_nodep, int stack_n)
{
register avl_node **node_p, *node;
register int hl, hr;
int height;
/* work our way back up, re-balancing the tree */
while (--stack_n >= 0) {
node_p = stack_nodep[stack_n];
node = *node_p;
hl = HEIGHT(node->left); /* watch for NIL */
hr = HEIGHT(node->right); /* watch for NIL */
if ((hr - hl) < -1) {
rotate_right(node_p);
} else if ((hr - hl) > 1) {
rotate_left(node_p);
} else {
height = XRNMAX(hl, hr) + 1;
if (height == node->height) break;
node->height = height;
}
}
}
static void rotate_left(avl_node **node_p)
{
register avl_node *old_root = *node_p, *new_root, *new_right;
if (BALANCE(old_root->right) >= 0) {
*node_p = new_root = old_root->right;
old_root->right = new_root->left;
new_root->left = old_root;
} else {
new_right = old_root->right;
*node_p = new_root = new_right->left;
old_root->right = new_root->left;
new_right->left = new_root->right;
new_root->right = new_right;
new_root->left = old_root;
compute_height(new_right); }
compute_height(old_root);
compute_height(new_root);
}
static void rotate_right(avl_node **node_p)
{
register avl_node *old_root = *node_p, *new_root, *new_left;
if (BALANCE(old_root->left) <= 0) {
*node_p = new_root = old_root->left;
old_root->left = new_root->right;
new_root->right = old_root;
} else {
new_left = old_root->left;
*node_p = new_root = new_left->right;
old_root->left = new_root->right;
new_left->right = new_root->left;
new_root->left = new_left;
new_root->right = old_root;
compute_height(new_left);
}
compute_height(old_root);
compute_height(new_root);
}
int avl_extremum(avl_tree *tree, int side, void **value_p)
{
register avl_node *node;
node = tree->root;
if (node == NIL(avl_node)) return 0;
if (side == AVL_MOST_LEFT)
while (node->left != NIL(avl_node)) node = node->left;
else
while (node->right != NIL(avl_node)) node = node->right;
if (value_p != NIL(void *)) {
*value_p = node->value;
return 1;
}
return 0;
}
static void free_entry(avl_node *node, void (*key_free)(void *key), void (*value_free)(void *value))
{
if (node != NIL(avl_node)) {
free_entry(node->left, key_free, value_free);
free_entry(node->right, key_free, value_free);
if (key_free != 0) (*key_free)(node->key);
if (value_free != 0) (*value_free)(node->value);
FREE(node);
}
}
void avl_free_table(avl_tree *tree, void (*key_free)(void *key), void (*value_free)(void *value))
{
free_entry(tree->root, key_free, value_free);
FREE(tree);
}
int avl_count(avl_tree *tree)
{
return tree->num_entries;
}
static avl_node *new_node(void *key, void *value)
{ register avl_node *newn;
newn = ALLOC(avl_node, 1);
newn->key = key;
newn->value = value;
newn->height = 0;
newn->left = newn->right = NIL(avl_node);
return newn;
}
int avl_numcmp(const void *x, const void*y)
{
return (long int) x - (long int) y;
}
int avl_check_tree(avl_tree *tree)
{
int error = 0;
(void) do_check_tree(tree->root, tree->compar, &error);
return error;
}
static int do_check_tree(avl_node *node,
int (*compar)(const void *key1, const void *key2), int *error)
{
int l_height, r_height, comp_height, bal;
if (node == NIL(avl_node)) {
return -1;
}
r_height = do_check_tree(node->right, compar, error);
l_height = do_check_tree(node->left, compar, error);
comp_height = XRNMAX(l_height, r_height) + 1;
bal = r_height - l_height;
if (comp_height != node->height) {
(void) printf("Bad height for %p: computed=%d stored=%d\n",
node, comp_height, node->height);
++*error;
}
if (bal > 1 || bal < -1) {
(void) printf("Out of balance at node %p, balance = %d\n",
node, bal);
++*error;
}
if (node->left != NIL(avl_node) &&
(*compar)(node->left->key, node->key) > 0) {
(void) printf("Bad ordering between %p and %p",
node, node->left);
++*error;
}
if (node->right != NIL(avl_node) &&
(*compar)(node->key, node->right->key) > 0) {
(void) printf("Bad ordering between %p and %p",
node, node->right);
++*error;
}
return comp_height;
}