Data Structures
union	COORD_VALUE
	Union to store the coordinate values. More...

struct	NODE_DATA
	structure of a TREE node data More...

union	NODE_DATA_TYPES
	union of the possibles data values of a TREE node More...

struct	OCTREE
	structure of an OCTREE More...

struct	OCTREE_NODE
	structure of an OCTREE node More...

struct	POINT2D
	Structure for a POINT2D in the 2D space. More...

struct	POINT3D
	Structure for a POINT3D in the 3D space. More...

struct	QUADTREE
	structure of a quad tree More...

struct	QUADTREE_NODE
	structure of a quad tree node More...

struct	TREE
	structure of a TREE More...

struct	TREE_NODE
	structure of a n-ary TREE node More...

Typedefs
typedef int(*	compare_func) (COORD_VALUE a, COORD_VALUE b)
	function pointer types for comparison

typedef void(*	print_func) (COORD_VALUE val)
	function pointer types for debug print

Enumerations
enum	COORD_TYPE { COORD_INT , COORD_FLOAT , COORD_DOUBLE }
	Enum for coordinate types. More...

Functions
QUADTREE_NODE *	create_node (COORD_VALUE x, COORD_VALUE y, void *data_ptr)
	function to create a new quad tree node

OCTREE *	create_octree (int type)
	Create a new OCTREE with a specified coordinate type.

OCTREE_NODE *	create_octree_node (POINT3D point, void *data_ptr)
	create and OCTREE node

QUADTREE *	create_quadtree (int coord_type)
	Function to create a new quad tree.

void	free_octree (OCTREE *OCTREE)
	free the OCTREE

void	free_octree_node (OCTREE_NODE *node)
	recursive function to free an OCTREE node and its children

void	free_quadtree (QUADTREE_NODE *root)
	Function to free the quad tree.

void	insert (QUADTREE qt, QUADTREE_NODE root, COORD_VALUE x, COORD_VALUE y, void data_ptr)
	Function to insert a point into the quad tree.

void	insert_octree (OCTREE OCTREE, POINT3D point, void data_ptr)
	Insert a point into the OCTREE.

TREE *	new_tree ()
	create a new TREE

QUADTREE_NODE *	search (QUADTREE qt, QUADTREE_NODE root, COORD_VALUE x, COORD_VALUE y)
	Function to search for a point in the quad tree.

TREE_NODE *	tree_create_node (NODE_DATA value, void(destroy_func)(void ptr))
	create a TREE node

int	tree_delete_node (TREE tree, TREE_NODE node)
	delete a TREE node

void	tree_destroy (TREE **tree)
	destroy a TREE

int	tree_insert_child (TREE_NODE parent, TREE_NODE child)
	insert a child node into the parent node

Detailed Description

Data Structure Documentation

◆ COORD_VALUE

union COORD_VALUE

Union to store the coordinate values.

Examples: ex_trees.c.

Definition at line 94 of file n_trees.h.

Collaboration diagram for COORD_VALUE:

Data Fields
double	d
float	f
int	i

◆ NODE_DATA

struct NODE_DATA

structure of a TREE node data

Definition at line 42 of file n_trees.h.

Collaboration diagram for NODE_DATA:

Data Fields
int32_t	type	node type
union NODE_DATA_TYPES	value	node value

◆ NODE_DATA_TYPES

union NODE_DATA_TYPES

union of the possibles data values of a TREE node

Definition at line 28 of file n_trees.h.

Collaboration diagram for NODE_DATA_TYPES:

Data Fields
double	fval	double type
int	ival	integral type
N_STR *	nstr	N_STR *type.
void *	ptr	pointer type
char *	string	char *type

◆ OCTREE

struct OCTREE

structure of an OCTREE

Definition at line 179 of file n_trees.h.

Collaboration diagram for OCTREE:

Data Fields
int	coord_type	Coordinate type for the entire tree.
OCTREE_NODE *	root	tree list first node

◆ OCTREE_NODE

struct OCTREE_NODE

structure of an OCTREE node

Definition at line 169 of file n_trees.h.

Collaboration diagram for OCTREE_NODE:

Data Fields
struct OCTREE_NODE *	children[8]	Child nodes.
void *	data_ptr	Pointer to additional data, can be NULL.
POINT3D	point	Point represented by this node.

◆ POINT2D

