[PATCH 2/4] basic priority queue implementation

[Jeff King <peff@peff.net>]

This can provide better algorithmic complexity for some of
the date-sorted commit list uses, among other things.

The queue is stored as a heap, allowing O(log) insertion and
top-element removal, and O(1) peeking at the top element.
Current commit lists are sorted linked lists, giving O(1)
peeking and top-element removal, but O(n^2) insertion.

Signed-off-by: Jeff King <peff@peff.net>
---
 .gitignore       |    1 +
 Makefile         |    3 ++
 queue.c          |   70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 queue.h          |   17 +++++++++++++
 t/t0007-queue.sh |   50 ++++++++++++++++++++++++++++++++++++++
 test-queue.c     |   39 ++++++++++++++++++++++++++++++
 6 files changed, 180 insertions(+), 0 deletions(-)
 create mode 100644 queue.c
 create mode 100644 queue.h
 create mode 100755 t/t0007-queue.sh
 create mode 100644 test-queue.c

diff --git a/.gitignore b/.gitignore
index 711fce7..179483a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -174,6 +174,7 @@
 /test-obj-pool
 /test-parse-options
 /test-path-utils
+/test-queue
 /test-run-command
 /test-sha1
 /test-sigchain
diff --git a/Makefile b/Makefile
index d09ee70..737b2d5 100644
--- a/Makefile
+++ b/Makefile
@@ -422,6 +422,7 @@ TEST_PROGRAMS_NEED_X += test-mktemp
 TEST_PROGRAMS_NEED_X += test-obj-pool
 TEST_PROGRAMS_NEED_X += test-parse-options
 TEST_PROGRAMS_NEED_X += test-path-utils
+TEST_PROGRAMS_NEED_X += test-queue
 TEST_PROGRAMS_NEED_X += test-run-command
 TEST_PROGRAMS_NEED_X += test-sha1
 TEST_PROGRAMS_NEED_X += test-sigchain
@@ -532,6 +533,7 @@ LIB_H += parse-options.h
 LIB_H += patch-ids.h
 LIB_H += pkt-line.h
 LIB_H += progress.h
+LIB_H += queue.h
 LIB_H += quote.h
 LIB_H += reflog-walk.h
 LIB_H += refs.h
@@ -629,6 +631,7 @@ LIB_OBJS += pkt-line.o
 LIB_OBJS += preload-index.o
 LIB_OBJS += pretty.o
 LIB_OBJS += progress.o
+LIB_OBJS += queue.o
 LIB_OBJS += quote.o
 LIB_OBJS += reachable.o
 LIB_OBJS += read-cache.o
diff --git a/queue.c b/queue.c
new file mode 100644
index 0000000..068b559
--- /dev/null
+++ b/queue.c
@@ -0,0 +1,70 @@
+#include "queue.h"
+#include "cache.h"
+
+static inline void queue_swap(struct queue *pq, unsigned i, unsigned j)
+{
+	void *tmp = pq->items[i];
+	pq->items[i] = pq->items[j];
+	pq->items[j] = tmp;
+}
+
+static void queue_heapify_up(struct queue *pq)
+{
+	unsigned i = pq->nr - 1;
+	while (i > 0) {
+		int parent = (i-1)/2;
+
+		if (pq->cmp(pq->items[i], pq->items[parent]) <= 0)
+			return;
+
+		queue_swap(pq, i, parent);
+		i = parent;
+	}
+}
+
+void queue_insert(struct queue *pq, void *item)
+{
+	ALLOC_GROW(pq->items, pq->nr + 1, pq->alloc);
+	pq->items[pq->nr++] = item;
+	queue_heapify_up(pq);
+}
+
+static void queue_heapify_down(struct queue *pq)
+{
+	unsigned i = 0;
+	while (1) {
+		int largest = i, left = 2*i + 1, right = 2*i + 2;
+
+		if (left < pq->nr &&
+		    pq->cmp(pq->items[left], pq->items[largest]) > 0)
+			largest = left;
+		if (right < pq->nr &&
+		    pq->cmp(pq->items[right], pq->items[largest]) > 0)
+			largest = right;
+
+		if (largest == i)
+			return;
+
+		queue_swap(pq, i, largest);
+		i = largest;
+	}
+}
+
+void *queue_peek(struct queue *pq)
+{
+	return pq->nr ? pq->items[0] : NULL;
+}
+
+void *queue_pop(struct queue *pq)
+{
+	void *ret;
+
+	if (!pq->nr)
+		return NULL;
+	ret = pq->items[0];
+
+	pq->items[0] = pq->items[--pq->nr];
+	queue_heapify_down(pq);
+
+	return ret;
+}
diff --git a/queue.h b/queue.h
new file mode 100644
index 0000000..fee5a51
--- /dev/null
+++ b/queue.h
@@ -0,0 +1,17 @@
+#ifndef QUEUE_H
+#define QUEUE_H
+
+typedef int (*queue_comparison_func_t)(const void *, const void *);
+
+struct queue {
+	queue_comparison_func_t cmp;
+	void **items;
+	unsigned nr;
+	unsigned alloc;
+};
+
+void queue_insert(struct queue *pq, void *item);
+void *queue_peek(struct queue *pq);
+void *queue_pop(struct queue *pq);
+
+#endif /* QUEUE_H */
diff --git a/t/t0007-queue.sh b/t/t0007-queue.sh
new file mode 100755
index 0000000..ee357bb
--- /dev/null
+++ b/t/t0007-queue.sh
@@ -0,0 +1,50 @@
+#!/bin/sh
+
+test_description='basic tests for priority queue implementation'
+. ./test-lib.sh
+
+cat >expect <<'EOF'
+10
+9
+8
+7
+6
+5
+5
+4
+3
+2
+1
+EOF
+test_expect_success 'basic ordering' '
+	test-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
+	test_cmp expect actual
+'
+
+cat >expect <<'EOF'
+3
+5
+4
+6
+2
+1
+EOF
+test_expect_success 'mixed insert and pop' '
+	test-queue 1 2 3 pop 4 5 pop pop 6 dump >actual &&
+	test_cmp expect actual
+'
+
+cat >expect <<'EOF'
+2
+1
+NULL
+2
+1
+NULL
+EOF
+test_expect_success 'notice empty queue' '
+	test-queue 1 2 pop pop pop 1 2 pop pop pop >actual &&
+	test_cmp expect actual
+'
+
+test_done
diff --git a/test-queue.c b/test-queue.c
new file mode 100644
index 0000000..a1e92e2
--- /dev/null
+++ b/test-queue.c
@@ -0,0 +1,39 @@
+#include "cache.h"
+#include "queue.h"
+
+static int intcmp(const void *va, const void *vb)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+static void show(int *v)
+{
+	if (!v)
+		printf("NULL\n");
+	else
+		printf("%d\n", *v);
+	free(v);
+}
+
+int main(int argc, char **argv)
+{
+	struct queue pq = { intcmp };
+
+	while (*++argv) {
+		if (!strcmp(*argv, "pop"))
+			show(queue_pop(&pq));
+		else if (!strcmp(*argv, "dump")) {
+			int *v;
+			while ((v = queue_pop(&pq)))
+			       show(v);
+		}
+		else {
+			int *v = malloc(sizeof(*v));
+			*v = atoi(*argv);
+			queue_insert(&pq, v);
+		}
+	}
+
+	return 0;
+}
-- 
1.7.5.8.ga95ab