Merge branch 'rs/commit-list-sort-in-batch'
authorJunio C Hamano <gitster@pobox.com>
Mon, 23 Apr 2012 19:52:54 +0000 (12:52 -0700)
committerJunio C Hamano <gitster@pobox.com>
Mon, 23 Apr 2012 19:52:55 +0000 (12:52 -0700)
Setting up a revision traversal with many starting points was inefficient
as these were placed in a date-order priority queue one-by-one.

By René Scharfe (3) and Junio C Hamano (1)
* rs/commit-list-sort-in-batch:
mergesort: rename it to llist_mergesort()
revision: insert unsorted, then sort in prepare_revision_walk()
commit: use mergesort() in commit_list_sort_by_date()
add mergesort() for linked lists

1  2 
.gitignore
Makefile
commit.c
revision.c
diff --combined .gitignore
index 5a0782fe815a299a3a79ea15269aa6e0a7738a56,1787c8185d5a750afc4020278cd569eedd173875..83a5c9df1b2c21e21be9375ac01be94c8dcf941a
@@@ -92,7 -92,6 +92,7 @@@
  /git-name-rev
  /git-mv
  /git-notes
 +/git-p4
  /git-pack-redundant
  /git-pack-objects
  /git-pack-refs
  /test-index-version
  /test-line-buffer
  /test-match-trees
+ /test-mergesort
  /test-mktemp
 -/test-obj-pool
  /test-parse-options
  /test-path-utils
  /test-run-command
  /test-sha1
  /test-sigchain
 -/test-string-pool
  /test-subprocess
  /test-svn-fe
 -/test-treap
  /common-cmds.h
  *.tar.gz
  *.dsc
diff --combined Makefile
index 172e924a29521886dc4d365302ee12ed73c357d5,330a7d5ae99eee96472261b4eddd063dd533edaa..f1caae8a827e7381df8226b36485409dfca71642
+++ b/Makefile
@@@ -47,19 -47,12 +47,19 @@@ all:
  # A translated Git requires GNU libintl or another gettext implementation,
  # plus libintl-perl at runtime.
  #
 +# Define USE_GETTEXT_SCHEME and set it to 'fallthrough', if you don't trust
 +# the installed gettext translation of the shell scripts output.
 +#
  # Define HAVE_LIBCHARSET_H if you haven't set NO_GETTEXT and you can't
  # trust the langinfo.h's nl_langinfo(CODESET) function to return the
  # current character set. GNU and Solaris have a nl_langinfo(CODESET),
  # FreeBSD can use either, but MinGW and some others need to use
  # libcharset.h's locale_charset() instead.
  #
 +# Define CHARSET_LIB to you need to link with library other than -liconv to
 +# use locale_charset() function.  On some platforms this needs to set to
 +# -lcharset
 +#
  # Define LIBC_CONTAINS_LIBINTL if your gettext implementation doesn't
  # need -lintl when linking.
  #
@@@ -346,7 -339,7 +346,7 @@@ pathsep = 
  
  export prefix bindir sharedir sysconfdir gitwebdir localedir
  
 -CC = gcc
 +CC = cc
  AR = ar
  RM = rm -f
  DIFF = diff
@@@ -381,11 -374,6 +381,11 @@@ BUILTIN_OBJS 
  BUILT_INS =
  COMPAT_CFLAGS =
  COMPAT_OBJS =
 +XDIFF_H =
 +XDIFF_OBJS =
 +VCSSVN_H =
 +VCSSVN_OBJS =
 +VCSSVN_TEST_OBJS =
  EXTRA_CPPFLAGS =
  LIB_H =
  LIB_OBJS =
@@@ -440,7 -428,6 +440,7 @@@ SCRIPT_PERL += git-send-email.per
  SCRIPT_PERL += git-svn.perl
  
  SCRIPT_PYTHON += git-remote-testgit.py
 +SCRIPT_PYTHON += git-p4.py
  
  SCRIPTS = $(patsubst %.sh,%,$(SCRIPT_SH)) \
          $(patsubst %.perl,%,$(SCRIPT_PERL)) \
