summaryrefslogtreecommitdiff
path: root/cesar/lib/heap.h
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/heap.h')
-rw-r--r--cesar/lib/heap.h124
1 files changed, 124 insertions, 0 deletions
diff --git a/cesar/lib/heap.h b/cesar/lib/heap.h
new file mode 100644
index 0000000000..6505f0f001
--- /dev/null
+++ b/cesar/lib/heap.h
@@ -0,0 +1,124 @@
+#ifndef lib_heap_h
+#define lib_heap_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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 */