MGE General C Library - Full Internal Documentation  v1.4.1
Library of general C functions.
bstree.c File Reference

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>
Include dependency graph for bstree.c:

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...
 
static struct bstreenodeadd_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'. More...
 
void * find_bst_node (const struct bstree *tree, const void *searchobj)
 Find an exact object match. More...
 
static void * find_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *))
 Find exact object match. More...
 
int get_counter_bst_node (const struct bstree *tree, const void *searchobj)
 Get the counter for a node. More...
 
static int get_counter_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *))
 Find exact object match. More...
 
void * find_next_bst_node (const struct bstree *tree, const void *searchobj)
 Find the next node. More...
 
static void * find_next_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *))
 Find and return the next object. More...
 
void * find_prev_bst_node (const struct bstree *tree, const void *searchobj)
 Find the previous node. More...
 
static void * find_prev_node (const struct bstreenode *currentnode, const void *searchobj, int(*comp)(const void *, const void *))
 Find and return the previous object. More...
 
void * upd_bst_node (const struct bstree *tree, const void *updobj, size_t objsize)
 Update a node's object. More...
 
static void * upd_node (struct bstreenode *currentnode, const void *updobj, size_t objsize, int(*comp)(const void *, const void *))
 Update the object. More...
 
struct bstreedel_bst_node (struct bstree *tree, const void *searchobj)
 Delete a node. More...
 
static struct bstreenodedel_node (struct bstreenode *currentnode, const void *searchobj, struct bstree *tree)
 Delete node. More...
 
struct bstreedel_bst (struct bstree *tree)
 Delete a bst. More...
 
static struct bstreenodefree_bstree (struct bstreenode *currentnode)
 Free memory allocated to the bstree. More...
 
static struct bstreenodefree_bst_node (struct bstreenode *currentnode)
 Free memory allocated to the node. 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...
 
static struct bstobjcoordfind_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. More...
 

Detailed Description

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().

Author
Copyright (C) 2015-2020 Mark Grant

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

Version
v1.1.9 ==== 20/07/2020

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.

◆ add_node()

static struct bstreenode* add_node ( struct bstreenode currentnode,
const void *  object,
size_t  objsize,
struct bstree tree 
)
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.

Parameters
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.
objectThe object to add.
objsizeThe size of the object.
treeThe tree to add to.
Returns
Returns NULL on error. On exit to user code a pointer to the root node. Within the function it is a pointer to the node being processed. On error the bst will remain as before the failed add. Hence it is important to preserve the pointer to the root node across this function.

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

◆ del_node()

static struct bstreenode* del_node ( struct bstreenode currentnode,
const void *  searchobj,
struct bstree tree 
)
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.

Parameters
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.
treeThe bst to search.
Returns
Returns to the calling function a pointer to the root node, or, NULL if it was the last remaining node which was deleted. Also returns NULL on some errors.

◆ 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_next_node()

static void* find_next_node ( const struct bstreenode currentnode,
const void *  searchobj,
int(*)(const void *, const void *)  comp 
)
static

Find and return the next object.

Errors - mge_errno will be set as required.

Parameters
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.
compA pointer to the comparison function to be used.
Returns
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_node_trace()

static struct bstobjcoord* find_next_node_trace ( const struct bstreenode currentnode,
struct bstobjcoord searchobj,
int(*)(const void *, const void *)  comp 
)
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.

Parameters
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.
compA pointer to the comparison function to be used.
Returns
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_node()

static void* find_node ( const struct bstreenode currentnode,
const void *  searchobj,
int(*)(const void *, const void *)  comp 
)
static

Find exact object match.

Errors - mge_errno will be set as required.

Parameters
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.
compA pointer to the comparison function to be used.
Returns
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_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.

◆ find_prev_node()

static void* find_prev_node ( const struct bstreenode currentnode,
const void *  searchobj,
int(*)(const void *, const void *)  comp 
)
static

Find and return the previous object.

Errors - mge_errno will be set as required.

Parameters
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.
compA pointer to the comparison function to be used.
Returns
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.

◆ free_bst_node()

static struct bstreenode* free_bst_node ( struct bstreenode currentnode)
static

Free memory allocated to the node.

(Both node and object).

Parameters
currentnodeThe node to free.
Returns
NULL

◆ free_bstree()

static struct bstreenode* free_bstree ( struct bstreenode currentnode)
static

Free memory allocated to the bstree.

Walks the tree deleting nodes.

Parameters
currentnodeThe root node.
Returns
NULL

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

◆ get_counter_node()

static int get_counter_node ( const struct bstreenode currentnode,
const void *  searchobj,
int(*)(const void *, const void *)  comp 
)
static

Find exact object match.

Returns the number of matches. Errors - mge_errno will be set as required.

Parameters
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.
compA pointer to the comparison function to be used.
Returns
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.

◆ upd_node()

static void* upd_node ( struct bstreenode currentnode,
const void *  updobj,
size_t  objsize,
int(*)(const void *, const void *)  comp 
)
static

Update the object.

(This only makes sense if the object is carrying a payload.) Errors - mge_errno will be set as required.

Parameters
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.
objsizeThe size of the new object.
compA pointer to the comparison function to be used.
Returns
Returns a pointer to the new object, or, NULL if not found or error.