Lely core libraries 2.3.4
pheap.h
Go to the documentation of this file.
1
33#ifndef LELY_UTIL_PHEAP_H_
34#define LELY_UTIL_PHEAP_H_
35
36#include <lely/features.h>
37
38#include <assert.h>
39#include <stddef.h>
40
41#ifndef LELY_UTIL_PHEAP_INLINE
42#define LELY_UTIL_PHEAP_INLINE static inline
43#endif
44
52struct pnode {
58 const void *key;
60 struct pnode *parent;
62 struct pnode *next;
64 struct pnode *child;
65};
66
68#define PNODE_INIT \
69 { \
70 NULL, NULL, NULL, NULL \
71 }
72
73#ifdef __cplusplus
74extern "C" {
75#endif
76
84typedef int pheap_cmp_t(const void *p1, const void *p2);
85
87struct pheap {
91 struct pnode *root;
93 size_t num_nodes;
94};
95
97#define PHEAP_INIT \
98 { \
99 NULL, NULL, 0 \
100 }
101
109LELY_UTIL_PHEAP_INLINE void pnode_init(struct pnode *node, const void *key);
110
112LELY_UTIL_PHEAP_INLINE struct pnode *pnode_next(const struct pnode *node);
113
126#ifdef __COUNTER__
127#define pnode_foreach(first, node) pnode_foreach_(__COUNTER__, first, node)
128#else
129#define pnode_foreach(first, node) pnode_foreach_(__LINE__, first, node)
130#endif
131#define pnode_foreach_(n, first, node) pnode_foreach__(n, first, node)
132// clang-format off
133#define pnode_foreach__(n, first, node) \
134 for (struct pnode *node = (first), \
135 *_pnode_next_##n = (node) ? pnode_next(node) : NULL; \
136 (node); (node) = _pnode_next_##n, \
137 _pnode_next_##n = (node) ? pnode_next(node) : NULL)
138// clang-format on
139
146LELY_UTIL_PHEAP_INLINE void pheap_init(struct pheap *heap, pheap_cmp_t *cmp);
147
149LELY_UTIL_PHEAP_INLINE int pheap_empty(const struct pheap *heap);
150
155LELY_UTIL_PHEAP_INLINE size_t pheap_size(const struct pheap *heap);
156
166void pheap_insert(struct pheap *heap, struct pnode *node);
167
175void pheap_remove(struct pheap *heap, struct pnode *node);
176
184struct pnode *pheap_find(const struct pheap *heap, const void *key);
185
191int pheap_contains(const struct pheap *heap, const struct pnode *node);
192
197LELY_UTIL_PHEAP_INLINE struct pnode *pheap_first(const struct pheap *heap);
198
204#define pheap_foreach(heap, node) pnode_foreach (pheap_first(heap), node)
205
206LELY_UTIL_PHEAP_INLINE void
207pnode_init(struct pnode *node, const void *key)
208{
209 assert(node);
210
211 node->key = key;
212}
213
214LELY_UTIL_PHEAP_INLINE struct pnode *
215pnode_next(const struct pnode *node)
216{
217 assert(node);
218
219 if (node->child)
220 return node->child;
221 do {
222 if (node->next)
223 return node->next;
224 } while ((node = node->parent));
225 return NULL;
226}
227
228LELY_UTIL_PHEAP_INLINE void
229pheap_init(struct pheap *heap, pheap_cmp_t *cmp)
230{
231 assert(heap);
232 assert(cmp);
233
234 heap->cmp = cmp;
235 heap->root = NULL;
236 heap->num_nodes = 0;
237}
238
239LELY_UTIL_PHEAP_INLINE int
240pheap_empty(const struct pheap *heap)
241{
242 return !pheap_size(heap);
243}
244
245LELY_UTIL_PHEAP_INLINE size_t
246pheap_size(const struct pheap *heap)
247{
248 assert(heap);
249
250 return heap->num_nodes;
251}
252
253LELY_UTIL_PHEAP_INLINE struct pnode *
254pheap_first(const struct pheap *heap)
255{
256 assert(heap);
257
258 return heap->root;
259}
260
261#ifdef __cplusplus
262}
263#endif
264
265#endif // !LELY_UTIL_PHEAP_H_
This header file is part of the Lely libraries; it contains the compiler feature definitions.
int pheap_contains(const struct pheap *heap, const struct pnode *node)
Checks if a node is part of a pairing heap.
Definition pheap.c:122
struct pnode * pheap_first(const struct pheap *heap)
Returns a pointer to the first (minimum) node in a pairing heap.
Definition pheap.h:254
void pheap_insert(struct pheap *heap, struct pnode *node)
Inserts a node into a pairing heap.
Definition pheap.c:35
size_t pheap_size(const struct pheap *heap)
Returns the size (in number of nodes) of a pairing heap.
Definition pheap.h:246
struct pnode * pheap_find(const struct pheap *heap, const void *key)
Finds a node in a pairing heap.
Definition pheap.c:96
int pheap_cmp_t(const void *p1, const void *p2)
The type of a comparison function suitable for use in a paring heap.
Definition pheap.h:84
void pheap_init(struct pheap *heap, pheap_cmp_t *cmp)
Initializes a pairing heap.
Definition pheap.h:229
struct pnode * pnode_next(const struct pnode *node)
Returns a pointer to the next node (in unspecified order) in a pairing heap.
Definition pheap.h:215
void pheap_remove(struct pheap *heap, struct pnode *node)
Removes a node from a pairing heap.
Definition pheap.c:63
int pheap_empty(const struct pheap *heap)
Returns 1 if the pairing heap is empty, and 0 if not.
Definition pheap.h:240
void pnode_init(struct pnode *node, const void *key)
Initializes a node in a paring heap.
Definition pheap.h:207
This header file is part of the C11 and POSIX compatibility library; it includes <stddef....
A pairing heap.
Definition pheap.h:87
pheap_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition pheap.h:89
struct pnode * root
A pointer to the root node of the heap.
Definition pheap.h:91
size_t num_nodes
The number of nodes stored in the heap.
Definition pheap.h:93
A node in a pairing heap.
Definition pheap.h:52
struct pnode * parent
A pointer to the parent node.
Definition pheap.h:60
struct pnode * child
A pointer to the first child node.
Definition pheap.h:64
const void * key
A pointer to the key of this node.
Definition pheap.h:58
struct pnode * next
A pointer to the next sibling node.
Definition pheap.h:62