@@@ -465,9 -452,6 +465,9 @@@ PROGRAM_OBJS += http-backend.
  PROGRAM_OBJS += sh-i18n--envsubst.o
  PROGRAM_OBJS += credential-store.o
  
 +# Binary suffix, set to .exe for Windows builds
 +X =
 +
  PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
  
  TEST_PROGRAMS_NEED_X += test-chmtime
@@@ -481,14 -465,18 +481,15 @@@ TEST_PROGRAMS_NEED_X += test-genrando
  TEST_PROGRAMS_NEED_X += test-index-version
  TEST_PROGRAMS_NEED_X += test-line-buffer
  TEST_PROGRAMS_NEED_X += test-match-trees
+ TEST_PROGRAMS_NEED_X += test-mergesort
  TEST_PROGRAMS_NEED_X += test-mktemp
 -TEST_PROGRAMS_NEED_X += test-obj-pool
  TEST_PROGRAMS_NEED_X += test-parse-options
  TEST_PROGRAMS_NEED_X += test-path-utils
  TEST_PROGRAMS_NEED_X += test-run-command
  TEST_PROGRAMS_NEED_X += test-sha1
  TEST_PROGRAMS_NEED_X += test-sigchain
 -TEST_PROGRAMS_NEED_X += test-string-pool
  TEST_PROGRAMS_NEED_X += test-subprocess
  TEST_PROGRAMS_NEED_X += test-svn-fe
 -TEST_PROGRAMS_NEED_X += test-treap
  
  TEST_PROGRAMS = $(patsubst %,%$X,$(TEST_PROGRAMS_NEED_X))
  
@@@ -591,6 -579,7 +592,7 @@@ LIB_H += log-tree.
  LIB_H += mailmap.h
  LIB_H += merge-file.h
  LIB_H += merge-recursive.h
+ LIB_H += mergesort.h
  LIB_H += notes.h
  LIB_H += notes-cache.h
  LIB_H += notes-merge.h
@@@ -621,7 -610,6 +623,7 @@@ LIB_H += streaming.
  LIB_H += string-list.h
  LIB_H += submodule.h
  LIB_H += tag.h
 +LIB_H += thread-utils.h
  LIB_H += transport.h
  LIB_H += tree.h
  LIB_H += tree-walk.h
@@@ -695,6 -683,7 +697,7 @@@ LIB_OBJS += mailmap.
  LIB_OBJS += match-trees.o
  LIB_OBJS += merge-file.o
  LIB_OBJS += merge-recursive.o
+ LIB_OBJS += mergesort.o
  LIB_OBJS += name-hash.o
  LIB_OBJS += notes.o
  LIB_OBJS += notes-cache.o
@@@ -1535,7 -1524,6 +1538,7 @@@ ifdef GETTEXT_POISO
  endif
  ifdef NO_GETTEXT
        BASIC_CFLAGS += -DNO_GETTEXT
 +      USE_GETTEXT_SCHEME ?= fallthrough
  endif
  ifdef NO_STRCASESTR
        COMPAT_CFLAGS += -DNO_STRCASESTR
@@@ -1707,7 -1695,6 +1710,7 @@@ endi
  
  ifdef HAVE_LIBCHARSET_H
        BASIC_CFLAGS += -DHAVE_LIBCHARSET_H
 +      EXTLIBS += $(CHARSET_LIB)
  endif
  
  ifdef HAVE_DEV_TTY
@@@ -1784,26 -1771,6 +1787,26 @@@ ifdef ASCIIDOC
        export ASCIIDOC7
  endif
  
 +### profile feedback build
 +#
 +
 +# Can adjust this to be a global directory if you want to do extended
 +# data gathering
 +PROFILE_DIR := $(CURDIR)
 +
 +ifeq ("$(PROFILE)","GEN")
 +      CFLAGS += -fprofile-generate=$(PROFILE_DIR) -DNO_NORETURN=1
 +      EXTLIBS += -lgcov
 +      export CCACHE_DISABLE=t
 +      V=1
 +else
 +ifneq ("$(PROFILE)","")
 +      CFLAGS += -fprofile-use=$(PROFILE_DIR) -fprofile-correction -DNO_NORETURN=1
 +      export CCACHE_DISABLE=t
 +      V=1
 +endif
 +endif
 +
  # Shell quote (do not use $(call) to accommodate ancient setups);
  
  SHA1_HEADER_SQ = $(subst ','\'',$(SHA1_HEADER))
