Modifies the topo-order code to keep track of the first child, using a heuristic. The heuristic works by assigning a (depth) level to all nodes. The first child is the node of which this node is a parent of and has the lowest level. Then it cuts all the links that are not the first child, resulting in a tree.
It also uses the level to sort the nodes: trying to keep descendent line (of a merge) together as a group. Add commandline option "--tree" to use this new feature. Signed-off-by: Micha Nelissen <[email protected]> --- commit.c | 136 +++++++++++++++++++++++++++++++++++++++++++++++------ commit.h | 1 + revision.c | 4 ++ 3 files changed, 127 insertions(+), 14 deletions(-) diff --git commit.c commit.c index a5333c7ac6..340757adc2 100644 --- commit.c +++ commit.c @@ -662,7 +662,12 @@ struct commit *pop_commit(struct commit_list **stack) */ /* count number of children that have not been emitted */ -define_commit_slab(indegree_slab, int); +struct indegree { + unsigned short indegree; + unsigned short level; /* first level this commit has been seen at */ +}; +define_commit_slab(indegree_slab, struct indegree); +define_commit_slab(first_child_slab, struct commit *); define_commit_slab(author_date_slab, timestamp_t); @@ -708,6 +713,22 @@ int compare_commits_by_author_date(const void *a_, const void *b_, return 0; } +static int compare_commits_by_tree_level(const void *a_, const void *b_, + void *cb_data) +{ + const struct commit *a = a_, *b = b_; + struct indegree_slab *indegree = cb_data; + unsigned short a_level = indegree_slab_at(indegree, a)->level; + unsigned short b_level = indegree_slab_at(indegree, b)->level; + + /* deepest tree level commits first */ + if (a_level < b_level) + return 1; + else if (a_level > b_level) + return -1; + return 0; +} + int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused) { const struct commit *a = a_, *b = b_; @@ -745,6 +766,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so struct commit_list *next, *orig = *list; struct commit_list **pptr; struct indegree_slab indegree; + struct first_child_slab first_child; struct prio_queue queue; struct commit *commit; struct author_date_slab author_date; @@ -760,6 +782,11 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so default: /* REV_SORT_IN_GRAPH_ORDER */ queue.compare = NULL; break; + case REV_SORT_IN_TREE_ORDER: + init_first_child_slab(&first_child); + queue.compare = compare_commits_by_tree_level; + queue.cb_data = &indegree; + break; case REV_SORT_BY_COMMIT_DATE: queue.compare = compare_commits_by_commit_date; break; @@ -773,7 +800,8 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so /* Mark them and clear the indegree */ for (next = orig; next; next = next->next) { struct commit *commit = next->item; - *(indegree_slab_at(&indegree, commit)) = 1; + struct indegree *pi = indegree_slab_at(&indegree, commit); + pi->indegree = 0, pi->level = 0; /* also record the author dates, if needed */ if (sort_order == REV_SORT_BY_AUTHOR_DATE) record_author_date(&author_date, commit); @@ -782,13 +810,12 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so /* update the indegree */ for (next = orig; next; next = next->next) { struct commit_list *parents = next->item->parents; - while (parents) { + for (; parents; parents = parents->next) { struct commit *parent = parents->item; - int *pi = indegree_slab_at(&indegree, parent); - - if (*pi) - (*pi)++; - parents = parents->next; + struct indegree *pi = indegree_slab_peek(&indegree, parent); + if (!pi) + continue; + pi->indegree++; } } @@ -801,9 +828,12 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so */ for (next = orig; next; next = next->next) { struct commit *commit = next->item; + struct indegree *pi = indegree_slab_at(&indegree, commit); - if (*(indegree_slab_at(&indegree, commit)) == 1) + if (pi->indegree == 0) { + pi->level = 1; prio_queue_put(&queue, commit); + } } /* @@ -820,31 +850,109 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so *list = NULL; while ((commit = prio_queue_get(&queue)) != NULL) { struct commit_list *parents; + unsigned short commit_level, parent_level; + commit_level = parent_level = indegree_slab_at(&indegree, commit)->level; - for (parents = commit->parents; parents ; parents = parents->next) { + for (parents = commit->parents; parents; parents = parents->next) { struct commit *parent = parents->item; - int *pi = indegree_slab_at(&indegree, parent); + struct indegree *pi = indegree_slab_peek(&indegree, parent); - if (!*pi) + if (!pi) continue; + if (sort_order == REV_SORT_IN_TREE_ORDER) { + struct commit **pfirst_child = + first_child_slab_at(&first_child, parent); + if (*pfirst_child != NULL) { + /* already set a first child, if it is from higher + level than we are, set ourselves as first */ + struct indegree *old_pi = + indegree_slab_at(&indegree, *pfirst_child); + if (old_pi->level >= commit_level) + *pfirst_child = NULL; + } + if (*pfirst_child == NULL) + *pfirst_child = commit; + + if (!pi->level || parent_level < pi->level) { + struct commit_list *gparent_list; + struct commit *gparent = parent; + struct indegree *gpi; + /* mark this 'branch' as this level */ + pi->level = parent_level; + while ((gparent_list = gparent->parents) != NULL) { + gparent = gparent_list->item; + gpi = indegree_slab_peek(&indegree, gparent); + if (!gpi || + (gpi->level && gpi->level < parent_level)) + break; + gpi->level = parent_level; + } + } + if (pi->level >= parent_level) + parent_level = pi->level + 1; + } + /* * parents are only enqueued for emission * when all their children have been emitted thereby * guaranteeing topological order. */ - if (--(*pi) == 1) + if (--pi->indegree == 0) prio_queue_put(&queue, parent); } /* * all children of commit have already been * emitted. we can emit it now. */ - *(indegree_slab_at(&indegree, commit)) = 0; + indegree_slab_at(&indegree, commit)->indegree = 0; pptr = &commit_list_insert(commit, pptr)->next; } + if (sort_order == REV_SORT_IN_TREE_ORDER) { + struct commit *commit, *next_commit; + /* + * go through the commit list to cut all the non-first + * parent-child links, so we get a tree + */ + next = *list; + if (next) { + commit = next->item; + next = next->next; + } + for (next = *list; next; next = next->next, commit = next_commit) { + struct commit_list *parents, **pparents = &commit->parents; + next_commit = next->item; + for (parents = commit->parents; parents; parents = parents->next) { + /* leave link between sequential commits alone because + the level is not 100% to column mapping. level might + be higher due to merges of merges from the same + origin; except if the next commit is on top level + then for sure it's not the same column */ + struct commit *parent = parents->item; + int cut = 1; + if (parent == next_commit) { + struct indegree *pi = + indegree_slab_peek(&indegree, parent); + /* cut as in, allow to cut */ + cut = pi && pi->level == 1; + } + if (cut) { + struct commit **pfirst_child = + first_child_slab_at(&first_child, parent); + cut = commit != *pfirst_child; + } + if (cut) + *pparents = parents->next; + else + pparents = &parents->next; + } + } + + clear_first_child_slab(&first_child); + } + clear_indegree_slab(&indegree); clear_prio_queue(&queue); if (sort_order == REV_SORT_BY_AUTHOR_DATE) diff --git commit.h commit.h index 42728c2906..25b236cb49 100644 --- commit.h +++ commit.h @@ -205,6 +205,7 @@ void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark); enum rev_sort_order { REV_SORT_IN_GRAPH_ORDER = 0, + REV_SORT_IN_TREE_ORDER, REV_SORT_BY_COMMIT_DATE, REV_SORT_BY_AUTHOR_DATE }; diff --git revision.c revision.c index 162d511d46..09074e2c08 100644 --- revision.c +++ revision.c @@ -2031,6 +2031,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg } else if (!strcmp(arg, "--topo-order")) { revs->sort_order = REV_SORT_IN_GRAPH_ORDER; revs->topo_order = 1; + } else if (!strcmp(arg, "--tree")) { + revs->sort_order = REV_SORT_IN_TREE_ORDER; + goto graph; } else if (!strcmp(arg, "--simplify-merges")) { revs->simplify_merges = 1; revs->topo_order = 1; @@ -2227,6 +2230,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg revs->pretty_given = 1; revs->abbrev_commit = 1; } else if (!strcmp(arg, "--graph")) { + graph: revs->topo_order = 1; revs->rewrite_parents = 1; revs->graph = graph_init(revs); -- 2.17.1
