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 
52 struct 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
74 extern "C" {
75 #endif
76 
84 typedef int pheap_cmp_t(const void *p1, const void *p2);
85 
87 struct pheap {
91  struct pnode *root;
93  size_t num_nodes;
94 };
95 
97 #define PHEAP_INIT \
98  { \
99  NULL, NULL, 0 \
100  }
101 
109 LELY_UTIL_PHEAP_INLINE void pnode_init(struct pnode *node, const void *key);
110 
112 LELY_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 
146 LELY_UTIL_PHEAP_INLINE void pheap_init(struct pheap *heap, pheap_cmp_t *cmp);
147 
149 LELY_UTIL_PHEAP_INLINE int pheap_empty(const struct pheap *heap);
150 
155 LELY_UTIL_PHEAP_INLINE size_t pheap_size(const struct pheap *heap);
156 
166 void pheap_insert(struct pheap *heap, struct pnode *node);
167 
175 void pheap_remove(struct pheap *heap, struct pnode *node);
176 
184 struct pnode *pheap_find(const struct pheap *heap, const void *key);
185 
191 int pheap_contains(const struct pheap *heap, const struct pnode *node);
192 
197 LELY_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 
206 LELY_UTIL_PHEAP_INLINE void
207 pnode_init(struct pnode *node, const void *key)
208 {
209  assert(node);
210 
211  node->key = key;
212 }
213 
214 LELY_UTIL_PHEAP_INLINE struct pnode *
215 pnode_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 
228 LELY_UTIL_PHEAP_INLINE void
229 pheap_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 
239 LELY_UTIL_PHEAP_INLINE int
240 pheap_empty(const struct pheap *heap)
241 {
242  return !pheap_size(heap);
243 }
244 
245 LELY_UTIL_PHEAP_INLINE size_t
246 pheap_size(const struct pheap *heap)
247 {
248  assert(heap);
249 
250  return heap->num_nodes;
251 }
252 
253 LELY_UTIL_PHEAP_INLINE struct pnode *
254 pheap_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_
pnode_init
void pnode_init(struct pnode *node, const void *key)
Initializes a node in a paring heap.
Definition: pheap.h:207
features.h
pnode
A node in a pairing heap.
Definition: pheap.h:52
pheap_empty
int pheap_empty(const struct pheap *heap)
Returns 1 if the pairing heap is empty, and 0 if not.
Definition: pheap.h:240
pheap_insert
void pheap_insert(struct pheap *heap, struct pnode *node)
Inserts a node into a pairing heap.
Definition: pheap.c:35
pheap_find
struct pnode * pheap_find(const struct pheap *heap, const void *key)
Finds a node in a pairing heap.
Definition: pheap.c:96
pheap_size
size_t pheap_size(const struct pheap *heap)
Returns the size (in number of nodes) of a pairing heap.
Definition: pheap.h:246
pnode::next
struct pnode * next
A pointer to the next sibling node.
Definition: pheap.h:62
pheap_init
void pheap_init(struct pheap *heap, pheap_cmp_t *cmp)
Initializes a pairing heap.
Definition: pheap.h:229
pheap_cmp_t
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
pheap
A pairing heap.
Definition: pheap.h:87
pnode::key
const void * key
A pointer to the key of this node.
Definition: pheap.h:58
pheap::root
struct pnode * root
A pointer to the root node of the heap.
Definition: pheap.h:91
pnode::parent
struct pnode * parent
A pointer to the parent node.
Definition: pheap.h:60
pnode_next
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
pheap::cmp
pheap_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: pheap.h:89
pnode::child
struct pnode * child
A pointer to the first child node.
Definition: pheap.h:64
pheap_first
struct pnode * pheap_first(const struct pheap *heap)
Returns a pointer to the first (minimum) node in a pairing heap.
Definition: pheap.h:254
pheap_contains
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
pheap::num_nodes
size_t num_nodes
The number of nodes stored in the heap.
Definition: pheap.h:93
stddef.h
pheap_remove
void pheap_remove(struct pheap *heap, struct pnode *node)
Removes a node from a pairing heap.
Definition: pheap.c:63