struct POINT2D

Structure for a POINT2D in the 2D space.

Definition at line 101 of file n_trees.h.

Collaboration diagram for POINT2D:

Data Fields
COORD_VALUE	x	x coordinate
COORD_VALUE	y	y coordinate

◆ POINT3D

struct POINT3D

Structure for a POINT3D in the 3D space.

Definition at line 110 of file n_trees.h.

Collaboration diagram for POINT3D:

Data Fields
COORD_VALUE	x	x coordinate
COORD_VALUE	y	y coordinate
COORD_VALUE	z	z coordinate

◆ QUADTREE

struct QUADTREE

structure of a quad tree

Examples: ex_trees.c.

Definition at line 146 of file n_trees.h.

Collaboration diagram for QUADTREE:

Data Fields
compare_func	compare	pointer to comparison function
int	coord_type	type of coordinate used in the quad tree
print_func	print	pointer to print function
QUADTREE_NODE *	root	tree list first node

◆ QUADTREE_NODE

struct QUADTREE_NODE

structure of a quad tree node

Examples: ex_trees.c.

Definition at line 126 of file n_trees.h.

Collaboration diagram for QUADTREE_NODE:

Data Fields
void *	data_ptr	Pointer to data, can be NULL.
struct QUADTREE_NODE *	ne	North-East child.
struct QUADTREE_NODE *	nw	North-West child.
POINT2D	point	X,Y point.
struct QUADTREE_NODE *	se	South-East child.
struct QUADTREE_NODE *	sw	South-West child.
COORD_VALUE	x	X coordinate.
COORD_VALUE	y	Y coordinate.

◆ TREE

struct TREE

structure of a TREE

Definition at line 64 of file n_trees.h.

Collaboration diagram for TREE:

Data Fields
size_t	height	height of the tree
size_t	nb_nodes	number of nodes in the tree
TREE_NODE *	root	pointer to first node
pthread_rwlock_t	rwlock	mutex for thread safety (optional)

◆ TREE_NODE

struct TREE_NODE

structure of a n-ary TREE node

Definition at line 50 of file n_trees.h.

Collaboration diagram for TREE_NODE:

Data Fields
LIST *	children
	ordered list of children

NODE_DATA	data
	structure holding values for node

void(*	destroy_func )(void *ptr)
	value destructor if of type ptr and specified, else a simple free will be used

struct TREE_NODE *	parent
	pointer to parent

LIST_NODE *	parent_list_node
	pointer to parent container of the TREE_NODE, LIST_NODE

Field Documentation

◆ children

LIST* TREE_NODE::children

ordered list of children

Definition at line 60 of file n_trees.h.

Referenced by tree_create_node(), tree_delete_node(), and tree_insert_child().

◆ data

NODE_DATA TREE_NODE::data

structure holding values for node

Definition at line 52 of file n_trees.h.

Referenced by tree_create_node(), and tree_delete_node().

◆ destroy_func

void(* TREE_NODE::destroy_func) (void *ptr)

value destructor if of type ptr and specified, else a simple free will be used

Definition at line 54 of file n_trees.h.

Referenced by tree_create_node(), tree_delete_node(), and tree_insert_child().

◆ parent

struct TREE_NODE* TREE_NODE::parent

pointer to parent

Definition at line 56 of file n_trees.h.

Referenced by tree_create_node(), tree_delete_node(), and tree_insert_child().

◆ parent_list_node

LIST_NODE* TREE_NODE::parent_list_node

pointer to parent container of the TREE_NODE, LIST_NODE

Definition at line 58 of file n_trees.h.

Referenced by tree_create_node(), tree_delete_node(), and tree_insert_child().

Typedef Documentation

◆ compare_func

typedef int(* compare_func) (COORD_VALUE a, COORD_VALUE b)

function pointer types for comparison

Definition at line 121 of file n_trees.h.

◆ print_func

typedef void(* print_func) (COORD_VALUE val)

function pointer types for debug print

Definition at line 123 of file n_trees.h.

Enumeration Type Documentation

◆ COORD_TYPE

enum COORD_TYPE

Enum for coordinate types.

Enumerator
COORD_INT
COORD_FLOAT
COORD_DOUBLE

Definition at line 87 of file n_trees.h.

Function Documentation

◆ create_node()

