MGE General C Library - Full Internal Documentation  v1.6.8
Library of general C functions.
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  * *
40  ************************************************************************
41  */
42 
43 #ifndef BSTREE_H
44 #define BSTREE_H
45 
46 #include <portability.h>
47 
49 
50 #define BST_NODES_UNIQUE 1
51 #define BST_NODES_DUPLICATES 0
54 struct bstobjcoord {
55  void *object;
56  int count;
57  int xdir;
58  int ydir;
59 };
60 
62 struct bstreenode {
63  void *object;
64  int count;
67 };
68 
70 struct bstree {
71  struct bstreenode *root;
72  int unique;
74  int node_total;
75  int (*comp)(const void *, const void *);
76 };
77 
78 struct bstree *cre_bst(int unique, int (*comp)(const void *, const void *));
79 
80 struct bstree *add_bst_node(struct bstree *tree, const void *object,
81  size_t objsize);
82 
83 void *find_bst_node(const struct bstree *tree, const void *searchobj);
84 
85 int get_counter_bst_node(const struct bstree *tree, const void *searchobj);
86 
87 void *find_next_bst_node(const struct bstree *tree, const void *searchobj);
88 
89 void *find_prev_bst_node(const struct bstree *tree, const void *searchobj);
90 
91 void *upd_bst_node(const struct bstree *tree, const void *updobj,
92  size_t objsize);
93 
94 struct bstree *del_bst_node(struct bstree *tree, const void *searchobj);
95 
96 struct bstree *del_bst(struct bstree *tree);
97 
98 struct bstobjcoord *find_next_bst_node_trace(const struct bstree *tree,
99  struct bstobjcoord *searchobj);
100 
102 
103 #endif /* ndef BSTREE_H */
104 
void * upd_bst_node(const struct bstree *tree, const void *updobj, size_t objsize)
Update a node's object.
Definition: bstree.c:540
void * find_next_bst_node(const struct bstree *tree, const void *searchobj)
Find the next node.
Definition: bstree.c:410
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'.
Definition: bstree.c:790
void * find_bst_node(const struct bstree *tree, const void *searchobj)
Find an exact object match.
Definition: bstree.c:289
struct bstree * del_bst_node(struct bstree *tree, const void *searchobj)
Delete a node.
Definition: bstree.c:609
int get_counter_bst_node(const struct bstree *tree, const void *searchobj)
Get the counter for a node.
Definition: bstree.c:349
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:167
struct bstree * cre_bst(int unique, int(*comp)(const void *, const void *))
Create a binary search tree.
Definition: bstree.c:118
void * find_prev_bst_node(const struct bstree *tree, const void *searchobj)
Find the previous node.
Definition: bstree.c:475
struct bstree * del_bst(struct bstree *tree)
Delete a bst.
Definition: bstree.c:732
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: portability.h:47
#define END_C_DECLS
Use END_C_DECLS at the end of C declarations.
Definition: portability.h:51
Node coordinates for test tracing.
Definition: bstree.h:54
void * object
The object.
Definition: bstree.h:55
int xdir
The x coordinate.
Definition: bstree.h:57
int ydir
The y coordinate.
Definition: bstree.h:58
int count
The node counter.
Definition: bstree.h:56
Binary search tree.
Definition: bstree.h:70
int unique
Uniqueness of nodes.
Definition: bstree.h:72
int node_total
Number of nodes in the tree.
Definition: bstree.h:74
int count_total
Sum of all node counters.
Definition: bstree.h:73
int(* comp)(const void *, const void *)
Comparison function.
Definition: bstree.h:75
struct bstreenode * root
The root node of the tree.
Definition: bstree.h:71
Binary search tree node.
Definition: bstree.h:62
void * object
The object attached to the node.
Definition: bstree.h:63
struct bstreenode * childgreater
Child node greater than this.
Definition: bstree.h:66
int count
The node counter.
Definition: bstree.h:64
struct bstreenode * childless
Child node less than this.
Definition: bstree.h:65