[PATCH 2/3] commit-queue: LIFO or priority queue of commits

[Junio C Hamano <gitster@pobox.com>]

Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history.  The most typical use
of the list is to insert commit that is newly discovered in it, keep
it sorted by commit timestamp, pick up the newest one from the list,
and keep digging.  The cost of keeping the singly linked list sorted
is nontrivial, and this typical use pattern better matches a priority
queue.

Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue.  This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Makefile       |  2 ++
 commit-queue.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 commit-queue.h | 31 +++++++++++++++++++++++++
 3 files changed, 104 insertions(+)
 create mode 100644 commit-queue.c
 create mode 100644 commit-queue.h

diff --git a/Makefile b/Makefile
index 598d631..3cf55e9 100644
--- a/Makefile
+++ b/Makefile
@@ -634,6 +634,7 @@ LIB_H += cache.h
 LIB_H += color.h
 LIB_H += column.h
 LIB_H += commit.h
+LIB_H += commit-queue.h
 LIB_H += compat/bswap.h
 LIB_H += compat/cygwin.h
 LIB_H += compat/mingw.h
@@ -757,6 +758,7 @@ LIB_OBJS += color.o
 LIB_OBJS += column.o
 LIB_OBJS += combine-diff.o
 LIB_OBJS += commit.o
+LIB_OBJS += commit-queue.o
 LIB_OBJS += compat/obstack.o
 LIB_OBJS += compat/terminal.o
 LIB_OBJS += config.o
diff --git a/commit-queue.c b/commit-queue.c
new file mode 100644
index 0000000..77d4b02
--- /dev/null
+++ b/commit-queue.c
@@ -0,0 +1,71 @@
+#include "cache.h"
+#include "commit.h"
+#include "commit-queue.h"
+
+void clear_commit_queue(struct commit_queue *queue)
+{
+	free(queue->array);
+	queue->nr = 0;
+	queue->alloc = 0;
+	queue->array = NULL;
+}
+
+void commit_queue_put(struct commit_queue *queue, struct commit *commit)
+{
+	commit_compare_fn compare = queue->compare;
+	int ix, parent;
+
+	/* Append at the end */
+	ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
+	queue->array[queue->nr++] = commit;
+	if (!compare)
+		return; /* LIFO */
+
+	/* Bubble up the new one */
+	for (ix = queue->nr - 1; ix; ix = parent) {
+		parent = (ix - 1) / 2;
+		if (compare(queue->array[parent], queue->array[ix],
+			    queue->cb_data) < 0)
+			break;
+
+		commit = queue->array[parent];
+		queue->array[parent] = queue->array[ix];
+		queue->array[ix] = commit;
+	}
+}
+
+struct commit *commit_queue_get(struct commit_queue *queue)
+{
+	struct commit *result, *swap;
+	int ix, child;
+	commit_compare_fn compare = queue->compare;
+
+	if (!queue->nr)
+		return NULL;
+	if (!compare)
+		return queue->array[--queue->nr]; /* LIFO */
+
+	result = queue->array[0];
+	if (!--queue->nr)
+		return result;
+
+	queue->array[0] = queue->array[queue->nr];
+
+	/* Push down the one at the root */
+	for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
+		child = ix * 2 + 1; /* left */
+		if ((child + 1 < queue->nr) &&
+		    (compare(queue->array[child], queue->array[child + 1],
+			     queue->cb_data) >= 0))
+			child++; /* use right child */
+
+		if (compare(queue->array[ix], queue->array[child],
+			    queue->cb_data) < 0)
+			break;
+
+		swap = queue->array[child];
+		queue->array[child] = queue->array[ix];
+		queue->array[ix] = swap;
+	}
+	return result;
+}
diff --git a/commit-queue.h b/commit-queue.h
new file mode 100644
index 0000000..7c5dc4c
--- /dev/null
+++ b/commit-queue.h
@@ -0,0 +1,31 @@
+#ifndef COMMIT_QUEUE_H
+#define COMMIT_QUEUE_H
+
+/*
+ * Compare two commits; the third parameter is cb_data in the
+ * commit_queue structure.
+ */
+typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);
+
+struct commit_queue {
+	commit_compare_fn compare;
+	void *cb_data;
+	int alloc, nr;
+	struct commit **array;
+};
+
+/*
+ * Add the commit to the queue
+ */
+extern void commit_queue_put(struct commit_queue *, struct commit *);
+
+/*
+ * Extract the commit that compares the smallest out of the queue,
+ * or NULL.  If compare function is NULL, the queue acts as a LIFO
+ * stack.
+ */
+extern struct commit *commit_queue_get(struct commit_queue *);
+
+extern void clear_commit_queue(struct commit_queue *);
+
+#endif /* COMMIT_QUEUE_H */
-- 
1.8.3-451-gb703ddf