@@@ -1850,13 -1817,6 +1853,13 @@@ DEFAULT_PAGER_CQ_SQ = $(subst ','\'',$(
  BASIC_CFLAGS += -DDEFAULT_PAGER='$(DEFAULT_PAGER_CQ_SQ)'
  endif
  
 +ifdef SHELL_PATH
 +SHELL_PATH_CQ = "$(subst ",\",$(subst \,\\,$(SHELL_PATH)))"
 +SHELL_PATH_CQ_SQ = $(subst ','\'',$(SHELL_PATH_CQ))
 +
 +BASIC_CFLAGS += -DSHELL_PATH='$(SHELL_PATH_CQ_SQ)'
 +endif
 +
  ALL_CFLAGS += $(BASIC_CFLAGS)
  ALL_LDFLAGS += $(BASIC_LDFLAGS)
  
@@@ -1867,17 -1827,7 +1870,17 @@@ export DIFF TAR INSTALL DESTDIR SHELL_P
  
  SHELL = $(SHELL_PATH)
  
 -all:: shell_compatibility_test $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) $(OTHER_PROGRAMS) GIT-BUILD-OPTIONS
 +all:: shell_compatibility_test
 +
 +ifeq "$(PROFILE)" "BUILD"
 +ifeq ($(filter all,$(MAKECMDGOALS)),all)
 +all:: profile-clean
 +      $(MAKE) PROFILE=GEN all
 +      $(MAKE) PROFILE=GEN -j1 test
 +endif
 +endif
 +
 +all:: $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) $(OTHER_PROGRAMS) GIT-BUILD-OPTIONS
  ifneq (,$X)
        $(QUIET_BUILT_IN)$(foreach p,$(patsubst %$X,%,$(filter %$X,$(ALL_PROGRAMS) $(BUILT_INS) git$X)), test -d '$p' -o '$p' -ef '$p$X' || $(RM) '$p';)
  endif
@@@ -1940,7 -1890,6 +1943,7 @@@ sed -e '1s|#!.*/sh|#!$(SHELL_PATH_SQ)|
      -e 's/@@GIT_VERSION@@/$(GIT_VERSION)/g' \
      -e 's|@@LOCALEDIR@@|$(localedir_SQ)|g' \
      -e 's/@@NO_CURL@@/$(NO_CURL)/g' \
 +    -e 's/@@USE_GETTEXT_SCHEME@@/$(USE_GETTEXT_SCHEME)/g' \
      -e $(BROKEN_PATH_FIX) \
      $@.sh >$@+
  endef
