diff options
| -rw-r--r-- | builtin/describe.c | 87 |
1 files changed, 63 insertions, 24 deletions
diff --git a/builtin/describe.c b/builtin/describe.c index d7dd8139de..0540976210 100644 --- a/builtin/describe.c +++ b/builtin/describe.c @@ -23,6 +23,7 @@ #include "list-objects.h" #include "commit-slab.h" #include "wildmatch.h" +#include "prio-queue.h" #define MAX_TAGS (FLAG_BITS - 1) #define DEFAULT_CANDIDATES 10 @@ -249,24 +250,62 @@ static int compare_pt(const void *a_, const void *b_) return 0; } -static unsigned long finish_depth_computation( - struct commit_list **list, - struct possible_tag *best) +struct lazy_queue { + struct prio_queue queue; + bool get_pending; +}; + +#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false } + +static void *lazy_queue_get(struct lazy_queue *queue) +{ + if (queue->get_pending) + prio_queue_get(&queue->queue); + else + queue->get_pending = true; + return prio_queue_peek(&queue->queue); +} + +static void lazy_queue_put(struct lazy_queue *queue, void *thing) +{ + if (queue->get_pending) + prio_queue_replace(&queue->queue, thing); + else + prio_queue_put(&queue->queue, thing); + queue->get_pending = false; +} + +static bool lazy_queue_empty(const struct lazy_queue *queue) +{ + return queue->queue.nr == (queue->get_pending ? 1 : 0); +} + +static void lazy_queue_clear(struct lazy_queue *queue) +{ + clear_prio_queue(&queue->queue); + queue->get_pending = false; +} + +static bool all_have_flag(const struct lazy_queue *queue, unsigned flag) +{ + for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) { + struct commit *commit = queue->queue.array[i].data; + if (!(commit->object.flags & flag)) + return false; + } + return true; +} + +static unsigned long finish_depth_computation(struct lazy_queue *queue, + struct possible_tag *best) { unsigned long seen_commits = 0; - while (*list) { - struct commit *c = pop_commit(list); + while (!lazy_queue_empty(queue)) { + struct commit *c = lazy_queue_get(queue); struct commit_list *parents = c->parents; seen_commits++; if (c->object.flags & best->flag_within) { - struct commit_list *a = *list; - while (a) { - struct commit *i = a->item; - if (!(i->object.flags & best->flag_within)) - break; - a = a->next; - } - if (!a) + if (all_have_flag(queue, best->flag_within)) break; } else best->depth++; @@ -274,7 +313,7 @@ static unsigned long finish_depth_computation( struct commit *p = parents->item; repo_parse_commit(the_repository, p); if (!(p->object.flags & SEEN)) - commit_list_insert_by_date(p, list); + lazy_queue_put(queue, p); p->object.flags |= c->object.flags; parents = parents->next; } @@ -316,7 +355,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf static void describe_commit(struct object_id *oid, struct strbuf *dst) { struct commit *cmit, *gave_up_on = NULL; - struct commit_list *list; + struct lazy_queue queue = LAZY_QUEUE_INIT; struct commit_name *n; struct possible_tag all_matches[MAX_TAGS]; unsigned int match_cnt = 0, annotated_cnt = 0, cur_match; @@ -359,11 +398,10 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst) have_util = 1; } - list = NULL; cmit->object.flags = SEEN; - commit_list_insert(cmit, &list); - while (list) { - struct commit *c = pop_commit(&list); + lazy_queue_put(&queue, cmit); + while (!lazy_queue_empty(&queue)) { + struct commit *c = lazy_queue_get(&queue); struct commit_list *parents = c->parents; struct commit_name **slot; @@ -397,7 +435,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst) t->depth++; } /* Stop if last remaining path already covered by best candidate(s) */ - if (annotated_cnt && !list) { + if (annotated_cnt && lazy_queue_empty(&queue)) { int best_depth = INT_MAX; unsigned best_within = 0; for (cur_match = 0; cur_match < match_cnt; cur_match++) { @@ -420,7 +458,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst) struct commit *p = parents->item; repo_parse_commit(the_repository, p); if (!(p->object.flags & SEEN)) - commit_list_insert_by_date(p, &list); + lazy_queue_put(&queue, p); p->object.flags |= c->object.flags; parents = parents->next; @@ -435,6 +473,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst) strbuf_add_unique_abbrev(dst, cmit_oid, abbrev); if (suffix) strbuf_addstr(dst, suffix); + lazy_queue_clear(&queue); return; } if (unannotated_cnt) @@ -450,11 +489,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst) QSORT(all_matches, match_cnt, compare_pt); if (gave_up_on) { - commit_list_insert_by_date(gave_up_on, &list); + lazy_queue_put(&queue, gave_up_on); seen_commits--; } - seen_commits += finish_depth_computation(&list, &all_matches[0]); - free_commit_list(list); + seen_commits += finish_depth_computation(&queue, &all_matches[0]); + lazy_queue_clear(&queue); if (debug) { static int label_width = -1; |