fheap

commit 4ef09af99e1a2bf1c81307f9cac3a2a8187d728e
parent 590cd75d85b342a63e26def1478701b31f38a5d5
Author: olikru <olikru@tkruger.se>
Date:   Thu, 11 Jan 2024 14:38:20 +0100

documented functions

Diffstat:
M
fheap.c
 | 
7
+++++++
M
fheap.h
 | 
105
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 112 insertions(+), 0 deletions(-)
diff --git a/fheap.c b/fheap.c
@@ -59,6 +59,8 @@ static inline void insert_leftof(fnode_t *x, fnode_t *y) {
 }
 
 fnode_t *fheap_insert(fheap_t *heap, const uint64_t value, void *data) {
+  assert(value != UINT64_MAX || data != NULL);
+
   fnode_t *nnode = malloc(sizeof(*nnode));
 
   fnode_init(nnode, value, data);
@@ -198,6 +200,11 @@ fnode_t *fheap_extract_min_node(fheap_t *heap) {
 uint64_t fheap_extract_min(void **data, fheap_t *heap) {
   fnode_t *z = fheap_extract_min_node(heap);
 
+  if (z == NULL) {
+    *data = NULL;
+    return UINT64_MAX;
+  }
+
   uint64_t value = z->value;
   *data = z->data;
 
diff --git a/fheap.h b/fheap.h
@@ -25,16 +25,121 @@ typedef struct {
   fnode_t *head;
 } fheap_t;
 
+/**
+ * Intialise a Fibonacci heap node
+ *
+ * Initialises a new node. Internally in the heap all elements should be
+ * represented as a fnode_t. The two members value and data corresponds
+ * to the "key" (by which we order the elements) and the "data" (some
+ * associated data we want to represent).
+ *
+ * Note that the memory position for node already has to be allocated
+ * (usually this is done by fheap_insert).
+ *
+ * @param node pointer to the fnode_t to initialise
+ * @param value the "key"/"value" to give it
+ * @param data pointer to some associated data
+ */
 void fnode_init(fnode_t *node, const uint64_t value, void *data);
+
+/**
+ * Clear a Fibonacci heap node
+ *
+ * Removes a node, and frees it recursively (i.e. both the node itself
+ * and all its children are cleared, and the allocated memory is freed).
+ *
+ * @param node pointer to the node to free
+ */
 void fnode_clear(fnode_t *node);
 
+/**
+ * Initialise a Fibonacci heap
+ *
+ * The heap will be initialised to an empty heap.
+ *
+ * @param heap pointer to the heap to initialise
+ */
 void fheap_init(fheap_t *heap);
+
+/**
+ * Clear a Fibonacci heap
+ *
+ * Clear a Fibonacci heap. All remaining inserted elements will be freed
+ * recursively.
+ *
+ * @param heap pointer to the heap to clear
+ */
 void fheap_clear(fheap_t *heap);
 
+/**
+ * Insert a (value, data) pair into a Fibonacci heap
+ *
+ * Inserts a (value, data) pair into a Fibonacci heap, and allocates a
+ * new fnode_t element for them. This will allocate memory for the node,
+ * which will have to be cleared. The function returns a pointer to the
+ * new fnode_t (so we can access it directly, update its value etc.)
+ *
+ * Note!
+ * This will fail (hard) if value is UINT64_MAX and data is a NULL
+ * pointer. This is a forbidden (value, data) pair!
+ *
+ * @param heap pointer to the heap to insert into
+ * @param value the value (aka. key) to insert
+ * @param data pointer to associated data of this node
+ * @returns pointer to the new fnode_t created
+ */
 fnode_t *fheap_insert(fheap_t *heap, const uint64_t value, void *data);
+
+/**
+ * Extract minimum node of a Fibonacci heap
+ *
+ * Extracts the minimum node of a Fibonacci heap. Note that this returns
+ * the pointer to this node, but does not deallocate it (which makes it
+ * possible to work with the node before deallocating it). It needs to
+ * be deallocated manually (because it is no longer in the heap). If the
+ * heap is empty a NULL pointer is returned.
+ *
+ * @param heap the heap to remove the minimum node from
+ */
 fnode_t *fheap_extract_min_node(fheap_t *heap);
+
+/**
+ * Extract minimum from a Fibonacci heap
+ *
+ * Extracts the minimum value in a heap (and removing this value from
+ * the heap). This function then deallocates the fnode_t (only this
+ * node). The value of the minimum node is returned, and the address to
+ * which *data points is set to the address of the associated data of
+ * the node. If the heap is empty this returns UINT64_MAX and sets *data
+ * to NULL;
+ *
+ * @param data
+ *   pointer to pointer (address) to associated data, which we want to
+ *   set to the pointer to the associated data of the node, i.e. *data
+ *   will be set to member .data of extracted minimum
+ * @param heap
+ *   pointer to the heap to extract minimum from
+ * @returns
+ *   the value ("key") associated with the extracted minimum
+ */
 uint64_t fheap_extract_min(void **data, fheap_t *heap);
 
+/**
+ * Decerease value of a node in a Fibonacci heap
+ *
+ * Decreases the value of a node in a Fibonacci heap. This will reorder
+ * the heap appropriately to and update its minimum if neccessary.
+ *
+ * Note!
+ * Unexpected behaviour may occur if value is greater than the previous
+ * value in the node. This is not checked for and will probably mess up
+ * the whole Fibonacci heap. If not sure, check before using this
+ * function.
+ *
+ * @param heap the heap in which we find the node
+ * @param node the node to decrease the value of
+ * @param value the new value of the node
+ */
 void fheap_decrease_value(fheap_t *heap, fnode_t *node, const uint64_t value);
 
 #endif