Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
n_trees.c
Go to the documentation of this file.
1
8#include <stdlib.h>
9#include <string.h>
10#include <pthread.h>
11
12#include "nilorea/n_common.h"
13#include "nilorea/n_log.h"
14#include "nilorea/n_str.h"
15#include "nilorea/n_trees.h"
16
22 TREE* tree = NULL;
23 Malloc(tree, TREE, 1);
24 __n_assert(tree, n_log(LOG_ERR, "Failed to allocate memory for tree.\n"); return NULL;);
25
26 tree->root = NULL;
27 tree->nb_nodes = 0;
28 tree->height = 0;
29 pthread_rwlock_init(&(tree->rwlock), NULL);
30
31 return tree;
32}
33
40TREE_NODE* tree_create_node(NODE_DATA value, void (*destroy_func)(void* ptr)) {
41 TREE_NODE* node = (TREE_NODE*)malloc(sizeof(TREE_NODE));
42 if (node == NULL) {
43 n_log(LOG_ERR, "Failed to allocate memory for tree node.\n");
44 return NULL;
45 }
46
47 node->data = value;
48 node->destroy_func = destroy_func;
49 node->parent_list_node = NULL;
50 node->parent = NULL;
51 node->children = new_generic_list(MAX_LIST_ITEMS);
52
53 return node;
54}
55
63 if (parent == NULL || child == NULL) {
64 return FALSE;
65 }
66
67 if (parent->children == NULL) {
68 parent->children = new_generic_list(MAX_LIST_ITEMS);
69 __n_assert(parent->children, n_log(LOG_ERR, "Failed to create parent->children list"); return FALSE;);
70 }
71
72 LIST_NODE* node = new_list_node(child, child->destroy_func);
73 __n_assert(node, n_log(LOG_ERR, "Failed to create child node"); return FALSE;);
74
75 if (!list_node_push(parent->children, node)) {
76 if (node->destroy_func != NULL) {
77 node->destroy_func(node->ptr);
78 }
79 Free(node);
80 return FALSE;
81 }
82
83 child->parent_list_node = node;
84 child->parent = parent;
85
86 return TRUE;
87}
88
95int tree_delete_node(TREE* tree, TREE_NODE* node) {
96 if (tree == NULL || node == NULL) {
97 return FALSE;
98 }
99
100 // Recursively delete child nodes
101 LIST_NODE* child_node = node->children->start;
102 while (child_node) {
103 TREE_NODE* child = (TREE_NODE*)child_node->ptr;
104 tree_delete_node(tree, child);
105 child_node = child_node->next;
106 }
107
108 // Remove the node from its parent's child list, if applicable
109 if (node->parent && node->parent->children) {
111 }
112
113 // Free node data if necessary
114 if (node->destroy_func) {
115 node->destroy_func(node->data.value.ptr);
116 } else {
117 free(node->data.value.ptr);
118 }
119
120 // Free the node itself
121 free(node);
122 tree->nb_nodes--;
123
124 return TRUE;
125}
126
131void tree_destroy(TREE** tree) {
132 if (tree == NULL || *tree == NULL) {
133 return;
134 }
135
136 TREE_NODE* root = (*tree)->root;
137 if (root != NULL) {
138 tree_delete_node(*tree, root);
139 }
140
141 pthread_rwlock_destroy(&((*tree)->rwlock));
142 free(*tree);
143 *tree = NULL;
144}
145
153 return a.i - b.i;
154}
155
163 return (a.f > b.f) - (a.f < b.f);
164}
165
173 return (a.d > b.d) - (a.d < b.d);
174}
175
181 printf("%d", val.i);
182}
183
190 printf("%f", val.f);
191}
192
198 printf("%lf", val.d);
199}
200
206QUADTREE* create_quadtree(int coord_type) {
207 QUADTREE* qt = (QUADTREE*)malloc(sizeof(QUADTREE));
208 if (!qt) {
209 n_log(LOG_ERR, "Failed to allocate QUADTREE");
210 return NULL;
211 }
212
213 qt->coord_type = coord_type;
214 qt->root = NULL;
215
216 switch (coord_type) {
217 case COORD_INT:
218 qt->compare = compare_int;
219 qt->print = print_int;
220 break;
221 case COORD_FLOAT:
223 qt->print = print_float;
224 break;
225 case COORD_DOUBLE:
227 qt->print = print_double;
228 break;
229 }
230
231 return qt;
232}
233
242 QUADTREE_NODE* node = (QUADTREE_NODE*)malloc(sizeof(QUADTREE_NODE));
243 if (!node) {
244 n_log(LOG_ERR, "Failed to allocate QUADTREE_NODE");
245 return NULL;
246 }
247 node->x = x;
248 node->y = y;
249 node->data_ptr = data_ptr;
250 node->nw = NULL;
251 node->ne = NULL;
252 node->sw = NULL;
253 node->se = NULL;
254 return node;
255}
256
265void insert(QUADTREE* qt, QUADTREE_NODE** root, COORD_VALUE x, COORD_VALUE y, void* data_ptr) {
266 if (*root == NULL) {
267 *root = create_node(x, y, data_ptr);
268 return;
269 }
270
271 if (qt->compare(x, (*root)->x) < 0 && qt->compare(y, (*root)->y) < 0) {
272 insert(qt, &((*root)->sw), x, y, data_ptr);
273 } else if (qt->compare(x, (*root)->x) < 0 && qt->compare(y, (*root)->y) >= 0) {
274 insert(qt, &((*root)->nw), x, y, data_ptr);
275 } else if (qt->compare(x, (*root)->x) >= 0 && qt->compare(y, (*root)->y) < 0) {
276 insert(qt, &((*root)->se), x, y, data_ptr);
277 } else if (qt->compare(x, (*root)->x) >= 0 && qt->compare(y, (*root)->y) >= 0) {
278 insert(qt, &((*root)->ne), x, y, data_ptr);
279 }
280}
281
291 if (root == NULL || (qt->compare(root->x, x) == 0 && qt->compare(root->y, y) == 0)) {
292 return root;
293 }
294
295 if (qt->compare(x, root->x) < 0 && qt->compare(y, root->y) < 0) {
296 return search(qt, root->sw, x, y);
297 } else if (qt->compare(x, root->x) < 0 && qt->compare(y, root->y) >= 0) {
298 return search(qt, root->nw, x, y);
299 } else if (qt->compare(x, root->x) >= 0 && qt->compare(y, root->y) < 0) {
300 return search(qt, root->se, x, y);
301 } else if (qt->compare(x, root->x) >= 0 && qt->compare(y, root->y) >= 0) {
302 return search(qt, root->ne, x, y);
303 }
304
305 return NULL; // Should not reach here
306}
307
313 __n_assert(root, return);
314
315 free_quadtree(root->nw);
316 free_quadtree(root->ne);
317 free_quadtree(root->sw);
318 free_quadtree(root->se);
319
320 free(root);
321}
322
329OCTREE_NODE* create_octree_node(POINT3D point, void* data_ptr) {
330 OCTREE_NODE* node = (OCTREE_NODE*)malloc(sizeof(OCTREE_NODE));
331 if (!node) {
332 n_log(LOG_ERR, "Failed to allocate OCTREE_NODE");
333 return NULL;
334 }
335
336 node->point = point;
337 node->data_ptr = data_ptr;
338 for (int i = 0; i < 8; i++) {
339 node->children[i] = NULL;
340 }
341
342 return node;
343}
344
351 OCTREE* octree = (OCTREE*)malloc(sizeof(OCTREE));
352 if (!octree) {
353 n_log(LOG_ERR, "Failed to allocate OCTREE\n");
354 return NULL;
355 }
356
357 octree->root = NULL;
358 octree->coord_type = type;
359
360 return octree;
361}
362
370int determine_octant(POINT3D point, POINT3D center, int type) {
371 int octant = 0;
372 if (type == COORD_INT) {
373 if (point.x.i >= center.x.i) octant |= 4;
374 if (point.y.i >= center.y.i) octant |= 2;
375 if (point.z.i >= center.z.i) octant |= 1;
376 } else if (type == COORD_FLOAT) {
377 if (point.x.f >= center.x.f) octant |= 4;
378 if (point.y.f >= center.y.f) octant |= 2;
379 if (point.z.f >= center.z.f) octant |= 1;
380 } else if (type == COORD_DOUBLE) {
381 if (point.x.d >= center.x.d) octant |= 4;
382 if (point.y.d >= center.y.d) octant |= 2;
383 if (point.z.d >= center.z.d) octant |= 1;
384 }
385 return octant;
386}
387
395void insert_octree_node(OCTREE_NODE* node, POINT3D point, void* data_ptr, int type) {
396 int octant = determine_octant(point, node->point, type);
397 if (!node->children[octant]) {
398 node->children[octant] = create_octree_node(point, data_ptr);
399 } else {
400 insert_octree_node(node->children[octant], point, data_ptr, type);
401 }
402}
403
410void insert_octree(OCTREE* octree, POINT3D point, void* data_ptr) {
411 if (!octree->root) {
412 octree->root = create_octree_node(point, data_ptr);
413 } else {
414 insert_octree_node(octree->root, point, data_ptr, octree->coord_type);
415 }
416}
417
423 if (node) {
424 for (int i = 0; i < 8; i++) {
425 free_octree_node(node->children[i]);
426 }
427 free(node);
428 }
429}
430
435void free_octree(OCTREE* octree) {
436 if (octree) {
437 free_octree_node(octree->root);
438 free(octree);
439 }
440}
#define Malloc(__ptr, __struct, __size)
Malloc Handler to get errors and set to 0.
Definition n_common.h:187
#define __n_assert(__ptr, __ret)
macro to assert things
Definition n_common.h:258
#define Free(__ptr)
Free Handler to get errors.
Definition n_common.h:242
void * ptr
void pointer to store
Definition n_list.h:26
LIST_NODE * start
pointer to the start of the list
Definition n_list.h:46
void(* destroy_func)(void *ptr)
pointer to destructor function if any, else NULL
Definition n_list.h:29
struct LIST_NODE * next
pointer to the next node
Definition n_list.h:32
LIST_NODE * new_list_node(void *ptr, void(*destructor)(void *ptr))
Allocate a new node to link in a list.
Definition n_list.c:38
void * remove_list_node_f(LIST *list, LIST_NODE *node)
Internal function called each time we need to get a node out of a list.
Definition n_list.c:57
#define MAX_LIST_ITEMS
flag to pass to new_generic_list for the maximum possible number of item in a list
Definition n_list.h:55
int list_node_push(LIST *list, LIST_NODE *node)
Add a filled node to the end of the list.
Definition n_list.c:96
Structure of a generic list node.
Definition n_list.h:24
#define n_log(__LEVEL__,...)
Logging function wrapper to get line and func.
Definition n_log.h:69
#define LOG_ERR
error conditions
Definition n_log.h:56
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
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
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
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
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
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
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
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
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 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
Common headers and low-level functions & define.
Generic log system.
N_STR and string function declaration.
int determine_octant(POINT3D point, POINT3D center, int type)
function to determine the octant for the given point relative to the node
Definition n_trees.c:370
void insert_octree_node(OCTREE_NODE *node, POINT3D point, void *data_ptr, int type)
recursive function to insert a point into the OCTREE
Definition n_trees.c:395
void print_int(COORD_VALUE val)
 
Definition n_trees.c:180
int compare_float(COORD_VALUE a, COORD_VALUE b)
float comparison function
Definition n_trees.c:162
int compare_double(COORD_VALUE a, COORD_VALUE b)
double comparison functions
Definition n_trees.c:172
void print_double(COORD_VALUE val)
 
Definition n_trees.c:197
int compare_int(COORD_VALUE a, COORD_VALUE b)
int comparison function
Definition n_trees.c:152
void print_float(COORD_VALUE val)
 
Definition n_trees.c:189
trees module headers