@@@ -2042,24 -1991,12 +2045,24 @@@ GIT_OBJS := $(LIB_OBJS) $(BUILTIN_OBJS
  ifndef NO_CURL
        GIT_OBJS += http.o http-walker.o remote-curl.o
  endif
 -XDIFF_OBJS = xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \
 -      xdiff/xmerge.o xdiff/xpatience.o xdiff/xhistogram.o
 -VCSSVN_OBJS = vcs-svn/string_pool.o vcs-svn/line_buffer.o \
 -      vcs-svn/repo_tree.o vcs-svn/fast_export.o vcs-svn/svndump.o
 -VCSSVN_TEST_OBJS = test-obj-pool.o test-string-pool.o \
 -      test-line-buffer.o test-treap.o
 +
 +XDIFF_OBJS += xdiff/xdiffi.o
 +XDIFF_OBJS += xdiff/xprepare.o
 +XDIFF_OBJS += xdiff/xutils.o
 +XDIFF_OBJS += xdiff/xemit.o
 +XDIFF_OBJS += xdiff/xmerge.o
 +XDIFF_OBJS += xdiff/xpatience.o
 +XDIFF_OBJS += xdiff/xhistogram.o
 +
 +VCSSVN_OBJS += vcs-svn/line_buffer.o
 +VCSSVN_OBJS += vcs-svn/sliding_window.o
 +VCSSVN_OBJS += vcs-svn/repo_tree.o
 +VCSSVN_OBJS += vcs-svn/fast_export.o
 +VCSSVN_OBJS += vcs-svn/svndiff.o
 +VCSSVN_OBJS += vcs-svn/svndump.o
 +
 +VCSSVN_TEST_OBJS += test-line-buffer.o
 +
  OBJECTS := $(GIT_OBJS) $(XDIFF_OBJS) $(VCSSVN_OBJS)
  
  dep_files := $(foreach f,$(OBJECTS),$(dir $f).depend/$(notdir $f).d)
@@@ -2178,25 -2115,16 +2181,25 @@@ connect.o transport.o url.o http-backen
  http-fetch.o http-walker.o remote-curl.o transport.o walker.o: walker.h
  http.o http-walker.o http-push.o http-fetch.o remote-curl.o: http.h url.h
  
 -xdiff-interface.o $(XDIFF_OBJS): \
 -      xdiff/xinclude.h xdiff/xmacros.h xdiff/xdiff.h xdiff/xtypes.h \
 -      xdiff/xutils.h xdiff/xprepare.h xdiff/xdiffi.h xdiff/xemit.h
 +XDIFF_H += xdiff/xinclude.h
 +XDIFF_H += xdiff/xmacros.h
 +XDIFF_H += xdiff/xdiff.h
 +XDIFF_H += xdiff/xtypes.h
 +XDIFF_H += xdiff/xutils.h
 +XDIFF_H += xdiff/xprepare.h
 +XDIFF_H += xdiff/xdiffi.h
 +XDIFF_H += xdiff/xemit.h
  
 -$(VCSSVN_OBJS) $(VCSSVN_TEST_OBJS): $(LIB_H) \
 -      vcs-svn/obj_pool.h vcs-svn/trp.h vcs-svn/string_pool.h \
 -      vcs-svn/line_buffer.h vcs-svn/repo_tree.h vcs-svn/fast_export.h \
 -      vcs-svn/svndump.h
 +xdiff-interface.o $(XDIFF_OBJS): $(XDIFF_H)
  
 -test-svn-fe.o: vcs-svn/svndump.h
 +VCSSVN_H += vcs-svn/line_buffer.h
 +VCSSVN_H += vcs-svn/sliding_window.h
 +VCSSVN_H += vcs-svn/repo_tree.h
 +VCSSVN_H += vcs-svn/fast_export.h
 +VCSSVN_H += vcs-svn/svndiff.h
 +VCSSVN_H += vcs-svn/svndump.h
 +
 +$(VCSSVN_OBJS) $(VCSSVN_TEST_OBJS): $(LIB_H) $(VCSSVN_H)
  endif
  
  exec_cmd.sp exec_cmd.s exec_cmd.o: EXTRA_CPPFLAGS = \
@@@ -2266,8 -2194,6 +2269,8 @@@ $(XDIFF_LIB): $(XDIFF_OBJS
  $(VCSSVN_LIB): $(VCSSVN_OBJS)
        $(QUIET_AR)$(RM) $@ && $(AR) rcs $@ $(VCSSVN_OBJS)
  
 +export DEFAULT_EDITOR DEFAULT_PAGER
 +
  doc:
        $(MAKE) -C Documentation all
  
@@@ -2341,7 -2267,7 +2344,7 @@@ cscope
  ### Detect prefix changes
  TRACK_CFLAGS = $(CC):$(subst ','\'',$(ALL_CFLAGS)):\
               $(bindir_SQ):$(gitexecdir_SQ):$(template_dir_SQ):$(prefix_SQ):\
 -             $(localedir_SQ)
 +             $(localedir_SQ):$(USE_GETTEXT_SCHEME)
  
  GIT-CFLAGS: FORCE
        @FLAGS='$(TRACK_CFLAGS)'; \
@@@ -2372,10 -2298,6 +2375,10 @@@ GIT-BUILD-OPTIONS: FORC
        @echo USE_LIBPCRE=\''$(subst ','\'',$(subst ','\'',$(USE_LIBPCRE)))'\' >>$@
        @echo NO_PERL=\''$(subst ','\'',$(subst ','\'',$(NO_PERL)))'\' >>$@
        @echo NO_PYTHON=\''$(subst ','\'',$(subst ','\'',$(NO_PYTHON)))'\' >>$@
 +      @echo NO_UNIX_SOCKETS=\''$(subst ','\'',$(subst ','\'',$(NO_UNIX_SOCKETS)))'\' >>$@
 +ifdef GIT_TEST_OPTS
 +      @echo GIT_TEST_OPTS=\''$(subst ','\'',$(subst ','\'',$(GIT_TEST_OPTS)))'\' >>$@
 +endif
  ifdef GIT_TEST_CMP
        @echo GIT_TEST_CMP=\''$(subst ','\'',$(subst ','\'',$(GIT_TEST_CMP)))'\' >>$@
  endif
@@@ -2384,18 -2306,7 +2387,18 @@@ ifdef GIT_TEST_CMP_USE_COPIED_CONTEX
  endif
        @echo NO_GETTEXT=\''$(subst ','\'',$(subst ','\'',$(NO_GETTEXT)))'\' >>$@
        @echo GETTEXT_POISON=\''$(subst ','\'',$(subst ','\'',$(GETTEXT_POISON)))'\' >>$@
 -      @echo NO_UNIX_SOCKETS=\''$(subst ','\'',$(subst ','\'',$(NO_UNIX_SOCKETS)))'\' >>$@
 +ifdef GIT_PERF_REPEAT_COUNT
 +      @echo GIT_PERF_REPEAT_COUNT=\''$(subst ','\'',$(subst ','\'',$(GIT_PERF_REPEAT_COUNT)))'\' >>$@
 +endif
 +ifdef GIT_PERF_REPO
 +      @echo GIT_PERF_REPO=\''$(subst ','\'',$(subst ','\'',$(GIT_PERF_REPO)))'\' >>$@
 +endif
 +ifdef GIT_PERF_LARGE_REPO
 +      @echo GIT_PERF_LARGE_REPO=\''$(subst ','\'',$(subst ','\'',$(GIT_PERF_LARGE_REPO)))'\' >>$@
 +endif
 +ifdef GIT_PERF_MAKE_OPTS
 +      @echo GIT_PERF_MAKE_OPTS=\''$(subst ','\'',$(subst ','\'',$(GIT_PERF_MAKE_OPTS)))'\' >>$@
 +endif
  
  ### Detect Tck/Tk interpreter path changes
  ifndef NO_TCLTK
@@@ -2431,11 -2342,6 +2434,11 @@@ export NO_SVN_TEST
  test: all
        $(MAKE) -C t/ all
  
 +perf: all
 +      $(MAKE) -C t/perf/ all
 +
 +.PHONY: test perf
 +
  test-ctype$X: ctype.o
  
  test-date$X: date.o ctype.o
@@@ -2446,6 -2352,8 +2449,6 @@@ test-line-buffer$X: vcs-svn/lib.
  
  test-parse-options$X: parse-options.o parse-options-cb.o
  
 -test-string-pool$X: vcs-svn/lib.a
 -
  test-svn-fe$X: vcs-svn/lib.a
  
  .PRECIOUS: $(TEST_OBJS)
@@@ -2645,12 -2553,9 +2648,12 @@@ dist-doc
  
  distclean: clean
        $(RM) configure
 -      $(RM) po/git.pot
  
 -clean:
 +profile-clean:
 +      $(RM) $(addsuffix *.gcda,$(addprefix $(PROFILE_DIR)/, $(object_dirs)))
 +      $(RM) $(addsuffix *.gcno,$(addprefix $(PROFILE_DIR)/, $(object_dirs)))
 +
 +clean: profile-clean
        $(RM) *.o block-sha1/*.o ppc/*.o compat/*.o compat/*/*.o xdiff/*.o vcs-svn/*.o \
                builtin/*.o $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
        $(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
@@@ -2680,7 -2585,7 +2683,7 @@@ ifndef NO_TCLT
  endif
        $(RM) GIT-VERSION-FILE GIT-CFLAGS GIT-LDFLAGS GIT-GUI-VARS GIT-BUILD-OPTIONS
  
 -.PHONY: all install clean strip
 +.PHONY: all install profile-clean clean strip
  .PHONY: shell_compatibility_test please_set_SHELL_PATH_to_a_more_modern_shell
  .PHONY: FORCE cscope
  
@@@ -2790,3 -2695,18 +2793,3 @@@ cover_db: coverage-repor
  cover_db_html: cover_db
        cover -report html -outputdir cover_db_html cover_db
  
 -### profile feedback build
 -#
 -.PHONY: profile-all profile-clean
 -
 -PROFILE_GEN_CFLAGS := $(CFLAGS) -fprofile-generate -DNO_NORETURN=1
 -PROFILE_USE_CFLAGS := $(CFLAGS) -fprofile-use -fprofile-correction -DNO_NORETURN=1
 -
 -profile-clean:
 -      $(RM) $(addsuffix *.gcda,$(object_dirs))
 -      $(RM) $(addsuffix *.gcno,$(object_dirs))
 -
 -profile-all: profile-clean
 -      $(MAKE) CFLAGS="$(PROFILE_GEN_CFLAGS)" all
 -      $(MAKE) CFLAGS="$(PROFILE_GEN_CFLAGS)" -j1 test
 -      $(MAKE) CFLAGS="$(PROFILE_USE_CFLAGS)" all
diff --combined commit.c
index 4b39c19123c7fa8584a67d5fd91e11f89e5816e4,84304c00ffeee223224e4686351935255d4c9a75..b80a45281ccf4234b685954651db4249201e60db
+++ b/commit.c
@@@ -7,6 -7,7 +7,7 @@@
  #include "revision.h"
  #include "notes.h"
  #include "gpg-interface.h"
+ #include "mergesort.h"
  
  int save_commit_buffer = 1;
  
@@@ -360,6 -361,21 +361,21 @@@ struct commit_list *commit_list_insert(
        return new_list;
  }
  
+ void commit_list_reverse(struct commit_list **list_p)
+ {
+       struct commit_list *prev = NULL, *curr = *list_p, *next;
+       if (!list_p)
+               return;
+       while (curr) {
+               next = curr->next;
+               curr->next = prev;
+               prev = curr;
+               curr = next;
+       }
+       *list_p = prev;
+ }
  unsigned commit_list_count(const struct commit_list *l)
  {
        unsigned c = 0;
@@@ -390,15 -406,31 +406,31 @@@ struct commit_list * commit_list_insert
        return commit_list_insert(item, pp);
  }
  
+ static int commit_list_compare_by_date(const void *a, const void *b)
+ {
+       unsigned long a_date = ((const struct commit_list *)a)->item->date;
+       unsigned long b_date = ((const struct commit_list *)b)->item->date;
+       if (a_date < b_date)
+               return 1;
+       if (a_date > b_date)
+               return -1;
+       return 0;
+ }
+ static void *commit_list_get_next(const void *a)
+ {
+       return ((const struct commit_list *)a)->next;
+ }
+ static void commit_list_set_next(void *a, void *next)
+ {
+       ((struct commit_list *)a)->next = next;
+ }
  
  void commit_list_sort_by_date(struct commit_list **list)
  {
-       struct commit_list *ret = NULL;
-       while (*list) {
-               commit_list_insert_by_date((*list)->item, &ret);
-               *list = (*list)->next;
-       }
-       *list = ret;
+       *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
+                               commit_list_compare_by_date);
  }
  
  struct commit *pop_most_recent_commit(struct commit_list **list,
        return ret;
  }
  
 -void clear_commit_marks(struct commit *commit, unsigned int mark)
 +static void clear_commit_marks_1(struct commit_list **plist,
 +                               struct commit *commit, unsigned int mark)
  {
        while (commit) {
                struct commit_list *parents;
                        return;
  
                while ((parents = parents->next))
 -                      clear_commit_marks(parents->item, mark);
 +                      commit_list_insert(parents->item, plist);
  
                commit = commit->parents->item;
        }
  }
  
 +void clear_commit_marks(struct commit *commit, unsigned int mark)
 +{
 +      struct commit_list *list = NULL;
 +      commit_list_insert(commit, &list);
 +      while (list)
 +              clear_commit_marks_1(&list, pop_commit(&list), mark);
 +}
 +
  void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
  {
        struct object *object;
diff --combined revision.c
index b3554ed11b5c1a987c1d22b7851c91641bbf7f56,a75a1d7201ea6e4ea26fa95665a24b2716bb07d0..92095f5fcbb4454b3d605d2cdd6c9a1567498562
@@@ -139,32 -139,11 +139,32 @@@ void mark_tree_uninteresting(struct tre
  
  void mark_parents_uninteresting(struct commit *commit)
  {
 -      struct commit_list *parents = commit->parents;
 +      struct commit_list *parents = NULL, *l;
 +
 +      for (l = commit->parents; l; l = l->next)
 +              commit_list_insert(l->item, &parents);
  
        while (parents) {
                struct commit *commit = parents->item;
 -              if (!(commit->object.flags & UNINTERESTING)) {
 +              l = parents;
 +              parents = parents->next;
 +              free(l);
 +
 +              while (commit) {
 +                      /*
 +                       * A missing commit is ok iff its parent is marked
 +                       * uninteresting.
 +                       *
 +                       * We just mark such a thing parsed, so that when
 +                       * it is popped next time around, we won't be trying
 +                       * to parse it and get an error.
 +                       */
 +                      if (!has_sha1_file(commit->object.sha1))
 +                              commit->object.parsed = 1;
 +
 +                      if (commit->object.flags & UNINTERESTING)
 +                              break;
 +
                        commit->object.flags |= UNINTERESTING;
  
                        /*
                         * wasn't uninteresting), in which case we need
                         * to mark its parents recursively too..
                         */
 -                      if (commit->parents)
 -                              mark_parents_uninteresting(commit);
 -              }
 +                      if (!commit->parents)
 +                              break;
  
 -              /*
 -               * A missing commit is ok iff its parent is marked
 -               * uninteresting.
 -               *
 -               * We just mark such a thing parsed, so that when
 -               * it is popped next time around, we won't be trying
 -               * to parse it and get an error.
 -               */
 -              if (!has_sha1_file(commit->object.sha1))
 -                      commit->object.parsed = 1;
 -              parents = parents->next;
 +                      for (l = commit->parents->next; l; l = l->next)
 +                              commit_list_insert(l->item, &parents);
 +                      commit = commit->parents->item;
 +              }
        }
  }
  
