avl.cpp File Reference

#include "GmshConfig.h"
#include <stdint.h>
#include <stdio.h>
#include "avl.h"
#include "MallocUtils.h"

Include dependency graph for avl.cpp:

Go to the source code of this file.

Macros
#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)
#define	COMPARE(key, nodekey, compare)

Functions
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))
int	avl_lookup (avl_tree *tree, void *key, void **value_p)
int	avl_insert (avl_tree *tree, void *key, void *value)
int	avl_delete (avl_tree *tree, void **key_p, void **value_p)
avl_generator *	avl_init_gen (avl_tree *tree, int dir)
int	avl_gen (avl_generator *gen, void **key_p, void **value_p)
void	avl_free_gen (avl_generator *gen)
int	avl_extremum (avl_tree *tree, int side, void **value_p)
void	avl_free_table (avl_tree *tree, void(*key_free)(void *key), void(*value_free)(void *value))
int	avl_count (avl_tree *tree)
int	avl_numcmp (const void *x, const void *y)
int	avl_check_tree (avl_tree *tree)

Macro Definition Documentation

ALLOC

#define ALLOC	(		type,
			number
	)		(type *) Malloc((unsigned) sizeof(type) * number)

Definition at line 39 of file avl.cpp.

BALANCE

#define BALANCE

(

node

)

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

Definition at line 43 of file avl.cpp.

COMPARE

#define COMPARE	(		key,
			nodekey,
			compare
	)

Value:

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

Definition at line 50 of file avl.cpp.

compute_height

#define compute_height

(

node

)

Value:

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

Definition at line 45 of file avl.cpp.

FREE

#define FREE

(

item

)

(void) Free(item)

Definition at line 40 of file avl.cpp.

HEIGHT

#define HEIGHT

(

node

)

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

Definition at line 42 of file avl.cpp.

XRNMAX

#define XRNMAX	(		a,
			b
	)		((a) > (b) ? (a) : (b))

Definition at line 41 of file avl.cpp.

Function Documentation

avl_check_tree()

int avl_check_tree

(

avl_tree *

tree

)

Definition at line 367 of file avl.cpp.

Here is the call graph for this function:

avl_count()

int avl_count

(

avl_tree *

tree

)

Definition at line 345 of file avl.cpp.

Referenced by avl_init_gen(), and Tree_Nbr().

Here is the caller graph for this function:

avl_delete()

int avl_delete	(	avl_tree *	tree,
		void **	key_p,
		void **	value_p
	)

Definition at line 123 of file avl.cpp.

Referenced by Tree_Suppress().

Here is the call graph for this function:

Here is the caller graph for this function:

avl_extremum()

int avl_extremum	(	avl_tree *	tree,
		int	side,
		void **	value_p
	)

Definition at line 309 of file avl.cpp.

avl_free_gen()

void avl_free_gen

(

avl_generator *

gen

)

Definition at line 218 of file avl.cpp.

avl_free_table()

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

Definition at line 339 of file avl.cpp.

Referenced by Tree_Delete().

Here is the call graph for this function:

Here is the caller graph for this function:

avl_gen()

int avl_gen	(	avl_generator *	gen,
		void **	key_p,
		void **	value_p
	)

Definition at line 204 of file avl.cpp.

avl_init_gen()

avl_generator* avl_init_gen	(	avl_tree *	tree,
		int	dir
	)

Definition at line 183 of file avl.cpp.

Here is the call graph for this function:

avl_init_table()

avl_tree* avl_init_table

(

int(*)(const void *key1, const void *key2)

compar

)

Definition at line 67 of file avl.cpp.

Referenced by Tree_Create().

Here is the caller graph for this function:

avl_insert()

int avl_insert	(	avl_tree *	tree,
		void *	key,
		void *	value
	)

Definition at line 96 of file avl.cpp.

Referenced by Tree_Add().

Here is the call graph for this function:

Here is the caller graph for this function:

avl_lookup()

int avl_lookup	(	avl_tree *	tree,
		void *	key,
		void **	value_p
	)

Definition at line 78 of file avl.cpp.

Referenced by Tree_PQuery(), Tree_Query(), and Tree_Search().

Here is the call graph for this function:

Here is the caller graph for this function:

avl_numcmp()

int avl_numcmp	(	const void *	x,
		const void *	y
	)

Definition at line 362 of file avl.cpp.

avl_record_gen_backward()

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

static

Definition at line 174 of file avl.cpp.

Referenced by avl_init_gen().

Here is the caller graph for this function:

avl_record_gen_forward()

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

static

Definition at line 165 of file avl.cpp.

Referenced by avl_init_gen().

Here is the caller graph for this function:

do_check_tree()

static int do_check_tree ( avl_node *  node, int(*)(const void *key1, const void *key2)  compar, int *  error  )

static

Definition at line 374 of file avl.cpp.

Referenced by avl_check_tree().

Here is the caller graph for this function:

do_rebalance()

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

static

Definition at line 242 of file avl.cpp.

Referenced by avl_delete(), avl_insert(), and find_rightmost().

Here is the call graph for this function:

Here is the caller graph for this function:

find_rightmost()

static avl_node * find_rightmost ( avl_node **  node_p )

static

Definition at line 224 of file avl.cpp.

Referenced by avl_delete().

Here is the call graph for this function:

Here is the caller graph for this function:

free_entry()

static void free_entry ( avl_node *  node, void(*)(void *key)  key_free, void(*)(void *value)  value_free  )

static

Definition at line 328 of file avl.cpp.

Referenced by avl_free_table().

Here is the caller graph for this function:

new_node()

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

static

Definition at line 350 of file avl.cpp.

Referenced by avl_insert().

Here is the caller graph for this function:

rotate_left()

static void rotate_left ( avl_node **  node_p )

static

Definition at line 266 of file avl.cpp.

Referenced by do_rebalance().

Here is the caller graph for this function:

rotate_right()

static void rotate_right ( avl_node **  node_p )

static

Definition at line 287 of file avl.cpp.

Referenced by do_rebalance().

Here is the caller graph for this function: