Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits

On Mon, Jun 10, 2013 at 12:21:00AM -0700, Junio C Hamano wrote:

quoted

It may be worth looking again for other places to use this over
commit_list, but even the caller you are introducing here justifies its
presence.

The next candidate is paint-down-to-common, probably.

Yeah, I don't think I looked at that at all last time (mostly because it
only large as the graph gets wide, which is typically acceptable for
us). But it should be easy to do.

quoted

Also, I wrote some basic tests to cover the priority queue as a unit. I
can rebase them on your commit if you are interested.

It would be great.

Squashable patch is below.

quoted

Is it worth making this "struct commit *" a void pointer, and handling
arbitrary items in our priority queue? The compare function should be
the only thing that dereferences them.
 
I do not have any non-commit priority queue use in mind, but I do not
think it adds any complexity in this case.

I didn't either (and still I don't think of one), but I agree that
the implementation can be reused for pq of any type, as long as it
is a pointer to struct.

I converted this to a void pointer in my patch below, simply because it
makes it easier to write a test-queue that operates on ints. Due to
implicit casting, it should work for the most part without changing the
calling code unless you have a caller that does something like:

  commit_queue_get(&q)->date

or similar. I didn't change the name, either. It may be silly to call it
"commit_queue" still since it is now more general. I simply called mine
"queue" (I wanted "pqueue", but that conflicted with globals defined by
OpenSSL; yours is a more general queue anyway, so maybe that is a good
name).

quoted

quoted

+	/* 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;

In my implementation, I stopped on "compare() <= 0". It is late and my
mind is fuzzy, but I recall that heaps are never stable with respect to
insertion order, so I don't think it would matter.

It would matter in the sense that we cannot replace linked-list, if
the caller wants stability.  It is more like "we cannot do anything
about it" than "it would not matter".

Right. I meant "I do not think it matters if you do <= or < here, as we
are not stable anyway". Doing "<= 0" stops the heapify operation sooner,
though I doubt it matters in practice (it is not an algorithmic
complexity change, but just that you can sometimes quit early).

I think it is the same situation in your "push down", too, where you can
quit when the parent is equal to the largest child.

We can make each queue element a pair of <pointer to payload,
insertion counter>, and tiebreak using the insertion order, if the
callers want the same stability as linked-list implementation, but
I tend to think it really matters.

Yes, I think that is the usual solution.

Here's the patch with the tests, meant to be squashed into your 2/4. As
I mentioned above, you may want to further tweak the name, which would
require fixing up the rebase patches on top.

If you don't want to do the "s/struct commit/void/" change now, we can
probably just have test-queue stuff the ints into commit pointers.

The tests themselves are not extremely extensive, but at least let you
check that you implemented the heap correctly. :)

---
 .gitignore       |  1 +
 Makefile         |  1 +
 commit-queue.c   |  6 ++---
 commit-queue.h   |  8 +++---
 t/t0009-queue.sh | 50 +++++++++++++++++++++++++++++++++++
 test-queue.c     | 39 +++++++++++++++++++++++++++
 6 files changed, 98 insertions(+), 7 deletions(-)

diff --git a/.gitignore b/.gitignore
index 6669bf0..8670e6d 100644
--- a/.gitignore
+++ b/.gitignore

@@ -193,6 +193,7 @@
 /test-regex
 /test-revision-walking
 /test-run-command
+/test-queue
 /test-sha1
 /test-sigchain
 /test-string-list

diff --git a/Makefile b/Makefile
index 3cf55e9..c957637 100644
--- a/Makefile
+++ b/Makefile

@@ -552,6 +552,7 @@ TEST_PROGRAMS_NEED_X += test-path-utils
 TEST_PROGRAMS_NEED_X += test-mktemp
 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-regex
 TEST_PROGRAMS_NEED_X += test-revision-walking
 TEST_PROGRAMS_NEED_X += test-run-command

diff --git a/commit-queue.c b/commit-queue.c
index 77d4b02..04acf23 100644
--- a/commit-queue.c
+++ b/commit-queue.c

@@ -10,7 +10,7 @@ void clear_commit_queue(struct commit_queue *queue)
 	queue->array = NULL;
 }
 
-void commit_queue_put(struct commit_queue *queue, struct commit *commit)
+void commit_queue_put(struct commit_queue *queue, void *commit)
 {
 	commit_compare_fn compare = queue->compare;
 	int ix, parent;

@@ -34,9 +34,9 @@ struct commit *commit_queue_get(struct commit_queue *queue)
 	}
 }
 
-struct commit *commit_queue_get(struct commit_queue *queue)
+void *commit_queue_get(struct commit_queue *queue)
 {
-	struct commit *result, *swap;
+	void *result, *swap;
 	int ix, child;
 	commit_compare_fn compare = queue->compare;
 

diff --git a/commit-queue.h b/commit-queue.h
index 7c5dc4c..ef8fb87 100644
--- a/commit-queue.h
+++ b/commit-queue.h

@@ -5,26 +5,26 @@ extern void commit_queue_put(struct commit_queue *, struct commit *);
  * Compare two commits; the third parameter is cb_data in the
  * commit_queue structure.
  */
-typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);
+typedef int (*commit_compare_fn)(void *, void *, void *);
 
 struct commit_queue {
 	commit_compare_fn compare;
 	void *cb_data;
 	int alloc, nr;
-	struct commit **array;
+	void **array;
 };
 
 /*
  * Add the commit to the queue
  */
-extern void commit_queue_put(struct commit_queue *, struct commit *);
+extern void commit_queue_put(struct commit_queue *, void *);
 
 /*
  * 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 *commit_queue_get(struct commit_queue *);
 
 extern void clear_commit_queue(struct commit_queue *);
 

diff --git a/t/t0009-queue.sh b/t/t0009-queue.sh
new file mode 100755
index 0000000..186df01
--- /dev/null
+++ b/t/t0009-queue.sh

@@ -0,0 +1,50 @@
+#!/bin/sh
+
+test_description='basic tests for priority queue implementation'
+. ./test-lib.sh
+
+cat >expect <<'EOF'
+1
+2
+3
+4
+5
+5
+6
+7
+8
+9
+10
+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'
+2
+3
+4
+1
+5
+6
+EOF
+test_expect_success 'mixed put and get' '
+	test-queue 6 2 4 get 5 3 get get 1 dump >actual &&
+	test_cmp expect actual
+'
+
+cat >expect <<'EOF'
+1
+2
+NULL
+1
+2
+NULL
+EOF
+test_expect_success 'notice empty queue' '
+	test-queue 1 2 get get get 1 2 get get get >actual &&
+	test_cmp expect actual
+'
+
+test_done

diff --git a/test-queue.c b/test-queue.c
new file mode 100644
index 0000000..7743775
--- /dev/null
+++ b/test-queue.c

@@ -0,0 +1,39 @@
+#include "cache.h"
+#include "commit-queue.h"
+
+static int intcmp(void *va, void *vb, void *data)
+{
+	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 commit_queue pq = { intcmp };
+
+	while (*++argv) {
+		if (!strcmp(*argv, "get"))
+			show(commit_queue_get(&pq));
+		else if (!strcmp(*argv, "dump")) {
+			int *v;
+			while ((v = commit_queue_get(&pq)))
+			       show(v);
+		}
+		else {
+			int *v = malloc(sizeof(*v));
+			*v = atoi(*argv);
+			commit_queue_put(&pq, v);
+		}
+	}
+
+	return 0;
+}