type_abr.h File Reference

Implementation of AVLs for representing sets of objects. More...

#include <stdbool.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include "type_basic.h"
#include "type_dequeue.h"
#include "alloc.h"

Go to the source code of this file.

Classes
struct	avlnode
	Type used to represent a single node in a generic AVL. More...
struct	uint_avlnode
	Type used to represent a single node in a light AVL. More...

Typedefs
typedef struct avlnode	avlnode
	Type used to represent a single node in a generic AVL.
typedef struct uint_avlnode	uint_avlnode
	Type used to represent a single node in a light AVL.

Functions
avlnode *	avl_search (void *, avlnode *, int(*f)(void *, void *))
	Searches for a value inside an generic AVL tree.
avlnode *	avl_insert (void *, avlnode *, int(*f)(void *, void *), void(*d)(void *))
	Insertion of a value inside a generic AVL tree.
int	getsize_avl (avlnode *)
	Computes the size of a generic AVL tree.
void	avl_free_strong (avlnode *, void(*f)(void *))
	Release of a generic AVL tree.
int	avl_height (avlnode *)
uint_avlnode *	uint_avl_search (uint, uint_avlnode *)
	Searches for a value inside an light AVL tree.
uint_avlnode *	uint_avl_insert (uint, uint_avlnode *)
	Insertion of a value inside a light AVL tree.
int	getsize_uint_avl (uint_avlnode *)
	Computes the size of a light AVL tree.
void	uint_avl_to_dequeue (uint_avlnode *, dequeue *)
	Extracts all values in a light AVL tree and stores on the right of the input dequeue in increasing order.

Detailed Description

Implementation of AVLs for representing sets of objects.

Remarks

Two versions are implemented. The first one is generic and stores void pointers. The second one is lighter and stores unsigned integers only.

Function Documentation

avl_free_strong()

void avl_free_strong	(	avlnode *	p,
		void(*	f )(void *) )

Release of a generic AVL tree.

Remarks

The input function is used to release the values contained in the AVL tree.

Parameters

p	Root node of the AVL tree.
f	Function used to release the values.

avl_height()

int avl_height

(

avlnode *

tree

)

Parameters

tree	Root node of the AVL tree.

avl_insert()

avlnode * avl_insert	(	void *	val,
		avlnode *	p,
		int(*	f )(void *, void *),
		void(*	d )(void *) )

Insertion of a value inside a generic AVL tree.

Returns

A pointer to the new root node of the AVL tree.

Parameters

val	The value that needs to be inserted.
p	Root node of the AVL tree.
f	Comparison function.
d	Function used to release the values when they are already in the tree (NULL if no release is desired).

avl_search()

avlnode * avl_search	(	void *	val,
		avlnode *	p,
		int(*	f )(void *, void *) )

Searches for a value inside an generic AVL tree.

Returns

A pointer to the node containing the searched value or NULL if the value wad not found.

Parameters

val	The searched value.
p	Root node of the AVL tree.
f	Comparison function.

getsize_avl()

int getsize_avl

(

avlnode *

p

)

Computes the size of a generic AVL tree.

Returns

The size of the AVL tree.

Parameters

p	Root node of the AVL tree.

getsize_uint_avl()

int getsize_uint_avl

(

uint_avlnode *

p

)

Computes the size of a light AVL tree.

Returns

The size of the AVL tree.

Parameters

p	Root node of the AVL tree.

uint_avl_insert()

uint_avlnode * uint_avl_insert	(	uint	val,
		uint_avlnode *	p )

Insertion of a value inside a light AVL tree.

Returns

A pointer to the new root node of the AVL tree.

Parameters

val	The value that needs to be inserted.
p	Root node of the AVL tree.

uint_avl_search()

uint_avlnode * uint_avl_search	(	uint	val,
		uint_avlnode *	p )

Searches for a value inside an light AVL tree.

Returns

A pointer to the node containing the searched value or NULL if the value wad not found.

Parameters

val	The searched value.
p	Root node of the AVL tree.

uint_avl_to_dequeue()

void uint_avl_to_dequeue	(	uint_avlnode *	p,
		dequeue *	v )

Extracts all values in a light AVL tree and stores on the right of the input dequeue in increasing order.

Parameters

p	Root node of the AVL tree.
v	The dequeue.