From: Junio C Hamano Date: Thu, 25 Apr 2019 07:41:18 +0000 (+0900) Subject: Merge branch 'jk/revision-rewritten-parents-in-prio-queue' X-Git-Tag: v2.22.0-rc0~56 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/d9d65e9f6ab3f5f1525ae8c86dfbab5978adf846?hp=-c Merge branch 'jk/revision-rewritten-parents-in-prio-queue' Performance fix for "rev-list --parents -- pathspec". * jk/revision-rewritten-parents-in-prio-queue: revision: use a prio_queue to hold rewritten parents --- d9d65e9f6ab3f5f1525ae8c86dfbab5978adf846 diff --combined revision.c index 60553d829d,9265200b7a..d4aaf0ef25 --- a/revision.c +++ b/revision.c @@@ -911,26 -911,11 +911,11 @@@ static void try_to_simplify_commit(stru commit->object.flags |= TREESAME; } - static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head, - struct commit_list *cached_base, struct commit_list **cache) - { - struct commit_list *new_entry; - - if (cached_base && p->date < cached_base->item->date) - new_entry = commit_list_insert_by_date(p, &cached_base->next); - else - new_entry = commit_list_insert_by_date(p, head); - - if (cache && (!*cache || p->date < (*cache)->item->date)) - *cache = new_entry; - } - static int process_parents(struct rev_info *revs, struct commit *commit, - struct commit_list **list, struct commit_list **cache_ptr) + struct commit_list **list, struct prio_queue *queue) { struct commit_list *parent = commit->parents; unsigned left_flag; - struct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL; if (commit->object.flags & ADDED) return 0; @@@ -966,7 -951,9 +951,9 @@@ continue; p->object.flags |= SEEN; if (list) - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + commit_list_insert_by_date(p, list); + if (queue) + prio_queue_put(queue, p); } return 0; } @@@ -1006,7 -993,9 +993,9 @@@ if (!(p->object.flags & SEEN)) { p->object.flags |= SEEN; if (list) - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + commit_list_insert_by_date(p, list); + if (queue) + prio_queue_put(queue, p); } if (revs->first_parent_only) break; @@@ -1894,7 -1883,7 +1883,7 @@@ int handle_revision_arg(const char *arg return 0; } -static void read_pathspec_from_stdin(struct rev_info *revs, struct strbuf *sb, +static void read_pathspec_from_stdin(struct strbuf *sb, struct argv_array *prune) { while (strbuf_getline(sb, stdin) != EOF) @@@ -1928,7 -1917,7 +1917,7 @@@ static void read_revisions_from_stdin(s die("bad revision '%s'", sb.buf); } if (seen_dashdash) - read_pathspec_from_stdin(revs, &sb, prune); + read_pathspec_from_stdin(&sb, prune); strbuf_release(&sb); warn_on_object_refname_ambiguity = save_warning; @@@ -2151,9 -2140,6 +2140,9 @@@ static int handle_revision_opt(struct r revs->diff = 1; revs->dense_combined_merges = 0; revs->combine_merges = 1; + } else if (!strcmp(arg, "--combined-all-paths")) { + revs->diff = 1; + revs->combined_all_paths = 1; } else if (!strcmp(arg, "--cc")) { revs->diff = 1; revs->dense_combined_merges = 1; @@@ -2650,9 -2636,6 +2639,9 @@@ int setup_revisions(int argc, const cha } if (revs->combine_merges) revs->ignore_merges = 0; + if (revs->combined_all_paths && !revs->combine_merges) + die("--combined-all-paths makes no sense without -c or --cc"); + revs->diffopt.abbrev = revs->abbrev; if (revs->line_level_traverse) { @@@ -2689,10 -2672,6 +2678,10 @@@ if (revs->first_parent_only && revs->bisect) die(_("--first-parent is incompatible with --bisect")); + if (revs->line_level_traverse && + (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT))) + die(_("-L does not yet support diff formats besides -p and -s")); + if (revs->expand_tabs_in_log < 0) revs->expand_tabs_in_log = revs->expand_tabs_in_log_default; @@@ -2752,7 -2731,7 +2741,7 @@@ static struct merge_simplify_state *loc return st; } -static int mark_redundant_parents(struct rev_info *revs, struct commit *commit) +static int mark_redundant_parents(struct commit *commit) { struct commit_list *h = reduce_heads(commit->parents); int i = 0, marked = 0; @@@ -2788,7 -2767,7 +2777,7 @@@ return marked; } -static int mark_treesame_root_parents(struct rev_info *revs, struct commit *commit) +static int mark_treesame_root_parents(struct commit *commit) { struct commit_list *p; int marked = 0; @@@ -2980,8 -2959,8 +2969,8 @@@ static struct commit_list **simplify_on * Detect and simplify both cases. */ if (1 < cnt) { - int marked = mark_redundant_parents(revs, commit); - marked += mark_treesame_root_parents(revs, commit); + int marked = mark_redundant_parents(commit); + marked += mark_treesame_root_parents(commit); if (marked) marked -= leave_one_treesame_to_parent(revs, commit); if (marked) @@@ -3345,14 -3324,14 +3334,14 @@@ int prepare_revision_walk(struct rev_in return 0; } - static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp) + static enum rewrite_result rewrite_one_1(struct rev_info *revs, + struct commit **pp, + struct prio_queue *queue) { - struct commit_list *cache = NULL; - for (;;) { struct commit *p = *pp; if (!revs->limited) - if (process_parents(revs, p, &revs->commits, &cache) < 0) + if (process_parents(revs, p, NULL, queue) < 0) return rewrite_one_error; if (p->object.flags & UNINTERESTING) return rewrite_one_ok; @@@ -3366,6 -3345,31 +3355,31 @@@ } } + static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list) + { + while (q->nr) { + struct commit *item = prio_queue_peek(q); + struct commit_list *p = *list; + + if (p && p->item->date >= item->date) + list = &p->next; + else { + p = commit_list_insert(item, list); + list = &p->next; /* skip newly added item */ + prio_queue_get(q); /* pop item */ + } + } + } + + static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp) + { + struct prio_queue queue = { compare_commits_by_commit_date }; + enum rewrite_result ret = rewrite_one_1(revs, pp, &queue); + merge_queue_into_list(&queue, &revs->commits); + clear_prio_queue(&queue); + return ret; + } + int rewrite_parents(struct rev_info *revs, struct commit *commit, rewrite_parent_fn_t rewrite_parent) {