1 files changed, 119 insertions, 0 deletions
diff --git a/roms/skiboot/ccan/heap/heap.c b/roms/skiboot/ccan/heap/heap.c
new file mode 100644
index 000000000..aec901678
--- /dev/null
+++ b/roms/skiboot/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);
+}