Lely core libraries  2.2.5
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 <stddef.h>
39 
40 #ifndef LELY_UTIL_PHEAP_INLINE
41 #define LELY_UTIL_PHEAP_INLINE static inline
42 #endif
43 
51 struct pnode {
57  const void *key;
59  struct pnode *parent;
61  struct pnode *next;
63  struct pnode *child;
64 };
65 
67 #define PNODE_INIT \
68  { \
69  NULL, NULL, NULL, NULL \
70  }
71 
72 #ifdef __cplusplus
73 extern "C" {
74 #endif
75 
83 typedef int pheap_cmp_t(const void *p1, const void *p2);
84 
86 struct pheap {
90  struct pnode *root;
92  size_t num_nodes;
93 };
94 
96 #define PHEAP_INIT \
97  { \
98  NULL, NULL, 0 \
99  }
100 
108 LELY_UTIL_PHEAP_INLINE void pnode_init(struct pnode *node, const void *key);
109 
111 LELY_UTIL_PHEAP_INLINE struct pnode *pnode_next(const struct pnode *node);
112 
125 #ifdef __COUNTER__
126 #define pnode_foreach(first, node) pnode_foreach_(__COUNTER__, first, node)
127 #else
128 #define pnode_foreach(first, node) pnode_foreach_(__LINE__, first, node)
129 #endif
130 #define pnode_foreach_(n, first, node) pnode_foreach__(n, first, node)
131 // clang-format off
132 #define pnode_foreach__(n, first, node) \
133  for (struct pnode *node = (first), \
134  *_pnode_next_##n = (node) ? pnode_next(node) : NULL; \
135  (node); (node) = _pnode_next_##n, \
136  _pnode_next_##n = (node) ? pnode_next(node) : NULL)
137 // clang-format on
138 
145 LELY_UTIL_PHEAP_INLINE void pheap_init(struct pheap *heap, pheap_cmp_t *cmp);
146 
148 LELY_UTIL_PHEAP_INLINE int pheap_empty(const struct pheap *heap);
149 
154 LELY_UTIL_PHEAP_INLINE size_t pheap_size(const struct pheap *heap);
155 
163 void pheap_insert(struct pheap *heap, struct pnode *node);
164 
171 void pheap_remove(struct pheap *heap, struct pnode *node);
172 
180 struct pnode *pheap_find(const struct pheap *heap, const void *key);
181 
186 LELY_UTIL_PHEAP_INLINE struct pnode *pheap_first(const struct pheap *heap);
187 
193 #define pheap_foreach(heap, node) pnode_foreach (pheap_first(heap), node)
194 
195 inline void
196 pnode_init(struct pnode *node, const void *key)
197 {
198  node->key = key;
199 }
200 
201 inline struct pnode *
202 pnode_next(const struct pnode *node)
203 {
204  if (node->child)
205  return node->child;
206  do {
207  if (node->next)
208  return node->next;
209  } while ((node = node->parent));
210  return NULL;
211 }
212 
213 inline void
214 pheap_init(struct pheap *heap, pheap_cmp_t *cmp)
215 {
216  heap->cmp = cmp;
217  heap->root = NULL;
218  heap->num_nodes = 0;
219 }
220 
221 inline int
222 pheap_empty(const struct pheap *heap)
223 {
224  return !pheap_size(heap);
225 }
226 
227 inline size_t
228 pheap_size(const struct pheap *heap)
229 {
230  return heap->num_nodes;
231 }
232 
233 inline struct pnode *
234 pheap_first(const struct pheap *heap)
235 {
236  return heap->root;
237 }
238 
239 #ifdef __cplusplus
240 }
241 #endif
242 
243 #endif // !LELY_UTIL_PHEAP_H_
This header file is part of the Lely libraries; it contains the compiler feature definitions.
struct pnode * pheap_first(const struct pheap *heap)
Returns a pointer to the first (minimum) node in a pairing heap.
Definition: pheap.h:234
void pheap_insert(struct pheap *heap, struct pnode *node)
Inserts a node into a pairing heap.
Definition: pheap.c:37
size_t pheap_size(const struct pheap *heap)
Returns the size (in number of nodes) of a pairing heap.
Definition: pheap.h:228
struct pnode * pheap_find(const struct pheap *heap, const void *key)
Finds a node in a pairing heap.
Definition: pheap.c:91
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:83
void pheap_init(struct pheap *heap, pheap_cmp_t *cmp)
Initializes a pairing heap.
Definition: pheap.h:214
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:202
void pheap_remove(struct pheap *heap, struct pnode *node)
Removes a node from a pairing heap.
Definition: pheap.c:65
int pheap_empty(const struct pheap *heap)
Returns 1 if the pairing heap is empty, and 0 if not.
Definition: pheap.h:222
void pnode_init(struct pnode *node, const void *key)
Initializes a node in a paring heap.
Definition: pheap.h:196
This header file is part of the C11 and POSIX compatibility library; it includes <stddef....
A pairing heap.
Definition: pheap.h:86
pheap_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: pheap.h:88
struct pnode * root
A pointer to the root node of the heap.
Definition: pheap.h:90
size_t num_nodes
The number of nodes stored in the heap.
Definition: pheap.h:92
A node in a pairing heap.
Definition: pheap.h:51
struct pnode * parent
A pointer to the parent node.
Definition: pheap.h:59
struct pnode * child
A pointer to the first child node.
Definition: pheap.h:63
const void * key
A pointer to the key of this node.
Definition: pheap.h:57
struct pnode * next
A pointer to the next sibling node.
Definition: pheap.h:61