avl.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "avl.h"

Go to the source code of this file.

Macros
#define	HEIGHT(node)   (node == NIL(avl_node) ? -1 : (node)->height)
#define	BALANCE(node)   (HEIGHT((node)->right) - HEIGHT((node)->left))
#define	compute_height(node)
#define	COMPARE(key, nodekey, compare)
#define	STACK_SIZE   50

Functions
static avl_node *	new_node ()
static avl_node *	find_rightmost ()
static void	do_rebalance ()
static	rotate_left ()
static	rotate_right ()
static int	do_check_tree ()
avl_tree *	avl_init_table (int(*)() compar)
	avl_lookup (avl_tree *tree, char *key, char **value_p)
	avl_first (avl_tree *tree, char **key_p, char **value_p)
	avl_last (avl_tree *tree, char **key_p, char **value_p)
	avl_insert (avl_tree *tree, char *key, char *value)
	avl_find_or_add (avl_tree *tree, char *key, char ***slot_p)
	avl_delete (avl_tree *tree, char **key_p, char **value_p)
static void	avl_record_gen_forward (avl_node *node, avl_generator *gen)
static void	avl_record_gen_backward (avl_node *node, avl_generator *gen)
avl_generator *	avl_init_gen (avl_tree *tree, int dir)
	avl_gen (avl_generator *gen, char **key_p, char **value_p)
void	avl_free_gen (avl_generator *gen)
static avl_node *	find_rightmost (avl_node **node_p)
static void	do_rebalance (avl_node ***stack_nodep, int stack_n)
static	rotate_left (avl_node **node_p)
static	rotate_right (avl_node **node_p)
static void	avl_walk_forward (avl_node *node, void(*)() func)
static void	avl_walk_backward (avl_node *node, void(*)() func)
void	avl_foreach (avl_tree *tree, void(*)() func, int direction)
static void	free_entry (avl_node *node, void(*)() key_free, void(*)() value_free)
void	avl_free_table (avl_tree *tree, void(*)() key_free, void(*)() value_free)
int	avl_count (avl_tree *tree)
static avl_node *	new_node (char *key, char *value)
int	avl_numcmp (char *x, char *y)
int	avl_check_tree (avl_tree *tree)
static int	do_check_tree (avl_node *node, int(*)() compar, int *error)

Macro Definition Documentation

#define BALANCE

(

node

)

(HEIGHT((node)->right) - HEIGHT((node)->left))

Definition at line 24 of file avl.c.

#define COMPARE	(		key,
			nodekey,
			compare
	)

Value:

((compare == avl_numcmp) ?              \
    (int) key - (int) nodekey :             \
    (*compare)(key, nodekey))

Definition at line 31 of file avl.c.

#define compute_height

(

node

)

Value:

{               \
    int x=HEIGHT(node->left), y=HEIGHT(node->right);    \
    (node)->height = MAX(x,y) + 1;          \
}

Definition at line 26 of file avl.c.

#define HEIGHT

(

node

)

(node == NIL(avl_node) ? -1 : (node)->height)

Definition at line 23 of file avl.c.

#define STACK_SIZE   50

Definition at line 37 of file avl.c.

Function Documentation

int avl_check_tree

(

avl_tree *

tree

)

Definition at line 560 of file avl.c.

{
    int error = 0;
    (void) do_check_tree (tree->root, tree->compar, &error);
    return error;
}

int avl_count

(

avl_tree *

tree

)

Definition at line 530 of file avl.c.

{
    return tree->num_entries;
}

avl_delete	(	avl_tree *	tree,
		char **	key_p,
		char **	value_p
	)

Definition at line 207 of file avl.c.

{
    register avl_node **node_p, *node, *rightmost;
    register int stack_n = 0;
    char *key = *key_p;
    int (*compare) () = tree->compar, diff;
    avl_node **stack_nodep[STACK_SIZE];

    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;
}

avl_find_or_add	(	avl_tree *	tree,
		char *	key,
		char ***	slot_p
	)

Definition at line 170 of file avl.c.

