[PATCH 3/4] commit: add infrastructure for priority queues of commits

[Jeff King <peff@xxxxxxxx>]

Using a priority queue to store date-ordered commits can be
algorithmically faster than the current implementation
(which uses sorted linked lists).

The previous commit introduced a generic priority queue.
This commit adds some infrastructure for using it with
commits. Specifically:

  1. A date-comparison function and queue-initializer, so
     you can create a queue like:

       struct queue pq = COMMIT_QUEUE_INIT;

  2. A function to pop the most recent commit from the
     queue, adding its parents to the queue unless a
     particular mark is seen on them. This is equivalent to
     the current pop_most_recent_commit, which operates on
     commit_list structs.

Signed-off-by: Jeff King <peff@xxxxxxxx>
---
 commit.c |   27 +++++++++++++++++++++++++++
 commit.h |    5 +++++
 2 files changed, 32 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index ac337c7..9d0a182 100644
--- a/commit.c
+++ b/commit.c
@@ -419,6 +419,33 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
 	return ret;
 }
 
+int commit_datecmp(const void *va, const void *vb)
+{
+	const struct commit *a = va, *b = vb;
+	if (a->date < b->date)
+		return -1;
+	else if (a->date > b->date)
+		return 1;
+	return 0;
+}
+
+struct commit *pop_commit_from_queue(struct queue *pq, unsigned int mark)
+{
+	struct commit *ret = queue_pop(pq);
+	struct commit_list *parents = ret ? ret->parents : NULL;
+
+	while (parents) {
+		struct commit *commit = parents->item;
+		if (!parse_commit(commit) && !(commit->object.flags & mark)) {
+			commit->object.flags |= mark;
+			queue_insert(pq, commit);
+		}
+		parents = parents->next;
+	}
+
+	return ret;
+}
+
 void clear_commit_marks(struct commit *commit, unsigned int mark)
 {
 	while (commit) {
diff --git a/commit.h b/commit.h
index 43940e2..87c9b4a 100644
--- a/commit.h
+++ b/commit.h
@@ -5,6 +5,7 @@
 #include "tree.h"
 #include "strbuf.h"
 #include "decorate.h"
+#include "queue.h"
 
 struct commit_list {
 	struct commit *item;
@@ -121,6 +122,10 @@ void pp_remainder(enum cmit_fmt fmt,
 struct commit *pop_most_recent_commit(struct commit_list **list,
 				      unsigned int mark);
 
+#define COMMIT_QUEUE_INIT { commit_datecmp }
+int commit_datecmp(const void *a, const void *b);
+struct commit *pop_commit_from_queue(struct queue *pq, unsigned int mark);
+
 struct commit *pop_commit(struct commit_list **stack);
 
 void clear_commit_marks(struct commit *commit, unsigned int mark);
-- 
1.7.5.8.ga95ab

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html