MGE General C Library - API Documentation  v1.4.1
Library of general C functions.
bstree.h File Reference

Binary search tree header file. More...

#include <portability.h>
Include dependency graph for bstree.h:
This graph shows which files directly or indirectly include this file:

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 bstreecre_bst (int unique, int(*comp)(const void *, const void *))
 Create a binary search tree. More...
 
struct bstreeadd_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 bstreedel_bst_node (struct bstree *tree, const void *searchobj)
 Delete a node. More...
 
struct bstreedel_bst (struct bstree *tree)
 Delete a bst. More...
 
struct bstobjcoordfind_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...
 

Detailed Description

Binary search tree header file.

Header file for binary search trees in the libmgec shared library.

Author
Copyright (C) 2015-2019 Mark Grant

Released under the GPLv3 only.
SPDX-License-Identifier: GPL-3.0

Version
v1.0.12 ==== 08/06/2019

Macro Definition Documentation

◆ BST_NODES_DUPLICATES

#define BST_NODES_DUPLICATES   0

BST allows duplicate nodes.

◆ BST_NODES_UNIQUE

#define BST_NODES_UNIQUE   1

BST allows unique nodes only.

Function Documentation

◆ add_bst_node()

struct bstree* add_bst_node ( struct bstree tree,
const void *  object,
size_t  objsize 
)

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;
Parameters
treeThe tree to add to.
objectThe object to add.
objsizeThe size of the object.
Returns
A pointer to the binary tree 'tree' or NULL on error.

◆ cre_bst()

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.

Parameters
uniqueIf 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.
compA pointer to the comparison function to be used. 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().
Returns
A pointer to the newly created binary search tree or NULL on error.

◆ del_bst()

struct bstree* del_bst ( struct bstree tree)

Delete a bst.

Delete a binary search tree.

Parameters
treeThe bst to delete.
Returns
NULL

◆ del_bst_node()

struct bstree* del_bst_node ( struct bstree tree,
const void *  searchobj 
)

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.

Parameters
treeThe bst to search.
searchobjThe 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.
Returns
A pointer to the updated bst, or, NULL on error.

◆ find_bst_node()

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.

Parameters
treeThe bst to search.
searchobjThe 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.
Returns
A pointer to the object found in the node, (i.e. the fully populated object), or, NULL if not found or an error was encountered.

◆ find_next_bst_node()

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.

Parameters
treeThe bst to search.
searchobjThe 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.
Returns
A pointer to the next object found in the tree, (i.e. a fully populated object), or, NULL if not found or an error was encountered.

◆ find_next_bst_node_trace()

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.

Parameters
treeThe bst to search.
searchobjThe 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.
Returns
A pointer to the next coordinate object found in the tree, (i.e. a fully populated object), or, the actual node object will be NULL if not found. Returns NULL on error.

◆ find_prev_bst_node()

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.

Parameters
treeThe bst to search.
searchobjThe 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.
Returns
A pointer to the preceding object in the tree, (i.e. a fully populated object), or, NULL if not found or an error was encountered.

◆ get_counter_bst_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.

Parameters
treeThe bst to search.
searchobjThe 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.
Returns
The number of times add_bst_node() was asked to create this node, or, 0 if not found, or, -mge_errno on error.

◆ upd_bst_node()

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.

Parameters
treeThe bst to search.
updobjThe object to update. The node is found and the existing object is replaced with the new object.
objsizeThe size of the new object.
Returns
A pointer to the new object, or, NULL if not found or error.