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

diff --combined revision.c
index 60553d829d822b39c811065b1fbb10df21a3bceb,9265200b7a0c507da3bd008d3b7195560a44770f..d4aaf0ef257943029923f741b4ae383bb00d7f5f
--- 1/revision.c
--- 2/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)
  {