@@@ -429,7 -416,7 +429,7 @@@ static int rev_same_tree_as_empty(struc
  static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
  {
        struct commit_list **pp, *parent;
 -      int tree_changed = 0, tree_same = 0;
 +      int tree_changed = 0, tree_same = 0, nth_parent = 0;
  
        /*
         * If we don't do pruning, everything is interesting
        while ((parent = *pp) != NULL) {
                struct commit *p = parent->item;
  
 +              /*
 +               * Do not compare with later parents when we care only about
 +               * the first parent chain, in order to avoid derailing the
 +               * traversal to follow a side branch that brought everything
 +               * in the path we are limited to by the pathspec.
 +               */
 +              if (revs->first_parent_only && nth_parent++)
 +                      break;
                if (parse_commit(p) < 0)
                        die("cannot simplify commit %s (because of %s)",
                            sha1_to_hex(commit->object.sha1),
@@@ -1582,7 -1561,6 +1582,7 @@@ static int handle_revision_opt(struct r
                revs->grep_filter.regflags |= REG_EXTENDED;
        } else if (!strcmp(arg, "--regexp-ignore-case") || !strcmp(arg, "-i")) {
                revs->grep_filter.regflags |= REG_ICASE;
 +              DIFF_OPT_SET(&revs->diffopt, PICKAXE_IGNORE_CASE);
        } else if (!strcmp(arg, "--fixed-strings") || !strcmp(arg, "-F")) {
                revs->grep_filter.fixed = 1;
        } else if (!strcmp(arg, "--all-match")) {
@@@ -2076,11 -2054,13 +2076,13 @@@ int prepare_revision_walk(struct rev_in
                if (commit) {
                        if (!(commit->object.flags & SEEN)) {
                                commit->object.flags |= SEEN;
-                               commit_list_insert_by_date(commit, &revs->commits);
+                               commit_list_insert(commit, &revs->commits);
                        }
                }
                e++;
        }
+       commit_list_reverse(&revs->commits);
+       commit_list_sort_by_date(&revs->commits);
        if (!revs->leak_pending)
                free(list);
  
@@@ -2150,6 -2130,7 +2152,6 @@@ static int commit_match(struct commit *
        if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list)
                return 1;
        return grep_buffer(&opt->grep_filter,
 -                         NULL, /* we say nothing, not even filename */
                           commit->buffer, strlen(commit->buffer));
  }