avltree.c File Reference

#include <stdlib.h>
#include "avltree.h"
#include "tm.h"

Include dependency graph for avltree.c:

Classes
struct	jsw_avlnode
struct	jsw_avltree
struct	jsw_avltrav

Macros
#define	HEIGHT_LIMIT   64 /* Tallest allowable tree */
#define	jsw_single(root, dir)
#define	jsw_double(root, dir)
#define	jsw_adjust_balance(root, dir, bal)
#define	jsw_insert_balance(root, dir)
#define	jsw_remove_balance(root, dir, done)

Typedefs
typedef struct jsw_avlnode	jsw_avlnode_t

Functions
static jsw_avlnode_t *	new_node (jsw_avltree_t *tree, void *data)
static jsw_avlnode_t *	Pnew_node (jsw_avltree_t *tree, void *data)
jsw_avltree_t *	jsw_avlnew (cmp_f cmp)
jsw_avltree_t *	Pjsw_avlnew (cmp_f cmp)
void	jsw_avldelete (jsw_avltree_t *tree)
void	Pjsw_avldelete (jsw_avltree_t *tree)
void *	jsw_avlfind (jsw_avltree_t *tree, void *data)
long	jsw_avlinsert (jsw_avltree_t *tree, void *data)
long	Pjsw_avlinsert (jsw_avltree_t *tree, void *data)
long	jsw_avlerase (jsw_avltree_t *tree, void *data)
long	Pjsw_avlerase (jsw_avltree_t *tree, void *data)
size_t	jsw_avlsize (jsw_avltree_t *tree)
jsw_avltrav_t *	jsw_avltnew (void)
void	jsw_avltdelete (jsw_avltrav_t *trav)
static void *	start (jsw_avltrav_t *trav, jsw_avltree_t *tree, long dir)
static void *	move (jsw_avltrav_t *trav, long dir)
void *	jsw_avltfirst (jsw_avltrav_t *trav, jsw_avltree_t *tree)
void *	jsw_avltlast (jsw_avltrav_t *trav, jsw_avltree_t *tree)
void *	jsw_avltnext (jsw_avltrav_t *trav)
void *	jsw_avltprev (jsw_avltrav_t *trav)

Macro Definition Documentation

#define HEIGHT_LIMIT   64 /* Tallest allowable tree */

#define jsw_adjust_balance	(		root,
			dir,
			bal
	)

Value:

do { \
  jsw_avlnode_t *n = root->link[dir];         \
  jsw_avlnode_t *nn = n->link[!dir];          \
  if ( nn->balance == 0 )                     \
    root->balance = n->balance = 0;           \
  else if ( nn->balance == bal ) {            \
    root->balance = -bal;                     \
    n->balance = 0;                           \
  }                                           \
  else { /* nn->balance == -bal */            \
    root->balance = 0;                        \
    n->balance = bal;                         \
  }                                           \
  nn->balance = 0;                            \
} while (0)

#define jsw_double	(		root,
			dir
	)

Value:

do {                    \
  jsw_avlnode_t *save = root->link[!dir]->link[dir]; \
  root->link[!dir]->link[dir] = save->link[!dir];    \
  save->link[!dir] = root->link[!dir];               \
  root->link[!dir] = save;                           \
  save = root->link[!dir];                           \
  root->link[!dir] = save->link[dir];                \
  save->link[dir] = root;                            \
  root = save;                                       \
} while (0)

#define jsw_insert_balance	(		root,
			dir
	)

Value:

do {  \
  jsw_avlnode_t *n = root->link[dir];      \
  long bal = dir == 0 ? -1 : +1;           \
  if ( n->balance == bal ) {               \
    root->balance = n->balance = 0;        \
    jsw_single ( root, !dir );             \
  }                                        \
  else { /* n->balance == -bal */          \
    jsw_adjust_balance ( root, dir, bal ); \
    jsw_double ( root, !dir );             \
  }                                        \
} while (0)

#define jsw_remove_balance	(		root,
			dir,
			done
	)

Value:

do { \
  jsw_avlnode_t *n = root->link[!dir];         \
  long bal = dir == 0 ? -1 : +1;               \
  if ( n->balance == -bal ) {                  \
    root->balance = n->balance = 0;            \
    jsw_single ( root, dir );                  \
  }                                            \
  else if ( n->balance == bal ) {              \
    jsw_adjust_balance ( root, !dir, -bal );   \
    jsw_double ( root, dir );                  \
  }                                            \
  else { /* n->balance == 0 */                 \
    root->balance = -bal;                      \
    n->balance = bal;                          \
    jsw_single ( root, dir );                  \
    done = 1;                                  \
  }                                            \
} while (0)

#define jsw_single	(		root,
			dir
	)

Value:

do {         \
  jsw_avlnode_t *save = root->link[!dir]; \
  root->link[!dir] = save->link[dir];     \
  save->link[dir] = root;                 \
  root = save;                            \
} while (0)

Typedef Documentation

typedef struct jsw_avlnode jsw_avlnode_t

Function Documentation

void jsw_avldelete

(

jsw_avltree_t *

tree

)

long jsw_avlerase	(	jsw_avltree_t *	tree,
		void *	data
	)

void* jsw_avlfind	(	jsw_avltree_t *	tree,
		void *	data
	)

long jsw_avlinsert	(	jsw_avltree_t *	tree,
		void *	data
	)

Here is the call graph for this function:

jsw_avltree_t* jsw_avlnew

(

cmp_f

cmp

)

size_t jsw_avlsize

(

jsw_avltree_t *

tree

)

void jsw_avltdelete

(

jsw_avltrav_t *

trav

)

void* jsw_avltfirst	(	jsw_avltrav_t *	trav,
		jsw_avltree_t *	tree
	)

Here is the call graph for this function:

void* jsw_avltlast	(	jsw_avltrav_t *	trav,
		jsw_avltree_t *	tree
	)

Here is the call graph for this function:

jsw_avltrav_t* jsw_avltnew

(

void

)

void* jsw_avltnext

(

jsw_avltrav_t *

trav

)

Here is the call graph for this function:

void* jsw_avltprev

(

jsw_avltrav_t *

trav

)

Here is the call graph for this function:

static void* move ( jsw_avltrav_t *  trav, long  dir  )

static

Here is the caller graph for this function:

static jsw_avlnode_t* new_node ( jsw_avltree_t *  tree, void *  data  )

static

Here is the caller graph for this function:

void Pjsw_avldelete

(

jsw_avltree_t *

tree

)

long Pjsw_avlerase	(	jsw_avltree_t *	tree,
		void *	data
	)

long Pjsw_avlinsert	(	jsw_avltree_t *	tree,
		void *	data
	)

Here is the call graph for this function:

jsw_avltree_t* Pjsw_avlnew

(

cmp_f

cmp

)

static jsw_avlnode_t* Pnew_node ( jsw_avltree_t *  tree, void *  data  )

static

Here is the caller graph for this function:

static void* start ( jsw_avltrav_t *  trav, jsw_avltree_t *  tree, long  dir  )

static

Here is the caller graph for this function: