MGE General C Library - Full Internal Documentation v1.8.4
Library of general C functions.
|
Builds, searches and releases a binary search tree. More...
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "internal.h"
#include <libmgec/mge-bstree.h>
#include <libmgec/mge-errno.h>
Functions | |
static struct bstreenode * | add_node (struct bstreenode *currentnode, const void *object, size_t objsize, struct bstree *tree) |
Add a binary search tree node with data of 'object' and using object comparison function of 'comp'. | |
static void * | find_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *)) |
Find exact object match. | |
static int | get_counter_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *)) |
Find exact object match. | |
static void * | find_next_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *)) |
Find and return the next object. | |
static void * | find_prev_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *)) |
Find and return the previous object. | |
static void * | upd_node (struct bstreenode *currentnode, const void *updobj, size_t objsize, int(*comp)(const void *, const void *)) |
Update the object. | |
static struct bstreenode * | del_node (struct bstreenode *currentnode, const void *searchobj, struct bstree *tree) |
Delete node. | |
static struct bstreenode * | free_bstree (struct bstreenode *currentnode) |
Free memory allocated to the bstree. | |
static struct bstreenode * | free_bst_node (struct bstreenode *currentnode) |
Free memory allocated to the node. | |
static struct bstobjcoord * | find_next_node_trace (const struct bstreenode *currentnode, struct bstobjcoord *searchobj, int(*comp)(const void *, const void *)) |
Find and return the next object and it's coordinates. | |
struct bstree * | cre_bst (int unique, int(*comp)(const void *, const void *)) |
Create a binary search tree. | |
struct bstree * | add_bst_node (struct bstree *tree, const void *object, size_t objsize) |
Add a node to a binary search tree. | |
void * | find_bst_node (const struct bstree *tree, const void *searchobj) |
Find an exact object match. | |
int | get_counter_bst_node (const struct bstree *tree, const void *searchobj) |
Get the counter for a node. | |
void * | find_next_bst_node (const struct bstree *tree, const void *searchobj) |
Find the next node. | |
void * | find_prev_bst_node (const struct bstree *tree, const void *searchobj) |
Find the previous node. | |
void * | upd_bst_node (const struct bstree *tree, const void *updobj, size_t objsize) |
Update a node's object. | |
struct bstree * | del_bst_node (struct bstree *tree, const void *searchobj) |
Delete a node. | |
struct bstree * | del_bst (struct bstree *tree) |
Delete a bst. | |
struct bstobjcoord * | find_next_bst_node_trace (const struct bstree *tree, struct bstobjcoord *searchobj) |
Find and return the next object and it's coordinates in the bst 'tree'. | |
Builds, searches and releases a binary search tree.
This implementation supports object independence by using a comparison function which conforms to the prototype:-
int (*comp)(const void *, const void *)
and which returns the value of:-
< 0 if the first parameter is less than the second,
0 if they are equal and
> 0 if the first is greater than the second.
In fact, the same as strcmp().
Released under the GPLv3 only.
SPDX-License-Identifier: GPL-3.0-only
Add a node to a binary search tree.
Attempts to add a node to a binary search tree. If the node exists and unique is true for this tree, an error is generated, if unique is false then the node counter is incremented. On error mge_errno is set and NULL is returned but the bst will remain as before the failed add. Hence it is important to preserve the pointer to the tree across this function.
tmp_tree = add_bst_node(tree, object, objsize); if (tmp_tree == NULL) { ... error handling return error; } tree = tmp_tree;
tree | The tree to add to. |
object | The object to add. |
objsize | The size of the object. |
|
static |
Add a binary search tree node with data of 'object' and using object comparison function of 'comp'.
Node uniqueness is defined by the unique parameter. Errors - mge_errno will be set as required.
currentnode | - On call from user code is a pointer to the root node or NULL if tree not yet started. Within the function and in recursion it is the node being processed. |
object | The object to add. |
objsize | The size of the object. |
tree | The tree to add to. |
struct bstree * cre_bst | ( | int | unique, |
int(*)(const void *, const void *) | comp | ||
) |
Create a binary search tree.
Creates a new binary search tree object which must eventually be freed by del_bst(). On error mge_errno is set.
unique | If set to true (1) then attempting to add a second identical node will generate an error. If set to false (0) then adding identical nodes increments the node counter. |
comp | A pointer to the comparison function to be used. This implementation supports object independence by using a comparison function which conforms to the prototype:-and which returns the value of:- In fact, the same as strcmp(). |
Delete a bst.
Delete a binary search tree.
tree | The bst to delete. |
Delete a node.
Delete a node in the bst 'tree'. Re-links any children. If the node counter is > 1 then duplicates are allowed and the counter is decremented instead of deleting the node. On error mge_errno will be set.
tree | The bst to search. |
searchobj | The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
|
static |
Delete node.
Re-links any children. If the node counter is > 1 then duplicates are allowed and the counter is decremented instead of deleting the node. Errors - mge_errno will be 0 on sucess or set as required.
currentnode | - On invocation from user code this is the root node. |
searchobj | - The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
tree | The bst to search. |
void * find_bst_node | ( | const struct bstree * | tree, |
const void * | searchobj | ||
) |
Find an exact object match.
Find an exact object match in the bst 'tree'. On error mge_errno will be set.
tree | The bst to search. |
searchobj | The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
void * find_next_bst_node | ( | const struct bstree * | tree, |
const void * | searchobj | ||
) |
Find the next node.
Find the next node in the bst and return the object. On error mge_errno will be set.
tree | The bst to search. |
searchobj | The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
struct bstobjcoord * find_next_bst_node_trace | ( | const struct bstree * | tree, |
struct bstobjcoord * | searchobj | ||
) |
Find and return the next object and it's coordinates in the bst 'tree'.
This is only really useful for testing purposes where this function can be used to verify the tree coordinates of nodes. On error mge_errno will be set.
tree | The bst to search. |
searchobj | The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
|
static |
Find and return the next object.
Errors - mge_errno will be set as required.
currentnode | - On invocation from user code this is the root node. |
searchobj | - The object to start from. It does not need to be a fully populated object nor does the object need to exist. It only needs enough information to support the comparison function. E.g. a key. |
comp | A pointer to the comparison function to be used. |
|
static |
Find and return the next object and it's coordinates.
This is only really useful for testing purposes where this function can be used to verify the tree coordinates of nodes. Errors - NULL will be returned and mge_errno will be set as required.
currentnode | - On invocation from user code this is the root node. |
searchobj | - The trace object to start from. It does not need to be a fully populated object nor does the object need to exist. It only needs enough information to support the comparison function. E.g. a key. |
comp | A pointer to the comparison function to be used. |
|
static |
Find exact object match.
Errors - mge_errno will be set as required.
currentnode | - On invocation from user code this is the root node. |
searchobj | - The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
comp | A pointer to the comparison function to be used. |
void * find_prev_bst_node | ( | const struct bstree * | tree, |
const void * | searchobj | ||
) |
Find the previous node.
Find and return the object attached to the previous node in the bst 'tree'. On error mge_errno will be set.
tree | The bst to search. |
searchobj | The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
|
static |
Find and return the previous object.
Errors - mge_errno will be set as required.
currentnode | - On invocation from user code this is the root node. |
searchobj | - The object to start from. It does not need to be a fully populated object nor does the object need to exist. It only needs enough information to support the comparison function. E.g. a key. |
comp | A pointer to the comparison function to be used. |
|
static |
Free memory allocated to the node.
(Both node and object).
currentnode | The node to free. |
|
static |
Free memory allocated to the bstree.
Walks the tree deleting nodes.
currentnode | The root node. |
int get_counter_bst_node | ( | const struct bstree * | tree, |
const void * | searchobj | ||
) |
Get the counter for a node.
Get the node counter for an object in the bst 'tree'. On error mge_errno will be set.
tree | The bst to search. |
searchobj | The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
|
static |
Find exact object match.
Returns the number of matches. Errors - mge_errno will be set as required.
currentnode | - On invocation from user code this is the root node. |
searchobj | - The object to find. It does not need to be a fully populated object. It only needs enough information to support the comparison function. E.g. a key. |
comp | A pointer to the comparison function to be used. |
void * upd_bst_node | ( | const struct bstree * | tree, |
const void * | updobj, | ||
size_t | objsize | ||
) |
Update a node's object.
Update the object in a node in the bst 'tree'. (This only makes sense if the object is carrying a payload.) On error mge_errno will be set.
tree | The bst to search. |
updobj | The object to update. The node is found and the existing object is replaced with the new object. |
objsize | The size of the new object. |
|
static |
Update the object.
(This only makes sense if the object is carrying a payload.) Errors - mge_errno will be set as required.
currentnode | - On invocation from user code this is the root node. |
updobj | - The object to update. The node is found and the existing object is replaced with the new object. |
objsize | The size of the new object. |
comp | A pointer to the comparison function to be used. |