MGE General C Library - API Documentation
v1.6.8
Library of general C functions.
|
Binary search tree header file. More...
#include <portability.h>
Go to the source code of this file.
Data Structures | |
struct | bstobjcoord |
Node coordinates for test tracing. More... | |
struct | bstreenode |
Binary search tree node. More... | |
struct | bstree |
Binary search tree. More... | |
Macros | |
#define | BST_NODES_UNIQUE 1 |
BST allows unique nodes only. More... | |
#define | BST_NODES_DUPLICATES 0 |
BST allows duplicate nodes. More... | |
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... | |
Binary search tree header file.
Header file for binary search trees in the libmgec shared library.
Released under the GPLv3 only.
SPDX-License-Identifier: GPL-3.0-only
#define BST_NODES_DUPLICATES 0 |
BST allows duplicate nodes.
#define BST_NODES_UNIQUE 1 |
BST allows unique nodes 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. |
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. |