1 files changed, 167 insertions, 0 deletions
diff --git a/src/heap.c b/src/heap.c
new file mode 100644
index 0000000..0d1a661
--- /dev/null
+++ b/src/heap.c
@@ -0,0 +1,167 @@
+/* heap.c - a linked heap implementation
+ *
+ * Copyright (C) 2009 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 or later as
+ * published by the Free Software Foundation.
+ *
+ * See http://www.gnu.org/ for details.
+ */
+
+#include <errno.h>
+#include <string.h>
+#include <libtf/heap.h>
+
+#define compare_values(a, b) tf_mtime_diff(a, b)
+
+static inline int tf_heap_parent(int index)
+{
+	return (index - TF_HEAP_ITEM0 - 1) / TF_HEAP_D + TF_HEAP_ITEM0;
+}
+
+static inline int tf_heap_first_child(int index)
+{
+	return TF_HEAP_D * (index - TF_HEAP_ITEM0) + TF_HEAP_ITEM0 + 1;
+}
+
+#if 0
+static void tf_heap_verify(struct tf_heap_head *head)
+{
+	int i, count = 0;
+
+	for (i = TF_HEAP_ITEM0; i < head->num_items + TF_HEAP_ITEM0; i++) {
+		if (head->item[i].ptr->index != i) {
+			printf("Heap item %d is corrupt ptr->index=%d\n", i, head->item[i].ptr->index);
+			count++;
+		}
+	}
+	TF_BUG_ON(count);
+}
+#endif
+
+static inline
+void tf_heap_downheap(struct tf_heap_child *heap, int last_index, int index)
+{
+	struct tf_heap_child he = heap[index];
+	struct tf_heap_child *minpos, *pos;
+	int c, i, mi;
+
+	while (1) {
+		c = tf_heap_first_child(index);
+		pos = &heap[c];
+
+		/* find minimum child */
+		minpos = pos;
+		mi = 0;
+		if (likely(c + TF_HEAP_D - 1 < last_index)) {
+			for (i = 1, pos++; i < TF_HEAP_D; i++, pos++)
+				if (compare_values(pos->val, minpos->val) < 0)
+					minpos = pos, mi = i;
+		} else if (c < last_index) {
+			for (i = 1, pos++; c + i < last_index; i++, pos++)
+				if (compare_values(pos->val, minpos->val) < 0)
+					minpos = pos, mi = i;
+	        } else
+			break;
+
+		if (compare_values(he.val, minpos->val) <= 0)
+			break;
+
+		heap[index] = *minpos;
+		minpos->ptr->index = index;
+		index = c + mi;
+	}
+
+	heap[index] = he;
+	he.ptr->index = index;
+}
+
+static inline
+void tf_heap_upheap(struct tf_heap_child *heap, int index)
+{
+	struct tf_heap_child he = heap[index];
+	int p = tf_heap_parent(index);
+
+	while (likely(index > TF_HEAP_ITEM0) &&
+	       compare_values(heap[p].val, he.val) > 0) {
+		heap[index] = heap[p];
+		heap[index].ptr->index = index;
+		index = p;
+		p = tf_heap_parent(p);
+	}
+
+	heap[index] = he;
+	he.ptr->index = index;
+}
+
+static inline
+void tf_heap_heapify(struct tf_heap_head *head, int index)
+{
+	struct tf_heap_child *heap = head->item;
+
+	if (likely(index > TF_HEAP_ITEM0) &&
+	    compare_values(heap[index].val, heap[tf_heap_parent(index)].val) <= 0)
+		tf_heap_upheap(heap, index);
+	else
+		tf_heap_downheap(heap, TF_HEAP_ITEM0 + head->num_items, index);
+}
+
+int __tf_heap_grow(struct tf_heap_head *head)
+{
+	void *item;
+
+	if (head->allocated)
+		head->allocated *= 2;
+	else
+		head->allocated = 128;
+
+	item = realloc(head->item, head->allocated * sizeof(head->item[0]));
+	if (item == NULL)
+		return -ENOMEM;
+
+	head->item = item;
+	return 0;
+}
+
+void tf_heap_insert(struct tf_heap_node *node, struct tf_heap_head *head,
+		    tf_heap_priority val)
+{
+	int i;
+
+	tf_heap_prealloc(head, head->num_items + 1);
+
+	i = node->index = TF_HEAP_ITEM0 + head->num_items;
+	head->num_items++;
+	head->item[i].ptr = node;
+	head->item[i].val = val;
+	tf_heap_upheap(head->item, i);
+}
+
+void tf_heap_delete(struct tf_heap_node *node, struct tf_heap_head *head)
+{
+	int index = node->index;
+
+	if (index == 0)
+		return;
+
+	head->num_items--;
+	if (likely(index < head->num_items + TF_HEAP_ITEM0)) {
+		head->item[index] = head->item[head->num_items+TF_HEAP_ITEM0];
+		tf_heap_heapify(head, index);
+	}
+	head->item[head->num_items+TF_HEAP_ITEM0].ptr = NULL;
+	node->index = 0;
+}
+
+void tf_heap_change(struct tf_heap_node *node, struct tf_heap_head *head,
+		    tf_heap_priority val)
+{
+	if (likely(node->index != 0)) {
+		head->item[node->index].val = val;
+		tf_heap_heapify(head, node->index);
+	} else {
+		tf_heap_insert(node, head, val);
+	}
+}