src/n_trees.c

Tree functions. More...

Functions

	Name
void	print_int(COORD_VALUE val) print int function
void	print_float(COORD_VALUE val) print float function
void	print_double(COORD_VALUE val) print double function
void	insert_octree_node(OCTREE_NODE * node, POINT3D point, void * data_ptr, int type) recursive function to insert a point into the OCTREE
int	determine_octant(POINT3D point, POINT3D center, int type) function to determine the octant for the given point relative to the node
int	compare_int(COORD_VALUE a, COORD_VALUE b) int comparison function
int	compare_float(COORD_VALUE a, COORD_VALUE b) float comparison function
int	compare_double(COORD_VALUE a, COORD_VALUE b) double comparison functions

Detailed Description

Tree functions.

Author: Castagnier Mickael

Version: 1.0

Date: 07/08/2024

Functions Documentation

function print_int

void print_int(
    COORD_VALUE val
)

print int function

Parameters:

• val the COORD_VALUE from which to read the int to print

function print_float

void print_float(
    COORD_VALUE val
)

print float function

Parameters:

• val the COORD_VALUE from which to read the float to print

function print_double

void print_double(
    COORD_VALUE val
)

print double function

Parameters:

• val the COORD_VALUE from which to read the double to print

function insert_octree_node

void insert_octree_node(
    OCTREE_NODE * node,
    POINT3D point,
    void * data_ptr,
    int type
)

recursive function to insert a point into the OCTREE

Parameters:

• node the target OCTREE_NODE *node
• point the POINT3D point to insert
• data_ptr eventual private data forthe point, can be NULL
• type the type of coordinate used by the OCTREE (COORD_INT,COORD_FLOAT,COORD_DOUBLE)

function determine_octant

int determine_octant(
    POINT3D point,
    POINT3D center,
    int type
)

function to determine the octant for the given point relative to the node

Parameters:

• point POINT3D coordinates of the target point
• center POINT3D coordinates of the center point
• type the type of coordinate used by the OCTREE (COORD_INT,COORD_FLOAT,COORD_DOUBLE)

Return: octant index from 0 to 7

function compare_int

int compare_int(
    COORD_VALUE a,
    COORD_VALUE b
)

int comparison function

Parameters:

• a COORD_VALUE int element to compare
• b COORD_VALUE int element to compare

Return: -1, 0, or 1 (less than, equal to, greater than)

function compare_float

int compare_float(
    COORD_VALUE a,
    COORD_VALUE b
)

float comparison function

Parameters:

• a COORD_VALUE float element to compare
• b COORD_VALUE float element to compare

Return: -1, 0, or 1 (less than, equal to, greater than)

function compare_double

int compare_double(
    COORD_VALUE a,
    COORD_VALUE b
)

double comparison functions

Parameters:

• a COORD_VALUE double element to compare
• b COORD_VALUE double element to compare

Return: -1, 0, or 1 (less than, equal to, greater than)

Source code

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * permissions and limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 */


#include <stdlib.h>
#include <string.h>
#include <pthread.h>

#include "nilorea/n_common.h"
#include "nilorea/n_log.h"
#include "nilorea/n_str.h"
#include "nilorea/n_trees.h"

TREE* new_tree() {
    TREE* tree = NULL;
    Malloc(tree, TREE, 1);
    __n_assert(tree, n_log(LOG_ERR, "Failed to allocate memory for tree"); return NULL;);

    tree->root = NULL;
    tree->nb_nodes = 0;
    tree->height = 0;
    pthread_rwlock_init(&(tree->rwlock), NULL);

    return tree;
}

TREE_NODE* tree_create_node(NODE_DATA value, void (*destroy_func)(void* ptr)) {
    TREE_NODE* node = (TREE_NODE*)malloc(sizeof(TREE_NODE));
    if (node == NULL) {
        n_log(LOG_ERR, "Failed to allocate memory for tree node");
        return NULL;
    }

    node->data = value;
    node->destroy_func = destroy_func;
    node->parent_list_node = NULL;
    node->parent = NULL;
    node->children = new_generic_list(MAX_LIST_ITEMS);
    if (!node->children) {
        Free(node);
        return NULL;
    }

    return node;
}

