{"thread":{"id":"34028","subject":"[PATCH/RFC] add --authorship-order flag to git log / rev-list","startedAt":"2013-06-04T18:08:17Z","lastAt":"2013-06-20T20:16:50Z","messageCount":51,"participants":["elliottcable","Junio C Hamano","Jeff King","Elliott Cable","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"219390","messageId":"1370369299-20744-1-git-send-email-me@ell.io","threadId":"34028","inReplyTo":null,"subject":"[PATCH/RFC] add --authorship-order flag to git log / rev-list","fromName":"elliottcable","fromEmail":"me@ell.io","sentAt":"2013-06-04T18:08:17Z","receivedAt":"2013-06-04T18:08:17Z","isPatch":true,"sender":{"key":"me@ell.io","avatar":"https://gravatar.com/avatar/0d35bb7d7c29b6bbcaafdf13ec70745573d31cb222130cc754a064e707c08d63?d=mp&s=160"},"body":"This is my first time submitting a patch to this list, so please, let me know if\nI'm doing any of this the wrong way! I've striven to follow\n`Documentation/SubmittingPatches`. I hope I've succeeded. For that matter, it's\nmy first time diving into git's sources, so I obviously would love some\ncommentary on the patch itself, as well. ;)\n\nI've tried herein to add an `--authorship-order` flag to complement git-log's\n`--topo-order` and `--date-order` flags; it should operate the same as\n`--date-order`, but using the `AUTHOR_DATE` instead of the `COMMITTER_DATE`.\n\nI've sent an e-mail to this list, previously, on this subject; I'd make this\npatchset a reply to that, except I have no idea what the in-reply-to should be:\nhttp://www.spinics.net/lists/git/msg208542.html\n\nThe original work is all on GitHub:\nhttps://github.com/git/git/pull/40\nhttps://github.com/ELLIOTTCABLE/git/compare/master...author-order+\n\nelliottcable (1):\n rev-list: add --authorship-order alternative ordering\n\n builtin/log.c | 2 +-\n builtin/rev-list.c | 1 +\n builtin/rev-parse.c | 1 +\n builtin/show-branch.c | 12 ++++-\n commit.c | 83 ++++++++++++++++++++++++++++++----\n commit.h | 3 +-\n contrib/completion/git-completion.bash | 4 +-\n po/de.po | 4 +-\n po/git.pot | 2 +-\n po/sv.po | 4 +-\n po/vi.po | 4 +-\n po/zh_CN.po | 4 +-\n revision.c | 11 ++++-\n revision.h | 1 +\n 14 files changed, 110 insertions(+), 26 deletions(-)\n\n-- \n1.8.1.3\n"},{"id":"219391","messageId":"1370369299-20744-2-git-send-email-me@ell.io","threadId":"34028","inReplyTo":"1370369299-20744-1-git-send-email-me@ell.io","subject":"[PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"elliottcable","fromEmail":"me@ell.io","sentAt":"2013-06-04T18:08:18Z","receivedAt":"2013-06-04T18:08:18Z","isPatch":true,"sender":{"key":"me@ell.io","avatar":"https://gravatar.com/avatar/0d35bb7d7c29b6bbcaafdf13ec70745573d31cb222130cc754a064e707c08d63?d=mp&s=160"},"body":"--date-order is an excellent alternative to --topo-order if you want a feel for\nthe *actual history*, chronologically, of your project. I use it often, with\n--graph as well; it's a great way to get an overview of a project's recent\ndevelopment history.\n\nHowever, in a project that rebases various in-development topic-branches often,\nit gets hard to demonstrate a *chronological history* of changes to the\ncodebase, as this always “resets” the COMMITTER_DATE (which --date-order uses)\nto the time the rebase happened; which often means ‘last time all of the\ntopic-branches were rebased on the latest fixes in master.’\n\nThus, I've added an --authorship-order version of --date-order, which relies\nupon the AUTHOR_DATE instead of the COMMITTER_DATE; this means that old commits\nwill continue to show up chronologically in-order despite rebasing.\n---\n builtin/log.c | 2 +-\n builtin/rev-list.c | 1 +\n builtin/rev-parse.c | 1 +\n builtin/show-branch.c | 12 ++++-\n commit.c | 83 ++++++++++++++++++++++++++++++----\n commit.h | 3 +-\n contrib/completion/git-completion.bash | 4 +-\n po/de.po | 4 +-\n po/git.pot | 2 +-\n po/sv.po | 4 +-\n po/vi.po | 4 +-\n po/zh_CN.po | 4 +-\n revision.c | 11 ++++-\n revision.h | 1 +\n 14 files changed, 110 insertions(+), 26 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 9e21232..54d4d7f 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -237,7 +237,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n \tint i = revs->early_output;\n \tint show_header = 1;\n \n-\tsort_in_topological_order(&list, revs->lifo);\n+\tsort_in_topological_order(&list, revs->lifo, revs->use_author);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 67701be..cfa5d1f 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -30,6 +30,7 @@ static const char rev_list_usage[] =\n \" ordering output:\\n\"\n \" --topo-order\\n\"\n \" --date-order\\n\"\n+\" --authorship-order\\n\"\n \" --reverse\\n\"\n \" formatting output:\\n\"\n \" --parents\\n\"\ndiff --git a/builtin/rev-parse.c b/builtin/rev-parse.c\nindex f267a1d..d08aebd 100644\n--- a/builtin/rev-parse.c\n+++ b/builtin/rev-parse.c\n@@ -65,6 +65,7 @@ static int is_rev_argument(const char *arg)\n \t\t\"--tags\",\n \t\t\"--topo-order\",\n \t\t\"--date-order\",\n+\t\t\"--authorship-order\",\n \t\t\"--unpacked\",\n \t\tNULL\n \t};\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 90fc6b1..ac06ac3 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -6,7 +6,7 @@\n #include \"parse-options.h\"\n \n static const char* show_branch_usage[] = {\n- N_(\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--current] [--color[=] | --no-color] [--sparse] [--more= | --list | --independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | )...]\"),\n+ N_(\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--current] [--color[=] | --no-color] [--sparse] [--more= | --list | --independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | )...]\"),\n N_(\"git show-branch (-g|--reflog)[=[,]] [--list] []\"),\n NULL\n };\n@@ -631,6 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \tint all_heads = 0, all_remotes = 0;\n \tint all_mask, all_revs;\n \tint lifo = 1;\n+\tint use_author = 0;\n \tchar head[128];\n \tconst char *head_p;\n \tint head_len;\n@@ -667,6 +668,8 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\t\t N_(\"show refs unreachable from any other ref\")),\n \t\tOPT_BOOLEAN(0, \"topo-order\", &lifo,\n \t\t\t N_(\"show commits in topological order\")),\n+\t\tOPT_BOOLEAN(0, \"authorship-order\", &use_author,\n+\t\t\t N_(\"like --date-order, but with the *author* date\")),\n \t\tOPT_BOOLEAN(0, \"topics\", &topics,\n \t\t\t N_(\"show only commits not on the first branch\")),\n \t\tOPT_SET_INT(0, \"sparse\", &dense,\n@@ -694,6 +697,11 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\t\t show_branch_usage, PARSE_OPT_STOP_AT_NON_OPTION);\n \tif (all_heads)\n \t\tall_remotes = 1;\n+\t/* I'm having trouble figuring out exactly what `lifo` stores. Why do both 'date-order' and\n+\t * 'topo-order' set the same variable!? Aren't they mutually exclusive? Since *both* set it, for\n+\t * the moment, I'm going to set it for '--authorship-order'; but that seems counterintuitive. */\n+\tif (use_author)\n+\t\tlifo = 1;\n \n \tif (extra || reflog) {\n \t\t/* \"listing\" mode is incompatible with\n@@ -900,7 +908,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\texit(0);\n \n \t/* Sort topologically */\n-\tsort_in_topological_order(&seen, lifo);\n+\tsort_in_topological_order(&seen, lifo, use_author);\n \n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\ndiff --git a/commit.c b/commit.c\nindex 888e02a..b8a0f60 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -78,7 +78,34 @@ struct commit *lookup_commit_reference_by_name(const char *name)\n \treturn commit;\n }\n \n-static unsigned long parse_commit_date(const char *buf, const char *tail)\n+static unsigned long parse_commit_author_date(const char *buf, const char *tail)\n+{\n+\tconst char *dateptr;\n+\n+\tif (buf + 6 >= tail)\n+\t\treturn 0;\n+\tif (memcmp(buf, \"author\", 6))\n+\t\treturn 0;\n+\twhile (buf < tail && *buf++ != '>')\n+\t\t/* nada */;\n+\tif (buf >= tail)\n+\t\treturn 0;\n+\tdateptr = buf;\n+\twhile (buf < tail && *buf++ != '\\n')\n+\t\t/* nada */;\n+\tif (buf + 9 >= tail)\n+\t\treturn 0;\n+\tif (memcmp(buf, \"committer\", 9))\n+\t\treturn 0;\n+\twhile (buf < tail && *buf++ != '\\n')\n+\t\t/* nada */;\n+\tif (buf >= tail)\n+\t\treturn 0;\n+\t/* dateptr < buf && buf[-1] == '\\n', so strtoul will stop at buf-1 */\n+\treturn strtoul(dateptr, NULL, 10);\n+}\n+\n+static unsigned long parse_commit_committer_date(const char *buf, const char *tail)\n {\n \tconst char *dateptr;\n \n@@ -301,7 +328,8 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n \t\t}\n \t}\n-\titem->date = parse_commit_date(bufptr, tail);\n+\titem->date = parse_commit_committer_date(bufptr, tail);\n+\titem->author_date = parse_commit_author_date(bufptr, tail);\n \n \treturn 0;\n }\n@@ -380,6 +408,19 @@ void free_commit_list(struct commit_list *list)\n \t}\n }\n \n+struct commit_list * commit_list_insert_by_author_date(struct commit *item, struct commit_list **list)\n+{\n+\tstruct commit_list **pp = list;\n+\tstruct commit_list *p;\n+\twhile ((p = *pp) != NULL) {\n+\t\tif (p->item->author_date < item->author_date) {\n+\t\t\tbreak;\n+\t\t}\n+\t\tpp = &p->next;\n+\t}\n+\treturn commit_list_insert(item, pp);\n+}\n+\n struct commit_list * commit_list_insert_by_date(struct commit *item, struct commit_list **list)\n {\n \tstruct commit_list **pp = list;\n@@ -393,6 +434,17 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm\n \treturn commit_list_insert(item, pp);\n }\n \n+static int commit_list_compare_by_author_date(const void *a, const void *b)\n+{\n+\tunsigned long a_date = ((const struct commit_list *)a)->item->author_date;\n+\tunsigned long b_date = ((const struct commit_list *)b)->item->author_date;\n+\tif (a_date < b_date)\n+\t\treturn 1;\n+\tif (a_date > b_date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n static int commit_list_compare_by_date(const void *a, const void *b)\n {\n \tunsigned long a_date = ((const struct commit_list *)a)->item->date;\n@@ -414,6 +466,12 @@ static void commit_list_set_next(void *a, void *next)\n \t((struct commit_list *)a)->next = next;\n }\n \n+void commit_list_sort_by_author_date(struct commit_list **list)\n+{\n+\t*list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,\n+\t\t\t\tcommit_list_compare_by_author_date);\n+}\n+\n void commit_list_sort_by_date(struct commit_list **list)\n {\n \t*list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,\n@@ -509,7 +567,7 @@ struct commit *pop_commit(struct commit_list **stack)\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo)\n+void sort_in_topological_order(struct commit_list ** list, int lifo, int use_author)\n {\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n@@ -554,8 +612,12 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t}\n \n \t/* process the list in topological order */\n-\tif (!lifo)\n-\t\tcommit_list_sort_by_date(&work);\n+\tif (!lifo) {\n+\t\tif (use_author)\n+\t\t\tcommit_list_sort_by_author_date(&work);\n+\t\telse\n+\t\t\tcommit_list_sort_by_date(&work);\n+\t}\n \n \tpptr = list;\n \t*list = NULL;\n@@ -580,10 +642,13 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n \t\t\tif (--parent->indegree == 1) {\n-\t\t\t\tif (!lifo)\n-\t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\telse\n-\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\tif (!lifo) {\n+\t\t\t\t\tif (use_author)\n+\t\t\t\t\t\tcommit_list_insert_by_author_date(parent, &work);\n+\t\t\t\t\telse\n+\t\t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n+\t\t\t\t} else {\n+\t\t\t\t\tcommit_list_insert(parent, &work); }\n \t\t\t}\n \t\t}\n \t\t/*\ndiff --git a/commit.h b/commit.h\nindex 67bd509..de07525 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -17,6 +17,7 @@ struct commit {\n \tvoid *util;\n \tunsigned int indegree;\n \tunsigned long date;\n+\tunsigned long author_date;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n \tchar *buffer;\n@@ -150,7 +151,7 @@ void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n * in addition, when lifo == 0, commits on parallel tracks are\n * sorted in the dates order.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo);\n+void sort_in_topological_order(struct commit_list ** list, int lifo, int use_author);\n \n struct commit_graft {\n \tunsigned char sha1[20];\ndiff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\nindex 91234d4..f051e53 100644\n--- a/contrib/completion/git-completion.bash\n+++ b/contrib/completion/git-completion.bash\n@@ -1445,7 +1445,7 @@ _git_log ()\n \t\t\t$__git_log_common_options\n \t\t\t$__git_log_shortlog_options\n \t\t\t$__git_log_gitk_options\n-\t\t\t--root --topo-order --date-order --reverse\n+\t\t\t--root --topo-order --date-order --authorship-order --reverse\n \t\t\t--follow --full-diff\n \t\t\t--abbrev-commit --abbrev=\n \t\t\t--relative-date --date=\n@@ -2291,7 +2291,7 @@ _git_show_branch ()\n \tcase \"$cur\" in\n \t--*)\n \t\t__gitcomp \"\n-\t\t\t--all --remotes --topo-order --current --more=\n+\t\t\t--all --remotes --topo-order --authorship-order --current --more=\n \t\t\t--list --independent --merge-base --no-name\n \t\t\t--color --no-color\n \t\t\t--sha1-name --sparse --topics --reflog\ndiff --git a/po/de.po b/po/de.po\nindex 4901488..0dc184f 100644\n--- a/po/de.po\n+++ b/po/de.po\n@@ -8716,12 +8716,12 @@ msgstr \"Ausgabe mit Zeilenumbrüchen\"\n \n #: builtin/show-branch.c:9\n msgid \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\n msgstr \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] \"\n \"[( | )...]\"\ndiff --git a/po/git.pot b/po/git.pot\nindex 4a9d4ef..325348d 100644\n--- a/po/git.pot\n+++ b/po/git.pot\n@@ -8123,7 +8123,7 @@ msgstr \"\"\n \n #: builtin/show-branch.c:9\n msgid \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\ndiff --git a/po/sv.po b/po/sv.po\nindex a5c88c9..5091224 100644\n--- a/po/sv.po\n+++ b/po/sv.po\n@@ -8478,12 +8478,12 @@ msgstr \"Radbryt utdata\"\n \n #: builtin/show-branch.c:9\n msgid \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\n msgstr \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\ndiff --git a/po/vi.po b/po/vi.po\nindex c6af8d5..ec41ff8 100644\n--- a/po/vi.po\n+++ b/po/vi.po\n@@ -8622,12 +8622,12 @@ msgstr \"Ngắt dòng khi quá dài\"\n \n #: builtin/show-branch.c:9\n msgid \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\n msgstr \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\ndiff --git a/po/zh_CN.po b/po/zh_CN.po\nindex ba757d9..a666aed 100644\n--- a/po/zh_CN.po\n+++ b/po/zh_CN.po\n@@ -8446,12 +8446,12 @@ msgstr \"折行输出\"\n \n #: builtin/show-branch.c:9\n msgid \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\n msgstr \"\"\n-\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--\"\n+\"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--\"\n \"current] [--color[=] | --no-color] [--sparse] [--more= | --list | --\"\n \"independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | \"\n \")...]\"\ndiff --git a/revision.c b/revision.c\nindex 518cd08..2d077ce 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1053,6 +1053,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \trevs->pruning.add_remove = file_add_remove;\n \trevs->pruning.change = file_change;\n \trevs->lifo = 1;\n+\trevs->use_author = 0;\n \trevs->dense = 1;\n \trevs->prefix = prefix;\n \trevs->max_age = -1;\n@@ -1394,6 +1395,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n \t\trevs->lifo = 1;\n \t\trevs->topo_order = 1;\n+\t\trevs->use_author = 0;\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n \t\trevs->topo_order = 1;\n@@ -1412,6 +1414,11 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->lifo = 0;\n \t\trevs->topo_order = 1;\n+\t\trevs->use_author = 0;\n+\t} else if (!strcmp(arg, \"--authorship-order\")) {\n+\t\trevs->lifo = 0;\n+\t\trevs->topo_order = 1;\n+\t\trevs->use_author = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n \t\tswitch (arg[14]) {\n@@ -2191,7 +2198,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n-\t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\t\tsort_in_topological_order(&revs->commits, revs->lifo, revs->use_author);\n \tif (revs->line_level_traverse)\n \t\tline_log_filter(revs);\n \tif (revs->simplify_merges)\n@@ -2503,7 +2510,7 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \t * If revs->topo_order is set, sort the boundary commits\n \t * in topological order\n \t */\n-\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tsort_in_topological_order(&revs->commits, revs->lifo, revs->use_author);\n }\n \n static struct commit *get_revision_internal(struct rev_info *revs)\ndiff --git a/revision.h b/revision.h\nindex a313a13..09effab 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -73,6 +73,7 @@ struct rev_info {\n \t\t\tsimplify_history:1,\n \t\t\tlifo:1,\n \t\t\ttopo_order:1,\n+\t\t\tuse_author:1,\n \t\t\tsimplify_merges:1,\n \t\t\tsimplify_by_decoration:1,\n \t\t\ttag_objects:1,\n-- \n1.8.1.3\n"},{"id":"219395","messageId":"7vmwr57lo1.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"1370369299-20744-1-git-send-email-me@ell.io","subject":"Re: [PATCH/RFC] add --authorship-order flag to git log / rev-list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-04T18:53:02Z","receivedAt":"2013-06-04T18:53:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"elliottcable writes:\n\n> This is my first time submitting a patch to this list, so please, let me know if\n> I'm doing any of this the wrong way! I've striven to follow\n> `Documentation/SubmittingPatches`. I hope I've succeeded. For that matter, it's\n> my first time diving into git's sources, so I obviously would love some\n> commentary on the patch itself, as well. ;)\n>\n> I've tried herein to add an `--authorship-order` flag to complement git-log's\n> `--topo-order` and `--date-order` flags; it should operate the same as\n> `--date-order`, but using the `AUTHOR_DATE` instead of the `COMMITTER_DATE`.\n\nAfter reading the subject alone, my reaction was \"is this sorting\ncommits by the name of the author\"?\n\nThat is one of the expected natural reactions when people hear about\nthis option, which is not what you want.\n\nPerhaps naming it --authordate-order (or enhance the command line\nparsing to allow --date-order=author|committer) would give us a\nbetter UI.\n\n(the above comment is before reading any of the code in the patch).\n"},{"id":"219399","messageId":"7vip1t7koi.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"1370369299-20744-2-git-send-email-me@ell.io","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-04T19:14:21Z","receivedAt":"2013-06-04T19:14:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"elliottcable writes:\n\n> --date-order is an excellent alternative to --topo-order if you want a feel for\n> the *actual history*, chronologically, of your project. I use it often, with\n> --graph as well; it's a great way to get an overview of a project's recent\n> development history.\n>\n> However, in a project that rebases various in-development topic-branches often,\n> it gets hard to demonstrate a *chronological history* of changes to the\n> codebase, as this always “resets” the COMMITTER_DATE (which --date-order uses)\n> to the time the rebase happened; which often means ‘last time all of the\n> topic-branches were rebased on the latest fixes in master.’\n>\n> Thus, I've added an --authorship-order version of --date-order, which relies\n> upon the AUTHOR_DATE instead of the COMMITTER_DATE; this means that old commits\n> will continue to show up chronologically in-order despite rebasing.\n> ---\n\nMissing sign-off. Please see Documentation/SubmittingPatches.\n\n> builtin/log.c | 2 +-\n> builtin/rev-list.c | 1 +\n> builtin/rev-parse.c | 1 +\n> builtin/show-branch.c | 12 ++++-\n> commit.c | 83 ++++++++++++++++++++++++++++++----\n> commit.h | 3 +-\n> contrib/completion/git-completion.bash | 4 +-\n> po/de.po | 4 +-\n> po/git.pot | 2 +-\n> po/sv.po | 4 +-\n> po/vi.po | 4 +-\n> po/zh_CN.po | 4 +-\n\nPlease drop all the changes to po/ area; it is managed by the i18n\ncoordinator and generated by an automated tool that extracts these\nstrings from the code.\n\nPeople who code should not (and do not have to) touch these files.\n\n> revision.c | 11 ++++-\n> revision.h | 1 +\n> 14 files changed, 110 insertions(+), 26 deletions(-)\n>\n> diff --git a/builtin/log.c b/builtin/log.c\n> index 9e21232..54d4d7f 100644\n> --- a/builtin/log.c\n> +++ b/builtin/log.c\n> @@ -237,7 +237,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n> \tint i = revs->early_output;\n> \tint show_header = 1;\n> \n> -\tsort_in_topological_order(&list, revs->lifo);\n> +\tsort_in_topological_order(&list, revs->lifo, revs->use_author);\n\nThe name \"use-author\" is a clear sign that the person who added this\ncode were too narrowly focused to think \"author\" automatically would\nmean \"author date\" ;-).\n\nIt probably makes sense to revamp sort_in_topological_order(), so\nthat its second parameter is not a boolean 'lifo' that tells too\nmuch about its implementation without telling what it actually\nmeans. Instead, we can make it an enum sort_order, that tells it to\nemit the commits in committer-date order, author-date order, or\ngraph-traversal order.\n\nAnd update revs->lifo to use that same enum, without adding\nuse_author_date bit to rev_info.\n\n> @@ -694,6 +697,11 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n> \t\t\t show_branch_usage, PARSE_OPT_STOP_AT_NON_OPTION);\n> \tif (all_heads)\n> \t\tall_remotes = 1;\n> +\t/* I'm having trouble figuring out exactly what `lifo` stores. Why do both 'date-order' and\n> +\t * 'topo-order' set the same variable!? Aren't they mutually exclusive? Since *both* set it, for\n> +\t * the moment, I'm going to set it for '--authorship-order'; but that seems counterintuitive. */\n\nLines that are too wide.\n\n\t/*\n * Also please format multi-line comments\n * like this, nothing other than slash-asterisk\n * on the first and the last lines.\n */\n\n> @@ -301,7 +328,8 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n> \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n> \t\t}\n> \t}\n> -\titem->date = parse_commit_date(bufptr, tail);\n> +\titem->date = parse_commit_committer_date(bufptr, tail);\n> +\titem->author_date = parse_commit_author_date(bufptr, tail);\n> ...\n> diff --git a/commit.h b/commit.h\n> index 67bd509..de07525 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -17,6 +17,7 @@ struct commit {\n> \tvoid *util;\n> \tunsigned int indegree;\n> \tunsigned long date;\n> +\tunsigned long author_date;\n\nWhile walking we keep many of them in-core, and 8-byte each for each\ncommit objects add up. We do not want to make \"struct commit\" any\nlarger than it already is.\n"},{"id":"219412","messageId":"7vobbl60aj.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"7vip1t7koi.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-04T21:20:04Z","receivedAt":"2013-06-04T21:20:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>> @@ -301,7 +328,8 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n>> \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n>> \t\t}\n>> \t}\n>> -\titem->date = parse_commit_date(bufptr, tail);\n>> +\titem->date = parse_commit_committer_date(bufptr, tail);\n>> +\titem->author_date = parse_commit_author_date(bufptr, tail);\n>> ...\n>> diff --git a/commit.h b/commit.h\n>> index 67bd509..de07525 100644\n>> --- a/commit.h\n>> +++ b/commit.h\n>> @@ -17,6 +17,7 @@ struct commit {\n>> \tvoid *util;\n>> \tunsigned int indegree;\n>> \tunsigned long date;\n>> +\tunsigned long author_date;\n>\n> While walking we keep many of them in-core, and 8-byte each for each\n> commit objects add up. We do not want to make \"struct commit\" any\n> larger than it already is.\n\nHaving said that, I do not see a reasonable alternative\nimplementation than adding an author-date field to struct commit\nwithout major restructuring if we were to add this feature.\n\nSo please do not take this part of the response as a \"patch rejected\nbecause we do not want to add anything to this structure\". We'll\nthink of something down the road, but as an independent topic after\nthis gets in (or doesn't).\n"},{"id":"219413","messageId":"20130604212254.GC3271@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7vip1t7koi.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-04T21:22:55Z","receivedAt":"2013-06-04T21:22:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 04, 2013 at 12:14:21PM -0700, Junio C Hamano wrote:\n\n> > diff --git a/commit.h b/commit.h\n> > index 67bd509..de07525 100644\n> > --- a/commit.h\n> > +++ b/commit.h\n> > @@ -17,6 +17,7 @@ struct commit {\n> > \tvoid *util;\n> > \tunsigned int indegree;\n> > \tunsigned long date;\n> > +\tunsigned long author_date;\n> \n> While walking we keep many of them in-core, and 8-byte each for each\n> commit objects add up. We do not want to make \"struct commit\" any\n> larger than it already is.\n\nYeah, I had the same thought. Maybe this is a good candidate to build on\ntop of the jk/commit-info slab experiment. The topo-sort could allocate\nan extra slab for author-date (or even expand the indegree slab to hold\nboth indegree and author date), use it during the sort, and then free it\nafterwards.\n\nElliott: you can see the relevant changes to the topo-sort in commit\n96c4f4a (commit: allow associating auxiliary info on-demand,\n2013-04-09).\n\n-Peff\n"},{"id":"219521","messageId":"CAPZ477O2mRCi3gUE+Qoa8Vig2Z2Q5cUzRS0+KEZK3zufmOceig@mail.gmail.com","threadId":"34028","inReplyTo":"7vmwr57lo1.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] add --authorship-order flag to git log / rev-list","fromName":"Elliott Cable","fromEmail":"me@ell.io","sentAt":"2013-06-06T18:06:39Z","receivedAt":"2013-06-06T18:06:39Z","isPatch":true,"sender":{"key":"me@ell.io","avatar":"https://gravatar.com/avatar/0d35bb7d7c29b6bbcaafdf13ec70745573d31cb222130cc754a064e707c08d63?d=mp&s=160"},"body":"On Tue, Jun 4, 2013 at 2:53 PM, Junio C Hamano wrote:\n> After reading the subject alone, my reaction was \"is this sorting\n> commits by the name of the author\"?\n>\n> That is one of the expected natural reactions when people hear about\n> this option, which is not what you want.\n>\n> Perhaps naming it --authordate-order (or enhance the command line\n> parsing to allow --date-order=author|committer) would give us a\n> better UI.\n\nThe same comment was raised by someone in IRC when I submitted an RFC\non this. The conclusion we'd arrived at, IIRC, was that the only\nremotely-not-ugly solutions were either --authorship-order or\n--author-date-order.\n\nI really like the idea of [--date-order[=author|committer]], but\nthat's getting beyond my knowledge of the code-base. Perhaps I should\njust implement the changes to the implementation in *my* revision of\nthe patch, and leave it up to a future patcher with the requisite\nknowledge of the argumentation features to throw in the changes to\nthat flag quickly? Either that, or implement it as --author-date-order\nright *now*, and change it later before it hits Master (so we don't\nend up with a no-longer-supported feature?)\n\n(It'd take me many hours to track down the details of how git's\ncodebase goes around doing that, and then attempting to replicate it,\nwhereas someone familiar could probably do it in fifteen minutes,\nhence the thought-process. Commentary welcome.)\n"},{"id":"219530","messageId":"CAPZ477OFM6D4n_Wz-OozN=aYn5-LmNA2ggL+9GNrbGrRQh9pRQ@mail.gmail.com","threadId":"34028","inReplyTo":"7vobbl60aj.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Elliott Cable","fromEmail":"me@ell.io","sentAt":"2013-06-06T19:03:13Z","receivedAt":"2013-06-06T19:03:13Z","isPatch":true,"sender":{"key":"me@ell.io","avatar":"https://gravatar.com/avatar/0d35bb7d7c29b6bbcaafdf13ec70745573d31cb222130cc754a064e707c08d63?d=mp&s=160"},"body":"On Tue, Jun 4, 2013 at 3:14 PM, Junio C Hamano wrote:\n> elliottcable writes:\n>> Thus, I've added an --authorship-order version of --date-order, which relies\n>> upon the AUTHOR_DATE instead of the COMMITTER_DATE; this means that old commits\n>> will continue to show up chronologically in-order despite rebasing.\n>> ---\n>\n> Missing sign-off. Please see Documentation/SubmittingPatches.\n\nWill-do.\n\nI read that part, and was rather confused. At no point did I get the\nidea that I should sign-off *my own initial commit*. Perhaps that part\nof the documentation needs to be slightly re-written? Would that be a\nwelcome change?\n\nOn Tue, Jun 4, 2013 at 3:14 PM, Junio C Hamano wrote:\n> elliottcable writes:\n>> diff --git a/builtin/log.c b/builtin/log.c\n>> index 9e21232..54d4d7f 100644\n>> --- a/builtin/log.c\n>> +++ b/builtin/log.c\n>> @@ -237,7 +237,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n>> int i = revs->early_output;\n>> int show_header = 1;\n>>\n>> - sort_in_topological_order(&list, revs->lifo);\n>> + sort_in_topological_order(&list, revs->lifo, revs->use_author);\n>\n> The name \"use-author\" is a clear sign that the person who added this\n> code were too narrowly focused to think \"author\" automatically would\n> mean \"author date\" ;-).\n>\n> It probably makes sense to revamp sort_in_topological_order(), so\n> that its second parameter is not a boolean 'lifo' that tells too\n> much about its implementation without telling what it actually\n> means. Instead, we can make it an enum sort_order, that tells it to\n> emit the commits in committer-date order, author-date order, or\n> graph-traversal order.\n>\n> And update revs->lifo to use that same enum, without adding\n> use_author_date bit to rev_info.\n\nI'll look into replacing lifo with an enum as soon as I can sit back\ndown to update this patch. For the moment, nothing more than\ncommitter_date_sort and author_date_sort, I suppose?\n\nOverview being, I suppose, that `lifo` will no longer exist (since it\neffectively determines, when truthy, that we operate in a\n*non*-date-ordered topological method); then have commiter_date_order\nand author_date_order bits in an enum, with zero being\nlifo/straightforward-topological-order. Sound about right?\n\nI'll try and make this a separate patch. First commit, to replace lifo\nwith an enum; second commit, to *actually implement* the code obeying\nthat enum when it is set to author_date_order.\n\nOn Tue, Jun 4, 2013 at 5:22 PM, Jeff King wrote:\n> On Tue, Jun 04, 2013 at 12:14:21PM -0700, Junio C Hamano wrote:\n>\n>> > diff --git a/commit.h b/commit.h\n>> > index 67bd509..de07525 100644\n>> > --- a/commit.h\n>> > +++ b/commit.h\n>> > @@ -17,6 +17,7 @@ struct commit {\n>> > void *util;\n>> > unsigned int indegree;\n>> > unsigned long date;\n>> > + unsigned long author_date;\n>>\n>> While walking we keep many of them in-core, and 8-byte each for each\n>> commit objects add up. We do not want to make \"struct commit\" any\n>> larger than it already is.\n>>\n>> Having said that, I do not see a reasonable alternative\n>> implementation than adding an author-date field to struct commit\n>> without major restructuring if we were to add this feature.\n>>\n>> So please do not take this part of the response as a \"patch rejected\n>> because we do not want to add anything to this structure\". We'll\n>> think of something down the road, but as an independent topic after\n>> this gets in (or doesn't).\n>\n> Yeah, I had the same thought. Maybe this is a good candidate to build on\n> top of the jk/commit-info slab experiment. The topo-sort could allocate\n> an extra slab for author-date (or even expand the indegree slab to hold\n> both indegree and author date), use it during the sort, and then free it\n> afterwards.\n>\n> Elliott: you can see the relevant changes to the topo-sort in commit\n> 96c4f4a (commit: allow associating auxiliary info on-demand,\n> 2013-04-09).\n>\n> -Peff\n\nAgain, might be a little over my head. If you really think it's best\nthat I look into that branch, I will try. :)\n\nMeantime, is there any other, more-immediate approach you can think\nof? I thought, for a moment, of only storing *either* the committer\n*or* the author date in the commit-struct at a given time, and\nflagging with a single bit ... but I'm not sure how widely-spread the\nnead for committer-date currently is. Maybe I can go back and\nparse-out the author date *when I need it*, instead, though that\nsounds slow …\n\nEpilogue: I'll make the *obvious* changes mentioned above sometime\nwithin the next week (I'm more than a little swamped; in the middle of\na big breakup, and a big move, simultaneously! :( ), especially the\nenum instead of the use_author bit … and submit another patch RFC. It\nwon't be finalized until we can decide what to do about the extra\n8bytes in the commit struct, though. More input welcome.\n"},{"id":"219533","messageId":"7vtxlbxcl7.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"CAPZ477OFM6D4n_Wz-OozN=aYn5-LmNA2ggL+9GNrbGrRQh9pRQ@mail.gmail.com","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-06T19:29:08Z","receivedAt":"2013-06-06T19:29:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elliott Cable writes:\n\n> On Tue, Jun 4, 2013 at 3:14 PM, Junio C Hamano wrote:\n>> elliottcable writes:\n>>> Thus, I've added an --authorship-order version of --date-order, which relies\n>>> upon the AUTHOR_DATE instead of the COMMITTER_DATE; this means that old commits\n>>> will continue to show up chronologically in-order despite rebasing.\n>>> ---\n>>\n>> Missing sign-off. Please see Documentation/SubmittingPatches.\n>\n> Will-do.\n>\n> I read that part, and was rather confused. At no point did I get the\n> idea that I should sign-off *my own initial commit*. Perhaps that part\n> of the documentation needs to be slightly re-written? Would that be a\n> welcome change?\n\nI fail to see what more needs to be clarified on top of what we\nalready have; please re-read \"(5) Sign your work\" section, paying\nwith special attention to:\n\n - \"YOU WROTE IT or otherwise have the right to pass it on\".\n\n - \"the contribution was created in whole or in part BY ME and I\n HAVE THE RIGHT TO SUBMIT\".\n\nBut perhaps you meant something else by \"*my own initial commit*\"???\n"},{"id":"219534","messageId":"CAPZ477O4DyAcd-eZp2UQhta61e6AeGZiTxPuXOcuEP0X+8wRAA@mail.gmail.com","threadId":"34028","inReplyTo":"7vtxlbxcl7.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Elliott Cable","fromEmail":"me@ell.io","sentAt":"2013-06-06T19:32:08Z","receivedAt":"2013-06-06T19:32:08Z","isPatch":true,"sender":{"key":"me@ell.io","avatar":"https://gravatar.com/avatar/0d35bb7d7c29b6bbcaafdf13ec70745573d31cb222130cc754a064e707c08d63?d=mp&s=160"},"body":"Wow. That's my bad entirely. I apparently hallucinated a section\nsuggesting that you “sign-off” commits that you'd reviewed, or\nsomething; and I'd completely skipped the section on certifying that\nyou have legal rights to the work, because I'd *written* it, and\ndidn't think it'd be relevant.\n\nI feel like an idiot. Forgive me. I'll --signoff my next version of\nthe patch. o7\n\nOn Thu, Jun 6, 2013 at 3:29 PM, Junio C Hamano wrote:\n> Elliott Cable writes:\n>\n>> On Tue, Jun 4, 2013 at 3:14 PM, Junio C Hamano wrote:\n>>> elliottcable writes:\n>>>> Thus, I've added an --authorship-order version of --date-order, which relies\n>>>> upon the AUTHOR_DATE instead of the COMMITTER_DATE; this means that old commits\n>>>> will continue to show up chronologically in-order despite rebasing.\n>>>> ---\n>>>\n>>> Missing sign-off. Please see Documentation/SubmittingPatches.\n>>\n>> Will-do.\n>>\n>> I read that part, and was rather confused. At no point did I get the\n>> idea that I should sign-off *my own initial commit*. Perhaps that part\n>> of the documentation needs to be slightly re-written? Would that be a\n>> welcome change?\n>\n> I fail to see what more needs to be clarified on top of what we\n> already have; please re-read \"(5) Sign your work\" section, paying\n> with special attention to:\n>\n> - \"YOU WROTE IT or otherwise have the right to pass it on\".\n>\n> - \"the contribution was created in whole or in part BY ME and I\n> HAVE THE RIGHT TO SUBMIT\".\n>\n> But perhaps you meant something else by \"*my own initial commit*\"???\n"},{"id":"219554","messageId":"7vobbjxc21.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"CAPZ477OFM6D4n_Wz-OozN=aYn5-LmNA2ggL+9GNrbGrRQh9pRQ@mail.gmail.com","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-06T19:40:38Z","receivedAt":"2013-06-06T19:40:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elliott Cable writes:\n\n>> And update revs->lifo to use that same enum, without adding\n>> use_author_date bit to rev_info.\n>\n> I'll look into replacing lifo with an enum as soon as I can sit back\n> down to update this patch. For the moment, nothing more than\n> committer_date_sort and author_date_sort, I suppose?\n\n> I'll try and make this a separate patch. First commit, to replace lifo\n> with an enum; second commit, to *actually implement* the code obeying\n> that enum when it is set to author_date_order.\n\nIf you want to do this in a multi-step series (which may not be a\nbad idea), I would imagine that the enum starts as a choice between\nthe two: traversal-order vs committer-date-order. The first patch\nwould change nothing else.\n\nAnd then you would add the third choice, author-date-order, and\nimplement the logic to sort them using author instead of committer\ndate in the same patch.\n\n>> Elliott: you can see the relevant changes to the topo-sort in commit\n>> 96c4f4a (commit: allow associating auxiliary info on-demand,\n>> 2013-04-09).\n>>\n>> -Peff\n>\n> Again, might be a little over my head. If you really think it's best\n> that I look into that branch, I will try. :)\n>\n> Meantime, is there any other, more-immediate approach you can think\n> of? I thought, for a moment, of only storing *either* the committer\n> *or* the author date in the commit-struct at a given time, and\n> flagging with a single bit ... but I'm not sure how widely-spread the\n> nead for committer-date currently is. Maybe I can go back and\n> parse-out the author date *when I need it*, instead, though that\n> sounds slow …\n\nYou would parse all of them at the beginning of topo-sort function\nonce and store these dates in the commit-info-slab (alongside with\nindegree). Once you are done sorting, you can discard the slab.\n\nThis could be done as a follow-up patch, but the tons of helper\nfunctions you added to compare by author date to revision.c will\nhave to be removed in such a transition, because the whole point of\nusing commit-info-slab is not to have commit->author_date field,\nwhich these new helpers work on.\n"},{"id":"219571","messageId":"7vvc5qx3cm.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"7vobbjxc21.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] rev-list: add --authorship-order alternative ordering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-06T22:48:41Z","receivedAt":"2013-06-06T22:48:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> If you want to do this in a multi-step series (which may not be a\n> bad idea), I would imagine that the enum starts as a choice between\n> the two: traversal-order vs committer-date-order. The first patch\n> would change nothing else.\n>\n> And then you would add the third choice, author-date-order, and\n> implement the logic to sort them using author instead of committer\n> date in the same patch.\n> ...\n> You would parse all of them at the beginning of topo-sort function\n> once and store these dates in the commit-info-slab (alongside with\n> indegree). Once you are done sorting, you can discard the slab.\n>\n> This could be done as a follow-up patch, but the tons of helper\n> functions you added to compare by author date to revision.c will\n> have to be removed in such a transition, because the whole point of\n> using commit-info-slab is not to have commit->author_date field,\n> which these new helpers work on.\n\nAs I needed to have an excuse to push jk/commit-info-slab topic\nfurther (I have an unpublished show-branch rewrite on top of it),\nI may take a look at doing this myself if/when I find some time.\n"},{"id":"219572","messageId":"7vppvyx1mv.fsf_-_@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"7vvc5qx3cm.fsf@alter.siamese.dyndns.org","subject":"[PATCH] toposort: rename \"lifo\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-06T23:25:44Z","receivedAt":"2013-06-06T23:25:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When sorting commits topologically, the primary invariant is to emit\nall children before its parent is emitted. When traversing a forked\nhistory like this with \"git log C E\":\n\n A----B----C\n \\\n D----E\n\nwe ensure that A is emitted after all of B, C, D, and E are done, B\nhas to wait until C is done, and D has to wait until E is done.\n\nIn some applications, however, we would further want to control how\nthese child commits B, C, D and E on two parallel ancestry chains\nare shown. Most of the time, we would want to see C and B emitted\ntogether, and then E and D, and finally A. This is the default\nbehaviour for --topo-order output.\n\nThe \"lifo\" parameter of the sort_in_topological_order() function is\nused to control this. After inspecting C, we notice and record that\nB needs to be inspected, and by structuring the \"work to be done\"\nset as a LIFO stack, we ensure that B is inspected next, before\nother in-flight commits we had known that we will need to inspect,\ne.g. E, that have already been in the \"work to be done\" set.\n\nWhen showing in --date-order, we would want to see commits ordered\nby timestamps, i.e. show C, E, B and D in this order before showing\nA, mixing commits from two parallel histories together. When \"lifo\"\nis set to false, the function keeps the \"work to be done\" set sorted\nin the date order to realize this sematics.\n\nBut the name \"lifo\" is too tied to the way how the function implements\nits behaviour, and does not describe _what_ is the desired semantcs.\n\nReplace the \"lifo\" field with an enum rev_sort_order, with two\npossible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE.\n\nThe mechanical replacement rule is:\n\n \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n\nSigned-off-by: Junio C Hamano \n---\n\n> As I needed to have an excuse to push jk/commit-info-slab topic\n> further (I have an unpublished show-branch rewrite on top of it),\n> I may take a look at doing this myself if/when I find some time.\n\n So this is the first step, applies on top of jk/commit-info-slab.\n\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 ++++++++------\n commit.c | 12 ++++++++----\n commit.h | 14 +++++++++++---\n revision.c | 10 +++++-----\n revision.h | 6 +++++-\n 6 files changed, 38 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 8f0b2e8..8d26042 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -205,7 +205,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n \tint i = revs->early_output;\n \tint show_header = 1;\n \n-\tsort_in_topological_order(&list, revs->lifo);\n+\tsort_in_topological_order(&list, revs->sort_order);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex d208fd6..7c57985 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -631,7 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \tint num_rev, i, extra = 0;\n \tint all_heads = 0, all_remotes = 0;\n \tint all_mask, all_revs;\n-\tint lifo = 1;\n+\tenum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;\n \tchar head[128];\n \tconst char *head_p;\n \tint head_len;\n@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\t\t N_(\"show possible merge bases\")),\n \t\tOPT_BOOLEAN(0, \"independent\", &independent,\n \t\t\t N_(\"show refs unreachable from any other ref\")),\n-\t\tOPT_BOOLEAN(0, \"topo-order\", &lifo,\n-\t\t\t N_(\"show commits in topological order\")),\n+\t\tOPT_SET_INT(0, \"topo-order\", &sort_order,\n+\t\t\t N_(\"show commits in topological order\"),\n+\t\t\t REV_SORT_IN_GRAPH_ORDER),\n \t\tOPT_BOOLEAN(0, \"topics\", &topics,\n \t\t\t N_(\"show only commits not on the first branch\")),\n \t\tOPT_SET_INT(0, \"sparse\", &dense,\n \t\t\t N_(\"show merges reachable from only one tip\"), 0),\n-\t\tOPT_SET_INT(0, \"date-order\", &lifo,\n+\t\tOPT_SET_INT(0, \"date-order\", &sort_order,\n \t\t\t N_(\"show commits where no parent comes before its \"\n-\t\t\t \"children\"), 0),\n+\t\t\t \"children\"),\n+\t\t\t REV_SORT_BY_COMMIT_DATE),\n \t\t{ OPTION_CALLBACK, 'g', \"reflog\", &reflog_base, N_(\"[,]\"),\n \t\t\t N_(\"show most recent ref-log entries starting at \"\n \t\t\t \"base\"),\n@@ -901,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\texit(0);\n \n \t/* Sort topologically */\n-\tsort_in_topological_order(&seen, lifo);\n+\tsort_in_topological_order(&seen, sort_order);\n \n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\ndiff --git a/commit.c b/commit.c\nindex 66a6c00..fc1734b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -507,7 +507,7 @@ define_commit_slab(indegree_slab, int);\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo)\n+void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n@@ -556,7 +556,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t}\n \n \t/* process the list in topological order */\n-\tif (!lifo)\n+\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n \t\tcommit_list_sort_by_date(&work);\n \n \tpptr = list;\n@@ -583,10 +583,14 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n \t\t\tif (--(*pi) == 1) {\n-\t\t\t\tif (!lifo)\n+\t\t\t\tswitch (sort_order) {\n+\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n \t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\telse\n+\t\t\t\t\tbreak;\n+\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t\t/*\ndiff --git a/commit.h b/commit.h\nindex 70e749d..247e474 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -139,15 +139,23 @@ struct commit *pop_commit(struct commit_list **stack);\n void clear_commit_marks(struct commit *commit, unsigned int mark);\n void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n \n+\n+enum rev_sort_order {\n+\tREV_SORT_IN_GRAPH_ORDER = 0,\n+\tREV_SORT_BY_COMMIT_DATE\n+};\n+\n /*\n * Performs an in-place topological sort of list supplied.\n *\n * invariant of resulting list is:\n * a reachable from b => ord(b) < ord(a)\n- * in addition, when lifo == 0, commits on parallel tracks are\n- * sorted in the dates order.\n+ * sort_order further specifies:\n+ * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\n+ * chain together.\n+ * REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo);\n+void sort_in_topological_order(struct commit_list **, enum rev_sort_order);\n \n struct commit_graft {\n \tunsigned char sha1[20];\ndiff --git a/revision.c b/revision.c\nindex cf620c6..966ebbc 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1038,7 +1038,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \tDIFF_OPT_SET(&revs->pruning, QUICK);\n \trevs->pruning.add_remove = file_add_remove;\n \trevs->pruning.change = file_change;\n-\trevs->lifo = 1;\n+\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \trevs->dense = 1;\n \trevs->prefix = prefix;\n \trevs->max_age = -1;\n@@ -1373,7 +1373,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--merge\")) {\n \t\trevs->show_merge = 1;\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n-\t\trevs->lifo = 1;\n+\t\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \t\trevs->topo_order = 1;\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n@@ -1391,7 +1391,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->prune = 1;\n \t\tload_ref_decorations(DECORATE_SHORT_REFS);\n \t} else if (!strcmp(arg, \"--date-order\")) {\n-\t\trevs->lifo = 0;\n+\t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n@@ -2165,7 +2165,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n-\t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n \tif (revs->children.name)\n@@ -2480,7 +2480,7 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \t * If revs->topo_order is set, sort the boundary commits\n \t * in topological order\n \t */\n-\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tsort_in_topological_order(&revs->commits, revs->sort_order);\n }\n \n static struct commit *get_revision_internal(struct rev_info *revs)\ndiff --git a/revision.h b/revision.h\nindex 5da09ee..2a5e325 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"grep.h\"\n #include \"notes.h\"\n+#include \"commit.h\"\n \n #define SEEN\t\t(1u<<0)\n #define UNINTERESTING (1u<<1)\n@@ -60,6 +61,10 @@ struct rev_info {\n \tconst char *prefix;\n \tconst char *def;\n \tstruct pathspec prune_data;\n+\n+\t/* topo-sort */\n+\tenum rev_sort_order sort_order;\n+\n \tunsigned int\tearly_output:1,\n \t\t\tignore_missing:1;\n \n@@ -70,7 +75,6 @@ struct rev_info {\n \t\t\tshow_all:1,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n-\t\t\tlifo:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\n \t\t\tsimplify_by_decoration:1,\n-- \n1.8.3-451-gb703ddf\n"},{"id":"219577","messageId":"7vfvwuww39.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"7vppvyx1mv.fsf_-_@alter.siamese.dyndns.org","subject":"Re: [PATCH] toposort: rename \"lifo\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-07T01:25:30Z","receivedAt":"2013-06-07T01:25:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> When sorting commits topologically, the primary invariant is to emit\n> all children before its parent is emitted. When traversing a forked\n\ns/its/their/;\n\n>> As I needed to have an excuse to push jk/commit-info-slab topic\n>> further (I have an unpublished show-branch rewrite on top of it),\n>> I may take a look at doing this myself if/when I find some time.\n>\n> So this is the first step, applies on top of jk/commit-info-slab.\n\nThe next step will be to replace the use of commit_list in this\nfunction with a priority queue, whose API may look like what is at\nthe end of this message.\n\nThen write a compare function that looks at commit->date field to\ncompare committer timestamp, and set it to commit_queue->compare\nwhen REV_SORT_BY_COMMIT_DATE is asked for. When doing the graph\ntraversal order, set compare function to NULL when initializing the\ncommit_queue and use it as a LIFO stack.\n\nAnd the step after that will be to add an author-date field to the\ncommit-info-slab we currently use to keep track of indegree, grab\nauthor timestamp from commits as we encounter them, and write\nanother comparison function to use that information (using the\ncb_data field of commit_queue to point at the info slab) to\nimplement REV_SORT_BY_AUTHOR_DATE. That step can also implement the\ncommand line option parsing for the new --author-date-order option\n(or alternatively, --date-order={author,committer}).\n\n\n#ifndef COMMIT_QUEUE_H\n#define COMMIT_QUEUE_H\n\n/*\n * Compare two commits; the third parameter is cb_data in the\n * commit_queue structure.\n */\ntypedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);\n\nstruct commit_queue {\n\tcommit_compare_fn compare;\n\tvoid *cb_data;\n\tint alloc, nr;\n\tstruct commit **array;\n};\n\n/*\n * Add the commit to the queue\n */\nstruct commit *commit_queue_put(struct commit_queue *, struct commit *);\n\n/*\n * Extract the commit that compares the smallest out of the queue,\n * or NULL. If compare function is NULL, the queue acts as a LIFO\n * stack.\n */\nstruct commit *commit_queue_get(struct commit_queue *);\n\n#endif /* COMMIT_QUEUE_H */\n"},{"id":"219592","messageId":"CAPig+cTJT2S1KuQgrBuJuSBukNqWjnCV5WC+zJoZxTugHBCZfQ@mail.gmail.com","threadId":"34028","inReplyTo":"7vppvyx1mv.fsf_-_@alter.siamese.dyndns.org","subject":"Re: [PATCH] toposort: rename \"lifo\" field","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-06-07T05:09:26Z","receivedAt":"2013-06-07T05:09:26Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Jun 6, 2013 at 7:25 PM, Junio C Hamano wrote:\n> When sorting commits topologically, the primary invariant is to emit\n> all children before its parent is emitted. When traversing a forked\n> history like this with \"git log C E\":\n>\n> A----B----C\n> \\\n> D----E\n>\n> we ensure that A is emitted after all of B, C, D, and E are done, B\n> has to wait until C is done, and D has to wait until E is done.\n>\n> In some applications, however, we would further want to control how\n> these child commits B, C, D and E on two parallel ancestry chains\n> are shown. Most of the time, we would want to see C and B emitted\n> together, and then E and D, and finally A. This is the default\n> behaviour for --topo-order output.\n>\n> The \"lifo\" parameter of the sort_in_topological_order() function is\n> used to control this. After inspecting C, we notice and record that\n> B needs to be inspected, and by structuring the \"work to be done\"\n> set as a LIFO stack, we ensure that B is inspected next, before\n> other in-flight commits we had known that we will need to inspect,\n> e.g. E, that have already been in the \"work to be done\" set.\n>\n> When showing in --date-order, we would want to see commits ordered\n> by timestamps, i.e. show C, E, B and D in this order before showing\n> A, mixing commits from two parallel histories together. When \"lifo\"\n> is set to false, the function keeps the \"work to be done\" set sorted\n> in the date order to realize this sematics.\n\ns/sematics/semantics/ (or perhaps s/.../semantic/ ?)\n\n> But the name \"lifo\" is too tied to the way how the function implements\n> its behaviour, and does not describe _what_ is the desired semantcs.\n\ns/semantcs/semantics/\n\n> Replace the \"lifo\" field with an enum rev_sort_order, with two\n> possible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE.\n>\n> The mechanical replacement rule is:\n>\n> \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n> \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n>\n> Signed-off-by: Junio C Hamano \n"},{"id":"219593","messageId":"1370581872-31580-1-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"7vfvwuww39.fsf@alter.siamese.dyndns.org","subject":"[PATCH 0/3] Preparing for --date-order=author","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-07T05:11:09Z","receivedAt":"2013-06-07T05:11:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"These three patches introduce a commit-queue API to manage a set of\ncommits in a priority queue, with a caller-specified comparison\nfunction. The priority queue replaces the singly-listed commit_list\nin the topological sort function.\n\nThe series applies on top of the commit-info-slab API sesries Peff\nand I did two months ago. These three patches do not use the slab\nAPI yet, but a follow-on patch to introduce REV_SORT_BY_AUTHOR_DATE\nneeds to use commit-slab to record author date for the commits being\nsorted, and consult it in its comparison function when comparing the\nauthor dates of commits.\n\nJunio C Hamano (3):\n toposort: rename \"lifo\" field\n commit-queue: LIFO or priority queue of commits\n sort-in-topological-order: use commit-queue\n\n Makefile | 2 ++\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 +++++----\n commit-queue.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++\n commit-queue.h | 34 +++++++++++++++++++++\n commit.c | 70 +++++++++++++++++++++++++-----------------\n commit.h | 14 +++++++--\n revision.c | 10 +++---\n revision.h | 6 +++-\n 9 files changed, 193 insertions(+), 43 deletions(-)\n create mode 100644 commit-queue.c\n create mode 100644 commit-queue.h\n\n-- \n1.8.3-451-gb703ddf\n"},{"id":"219596","messageId":"1370581872-31580-2-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370581872-31580-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/3] toposort: rename \"lifo\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-07T05:11:10Z","receivedAt":"2013-06-07T05:11:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The primary invariant of sort_in_topological_order() is to emit all\nchildren before their parent is emitted. When traversing a forked\nhistory like this with \"git log C E\":\n\n A----B----C\n \\\n D----E\n\nwe ensure that A is emitted after all of B, C, D, and E are done, B\nhas to wait until C is done, and D has to wait until E is done.\n\nIn some applications, however, we would further want to control how\nthese child commits B, C, D and E on two parallel ancestry chains\nare shown. Most of the time, we would want to see C and B emitted\ntogether, and then E and D, and finally A, which is the default\nbehaviour for --topo-order output.\n\nThe \"lifo\" parameter of the sort_in_topological_order() function is\nused to implement this behaviour. After inspecting C, we notice and\nrecord that B needs to be inspected, and by structuring the \"work to\nbe done\" set as a LIFO stack, we ensure that B is inspected next,\nbefore other in-flight commits we had known that we will need to\ninspect, e.g. E, that may have already been sitting in the \"work to\nbe done\" set.\n\nWhen showing in --date-order, we would want to see commits ordered\nby timestamps, i.e. show C, E, B and D in this order before showing\nA, possibly mixing commits from two parallel histories together.\nWhen \"lifo\" parameter is set to false, the function keeps the \"work\nto be done\" set sorted in the date order to realize this semantics.\n\nBut the name \"lifo\" is too tied to the way how the function implements\nits behaviour, and does not describe _what_ the desired semantics is.\n\nReplace the \"lifo\" field with an enum rev_sort_order, with two\npossible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE.\n\nThe mechanical replacement rule is:\n\n \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n\nSigned-off-by: Junio C Hamano \n---\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 ++++++++------\n commit.c | 12 ++++++++----\n commit.h | 14 +++++++++++---\n revision.c | 10 +++++-----\n revision.h | 6 +++++-\n 6 files changed, 38 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 8f0b2e8..8d26042 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -205,7 +205,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n \tint i = revs->early_output;\n \tint show_header = 1;\n \n-\tsort_in_topological_order(&list, revs->lifo);\n+\tsort_in_topological_order(&list, revs->sort_order);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex d208fd6..7c57985 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -631,7 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \tint num_rev, i, extra = 0;\n \tint all_heads = 0, all_remotes = 0;\n \tint all_mask, all_revs;\n-\tint lifo = 1;\n+\tenum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;\n \tchar head[128];\n \tconst char *head_p;\n \tint head_len;\n@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\t\t N_(\"show possible merge bases\")),\n \t\tOPT_BOOLEAN(0, \"independent\", &independent,\n \t\t\t N_(\"show refs unreachable from any other ref\")),\n-\t\tOPT_BOOLEAN(0, \"topo-order\", &lifo,\n-\t\t\t N_(\"show commits in topological order\")),\n+\t\tOPT_SET_INT(0, \"topo-order\", &sort_order,\n+\t\t\t N_(\"show commits in topological order\"),\n+\t\t\t REV_SORT_IN_GRAPH_ORDER),\n \t\tOPT_BOOLEAN(0, \"topics\", &topics,\n \t\t\t N_(\"show only commits not on the first branch\")),\n \t\tOPT_SET_INT(0, \"sparse\", &dense,\n \t\t\t N_(\"show merges reachable from only one tip\"), 0),\n-\t\tOPT_SET_INT(0, \"date-order\", &lifo,\n+\t\tOPT_SET_INT(0, \"date-order\", &sort_order,\n \t\t\t N_(\"show commits where no parent comes before its \"\n-\t\t\t \"children\"), 0),\n+\t\t\t \"children\"),\n+\t\t\t REV_SORT_BY_COMMIT_DATE),\n \t\t{ OPTION_CALLBACK, 'g', \"reflog\", &reflog_base, N_(\"[,]\"),\n \t\t\t N_(\"show most recent ref-log entries starting at \"\n \t\t\t \"base\"),\n@@ -901,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\texit(0);\n \n \t/* Sort topologically */\n-\tsort_in_topological_order(&seen, lifo);\n+\tsort_in_topological_order(&seen, sort_order);\n \n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\ndiff --git a/commit.c b/commit.c\nindex 66a6c00..fc1734b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -507,7 +507,7 @@ define_commit_slab(indegree_slab, int);\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo)\n+void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n@@ -556,7 +556,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t}\n \n \t/* process the list in topological order */\n-\tif (!lifo)\n+\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n \t\tcommit_list_sort_by_date(&work);\n \n \tpptr = list;\n@@ -583,10 +583,14 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n \t\t\tif (--(*pi) == 1) {\n-\t\t\t\tif (!lifo)\n+\t\t\t\tswitch (sort_order) {\n+\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n \t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\telse\n+\t\t\t\t\tbreak;\n+\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t\t/*\ndiff --git a/commit.h b/commit.h\nindex 70e749d..247e474 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -139,15 +139,23 @@ struct commit *pop_commit(struct commit_list **stack);\n void clear_commit_marks(struct commit *commit, unsigned int mark);\n void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n \n+\n+enum rev_sort_order {\n+\tREV_SORT_IN_GRAPH_ORDER = 0,\n+\tREV_SORT_BY_COMMIT_DATE\n+};\n+\n /*\n * Performs an in-place topological sort of list supplied.\n *\n * invariant of resulting list is:\n * a reachable from b => ord(b) < ord(a)\n- * in addition, when lifo == 0, commits on parallel tracks are\n- * sorted in the dates order.\n+ * sort_order further specifies:\n+ * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\n+ * chain together.\n+ * REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo);\n+void sort_in_topological_order(struct commit_list **, enum rev_sort_order);\n \n struct commit_graft {\n \tunsigned char sha1[20];\ndiff --git a/revision.c b/revision.c\nindex cf620c6..966ebbc 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1038,7 +1038,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \tDIFF_OPT_SET(&revs->pruning, QUICK);\n \trevs->pruning.add_remove = file_add_remove;\n \trevs->pruning.change = file_change;\n-\trevs->lifo = 1;\n+\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \trevs->dense = 1;\n \trevs->prefix = prefix;\n \trevs->max_age = -1;\n@@ -1373,7 +1373,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--merge\")) {\n \t\trevs->show_merge = 1;\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n-\t\trevs->lifo = 1;\n+\t\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \t\trevs->topo_order = 1;\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n@@ -1391,7 +1391,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->prune = 1;\n \t\tload_ref_decorations(DECORATE_SHORT_REFS);\n \t} else if (!strcmp(arg, \"--date-order\")) {\n-\t\trevs->lifo = 0;\n+\t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n@@ -2165,7 +2165,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n-\t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n \tif (revs->children.name)\n@@ -2480,7 +2480,7 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \t * If revs->topo_order is set, sort the boundary commits\n \t * in topological order\n \t */\n-\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tsort_in_topological_order(&revs->commits, revs->sort_order);\n }\n \n static struct commit *get_revision_internal(struct rev_info *revs)\ndiff --git a/revision.h b/revision.h\nindex 5da09ee..2a5e325 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"grep.h\"\n #include \"notes.h\"\n+#include \"commit.h\"\n \n #define SEEN\t\t(1u<<0)\n #define UNINTERESTING (1u<<1)\n@@ -60,6 +61,10 @@ struct rev_info {\n \tconst char *prefix;\n \tconst char *def;\n \tstruct pathspec prune_data;\n+\n+\t/* topo-sort */\n+\tenum rev_sort_order sort_order;\n+\n \tunsigned int\tearly_output:1,\n \t\t\tignore_missing:1;\n \n@@ -70,7 +75,6 @@ struct rev_info {\n \t\t\tshow_all:1,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n-\t\t\tlifo:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\n \t\t\tsimplify_by_decoration:1,\n-- \n1.8.3-451-gb703ddf\n"},{"id":"219594","messageId":"1370581872-31580-3-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370581872-31580-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/3] commit-queue: LIFO or priority queue of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-07T05:11:11Z","receivedAt":"2013-06-07T05:11:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Traditionally we used a singly linked list of commits to hold a set\nof in-flight commits while traversing history. The most typical use\nof the list is to insert commit that is newly discovered in it, keep\nit sorted by commit timestamp, pick up the newest one from the list,\nand keep digging. The cost of keeping the singly linked list sorted\nis nontrivial, and this typical use pattern better matches a priority\nqueue.\n\nIntroduce a commit-queue structure, that can be used either as a\nLIFO stack, or a priority queue. This will be used in the next\npatch to hold in-flight commits during sort-in-topological-order.\n\nSigned-off-by: Junio C Hamano \n---\n Makefile | 2 ++\n commit-queue.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit-queue.h | 31 +++++++++++++++++++++++++\n 3 files changed, 104 insertions(+)\n create mode 100644 commit-queue.c\n create mode 100644 commit-queue.h\n\ndiff --git a/Makefile b/Makefile\nindex 598d631..3cf55e9 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -634,6 +634,7 @@ LIB_H += cache.h\n LIB_H += color.h\n LIB_H += column.h\n LIB_H += commit.h\n+LIB_H += commit-queue.h\n LIB_H += compat/bswap.h\n LIB_H += compat/cygwin.h\n LIB_H += compat/mingw.h\n@@ -757,6 +758,7 @@ LIB_OBJS += color.o\n LIB_OBJS += column.o\n LIB_OBJS += combine-diff.o\n LIB_OBJS += commit.o\n+LIB_OBJS += commit-queue.o\n LIB_OBJS += compat/obstack.o\n LIB_OBJS += compat/terminal.o\n LIB_OBJS += config.o\ndiff --git a/commit-queue.c b/commit-queue.c\nnew file mode 100644\nindex 0000000..77d4b02\n--- /dev/null\n+++ b/commit-queue.c\n@@ -0,0 +1,71 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"commit-queue.h\"\n+\n+void clear_commit_queue(struct commit_queue *queue)\n+{\n+\tfree(queue->array);\n+\tqueue->nr = 0;\n+\tqueue->alloc = 0;\n+\tqueue->array = NULL;\n+}\n+\n+void commit_queue_put(struct commit_queue *queue, struct commit *commit)\n+{\n+\tcommit_compare_fn compare = queue->compare;\n+\tint ix, parent;\n+\n+\t/* Append at the end */\n+\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n+\tqueue->array[queue->nr++] = commit;\n+\tif (!compare)\n+\t\treturn; /* LIFO */\n+\n+\t/* Bubble up the new one */\n+\tfor (ix = queue->nr - 1; ix; ix = parent) {\n+\t\tparent = (ix - 1) / 2;\n+\t\tif (compare(queue->array[parent], queue->array[ix],\n+\t\t\t queue->cb_data) < 0)\n+\t\t\tbreak;\n+\n+\t\tcommit = queue->array[parent];\n+\t\tqueue->array[parent] = queue->array[ix];\n+\t\tqueue->array[ix] = commit;\n+\t}\n+}\n+\n+struct commit *commit_queue_get(struct commit_queue *queue)\n+{\n+\tstruct commit *result, *swap;\n+\tint ix, child;\n+\tcommit_compare_fn compare = queue->compare;\n+\n+\tif (!queue->nr)\n+\t\treturn NULL;\n+\tif (!compare)\n+\t\treturn queue->array[--queue->nr]; /* LIFO */\n+\n+\tresult = queue->array[0];\n+\tif (!--queue->nr)\n+\t\treturn result;\n+\n+\tqueue->array[0] = queue->array[queue->nr];\n+\n+\t/* Push down the one at the root */\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\t\tchild = ix * 2 + 1; /* left */\n+\t\tif ((child + 1 < queue->nr) &&\n+\t\t (compare(queue->array[child], queue->array[child + 1],\n+\t\t\t queue->cb_data) >= 0))\n+\t\t\tchild++; /* use right child */\n+\n+\t\tif (compare(queue->array[ix], queue->array[child],\n+\t\t\t queue->cb_data) < 0)\n+\t\t\tbreak;\n+\n+\t\tswap = queue->array[child];\n+\t\tqueue->array[child] = queue->array[ix];\n+\t\tqueue->array[ix] = swap;\n+\t}\n+\treturn result;\n+}\ndiff --git a/commit-queue.h b/commit-queue.h\nnew file mode 100644\nindex 0000000..7c5dc4c\n--- /dev/null\n+++ b/commit-queue.h\n@@ -0,0 +1,31 @@\n+#ifndef COMMIT_QUEUE_H\n+#define COMMIT_QUEUE_H\n+\n+/*\n+ * Compare two commits; the third parameter is cb_data in the\n+ * commit_queue structure.\n+ */\n+typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);\n+\n+struct commit_queue {\n+\tcommit_compare_fn compare;\n+\tvoid *cb_data;\n+\tint alloc, nr;\n+\tstruct commit **array;\n+};\n+\n+/*\n+ * Add the commit to the queue\n+ */\n+extern void commit_queue_put(struct commit_queue *, struct commit *);\n+\n+/*\n+ * Extract the commit that compares the smallest out of the queue,\n+ * or NULL. If compare function is NULL, the queue acts as a LIFO\n+ * stack.\n+ */\n+extern struct commit *commit_queue_get(struct commit_queue *);\n+\n+extern void clear_commit_queue(struct commit_queue *);\n+\n+#endif /* COMMIT_QUEUE_H */\n-- \n1.8.3-451-gb703ddf\n"},{"id":"219595","messageId":"1370581872-31580-4-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370581872-31580-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/3] sort-in-topological-order: use commit-queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-07T05:11:12Z","receivedAt":"2013-06-07T05:11:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Use the commit-queue data structure to implement a priority queue\nof commits sorted by committer date, when handling --date-order.\nThe commit-queue structure can also be used as a simple LIFO stack,\nwhich is a good match for --topo-order processing.\n\nSigned-off-by: Junio C Hamano \n---\n commit-queue.c | 13 +++++++++++\n commit-queue.h | 3 +++\n commit.c | 74 ++++++++++++++++++++++++++++++++++------------------------\n 3 files changed, 59 insertions(+), 31 deletions(-)\n\ndiff --git a/commit-queue.c b/commit-queue.c\nindex 77d4b02..ffffc4e 100644\n--- a/commit-queue.c\n+++ b/commit-queue.c\n@@ -2,6 +2,19 @@\n #include \"commit.h\"\n #include \"commit-queue.h\"\n \n+void commit_queue_reverse(struct commit_queue *queue)\n+{\n+\tint i, j;\n+\n+\tif (queue->compare != NULL)\n+\t\tdie(\"BUG: commit_queue_reverse() on non-LIFO queue\");\n+\tfor (i = 0; i <= (j = (queue->nr - 1) - i); i++) {\n+\t\tstruct commit *swap = queue->array[i];\n+\t\tqueue->array[i] = queue->array[j];\n+\t\tqueue->array[j] = swap;\n+\t}\n+}\n+\n void clear_commit_queue(struct commit_queue *queue)\n {\n \tfree(queue->array);\ndiff --git a/commit-queue.h b/commit-queue.h\nindex 7c5dc4c..d3c92e5 100644\n--- a/commit-queue.h\n+++ b/commit-queue.h\n@@ -28,4 +28,7 @@ extern struct commit *commit_queue_get(struct commit_queue *);\n \n extern void clear_commit_queue(struct commit_queue *);\n \n+/* Reverse the LIFO elements */\n+extern void commit_queue_reverse(struct commit_queue *);\n+\n #endif /* COMMIT_QUEUE_H */\ndiff --git a/commit.c b/commit.c\nindex fc1734b..46cd150 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -9,6 +9,7 @@\n #include \"gpg-interface.h\"\n #include \"mergesort.h\"\n #include \"commit-slab.h\"\n+#include \"commit-queue.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -504,21 +505,41 @@ struct commit *pop_commit(struct commit_list **stack)\n \n define_commit_slab(indegree_slab, int);\n \n+static int compare_commits_by_commit_date(struct commit *a, struct commit *b, void *unused)\n+{\n+\t/* newer commits with larger date first */\n+\tif (a->date < b->date)\n+\t\treturn 1;\n+\telse if (a->date > b->date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n+void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n-\tstruct commit_list *work, **insert;\n \tstruct commit_list **pptr;\n \tstruct indegree_slab indegree;\n+\tstruct commit_queue queue;\n+\tstruct commit *commit;\n \n \tif (!orig)\n \t\treturn;\n \t*list = NULL;\n \n \tinit_indegree_slab(&indegree);\n+\tmemset(&queue, '\\0', sizeof(queue));\n+\tswitch (sort_order) {\n+\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n+\t\tqueue.compare = NULL;\n+\t\tbreak;\n+\tcase REV_SORT_BY_COMMIT_DATE:\n+\t\tqueue.compare = compare_commits_by_commit_date;\n+\t\tbreak;\n+\t}\n \n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n@@ -528,7 +549,7 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \n \t/* update the indegree */\n \tfor (next = orig; next; next = next->next) {\n-\t\tstruct commit_list * parents = next->item->parents;\n+\t\tstruct commit_list *parents = next->item->parents;\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n@@ -546,30 +567,28 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \t *\n \t * the tips serve as a starting set for the work queue.\n \t */\n-\twork = NULL;\n-\tinsert = &work;\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \n \t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n-\t\t\tinsert = &commit_list_insert(commit, insert)->next;\n+\t\t\tcommit_queue_put(&queue, commit);\n \t}\n \n-\t/* process the list in topological order */\n-\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n-\t\tcommit_list_sort_by_date(&work);\n+\t/*\n+\t * This is unfortunate; the initial tips need to be shown\n+\t * in the order given from the revision traversal machinery.\n+\t */\n+\tif (sort_order == REV_SORT_IN_GRAPH_ORDER)\n+\t\tcommit_queue_reverse(&queue);\n+\n+\t/* We no longer need the commit list */\n+\tfree_commit_list(orig);\n \n \tpptr = list;\n \t*list = NULL;\n-\twhile (work) {\n-\t\tstruct commit *commit;\n-\t\tstruct commit_list *parents, *work_item;\n-\n-\t\twork_item = work;\n-\t\twork = work_item->next;\n-\t\twork_item->next = NULL;\n+\twhile ((commit = commit_queue_get(&queue)) != NULL) {\n+\t\tstruct commit_list *parents;\n \n-\t\tcommit = work_item->item;\n \t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n@@ -582,27 +601,20 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \t\t\t * when all their children have been emitted thereby\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n-\t\t\tif (--(*pi) == 1) {\n-\t\t\t\tswitch (sort_order) {\n-\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n-\t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\t\tbreak;\n-\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n-\t\t\t\t\tcommit_list_insert(parent, &work);\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t}\n+\t\t\tif (--(*pi) == 1)\n+\t\t\t\tcommit_queue_put(&queue, parent);\n \t\t}\n \t\t/*\n-\t\t * work_item is a commit all of whose children\n-\t\t * have already been emitted. we can emit it now.\n+\t\t * all children of commit have already been\n+\t\t * emitted. we can emit it now.\n \t\t */\n \t\t*(indegree_slab_at(&indegree, commit)) = 0;\n-\t\t*pptr = work_item;\n-\t\tpptr = &work_item->next;\n+\n+\t\tpptr = &commit_list_insert(commit, pptr)->next;\n \t}\n \n \tclear_indegree_slab(&indegree);\n+\tclear_commit_queue(&queue);\n }\n \n /* merge-base stuff */\n-- \n1.8.3-451-gb703ddf\n"},{"id":"219597","messageId":"CAPig+cQnQv-Df52dptTDYfNFSzEUv_Db4rrddB2jQv9NhfLhbw@mail.gmail.com","threadId":"34028","inReplyTo":"1370581872-31580-2-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 1/3] toposort: rename \"lifo\" field","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-06-07T05:18:12Z","receivedAt":"2013-06-07T05:18:12Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Jun 7, 2013 at 1:11 AM, Junio C Hamano wrote:\n> The primary invariant of sort_in_topological_order() is to emit all\n> children before their parent is emitted. When traversing a forked\n\ns/parent is/parents are/\n\n> history like this with \"git log C E\":\n>\n> A----B----C\n> \\\n> D----E\n>\n> we ensure that A is emitted after all of B, C, D, and E are done, B\n> has to wait until C is done, and D has to wait until E is done.\n>\n> In some applications, however, we would further want to control how\n> these child commits B, C, D and E on two parallel ancestry chains\n> are shown. Most of the time, we would want to see C and B emitted\n> together, and then E and D, and finally A, which is the default\n> behaviour for --topo-order output.\n>\n> The \"lifo\" parameter of the sort_in_topological_order() function is\n> used to implement this behaviour. After inspecting C, we notice and\n> record that B needs to be inspected, and by structuring the \"work to\n> be done\" set as a LIFO stack, we ensure that B is inspected next,\n> before other in-flight commits we had known that we will need to\n> inspect, e.g. E, that may have already been sitting in the \"work to\n> be done\" set.\n>\n> When showing in --date-order, we would want to see commits ordered\n> by timestamps, i.e. show C, E, B and D in this order before showing\n> A, possibly mixing commits from two parallel histories together.\n> When \"lifo\" parameter is set to false, the function keeps the \"work\n> to be done\" set sorted in the date order to realize this semantics.\n>\n> But the name \"lifo\" is too tied to the way how the function implements\n> its behaviour, and does not describe _what_ the desired semantics is.\n>\n> Replace the \"lifo\" field with an enum rev_sort_order, with two\n> possible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE.\n>\n> The mechanical replacement rule is:\n>\n> \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n> \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n>\n> Signed-off-by: Junio C Hamano \n"},{"id":"219598","messageId":"7vy5amv6lr.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"CAPig+cQnQv-Df52dptTDYfNFSzEUv_Db4rrddB2jQv9NhfLhbw@mail.gmail.com","subject":"Re: [PATCH 1/3] toposort: rename \"lifo\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-07T05:21:20Z","receivedAt":"2013-06-07T05:21:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Sunshine writes:\n\n> On Fri, Jun 7, 2013 at 1:11 AM, Junio C Hamano wrote:\n>> The primary invariant of sort_in_topological_order() is to emit all\n>> children before their parent is emitted. When traversing a forked\n>\n> s/parent is/parents are/\n\nHmm, not quite. The above refers to:\n\n B\n /\n A---C\n \\\n D\n\nwhere A is the parent, B, C and D are all its children. We want to\nemit all children (B, C and D) before their parent A _is_ emitted.\n"},{"id":"219599","messageId":"CAPig+cQetpnYWv6OZnYfK9-gz2L86KdCFvBS7GfEE3dxN9-Qvw@mail.gmail.com","threadId":"34028","inReplyTo":"1370581872-31580-3-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 2/3] commit-queue: LIFO or priority queue of commits","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-06-07T05:29:34Z","receivedAt":"2013-06-07T05:29:34Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Jun 7, 2013 at 1:11 AM, Junio C Hamano wrote:\n> Traditionally we used a singly linked list of commits to hold a set\n> of in-flight commits while traversing history. The most typical use\n> of the list is to insert commit that is newly discovered in it, keep\n\ns/commit/a commit/\n\nAlso, \"in it\" is perhaps implied by \"insert\", so s/in it// may be appropriate.\n\n> it sorted by commit timestamp, pick up the newest one from the list,\n> and keep digging. The cost of keeping the singly linked list sorted\n> is nontrivial, and this typical use pattern better matches a priority\n> queue.\n>\n> Introduce a commit-queue structure, that can be used either as a\n> LIFO stack, or a priority queue. This will be used in the next\n> patch to hold in-flight commits during sort-in-topological-order.\n>\n> Signed-off-by: Junio C Hamano \n"},{"id":"220207","messageId":"1370820277-30158-1-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370581872-31580-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 0/4] log --author-date-order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-09T23:24:33Z","receivedAt":"2013-06-09T23:24:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Not much changed in the first three patches since the edition from\nlast week. A clean-up to clarify the toposort API, introduction of\npriority queue API, and then its use in topological sort logic.\n\nThe final patch adds \"log --author-date-order\" to build on top of\nthem.\n\nAdding tests to t4202 and/or t6012 is left as an exercise to readers.\n\nJunio C Hamano (4):\n toposort: rename \"lifo\" field\n commit-queue: LIFO or priority queue of commits\n sort-in-topological-order: use commit-queue\n log: --author-date-order\n\n Documentation/rev-list-options.txt | 4 ++\n Makefile | 2 +\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 ++--\n commit-queue.c | 84 ++++++++++++++++++++++++\n commit-queue.h | 34 ++++++++++\n commit.c | 129 +++++++++++++++++++++++++++++--------\n commit.h | 15 ++++-\n revision.c | 13 ++--\n revision.h | 6 +-\n 10 files changed, 260 insertions(+), 43 deletions(-)\n create mode 100644 commit-queue.c\n create mode 100644 commit-queue.h\n\n-- \n1.8.3-451-gb703ddf\n"},{"id":"220208","messageId":"1370820277-30158-2-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370820277-30158-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 1/4] toposort: rename \"lifo\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-09T23:24:34Z","receivedAt":"2013-06-09T23:24:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The primary invariant of sort_in_topological_order() is that a\nparent commit is not emitted untile all children of it are. When\ntraversing a forked history like this with \"git log C E\":\n\n A----B----C\n \\\n D----E\n\nwe ensure that A is emitted after all of B, C, D, and E are done, B\nhas to wait until C is done, and D has to wait until E is done.\n\nIn some applications, however, we would further want to control how\nthese child commits B, C, D and E on two parallel ancestry chains\nare shown.\n\nMost of the time, we would want to see C and B emitted together, and\nthen E and D, and finally A (i.e. the --topo-order output). The\n\"lifo\" parameter of the sort_in_topological_order() function is used\nto control this behaviour. We start the traversal by knowing two\ncommits, C and E. While keeping in mind that we also need to\ninspect E later, we pick C first to inspect, and we notice and\nrecord that B needs to be inspected. By structuring the \"work to be\ndone\" set as a LIFO stack, we ensure that B is inspected next,\nbefore other in-flight commits we had known that we will need to\ninspect, e.g. E.\n\nWhen showing in --date-order, we would want to see commits ordered\nby timestamps, i.e. show C, E, B and D in this order before showing\nA, possibly mixing commits from two parallel histories together.\nWhen \"lifo\" parameter is set to false, the function keeps the \"work\nto be done\" set sorted in the date order to realize this semantics.\nAfter inspecting C, we add B to the \"work to be done\" set, but the\nnext commit we inspect from the set is E which is newer than B.\n\nThe name \"lifo\", however, is too strongly tied to the way how the\nfunction implements its behaviour, and does not describe what the\nbehaviour _means_.\n\nReplace this field with an enum rev_sort_order, with two possible\nvalues: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and\nupdate the existing code. The mechanical replacement rule is:\n\n \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n\nSigned-off-by: Junio C Hamano \n---\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 ++++++++------\n commit.c | 12 ++++++++----\n commit.h | 14 +++++++++++---\n revision.c | 10 +++++-----\n revision.h | 6 +++++-\n 6 files changed, 38 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 8f0b2e8..8d26042 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -205,7 +205,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n \tint i = revs->early_output;\n \tint show_header = 1;\n \n-\tsort_in_topological_order(&list, revs->lifo);\n+\tsort_in_topological_order(&list, revs->sort_order);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex d208fd6..7c57985 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -631,7 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \tint num_rev, i, extra = 0;\n \tint all_heads = 0, all_remotes = 0;\n \tint all_mask, all_revs;\n-\tint lifo = 1;\n+\tenum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;\n \tchar head[128];\n \tconst char *head_p;\n \tint head_len;\n@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\t\t N_(\"show possible merge bases\")),\n \t\tOPT_BOOLEAN(0, \"independent\", &independent,\n \t\t\t N_(\"show refs unreachable from any other ref\")),\n-\t\tOPT_BOOLEAN(0, \"topo-order\", &lifo,\n-\t\t\t N_(\"show commits in topological order\")),\n+\t\tOPT_SET_INT(0, \"topo-order\", &sort_order,\n+\t\t\t N_(\"show commits in topological order\"),\n+\t\t\t REV_SORT_IN_GRAPH_ORDER),\n \t\tOPT_BOOLEAN(0, \"topics\", &topics,\n \t\t\t N_(\"show only commits not on the first branch\")),\n \t\tOPT_SET_INT(0, \"sparse\", &dense,\n \t\t\t N_(\"show merges reachable from only one tip\"), 0),\n-\t\tOPT_SET_INT(0, \"date-order\", &lifo,\n+\t\tOPT_SET_INT(0, \"date-order\", &sort_order,\n \t\t\t N_(\"show commits where no parent comes before its \"\n-\t\t\t \"children\"), 0),\n+\t\t\t \"children\"),\n+\t\t\t REV_SORT_BY_COMMIT_DATE),\n \t\t{ OPTION_CALLBACK, 'g', \"reflog\", &reflog_base, N_(\"[,]\"),\n \t\t\t N_(\"show most recent ref-log entries starting at \"\n \t\t\t \"base\"),\n@@ -901,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\texit(0);\n \n \t/* Sort topologically */\n-\tsort_in_topological_order(&seen, lifo);\n+\tsort_in_topological_order(&seen, sort_order);\n \n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\ndiff --git a/commit.c b/commit.c\nindex f97456d..11b9635 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -512,7 +512,7 @@ define_commit_slab(indegree_slab, int);\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo)\n+void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n@@ -561,7 +561,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t}\n \n \t/* process the list in topological order */\n-\tif (!lifo)\n+\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n \t\tcommit_list_sort_by_date(&work);\n \n \tpptr = list;\n@@ -588,10 +588,14 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n \t\t\tif (--(*pi) == 1) {\n-\t\t\t\tif (!lifo)\n+\t\t\t\tswitch (sort_order) {\n+\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n \t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\telse\n+\t\t\t\t\tbreak;\n+\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t\t/*\ndiff --git a/commit.h b/commit.h\nindex 70e749d..247e474 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -139,15 +139,23 @@ struct commit *pop_commit(struct commit_list **stack);\n void clear_commit_marks(struct commit *commit, unsigned int mark);\n void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n \n+\n+enum rev_sort_order {\n+\tREV_SORT_IN_GRAPH_ORDER = 0,\n+\tREV_SORT_BY_COMMIT_DATE\n+};\n+\n /*\n * Performs an in-place topological sort of list supplied.\n *\n * invariant of resulting list is:\n * a reachable from b => ord(b) < ord(a)\n- * in addition, when lifo == 0, commits on parallel tracks are\n- * sorted in the dates order.\n+ * sort_order further specifies:\n+ * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\n+ * chain together.\n+ * REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo);\n+void sort_in_topological_order(struct commit_list **, enum rev_sort_order);\n \n struct commit_graft {\n \tunsigned char sha1[20];\ndiff --git a/revision.c b/revision.c\nindex cf620c6..966ebbc 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1038,7 +1038,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \tDIFF_OPT_SET(&revs->pruning, QUICK);\n \trevs->pruning.add_remove = file_add_remove;\n \trevs->pruning.change = file_change;\n-\trevs->lifo = 1;\n+\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \trevs->dense = 1;\n \trevs->prefix = prefix;\n \trevs->max_age = -1;\n@@ -1373,7 +1373,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--merge\")) {\n \t\trevs->show_merge = 1;\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n-\t\trevs->lifo = 1;\n+\t\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \t\trevs->topo_order = 1;\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n@@ -1391,7 +1391,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->prune = 1;\n \t\tload_ref_decorations(DECORATE_SHORT_REFS);\n \t} else if (!strcmp(arg, \"--date-order\")) {\n-\t\trevs->lifo = 0;\n+\t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n@@ -2165,7 +2165,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n-\t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n \tif (revs->children.name)\n@@ -2480,7 +2480,7 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \t * If revs->topo_order is set, sort the boundary commits\n \t * in topological order\n \t */\n-\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tsort_in_topological_order(&revs->commits, revs->sort_order);\n }\n \n static struct commit *get_revision_internal(struct rev_info *revs)\ndiff --git a/revision.h b/revision.h\nindex 5da09ee..2a5e325 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"grep.h\"\n #include \"notes.h\"\n+#include \"commit.h\"\n \n #define SEEN\t\t(1u<<0)\n #define UNINTERESTING (1u<<1)\n@@ -60,6 +61,10 @@ struct rev_info {\n \tconst char *prefix;\n \tconst char *def;\n \tstruct pathspec prune_data;\n+\n+\t/* topo-sort */\n+\tenum rev_sort_order sort_order;\n+\n \tunsigned int\tearly_output:1,\n \t\t\tignore_missing:1;\n \n@@ -70,7 +75,6 @@ struct rev_info {\n \t\t\tshow_all:1,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n-\t\t\tlifo:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\n \t\t\tsimplify_by_decoration:1,\n-- \n1.8.3-451-gb703ddf\n"},{"id":"220209","messageId":"1370820277-30158-3-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370820277-30158-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-09T23:24:35Z","receivedAt":"2013-06-09T23:24:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Traditionally we used a singly linked list of commits to hold a set\nof in-flight commits while traversing history. The most typical use\nof the list is to add commits that are newly discovered to it, keep\nthe list sorted by commit timestamp, pick up the newest one from the\nlist, and keep digging. The cost of keeping the singly linked list\nsorted is nontrivial, and this typical use pattern better matches a\npriority queue.\n\nIntroduce a commit-queue structure, that can be used either as a\nLIFO stack, or a priority queue. This will be used in the next\npatch to hold in-flight commits during sort-in-topological-order.\n\nSigned-off-by: Junio C Hamano \n---\n Makefile | 2 ++\n commit-queue.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit-queue.h | 31 +++++++++++++++++++++++++\n 3 files changed, 104 insertions(+)\n create mode 100644 commit-queue.c\n create mode 100644 commit-queue.h\n\ndiff --git a/Makefile b/Makefile\nindex 598d631..3cf55e9 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -634,6 +634,7 @@ LIB_H += cache.h\n LIB_H += color.h\n LIB_H += column.h\n LIB_H += commit.h\n+LIB_H += commit-queue.h\n LIB_H += compat/bswap.h\n LIB_H += compat/cygwin.h\n LIB_H += compat/mingw.h\n@@ -757,6 +758,7 @@ LIB_OBJS += color.o\n LIB_OBJS += column.o\n LIB_OBJS += combine-diff.o\n LIB_OBJS += commit.o\n+LIB_OBJS += commit-queue.o\n LIB_OBJS += compat/obstack.o\n LIB_OBJS += compat/terminal.o\n LIB_OBJS += config.o\ndiff --git a/commit-queue.c b/commit-queue.c\nnew file mode 100644\nindex 0000000..77d4b02\n--- /dev/null\n+++ b/commit-queue.c\n@@ -0,0 +1,71 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"commit-queue.h\"\n+\n+void clear_commit_queue(struct commit_queue *queue)\n+{\n+\tfree(queue->array);\n+\tqueue->nr = 0;\n+\tqueue->alloc = 0;\n+\tqueue->array = NULL;\n+}\n+\n+void commit_queue_put(struct commit_queue *queue, struct commit *commit)\n+{\n+\tcommit_compare_fn compare = queue->compare;\n+\tint ix, parent;\n+\n+\t/* Append at the end */\n+\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n+\tqueue->array[queue->nr++] = commit;\n+\tif (!compare)\n+\t\treturn; /* LIFO */\n+\n+\t/* Bubble up the new one */\n+\tfor (ix = queue->nr - 1; ix; ix = parent) {\n+\t\tparent = (ix - 1) / 2;\n+\t\tif (compare(queue->array[parent], queue->array[ix],\n+\t\t\t queue->cb_data) < 0)\n+\t\t\tbreak;\n+\n+\t\tcommit = queue->array[parent];\n+\t\tqueue->array[parent] = queue->array[ix];\n+\t\tqueue->array[ix] = commit;\n+\t}\n+}\n+\n+struct commit *commit_queue_get(struct commit_queue *queue)\n+{\n+\tstruct commit *result, *swap;\n+\tint ix, child;\n+\tcommit_compare_fn compare = queue->compare;\n+\n+\tif (!queue->nr)\n+\t\treturn NULL;\n+\tif (!compare)\n+\t\treturn queue->array[--queue->nr]; /* LIFO */\n+\n+\tresult = queue->array[0];\n+\tif (!--queue->nr)\n+\t\treturn result;\n+\n+\tqueue->array[0] = queue->array[queue->nr];\n+\n+\t/* Push down the one at the root */\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\t\tchild = ix * 2 + 1; /* left */\n+\t\tif ((child + 1 < queue->nr) &&\n+\t\t (compare(queue->array[child], queue->array[child + 1],\n+\t\t\t queue->cb_data) >= 0))\n+\t\t\tchild++; /* use right child */\n+\n+\t\tif (compare(queue->array[ix], queue->array[child],\n+\t\t\t queue->cb_data) < 0)\n+\t\t\tbreak;\n+\n+\t\tswap = queue->array[child];\n+\t\tqueue->array[child] = queue->array[ix];\n+\t\tqueue->array[ix] = swap;\n+\t}\n+\treturn result;\n+}\ndiff --git a/commit-queue.h b/commit-queue.h\nnew file mode 100644\nindex 0000000..7c5dc4c\n--- /dev/null\n+++ b/commit-queue.h\n@@ -0,0 +1,31 @@\n+#ifndef COMMIT_QUEUE_H\n+#define COMMIT_QUEUE_H\n+\n+/*\n+ * Compare two commits; the third parameter is cb_data in the\n+ * commit_queue structure.\n+ */\n+typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);\n+\n+struct commit_queue {\n+\tcommit_compare_fn compare;\n+\tvoid *cb_data;\n+\tint alloc, nr;\n+\tstruct commit **array;\n+};\n+\n+/*\n+ * Add the commit to the queue\n+ */\n+extern void commit_queue_put(struct commit_queue *, struct commit *);\n+\n+/*\n+ * Extract the commit that compares the smallest out of the queue,\n+ * or NULL. If compare function is NULL, the queue acts as a LIFO\n+ * stack.\n+ */\n+extern struct commit *commit_queue_get(struct commit_queue *);\n+\n+extern void clear_commit_queue(struct commit_queue *);\n+\n+#endif /* COMMIT_QUEUE_H */\n-- \n1.8.3-451-gb703ddf\n"},{"id":"220210","messageId":"1370820277-30158-4-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370820277-30158-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 3/4] sort-in-topological-order: use commit-queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-09T23:24:36Z","receivedAt":"2013-06-09T23:24:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Use the commit-queue data structure to implement a priority queue\nof commits sorted by committer date, when handling --date-order.\nThe commit-queue structure can also be used as a simple LIFO stack,\nwhich is a good match for --topo-order processing.\n\nSigned-off-by: Junio C Hamano \n---\n commit-queue.c | 13 +++++++++++\n commit-queue.h | 3 +++\n commit.c | 74 ++++++++++++++++++++++++++++++++++------------------------\n 3 files changed, 59 insertions(+), 31 deletions(-)\n\ndiff --git a/commit-queue.c b/commit-queue.c\nindex 77d4b02..ffffc4e 100644\n--- a/commit-queue.c\n+++ b/commit-queue.c\n@@ -2,6 +2,19 @@\n #include \"commit.h\"\n #include \"commit-queue.h\"\n \n+void commit_queue_reverse(struct commit_queue *queue)\n+{\n+\tint i, j;\n+\n+\tif (queue->compare != NULL)\n+\t\tdie(\"BUG: commit_queue_reverse() on non-LIFO queue\");\n+\tfor (i = 0; i <= (j = (queue->nr - 1) - i); i++) {\n+\t\tstruct commit *swap = queue->array[i];\n+\t\tqueue->array[i] = queue->array[j];\n+\t\tqueue->array[j] = swap;\n+\t}\n+}\n+\n void clear_commit_queue(struct commit_queue *queue)\n {\n \tfree(queue->array);\ndiff --git a/commit-queue.h b/commit-queue.h\nindex 7c5dc4c..d3c92e5 100644\n--- a/commit-queue.h\n+++ b/commit-queue.h\n@@ -28,4 +28,7 @@ extern struct commit *commit_queue_get(struct commit_queue *);\n \n extern void clear_commit_queue(struct commit_queue *);\n \n+/* Reverse the LIFO elements */\n+extern void commit_queue_reverse(struct commit_queue *);\n+\n #endif /* COMMIT_QUEUE_H */\ndiff --git a/commit.c b/commit.c\nindex 11b9635..cc6d385 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -9,6 +9,7 @@\n #include \"gpg-interface.h\"\n #include \"mergesort.h\"\n #include \"commit-slab.h\"\n+#include \"commit-queue.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -509,21 +510,41 @@ struct commit *pop_commit(struct commit_list **stack)\n /* count number of children that have not been emitted */\n define_commit_slab(indegree_slab, int);\n \n+static int compare_commits_by_commit_date(struct commit *a, struct commit *b, void *unused)\n+{\n+\t/* newer commits with larger date first */\n+\tif (a->date < b->date)\n+\t\treturn 1;\n+\telse if (a->date > b->date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n+void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n-\tstruct commit_list *work, **insert;\n \tstruct commit_list **pptr;\n \tstruct indegree_slab indegree;\n+\tstruct commit_queue queue;\n+\tstruct commit *commit;\n \n \tif (!orig)\n \t\treturn;\n \t*list = NULL;\n \n \tinit_indegree_slab(&indegree);\n+\tmemset(&queue, '\\0', sizeof(queue));\n+\tswitch (sort_order) {\n+\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n+\t\tqueue.compare = NULL;\n+\t\tbreak;\n+\tcase REV_SORT_BY_COMMIT_DATE:\n+\t\tqueue.compare = compare_commits_by_commit_date;\n+\t\tbreak;\n+\t}\n \n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n@@ -533,7 +554,7 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \n \t/* update the indegree */\n \tfor (next = orig; next; next = next->next) {\n-\t\tstruct commit_list * parents = next->item->parents;\n+\t\tstruct commit_list *parents = next->item->parents;\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n@@ -551,30 +572,28 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \t *\n \t * the tips serve as a starting set for the work queue.\n \t */\n-\twork = NULL;\n-\tinsert = &work;\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \n \t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n-\t\t\tinsert = &commit_list_insert(commit, insert)->next;\n+\t\t\tcommit_queue_put(&queue, commit);\n \t}\n \n-\t/* process the list in topological order */\n-\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n-\t\tcommit_list_sort_by_date(&work);\n+\t/*\n+\t * This is unfortunate; the initial tips need to be shown\n+\t * in the order given from the revision traversal machinery.\n+\t */\n+\tif (sort_order == REV_SORT_IN_GRAPH_ORDER)\n+\t\tcommit_queue_reverse(&queue);\n+\n+\t/* We no longer need the commit list */\n+\tfree_commit_list(orig);\n \n \tpptr = list;\n \t*list = NULL;\n-\twhile (work) {\n-\t\tstruct commit *commit;\n-\t\tstruct commit_list *parents, *work_item;\n-\n-\t\twork_item = work;\n-\t\twork = work_item->next;\n-\t\twork_item->next = NULL;\n+\twhile ((commit = commit_queue_get(&queue)) != NULL) {\n+\t\tstruct commit_list *parents;\n \n-\t\tcommit = work_item->item;\n \t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n@@ -587,27 +606,20 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \t\t\t * when all their children have been emitted thereby\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n-\t\t\tif (--(*pi) == 1) {\n-\t\t\t\tswitch (sort_order) {\n-\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n-\t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\t\tbreak;\n-\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n-\t\t\t\t\tcommit_list_insert(parent, &work);\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t}\n+\t\t\tif (--(*pi) == 1)\n+\t\t\t\tcommit_queue_put(&queue, parent);\n \t\t}\n \t\t/*\n-\t\t * work_item is a commit all of whose children\n-\t\t * have already been emitted. we can emit it now.\n+\t\t * all children of commit have already been\n+\t\t * emitted. we can emit it now.\n \t\t */\n \t\t*(indegree_slab_at(&indegree, commit)) = 0;\n-\t\t*pptr = work_item;\n-\t\tpptr = &work_item->next;\n+\n+\t\tpptr = &commit_list_insert(commit, pptr)->next;\n \t}\n \n \tclear_indegree_slab(&indegree);\n+\tclear_commit_queue(&queue);\n }\n \n /* merge-base stuff */\n-- \n1.8.3-451-gb703ddf\n"},{"id":"220211","messageId":"1370820277-30158-5-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370820277-30158-1-git-send-email-gitster@pobox.com","subject":"[PATCH v2 4/4] log: --author-date-order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-09T23:24:37Z","receivedAt":"2013-06-09T23:24:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sometimes people would want to view the commits in parallel\nhistories in the order of author dates, not committer dates.\n\nTeach \"topo-order\" sort machinery to do so, using a commit-info slab\nto record the author dates of each commit, and commit-queue to sort\nthem.\n\nSigned-off-by: Junio C Hamano \n---\n Documentation/rev-list-options.txt | 4 +++\n commit.c | 59 ++++++++++++++++++++++++++++++++++++++\n commit.h | 3 +-\n revision.c | 3 ++\n 4 files changed, 68 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 3bdbf5e..8302402 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -617,6 +617,10 @@ By default, the commits are shown in reverse chronological order.\n \tShow no parents before all of its children are shown, but\n \totherwise show commits in the commit timestamp order.\n \n+--author-date-order::\n+\tShow no parents before all of its children are shown, but\n+\totherwise show commits in the author timestamp order.\n+\n --topo-order::\n \tShow no parents before all of its children are shown, and\n \tavoid showing commits on multiple lines of history\ndiff --git a/commit.c b/commit.c\nindex cc6d385..f3a2f09 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -510,6 +510,53 @@ struct commit *pop_commit(struct commit_list **stack)\n /* count number of children that have not been emitted */\n define_commit_slab(indegree_slab, int);\n \n+/* record author-date for each commit object */\n+define_commit_slab(author_date_slab, unsigned long);\n+\n+static void record_author_date(struct author_date_slab *author_date,\n+\t\t\t struct commit *commit)\n+{\n+\tconst char *buf, *line_end;\n+\tstruct ident_split ident;\n+\tchar *date_end;\n+\tunsigned long date;\n+\n+\tfor (buf = commit->buffer; buf; buf = line_end + 1) {\n+\t\tline_end = strchrnul(buf, '\\n');\n+\t\tif (prefixcmp(buf, \"author \")) {\n+\t\t\tif (!line_end[0] || line_end[1] == '\\n')\n+\t\t\t\treturn; /* end of header */\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (split_ident_line(&ident,\n+\t\t\t\t buf + strlen(\"author \"),\n+\t\t\t\t line_end - (buf + strlen(\"author \"))) ||\n+\t\t !ident.date_begin || !ident.date_end)\n+\t\t\treturn; /* malformed \"author\" line */\n+\t\tbreak;\n+\t}\n+\n+\tdate = strtoul(ident.date_begin, &date_end, 10);\n+\tif (date_end != ident.date_end)\n+\t\treturn; /* malformed date */\n+\t*(author_date_slab_at(author_date, commit)) = date;\n+}\n+\n+static int compare_commits_by_author_date(struct commit *a, struct commit *b,\n+\t\t\t\t\t void *cb_data)\n+{\n+\tstruct author_date_slab *author_date = cb_data;\n+\tunsigned long a_date = *(author_date_slab_at(author_date, a));\n+\tunsigned long b_date = *(author_date_slab_at(author_date, b));\n+\n+\t/* newer commits with larger date first */\n+\tif (a_date < b_date)\n+\t\treturn 1;\n+\telse if (a_date > b_date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n static int compare_commits_by_commit_date(struct commit *a, struct commit *b, void *unused)\n {\n \t/* newer commits with larger date first */\n@@ -530,6 +577,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tstruct indegree_slab indegree;\n \tstruct commit_queue queue;\n \tstruct commit *commit;\n+\tstruct author_date_slab author_date;\n \n \tif (!orig)\n \t\treturn;\n@@ -537,6 +585,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \n \tinit_indegree_slab(&indegree);\n \tmemset(&queue, '\\0', sizeof(queue));\n+\n \tswitch (sort_order) {\n \tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\tqueue.compare = NULL;\n@@ -544,12 +593,20 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tcase REV_SORT_BY_COMMIT_DATE:\n \t\tqueue.compare = compare_commits_by_commit_date;\n \t\tbreak;\n+\tcase REV_SORT_BY_AUTHOR_DATE:\n+\t\tinit_author_date_slab(&author_date);\n+\t\tqueue.compare = compare_commits_by_author_date;\n+\t\tqueue.cb_data = &author_date;\n+\t\tbreak;\n \t}\n \n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \t\t*(indegree_slab_at(&indegree, commit)) = 1;\n+\t\t/* also record the author dates, if needed */\n+\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n+\t\t\trecord_author_date(&author_date, commit);\n \t}\n \n \t/* update the indegree */\n@@ -620,6 +677,8 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \n \tclear_indegree_slab(&indegree);\n \tclear_commit_queue(&queue);\n+\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n+\t\tclear_author_date_slab(&author_date);\n }\n \n /* merge-base stuff */\ndiff --git a/commit.h b/commit.h\nindex 247e474..e43dfd0 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -142,7 +142,8 @@ void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n \n enum rev_sort_order {\n \tREV_SORT_IN_GRAPH_ORDER = 0,\n-\tREV_SORT_BY_COMMIT_DATE\n+\tREV_SORT_BY_COMMIT_DATE,\n+\tREV_SORT_BY_AUTHOR_DATE\n };\n \n /*\ndiff --git a/revision.c b/revision.c\nindex 966ebbc..12d9b64 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1393,6 +1393,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--author-date-order\")) {\n+\t\trevs->sort_order = REV_SORT_BY_AUTHOR_DATE;\n+\t\trevs->topo_order = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n \t\tswitch (arg[14]) {\n-- \n1.8.3-451-gb703ddf\n"},{"id":"220214","messageId":"7vehcan9e0.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"1370820277-30158-4-git-send-email-gitster@pobox.com","subject":"Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-09T23:37:27Z","receivedAt":"2013-06-09T23:37:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Use the commit-queue data structure to implement a priority queue\n> of commits sorted by committer date, when handling --date-order.\n> The commit-queue structure can also be used as a simple LIFO stack,\n> which is a good match for --topo-order processing.\n>\n> Signed-off-by: Junio C Hamano \n> ---\n> commit-queue.c | 13 +++++++++++\n> commit-queue.h | 3 +++\n> commit.c | 74 ++++++++++++++++++++++++++++++++++------------------------\n> 3 files changed, 59 insertions(+), 31 deletions(-)\n\nPeff, I think you were the one who did a priority queue previously,\nprimarily for performance. The primary reason for this round was so\nthat I didn't have to touch the revision.c and struct commit in\norder to sort by keys in commit-info-slabs and I was not aiming for\nperformance but a quick and rough benchmarking seems to indicate\nthat\n\n - for a small repository like git.git, there is not much difference\n in runtime;\n\n - but it does seem to cut down the memory pressure (less minor\n faults).\n\nRepresentative runs of \"rev-list --date-order v0.99..v1.8.3\" on my\nbox with 'master' and with these patches spend 0.47user/0.04system\nwith 0.50elapsed (no time change), with 13450 vs 13108 minor faults\n(smaller memory use).\n"},{"id":"220230","messageId":"CAPig+cQg11r=87kExamD=9C5bM5DMHScY7U=g4v+y+o+skbUEw@mail.gmail.com","threadId":"34028","inReplyTo":"1370820277-30158-2-git-send-email-gitster@pobox.com","subject":"Re: [PATCH v2 1/4] toposort: rename \"lifo\" field","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-06-10T02:12:47Z","receivedAt":"2013-06-10T02:12:47Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sun, Jun 9, 2013 at 7:24 PM, Junio C Hamano wrote:\n> The primary invariant of sort_in_topological_order() is that a\n> parent commit is not emitted untile all children of it are. When\n\ns/untile/until/\n\n> traversing a forked history like this with \"git log C E\":\n>\n> A----B----C\n> \\\n> D----E\n>\n> we ensure that A is emitted after all of B, C, D, and E are done, B\n> has to wait until C is done, and D has to wait until E is done.\n>\n> In some applications, however, we would further want to control how\n> these child commits B, C, D and E on two parallel ancestry chains\n> are shown.\n>\n> Most of the time, we would want to see C and B emitted together, and\n> then E and D, and finally A (i.e. the --topo-order output). The\n> \"lifo\" parameter of the sort_in_topological_order() function is used\n> to control this behaviour. We start the traversal by knowing two\n> commits, C and E. While keeping in mind that we also need to\n> inspect E later, we pick C first to inspect, and we notice and\n> record that B needs to be inspected. By structuring the \"work to be\n> done\" set as a LIFO stack, we ensure that B is inspected next,\n> before other in-flight commits we had known that we will need to\n> inspect, e.g. E.\n>\n> When showing in --date-order, we would want to see commits ordered\n> by timestamps, i.e. show C, E, B and D in this order before showing\n> A, possibly mixing commits from two parallel histories together.\n> When \"lifo\" parameter is set to false, the function keeps the \"work\n> to be done\" set sorted in the date order to realize this semantics.\n> After inspecting C, we add B to the \"work to be done\" set, but the\n> next commit we inspect from the set is E which is newer than B.\n>\n> The name \"lifo\", however, is too strongly tied to the way how the\n\ns/the way//\n\n> function implements its behaviour, and does not describe what the\n> behaviour _means_.\n>\n> Replace this field with an enum rev_sort_order, with two possible\n> values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and\n> update the existing code. The mechanical replacement rule is:\n>\n> \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n> \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n>\n> Signed-off-by: Junio C Hamano \n"},{"id":"220232","messageId":"20130610050526.GC3621@sigill.intra.peff.net","threadId":"34028","inReplyTo":"1370820277-30158-2-git-send-email-gitster@pobox.com","subject":"Re: [PATCH v2 1/4] toposort: rename \"lifo\" field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T05:05:26Z","receivedAt":"2013-06-10T05:05:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 09, 2013 at 04:24:34PM -0700, Junio C Hamano wrote:\n\n> The name \"lifo\", however, is too strongly tied to the way how the\n> function implements its behaviour, and does not describe what the\n> behaviour _means_.\n> \n> Replace this field with an enum rev_sort_order, with two possible\n> values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and\n> update the existing code. The mechanical replacement rule is:\n> \n> \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n> \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n\nThanks. Having looked at this code for the first time in a long time\nrecently, I was very confused by the purpose of the \"lifo\" flag; this\npatch would have made it much clearer.\n\nPatch itself looks fine to me.\n\n-Peff\n"},{"id":"220237","messageId":"20130610052500.GD3621@sigill.intra.peff.net","threadId":"34028","inReplyTo":"1370820277-30158-3-git-send-email-gitster@pobox.com","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T05:25:00Z","receivedAt":"2013-06-10T05:25:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 09, 2013 at 04:24:35PM -0700, Junio C Hamano wrote:\n\n> Traditionally we used a singly linked list of commits to hold a set\n> of in-flight commits while traversing history. The most typical use\n> of the list is to add commits that are newly discovered to it, keep\n> the list sorted by commit timestamp, pick up the newest one from the\n> list, and keep digging. The cost of keeping the singly linked list\n> sorted is nontrivial, and this typical use pattern better matches a\n> priority queue.\n> \n> Introduce a commit-queue structure, that can be used either as a\n> LIFO stack, or a priority queue. This will be used in the next\n> patch to hold in-flight commits during sort-in-topological-order.\n\nGreat. You may recall I had a similar patch or year or two back, in an\nattempt to fix some of the O(n^2) places (e.g., in fetch-pack's\nmark_complete). We ended up dropping it because duplicate removal kept\n\"n\" small enough for common cases, and most of the commit_list users\ndepend on doing cheap splicing and other linked-list operations.\n\nIt may be worth looking again for other places to use this over\ncommit_list, but even the caller you are introducing here justifies its\npresence.\n\nAlso, I wrote some basic tests to cover the priority queue as a unit. I\ncan rebase them on your commit if you are interested.\n\nA few comments on the code itself:\n\n> +void commit_queue_put(struct commit_queue *queue, struct commit *commit)\n\nIs it worth making this \"struct commit *\" a void pointer, and handling\narbitrary items in our priority queue? The compare function should be\nthe only thing that dereferences them.\n\nI do not have any non-commit priority queue use in mind, but I do not\nthink it adds any complexity in this case.\n\n> +\t/* Bubble up the new one */\n> +\tfor (ix = queue->nr - 1; ix; ix = parent) {\n> +\t\tparent = (ix - 1) / 2;\n> +\t\tif (compare(queue->array[parent], queue->array[ix],\n> +\t\t\t queue->cb_data) < 0)\n> +\t\t\tbreak;\n\nIn my implementation, I stopped on \"compare() <= 0\". It is late and my\nmind is fuzzy, but I recall that heaps are never stable with respect to\ninsertion order, so I don't think it would matter.\n\n-Peff\n"},{"id":"220238","messageId":"20130610053059.GE3621@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7vehcan9e0.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T05:31:00Z","receivedAt":"2013-06-10T05:31:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 09, 2013 at 04:37:27PM -0700, Junio C Hamano wrote:\n\n> Junio C Hamano writes:\n> \n> > Use the commit-queue data structure to implement a priority queue\n> > of commits sorted by committer date, when handling --date-order.\n> > The commit-queue structure can also be used as a simple LIFO stack,\n> > which is a good match for --topo-order processing.\n> >\n> > Signed-off-by: Junio C Hamano \n> > ---\n> > commit-queue.c | 13 +++++++++++\n> > commit-queue.h | 3 +++\n> > commit.c | 74 ++++++++++++++++++++++++++++++++++------------------------\n> > 3 files changed, 59 insertions(+), 31 deletions(-)\n> \n> Peff, I think you were the one who did a priority queue previously,\n> primarily for performance. The primary reason for this round was so\n> that I didn't have to touch the revision.c and struct commit in\n> order to sort by keys in commit-info-slabs and I was not aiming for\n> performance but a quick and rough benchmarking seems to indicate\n> that\n> \n> - for a small repository like git.git, there is not much difference\n> in runtime;\n> \n> - but it does seem to cut down the memory pressure (less minor\n> faults).\n> \n> Representative runs of \"rev-list --date-order v0.99..v1.8.3\" on my\n> box with 'master' and with these patches spend 0.47user/0.04system\n> with 0.50elapsed (no time change), with 13450 vs 13108 minor faults\n> (smaller memory use).\n\nThe performance enhancement of the priority queue came from replacing\n\"commit_list_insert_by_date\" calls with insertion into a queue. That\ndrops O(n^2) behavior on the linked-list down to O(n log n), as we have\n\"n\" insertions, each causing an O(log n) heapify operation.\n\nAround the same time, though, René wrote the linked-list merge sort that\npowers commit_list_sort_by_date. And topo-sort learned to do O(1)\ninsertions into the unsorted list, and then one O(n log n) sort.\n\nSo your results are exactly what I would expect: the time should be\nabout the same (due to the same complexity), but the memory is used more\ncompactly (array of pointers instead of linked list of pointers).\n\n-Peff\n"},{"id":"220241","messageId":"20130610055014.GF3621@sigill.intra.peff.net","threadId":"34028","inReplyTo":"1370820277-30158-5-git-send-email-gitster@pobox.com","subject":"Re: [PATCH v2 4/4] log: --author-date-order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T05:50:14Z","receivedAt":"2013-06-10T05:50:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 09, 2013 at 04:24:37PM -0700, Junio C Hamano wrote:\n\n> Sometimes people would want to view the commits in parallel\n> histories in the order of author dates, not committer dates.\n> \n> Teach \"topo-order\" sort machinery to do so, using a commit-info slab\n> to record the author dates of each commit, and commit-queue to sort\n> them.\n\nNice, this is basically what I was envisioning when I mentioned the\nslabs. However, I don't think the code works. :(\n\n> +static void record_author_date(struct author_date_slab *author_date,\n> +\t\t\t struct commit *commit)\n> +{\n> +\tconst char *buf, *line_end;\n> +\tstruct ident_split ident;\n> +\tchar *date_end;\n> +\tunsigned long date;\n> +\n> +\tfor (buf = commit->buffer; buf; buf = line_end + 1) {\n> +\t\tline_end = strchrnul(buf, '\\n');\n> +\t\tif (prefixcmp(buf, \"author \")) {\n> +\t\t\tif (!line_end[0] || line_end[1] == '\\n')\n> +\t\t\t\treturn; /* end of header */\n> +\t\t\tcontinue;\n> +\t\t}\n> +\t\tif (split_ident_line(&ident,\n> +\t\t\t\t buf + strlen(\"author \"),\n> +\t\t\t\t line_end - (buf + strlen(\"author \"))) ||\n> +\t\t !ident.date_begin || !ident.date_end)\n> +\t\t\treturn; /* malformed \"author\" line */\n> +\t\tbreak;\n> +\t}\n> +\n> +\tdate = strtoul(ident.date_begin, &date_end, 10);\n> +\tif (date_end != ident.date_end)\n> +\t\treturn; /* malformed date */\n> +\t*(author_date_slab_at(author_date, commit)) = date;\n> +}\n\nI'm not excited about introducing yet another place that parses commit\nobjects (mostly not for correctness, but because we have had\ninconsistency in how malformed objects are treated). It is at least\nusing split_ident_line which covers the hard bits. I wonder how much\nslower it would be to simply call format_commit_message to do the\nparsing.\n\n> \t/* Mark them and clear the indegree */\n> \tfor (next = orig; next; next = next->next) {\n> \t\tstruct commit *commit = next->item;\n> \t\t*(indegree_slab_at(&indegree, commit)) = 1;\n> +\t\t/* also record the author dates, if needed */\n> +\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> +\t\t\trecord_author_date(&author_date, commit);\n\nThe record_author_date function assumes that commit->buffer is valid\n(i.e., not NULL). We seem to assume that the commits are parsed already\n(for looking at parents, and at the committer date). But if\n\"save_commit_buffer\" is set to 0 (as it is for rev-list), we would not\nhave a buffer at all.\n\nIt's hard to notice the problem because a NULL buffer will cause\nrecord_author_date to simply leave the slab entry at 0. That would give\nthe same output as regular \"--topo-order\" (because everybody has the\nsame timestamp), except that the priority queue heap is not stable.\nWith this patch:\n\ndiff --git a/commit.c b/commit.c\nindex f3a2f09..5e62ae8 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -521,6 +521,9 @@ static void record_author_date(struct author_date_slab *author_date,\n \tchar *date_end;\n \tunsigned long date;\n \n+\tif (!commit->buffer)\n+\t\tdie(\"whooops!\");\n+\n \tfor (buf = commit->buffer; buf; buf = line_end + 1) {\n \t\tline_end = strchrnul(buf, '\\n');\n \t\tif (prefixcmp(buf, \"author \")) {\n\nyou can see the problem more clearly with \"git rev-list\n--author-date-order HEAD\".\n\n-Peff\n"},{"id":"220245","messageId":"7vwqq2l9cz.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130610052500.GD3621@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-10T07:21:00Z","receivedAt":"2013-06-10T07:21:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It may be worth looking again for other places to use this over\n> commit_list, but even the caller you are introducing here justifies its\n> presence.\n\nThe next candidate is paint-down-to-common, probably.\n\n> Also, I wrote some basic tests to cover the priority queue as a unit. I\n> can rebase them on your commit if you are interested.\n\nIt would be great.\n\n> A few comments on the code itself:\n>\n>> +void commit_queue_put(struct commit_queue *queue, struct commit *commit)\n>\n> Is it worth making this \"struct commit *\" a void pointer, and handling\n> arbitrary items in our priority queue? The compare function should be\n> the only thing that dereferences them.\n> \n> I do not have any non-commit priority queue use in mind, but I do not\n> think it adds any complexity in this case.\n\nI didn't either (and still I don't think of one), but I agree that\nthe implementation can be reused for pq of any type, as long as it\nis a pointer to struct.\n\n>> +\t/* Bubble up the new one */\n>> +\tfor (ix = queue->nr - 1; ix; ix = parent) {\n>> +\t\tparent = (ix - 1) / 2;\n>> +\t\tif (compare(queue->array[parent], queue->array[ix],\n>> +\t\t\t queue->cb_data) < 0)\n>> +\t\t\tbreak;\n>\n> In my implementation, I stopped on \"compare() <= 0\". It is late and my\n> mind is fuzzy, but I recall that heaps are never stable with respect to\n> insertion order, so I don't think it would matter.\n\nIt would matter in the sense that we cannot replace linked-list, if\nthe caller wants stability. It is more like \"we cannot do anything\nabout it\" than \"it would not matter\".\n\nWe can make each queue element a pair of , and tiebreak using the insertion order, if the\ncallers want the same stability as linked-list implementation, but\nI tend to think it really matters.\n"},{"id":"220246","messageId":"7vsj0ql924.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130610053059.GE3621@sigill.intra.peff.net","subject":"Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-10T07:27:31Z","receivedAt":"2013-06-10T07:27:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The performance enhancement of the priority queue came from replacing\n> \"commit_list_insert_by_date\" calls with insertion into a queue. That\n> drops O(n^2) behavior on the linked-list down to O(n log n), as we have\n> \"n\" insertions, each causing an O(log n) heapify operation.\n\nYes.\n\n> Around the same time, though, René wrote the linked-list merge sort that\n> powers commit_list_sort_by_date. And topo-sort learned to do O(1)\n> insertions into the unsorted list, and then one O(n log n) sort.\n\nYes, but that only affects the \"sort the work queue in date order\"\nbefore entering the main loop, and maintenance of work queue as we\ndig along still is \"find the place to put this in the date-order\nsorted linked list\", no?\n\n> So your results are exactly what I would expect: the time should be\n> about the same (due to the same complexity), but the memory is used more\n> compactly (array of pointers instead of linked list of pointers).\n\nI've been disturbed every time I saw the commit_list insertion\nfunction that does a small allocation which will be freed fairly\noften and have been wondering if we can rewrite it with custom slab\nallocator, but not using linked list where we do not have to feels\nlike a better solution to that issue, and use of pqueue may be a\nright direction to go in.\n"},{"id":"220248","messageId":"7vobbel8ib.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130610055014.GF3621@sigill.intra.peff.net","subject":"Re: [PATCH v2 4/4] log: --author-date-order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-10T07:39:24Z","receivedAt":"2013-06-10T07:39:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I'm not excited about introducing yet another place that parses commit\n> objects (mostly not for correctness, but because we have had\n> inconsistency in how malformed objects are treated). It is at least\n> using split_ident_line which covers the hard bits. I wonder how much\n> slower it would be to simply call format_commit_message to do the\n> parsing.\n\nThe thought certainly crossed my mind, not exactly in that form but\nmore about splitting the machinery used in pretty.c into a more\nreusable form.\n\nThe result of my attempt however did not become all that reusable\n(admittedly I didn't spend too much brain cycles on it), so I punted\n;-).\n\n> The record_author_date function assumes that commit->buffer is valid\n> (i.e., not NULL). We seem to assume that the commits are parsed already\n> (for looking at parents, and at the committer date). \n\nI thought that the latter is warranted, as the function worked on\nthe output of limit_list(), and by the time limit_list() finishes,\neverything relevant must have been parsed already.\n\nBut you are right. The commit->buffer may no longer be there, and\nthe --author-date-order option needs to read the object again\nin this codepath. That would be in line with what --pretty/format\nwould do, I guess.\n\nOr we could extend parse_commit() API to take an optional commit\ninfo slab to store not just author date but other non-essential\nstuff like people's names, and we arrange that extended API to be\ntriggered when we know --author-date-order is in effect?\n"},{"id":"220337","messageId":"20130610181557.GA2084@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7vwqq2l9cz.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T18:15:57Z","receivedAt":"2013-06-10T18:15:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 10, 2013 at 12:21:00AM -0700, Junio C Hamano wrote:\n\n> > It may be worth looking again for other places to use this over\n> > commit_list, but even the caller you are introducing here justifies its\n> > presence.\n> \n> The next candidate is paint-down-to-common, probably.\n\nYeah, I don't think I looked at that at all last time (mostly because it\nonly large as the graph gets wide, which is typically acceptable for\nus). But it should be easy to do.\n\n> > Also, I wrote some basic tests to cover the priority queue as a unit. I\n> > can rebase them on your commit if you are interested.\n> \n> It would be great.\n\nSquashable patch is below.\n\n> > Is it worth making this \"struct commit *\" a void pointer, and handling\n> > arbitrary items in our priority queue? The compare function should be\n> > the only thing that dereferences them.\n> > \n> > I do not have any non-commit priority queue use in mind, but I do not\n> > think it adds any complexity in this case.\n> \n> I didn't either (and still I don't think of one), but I agree that\n> the implementation can be reused for pq of any type, as long as it\n> is a pointer to struct.\n\nI converted this to a void pointer in my patch below, simply because it\nmakes it easier to write a test-queue that operates on ints. Due to\nimplicit casting, it should work for the most part without changing the\ncalling code unless you have a caller that does something like:\n\n commit_queue_get(&q)->date\n\nor similar. I didn't change the name, either. It may be silly to call it\n\"commit_queue\" still since it is now more general. I simply called mine\n\"queue\" (I wanted \"pqueue\", but that conflicted with globals defined by\nOpenSSL; yours is a more general queue anyway, so maybe that is a good\nname).\n\n> >> +\t/* Bubble up the new one */\n> >> +\tfor (ix = queue->nr - 1; ix; ix = parent) {\n> >> +\t\tparent = (ix - 1) / 2;\n> >> +\t\tif (compare(queue->array[parent], queue->array[ix],\n> >> +\t\t\t queue->cb_data) < 0)\n> >> +\t\t\tbreak;\n> >\n> > In my implementation, I stopped on \"compare() <= 0\". It is late and my\n> > mind is fuzzy, but I recall that heaps are never stable with respect to\n> > insertion order, so I don't think it would matter.\n> \n> It would matter in the sense that we cannot replace linked-list, if\n> the caller wants stability. It is more like \"we cannot do anything\n> about it\" than \"it would not matter\".\n\nRight. I meant \"I do not think it matters if you do <= or < here, as we\nare not stable anyway\". Doing \"<= 0\" stops the heapify operation sooner,\nthough I doubt it matters in practice (it is not an algorithmic\ncomplexity change, but just that you can sometimes quit early).\n\nI think it is the same situation in your \"push down\", too, where you can\nquit when the parent is equal to the largest child.\n\n> We can make each queue element a pair of insertion counter>, and tiebreak using the insertion order, if the\n> callers want the same stability as linked-list implementation, but\n> I tend to think it really matters.\n\nYes, I think that is the usual solution.\n\nHere's the patch with the tests, meant to be squashed into your 2/4. As\nI mentioned above, you may want to further tweak the name, which would\nrequire fixing up the rebase patches on top.\n\nIf you don't want to do the \"s/struct commit/void/\" change now, we can\nprobably just have test-queue stuff the ints into commit pointers.\n\nThe tests themselves are not extremely extensive, but at least let you\ncheck that you implemented the heap correctly. :)\n\n---\n .gitignore | 1 +\n Makefile | 1 +\n commit-queue.c | 6 ++---\n commit-queue.h | 8 +++---\n t/t0009-queue.sh | 50 +++++++++++++++++++++++++++++++++++\n test-queue.c | 39 +++++++++++++++++++++++++++\n 6 files changed, 98 insertions(+), 7 deletions(-)\n\ndiff --git a/.gitignore b/.gitignore\nindex 6669bf0..8670e6d 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -193,6 +193,7 @@\n /test-regex\n /test-revision-walking\n /test-run-command\n+/test-queue\n /test-sha1\n /test-sigchain\n /test-string-list\ndiff --git a/Makefile b/Makefile\nindex 3cf55e9..c957637 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -552,6 +552,7 @@ TEST_PROGRAMS_NEED_X += test-path-utils\n TEST_PROGRAMS_NEED_X += test-mktemp\n TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n+TEST_PROGRAMS_NEED_X += test-queue\n TEST_PROGRAMS_NEED_X += test-regex\n TEST_PROGRAMS_NEED_X += test-revision-walking\n TEST_PROGRAMS_NEED_X += test-run-command\ndiff --git a/commit-queue.c b/commit-queue.c\nindex 77d4b02..04acf23 100644\n--- a/commit-queue.c\n+++ b/commit-queue.c\n@@ -10,7 +10,7 @@ void clear_commit_queue(struct commit_queue *queue)\n \tqueue->array = NULL;\n }\n \n-void commit_queue_put(struct commit_queue *queue, struct commit *commit)\n+void commit_queue_put(struct commit_queue *queue, void *commit)\n {\n \tcommit_compare_fn compare = queue->compare;\n \tint ix, parent;\n@@ -34,9 +34,9 @@ struct commit *commit_queue_get(struct commit_queue *queue)\n \t}\n }\n \n-struct commit *commit_queue_get(struct commit_queue *queue)\n+void *commit_queue_get(struct commit_queue *queue)\n {\n-\tstruct commit *result, *swap;\n+\tvoid *result, *swap;\n \tint ix, child;\n \tcommit_compare_fn compare = queue->compare;\n \ndiff --git a/commit-queue.h b/commit-queue.h\nindex 7c5dc4c..ef8fb87 100644\n--- a/commit-queue.h\n+++ b/commit-queue.h\n@@ -5,26 +5,26 @@ extern void commit_queue_put(struct commit_queue *, struct commit *);\n * Compare two commits; the third parameter is cb_data in the\n * commit_queue structure.\n */\n-typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);\n+typedef int (*commit_compare_fn)(void *, void *, void *);\n \n struct commit_queue {\n \tcommit_compare_fn compare;\n \tvoid *cb_data;\n \tint alloc, nr;\n-\tstruct commit **array;\n+\tvoid **array;\n };\n \n /*\n * Add the commit to the queue\n */\n-extern void commit_queue_put(struct commit_queue *, struct commit *);\n+extern void commit_queue_put(struct commit_queue *, void *);\n \n /*\n * Extract the commit that compares the smallest out of the queue,\n * or NULL. If compare function is NULL, the queue acts as a LIFO\n * stack.\n */\n-extern struct commit *commit_queue_get(struct commit_queue *);\n+extern void *commit_queue_get(struct commit_queue *);\n \n extern void clear_commit_queue(struct commit_queue *);\n \ndiff --git a/t/t0009-queue.sh b/t/t0009-queue.sh\nnew file mode 100755\nindex 0000000..186df01\n--- /dev/null\n+++ b/t/t0009-queue.sh\n@@ -0,0 +1,50 @@\n+#!/bin/sh\n+\n+test_description='basic tests for priority queue implementation'\n+. ./test-lib.sh\n+\n+cat >expect <<'EOF'\n+1\n+2\n+3\n+4\n+5\n+5\n+6\n+7\n+8\n+9\n+10\n+EOF\n+test_expect_success 'basic ordering' '\n+\ttest-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+2\n+3\n+4\n+1\n+5\n+6\n+EOF\n+test_expect_success 'mixed put and get' '\n+\ttest-queue 6 2 4 get 5 3 get get 1 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+1\n+2\n+NULL\n+1\n+2\n+NULL\n+EOF\n+test_expect_success 'notice empty queue' '\n+\ttest-queue 1 2 get get get 1 2 get get get >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/test-queue.c b/test-queue.c\nnew file mode 100644\nindex 0000000..7743775\n--- /dev/null\n+++ b/test-queue.c\n@@ -0,0 +1,39 @@\n+#include \"cache.h\"\n+#include \"commit-queue.h\"\n+\n+static int intcmp(void *va, void *vb, void *data)\n+{\n+\tconst int *a = va, *b = vb;\n+\treturn *a - *b;\n+}\n+\n+static void show(int *v)\n+{\n+\tif (!v)\n+\t\tprintf(\"NULL\\n\");\n+\telse\n+\t\tprintf(\"%d\\n\", *v);\n+\tfree(v);\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct commit_queue pq = { intcmp };\n+\n+\twhile (*++argv) {\n+\t\tif (!strcmp(*argv, \"get\"))\n+\t\t\tshow(commit_queue_get(&pq));\n+\t\telse if (!strcmp(*argv, \"dump\")) {\n+\t\t\tint *v;\n+\t\t\twhile ((v = commit_queue_get(&pq)))\n+\t\t\t show(v);\n+\t\t}\n+\t\telse {\n+\t\t\tint *v = malloc(sizeof(*v));\n+\t\t\t*v = atoi(*argv);\n+\t\t\tcommit_queue_put(&pq, v);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n"},{"id":"220340","messageId":"20130610182441.GB2084@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7vsj0ql924.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 3/4] sort-in-topological-order: use commit-queue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T18:24:41Z","receivedAt":"2013-06-10T18:24:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 10, 2013 at 12:27:31AM -0700, Junio C Hamano wrote:\n\n> > Around the same time, though, René wrote the linked-list merge sort that\n> > powers commit_list_sort_by_date. And topo-sort learned to do O(1)\n> > insertions into the unsorted list, and then one O(n log n) sort.\n> \n> Yes, but that only affects the \"sort the work queue in date order\"\n> before entering the main loop, and maintenance of work queue as we\n> dig along still is \"find the place to put this in the date-order\n> sorted linked list\", no?\n\nAh, you're right. I was thinking that we saw all of the commits up\nfront and then sorted. And we do, but we still keep a separate list in\nthe work queue.\n\nSo I think it may just be the case that \"N\" does not get very big here\n(the width of the graph), so log(N) versus (N) does not make a big\ndifference.\n\n> I've been disturbed every time I saw the commit_list insertion\n> function that does a small allocation which will be freed fairly\n> often and have been wondering if we can rewrite it with custom slab\n> allocator, but not using linked list where we do not have to feels\n> like a better solution to that issue, and use of pqueue may be a\n> right direction to go in.\n\nAgreed. The only thing I'd worry about is that somebody cares about the\norder stability of same-time commits in the output. But I cannot think\nof a case where it is important (especially because the timestamps are\nsubject to minor skew anyway, so it is not like you could even count on\nparticular commits having equivalent timestamps).\n\n-Peff\n"},{"id":"220355","messageId":"20130610184918.GC2084@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7vobbel8ib.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 4/4] log: --author-date-order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T18:49:18Z","receivedAt":"2013-06-10T18:49:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 10, 2013 at 12:39:24AM -0700, Junio C Hamano wrote:\n\n> > I'm not excited about introducing yet another place that parses commit\n> > objects (mostly not for correctness, but because we have had\n> > inconsistency in how malformed objects are treated). It is at least\n> > using split_ident_line which covers the hard bits. I wonder how much\n> > slower it would be to simply call format_commit_message to do the\n> > parsing.\n> \n> The thought certainly crossed my mind, not exactly in that form but\n> more about splitting the machinery used in pretty.c into a more\n> reusable form.\n> \n> The result of my attempt however did not become all that reusable\n> (admittedly I didn't spend too much brain cycles on it), so I punted\n> ;-).\n\nYes, I feel like it has been tried before. The problem is that a clean\ninterface would let you get individual pieces of information with a\nsingle call. But an efficient interface will utilize the same parsing\npass to get multiple items out, and stop parsing when we have gotten all\nrequired items (but leave the parser in a consistent state so that we\ncan pick it up later).\n\nThe format_commit_one parser does that, but the \"format_commit_context\"\nit holds is a bit bulky. I think it might be possible to pull out the\nparsing bits into a separate struct, and you could call it something\nlike:\n\n struct commit_parser parser;\n unsigned long authordate;\n const char *authorname;\n int authorlen;\n\n commit_parser_init(&parser, commit);\n authordate = commit_parse_authordate(&parser);\n authorname = commit_parse_authorname(&parser, &authorlen);\n\nwhere the second parse call is basically \"free\", because we've already\ndone (and cached) the hard work in the first call.\n\nSo they might look like:\n\n static void parse_author_ident(struct commit_parser *parser)\n {\n if (!parser->author.name_begin) {\n if (!parser->authorline.start)\n parse_commit_header(parser);\n split_ident_line(&parser->author,\n parser->authorline.start,\n parser->authorline.len);\n }\n }\n\n unsigned long commit_parse_authordate(struct commit_parser *parser)\n {\n parse_author_ident(parser);\n /* XXX should check for malformedness here */\n return strtoul(ident.date_begin, NULL, 10);\n }\n\n const char *commit_parse_authorname(struct commit_parser *parser,\n unsigned long *len)\n {\n parse_author_ident(parser);\n *len = parser.author.name_end - parser.author.name_begin;\n return parser.author.name_begin;\n }\n\nand so forth. It would be easy (and have the same efficiency) for\nformat_commit_message to build on that, and it calling it from regular\ncode is not too bad.\n\n> But you are right. The commit->buffer may no longer be there, and\n> the --author-date-order option needs to read the object again\n> in this codepath. That would be in line with what --pretty/format\n> would do, I guess.\n> \n> Or we could extend parse_commit() API to take an optional commit\n> info slab to store not just author date but other non-essential\n> stuff like people's names, and we arrange that extended API to be\n> triggered when we know --author-date-order is in effect?\n\nI like the latter option. It takes a non-trivial amount of time to load\nthe commits from disk, and now we are potentially doing it 2 or 3 times\nfor a run (once to parse, once to get the author info for topo-sort, and\npossibly later to show it if --pretty is given; though I did not check\nand maybe we turn off save_commit_buffer with --pretty). It would be\nnice to have an extended parse_object that handled that. I'm not sure of\nthe interface. Maybe variadic with pairs of type/slab, like:\n\n parse_commit_extended(commit,\n PARSE_COMMIT_AUTHORDATE, &authordate_slab,\n PARSE_COMMIT_DONE);\n\n?\n\n-Peff\n"},{"id":"220356","messageId":"7v1u89iyla.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130610181557.GA2084@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-10T18:56:33Z","receivedAt":"2013-06-10T18:56:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Mon, Jun 10, 2013 at 12:21:00AM -0700, Junio C Hamano wrote:\n>\n>> > It may be worth looking again for other places to use this over\n>> > commit_list, but even the caller you are introducing here justifies its\n>> > presence.\n>> \n>> The next candidate is paint-down-to-common, probably.\n>\n> Yeah, I don't think I looked at that at all last time (mostly because it\n> only large as the graph gets wide, which is typically acceptable for\n> us). But it should be easy to do.\n>\n>> > Also, I wrote some basic tests to cover the priority queue as a unit. I\n>> > can rebase them on your commit if you are interested.\n>> \n>> It would be great.\n>\n> Squashable patch is below.\n>\n>> > Is it worth making this \"struct commit *\" a void pointer, and handling\n>> > arbitrary items in our priority queue? The compare function should be\n>> > the only thing that dereferences them.\n>> > \n>> > I do not have any non-commit priority queue use in mind, but I do not\n>> > think it adds any complexity in this case.\n>> \n>> I didn't either (and still I don't think of one), but I agree that\n>> the implementation can be reused for pq of any type, as long as it\n>> is a pointer to struct.\n>\n> I converted this to a void pointer in my patch below, simply because it\n> makes it easier to write a test-queue that operates on ints. Due to\n> implicit casting, it should work for the most part without changing the\n> calling code unless you have a caller that does something like:\n>\n> commit_queue_get(&q)->date\n>\n> or similar. I didn't change the name, either. It may be silly to call it\n> \"commit_queue\" still since it is now more general. I simply called mine\n> \"queue\" (I wanted \"pqueue\", but that conflicted with globals defined by\n> OpenSSL; yours is a more general queue anyway, so maybe that is a good\n> name).\n\nI agree that it makes sense not to call it either commit-queue or\npqueue. While at it, the filenames should probably be moved as\nwell, no?\n\n> Here's the patch with the tests, meant to be squashed into your 2/4. As\n> I mentioned above, you may want to further tweak the name, which would\n> require fixing up the rebase patches on top.\n>\n> If you don't want to do the \"s/struct commit/void/\" change now, we can\n> probably just have test-queue stuff the ints into commit pointers.\n>\n> The tests themselves are not extremely extensive, but at least let you\n> check that you implemented the heap correctly. :)\n\nThanks.\n"},{"id":"220357","messageId":"20130610185907.GD2084@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7v1u89iyla.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-10T18:59:07Z","receivedAt":"2013-06-10T18:59:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 10, 2013 at 11:56:33AM -0700, Junio C Hamano wrote:\n\n> > or similar. I didn't change the name, either. It may be silly to call it\n> > \"commit_queue\" still since it is now more general. I simply called mine\n> > \"queue\" (I wanted \"pqueue\", but that conflicted with globals defined by\n> > OpenSSL; yours is a more general queue anyway, so maybe that is a good\n> > name).\n> \n> I agree that it makes sense not to call it either commit-queue or\n> pqueue. While at it, the filenames should probably be moved as\n> well, no?\n\nYeah, definitely. I left all of that as an exercise for you, since the\nname change will involve a lot of fallout in the other patches.\n\n-Peff\n"},{"id":"220400","messageId":"7vd2rteej0.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130610185907.GD2084@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-10T23:23:31Z","receivedAt":"2013-06-10T23:23:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Mon, Jun 10, 2013 at 11:56:33AM -0700, Junio C Hamano wrote:\n>\n>> > or similar. I didn't change the name, either. It may be silly to call it\n>> > \"commit_queue\" still since it is now more general. I simply called mine\n>> > \"queue\" (I wanted \"pqueue\", but that conflicted with globals defined by\n>> > OpenSSL; yours is a more general queue anyway, so maybe that is a good\n>> > name).\n>> \n>> I agree that it makes sense not to call it either commit-queue or\n>> pqueue. While at it, the filenames should probably be moved as\n>> well, no?\n>\n> Yeah, definitely. I left all of that as an exercise for you, since the\n> name change will involve a lot of fallout in the other patches.\n\nOK, I pushed out a result of some renaming and rebasing. Notable\nchanges are:\n\n - The data and API is called prio-queue and they live in prio-queue.[ch];\n\n - The test script is also named test-prio-queue.c, to leave the\n door open for other kinds of queue;\n\n - For now, record_author_date() does the obvious read-sha1-file and\n free; and\n\n - The comparison callback's function signature had three \"void *\",\n so they are named in the header file now. Also two \"thing\"\n pointers are marked as \"const void *\".\n\nI may have flipped the comparison < vs <= as well.\n\nThanks.\n"},{"id":"220416","messageId":"20130611063648.GB23650@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7vd2rteej0.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-11T06:36:48Z","receivedAt":"2013-06-11T06:36:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 10, 2013 at 04:23:31PM -0700, Junio C Hamano wrote:\n\n> OK, I pushed out a result of some renaming and rebasing. Notable\n> changes are:\n> \n> - The data and API is called prio-queue and they live in prio-queue.[ch];\n> \n> - The test script is also named test-prio-queue.c, to leave the\n> door open for other kinds of queue;\n\nSounds reasonable, though you may want to update the commit message of\njc/topo-author-date-sort~2.\n\n> - For now, record_author_date() does the obvious read-sha1-file and\n> free; and\n\nI think that is a good place to leave it in this series. It does not\nhurt performance in any existing cases, and any parsing refactoring can\ncome later if somebody wants to work on it.\n\n> - The comparison callback's function signature had three \"void *\",\n> so they are named in the header file now. Also two \"thing\"\n> pointers are marked as \"const void *\".\n\nYeah, I noticed both when porting my tests, but didn't want to add too\nmany distracting details. Thanks for fixing.\n\nOverall, it looks good for me except for the commit message tweaks I\nmentioned above.\n\n-Peff\n"},{"id":"220460","messageId":"7vy5agbmxs.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130611063648.GB23650@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-11T17:02:23Z","receivedAt":"2013-06-11T17:02:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Overall, it looks good for me except for the commit message tweaks I\n> mentioned above.\n\nThanks. Rerolled; will resend when I have time (and if I do not\nforget).\n"},{"id":"220548","messageId":"1370989149-28538-1-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"20130611063648.GB23650@sigill.intra.peff.net","subject":"[PATCH v3 0/4] log --author-date-order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-11T22:19:05Z","receivedAt":"2013-06-11T22:19:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The first one is unchanged. The second one was redone with Peff's\nhelp, and the other two patches have been adjusted for it.\n\nAdding tests to t4202 and/or t6012 is left as an exercise to readers.\n\nJunio C Hamano (4):\n toposort: rename \"lifo\" field\n prio-queue: priority queue of pointers to structs\n sort-in-topological-order: use prio-queue\n log: --author-date-order\n\n .gitignore | 1 +\n Documentation/rev-list-options.txt | 4 +\n Makefile | 3 +\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 ++--\n commit.c | 145 ++++++++++++++++++++++++++++++-------\n commit.h | 15 +++-\n prio-queue.c | 84 +++++++++++++++++++++\n prio-queue.h | 48 ++++++++++++\n revision.c | 13 ++--\n revision.h | 6 +-\n t/t0009-prio-queue.sh | 50 +++++++++++++\n test-prio-queue.c | 39 ++++++++++\n 13 files changed, 381 insertions(+), 43 deletions(-)\n create mode 100644 prio-queue.c\n create mode 100644 prio-queue.h\n create mode 100755 t/t0009-prio-queue.sh\n create mode 100644 test-prio-queue.c\n\n-- \n1.8.3.1-494-g51b8af5\n"},{"id":"220543","messageId":"1370989149-28538-2-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370989149-28538-1-git-send-email-gitster@pobox.com","subject":"[PATCH v3 1/4] toposort: rename \"lifo\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-11T22:19:06Z","receivedAt":"2013-06-11T22:19:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The primary invariant of sort_in_topological_order() is that a\nparent commit is not emitted until all children of it are. When\ntraversing a forked history like this with \"git log C E\":\n\n A----B----C\n \\\n D----E\n\nwe ensure that A is emitted after all of B, C, D, and E are done, B\nhas to wait until C is done, and D has to wait until E is done.\n\nIn some applications, however, we would further want to control how\nthese child commits B, C, D and E on two parallel ancestry chains\nare shown.\n\nMost of the time, we would want to see C and B emitted together, and\nthen E and D, and finally A (i.e. the --topo-order output). The\n\"lifo\" parameter of the sort_in_topological_order() function is used\nto control this behaviour. We start the traversal by knowing two\ncommits, C and E. While keeping in mind that we also need to\ninspect E later, we pick C first to inspect, and we notice and\nrecord that B needs to be inspected. By structuring the \"work to be\ndone\" set as a LIFO stack, we ensure that B is inspected next,\nbefore other in-flight commits we had known that we will need to\ninspect, e.g. E.\n\nWhen showing in --date-order, we would want to see commits ordered\nby timestamps, i.e. show C, E, B and D in this order before showing\nA, possibly mixing commits from two parallel histories together.\nWhen \"lifo\" parameter is set to false, the function keeps the \"work\nto be done\" set sorted in the date order to realize this semantics.\nAfter inspecting C, we add B to the \"work to be done\" set, but the\nnext commit we inspect from the set is E which is newer than B.\n\nThe name \"lifo\", however, is too strongly tied to the way how the\nfunction implements its behaviour, and does not describe what the\nbehaviour _means_.\n\nReplace this field with an enum rev_sort_order, with two possible\nvalues: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and\nupdate the existing code. The mechanical replacement rule is:\n\n \"lifo == 0\" is equivalent to \"sort_order == REV_SORT_BY_COMMIT_DATE\"\n \"lifo == 1\" is equivalent to \"sort_order == REV_SORT_IN_GRAPH_ORDER\"\n\nSigned-off-by: Junio C Hamano \n---\n builtin/log.c | 2 +-\n builtin/show-branch.c | 14 ++++++++------\n commit.c | 12 ++++++++----\n commit.h | 14 +++++++++++---\n revision.c | 10 +++++-----\n revision.h | 6 +++++-\n 6 files changed, 38 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 8f0b2e8..8d26042 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -205,7 +205,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n \tint i = revs->early_output;\n \tint show_header = 1;\n \n-\tsort_in_topological_order(&list, revs->lifo);\n+\tsort_in_topological_order(&list, revs->sort_order);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex d208fd6..7c57985 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -631,7 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \tint num_rev, i, extra = 0;\n \tint all_heads = 0, all_remotes = 0;\n \tint all_mask, all_revs;\n-\tint lifo = 1;\n+\tenum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;\n \tchar head[128];\n \tconst char *head_p;\n \tint head_len;\n@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\t\t N_(\"show possible merge bases\")),\n \t\tOPT_BOOLEAN(0, \"independent\", &independent,\n \t\t\t N_(\"show refs unreachable from any other ref\")),\n-\t\tOPT_BOOLEAN(0, \"topo-order\", &lifo,\n-\t\t\t N_(\"show commits in topological order\")),\n+\t\tOPT_SET_INT(0, \"topo-order\", &sort_order,\n+\t\t\t N_(\"show commits in topological order\"),\n+\t\t\t REV_SORT_IN_GRAPH_ORDER),\n \t\tOPT_BOOLEAN(0, \"topics\", &topics,\n \t\t\t N_(\"show only commits not on the first branch\")),\n \t\tOPT_SET_INT(0, \"sparse\", &dense,\n \t\t\t N_(\"show merges reachable from only one tip\"), 0),\n-\t\tOPT_SET_INT(0, \"date-order\", &lifo,\n+\t\tOPT_SET_INT(0, \"date-order\", &sort_order,\n \t\t\t N_(\"show commits where no parent comes before its \"\n-\t\t\t \"children\"), 0),\n+\t\t\t \"children\"),\n+\t\t\t REV_SORT_BY_COMMIT_DATE),\n \t\t{ OPTION_CALLBACK, 'g', \"reflog\", &reflog_base, N_(\"[,]\"),\n \t\t\t N_(\"show most recent ref-log entries starting at \"\n \t\t\t \"base\"),\n@@ -901,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\texit(0);\n \n \t/* Sort topologically */\n-\tsort_in_topological_order(&seen, lifo);\n+\tsort_in_topological_order(&seen, sort_order);\n \n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\ndiff --git a/commit.c b/commit.c\nindex f97456d..11b9635 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -512,7 +512,7 @@ define_commit_slab(indegree_slab, int);\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo)\n+void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n@@ -561,7 +561,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t}\n \n \t/* process the list in topological order */\n-\tif (!lifo)\n+\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n \t\tcommit_list_sort_by_date(&work);\n \n \tpptr = list;\n@@ -588,10 +588,14 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n \t\t\tif (--(*pi) == 1) {\n-\t\t\t\tif (!lifo)\n+\t\t\t\tswitch (sort_order) {\n+\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n \t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\telse\n+\t\t\t\t\tbreak;\n+\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t\t/*\ndiff --git a/commit.h b/commit.h\nindex 70e749d..247e474 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -139,15 +139,23 @@ struct commit *pop_commit(struct commit_list **stack);\n void clear_commit_marks(struct commit *commit, unsigned int mark);\n void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n \n+\n+enum rev_sort_order {\n+\tREV_SORT_IN_GRAPH_ORDER = 0,\n+\tREV_SORT_BY_COMMIT_DATE\n+};\n+\n /*\n * Performs an in-place topological sort of list supplied.\n *\n * invariant of resulting list is:\n * a reachable from b => ord(b) < ord(a)\n- * in addition, when lifo == 0, commits on parallel tracks are\n- * sorted in the dates order.\n+ * sort_order further specifies:\n+ * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\n+ * chain together.\n+ * REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.\n */\n-void sort_in_topological_order(struct commit_list ** list, int lifo);\n+void sort_in_topological_order(struct commit_list **, enum rev_sort_order);\n \n struct commit_graft {\n \tunsigned char sha1[20];\ndiff --git a/revision.c b/revision.c\nindex cf620c6..966ebbc 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1038,7 +1038,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \tDIFF_OPT_SET(&revs->pruning, QUICK);\n \trevs->pruning.add_remove = file_add_remove;\n \trevs->pruning.change = file_change;\n-\trevs->lifo = 1;\n+\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \trevs->dense = 1;\n \trevs->prefix = prefix;\n \trevs->max_age = -1;\n@@ -1373,7 +1373,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--merge\")) {\n \t\trevs->show_merge = 1;\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n-\t\trevs->lifo = 1;\n+\t\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \t\trevs->topo_order = 1;\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n@@ -1391,7 +1391,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->prune = 1;\n \t\tload_ref_decorations(DECORATE_SHORT_REFS);\n \t} else if (!strcmp(arg, \"--date-order\")) {\n-\t\trevs->lifo = 0;\n+\t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n@@ -2165,7 +2165,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n-\t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n \tif (revs->children.name)\n@@ -2480,7 +2480,7 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \t * If revs->topo_order is set, sort the boundary commits\n \t * in topological order\n \t */\n-\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tsort_in_topological_order(&revs->commits, revs->sort_order);\n }\n \n static struct commit *get_revision_internal(struct rev_info *revs)\ndiff --git a/revision.h b/revision.h\nindex 5da09ee..2a5e325 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"grep.h\"\n #include \"notes.h\"\n+#include \"commit.h\"\n \n #define SEEN\t\t(1u<<0)\n #define UNINTERESTING (1u<<1)\n@@ -60,6 +61,10 @@ struct rev_info {\n \tconst char *prefix;\n \tconst char *def;\n \tstruct pathspec prune_data;\n+\n+\t/* topo-sort */\n+\tenum rev_sort_order sort_order;\n+\n \tunsigned int\tearly_output:1,\n \t\t\tignore_missing:1;\n \n@@ -70,7 +75,6 @@ struct rev_info {\n \t\t\tshow_all:1,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n-\t\t\tlifo:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\n \t\t\tsimplify_by_decoration:1,\n-- \n1.8.3.1-494-g51b8af5\n"},{"id":"220542","messageId":"1370989149-28538-3-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370989149-28538-1-git-send-email-gitster@pobox.com","subject":"[PATCH v3 2/4] prio-queue: priority queue of pointers to structs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-11T22:19:07Z","receivedAt":"2013-06-11T22:19:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Traditionally we used a singly linked list of commits to hold a set\nof in-flight commits while traversing history. The most typical use\nof the list is to add commits that are newly discovered to it, keep\nthe list sorted by commit timestamp, pick up the newest one from the\nlist, and keep digging. The cost of keeping the singly linked list\nsorted is nontrivial, and this typical use pattern better matches a\npriority queue.\n\nIntroduce a prio-queue structure, that can be used either as a LIFO\nstack, or a priority queue. This will be used in the next patch to\nhold in-flight commits during sort-in-topological-order.\n\nTests and the idea to make it usable for any \"void *\" pointers to\n\"things\" are by Jeff King. Bugs are mine.\n\nSigned-off-by: Junio C Hamano \n---\n .gitignore | 1 +\n Makefile | 3 +++\n prio-queue.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++\n prio-queue.h | 45 ++++++++++++++++++++++++++++++++\n t/t0009-prio-queue.sh | 50 ++++++++++++++++++++++++++++++++++++\n test-prio-queue.c | 39 ++++++++++++++++++++++++++++\n 6 files changed, 209 insertions(+)\n create mode 100644 prio-queue.c\n create mode 100644 prio-queue.h\n create mode 100755 t/t0009-prio-queue.sh\n create mode 100644 test-prio-queue.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 6669bf0..b753817 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -190,6 +190,7 @@\n /test-mktemp\n /test-parse-options\n /test-path-utils\n+/test-prio-queue\n /test-regex\n /test-revision-walking\n /test-run-command\ndiff --git a/Makefile b/Makefile\nindex 598d631..0246194 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -552,6 +552,7 @@ TEST_PROGRAMS_NEED_X += test-mergesort\n TEST_PROGRAMS_NEED_X += test-mktemp\n TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n+TEST_PROGRAMS_NEED_X += test-prio-queue\n TEST_PROGRAMS_NEED_X += test-regex\n TEST_PROGRAMS_NEED_X += test-revision-walking\n TEST_PROGRAMS_NEED_X += test-run-command\n@@ -685,6 +686,7 @@ LIB_H += parse-options.h\n LIB_H += patch-ids.h\n LIB_H += pathspec.h\n LIB_H += pkt-line.h\n+LIB_H += prio-queue.h\n LIB_H += progress.h\n LIB_H += prompt.h\n LIB_H += quote.h\n@@ -824,6 +826,7 @@ LIB_OBJS += pathspec.o\n LIB_OBJS += pkt-line.o\n LIB_OBJS += preload-index.o\n LIB_OBJS += pretty.o\n+LIB_OBJS += prio-queue.o\n LIB_OBJS += progress.o\n LIB_OBJS += prompt.o\n LIB_OBJS += quote.o\ndiff --git a/prio-queue.c b/prio-queue.c\nnew file mode 100644\nindex 0000000..f2a4973\n--- /dev/null\n+++ b/prio-queue.c\n@@ -0,0 +1,71 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"prio-queue.h\"\n+\n+void clear_prio_queue(struct prio_queue *queue)\n+{\n+\tfree(queue->array);\n+\tqueue->nr = 0;\n+\tqueue->alloc = 0;\n+\tqueue->array = NULL;\n+}\n+\n+void prio_queue_put(struct prio_queue *queue, void *thing)\n+{\n+\tprio_queue_compare_fn compare = queue->compare;\n+\tint ix, parent;\n+\n+\t/* Append at the end */\n+\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n+\tqueue->array[queue->nr++] = thing;\n+\tif (!compare)\n+\t\treturn; /* LIFO */\n+\n+\t/* Bubble up the new one */\n+\tfor (ix = queue->nr - 1; ix; ix = parent) {\n+\t\tparent = (ix - 1) / 2;\n+\t\tif (compare(queue->array[parent], queue->array[ix],\n+\t\t\t queue->cb_data) <= 0)\n+\t\t\tbreak;\n+\n+\t\tthing = queue->array[parent];\n+\t\tqueue->array[parent] = queue->array[ix];\n+\t\tqueue->array[ix] = thing;\n+\t}\n+}\n+\n+void *prio_queue_get(struct prio_queue *queue)\n+{\n+\tvoid *result, *swap;\n+\tint ix, child;\n+\tprio_queue_compare_fn compare = queue->compare;\n+\n+\tif (!queue->nr)\n+\t\treturn NULL;\n+\tif (!compare)\n+\t\treturn queue->array[--queue->nr]; /* LIFO */\n+\n+\tresult = queue->array[0];\n+\tif (!--queue->nr)\n+\t\treturn result;\n+\n+\tqueue->array[0] = queue->array[queue->nr];\n+\n+\t/* Push down the one at the root */\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\t\tchild = ix * 2 + 1; /* left */\n+\t\tif ((child + 1 < queue->nr) &&\n+\t\t (compare(queue->array[child], queue->array[child + 1],\n+\t\t\t queue->cb_data) >= 0))\n+\t\t\tchild++; /* use right child */\n+\n+\t\tif (compare(queue->array[ix], queue->array[child],\n+\t\t\t queue->cb_data) <= 0)\n+\t\t\tbreak;\n+\n+\t\tswap = queue->array[child];\n+\t\tqueue->array[child] = queue->array[ix];\n+\t\tqueue->array[ix] = swap;\n+\t}\n+\treturn result;\n+}\ndiff --git a/prio-queue.h b/prio-queue.h\nnew file mode 100644\nindex 0000000..ed354a5\n--- /dev/null\n+++ b/prio-queue.h\n@@ -0,0 +1,45 @@\n+#ifndef PRIO_QUEUE_H\n+#define PRIO_QUEUE_H\n+\n+/*\n+ * A priority queue implementation, primarily for keeping track of\n+ * commits in the 'date-order' so that we process them from new to old\n+ * as they are discovered, but can be used to hold any pointer to\n+ * struct. The caller is responsible for supplying a function to\n+ * compare two \"things\".\n+ *\n+ * Alternatively, this data structure can also be used as a LIFO stack\n+ * by specifying NULL as the comparison function.\n+ */\n+\n+/*\n+ * Compare two \"things\", one and two; the third parameter is cb_data\n+ * in the prio_queue structure. The result is returned as a sign of\n+ * the return value, being the same as the sign of the result of\n+ * subtracting \"two\" from \"one\" (i.e. negative if \"one\" sorts earlier\n+ * than \"two\").\n+ */\n+typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);\n+\n+struct prio_queue {\n+\tprio_queue_compare_fn compare;\n+\tvoid *cb_data;\n+\tint alloc, nr;\n+\tvoid **array;\n+};\n+\n+/*\n+ * Add the \"thing\" to the queue.\n+ */\n+extern void prio_queue_put(struct prio_queue *, void *thing);\n+\n+/*\n+ * Extract the \"thing\" that compares the smallest out of the queue,\n+ * or NULL. If compare function is NULL, the queue acts as a LIFO\n+ * stack.\n+ */\n+extern void *prio_queue_get(struct prio_queue *);\n+\n+extern void clear_prio_queue(struct prio_queue *);\n+\n+#endif /* PRIO_QUEUE_H */\ndiff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh\nnew file mode 100755\nindex 0000000..94045c3\n--- /dev/null\n+++ b/t/t0009-prio-queue.sh\n@@ -0,0 +1,50 @@\n+#!/bin/sh\n+\n+test_description='basic tests for priority queue implementation'\n+. ./test-lib.sh\n+\n+cat >expect <<'EOF'\n+1\n+2\n+3\n+4\n+5\n+5\n+6\n+7\n+8\n+9\n+10\n+EOF\n+test_expect_success 'basic ordering' '\n+\ttest-prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+2\n+3\n+4\n+1\n+5\n+6\n+EOF\n+test_expect_success 'mixed put and get' '\n+\ttest-prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+cat >expect <<'EOF'\n+1\n+2\n+NULL\n+1\n+2\n+NULL\n+EOF\n+test_expect_success 'notice empty queue' '\n+\ttest-prio-queue 1 2 get get get 1 2 get get get >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\ndiff --git a/test-prio-queue.c b/test-prio-queue.c\nnew file mode 100644\nindex 0000000..7be72f0\n--- /dev/null\n+++ b/test-prio-queue.c\n@@ -0,0 +1,39 @@\n+#include \"cache.h\"\n+#include \"prio-queue.h\"\n+\n+static int intcmp(const void *va, const void *vb, void *data)\n+{\n+\tconst int *a = va, *b = vb;\n+\treturn *a - *b;\n+}\n+\n+static void show(int *v)\n+{\n+\tif (!v)\n+\t\tprintf(\"NULL\\n\");\n+\telse\n+\t\tprintf(\"%d\\n\", *v);\n+\tfree(v);\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct prio_queue pq = { intcmp };\n+\n+\twhile (*++argv) {\n+\t\tif (!strcmp(*argv, \"get\"))\n+\t\t\tshow(prio_queue_get(&pq));\n+\t\telse if (!strcmp(*argv, \"dump\")) {\n+\t\t\tint *v;\n+\t\t\twhile ((v = prio_queue_get(&pq)))\n+\t\t\t show(v);\n+\t\t}\n+\t\telse {\n+\t\t\tint *v = malloc(sizeof(*v));\n+\t\t\t*v = atoi(*argv);\n+\t\t\tprio_queue_put(&pq, v);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n-- \n1.8.3.1-494-g51b8af5\n"},{"id":"220544","messageId":"1370989149-28538-4-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370989149-28538-1-git-send-email-gitster@pobox.com","subject":"[PATCH v3 3/4] sort-in-topological-order: use prio-queue","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-11T22:19:08Z","receivedAt":"2013-06-11T22:19:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Use the prio-queue data structure to implement a priority queue of\ncommits sorted by committer date, when handling --date-order. The\nstructure can also be used as a simple LIFO stack, which is a good\nmatch for --topo-order processing.\n\nSigned-off-by: Junio C Hamano \n---\n commit.c | 75 +++++++++++++++++++++++++++++++++++-------------------------\n prio-queue.c | 13 +++++++++++\n prio-queue.h | 3 +++\n 3 files changed, 60 insertions(+), 31 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 11b9635..8b84ebf 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -9,6 +9,7 @@\n #include \"gpg-interface.h\"\n #include \"mergesort.h\"\n #include \"commit-slab.h\"\n+#include \"prio-queue.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -509,21 +510,42 @@ struct commit *pop_commit(struct commit_list **stack)\n /* count number of children that have not been emitted */\n define_commit_slab(indegree_slab, int);\n \n+static int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n+{\n+\tconst struct commit *a = a_, *b = b_;\n+\t/* newer commits with larger date first */\n+\tif (a->date < b->date)\n+\t\treturn 1;\n+\telse if (a->date > b->date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n /*\n * Performs an in-place topological sort on the list supplied.\n */\n-void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)\n+void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n-\tstruct commit_list *work, **insert;\n \tstruct commit_list **pptr;\n \tstruct indegree_slab indegree;\n+\tstruct prio_queue queue;\n+\tstruct commit *commit;\n \n \tif (!orig)\n \t\treturn;\n \t*list = NULL;\n \n \tinit_indegree_slab(&indegree);\n+\tmemset(&queue, '\\0', sizeof(queue));\n+\tswitch (sort_order) {\n+\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n+\t\tqueue.compare = NULL;\n+\t\tbreak;\n+\tcase REV_SORT_BY_COMMIT_DATE:\n+\t\tqueue.compare = compare_commits_by_commit_date;\n+\t\tbreak;\n+\t}\n \n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n@@ -533,7 +555,7 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \n \t/* update the indegree */\n \tfor (next = orig; next; next = next->next) {\n-\t\tstruct commit_list * parents = next->item->parents;\n+\t\tstruct commit_list *parents = next->item->parents;\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n@@ -551,30 +573,28 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \t *\n \t * the tips serve as a starting set for the work queue.\n \t */\n-\twork = NULL;\n-\tinsert = &work;\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \n \t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n-\t\t\tinsert = &commit_list_insert(commit, insert)->next;\n+\t\t\tprio_queue_put(&queue, commit);\n \t}\n \n-\t/* process the list in topological order */\n-\tif (sort_order != REV_SORT_IN_GRAPH_ORDER)\n-\t\tcommit_list_sort_by_date(&work);\n+\t/*\n+\t * This is unfortunate; the initial tips need to be shown\n+\t * in the order given from the revision traversal machinery.\n+\t */\n+\tif (sort_order == REV_SORT_IN_GRAPH_ORDER)\n+\t\tprio_queue_reverse(&queue);\n+\n+\t/* We no longer need the commit list */\n+\tfree_commit_list(orig);\n \n \tpptr = list;\n \t*list = NULL;\n-\twhile (work) {\n-\t\tstruct commit *commit;\n-\t\tstruct commit_list *parents, *work_item;\n-\n-\t\twork_item = work;\n-\t\twork = work_item->next;\n-\t\twork_item->next = NULL;\n+\twhile ((commit = prio_queue_get(&queue)) != NULL) {\n+\t\tstruct commit_list *parents;\n \n-\t\tcommit = work_item->item;\n \t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n@@ -587,27 +607,20 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s\n \t\t\t * when all their children have been emitted thereby\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n-\t\t\tif (--(*pi) == 1) {\n-\t\t\t\tswitch (sort_order) {\n-\t\t\t\tcase REV_SORT_BY_COMMIT_DATE:\n-\t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n-\t\t\t\t\tbreak;\n-\t\t\t\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n-\t\t\t\t\tcommit_list_insert(parent, &work);\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t}\n+\t\t\tif (--(*pi) == 1)\n+\t\t\t\tprio_queue_put(&queue, parent);\n \t\t}\n \t\t/*\n-\t\t * work_item is a commit all of whose children\n-\t\t * have already been emitted. we can emit it now.\n+\t\t * all children of commit have already been\n+\t\t * emitted. we can emit it now.\n \t\t */\n \t\t*(indegree_slab_at(&indegree, commit)) = 0;\n-\t\t*pptr = work_item;\n-\t\tpptr = &work_item->next;\n+\n+\t\tpptr = &commit_list_insert(commit, pptr)->next;\n \t}\n \n \tclear_indegree_slab(&indegree);\n+\tclear_prio_queue(&queue);\n }\n \n /* merge-base stuff */\ndiff --git a/prio-queue.c b/prio-queue.c\nindex f2a4973..c9f8c6d 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -2,6 +2,19 @@\n #include \"commit.h\"\n #include \"prio-queue.h\"\n \n+void prio_queue_reverse(struct prio_queue *queue)\n+{\n+\tint i, j;\n+\n+\tif (queue->compare != NULL)\n+\t\tdie(\"BUG: prio_queue_reverse() on non-LIFO queue\");\n+\tfor (i = 0; i <= (j = (queue->nr - 1) - i); i++) {\n+\t\tstruct commit *swap = queue->array[i];\n+\t\tqueue->array[i] = queue->array[j];\n+\t\tqueue->array[j] = swap;\n+\t}\n+}\n+\n void clear_prio_queue(struct prio_queue *queue)\n {\n \tfree(queue->array);\ndiff --git a/prio-queue.h b/prio-queue.h\nindex ed354a5..e8b81e2 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -42,4 +42,7 @@ extern void *prio_queue_get(struct prio_queue *);\n \n extern void clear_prio_queue(struct prio_queue *);\n \n+/* Reverse the LIFO elements */\n+extern void prio_queue_reverse(struct prio_queue *);\n+\n #endif /* PRIO_QUEUE_H */\n-- \n1.8.3.1-494-g51b8af5\n"},{"id":"220545","messageId":"1370989149-28538-5-git-send-email-gitster@pobox.com","threadId":"34028","inReplyTo":"1370989149-28538-1-git-send-email-gitster@pobox.com","subject":"[PATCH v3 4/4] log: --author-date-order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-11T22:19:09Z","receivedAt":"2013-06-11T22:19:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sometimes people would want to view the commits in parallel\nhistories in the order of author dates, not committer dates.\n\nTeach \"topo-order\" sort machinery to do so, using a commit-info slab\nto record the author dates of each commit, and prio-queue to sort\nthem.\n\nSigned-off-by: Junio C Hamano \n---\n\n * This re-reads the commit object when commit->buf has already been\n freed, which is necessary to sort by the author date.\n\n Documentation/rev-list-options.txt | 4 +++\n commit.c | 74 ++++++++++++++++++++++++++++++++++++++\n commit.h | 3 +-\n revision.c | 3 ++\n 4 files changed, 83 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 3bdbf5e..8302402 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -617,6 +617,10 @@ By default, the commits are shown in reverse chronological order.\n \tShow no parents before all of its children are shown, but\n \totherwise show commits in the commit timestamp order.\n \n+--author-date-order::\n+\tShow no parents before all of its children are shown, but\n+\totherwise show commits in the author timestamp order.\n+\n --topo-order::\n \tShow no parents before all of its children are shown, and\n \tavoid showing commits on multiple lines of history\ndiff --git a/commit.c b/commit.c\nindex 8b84ebf..076c1fa 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -510,6 +510,68 @@ struct commit *pop_commit(struct commit_list **stack)\n /* count number of children that have not been emitted */\n define_commit_slab(indegree_slab, int);\n \n+/* record author-date for each commit object */\n+define_commit_slab(author_date_slab, unsigned long);\n+\n+static void record_author_date(struct author_date_slab *author_date,\n+\t\t\t struct commit *commit)\n+{\n+\tconst char *buf, *line_end;\n+\tchar *buffer = NULL;\n+\tstruct ident_split ident;\n+\tchar *date_end;\n+\tunsigned long date;\n+\n+\tif (!commit->buffer) {\n+\t\tunsigned long size;\n+\t\tenum object_type type;\n+\t\tbuffer = read_sha1_file(commit->object.sha1, &type, &size);\n+\t\tif (!buffer)\n+\t\t\treturn;\n+\t}\n+\n+\tfor (buf = commit->buffer ? commit->buffer : buffer;\n+\t buf;\n+\t buf = line_end + 1) {\n+\t\tline_end = strchrnul(buf, '\\n');\n+\t\tif (prefixcmp(buf, \"author \")) {\n+\t\t\tif (!line_end[0] || line_end[1] == '\\n')\n+\t\t\t\treturn; /* end of header */\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (split_ident_line(&ident,\n+\t\t\t\t buf + strlen(\"author \"),\n+\t\t\t\t line_end - (buf + strlen(\"author \"))) ||\n+\t\t !ident.date_begin || !ident.date_end)\n+\t\t\tgoto fail_exit; /* malformed \"author\" line */\n+\t\tbreak;\n+\t}\n+\n+\tdate = strtoul(ident.date_begin, &date_end, 10);\n+\tif (date_end != ident.date_end)\n+\t\tgoto fail_exit; /* malformed date */\n+\t*(author_date_slab_at(author_date, commit)) = date;\n+\n+fail_exit:\n+\tfree(buffer);\n+}\n+\n+static int compare_commits_by_author_date(const void *a_, const void *b_,\n+\t\t\t\t\t void *cb_data)\n+{\n+\tconst struct commit *a = a_, *b = b_;\n+\tstruct author_date_slab *author_date = cb_data;\n+\tunsigned long a_date = *(author_date_slab_at(author_date, a));\n+\tunsigned long b_date = *(author_date_slab_at(author_date, b));\n+\n+\t/* newer commits with larger date first */\n+\tif (a_date < b_date)\n+\t\treturn 1;\n+\telse if (a_date > b_date)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n static int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n {\n \tconst struct commit *a = a_, *b = b_;\n@@ -531,6 +593,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tstruct indegree_slab indegree;\n \tstruct prio_queue queue;\n \tstruct commit *commit;\n+\tstruct author_date_slab author_date;\n \n \tif (!orig)\n \t\treturn;\n@@ -538,6 +601,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \n \tinit_indegree_slab(&indegree);\n \tmemset(&queue, '\\0', sizeof(queue));\n+\n \tswitch (sort_order) {\n \tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\tqueue.compare = NULL;\n@@ -545,12 +609,20 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tcase REV_SORT_BY_COMMIT_DATE:\n \t\tqueue.compare = compare_commits_by_commit_date;\n \t\tbreak;\n+\tcase REV_SORT_BY_AUTHOR_DATE:\n+\t\tinit_author_date_slab(&author_date);\n+\t\tqueue.compare = compare_commits_by_author_date;\n+\t\tqueue.cb_data = &author_date;\n+\t\tbreak;\n \t}\n \n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \t\t*(indegree_slab_at(&indegree, commit)) = 1;\n+\t\t/* also record the author dates, if needed */\n+\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n+\t\t\trecord_author_date(&author_date, commit);\n \t}\n \n \t/* update the indegree */\n@@ -621,6 +693,8 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \n \tclear_indegree_slab(&indegree);\n \tclear_prio_queue(&queue);\n+\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n+\t\tclear_author_date_slab(&author_date);\n }\n \n /* merge-base stuff */\ndiff --git a/commit.h b/commit.h\nindex 247e474..e43dfd0 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -142,7 +142,8 @@ void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);\n \n enum rev_sort_order {\n \tREV_SORT_IN_GRAPH_ORDER = 0,\n-\tREV_SORT_BY_COMMIT_DATE\n+\tREV_SORT_BY_COMMIT_DATE,\n+\tREV_SORT_BY_AUTHOR_DATE\n };\n \n /*\ndiff --git a/revision.c b/revision.c\nindex 966ebbc..12d9b64 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1393,6 +1393,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--author-date-order\")) {\n+\t\trevs->sort_order = REV_SORT_BY_AUTHOR_DATE;\n+\t\trevs->topo_order = 1;\n \t} else if (!prefixcmp(arg, \"--early-output\")) {\n \t\tint count = 100;\n \t\tswitch (arg[14]) {\n-- \n1.8.3.1-494-g51b8af5\n"},{"id":"221507","messageId":"7v61x8tw0a.fsf@alter.siamese.dyndns.org","threadId":"34028","inReplyTo":"20130610184918.GC2084@sigill.intra.peff.net","subject":"Re: [PATCH v2 4/4] log: --author-date-order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-06-20T19:36:21Z","receivedAt":"2013-06-20T19:36:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> Or we could extend parse_commit() API to take an optional commit\n>> info slab to store not just author date but other non-essential\n>> stuff like people's names, and we arrange that extended API to be\n>> triggered when we know --author-date-order is in effect?\n>\n> I like the latter option. It takes a non-trivial amount of time to load\n> the commits from disk, and now we are potentially doing it 2 or 3 times\n> for a run (once to parse, once to get the author info for topo-sort, and\n> possibly later to show it if --pretty is given; though I did not check\n> and maybe we turn off save_commit_buffer with --pretty). It would be\n> nice to have an extended parse_object that handled that. I'm not sure of\n> the interface. Maybe variadic with pairs of type/slab, like:\n>\n> parse_commit_extended(commit,\n> PARSE_COMMIT_AUTHORDATE, &authordate_slab,\n> PARSE_COMMIT_DONE);\n>\n> ?\n\nWhat I had in mind actually was a custom slab tailored for each\ncaller that is an array of struct. If the caller is interested in\nauthordate and authorname, instead of populating two separate\nauthordate_slab and authorname_slab, the caller declares a\n\n\tstruct {\n \tunsigned long date;\n char name[FLEX_ARRAY];\n\t} author_info;\n\nprepares author_info_slab, and use your commit_parser API to fill\nthem.\n"},{"id":"221511","messageId":"20130620201650.GB31364@sigill.intra.peff.net","threadId":"34028","inReplyTo":"7v61x8tw0a.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 4/4] log: --author-date-order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-06-20T20:16:50Z","receivedAt":"2013-06-20T20:16:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 20, 2013 at 12:36:21PM -0700, Junio C Hamano wrote:\n\n> > I like the latter option. It takes a non-trivial amount of time to load\n> > the commits from disk, and now we are potentially doing it 2 or 3 times\n> > for a run (once to parse, once to get the author info for topo-sort, and\n> > possibly later to show it if --pretty is given; though I did not check\n> > and maybe we turn off save_commit_buffer with --pretty). It would be\n> > nice to have an extended parse_object that handled that. I'm not sure of\n> > the interface. Maybe variadic with pairs of type/slab, like:\n> >\n> > parse_commit_extended(commit,\n> > PARSE_COMMIT_AUTHORDATE, &authordate_slab,\n> > PARSE_COMMIT_DONE);\n> >\n> > ?\n> \n> What I had in mind actually was a custom slab tailored for each\n> caller that is an array of struct. If the caller is interested in\n> authordate and authorname, instead of populating two separate\n> authordate_slab and authorname_slab, the caller declares a\n> \n> \tstruct {\n> \tunsigned long date;\n> char name[FLEX_ARRAY];\n> \t} author_info;\n> \n> prepares author_info_slab, and use your commit_parser API to fill\n> them.\n\nYes, I think it is nicer to stay in one slab if you have multiple\nvalues, but it means more custom code for the caller. If the\ncommit_parser API is nice, it should not be that much code, though.\n\nIt does make it harder to support arbitrary combinations directly in\nparse_commit. If a caller wants to also parse_commit and use the same\nbuffer to pick out its custom information, I think we'd need to do one\nof:\n\n 1. Give parse_commit a callback, so that the callback can pick out the\n data it wants while parse_commit has the commit buffer in memory.\n E.g.:\n\n void grab_author_info(const char *buf, unsigned long len, void *data)\n {\n struct author_info *ai = data;\n /* fill fields from buffer */\n }\n\n ...\n parse_commit_extra(commit, grab_author_info,\n slab_at(&author_slab, commit));\n\n 2. Teach parse_commit to operate not only on a raw commit object, but\n also on the commit_parser API. Like:\n\n struct commit_parser parser = {0};\n\n /* actually open the object and start our incremental parser */\n init_commit_parser(&parser, commit);\n\n /* fill in parents, date, etc, as parse_commit does now */\n parse_commit_from_parser(commit, &parser);\n\n /* fill in whatever extra data we are interested in */\n *slab_at(&slab, commit) = get_author_date(&parser);\n\n /* done, drop the buffer */\n close_commit_parser(&parser);\n\nThe latter would need to handle transferring ownership of the buffer to\n\"struct commit\" from \"struct commit_parser\" when save_commit_buffer is\nturned off.\n\nI think we're a bit high-level now to be making such decisions, though,\nas we do not even have such a commit_parser API.\n\n-Peff\n"}]}