QUADTREE_NODE * create_node	(	COORD_VALUE	x,
		COORD_VALUE	y,
		void *	data_ptr
	)

function to create a new quad tree node

Parameters

x	x coordinate
y	y coordinate
data_ptr	node private data pointer, can be NULL

Returns: a new QUADTREE_NODE or NULL

Definition at line 242 of file n_trees.c.

References QUADTREE_NODE::data_ptr, LOG_ERR, n_log, QUADTREE_NODE::ne, QUADTREE_NODE::nw, QUADTREE_NODE::se, QUADTREE_NODE::sw, QUADTREE_NODE::x, and QUADTREE_NODE::y.

Referenced by insert().

Here is the caller graph for this function:

◆ create_octree()

OCTREE * create_octree ( int type )

Create a new OCTREE with a specified coordinate type.

Parameters

type	the type of coordinate used by the OCTREE (COORD_INT,COORD_FLOAT,COORD_DOUBLE)

Returns: a new empty OCTREE or NULL

Definition at line 351 of file n_trees.c.

References OCTREE::coord_type, LOG_ERR, n_log, and OCTREE::root.

◆ create_octree_node()

OCTREE_NODE * create_octree_node	(	POINT3D	point,
		void *	data_ptr
	)

create and OCTREE node

Parameters

point	the POINT3D representing the coordinate
data_ptr	the data to insert. Can be NULL

Returns: a new OCTREE_NODE or NULL

Definition at line 330 of file n_trees.c.

References OCTREE_NODE::children, OCTREE_NODE::data_ptr, LOG_ERR, n_log, and OCTREE_NODE::point.

Referenced by insert_octree(), and insert_octree_node().

Here is the caller graph for this function:

◆ create_quadtree()

QUADTREE * create_quadtree ( int coord_type )

Function to create a new quad tree.

Parameters

coord_type the type of nodes for the new tree (COORD_INT,COORD_FLOAT,COORD_DOUBLE)

Returns: a new empty QUADTREE

Definition at line 207 of file n_trees.c.

References QUADTREE::compare, compare_double(), compare_float(), compare_int(), COORD_DOUBLE, COORD_FLOAT, COORD_INT, QUADTREE::coord_type, LOG_ERR, n_log, QUADTREE::print, print_double(), print_float(), print_int(), and QUADTREE::root.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ free_octree()

void free_octree ( OCTREE * octree )

free the OCTREE

Parameters

octree the OCTREE to free

Definition at line 436 of file n_trees.c.

References free_octree_node(), and OCTREE::root.

Here is the call graph for this function:

◆ free_octree_node()

void free_octree_node ( OCTREE_NODE * node )

recursive function to free an OCTREE node and its children

Parameters

node	the starting node for the deletion

Definition at line 423 of file n_trees.c.

References OCTREE_NODE::children, and free_octree_node().

Referenced by free_octree(), and free_octree_node().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ free_quadtree()

void free_quadtree ( QUADTREE_NODE * root )

Function to free the quad tree.

Parameters

root	target quad tree to free

Definition at line 313 of file n_trees.c.

References __n_assert, free_quadtree(), QUADTREE_NODE::ne, QUADTREE_NODE::nw, QUADTREE_NODE::se, and QUADTREE_NODE::sw.