{
    register avl_node **node_p, *node;
    register int stack_n = 0;
    register int (*compare) () = tree->compar;
    avl_node **stack_nodep[STACK_SIZE];
    int diff;

    node_p = &tree->root;

    /* walk down the tree (saving the path); stop at insertion point */
    while ((node = *node_p) != NIL (avl_node))
    {
        stack_nodep[stack_n++] = node_p;
        diff = COMPARE (key, node->key, compare);
        if (diff == 0)
        {
            if (slot_p != 0)
                *slot_p = &node->value;
            return 1;           /* found */
        }
        node_p = (diff < 0) ? &node->left : &node->right;
    }

    /* insert the item and re-balance the tree */
    *node_p = new_node (key, NIL (char));
    if (slot_p != 0)
        *slot_p = &(*node_p)->value;
    do_rebalance (stack_nodep, stack_n);
    tree->num_entries++;
    tree->modified = 1;
    return 0;                   /* not already in tree */
}

avl_first	(	avl_tree *	tree,
		char **	key_p,
		char **	value_p
	)

Definition at line 85 of file avl.c.

{
    register avl_node *node;

    if (tree->root == 0)
    {
        return 0;               /* no entries */
    }
    else
    {
        /* walk down the tree; stop at leftmost leaf */
        for (node = tree->root; node->left != 0; node = node->left)
        {
        }
        if (key_p != NIL (char *))
             *key_p = node->key;
        if (value_p != NIL (char *))
             *value_p = node->value;
        return 1;
    }
}

void avl_foreach	(	avl_tree *	tree,
		void (*) ()	func,
		int	direction
	)

Definition at line 483 of file avl.c.

{
    if (direction == AVL_FORWARD)
    {
        avl_walk_forward (tree->root, func);
    }
    else
    {
        avl_walk_backward (tree->root, func);
    }
}

void avl_free_gen

(

avl_generator *

gen

)

Definition at line 338 of file avl.c.

{
    FREE (gen->nodelist);
    FREE (gen);
}

void avl_free_table	(	avl_tree *	tree,
		void (*) ()	key_free,
		void (*) ()	value_free
	)

Definition at line 519 of file avl.c.

{
    free_entry (tree->root, key_free, value_free);
    FREE (tree);
}

avl_gen	(	avl_generator *	gen,
		char **	key_p,
		char **	value_p
	)

Definition at line 314 of file avl.c.

{
    avl_node *node;

    if (gen->count == gen->tree->num_entries)
    {
        return 0;
    }
    else
    {
        node = gen->nodelist[gen->count++];
        if (key_p != NIL (char *))
             *key_p = node->key;
        if (value_p != NIL (char *))
             *value_p = node->value;
        return 1;
    }
}

avl_generator* avl_init_gen	(	avl_tree *	tree,
		int	dir
	)

Definition at line 287 of file avl.c.

{
    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;
}

avl_tree* avl_init_table

(

int (*) ()

compar

)

Definition at line 47 of file avl.c.

{
    avl_tree *tree;

    tree = ALLOC (avl_tree, 1);
    tree->root = NIL (avl_node);
    tree->compar = compar;
    tree->num_entries = 0;
    return tree;
}

avl_insert	(	avl_tree *	tree,
		char *	key,
		char *	value
	)

Definition at line 136 of file avl.c.

{
    register avl_node **node_p, *node;
    register int stack_n = 0;
    register int (*compare) () = tree->compar;
    avl_node **stack_nodep[STACK_SIZE];
    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;
}

avl_last	(	avl_tree *	tree,
		char **	key_p,
		char **	value_p
	)

Definition at line 111 of file avl.c.

{
    register avl_node *node;

    if (tree->root == 0)
    {
        return 0;               /* no entries */
    }
    else
    {
        /* walk down the tree; stop at rightmost leaf */
        for (node = tree->root; node->right != 0; node = node->right)
        {
        }
        if (key_p != NIL (char *))
             *key_p = node->key;
        if (value_p != NIL (char *))
             *value_p = node->value;
        return 1;
    }
}

avl_lookup	(	avl_tree *	tree,
		char *	key,
		char **	value_p
	)

Definition at line 61 of file avl.c.