int tree_insert_child(TREE_NODE* parent, TREE_NODE* child) {
    if (parent == NULL || child == NULL) {
        return FALSE;
    }

    if (parent->children == NULL) {
        parent->children = new_generic_list(MAX_LIST_ITEMS);
        __n_assert(parent->children, n_log(LOG_ERR, "Failed to create parent->children list"); return FALSE;);
    }

    LIST_NODE* node = new_list_node(child, NULL);
    __n_assert(node, n_log(LOG_ERR, "Failed to create child node"); return FALSE;);

    if (!list_node_push(parent->children, node)) {
        if (node->destroy_func != NULL) {
            node->destroy_func(node->ptr);
        }
        Free(node);
        return FALSE;
    }

    child->parent_list_node = node;
    child->parent = parent;

    return TRUE;
}

int tree_delete_node(TREE* tree, TREE_NODE* node) {
    if (tree == NULL || node == NULL) {
        return FALSE;
    }

    // Recursively delete child nodes
    LIST_NODE* child_node = node->children->start;
    while (child_node) {
        LIST_NODE* next_node = child_node->next;
        TREE_NODE* child = (TREE_NODE*)child_node->ptr;
        tree_delete_node(tree, child);
        child_node = next_node;
    }
    list_destroy(&node->children);

    // Remove the node from its parent's child list, if applicable
    if (node->parent && node->parent->children) {
        remove_list_node_f(node->parent->children, node->parent_list_node);
    }

    // Free node data if necessary
    if (node->destroy_func) {
        node->destroy_func(node->data.value.ptr);
    }

    // Free the node itself
    free(node);
    tree->nb_nodes--;

    return TRUE;
}

void tree_destroy(TREE** tree) {
    if (tree == NULL || *tree == NULL) {
        return;
    }

    TREE_NODE* root = (*tree)->root;
    if (root != NULL) {
        tree_delete_node(*tree, root);
    }

    pthread_rwlock_destroy(&((*tree)->rwlock));
    free(*tree);
    *tree = NULL;
}

int compare_int(COORD_VALUE a, COORD_VALUE b) {
    return (a.i > b.i) - (a.i < b.i);
}

int compare_float(COORD_VALUE a, COORD_VALUE b) {
    return (a.f > b.f) - (a.f < b.f);
}

int compare_double(COORD_VALUE a, COORD_VALUE b) {
    return (a.d > b.d) - (a.d < b.d);
}

void print_int(COORD_VALUE val) {
    printf("%d", val.i);
}


void print_float(COORD_VALUE val) {
    printf("%f", val.f);
}

void print_double(COORD_VALUE val) {
    printf("%lf", val.d);
}

QUADTREE* create_quadtree(int coord_type) {
    QUADTREE* qt = (QUADTREE*)calloc(1, sizeof(QUADTREE));
    if (!qt) {
        n_log(LOG_ERR, "Failed to allocate QUADTREE");
        return NULL;
    }

    qt->coord_type = coord_type;
    qt->root = NULL;

    switch (coord_type) {
        case COORD_INT:
            qt->compare = compare_int;
            qt->print = print_int;
            break;
        case COORD_FLOAT:
            qt->compare = compare_float;
            qt->print = print_float;
            break;
        case COORD_DOUBLE:
            qt->compare = compare_double;
            qt->print = print_double;
            break;
        default:
            qt->compare = NULL;
            qt->print = NULL;
            n_log(LOG_ERR, "Unknown coord_type %d", coord_type);
            Free(qt);
            return NULL;
    }

    return qt;
}

QUADTREE_NODE* create_node(COORD_VALUE x, COORD_VALUE y, void* data_ptr) {
    QUADTREE_NODE* node = (QUADTREE_NODE*)malloc(sizeof(QUADTREE_NODE));
    if (!node) {
        n_log(LOG_ERR, "Failed to allocate QUADTREE_NODE");
        return NULL;
    }
    node->x = x;
    node->y = y;
    node->data_ptr = data_ptr;
    node->nw = NULL;
    node->ne = NULL;
    node->sw = NULL;
    node->se = NULL;
    return node;
}

