avl.c File Reference

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

Include dependency graph for avl.c:

Go to the source code of this file.

Macros
#define	HEIGHT(node)
#define	BALANCE(node)
#define	compute_height(node)
#define	COMPARE(key, nodekey, compare)
#define	STACK_SIZE   50

Functions
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)
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)
void	avl_foreach (avl_tree *tree, void *func, int direction)
void	avl_free_table (avl_tree *tree, void *key_free, void *value_free)
int	avl_count (avl_tree *tree)
int	avl_numcmp (char *x, char *y)
int	avl_check_tree (avl_tree *tree)

Macro Definition Documentation

BALANCE

#define BALANCE

(

node

)

Value:

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

Definition at line 24 of file avl.c.

COMPARE

#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 COMPARE(key, nodekey, compare)             \
    ((compare == avl_numcmp) ?                 \
    (int) key - (int) nodekey :             \
    (*compare)(key, nodekey))

compute_height

#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 compute_height(node) {                \
    int x=HEIGHT(node->left), y=HEIGHT(node->right);    \
    (node)->height = MAX(x,y) + 1;            \
}

HEIGHT

#define HEIGHT

(

node

)

Value:

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

Definition at line 23 of file avl.c.

STACK_SIZE

#define STACK_SIZE   50

Definition at line 37 of file avl.c.

Function Documentation

avl_check_tree()

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

avl_count()

int avl_count

(

avl_tree *

tree

)

Definition at line 530 of file avl.c.

{
    return tree->num_entries;
}

Here is the caller graph for this function:

avl_delete()

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

Here is the caller graph for this function:

avl_find_or_add()

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 */
}

Here is the caller graph for this function:

avl_first()

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

Here is the caller graph for this function:

avl_foreach()

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

Here is the caller graph for this function:

avl_free_gen()

void avl_free_gen

(

avl_generator *

gen

)

Definition at line 338 of file avl.c.

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

Here is the caller graph for this function:

avl_free_table()

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

Here is the caller graph for this function:

avl_gen()

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

Here is the caller graph for this function:

avl_init_gen()

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

Here is the call graph for this function:

Here is the caller graph for this function:

avl_init_table()

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

Here is the caller graph for this function:

avl_insert()

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

Here is the caller graph for this function:

avl_last()

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

Here is the caller graph for this function:

avl_lookup()

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

Here is the caller graph for this function:

avl_numcmp()

int avl_numcmp	(	char *	x,
		char *	y )

Definition at line 553 of file avl.c.

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

Here is the caller graph for this function: