From 08f704f294e4a3525b405c2cb1f4ee85e73fd92c Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 6 Jun 2013 16:07:14 -0700 Subject: toposort: rename "lifo" field The primary invariant of sort_in_topological_order() is that a parent commit is not emitted until all children of it are. When traversing a forked history like this with "git log C E": A----B----C \ D----E we ensure that A is emitted after all of B, C, D, and E are done, B has to wait until C is done, and D has to wait until E is done. In some applications, however, we would further want to control how these child commits B, C, D and E on two parallel ancestry chains are shown. Most of the time, we would want to see C and B emitted together, and then E and D, and finally A (i.e. the --topo-order output). The "lifo" parameter of the sort_in_topological_order() function is used to control this behaviour. We start the traversal by knowing two commits, C and E. While keeping in mind that we also need to inspect E later, we pick C first to inspect, and we notice and record that B needs to be inspected. By structuring the "work to be done" set as a LIFO stack, we ensure that B is inspected next, before other in-flight commits we had known that we will need to inspect, e.g. E. When showing in --date-order, we would want to see commits ordered by timestamps, i.e. show C, E, B and D in this order before showing A, possibly mixing commits from two parallel histories together. When "lifo" parameter is set to false, the function keeps the "work to be done" set sorted in the date order to realize this semantics. After inspecting C, we add B to the "work to be done" set, but the next commit we inspect from the set is E which is newer than B. The name "lifo", however, is too strongly tied to the way how the function implements its behaviour, and does not describe what the behaviour _means_. Replace this field with an enum rev_sort_order, with two possible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and update the existing code. The mechanical replacement rule is: "lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE" "lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER" Signed-off-by: Junio C Hamano --- commit.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index f97456ddfa..11b9635df2 100644 --- a/commit.c +++ b/commit.c @@ -512,7 +512,7 @@ define_commit_slab(indegree_slab, int); /* * Performs an in-place topological sort on the list supplied. */ -void sort_in_topological_order(struct commit_list ** list, int lifo) +void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order) { struct commit_list *next, *orig = *list; struct commit_list *work, **insert; @@ -561,7 +561,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo) } /* process the list in topological order */ - if (!lifo) + if (sort_order != REV_SORT_IN_GRAPH_ORDER) commit_list_sort_by_date(&work); pptr = list; @@ -588,10 +588,14 @@ void sort_in_topological_order(struct commit_list ** list, int lifo) * guaranteeing topological order. */ if (--(*pi) == 1) { - if (!lifo) + switch (sort_order) { + case REV_SORT_BY_COMMIT_DATE: commit_list_insert_by_date(parent, &work); - else + break; + default: /* REV_SORT_IN_GRAPH_ORDER */ commit_list_insert(parent, &work); + break; + } } } /* -- cgit v1.2.1 From da24b1044f7dc85cda52d6423f5a794a7074fbf8 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 6 Jun 2013 21:58:12 -0700 Subject: sort-in-topological-order: use prio-queue Use the prio-queue data structure to implement a priority queue of commits sorted by committer date, when handling --date-order. The structure can also be used as a simple LIFO stack, which is a good match for --topo-order processing. Signed-off-by: Junio C Hamano --- commit.c | 75 +++++++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 44 insertions(+), 31 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 11b9635df2..8b84ebf2b7 100644 --- a/commit.c +++ b/commit.c @@ -9,6 +9,7 @@ #include "gpg-interface.h" #include "mergesort.h" #include "commit-slab.h" +#include "prio-queue.h" static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **); @@ -509,21 +510,42 @@ struct commit *pop_commit(struct commit_list **stack) /* count number of children that have not been emitted */ define_commit_slab(indegree_slab, int); +static int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused) +{ + const struct commit *a = a_, *b = b_; + /* newer commits with larger date first */ + if (a->date < b->date) + return 1; + else if (a->date > b->date) + return -1; + return 0; +} + /* * Performs an in-place topological sort on the list supplied. */ -void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order) +void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order) { struct commit_list *next, *orig = *list; - struct commit_list *work, **insert; struct commit_list **pptr; struct indegree_slab indegree; + struct prio_queue queue; + struct commit *commit; if (!orig) return; *list = NULL; init_indegree_slab(&indegree); + memset(&queue, '\0', sizeof(queue)); + switch (sort_order) { + default: /* REV_SORT_IN_GRAPH_ORDER */ + queue.compare = NULL; + break; + case REV_SORT_BY_COMMIT_DATE: + queue.compare = compare_commits_by_commit_date; + break; + } /* Mark them and clear the indegree */ for (next = orig; next; next = next->next) { @@ -533,7 +555,7 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s /* update the indegree */ for (next = orig; next; next = next->next) { - struct commit_list * parents = next->item->parents; + struct commit_list *parents = next->item->parents; while (parents) { struct commit *parent = parents->item; int *pi = indegree_slab_at(&indegree, parent); @@ -551,30 +573,28 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s * * the tips serve as a starting set for the work queue. */ - work = NULL; - insert = &work; for (next = orig; next; next = next->next) { struct commit *commit = next->item; if (*(indegree_slab_at(&indegree, commit)) == 1) - insert = &commit_list_insert(commit, insert)->next; + prio_queue_put(&queue, commit); } - /* process the list in topological order */ - if (sort_order != REV_SORT_IN_GRAPH_ORDER) - commit_list_sort_by_date(&work); + /* + * This is unfortunate; the initial tips need to be shown + * in the order given from the revision traversal machinery. + */ + if (sort_order == REV_SORT_IN_GRAPH_ORDER) + prio_queue_reverse(&queue); + + /* We no longer need the commit list */ + free_commit_list(orig); pptr = list; *list = NULL; - while (work) { - struct commit *commit; - struct commit_list *parents, *work_item; - - work_item = work; - work = work_item->next; - work_item->next = NULL; + while ((commit = prio_queue_get(&queue)) != NULL) { + struct commit_list *parents; - commit = work_item->item; for (parents = commit->parents; parents ; parents = parents->next) { struct commit *parent = parents->item; int *pi = indegree_slab_at(&indegree, parent); @@ -587,27 +607,20 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s * when all their children have been emitted thereby * guaranteeing topological order. */ - if (--(*pi) == 1) { - switch (sort_order) { - case REV_SORT_BY_COMMIT_DATE: - commit_list_insert_by_date(parent, &work); - break; - default: /* REV_SORT_IN_GRAPH_ORDER */ - commit_list_insert(parent, &work); - break; - } - } + if (--(*pi) == 1) + prio_queue_put(&queue, parent); } /* - * work_item is a commit all of whose children - * have already been emitted. we can emit it now. + * all children of commit have already been + * emitted. we can emit it now. */ *(indegree_slab_at(&indegree, commit)) = 0; - *pptr = work_item; - pptr = &work_item->next; + + pptr = &commit_list_insert(commit, pptr)->next; } clear_indegree_slab(&indegree); + clear_prio_queue(&queue); } /* merge-base stuff */ -- cgit v1.2.1 From 81c6b38b67019eff48e8e5c324bb77f6c796c0b5 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 7 Jun 2013 10:35:54 -0700 Subject: log: --author-date-order Sometimes people would want to view the commits in parallel histories in the order of author dates, not committer dates. Teach "topo-order" sort machinery to do so, using a commit-info slab to record the author dates of each commit, and prio-queue to sort them. Signed-off-by: Junio C Hamano --- commit.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 74 insertions(+) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 8b84ebf2b7..076c1fa606 100644 --- a/commit.c +++ b/commit.c @@ -510,6 +510,68 @@ struct commit *pop_commit(struct commit_list **stack) /* count number of children that have not been emitted */ define_commit_slab(indegree_slab, int); +/* record author-date for each commit object */ +define_commit_slab(author_date_slab, unsigned long); + +static void record_author_date(struct author_date_slab *author_date, + struct commit *commit) +{ + const char *buf, *line_end; + char *buffer = NULL; + struct ident_split ident; + char *date_end; + unsigned long date; + + if (!commit->buffer) { + unsigned long size; + enum object_type type; + buffer = read_sha1_file(commit->object.sha1, &type, &size); + if (!buffer) + return; + } + + for (buf = commit->buffer ? commit->buffer : buffer; + buf; + buf = line_end + 1) { + line_end = strchrnul(buf, '\n'); + if (prefixcmp(buf, "author ")) { + if (!line_end[0] || line_end[1] == '\n') + return; /* end of header */ + continue; + } + if (split_ident_line(&ident, + buf + strlen("author "), + line_end - (buf + strlen("author "))) || + !ident.date_begin || !ident.date_end) + goto fail_exit; /* malformed "author" line */ + break; + } + + date = strtoul(ident.date_begin, &date_end, 10); + if (date_end != ident.date_end) + goto fail_exit; /* malformed date */ + *(author_date_slab_at(author_date, commit)) = date; + +fail_exit: + free(buffer); +} + +static int compare_commits_by_author_date(const void *a_, const void *b_, + void *cb_data) +{ + const struct commit *a = a_, *b = b_; + struct author_date_slab *author_date = cb_data; + unsigned long a_date = *(author_date_slab_at(author_date, a)); + unsigned long b_date = *(author_date_slab_at(author_date, b)); + + /* newer commits with larger date first */ + if (a_date < b_date) + return 1; + else if (a_date > b_date) + return -1; + return 0; +} + static int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused) { const struct commit *a = a_, *b = b_; @@ -531,6 +593,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so struct indegree_slab indegree; struct prio_queue queue; struct commit *commit; + struct author_date_slab author_date; if (!orig) return; @@ -538,6 +601,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so init_indegree_slab(&indegree); memset(&queue, '\0', sizeof(queue)); + switch (sort_order) { default: /* REV_SORT_IN_GRAPH_ORDER */ queue.compare = NULL; @@ -545,12 +609,20 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so case REV_SORT_BY_COMMIT_DATE: queue.compare = compare_commits_by_commit_date; break; + case REV_SORT_BY_AUTHOR_DATE: + init_author_date_slab(&author_date); + queue.compare = compare_commits_by_author_date; + queue.cb_data = &author_date; + break; } /* Mark them and clear the indegree */ for (next = orig; next; next = next->next) { struct commit *commit = next->item; *(indegree_slab_at(&indegree, commit)) = 1; + /* also record the author dates, if needed */ + if (sort_order == REV_SORT_BY_AUTHOR_DATE) + record_author_date(&author_date, commit); } /* update the indegree */ @@ -621,6 +693,8 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so clear_indegree_slab(&indegree); clear_prio_queue(&queue); + if (sort_order == REV_SORT_BY_AUTHOR_DATE) + clear_author_date_slab(&author_date); } /* merge-base stuff */ -- cgit v1.2.1