diff options
| -rw-r--r-- | builtin/name-rev.c | 102 | ||||
| -rwxr-xr-x | t/t6120-describe.sh | 2 |
2 files changed, 65 insertions, 39 deletions
diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 6c1e6e9868..a3b796eac4 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -6,6 +6,7 @@ #include "tag.h" #include "refs.h" #include "parse-options.h" +#include "prio-queue.h" #include "sha1-lookup.h" #include "commit-slab.h" @@ -104,52 +105,77 @@ copy_data: return NULL; } -static void name_rev(struct commit *commit, +static void name_rev(struct commit *start_commit, const char *tip_name, timestamp_t taggerdate, int from_tag) { - struct rev_name *name = get_commit_rev_name(commit); - struct commit_list *parents; - int parent_number = 1; - - for (parents = commit->parents; - parents; - parents = parents->next, parent_number++) { - struct commit *parent = parents->item; - const char *new_name; - int generation, distance; - - parse_commit(parent); - if (parent->date < cutoff) - continue; + struct prio_queue queue; + struct commit *commit; + struct commit **parents_to_queue = NULL; + size_t parents_to_queue_nr, parents_to_queue_alloc = 0; + + memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */ + prio_queue_put(&queue, start_commit); + + while ((commit = prio_queue_get(&queue))) { + struct rev_name *name = get_commit_rev_name(commit); + struct commit_list *parents; + int parent_number = 1; + + parents_to_queue_nr = 0; + + for (parents = commit->parents; + parents; + parents = parents->next, parent_number++) { + struct commit *parent = parents->item; + const char *new_name; + int generation, distance; + + parse_commit(parent); + if (parent->date < cutoff) + continue; - if (parent_number > 1) { - size_t len; + if (parent_number > 1) { + size_t len; + + strip_suffix(name->tip_name, "^0", &len); + if (name->generation > 0) + new_name = xstrfmt("%.*s~%d^%d", + (int)len, + name->tip_name, + name->generation, + parent_number); + else + new_name = xstrfmt("%.*s^%d", (int)len, + name->tip_name, + parent_number); + generation = 0; + distance = name->distance + MERGE_TRAVERSAL_WEIGHT; + } else { + new_name = name->tip_name; + generation = name->generation + 1; + distance = name->distance + 1; + } - strip_suffix(name->tip_name, "^0", &len); - if (name->generation > 0) - new_name = xstrfmt("%.*s~%d^%d", - (int)len, - name->tip_name, - name->generation, - parent_number); - else - new_name = xstrfmt("%.*s^%d", (int)len, - name->tip_name, - parent_number); - generation = 0; - distance = name->distance + MERGE_TRAVERSAL_WEIGHT; - } else { - new_name = name->tip_name; - generation = name->generation + 1; - distance = name->distance + 1; + if (create_or_update_name(parent, new_name, taggerdate, + generation, distance, + from_tag)) { + ALLOC_GROW(parents_to_queue, + parents_to_queue_nr + 1, + parents_to_queue_alloc); + parents_to_queue[parents_to_queue_nr] = parent; + parents_to_queue_nr++; + } } - if (create_or_update_name(parent, new_name, taggerdate, - generation, distance, - from_tag)) - name_rev(parent, new_name, taggerdate, from_tag); + /* The first parent must come out first from the prio_queue */ + while (parents_to_queue_nr) + prio_queue_put(&queue, + parents_to_queue[--parents_to_queue_nr]); } + + clear_prio_queue(&queue); + free(parents_to_queue); } static int subpath_matches(const char *path, const char *filter) diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh index 0d119e9652..09c50f3f04 100755 --- a/t/t6120-describe.sh +++ b/t/t6120-describe.sh @@ -381,7 +381,7 @@ test_expect_success 'describe tag object' ' test_i18ngrep "fatal: test-blob-1 is neither a commit nor blob" actual ' -test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' ' +test_expect_success ULIMIT_STACK_SIZE 'name-rev works in a deep repo' ' i=1 && while test $i -lt 8000 do |