[Skiboot] [PATCH v2 14/16] ccan: Add CCAN heap source
Jordan Niethe
jniethe5 at gmail.com
Tue Apr 2 10:43:25 AEDT 2019
We would like to be able to use dump_trace to dump multiple trace
buffers at a time. The entries should be displayed in timestamp order.
As each buffer is already ordered on timestamp, a k-way merge is an
efficient method to sort the buffers together by timestamp. A heap can
be used to implement a k-way merge. As CCAN is already included in
Skiboot, use the CCAN heap. Add the source for heap.
Signed-off-by: Jordan Niethe <jniethe5 at gmail.com>
---
ccan/Makefile.inc | 4 +-
ccan/heap/LICENSE | 1 +
ccan/heap/_info | 68 ++++++++++++++++++++++
ccan/heap/heap.c | 119 ++++++++++++++++++++++++++++++++++++++
ccan/heap/heap.h | 122 +++++++++++++++++++++++++++++++++++++++
ccan/heap/test/run.c | 133 +++++++++++++++++++++++++++++++++++++++++++
6 files changed, 445 insertions(+), 2 deletions(-)
create mode 120000 ccan/heap/LICENSE
create mode 100644 ccan/heap/_info
create mode 100644 ccan/heap/heap.c
create mode 100644 ccan/heap/heap.h
create mode 100644 ccan/heap/test/run.c
diff --git a/ccan/Makefile.inc b/ccan/Makefile.inc
index 36e75774a716..546891b62328 100644
--- a/ccan/Makefile.inc
+++ b/ccan/Makefile.inc
@@ -1,7 +1,7 @@
# -*-Makefile-*-
-SUBDIRS += ccan ccan/list ccan/str
-CCAN_OBJS = list/list.o str/str.o
+SUBDIRS += ccan ccan/list ccan/str ccan/heap
+CCAN_OBJS = list/list.o str/str.o heap/heap.o
CCAN=ccan/built-in.a
$(CCAN): $(CCAN_OBJS:%=ccan/%)
diff --git a/ccan/heap/LICENSE b/ccan/heap/LICENSE
new file mode 120000
index 000000000000..2354d12945d3
--- /dev/null
+++ b/ccan/heap/LICENSE
@@ -0,0 +1 @@
+../../licenses/BSD-MIT
\ No newline at end of file
diff --git a/ccan/heap/_info b/ccan/heap/_info
new file mode 100644
index 000000000000..fe5866d04677
--- /dev/null
+++ b/ccan/heap/_info
@@ -0,0 +1,68 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * heap - a simple heap implementation
+ *
+ * Each heap entry is added as a void pointer. This means the implementation
+ * does _not_ assume you already have an array of entries. Instead, it keeps
+ * an internal array of pointers to those entries.
+ *
+ * Example:
+ * #include <stdio.h>
+ *
+ * #include <ccan/heap/heap.h>
+ *
+ * static bool less(const int *i, const int *j)
+ * {
+ * return *i < *j;
+ * }
+ *
+ * static bool __less(const void *i, const void *j)
+ * {
+ * return less(i, j);
+ * }
+ *
+ * int main(int argc, char *argv[])
+ * {
+ * struct heap *h;
+ * int arr[] = {1, 0, 2};
+ * int i;
+ *
+ * h = heap_init(__less);
+ * if (h == NULL) {
+ * perror("heap alloc");
+ * exit(1);
+ * }
+ *
+ * for (i = 0; i < 3; i++) {
+ * if (heap_push(h, &arr[i])) {
+ * perror("heap push");
+ * exit(1);
+ * }
+ * }
+ * // should print 0, 1, 2
+ * for (i = 0; i < 3; i++) {
+ * int *v = heap_pop(h);
+ * printf("%d\n", *v);
+ * }
+ * heap_free(h);
+ * return 0;
+ * }
+ *
+ * License: BSD-MIT
+ * Author: Emilio G. Cota <cota at braap.org>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/heap/heap.c b/ccan/heap/heap.c
new file mode 100644
index 000000000000..aec9016788bb
--- /dev/null
+++ b/ccan/heap/heap.c
@@ -0,0 +1,119 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#include <ccan/heap/heap.h>
+
+/*
+ * Allocating memory in chunks greater than needed does not yield measurable
+ * speedups of the test program when linking against glibc 2.15.
+ *
+ * When the data array has to be shrunk though, limiting calls to realloc
+ * does help a little bit (~7% speedup), hence the following parameter.
+ */
+#define HEAP_MEM_HYSTERESIS 4096
+
+static inline void swap(struct heap *h, size_t i, size_t j)
+{
+ void *foo = h->data[i];
+
+ h->data[i] = h->data[j];
+ h->data[j] = foo;
+}
+
+static void __up(struct heap *h, size_t j)
+{
+ size_t i; /* parent */
+
+ while (j) {
+ i = (j - 1) / 2;
+
+ if (h->less(h->data[j], h->data[i])) {
+ swap(h, i, j);
+ j = i;
+ } else {
+ break;
+ }
+ }
+}
+
+int heap_push(struct heap *h, void *data)
+{
+ if (h->len == h->cap) {
+ void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
+ if (m == NULL)
+ return -1;
+ h->data = m;
+ h->cap++;
+ }
+ h->data[h->len++] = data;
+ __up(h, h->len - 1);
+ return 0;
+}
+
+static void __down(struct heap *h, size_t i)
+{
+ size_t l, r, j; /* left, right, min child */
+
+ while (1) {
+ l = 2 * i + 1;
+ if (l >= h->len)
+ break;
+ r = l + 1;
+ if (r >= h->len)
+ j = l;
+ else
+ j = h->less(h->data[l], h->data[r]) ? l : r;
+
+ if (h->less(h->data[j], h->data[i])) {
+ swap(h, i, j);
+ i = j;
+ } else {
+ break;
+ }
+ }
+}
+
+void *heap_pop(struct heap *h)
+{
+ void *ret = h->data[0];
+ void *m;
+
+ swap(h, 0, --h->len);
+ if (h->len) {
+ __down(h, 0);
+ if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
+ m = realloc(h->data, h->len * sizeof(void *));
+ if (m == NULL)
+ return NULL;
+ h->data = m;
+ h->cap = h->len;
+ }
+ }
+
+ return ret;
+}
+
+struct heap *heap_init(heap_less_func_t less)
+{
+ struct heap *heap = calloc(1, sizeof(*heap));
+
+ if (heap == NULL)
+ return NULL;
+ heap->less = less;
+ return heap;
+}
+
+void heap_ify(struct heap *h, heap_less_func_t less)
+{
+ int i;
+
+ if (less)
+ h->less = less;
+
+ for (i = h->len / 2 - 1; i >= 0; i--)
+ __down(h, i);
+}
+
+void heap_free(struct heap *heap)
+{
+ free(heap->data);
+ free(heap);
+}
diff --git a/ccan/heap/heap.h b/ccan/heap/heap.h
new file mode 100644
index 000000000000..69368a1ce719
--- /dev/null
+++ b/ccan/heap/heap.h
@@ -0,0 +1,122 @@
+/* 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. When in doubt,
+ * check heap->len. See heap_peek()'s documentation for an example.
+ *
+ * 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; check the heap's
+ * number of items and act accordingly, as in the example below.
+ *
+ * See also: heap_pop()
+ *
+ * Example:
+ * static inline void *heap_peek_safe(const struct heap *h)
+ * {
+ * return h->len ? heap_peek(h) : NULL;
+ * }
+ */
+static inline void *heap_peek(const struct heap *h)
+{
+ return h->data[0];
+}
+
+#endif /* CCAN_HEAP_H */
diff --git a/ccan/heap/test/run.c b/ccan/heap/test/run.c
new file mode 100644
index 000000000000..6972a6bea013
--- /dev/null
+++ b/ccan/heap/test/run.c
@@ -0,0 +1,133 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include <ccan/heap/heap.h>
+/* Include the C files directly. */
+#include <ccan/heap/heap.c>
+#include <ccan/tap/tap.h>
+
+struct item {
+ void *foobar;
+ int v;
+};
+
+static bool heap_ok(const struct heap *h, heap_less_func_t less, int i)
+{
+ int l, r;
+
+ l = 2 * i + 1;
+ r = l + 1;
+
+ if (l < h->len) {
+ if (less(h->data[l], h->data[i])) {
+ fprintf(stderr, "heap property violation\n");
+ return false;
+ }
+ if (!heap_ok(h, less, l))
+ return false;
+ }
+ if (r < h->len) {
+ if (less(h->data[r], h->data[i])) {
+ fprintf(stderr, "heap property violation\n");
+ return false;
+ }
+ if (!heap_ok(h, less, r))
+ return false;
+ }
+ return true;
+}
+
+static bool less(const struct item *a, const struct item *b)
+{
+ return a->v < b->v;
+}
+
+static bool __less(const void *a, const void *b)
+{
+ return less(a, b);
+}
+
+static bool more(const struct item *a, const struct item *b)
+{
+ return a->v > b->v;
+}
+
+static bool __more(const void *a, const void *b)
+{
+ return more(a, b);
+}
+
+static bool some_test(size_t n, bool is_less)
+{
+ struct item *items = calloc(n, sizeof(*items));
+ struct item *item, *prev;
+ struct heap *h;
+ int i;
+
+ if (items == NULL) {
+ perror("items");
+ exit(EXIT_FAILURE);
+ }
+
+ if (is_less)
+ h = heap_init(__less);
+ else
+ h = heap_init(__more);
+ if (h == NULL) {
+ perror("heap_init");
+ exit(EXIT_FAILURE);
+ }
+
+ for (i = 0; i < n; i++) {
+ item = &items[i];
+
+ item->v = rand();
+ printf("pushing %d\n", item->v);
+ heap_push(h, item);
+ if (!heap_ok(h, is_less ? __less : __more, 0))
+ return false;
+ }
+ if (is_less) {
+ heap_ify(h, __more);
+ if (!heap_ok(h, __more, 0))
+ return false;
+ heap_ify(h, __less);
+ if (!heap_ok(h, __less, 0))
+ return false;
+ } else {
+ heap_ify(h, NULL);
+ if (!heap_ok(h, __more, 0))
+ return false;
+ }
+
+ for (i = 0; i < n; i++) {
+ item = heap_pop(h);
+ if (!heap_ok(h, is_less ? __less : __more, 0))
+ return false;
+ printf("popped %d\n", item->v);
+ if (i > 0) {
+ if (is_less) {
+ if (less(item, prev))
+ return false;
+ } else {
+ if (more(item, prev))
+ return false;
+ }
+ }
+ prev = item;
+ }
+ heap_free(h);
+ free(items);
+ return true;
+}
+
+int main(void)
+{
+ plan_tests(3);
+
+ ok1(some_test(5000, true));
+ ok1(some_test(1, true));
+ ok1(some_test(33, false));
+
+ return exit_status();
+}
--
2.20.1
More information about the Skiboot
mailing list