MGE General C Library - Full Internal Documentation  v1.7.4
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
62 struct bstreenode {
63  void *object;
64  int count;
71 };
72 
74 struct bstree {
75  struct bstreenode *root;
76  int unique;
79  int node_total;
80  int (*comp)(const void *, const void *);
84 };
85 
86 struct bstree *cre_bst(int unique, int (*comp)(const void *, const void *));
87 
88 struct bstree *add_bst_node(struct bstree *tree, const void *object,
89  size_t objsize);
90 
91 void *find_bst_node(const struct bstree *tree, const void *searchobj);
92 
93 int get_counter_bst_node(const struct bstree *tree, const void *searchobj);
94 
95 void *find_next_bst_node(const struct bstree *tree, const void *searchobj);
96 
97 void *find_prev_bst_node(const struct bstree *tree, const void *searchobj);
98 
99 void *upd_bst_node(const struct bstree *tree, const void *updobj,
100  size_t objsize);
101 
102 struct bstree *del_bst_node(struct bstree *tree, const void *searchobj);
103 
104 struct 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
void * find_next_bst_node(const struct bstree *tree, const void *searchobj)
Find the next node.
Definition: bstree.c:451
void * find_bst_node(const struct bstree *tree, const void *searchobj)
Find an exact object match.
Definition: bstree.c:330
struct bstree * del_bst_node(struct bstree *tree, const void *searchobj)
Delete a node.
Definition: bstree.c:650
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
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
struct bstree * del_bst(struct bstree *tree)
Delete a bst.
Definition: bstree.c:773
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