{"thread":{"id":"1055","subject":"[PATCH 1/1] Add a topological sort procedure to commit.c","startedAt":"2005-06-30T05:58:21Z","lastAt":"2005-06-30T07:36:40Z","messageCount":5,"participants":["Jon Seymour","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"5438","messageId":"20050630055821.1329.qmail@blackcubes.dyndns.org","threadId":"1055","inReplyTo":null,"subject":"[PATCH 1/1] Add a topological sort procedure to commit.c","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-30T05:58:21Z","receivedAt":"2005-06-30T05:58:21Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis patch introduces an in-place topological sort procedure to commit.c\n\nGiven a list of commits, sort_in_topological_order() will perform an in-place\ntopological sort of that list.\n\nThe invariant that applies to the resulting list is:\n\n\ta reachable from b => ord(b) < ord(a)\n\nThis invariant is weaker than the --merge-order invariant, but is cheaper\nto calculate (assuming the list has been identified) and will serve any\npurpose where only a minimal topological order guarantee is required.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\nNote: this patch currently has no observable consequences since nothing\nin this patch calls it. A future patch will use this algorithm to provide\nan O(n) bisection algorithm as a suggested replacement for the\nexisting O(n^2) bisection algorithm.\n---\n\n commit.c |   82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h |    5 ++++\n 2 files changed, 87 insertions(+), 0 deletions(-)\n\n9beb76a20443b8d5ee6010bf0bd55344e5b39546\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -3,6 +3,12 @@\n #include \"commit.h\"\n #include \"cache.h\"\n \n+struct sort_node\n+{\n+\tunsigned int indegree;\n+\tstruct commit_list * list_item;\n+};\n+\n const char *commit_type = \"commit\";\n \n enum cmit_fmt get_commit_format(const char *arg)\n@@ -346,3 +352,79 @@ int count_parents(struct commit * commit\n         return count;\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)\n+{\n+\tstruct commit_list * next = *list;\n+\tstruct commit_list * work = NULL;\n+\tstruct commit_list ** pptr = list;\n+\tstruct sort_node * nodes;\n+\tstruct sort_node * next_nodes;\n+\tint count = 0;\n+\n+\t/* determine the size of the list */\n+\twhile (next) {\n+\t\tnext = next->next;\n+\t\tcount++;\n+\t}\n+\t/* allocate an array to help sort the list */\n+\tnodes = xmalloc(sizeof(*nodes) * count);\n+\t/* link the list to the array */\n+\tnext_nodes = nodes;\n+\tnext=*list;\n+\twhile (next) {\n+\t\tnext_nodes->list_item = next;\n+\t\tnext->item->object.util = next_nodes;\n+\t\tnext_nodes++;\n+\t\tnext = next->next;\n+\t}\n+\t/* update the indegree */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct commit_list * parents = next->item->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn)\n+\t\t\t\tpn->indegree++;\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* find the roots */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct sort_node * node = (struct sort_node *)next->item->object.util;\n+\n+\t\tif (node->indegree == 0) {\n+\t\t\tcommit_list_insert(next->item, &work);\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* process the list in topological order */\n+\twhile (work) {\n+\t\tstruct commit * work_item = pop_commit(&work);\n+\t\tstruct sort_node * work_node = (struct sort_node *)work_item->object.util;\n+\t\tstruct commit_list * parents = work_item->parents;\n+\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn) {\n+\t\t\t\tpn->indegree--;\n+\t\t\t\tif (!pn->indegree) \n+\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t}\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\t*pptr = work_node->list_item;\n+\t\twork_node->list_item->next = NULL;\n+\t\tpptr = &(*pptr)->next;\n+\t\twork_item->object.util = NULL;\n+\t}\n+\tfree(nodes);\n+}\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -55,4 +55,9 @@ struct commit *pop_most_recent_commit(st\n struct commit *pop_commit(struct commit_list **stack);\n \n int count_parents(struct commit * commit);\n+\n+/*\n+ * Performs an in-place topological sort of list supplied.\n+ */\n+void sort_in_topological_order(struct commit_list ** list);\n #endif /* COMMIT_H */\n------------\n"},{"id":"5440","messageId":"7v1x6k5oau.fsf@assigned-by-dhcp.cox.net","threadId":"1055","inReplyTo":"20050630055821.1329.qmail@blackcubes.dyndns.org","subject":"Re: [PATCH 1/1] Add a topological sort procedure to commit.c","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-30T06:52:41Z","receivedAt":"2005-06-30T06:52:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Interesting idea.  Help me understand the code.\n\n@@ -346,3 +352,79 @@ int count_parents(struct commit * commit\n         return count;\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)\n+{\n+\t...\n+\t/* allocate an array to help sort the list */\n+\tnodes = xmalloc(sizeof(*nodes) * count);\n+\t/* link the list to the array */\n+\tnext_nodes = nodes;\n+\tnext=*list;\n+\twhile (next) {\n+\t\tnext_nodes->list_item = next;\n+\t\tnext->item->object.util = next_nodes;\n+\t\tnext_nodes++;\n+\t\tnext = next->next;\n+\t}\n+\t/* update the indegree */\n\nDon't you want to initialize before update?  Either in the above\nwhile(next) loop or just after xmalloc() with a single\nmemset(0), or xcalloc()?\n\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct commit_list * parents = next->item->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn)\n+\t\t\t\tpn->indegree++;\n\nI take this to mean that not all commits are on *list and such\ncommits not on *list have object.util set to NULL.  Who\ninitializes object.util (this is not a nitpick but a question as\na user)?   commit.c::lookup_commit() uses memset(0) and when\nsort_in_topological_order() function is called everybody (not\nlimited to the ones on *list but all commits reachable from\nthem) are supposed to have object.util set to NULL?\n\nSo sort_node->indegree means how many children of it are on the\n*list.  Am I reading you correctly so far?\n\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* find the roots */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct sort_node * node = (struct sort_node *)next->item->object.util;\n+\n+\t\tif (node->indegree == 0) {\n+\t\t\tcommit_list_insert(next->item, &work);\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n\nYou say \"find the roots\", but this sounds more like finding the\ntips of forests.  You are finding people without children,\nright (again, not a nitpick but trying to understand the code)?\n\n+\t/* process the list in topological order */\n+\twhile (work) {\n+\t\tstruct commit * work_item = pop_commit(&work);\n+\t\tstruct sort_node * work_node = (struct sort_node *)work_item->object.util;\n+\t\tstruct commit_list * parents = work_item->parents;\n+\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn) {\n+\t\t\t\tpn->indegree--;\n+\t\t\t\tif (!pn->indegree) \n+\t\t\t\t\tcommit_list_insert(parent, &work);\n\nAnd when you look at each parent, and push the parent into work\nqueue when you have seen all its children.\n\n+\t\t\t}\n+\t\t\tparents=parents->next;\n+\t\t}\n\nAnd at this point work_item, popped from your work queue, is\nguaranteed to be a commit all of whose children have been\nprocessed (i.e. pushed into the original *list).\n\n+\t\t*pptr = work_node->list_item;\n+\t\twork_node->list_item->next = NULL;\n+\t\tpptr = &(*pptr)->next;\n+\t\twork_item->object.util = NULL;\n\n+\t}\n+\tfree(nodes);\n+}\n\nBy the way, you seem to be using \"git format-patch\".  Do you\nwant to help me pushing it upstream ;-)?\n"},{"id":"5441","messageId":"2cfc403205063000009d149f5@mail.gmail.com","threadId":"1055","inReplyTo":"7v1x6k5oau.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 1/1] Add a topological sort procedure to commit.c","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-30T07:00:40Z","receivedAt":"2005-06-30T07:00:40Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/30/05, Junio C Hamano <junkio@cox.net> wrote:\n> Interesting idea.  Help me understand the code.\n> \n> @@ -346,3 +352,79 @@ int count_parents(struct commit * commit\n>          return count;\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)\n> +{\n> +       ...\n> +       /* allocate an array to help sort the list */\n> +       nodes = xmalloc(sizeof(*nodes) * count);\n> +       /* link the list to the array */\n> +       next_nodes = nodes;\n> +       next=*list;\n> +       while (next) {\n> +               next_nodes->list_item = next;\n> +               next->item->object.util = next_nodes;\n> +               next_nodes++;\n> +               next = next->next;\n> +       }\n> +       /* update the indegree */\n> \n> Don't you want to initialize before update?  Either in the above\n> while(next) loop or just after xmalloc() with a single\n> memset(0), or xcalloc()?\n\nOops, yes I do.\n\n> \n> +       next=*list;\n> +       while (next) {\n> +               struct commit_list * parents = next->item->parents;\n> +               while (parents) {\n> +                       struct commit * parent=parents->item;\n> +                       struct sort_node * pn = (struct sort_node *)parent->object.util;\n> +\n> +                       if (pn)\n> +                               pn->indegree++;\n> \n> I take this to mean that not all commits are on *list and such\n> commits not on *list have object.util set to NULL.  Who\n> initializes object.util (this is not a nitpick but a question as\n> a user)?   commit.c::lookup_commit() uses memset(0) and when\n> sort_in_topological_order() function is called everybody (not\n> limited to the ones on *list but all commits reachable from\n> them) are supposed to have object.util set to NULL?\n> \n\nYes, that is the current assumption. Alternatively, I could save the current\nversion of object.util in the temporary structure and restore it when done.\nPerhaps I'll do that.\n\n> So sort_node->indegree means how many children of it are on the\n> *list.  Am I reading you correctly so far?\n\nCorrect.\n\n> \n> +                       parents=parents->next;\n> +               }\n> +               next=next->next;\n> +       }\n> +       /* find the roots */\n> +       next=*list;\n> +       while (next) {\n> +               struct sort_node * node = (struct sort_node *)next->item->object.util;\n> +\n> +               if (node->indegree == 0) {\n> +                       commit_list_insert(next->item, &work);\n> +               }\n> +               next=next->next;\n> +       }\n> \n> You say \"find the roots\", but this sounds more like finding the\n> tips of forests.  You are finding people without children,\n> right (again, not a nitpick but trying to understand the code)?\n\nTrue. Should reword the comment to find the tips.\n\n> \n> +       /* process the list in topological order */\n> +       while (work) {\n> +               struct commit * work_item = pop_commit(&work);\n> +               struct sort_node * work_node = (struct sort_node *)work_item->object.util;\n> +               struct commit_list * parents = work_item->parents;\n> +\n> +               while (parents) {\n> +                       struct commit * parent=parents->item;\n> +                       struct sort_node * pn = (struct sort_node *)parent->object.util;\n> +\n> +                       if (pn) {\n> +                               pn->indegree--;\n> +                               if (!pn->indegree)\n> +                                       commit_list_insert(parent, &work);\n> \n> And when you look at each parent, and push the parent into work\n> queue when you have seen all its children.\n\nCorrect.\n\n> \n> +                       }\n> +                       parents=parents->next;\n> +               }\n> \n> And at this point work_item, popped from your work queue, is\n> guaranteed to be a commit all of whose children have been\n> processed (i.e. pushed into the original *list).\n\nYep.\n\n> \n> +               *pptr = work_node->list_item;\n> +               work_node->list_item->next = NULL;\n> +               pptr = &(*pptr)->next;\n> +               work_item->object.util = NULL;\n> \n> +       }\n> +       free(nodes);\n> +}\n> \n> By the way, you seem to be using \"git format-patch\".  Do you\n> want to help me pushing it upstream ;-)?\n\nYep, but can you fix the PATCH 1/1 thing first :-)\n\nI'll rework the patch, incorporating answers to your questions into the comment.\n\nRegards,\n\njon.\n"},{"id":"5442","messageId":"7vwtoc48rh.fsf@assigned-by-dhcp.cox.net","threadId":"1055","inReplyTo":"2cfc403205063000009d149f5@mail.gmail.com","subject":"Re: [PATCH 1/1] Add a topological sort procedure to commit.c","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-30T07:13:38Z","receivedAt":"2005-06-30T07:13:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JS\" == Jon Seymour <jon.seymour@gmail.com> writes:\n\n>> By the way, you seem to be using \"git format-patch\".  Do you\n>> want to help me pushing it upstream ;-)?\n\nJS> Yep, but can you fix the PATCH 1/1 thing first :-)\n\nFix how?  Only special case 1/1?\n\nThat is easy to do, so I would do it, but on the other hand I\nalways end up editing the line anyway (my [PATCH 2/3] is often\noriginally [PATCH 4/7] because I have more than one series since\nforked from upstream, and I would need to move it to Subject:\nline), so it would not help very much, at least in my case.\n"},{"id":"5444","messageId":"7vll4s47p3.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1055","inReplyTo":"7vwtoc48rh.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] git-format-patch: Prepare patches for e-mail submission.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-30T07:36:40Z","receivedAt":"2005-06-30T07:36:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is the script I use to prepare patches for e-mail submission.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n*** Jon, I made it by default not to say [PATCH N/M] for any M,\n*** and you can turn it on with --numbered flag.   Even with\n*** --numbered, \" N/M\" is not shown if M==1.\n\n Makefile                |    3 +\n git-format-patch-script |  122 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 124 insertions(+), 1 deletions(-)\n create mode 100755 git-format-patch-script\n\n16daa73282d5aa1cc7d227945aea193553fdfaad\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -25,7 +25,8 @@ SCRIPTS=git git-apply-patch-script git-m\n \tgit-fetch-script git-status-script git-commit-script \\\n \tgit-log-script git-shortlog git-cvsimport-script git-diff-script \\\n \tgit-reset-script git-add-script git-checkout-script git-clone-script \\\n-\tgitk git-cherry git-rebase-script git-relink-script\n+\tgitk git-cherry git-rebase-script git-relink-script \\\n+\tgit-format-patch-script\n \n PROG=   git-update-cache git-diff-files git-init-db git-write-tree \\\n \tgit-read-tree git-commit-tree git-cat-file git-fsck-cache \\\ndiff --git a/git-format-patch-script b/git-format-patch-script\nnew file mode 100755\n--- /dev/null\n+++ b/git-format-patch-script\n@@ -0,0 +1,122 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Junio C Hamano\n+#\n+\n+usage () {\n+    echo >&2 \"usage: $0\"' [-n] [-o dir] [-<diff options>...] upstream [ our-head ]\n+\n+Prepare each commit with its patch since our-head forked from upstream,\n+one file per patch, for e-mail submission.  Each output file is\n+numbered sequentially from 1, and uses the first line of the commit\n+message (massaged for pathname safety) as the filename.\n+\n+When -o is specified, output files are created in that directory; otherwise in\n+the current working directory.\n+\n+When -n is specified, instead of \"[PATCH] Subject\", the first line is formatted\n+as \"[PATCH N/M] Subject\", unless you have only one patch.\n+'\n+    exit 1\n+}\n+\n+diff_opts=\n+IFS='\n+'\n+LF='\n+'\n+outdir=./\n+\n+while case \"$#\" in 0) break;; esac\n+do\n+    case \"$1\" in\n+    -n|--n|--nu|--num|--numb|--numbe|--number|--numbere|--numbered)\n+    numbered=t ;;\n+    -o=*|--o=*|--ou=*|--out=*|--outp=*|--outpu=*|--output=*|--output-=*|\\\n+    --output-d=*|--output-di=*|--output-dir=*|--output-dire=*|\\\n+    --output-direc=*|--output-direct=*|--output-directo=*|\\\n+    --output-director=*|--output-directory=*)\n+    outdir=`expr \"$1\" : '-[^=]*=\\(.*\\)'` ;;\n+    -o|--o|--ou|--out|--outp|--outpu|--output|--output-|--output-d|\\\n+    --output-di|--output-dir|--output-dire|--output-direc|--output-direct|\\\n+    --output-directo|--output-director|--output-directory)\n+    case \"$#\" in 1) usage ;; esac; shift\n+    outdir=\"$1\" ;;\n+    -*)\tdiff_opts=\"$diff_opts$LF$1\" ;;\n+    *) break ;;\n+    esac\n+    shift\n+done\n+\n+case \"$#\" in\n+2)    linus=\"$1\" junio=\"$2\" ;;\n+1)    linus=\"$1\" junio=HEAD ;;\n+*)    usage ;;\n+esac\n+\n+case \"$outdir\" in\n+*/) ;;\n+*) outdir=\"$outdir/\" ;;\n+esac\n+test -d \"$outdir\" || mkdir -p \"$outdir\" || exit\n+\n+tmp=.tmp-series$$\n+trap 'rm -f $tmp-*' 0 1 2 3 15\n+\n+series=$tmp-series\n+\n+titleScript='\n+\t1,/^$/d\n+\t: loop\n+\t/^$/b loop\n+\ts/[^-a-z.A-Z_0-9]/-/g\n+        s/\\.\\.\\.*/\\./g\n+\ts/\\.*$//\n+\ts/--*/-/g\n+\ts/^-//\n+\ts/-$//\n+\ts/$/./\n+\tq\n+'\n+\n+_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'\n+_x40=\"$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40\"\n+stripCommitHead='/^'\"$_x40\"' (from '\"$_x40\"')$/d'\n+\n+git-rev-list \"$junio\" \"^$linus\" >$series\n+total=`wc -l <$series`\n+i=$total\n+while read commit\n+do\n+    title=`git-cat-file commit \"$commit\" | sed -e \"$titleScript\"`\n+    case \"$numbered\" in\n+    '') num= ;;\n+    *)\n+\tcase $total in\n+\t1) num= ;;\n+\t*) num=' '`printf \"%d/%d\" $i $total` ;;\n+\tesac\n+    esac\n+    file=`printf '%04d-%stxt' $i \"$title\"`\n+    i=`expr \"$i\" - 1`\n+    echo \"$file\"\n+    {\n+\tmailScript='\n+\t1,/^$/d\n+\t: loop\n+\t/^$/b loop\n+\ts|^|[PATCH'\"$num\"'] |\n+\t: body\n+\tp\n+\tn\n+\tb body'\n+\n+\tgit-cat-file commit \"$commit\" | sed -ne \"$mailScript\"\n+\techo '---'\n+\techo\n+\tgit-diff-tree -p $diff_opts \"$commit\" | git-apply --stat --summary\n+\techo\n+\tgit-diff-tree -p $diff_opts \"$commit\" | sed -e \"$stripCommitHead\"\n+\techo '------------'\n+    } >\"$outdir$file\"\n+done <$series\n------------\n"}]}