MGE General C Library - API Documentation
v1.3.5
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 "bstree-internal.h"
#include <bstree.h>
#include <mge-errno.h>
Functions | |
struct bstree * | cre_bst (int unique, int(*comp)(const void *, const void *)) |
Create a binary search tree. More... | |
struct bstree * | add_bst_node (struct bstree *tree, const void *object, size_t objsize) |
Add a node to a binary search tree. More... | |
void * | find_bst_node (const struct bstree *tree, const void *searchobj) |
Find an exact object match. More... | |
int | get_counter_bst_node (const struct bstree *tree, const void *searchobj) |
Get the counter for a node. More... | |
void * | find_next_bst_node (const struct bstree *tree, const void *searchobj) |
Find the next node. More... | |
void * | find_prev_bst_node (const struct bstree *tree, const void *searchobj) |
Find the previous node. More... | |
void * | upd_bst_node (const struct bstree *tree, const void *updobj, size_t objsize) |
Update a node's object. More... | |
struct bstree * | del_bst_node (struct bstree *tree, const void *searchobj) |
Delete a node. More... | |
struct bstree * | del_bst (struct bstree *tree) |
Delete a bst. More... | |
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'. More... | |
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
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. |
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. |
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. |
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. |
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. |
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. |