MGE General C Library - API Documentation v1.8.0
Library of general C functions.
mge-bstree.h
Go to the documentation of this file.
1
16/* **********************************************************************
17 * *
18 * Changelog *
19 * *
20 * Date Author Version Description *
21 * *
22 * 05/11/2015 MG 1.0.1 First release. *
23 * 06/11/2015 MG 1.0.2 Elevate errno defs to listsandsorts.h. *
24 * 16/07/2016 MG 1.0.3 Move towards kernel coding style. *
25 * 17/07/2016 MG 1.0.4 Remove function prototype comments. *
26 * 21/01/2017 MG 1.0.5 listsandsorts.h mentioned above has *
27 * been replaced with mgeerrno.h. *
28 * 22/03/2017 MG 1.0.6 Added node trace function prototype and *
29 * struct. *
30 * 03/04/2017 MG 1.0.7 Add bst struct, cre_bst & del_bst() *
31 * prototypes. *
32 * 04/11/2017 MG 1.0.8 Add Doxygen comments. *
33 * 09/11/2017 MG 1.0.9 Add SPDX license tag. *
34 * 02/01/2018 MG 1.0.10 Move to new source directory structure. *
35 * 02/06/2018 MG 1.0.11 Add node and counter totals to the tree *
36 * struct. *
37 * 08/06/2019 MG 1.0.12 clang-format coding style changes. *
38 * 03/12/2021 MG 1.0.13 Tighten SPDX tag. *
39 * 16/09/2022 MG 1.0.14 New name for portability.h *
40 * Rename to add namespace. *
41 * Add stddef.h for size_t. *
42 * Improve member comments. *
43 * Move test tracing elements to internal *
44 * header, they are not part of the API. *
45 * *
46 ************************************************************************
47 */
48
49#ifndef MGE_BSTREE_H
50#define MGE_BSTREE_H
51
53
54#include <stddef.h>
55
57
58#define BST_NODES_UNIQUE 1
59#define BST_NODES_DUPLICATES 0
62struct bstreenode {
63 void *object;
64 int count;
71};
72
74struct bstree {
75 struct bstreenode *root;
76 int unique;
80 int (*comp)(const void *, const void *);
84};
85
86struct bstree *cre_bst(int unique, int (*comp)(const void *, const void *));
87
88struct bstree *add_bst_node(struct bstree *tree, const void *object,
89 size_t objsize);
90
91void *find_bst_node(const struct bstree *tree, const void *searchobj);
92
93int get_counter_bst_node(const struct bstree *tree, const void *searchobj);
94
95void *find_next_bst_node(const struct bstree *tree, const void *searchobj);
96
97void *find_prev_bst_node(const struct bstree *tree, const void *searchobj);
98
99void *upd_bst_node(const struct bstree *tree, const void *updobj,
100 size_t objsize);
101
102struct bstree *del_bst_node(struct bstree *tree, const void *searchobj);
103
104struct bstree *del_bst(struct bstree *tree);
105
107
108#endif /* ndef MGE_BSTREE_H */
void * upd_bst_node(const struct bstree *tree, const void *updobj, size_t objsize)
Update a node's object.
Definition: bstree.c:581
struct bstree * del_bst_node(struct bstree *tree, const void *searchobj)
Delete a node.
Definition: bstree.c:650
struct bstree * del_bst(struct bstree *tree)
Delete a bst.
Definition: bstree.c:773
void * find_next_bst_node(const struct bstree *tree, const void *searchobj)
Find the next node.
Definition: bstree.c:451
struct bstree * cre_bst(int unique, int(*comp)(const void *, const void *))
Create a binary search tree.
Definition: bstree.c:159
void * find_prev_bst_node(const struct bstree *tree, const void *searchobj)
Find the previous node.
Definition: bstree.c:516
void * find_bst_node(const struct bstree *tree, const void *searchobj)
Find an exact object match.
Definition: bstree.c:330
int get_counter_bst_node(const struct bstree *tree, const void *searchobj)
Get the counter for a node.
Definition: bstree.c:390
struct bstree * add_bst_node(struct bstree *tree, const void *object, size_t objsize)
Add a node to a binary search tree.
Definition: bstree.c:208
Header file to ease portability.
#define BEGIN_C_DECLS
BEGIN_C_DECLS should be used at the beginning of declarations so that C++ compilers don't mangle thei...
Definition: mge-portability.h:48
#define END_C_DECLS
Use END_C_DECLS at the end of C declarations.
Definition: mge-portability.h:52
Binary search tree.
Definition: mge-bstree.h:74
int unique
Uniqueness of nodes.
Definition: mge-bstree.h:76
int node_total
Number of nodes in the tree.
Definition: mge-bstree.h:79
int count_total
Sum of all node counters.
Definition: mge-bstree.h:78
int(* comp)(const void *, const void *)
Comparison function.
Definition: mge-bstree.h:80
struct bstreenode * root
The root node of the tree.
Definition: mge-bstree.h:75
Binary search tree node.
Definition: mge-bstree.h:62
void * object
The object attached to the node.
Definition: mge-bstree.h:63
struct bstreenode * childgreater
Child node greater than this node.
Definition: mge-bstree.h:69
int count
The node counter.
Definition: mge-bstree.h:64
struct bstreenode * childless
Child node less than this node.
Definition: mge-bstree.h:68