Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
n_trees.h
Go to the documentation of this file.
1
8#ifndef __NILOREA_TREES__
9#define __NILOREA_TREES__
10
11#ifdef __cplusplus
12extern "C" {
13#endif
14
15#include "nilorea/n_common.h"
16#include "nilorea/n_str.h"
17#include "nilorea/n_log.h"
18#include "nilorea/n_list.h"
19#include "nilorea/n_hash.h"
20#include "nilorea/n_3d.h"
21
30 int ival;
32 double fval;
34 void* ptr;
36 char* string;
39};
40
42typedef struct NODE_DATA {
46 int32_t type;
47} NODE_DATA;
48
62
64typedef struct TREE {
68 pthread_rwlock_t rwlock;
70 size_t nb_nodes;
72 size_t height;
73} TREE;
74
75// create a TREE
76TREE* new_tree();
77// create a TREE node
78TREE_NODE* tree_create_node(NODE_DATA value, void (*destroy_func)(void* ptr));
79// insert a node in the parent node
80int tree_insert_child(TREE_NODE* parent, TREE_NODE* child);
81// delete a TREE node
82int tree_delete_node(TREE* tree, TREE_NODE* node);
83// delete a TREE
84void tree_destroy(TREE** tree);
85
88 COORD_INT,
89 COORD_FLOAT,
90 COORD_DOUBLE
91};
92
94typedef union {
95 int i;
96 float f;
97 double d;
99
101typedef struct POINT2D {
107} POINT2D;
108
110typedef struct POINT3D {
118} POINT3D;
119
123typedef void (*print_func)(COORD_VALUE val);
124
144
156
157// Function to create a new quad tree
158QUADTREE* create_quadtree(int coord_type);
159// Function to create a new quad tree node
160QUADTREE_NODE* create_node(COORD_VALUE x, COORD_VALUE y, void* data_ptr);
161// Function to search for a point in the quad tree
163// Function to insert a point into the quad tree
164void insert(QUADTREE* qt, QUADTREE_NODE** root, COORD_VALUE x, COORD_VALUE y, void* data_ptr);
165// Function to free the quad tree
166void free_quadtree(QUADTREE_NODE* root);
167
177
179typedef struct {
184} OCTREE;
185
186// Function prototypes
187OCTREE* create_octree(int type);
188OCTREE_NODE* create_octree_node(POINT3D point, void* data_ptr);
189void insert_octree(OCTREE* OCTREE, POINT3D point, void* data_ptr);
190void free_octree_node(OCTREE_NODE* node);
192
193#ifdef __cplusplus
194}
195#endif
196
201#endif // header guard
Structure of a generic LIST container.
Definition n_list.h:39
Structure of a generic list node.
Definition n_list.h:24
A box including a string and his lenght.
Definition n_str.h:39
POINT2D point
X,Y point.
Definition n_trees.h:132
print_func print
pointer to print function
Definition n_trees.h:152
compare_func compare
pointer to comparison function
Definition n_trees.h:150
TREE_NODE * root
pointer to first node
Definition n_trees.h:66
pthread_rwlock_t rwlock
mutex for thread safety (optional)
Definition n_trees.h:68
struct QUADTREE_NODE * nw
North-West child.
Definition n_trees.h:136
char * string
char *type
Definition n_trees.h:36
int coord_type
type of coordinate used in the quad tree
Definition n_trees.h:148
size_t nb_nodes
number of nodes in the tree
Definition n_trees.h:70
COORD_VALUE z
z coordinate
Definition n_trees.h:117
void * data_ptr
Pointer to additional data, can be NULL.
Definition n_trees.h:173
OCTREE_NODE * root
tree list first node
Definition n_trees.h:181
COORD_VALUE y
Y coordinate.
Definition n_trees.h:130
QUADTREE_NODE * root
tree list first node
Definition n_trees.h:154
union NODE_DATA_TYPES value
node value
Definition n_trees.h:44
COORD_VALUE x
x coordinate
Definition n_trees.h:104
int32_t type
node type
Definition n_trees.h:46
NODE_DATA data
structure holding values for node
Definition n_trees.h:52
struct QUADTREE_NODE * sw
South-West child.
Definition n_trees.h:140
COORD_VALUE x
x coordinate
Definition n_trees.h:113
COORD_VALUE y
y coordinate
Definition n_trees.h:106
double fval
double type
Definition n_trees.h:32
void * ptr
pointer type
Definition n_trees.h:34
void * data_ptr
Pointer to data, can be NULL.
Definition n_trees.h:134
struct QUADTREE_NODE * se
South-East child.
Definition n_trees.h:142
POINT3D point
Point represented by this node.
Definition n_trees.h:171
struct QUADTREE_NODE * ne
North-East child.
Definition n_trees.h:138
void(* destroy_func)(void *ptr)
value destructor if of type ptr and specified, else a simple free will be used
Definition n_trees.h:54
int ival
integral type
Definition n_trees.h:30
COORD_VALUE y
y coordinate
Definition n_trees.h:115
COORD_VALUE x
X coordinate.
Definition n_trees.h:128
struct OCTREE_NODE * children[8]
Child nodes.
Definition n_trees.h:175
LIST_NODE * parent_list_node
pointer to parent container of the TREE_NODE, LIST_NODE
Definition n_trees.h:58
N_STR * nstr
N_STR *type.
Definition n_trees.h:38
struct TREE_NODE * parent
pointer to parent
Definition n_trees.h:56
size_t height
height of the tree
Definition n_trees.h:72
LIST * children
ordered list of children
Definition n_trees.h:60
int coord_type
Coordinate type for the entire tree.
Definition n_trees.h:183
int(* compare_func)(COORD_VALUE a, COORD_VALUE b)
function pointer types for comparison
Definition n_trees.h:121
void free_octree_node(OCTREE_NODE *node)
recursive function to free an OCTREE node and its children
Definition n_trees.c:422
void insert_octree(OCTREE *OCTREE, POINT3D point, void *data_ptr)
Insert a point into the OCTREE.
Definition n_trees.c:410
int tree_insert_child(TREE_NODE *parent, TREE_NODE *child)
insert a child node into the parent node
Definition n_trees.c:62
void free_quadtree(QUADTREE_NODE *root)
Function to free the quad tree.
Definition n_trees.c:312
TREE * new_tree()
create a new TREE
Definition n_trees.c:21
TREE_NODE * tree_create_node(NODE_DATA value, void(*destroy_func)(void *ptr))
create a TREE node
Definition n_trees.c:40
void(* print_func)(COORD_VALUE val)
function pointer types for debug print
Definition n_trees.h:123
QUADTREE_NODE * search(QUADTREE *qt, QUADTREE_NODE *root, COORD_VALUE x, COORD_VALUE y)
Function to search for a point in the quad tree.
Definition n_trees.c:290
COORD_TYPE
Enum for coordinate types.
Definition n_trees.h:87
void free_octree(OCTREE *OCTREE)
free the OCTREE
Definition n_trees.c:435
void tree_destroy(TREE **tree)
destroy a TREE
Definition n_trees.c:131
OCTREE_NODE * create_octree_node(POINT3D point, void *data_ptr)
create and OCTREE node
Definition n_trees.c:329
OCTREE * create_octree(int type)
Create a new OCTREE with a specified coordinate type.
Definition n_trees.c:350
int tree_delete_node(TREE *tree, TREE_NODE *node)
delete a TREE node
Definition n_trees.c:95
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.
Definition n_trees.c:265
QUADTREE * create_quadtree(int coord_type)
Function to create a new quad tree.
Definition n_trees.c:206
QUADTREE_NODE * create_node(COORD_VALUE x, COORD_VALUE y, void *data_ptr)
function to create a new quad tree node
Definition n_trees.c:241
structure of a TREE node data
Definition n_trees.h:42
structure of an OCTREE
Definition n_trees.h:179
structure of an OCTREE node
Definition n_trees.h:169
Structure for a POINT2D in the 2D space.
Definition n_trees.h:101
Structure for a POINT3D in the 3D space.
Definition n_trees.h:110
structure of a quad tree
Definition n_trees.h:146
structure of a quad tree node
Definition n_trees.h:126
structure of a TREE
Definition n_trees.h:64
structure of a n-ary TREE node
Definition n_trees.h:50
Union to store the coordinate values.
Definition n_trees.h:94
union of the possibles data values of a TREE node
Definition n_trees.h:28
Simple 3D movement simulation.
Common headers and low-level functions & define.
Hash functions and table.
List structures and definitions.
Generic log system.
N_STR and string function declaration.