Merge branch 'rs/pop-recent-commit-with-prio-queue'

The pop_most_recent_commit() function can have quite expensive
worst case performance characteristics, which has been optimized by
using prio-queue data structure.

* rs/pop-recent-commit-with-prio-queue:
  commit: use prio_queue_replace() in pop_most_recent_commit()
  prio-queue: add prio_queue_replace()
  commit: convert pop_most_recent_commit() to prio_queue

1 files changed, 11 insertions, 3 deletions

diff --git a/commit.c b/commit.c
index 15115125c3..ea84c8e7f6 100644
--- a/commit.c
+++ b/commit.c
@@ -31,6 +31,7 @@
 #include "parse.h"
 #include "object-file.h"
 #include "object-file-convert.h"
+#include "prio-queue.h"
 
 static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
 
@@ -739,20 +740,27 @@ void commit_list_sort_by_date(struct commit_list **list)
 	commit_list_sort(list, commit_list_compare_by_date);
 }
 
-struct commit *pop_most_recent_commit(struct commit_list **list,
+struct commit *pop_most_recent_commit(struct prio_queue *queue,
 				      unsigned int mark)
 {
-	struct commit *ret = pop_commit(list);
+	struct commit *ret = prio_queue_peek(queue);
+	int get_pending = 1;
 	struct commit_list *parents = ret->parents;
 
 	while (parents) {
 		struct commit *commit = parents->item;
 		if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
 			commit->object.flags |= mark;
-			commit_list_insert_by_date(commit, list);
+			if (get_pending)
+				prio_queue_replace(queue, commit);
+			else
+				prio_queue_put(queue, commit);
+			get_pending = 0;
 		}
 		parents = parents->next;
 	}
+	if (get_pending)
+		prio_queue_get(queue);
 	return ret;
 }