n_trees.c

Go to the documentation of this file.

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#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);
    }
}