libGimbal 0.1.0
C17-Based Extended Standard Library and Cross-Language Runtime Framework
Loading...
Searching...
No Matches
gimbal_hash_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 Falco Girgis
7 */
8
9#ifndef GIMBAL_HASHSET_H
10#define GIMBAL_HASHSET_H
11
12#include "../core/gimbal_typedefs.h"
13#include "../core/gimbal_ctx.h"
14
15#define GBL_SELF_TYPE GblHashSet
16
17GBL_DECLS_BEGIN
18
19GBL_FORWARD_DECLARE_STRUCT(GblHashSet);
20
21typedef GblHash (*GblHashSetHashFn)(GBL_CSELF, const void*); //!< User-defined hasher function, hashing two entries
22typedef GblBool (*GblHashSetCmpFn) (GBL_CSELF, const void*, const void*); //!< User-defined comparator function, comparing two entries
23typedef void (*GblHashSetDtorFn)(GBL_CSELF, void*); //!< User-defined destructor function, destroying an entry
24typedef GblBool (*GblHashSetIterFn)(GBL_CSELF, void*, void*); //!< User-defined iterator function for traversal
25
26/*! Hash-table based abstract associative container with C++-style STL std::unoredered_set API
27 *
28 * GblHashSet uses open-addressing ans is implemented using a Robin Hood hashing algorithm.
29 * Using it requires providing a custom hasher function (which typically uses one of
30 * the libGimbal hashing algorithms such as gblHashMurmur()) as well as a custom comparator function.
31 *
32 * \note
33 * Performance is pretty darn good. Read speed is faster than both C++'s std::unordered_pSelf and
34 * Qt's QHash (despite being runtime polymorphic with C function pointers) while write speed
35 * is slightly slower than both.
36 *
37 * \ingroup containers
38 */
39typedef struct GblHashSet {
40 GBL_PRIVATE_BEGIN
41 GblContext* pCtx;
42 size_t entrySize;
43 size_t capacity;
44 GblHashSetHashFn pFnHash;
45 GblHashSetCmpFn pFnCompare;
46 GblHashSetDtorFn pFnDestruct;
47 size_t bucketSize;
48 size_t bucketCount;
49 size_t count;
50 size_t mask;
51 void* pBuckets;
52 void* pSpare;
53 void* pUserdata;
54 GBL_PRIVATE_END
55} GblHashSet;
56
57/*! \brief Iterator structure used for iterating over GblHashSet
58 * \sa GblHashSet
59 */
60typedef struct GblHashSetIter {
61 GBL_PRIVATE_BEGIN
62 GblHashSet* pSet;
63 size_t bucketIdx;
64 GBL_PRIVATE_END
65} GblHashSetIter;
66
67GBL_EXPORT GBL_RESULT GblHashSet_construct_8 (GBL_SELF,
68 size_t entrySize,
69 GblHashSetHashFn pFnHash,
70 GblHashSetCmpFn pFnCompare,
71 GblHashSetDtorFn pFnDestruct,
72 size_t capacity,
73 GblContext* pCtx,
74 void* pUserdata) GBL_NOEXCEPT;
75GBL_EXPORT GBL_RESULT GblHashSet_construct_7 (GBL_SELF,
76 size_t entrySize,
77 GblHashSetHashFn pFnHash,
78 GblHashSetCmpFn pFnCompare,
79 GblHashSetDtorFn pFnDestruct,
80 size_t capacity,
81 GblContext* pCtx) GBL_NOEXCEPT;
82GBL_EXPORT GBL_RESULT GblHashSet_construct_6 (GBL_SELF,
83 size_t entrySize,
84 GblHashSetHashFn pFnHash,
85 GblHashSetCmpFn pFnCompare,
86 GblHashSetDtorFn pFnDestruct,
87 size_t capacity) GBL_NOEXCEPT;
88GBL_EXPORT GBL_RESULT GblHashSet_construct_5 (GBL_SELF,
89 size_t entrySize,
90 GblHashSetHashFn pFnHash,
91 GblHashSetCmpFn pFnCompare,
92 GblHashSetDtorFn pFnDestruct) GBL_NOEXCEPT;
93GBL_EXPORT GBL_RESULT GblHashSet_construct_4 (GBL_SELF,
94 size_t entrySize,
95 GblHashSetHashFn pFnHash,
96 GblHashSetCmpFn pFnCompare) GBL_NOEXCEPT;
97#define GblHashSet_construct(...)
98 GBL_VA_OVERLOAD_CALL_ARGC(GblHashSet_construct, __VA_ARGS__)
99
100GBL_EXPORT GBL_RESULT GblHashSet_clone (GBL_SELF,
101 const GblHashSet* pRhs,
102 GblContext* hCtx) GBL_NOEXCEPT;
103
104GBL_EXPORT GBL_RESULT GblHashSet_constructMove (GBL_SELF,
105 GblHashSet* pRhs,
106 GblContext* hCtx) GBL_NOEXCEPT;
107
108GBL_EXPORT GBL_RESULT GblHashSet_constructClone(GBL_SELF, GblHashSet* pRhs) GBL_NOEXCEPT;
109GBL_EXPORT GBL_RESULT GblHashSet_assignMove (GBL_SELF, GblHashSet* pRhs) GBL_NOEXCEPT;
110GBL_EXPORT GBL_RESULT GblHashSet_destruct (GBL_SELF) GBL_NOEXCEPT;
111
112GBL_EXPORT size_t GblHashSet_size (GBL_CSELF) GBL_NOEXCEPT;
113GBL_EXPORT size_t GblHashSet_bucketCount (GBL_CSELF) GBL_NOEXCEPT;
114GBL_EXPORT size_t GblHashSet_bucketSize (GBL_CSELF) GBL_NOEXCEPT;
115GBL_EXPORT GblContext* GblHashSet_context (GBL_CSELF) GBL_NOEXCEPT;
116GBL_EXPORT GblBool GblHashSet_empty (GBL_CSELF) GBL_NOEXCEPT;
117GBL_EXPORT void* GblHashSet_userdata (GBL_CSELF) GBL_NOEXCEPT;
118
119GBL_EXPORT void* GblHashSet_get (GBL_CSELF, const void* pKey) GBL_NOEXCEPT; //raw get, no error
120GBL_EXPORT void* GblHashSet_at (GBL_CSELF, const void* pKey) GBL_NOEXCEPT; //throws range error
121GBL_EXPORT GblBool GblHashSet_contains (GBL_CSELF, const void* pKey) GBL_NOEXCEPT; //true if entry exists
122GBL_EXPORT size_t GblHashSet_count (GBL_CSELF, const void* pKey) GBL_NOEXCEPT; //# of matching entries (0 or 1)
123GBL_EXPORT GblHashSetIter GblHashSet_find (GBL_CSELF, const void* pKey) GBL_NOEXCEPT;
124
125GBL_EXPORT void* GblHashSet_set (GBL_SELF, const void* pEntry) GBL_NOEXCEPT; //raw set, returns existing item w/o deleting
126GBL_EXPORT GblBool GblHashSet_insert (GBL_SELF, const void* pEntry) GBL_NOEXCEPT; //throws duplicate error
127GBL_EXPORT void GblHashSet_insertOrAssign(GBL_SELF, const void* pEntry) GBL_NOEXCEPT; //deletes any overwritten value
128GBL_EXPORT void* GblHashSet_emplace (GBL_SELF, const void* pKey) GBL_NOEXCEPT; //throws duplicate error
129GBL_EXPORT void* GblHashSet_tryEmplace (GBL_SELF, const void* pKey) GBL_NOEXCEPT; //gracefully returns NULL if already exists
130
131GBL_EXPORT GblBool GblHashSet_erase (GBL_SELF, const void* pKey) GBL_NOEXCEPT; //deletes entry, not found is fine
132GBL_EXPORT void* GblHashSet_extract (GBL_SELF, const void* pKey) GBL_NOEXCEPT; //removes entry, no deletion, not found is fine
133GBL_EXPORT void GblHashSet_clear (GBL_SELF) GBL_NOEXCEPT; //deletes entries
134
135GBL_EXPORT GBL_RESULT GblHashSet_shrinkToFit (GBL_SELF) GBL_NOEXCEPT;
136
137GBL_EXPORT void* GblHashSet_probe (GBL_CSELF, size_t position) GBL_NOEXCEPT; //returns entry at slot or NULL, sparse
138
139GBL_EXPORT GblBool GblHashSet_foreach (GBL_CSELF,
140 GblHashSetIterFn iter,
141 void* pUdata) GBL_NOEXCEPT; //iterates over every non-null position
142
143GBL_EXPORT GblHashSetIter GblHashSet_next (GBL_CSELF,
144 const GblHashSetIter* pPrev) GBL_NOEXCEPT; //[Lua-style] Returns iterator after given
145GBL_EXPORT const GblHashSet* GblHashSetIter_container (const GblHashSetIter* pSelf) GBL_NOEXCEPT;
146GBL_EXPORT GblBool GblHashSetIter_valid (const GblHashSetIter* pSelf) GBL_NOEXCEPT;
147GBL_EXPORT void* GblHashSetIter_value (const GblHashSetIter* pSelf) GBL_NOEXCEPT;
148
149GBL_DECLS_END
150
151#undef GBL_SELF_TYPE
152
153#endif // GIMBAL_HASHSET_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_PRIVATE_BEGIN
#define GBL_PRIVATE_BEGIN
Definition gimbal_decls.h:199
GBL_EXPORT
#define GBL_EXPORT
Definition gimbal_decls.h:232
GBL_PRIVATE_END
#define GBL_PRIVATE_END
Private data structure.
Definition gimbal_decls.h:201
GblHashSet_construct
#define GblHashSet_construct(...)
Definition gimbal_hash_set.h:97
GblHashSetDtorFn
void(* GblHashSetDtorFn)(const GblHashSet *pSelf, void *)
User-defined destructor function, destroying an entry.
Definition gimbal_hash_set.h:23
GBL_VA_OVERLOAD_CALL_ARGC
#define GBL_VA_OVERLOAD_CALL_ARGC(BASE,...)
Definition gimbal_macro_composition.h:121
GblHash
uint32_t GblHash
Type representing a calculated numeric hash across the codebase.
Definition gimbal_typedefs.h:41
GblBool
uint8_t GblBool
Basic boolean type, standardized to sizeof(char)
Definition gimbal_typedefs.h:20
GblHashSet
Hash-table based abstract associative container with C++-style STL std::unoredered_set API.
Definition gimbal_hash_set.h:39
GblHashSetIter
Iterator structure used for iterating over GblHashSet.
Definition gimbal_hash_set.h:60