libGimbal 0.2.0
C17-Based Extended Standard Library and Cross-Language Runtime Framework
Loading...
Searching...
No Matches
gimbal_nary_tree.h
Go to the documentation of this file.
1/*! \file
2 * \brief GblNaryTreeNode structure and related functions.
3 * \ingroup containers
4 *
5 * Public API for the GblNaryTree, intrusive tree node
6 * container type.
7 *
8 * \author Falco Girgis 2023, 2026
9 * \copyright MIT License
10 */
11
12#ifndef GIMBAL_NARY_TREE_H
13#define GIMBAL_NARY_TREE_H
14
15#include "../core/gimbal_ctx.h"
16
17#define GBL_NARY_TREE_NPOS GBL_NPOS
18#define GBL_NARY_TREE_ENTRY(node, structure, field) GBL_CONTAINER_OF(node, structure, field)
19#define GBL_NARY_TREE_TRAVERSAL_MASK(order, flags) ((order << 0x3) | (flags))
20
21#define GBL_SELF_TYPE GblNaryTreeNode
22
23GBL_DECLS_BEGIN
24
25GBL_FORWARD_DECLARE_STRUCT(GblNaryTreeNode);
26
27typedef GblBool (*GblNaryTreeIterFn)(const GblNaryTreeNode* pNode, void* pUd);
28
29typedef enum GBL_NARY_TREE_NODE_FLAGS {
30 GBL_NARY_TREE_NODE_FLAG_ROOT = 0x1,
31 GBL_NARY_TREE_NODE_FLAG_INTERNAL = 0x2,
32 GBL_NARY_TREE_NODE_FLAG_LEAF = 0x4,
33 GBL_NARY_TREE_NODE_FLAGS_ALL = 0x7
34} GBL_NARY_TREE_NODE_FLAGS;
35
36typedef enum GBL_NARY_TREE_TRAVERSAL_ORDER {
37 GBL_NARY_TREE_TRAVERSAL_ORDER_PRE,
38 GBL_NARY_TREE_TRAVERSAL_ORDER_IN,
39 GBL_NARY_TREE_TRAVERSAL_ORDER_POST,
40 GBL_NARY_TREE_TRAVERSAL_ORDER_LEVEL
41} GBL_NARY_TREE_TRAVERSAL_ORDER;
42
43/*! \brief Represents a single intrusive node within an N-Ary tree structure
44 *
45 * GblNaryTreeNode is a single node which is to be embedded within another
46 * structure, providing heirarchial relationships between its instances. As
47 * relationships are established between these instances, they become nodes
48 * comprising an aggregate tree structure.
49 *
50 * A single node contains only a pointer to its parent node plus a linked list of
51 * its child nodes, resulting in a minimal memory footprint. The API attempts to
52 * present psuedo list-style semantics for accessing ancestors, bases, siblings,
53 * and children by index; however, these are linked structures and such operations
54 * are of O(N) time complexity, requiring traversals for random access.
55 *
56 * \ingroup containers
57 */
58typedef struct GblNaryTreeNode {
59 struct GblNaryTreeNode* pParent; //!< Node's parent
60 struct GblNaryTreeNode* pChildFirst; //!< Node's first child (beginning of child linked list)
61 struct GblNaryTreeNode* pSiblingNext; //!< Node's next sibling (next entry of child linked list)
62} GblNaryTreeNode;
63
64GBL_EXPORT size_t GblNaryTree_size (GBL_CSELF) GBL_NOEXCEPT;
65GBL_EXPORT size_t GblNaryTree_width (GBL_CSELF, size_t depth) GBL_NOEXCEPT;
66GBL_EXPORT size_t GblNaryTree_height (GBL_CSELF) GBL_NOEXCEPT;
67GBL_EXPORT size_t GblNaryTree_depth (GBL_CSELF) GBL_NOEXCEPT;
68GBL_EXPORT size_t GblNaryTree_breadth (GBL_CSELF) GBL_NOEXCEPT;
69GBL_EXPORT size_t GblNaryTree_degree (GBL_CSELF) GBL_NOEXCEPT;
70GBL_EXPORT size_t GblNaryTree_arity (GBL_CSELF) GBL_NOEXCEPT;
71GBL_EXPORT GblFlags GblNaryTree_flags (GBL_CSELF) GBL_NOEXCEPT;
72
73GBL_EXPORT GblBool GblNaryTree_isConnected (GBL_CSELF) GBL_NOEXCEPT;
74GBL_EXPORT GblBool GblNaryTree_isRoot (GBL_CSELF) GBL_NOEXCEPT;
75GBL_EXPORT GblBool GblNaryTree_isInternal (GBL_CSELF) GBL_NOEXCEPT;
76GBL_EXPORT GblBool GblNaryTree_isLeaf (GBL_CSELF) GBL_NOEXCEPT;
77GBL_EXPORT GblBool GblNaryTree_isBalanced (GBL_CSELF) GBL_NOEXCEPT;
78GBL_EXPORT GblBool GblNaryTree_isParent (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
79GBL_EXPORT GblBool GblNaryTree_isAncestor (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
80GBL_EXPORT GblBool GblNaryTree_isSibling (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
81GBL_EXPORT GblBool GblNaryTree_isChild (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
82GBL_EXPORT GblBool GblNaryTree_isDescendent (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
83GBL_EXPORT GblBool GblNaryTree_isRelative (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
84
85GBL_EXPORT size_t GblNaryTree_childCount (GBL_CSELF) GBL_NOEXCEPT;
86GBL_EXPORT GblNaryTreeNode* GblNaryTree_childLast (GBL_CSELF) GBL_NOEXCEPT;
87GBL_EXPORT GblNaryTreeNode* GblNaryTree_childBefore (GBL_CSELF, const GblNaryTreeNode* pChild) GBL_NOEXCEPT;
88GBL_EXPORT GblNaryTreeNode* GblNaryTree_childAt (GBL_CSELF, size_t index) GBL_NOEXCEPT;
89GBL_EXPORT size_t GblNaryTree_childIndex (GBL_CSELF, const GblNaryTreeNode* pChild) GBL_NOEXCEPT;
90
91GBL_EXPORT void GblNaryTree_addChildFront (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
92GBL_EXPORT void GblNaryTree_addChildBack (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
93GBL_EXPORT void GblNaryTree_addChildTo (GBL_SELF, size_t index, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
94GBL_EXPORT void GblNaryTree_addChildBefore (GBL_SELF, GblNaryTreeNode* pBefore, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
95GBL_EXPORT void GblNaryTree_addChildAfter (GBL_SELF, GblNaryTreeNode* pAfter, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
96
97GBL_EXPORT void GblNaryTree_moveChildFront (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
98GBL_EXPORT void GblNaryTree_moveChildBack (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
99GBL_EXPORT void GblNaryTree_moveChildTo (GBL_SELF, size_t index, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
100
101GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChild (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
102GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChildFront (GBL_SELF) GBL_NOEXCEPT;
103GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChildBack (GBL_SELF) GBL_NOEXCEPT;
104GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChildAt (GBL_SELF, size_t index) GBL_NOEXCEPT;
105
106GBL_EXPORT void GblNaryTree_replaceChild (GBL_SELF, GblNaryTreeNode* pOld, GblNaryTreeNode* pNew) GBL_NOEXCEPT;
107GBL_EXPORT void GblNaryTree_replaceChildAt (GBL_SELF, size_t index, GblNaryTreeNode* pNewChild) GBL_NOEXCEPT;
108
109GBL_EXPORT void GblNaryTree_swapChildren (GBL_SELF, GblNaryTreeNode* pChild1, GblNaryTreeNode* pChild2) GBL_NOEXCEPT;
110GBL_EXPORT void GblNaryTree_swapChildrenAt (GBL_SELF, size_t index1, size_t index2) GBL_NOEXCEPT;
111
112GBL_EXPORT void GblNaryTree_reverseChildren (GBL_SELF) GBL_NOEXCEPT;
113
114GBL_EXPORT GblNaryTreeNode* GblNaryTree_root (GBL_SELF) GBL_NOEXCEPT;
115GBL_EXPORT GblNaryTreeNode* GblNaryTree_base (GBL_SELF, size_t depth) GBL_NOEXCEPT;
116GBL_EXPORT GblNaryTreeNode* GblNaryTree_ancestor (GBL_CSELF, size_t height) GBL_NOEXCEPT;
117GBL_EXPORT size_t GblNaryTree_ancestorHeight (GBL_CSELF, const GblNaryTreeNode* pParent) GBL_NOEXCEPT;
118
119GBL_EXPORT size_t GblNaryTree_siblingCount (GBL_CSELF) GBL_NOEXCEPT;
120GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingLast (GBL_CSELF) GBL_NOEXCEPT;
121GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingBefore (GBL_CSELF) GBL_NOEXCEPT;
122GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingFirst (GBL_CSELF) GBL_NOEXCEPT;
123GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingAt (GBL_CSELF, size_t index) GBL_NOEXCEPT;
124GBL_EXPORT size_t GblNaryTree_siblingIndex (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
125
126GBL_EXPORT void GblNaryTree_disconnect (GBL_SELF) GBL_NOEXCEPT;
127
128GBL_EXPORT GblNaryTreeNode* GblNaryTree_lowestCommonAncestor (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
129GBL_EXPORT size_t GblNaryTree_distance (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
130GBL_EXPORT GblBool GblNaryTree_traverse (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIt, void* pUd) GBL_NOEXCEPT;
131GBL_EXPORT GblBool GblNaryTree_traverseInOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
132GBL_EXPORT GblBool GblNaryTree_traversePreOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
133GBL_EXPORT GblBool GblNaryTree_traversePostOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
134GBL_EXPORT GblBool GblNaryTree_traverseLevelOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
135
136GBL_DECLS_END
137
138#undef GBL_SELF_TYPE
139
140#endif // GIMBAL_NARY_TREE_H
GBL_NOEXCEPT
#define GBL_NOEXCEPT
Definition gimbal_compiler.h:152
GBL_DECLS_BEGIN
#define GBL_DECLS_BEGIN
Definition gimbal_decls.h:23
GBL_FORWARD_DECLARE_STRUCT
#define GBL_FORWARD_DECLARE_STRUCT(S)
Definition gimbal_decls.h:181
GBL_EXPORT
#define GBL_EXPORT
Definition gimbal_decls.h:253
GBL_CONTAINER_OF
#define GBL_CONTAINER_OF(ptr, type, member)
Definition gimbal_macro_utils.h:36
GblFlags
uint32_t GblFlags
Standard-sized flags type, 32-bits across platforms.
Definition gimbal_typedefs.h:37
GblBool
uint8_t GblBool
Basic boolean type, standardized to sizeof(char)
Definition gimbal_typedefs.h:20
GBL_NPOS
#define GBL_NPOS
Definition gimbal_typedefs.h:16
GblNaryTreeNode
Represents a single intrusive node within an N-Ary tree structure.
Definition gimbal_nary_tree.h:58
GblNaryTreeNode::pParent
struct GblNaryTreeNode * pParent
Node's parent.
Definition gimbal_nary_tree.h:59
GblNaryTreeNode::pSiblingNext
struct GblNaryTreeNode * pSiblingNext
Node's next sibling (next entry of child linked list)
Definition gimbal_nary_tree.h:61
GblNaryTreeNode::pChildFirst
struct GblNaryTreeNode * pChildFirst
Node's first child (beginning of child linked list)
Definition gimbal_nary_tree.h:60