heap: new module

[ccan] / ccan / heap / heap.h

diff --git a/ccan/heap/heap.h b/ccan/heap/heap.h
new file mode 100644 (file)
index 0000000..e7694a3
--- /dev/null
+++ b/ccan/heap/heap.h
@@ -0,0 +1,114 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_HEAP_H
+#define CCAN_HEAP_H
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+typedef bool (*heap_less_func_t)(const void *, const void *);
+
+/**
+ * struct heap - a simple, generic heap structure
+ * @data: array of pointers to the heap's entries
+ * @less: function to compare heap entries
+ * @cap: capacity of the heap array in @data
+ * @len: number of valid elements in the heap array
+ *
+ * The @less function determines the nature of the heap. If @less is
+ * something akin to 'return a.foo < b.foo', then the heap will be
+ * a min heap. Conversely, a '>' predicate will result in a max heap.
+ *
+ * Elements in the @data array are allocated as needed, hence the need for
+ * @cap and @len.
+ */
+struct heap {
+       void **data;
+       heap_less_func_t less;
+       size_t cap;
+       size_t len;
+};
+
+/**
+ * heap_init - allocate and initialise an empty heap
+ * @less: function to be used to compare heap entries
+ *
+ * Returns a pointer to an initialised heap struct on success, NULL if
+ * the heap could not be allocated.
+ *
+ * See also: HEAP_INIT()
+ */
+struct heap *heap_init(heap_less_func_t less);
+
+/**
+ * HEAP_INIT - initialiser for an empty heap
+ * @func: comparison function to be used in the heap
+ *
+ * Explicit initialiser for a heap.
+ *
+ * See also: heap_init()
+ */
+#define HEAP_INIT(func) { NULL, func, 0, 0 }
+
+/**
+ * heap_free - free a heap allocated via heap_init()
+ * @heap: the heap to be freed
+ *
+ * Note that this only frees the heap and its internal resources, not
+ * the entries pointed to by it.
+ *
+ * See also: heap_init()
+ */
+void heap_free(struct heap *heap);
+
+/**
+ * heap_ify - enforce the heap property based on a new comparison function
+ * @h: heap to be heapified
+ * @less: new comparison function
+ *
+ * Complexity: O(n)
+ */
+void heap_ify(struct heap *h, heap_less_func_t less);
+
+/**
+ * heap_push - push a new heap entry
+ * @h: heap to receive the new entry
+ * @data: pointer to the new entry
+ *
+ * Returns 0 on success, -1 on error.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_pop()
+ */
+int heap_push(struct heap *h, void *data);
+
+/**
+ * heap_pop - pops the root heap entry
+ * @h: heap to pop the head from
+ *
+ * Returns the root entry of the heap after extracting it, or NULL on error.
+ *
+ * Note: Calling heap_pop() on an empty heap is a bug--don't do it.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_push(), heap_peek()
+ */
+void *heap_pop(struct heap *h);
+
+/**
+ * heap_peek - inspect the root entry of a heap
+ * @h: heap whose root entry is to be inspected
+ *
+ * Returns the root entry in the heap, without extracting it from @h.
+ *
+ * Note: Calling heap_peek() on an empty heap is a bug--don't do it.
+ *
+ * See also: heap_pop()
+ */
+static inline void *heap_peek(const struct heap *h)
+{
+       return h->data[0];
+}
+
+#endif /* CCAN_HEAP_H */