Referenced by free_quadtree(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert()

void insert	(	QUADTREE *	qt,
		QUADTREE_NODE **	root,
		COORD_VALUE	x,
		COORD_VALUE	y,
		void *	data_ptr
	)

Function to insert a point into the quad tree.

Parameters

qt	the target quad tree
root	the QUADTREE_NODE to insert
x	x coordinate
y	y coordinate
data_ptr	node private data pointer, can be NULL

Definition at line 266 of file n_trees.c.

References QUADTREE::compare, create_node(), and insert().

Referenced by insert(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_octree()

void insert_octree	(	OCTREE *	octree,
		POINT3D	point,
		void *	data_ptr
	)

Insert a point into the OCTREE.

Parameters

octree	target OCTREE tree
point	the POINT3D point to insert in the OCTREE
data_ptr	eventual private data for the point, can be NULL

Definition at line 411 of file n_trees.c.

References OCTREE::coord_type, create_octree_node(), insert_octree_node(), and OCTREE::root.

Here is the call graph for this function:

◆ new_tree()

TREE * new_tree ( )

create a new TREE

Returns: a pointer to the new tree or NULL on failure

Definition at line 22 of file n_trees.c.

References __n_assert, height, LOG_ERR, Malloc, n_log, nb_nodes, root, and rwlock.

◆ search()

QUADTREE_NODE * search	(	QUADTREE *	qt,
		QUADTREE_NODE *	root,
		COORD_VALUE	x,
		COORD_VALUE	y
	)

Function to search for a point in the quad tree.

Parameters

qt	the target QUADTREE in which to search
root	the starting QUADTREE_NODE in the tree
x	x coordinate
y	y coordinate

Returns: the QUADTREE_NODE found at coordinate or NULL

Definition at line 291 of file n_trees.c.

References QUADTREE::compare, QUADTREE_NODE::ne, QUADTREE_NODE::nw, QUADTREE_NODE::se, search(), QUADTREE_NODE::sw, QUADTREE_NODE::x, and QUADTREE_NODE::y.

Referenced by main(), and search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ tree_create_node()

TREE_NODE * tree_create_node	(	NODE_DATA	value,
		void()(void ptr)	destroy_func
	)

create a TREE node

Parameters

value	NODE_DATA containing the value to add
destroy_func	a destroy function pointer for the eventual private data_ptr that will later on be attached to the node

Returns: a pointer to the new node or NULL on failure

Definition at line 41 of file n_trees.c.

References TREE_NODE::children, TREE_NODE::data, TREE_NODE::destroy_func, LOG_ERR, MAX_LIST_ITEMS, n_log, new_generic_list(), TREE_NODE::parent, and TREE_NODE::parent_list_node.

Here is the call graph for this function:

◆ tree_delete_node()

int tree_delete_node	(	TREE *	tree,
		TREE_NODE *	node
	)

delete a TREE node

Parameters

tree	the TREE in which we want to delete a node
node	the TREE node we want to delete

Returns: TRUE on success or FALSE on failure

Definition at line 96 of file n_trees.c.

References TREE_NODE::children, TREE_NODE::data, TREE_NODE::destroy_func, nb_nodes, LIST_NODE::next, TREE_NODE::parent, TREE_NODE::parent_list_node, LIST_NODE::ptr, NODE_DATA_TYPES::ptr, remove_list_node_f(), LIST::start, tree_delete_node(), and NODE_DATA::value.

Referenced by tree_delete_node(), and tree_destroy().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ tree_destroy()

void tree_destroy ( TREE ** tree )

destroy a TREE

Parameters

tree	a pointer to the pointer of the TREE to destroy

Definition at line 132 of file n_trees.c.

References tree_delete_node().

Here is the call graph for this function:

◆ tree_insert_child()

int tree_insert_child	(	TREE_NODE *	parent,
		TREE_NODE *	child
	)

insert a child node into the parent node

Parameters

parent	the parent TREE_NODE
child	the new TREE_NODE to add as a child

Returns: TRUE on success or FALSE on failure

Definition at line 63 of file n_trees.c.

References __n_assert, TREE_NODE::children, LIST_NODE::destroy_func, TREE_NODE::destroy_func, Free, list_node_push(), LOG_ERR, MAX_LIST_ITEMS, n_log, new_generic_list(), new_list_node(), TREE_NODE::parent, TREE_NODE::parent_list_node, and LIST_NODE::ptr.

Here is the call graph for this function:

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Data Structure Documentation

◆ COORD_VALUE

◆ NODE_DATA

◆ NODE_DATA_TYPES

◆ OCTREE

◆ OCTREE_NODE

◆ POINT2D

◆ POINT3D

◆ QUADTREE

◆ QUADTREE_NODE

◆ TREE

◆ TREE_NODE

Data Fields

Field Documentation

◆ children

◆ data

◆ destroy_func

◆ parent

◆ parent_list_node

Typedef Documentation

◆ compare_func

◆ print_func

Enumeration Type Documentation

◆ COORD_TYPE

Function Documentation

◆ create_node()

◆ create_octree()

◆ create_octree_node()

◆ create_quadtree()

◆ free_octree()

◆ free_octree_node()

◆ free_quadtree()

◆ insert()

◆ insert_octree()

◆ new_tree()

◆ search()

◆ tree_create_node()

◆ tree_delete_node()

◆ tree_destroy()

◆ tree_insert_child()