libGimbal 0.1.0
C17-Based Extended Standard Library and Cross-Language Runtime Framework
Loading...
Searching...
No Matches
gimbal_tree_set.h
Go to the documentation of this file.
1/*! \file
2 * \brief GblHashSet structure and related functions
3 * \ingroup containers
4 *
5 * \author Josh Baker
6 * \author 2023 Falco Girgis
7 */
8
9#ifndef GIMBAL_BTREE_H
10#define GIMBAL_BTREE_H
11
12#include <time.h>
13#include "../core/gimbal_ctx.h"
14
15#define GBL_SELF_TYPE GblTreeSet
16
17GBL_DECLS_BEGIN
18
19GBL_FORWARD_DECLARE_STRUCT(GblTreeSet);
20
21typedef int (*GblTreeSetCompareFn) (GBL_CSELF, const void*, const void*);
22typedef void (*GblTreeSetDestructFn)(GBL_CSELF, void*);
23
24//! Internal structure representing a single node within a GblTreeSet
25typedef struct GblTreeSetNode {
26 uint16_t entryCount;
27 GblBool leaf;
28 uint8_t padding[sizeof(void*)-3];
29 void* pEntries;
30 struct GblTreeSetNode* pChildren[1];
31} GblTreeSetNode;
32
33//! Internal structure representing a group of nodes within a GblTreeSet
34typedef struct GblTreeSetGroup {
35 GblTreeSetNode** ppNodes;
36 size_t length;
37 size_t capacity;
38} GblTreeSetGroup;
39
40//! Internal structure representing a pool of \ref GblTreeSetGroup items within a GblTreeSet
41typedef struct GblTreeSetPool {
42 GblTreeSetGroup leaves;
43 GblTreeSetGroup branches;
44 } GblTreeSetPool;
45
46/*! \brief Binary tree based abstract associative container with C++-style STL API
47 * \ingroup containers
48 */
49typedef struct GblTreeSet {
50 GblContext* pCtx;
51 size_t entrySize;
52 GblTreeSetCompareFn pFnCompare;
53 GblTreeSetDestructFn pFnDestruct;
54 GblTreeSetPool pool;
55 GblTreeSetNode* pRoot;
56 size_t count;
57 size_t height;
58 size_t maxCount;
59 size_t minCount;
60 void* pSpares[3];
61 void* pLastEntry;
62 void* pLastNode;
63 void* pUserdata;
64} GblTreeSet;
65
66//! Represents an iterator for iterating over a GblTreeSet
67typedef struct GblTreeSetIterator {
68 GblTreeSet* pContainer;
69 GblTreeSetNode* pNode;
70 uint16_t index;
71} GblTreeSetIterator;
72
73
74GBL_EXPORT GBL_RESULT GblTreeSet_construct_7 (GBL_SELF,
75 size_t entrySize,
76 GblTreeSetCompareFn pFnCompare,
77 GblTreeSetDestructFn pFnDestruct,
78 size_t maxEntries,
79 GblContext* pCtx,
80 void* pUserdata) GBL_NOEXCEPT;
81GBL_EXPORT GBL_RESULT GblTreeSet_construct_6 (GBL_SELF,
82 size_t entrySize,
83 GblTreeSetCompareFn pFnCompare,
84 GblTreeSetDestructFn pFnDestruct,
85 size_t maxEntries,
86 GblContext* pCtx) GBL_NOEXCEPT;
87GBL_EXPORT GBL_RESULT GblTreeSet_construct_5 (GBL_SELF,
88 size_t entrySize,
89 GblTreeSetCompareFn pFnCompare,
90 GblTreeSetDestructFn pFnDestruct,
91 size_t maxEntries) GBL_NOEXCEPT;
92GBL_EXPORT GBL_RESULT GblTreeSet_construct_4 (GBL_SELF,
93 size_t entrySize,
94 GblTreeSetCompareFn pFnCompare,
95 GblTreeSetDestructFn pFnDestruct) GBL_NOEXCEPT;
96GBL_EXPORT GBL_RESULT GblTreeSet_construct_3 (GBL_SELF,
97 size_t entrySize,
98 GblTreeSetCompareFn pFnCompare) GBL_NOEXCEPT;
99#define GblTreeSet_construct(...)
100 GBL_VA_OVERLOAD_CALL_ARGC(GblTreeSet_construct, __VA_ARGS__)
101
102GBL_EXPORT GBL_RESULT GblTreeSet_destruct (GBL_SELF) GBL_NOEXCEPT;
103
104GBL_EXPORT size_t GblTreeSet_size (GBL_CSELF) GBL_NOEXCEPT;
105GBL_EXPORT size_t GblTreeSet_height (GBL_CSELF) GBL_NOEXCEPT;
106GBL_EXPORT GblContext* GblTreeSet_context (GBL_CSELF) GBL_NOEXCEPT;
107GBL_EXPORT GblBool GblTreeSet_empty (GBL_CSELF) GBL_NOEXCEPT;
108GBL_EXPORT void* GblTreeSet_userdata (GBL_CSELF) GBL_NOEXCEPT;
109
110GBL_EXPORT void* GblTreeSet_get (GBL_CSELF, const void* pKey) GBL_NOEXCEPT;
111GBL_EXPORT void* GblTreeSet_getHint (GBL_CSELF,
112 const void* pKey,
113 uint64_t* pHint) GBL_NOEXCEPT;
114GBL_EXPORT void* GblTreeSet_at (GBL_CSELF, const void* pKey) GBL_NOEXCEPT;
115GBL_EXPORT void* GblTreeSet_atHint (GBL_CSELF,
116 const void* pKey,
117 uint64_t* pHint) GBL_NOEXCEPT;
118GBL_EXPORT GblBool GblTreeSet_contains (GBL_CSELF, const void* pKey) GBL_NOEXCEPT;
119GBL_EXPORT size_t GblTreeSet_count (GBL_CSELF, const void* pKey) GBL_NOEXCEPT;
120//GBL_EXPORT ??? GblTreeSet_find (GBL_CSELF, const void* pKey) GBL_NOEXCEPT;
121
122GBL_EXPORT void* GblTreeSet_set (GBL_SELF, const void* pEntry) GBL_NOEXCEPT;
123GBL_EXPORT void* GblTreeSet_setHint (GBL_SELF,
124 const void* pEntry,
125 uint64_t* pHint) GBL_NOEXCEPT;
126//GBL_EXPORT GblBool GblTreeSet_insert (GBL_SELF, const void* pEntry) GBL_NOEXCEPT;
127//GBL_EXPORT void GblTreeSet_insertOrAssign(GBL_SELF, const void* pEntry) GBL_NOEXCEPT;
128//GBL_EXPORT void* GblTreeSet_emplace (GBL_SELF, const void* pEntry) GBL_NOEXCEPT;
129//GBL_EXPORT void* GblTreeSet_tryEmplace (GBL_SELF, const void* pEntry) GBL_NOEXCEPT;
130
131GBL_EXPORT void* GblTreeSet_popMax (GBL_SELF) GBL_NOEXCEPT;
132GBL_EXPORT void* GblTreeSet_popMin (GBL_SELF) GBL_NOEXCEPT;
133
134GBL_EXPORT void* GblTreeSet_min (GBL_CSELF) GBL_NOEXCEPT;
135GBL_EXPORT void* GblTreeSet_max (GBL_CSELF) GBL_NOEXCEPT;
136
137GBL_EXPORT GblBool GblTreeSet_erase (GBL_SELF, const void* pKey) GBL_NOEXCEPT;
138GBL_EXPORT void* GblTreeSet_extract (GBL_SELF, const void* pKey) GBL_NOEXCEPT;
139GBL_EXPORT void GblTreeSet_clear (GBL_SELF) GBL_NOEXCEPT;
140
141GBL_DECLS_END
142
143#undef GBL_SELF_TYPE
144
145#endif // GIMBAL_TREE_SET_H
GBL_NOEXCEPT
#define GBL_NOEXCEPT
Definition gimbal_compiler.h:264
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:160
GBL_EXPORT
#define GBL_EXPORT
Definition gimbal_decls.h:232
GBL_VA_OVERLOAD_CALL_ARGC
#define GBL_VA_OVERLOAD_CALL_ARGC(BASE,...)
Definition gimbal_macro_composition.h:121
GblTreeSet_construct
#define GblTreeSet_construct(...)
Definition gimbal_tree_set.h:99
GblBool
uint8_t GblBool
Basic boolean type, standardized to sizeof(char)
Definition gimbal_typedefs.h:20
GblTreeSetGroup
Internal structure representing a group of nodes within a GblTreeSet.
Definition gimbal_tree_set.h:34
GblTreeSet
Binary tree based abstract associative container with C++-style STL API.
Definition gimbal_tree_set.h:49
GblTreeSetIterator
Represents an iterator for iterating over a GblTreeSet.
Definition gimbal_tree_set.h:67
GblTreeSetNode
Internal structure representing a single node within a GblTreeSet.
Definition gimbal_tree_set.h:25
GblTreeSetPool
Internal structure representing a pool of GblTreeSetGroup items within a GblTreeSet.
Definition gimbal_tree_set.h:41