void insert(QUADTREE* qt, QUADTREE_NODE** root, COORD_VALUE x, COORD_VALUE y, void* data_ptr) {
    __n_assert(qt, return);

    if (*root == NULL) {
        *root = create_node(x, y, data_ptr);
        __n_assert(*root, n_log(LOG_ERR, "Failed to create node"); return);
        return;
    }

    if (qt->compare(x, (*root)->x) < 0 && qt->compare(y, (*root)->y) < 0) {
        insert(qt, &((*root)->sw), x, y, data_ptr);
    } else if (qt->compare(x, (*root)->x) < 0 && qt->compare(y, (*root)->y) >= 0) {
        insert(qt, &((*root)->nw), x, y, data_ptr);
    } else if (qt->compare(x, (*root)->x) >= 0 && qt->compare(y, (*root)->y) < 0) {
        insert(qt, &((*root)->se), x, y, data_ptr);
    } else if (qt->compare(x, (*root)->x) >= 0 && qt->compare(y, (*root)->y) >= 0) {
        insert(qt, &((*root)->ne), x, y, data_ptr);
    }
}

QUADTREE_NODE* search(QUADTREE* qt, QUADTREE_NODE* root, COORD_VALUE x, COORD_VALUE y) {
    if (root == NULL || (qt->compare(root->x, x) == 0 && qt->compare(root->y, y) == 0)) {
        return root;
    }

    if (qt->compare(x, root->x) < 0 && qt->compare(y, root->y) < 0) {
        return search(qt, root->sw, x, y);
    } else if (qt->compare(x, root->x) < 0 && qt->compare(y, root->y) >= 0) {
        return search(qt, root->nw, x, y);
    } else if (qt->compare(x, root->x) >= 0 && qt->compare(y, root->y) < 0) {
        return search(qt, root->se, x, y);
    } else if (qt->compare(x, root->x) >= 0 && qt->compare(y, root->y) >= 0) {
        return search(qt, root->ne, x, y);
    }

    return NULL;  // Should not reach here
}

void free_quadtree(QUADTREE_NODE* root) {
    __n_assert(root, return);

    free_quadtree(root->nw);
    free_quadtree(root->ne);
    free_quadtree(root->sw);
    free_quadtree(root->se);

    free(root);
}

OCTREE_NODE* create_octree_node(POINT3D point, void* data_ptr) {
    OCTREE_NODE* node = (OCTREE_NODE*)malloc(sizeof(OCTREE_NODE));
    if (!node) {
        n_log(LOG_ERR, "Failed to allocate OCTREE_NODE");
        return NULL;
    }

    node->point = point;
    node->data_ptr = data_ptr;
    for (int i = 0; i < 8; i++) {
        node->children[i] = NULL;
    }

    return node;
}

OCTREE* create_octree(int type) {
    OCTREE* octree = (OCTREE*)malloc(sizeof(OCTREE));
    if (!octree) {
        n_log(LOG_ERR, "Failed to allocate OCTREE");
        return NULL;
    }

    octree->root = NULL;
    octree->coord_type = type;

    return octree;
}

int determine_octant(POINT3D point, POINT3D center, int type) {
    int octant = 0;
    if (type == COORD_INT) {
        if (point.x.i >= center.x.i) octant |= 4;
        if (point.y.i >= center.y.i) octant |= 2;
        if (point.z.i >= center.z.i) octant |= 1;
    } else if (type == COORD_FLOAT) {
        if (point.x.f >= center.x.f) octant |= 4;
        if (point.y.f >= center.y.f) octant |= 2;
        if (point.z.f >= center.z.f) octant |= 1;
    } else if (type == COORD_DOUBLE) {
        if (point.x.d >= center.x.d) octant |= 4;
        if (point.y.d >= center.y.d) octant |= 2;
        if (point.z.d >= center.z.d) octant |= 1;
    }
    return octant;
}

void insert_octree_node(OCTREE_NODE* node, POINT3D point, void* data_ptr, int type) {
    int octant = determine_octant(point, node->point, type);
    if (!node->children[octant]) {
        node->children[octant] = create_octree_node(point, data_ptr);
    } else {
        insert_octree_node(node->children[octant], point, data_ptr, type);
    }
}

void insert_octree(OCTREE* octree, POINT3D point, void* data_ptr) {
    if (!octree->root) {
        octree->root = create_octree_node(point, data_ptr);
    } else {
        insert_octree_node(octree->root, point, data_ptr, octree->coord_type);
    }
}

void free_octree_node(OCTREE_NODE* node) {
    if (node) {
        for (int i = 0; i < 8; i++) {
            free_octree_node(node->children[i]);
        }
        free(node);
    }
}

void free_octree(OCTREE* octree) {
    if (octree) {
        free_octree_node(octree->root);
        free(octree);
    }
}