#ifndef lib_heap_h #define lib_heap_h /* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/heap.h * \brief Heap (the data structure) service. * \ingroup lib * * An heap is a tree data structure which satisfies the following property: if B * is a child of A, then B.key >= A.key. * * It defines the following set of operations efficiently: * - insert, * - find root (the minimum value), * - remove root (the minimum value). * * Some heap algorithms also define the following efficient operations: * - remove a arbitrary node, * - merge two heaps. * * Its common use is to implement priority queue. */ #include "config/heap.h" /* Forward declaration. */ typedef struct heap_node_t heap_node_t; /** * Heap node comparison function pointer. * \param left left hand node * \param right right hand node * \return true iff left is lesser than right */ typedef bool (*heap_node_less_t) (heap_node_t *left, heap_node_t *right); /** Heap structure. */ struct heap_t { /** Heap root node. */ heap_node_t *root; /** Heap "is lesser than" comparison function. */ heap_node_less_t less; }; typedef struct heap_t heap_t; #if CONFIG_HEAP_SKEW # include "lib/skewheap.h" #elif CONFIG_HEAP_LEFTIST # include "lib/leftheap.h" #endif /** Heap node with an u32 key. */ struct heap_node_u32_t { heap_node_t node; u32 key; }; typedef struct heap_node_u32_t heap_node_u32_t; BEGIN_DECLS /** * Initialise a new heap. * \param heap the heap * \param less the "is lesser than" comparison function */ void heap_init (heap_t *heap, heap_node_less_t less); /** * Adjust position of a given node after a key change. * \param heap the heap * \param node the node to adjust. * * Actually, if the node is at a good position, nothing is done. In other * cases, it is removed, then inserted. */ void heap_adjust (heap_t *heap, heap_node_t *node); /** * Get heap root. * \param heap the heap * \return the root or NULL if the heap is empty */ extern inline heap_node_t * heap_get_root (heap_t *heap) { return heap->root; } /** * Return whether the heap is empty. * \param heap the heap * \return true if empty */ extern inline bool heap_empty (heap_t *heap) { return !heap->root; } /** * Merge two heaps, result in the first one. * \param heap_to heap receiving the result * \param heap_from heap to be merge with the first one */ void heap_merge (heap_t *heap_to, heap_t *heap_from); /** Heap comparison function for an u32 node using modulo 2^32. */ bool heap_node_u32_less_mod2p32 (heap_node_t *left, heap_node_t *right); END_DECLS #endif /* lib_heap_h */