pheap.h

Go to the documentation of this file.

 
#ifndef LELY_UTIL_PHEAP_H_
#define LELY_UTIL_PHEAP_H_
 
#include <lely/features.h>
 
#include <stddef.h>
 
#ifndef LELY_UTIL_PHEAP_INLINE
#define LELY_UTIL_PHEAP_INLINE static inline
#endif
 
struct pnode {
        const void *key;
        struct pnode *parent;
        struct pnode *next;
        struct pnode *child;
};
 
#define PNODE_INIT \
        { \
                NULL, NULL, NULL, NULL \
        }
 
#ifdef __cplusplus
extern "C" {
#endif
 
typedef int pheap_cmp_t(const void *p1, const void *p2);
 
struct pheap {
        pheap_cmp_t *cmp;
        struct pnode *root;
        size_t num_nodes;
};
 
#define PHEAP_INIT \
        { \
                NULL, NULL, 0 \
        }
 
LELY_UTIL_PHEAP_INLINE void pnode_init(struct pnode *node, const void *key);
 
LELY_UTIL_PHEAP_INLINE struct pnode *pnode_next(const struct pnode *node);
 
#ifdef __COUNTER__
#define pnode_foreach(first, node) pnode_foreach_(__COUNTER__, first, node)
#else
#define pnode_foreach(first, node) pnode_foreach_(__LINE__, first, node)
#endif
#define pnode_foreach_(n, first, node) pnode_foreach__(n, first, node)
// clang-format off
#define pnode_foreach__(n, first, node) \
        for (struct pnode *node = (first), \
                        *_pnode_next_##n = (node) ? pnode_next(node) : NULL; \
                        (node); (node) = _pnode_next_##n, \
                        _pnode_next_##n = (node) ? pnode_next(node) : NULL)
// clang-format on
 
LELY_UTIL_PHEAP_INLINE void pheap_init(struct pheap *heap, pheap_cmp_t *cmp);
 
LELY_UTIL_PHEAP_INLINE int pheap_empty(const struct pheap *heap);
 
LELY_UTIL_PHEAP_INLINE size_t pheap_size(const struct pheap *heap);
 
void pheap_insert(struct pheap *heap, struct pnode *node);
 
void pheap_remove(struct pheap *heap, struct pnode *node);
 
struct pnode *pheap_find(const struct pheap *heap, const void *key);
 
LELY_UTIL_PHEAP_INLINE struct pnode *pheap_first(const struct pheap *heap);
 
#define pheap_foreach(heap, node) pnode_foreach (pheap_first(heap), node)
 
inline void
pnode_init(struct pnode *node, const void *key)
{
        node->key = key;
}
 
inline struct pnode *
pnode_next(const struct pnode *node)
{
        if (node->child)
                return node->child;
        do {
                if (node->next)
                        return node->next;
        } while ((node = node->parent));
        return NULL;
}
 
inline void
pheap_init(struct pheap *heap, pheap_cmp_t *cmp)
{
        heap->cmp = cmp;
        heap->root = NULL;
        heap->num_nodes = 0;
}
 
inline int
pheap_empty(const struct pheap *heap)
{
        return !pheap_size(heap);
}
 
inline size_t
pheap_size(const struct pheap *heap)
{
        return heap->num_nodes;
}
 
inline struct pnode *
pheap_first(const struct pheap *heap)
{
        return heap->root;
}
 
#ifdef __cplusplus
}
#endif
 
#endif // !LELY_UTIL_PHEAP_H_