{
    register avl_node *node;
    register int (*compare) () = tree->compar, diff;

    node = tree->root;
    while (node != NIL (avl_node))
    {
        diff = COMPARE (key, node->key, compare);
        if (diff == 0)
        {
            /* got a match */
            if (value_p != NIL (char *))
                 *value_p = node->value;
            return 1;
        }
        node = (diff < 0) ? node->left : node->right;
    }
    return 0;
}

int avl_numcmp	(	char *	x,
		char *	y
	)

Definition at line 553 of file avl.c.

{
    return (int) x - (int) y;
}

static void avl_record_gen_backward ( avl_node *  node, avl_generator *  gen  )

static

Definition at line 273 of file avl.c.

{
    if (node != NIL (avl_node))
    {
        avl_record_gen_backward (node->right, gen);
        gen->nodelist[gen->count++] = node;
        avl_record_gen_backward (node->left, gen);
    }
}

static void avl_record_gen_forward ( avl_node *  node, avl_generator *  gen  )

static

Definition at line 259 of file avl.c.

{
    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_walk_backward ( avl_node *  node, void (*) ()  func  )

static

Definition at line 469 of file avl.c.

{
    if (node != NIL (avl_node))
    {
        avl_walk_backward (node->right, func);
        (*func) (node->key, node->value);
        avl_walk_backward (node->left, func);
    }
}

static void avl_walk_forward ( avl_node *  node, void (*) ()  func  )

static

Definition at line 455 of file avl.c.

{
    if (node != NIL (avl_node))
    {
        avl_walk_forward (node->left, func);
        (*func) (node->key, node->value);
        avl_walk_forward (node->right, func);
    }
}

static int do_check_tree ( )

static

static int do_check_tree ( avl_node *  node, int (*) ()  compar, int *  error  )

static

Definition at line 570 of file avl.c.

{
    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 = MAX (l_height, r_height) + 1;
    bal = r_height - l_height;

    if (comp_height != node->height)
    {
        (void) printf ("Bad height for 0x%08x: computed=%d stored=%d\n",
                       node, comp_height, node->height);
        ++*error;
    }

    if (bal > 1 || bal < -1)
    {
        (void) printf ("Out of balance at node 0x%08x, balance = %d\n",
                       node, bal);
        ++*error;
    }

    if (node->left != NIL (avl_node) &&
        (*compar) (node->left->key, node->key) > 0)
    {
        (void) printf ("Bad ordering between 0x%08x and 0x%08x",
                       node, node->left);
        ++*error;
    }

    if (node->right != NIL (avl_node) &&
        (*compar) (node->key, node->right->key) > 0)
    {
        (void) printf ("Bad ordering between 0x%08x and 0x%08x",
                       node, node->right);
        ++*error;
    }

    return comp_height;
}

static void do_rebalance ( )

static

static void do_rebalance ( avl_node ***  stack_nodep, int  stack_n  )

static

Definition at line 368 of file avl.c.

{
    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 = MAX (hl, hr) + 1;
            if (height == node->height)
                break;
            node->height = height;
        }
    }
}

static avl_node* find_rightmost ( )

static

static avl_node* find_rightmost ( avl_node **  node_p )

static

Definition at line 346 of file avl.c.

{
    register avl_node *node;
    register int stack_n = 0;
    avl_node **stack_nodep[STACK_SIZE];

    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 free_entry ( avl_node *  node, void (*) ()  key_free, void (*) ()  value_free  )

static

Definition at line 500 of file avl.c.

{
    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);
    }
}

static avl_node* new_node ( )

static

static avl_node* new_node ( char *  key, char *  value  )

static

Definition at line 537 of file avl.c.

{
    register avl_node *new;

    new = ALLOC (avl_node, 1);
    new->key = key;
    new->value = value;
    new->height = 0;
    new->left = new->right = NIL (avl_node);
    return new;
}

static rotate_left ( )

static

static rotate_left ( avl_node **  node_p )

static

Definition at line 402 of file avl.c.

{
    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 rotate_right ( )

static

static rotate_right ( avl_node **  node_p )

static

Definition at line 429 of file avl.c.

{
    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);
}