From 5411b10cef90377afc584fc2562f26ac051fc357 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Tue, 11 Oct 2016 17:20:16 -0400 Subject: upload-pack: use priority queue in reachable() check Like a lot of old commit-traversal code, this keeps a commit_list in commit-date order, and and inserts parents into the list. This means each insertion is potentially linear, and the whole thing is quadratic (though the exact runtime depends on the relationship between the commit dates and the parent topology). These days we have a priority queue, which can do the same thing with a much better worst-case time. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- upload-pack.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'upload-pack.c') diff --git a/upload-pack.c b/upload-pack.c index 5ec21e61d9..d9e381f291 100644 --- a/upload-pack.c +++ b/upload-pack.c @@ -16,6 +16,7 @@ #include "string-list.h" #include "parse-options.h" #include "argv-array.h" +#include "prio-queue.h" static const char * const upload_pack_usage[] = { N_("git upload-pack [] "), @@ -319,12 +320,12 @@ static int got_sha1(const char *hex, unsigned char *sha1) static int reachable(struct commit *want) { - struct commit_list *work = NULL; + struct prio_queue work = { compare_commits_by_commit_date }; - commit_list_insert_by_date(want, &work); - while (work) { + prio_queue_put(&work, want); + while (work.nr) { struct commit_list *list; - struct commit *commit = pop_commit(&work); + struct commit *commit = prio_queue_get(&work); if (commit->object.flags & THEY_HAVE) { want->object.flags |= COMMON_KNOWN; @@ -340,12 +341,12 @@ static int reachable(struct commit *want) for (list = commit->parents; list; list = list->next) { struct commit *parent = list->item; if (!(parent->object.flags & REACHABLE)) - commit_list_insert_by_date(parent, &work); + prio_queue_put(&work, parent); } } want->object.flags |= REACHABLE; clear_commit_marks(want, REACHABLE); - free_commit_list(work); + clear_prio_queue(&work); return (want->object.flags & COMMON_KNOWN); } -- cgit v1.2.3