diff options
Diffstat (limited to 'builtin/name-rev.c')
| -rw-r--r-- | builtin/name-rev.c | 191 |
1 files changed, 127 insertions, 64 deletions
diff --git a/builtin/name-rev.c b/builtin/name-rev.c index 6b9e8c8..a9dcd25 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -16,15 +16,15 @@ */ #define CUTOFF_DATE_SLOP 86400 -typedef struct rev_name { - const char *tip_name; +struct rev_name { + char *tip_name; timestamp_t taggerdate; int generation; int distance; int from_tag; -} rev_name; +}; -define_commit_slab(commit_rev_name, struct rev_name *); +define_commit_slab(commit_rev_name, struct rev_name); static timestamp_t cutoff = TIME_MAX; static struct commit_rev_name rev_names; @@ -32,16 +32,16 @@ static struct commit_rev_name rev_names; /* How many generations are maximally preferred over _one_ merge traversal? */ #define MERGE_TRAVERSAL_WEIGHT 65535 -static struct rev_name *get_commit_rev_name(struct commit *commit) +static int is_valid_rev_name(const struct rev_name *name) { - struct rev_name **slot = commit_rev_name_peek(&rev_names, commit); - - return slot ? *slot : NULL; + return name && (name->generation || name->tip_name); } -static void set_commit_rev_name(struct commit *commit, struct rev_name *name) +static struct rev_name *get_commit_rev_name(const struct commit *commit) { - *commit_rev_name_at(&rev_names, commit) = name; + struct rev_name *name = commit_rev_name_peek(&rev_names, commit); + + return is_valid_rev_name(name) ? name : NULL; } static int is_better_name(struct rev_name *name, @@ -81,28 +81,54 @@ static int is_better_name(struct rev_name *name, } static struct rev_name *create_or_update_name(struct commit *commit, - const char *tip_name, timestamp_t taggerdate, int generation, int distance, int from_tag) { - struct rev_name *name = get_commit_rev_name(commit); - - if (name == NULL) { - name = xmalloc(sizeof(*name)); - set_commit_rev_name(commit, name); - goto copy_data; - } else if (is_better_name(name, taggerdate, distance, from_tag)) { -copy_data: - name->tip_name = tip_name; - name->taggerdate = taggerdate; - name->generation = generation; - name->distance = distance; - name->from_tag = from_tag; - - return name; - } else - return NULL; + struct rev_name *name = commit_rev_name_at(&rev_names, commit); + + if (is_valid_rev_name(name)) { + if (!is_better_name(name, taggerdate, distance, from_tag)) + return NULL; + + /* + * This string might still be shared with ancestors + * (generation > 0). We can release it here regardless, + * because the new name that has just won will be better + * for them as well, so name_rev() will replace these + * stale pointers when it processes the parents. + */ + if (!name->generation) + free(name->tip_name); + } + + name->taggerdate = taggerdate; + name->generation = generation; + name->distance = distance; + name->from_tag = from_tag; + + return name; +} + +static char *get_parent_name(const struct rev_name *name, int parent_number) +{ + struct strbuf sb = STRBUF_INIT; + size_t len; + + strip_suffix(name->tip_name, "^0", &len); + if (name->generation > 0) { + strbuf_grow(&sb, len + + 1 + decimal_width(name->generation) + + 1 + decimal_width(parent_number)); + strbuf_addf(&sb, "%.*s~%d^%d", (int)len, name->tip_name, + name->generation, parent_number); + } else { + strbuf_grow(&sb, len + + 1 + decimal_width(parent_number)); + strbuf_addf(&sb, "%.*s^%d", (int)len, name->tip_name, + parent_number); + } + return strbuf_detach(&sb, NULL); } static void name_rev(struct commit *start_commit, @@ -113,20 +139,20 @@ static void name_rev(struct commit *start_commit, struct commit *commit; struct commit **parents_to_queue = NULL; size_t parents_to_queue_nr, parents_to_queue_alloc = 0; - char *to_free = NULL; + struct rev_name *start_name; parse_commit(start_commit); if (start_commit->date < cutoff) return; - if (deref) - tip_name = to_free = xstrfmt("%s^0", tip_name); - - if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0, - from_tag)) { - free(to_free); + start_name = create_or_update_name(start_commit, taggerdate, 0, 0, + from_tag); + if (!start_name) return; - } + if (deref) + start_name->tip_name = xstrfmt("%s^0", tip_name); + else + start_name->tip_name = xstrdup(tip_name); memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */ prio_queue_put(&queue, start_commit); @@ -142,7 +168,7 @@ static void name_rev(struct commit *start_commit, parents; parents = parents->next, parent_number++) { struct commit *parent = parents->item; - const char *new_name; + struct rev_name *parent_name; int generation, distance; parse_commit(parent); @@ -150,30 +176,23 @@ static void name_rev(struct commit *start_commit, continue; 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; } - if (create_or_update_name(parent, new_name, taggerdate, - generation, distance, - from_tag)) { + parent_name = create_or_update_name(parent, taggerdate, + generation, + distance, from_tag); + if (parent_name) { + if (parent_number > 1) + parent_name->tip_name = + get_parent_name(name, + parent_number); + else + parent_name->tip_name = name->tip_name; ALLOC_GROW(parents_to_queue, parents_to_queue_nr + 1, parents_to_queue_alloc); @@ -228,6 +247,10 @@ static struct tip_table { struct tip_table_entry { struct object_id oid; const char *refname; + struct commit *commit; + timestamp_t taggerdate; + unsigned int from_tag:1; + unsigned int deref:1; } *table; int nr; int alloc; @@ -235,13 +258,18 @@ static struct tip_table { } tip_table; static void add_to_tip_table(const struct object_id *oid, const char *refname, - int shorten_unambiguous) + int shorten_unambiguous, struct commit *commit, + timestamp_t taggerdate, int from_tag, int deref) { refname = name_ref_abbrev(refname, shorten_unambiguous); ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc); oidcpy(&tip_table.table[tip_table.nr].oid, oid); tip_table.table[tip_table.nr].refname = xstrdup(refname); + tip_table.table[tip_table.nr].commit = commit; + tip_table.table[tip_table.nr].taggerdate = taggerdate; + tip_table.table[tip_table.nr].from_tag = from_tag; + tip_table.table[tip_table.nr].deref = deref; tip_table.nr++; tip_table.sorted = 0; } @@ -252,12 +280,30 @@ static int tipcmp(const void *a_, const void *b_) return oidcmp(&a->oid, &b->oid); } +static int cmp_by_tag_and_age(const void *a_, const void *b_) +{ + const struct tip_table_entry *a = a_, *b = b_; + int cmp; + + /* Prefer tags. */ + cmp = b->from_tag - a->from_tag; + if (cmp) + return cmp; + + /* Older is better. */ + if (a->taggerdate < b->taggerdate) + return -1; + return a->taggerdate != b->taggerdate; +} + static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data) { struct object *o = parse_object(the_repository, oid); struct name_ref_data *data = cb_data; int can_abbreviate_output = data->tags_only && data->name_only; int deref = 0; + int from_tag = 0; + struct commit *commit = NULL; timestamp_t taggerdate = TIME_MAX; if (data->tags_only && !starts_with(path, "refs/tags/")) @@ -306,8 +352,6 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo return 0; } - add_to_tip_table(oid, path, can_abbreviate_output); - while (o && o->type == OBJ_TAG) { struct tag *t = (struct tag *) o; if (!t->tagged) @@ -317,17 +361,35 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo taggerdate = t->date; } if (o && o->type == OBJ_COMMIT) { - struct commit *commit = (struct commit *)o; - int from_tag = starts_with(path, "refs/tags/"); - + commit = (struct commit *)o; + from_tag = starts_with(path, "refs/tags/"); if (taggerdate == TIME_MAX) taggerdate = commit->date; - path = name_ref_abbrev(path, can_abbreviate_output); - name_rev(commit, xstrdup(path), taggerdate, from_tag, deref); } + + add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate, + from_tag, deref); return 0; } +static void name_tips(void) +{ + int i; + + /* + * Try to set better names first, so that worse ones spread + * less. + */ + QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age); + for (i = 0; i < tip_table.nr; i++) { + struct tip_table_entry *e = &tip_table.table[i]; + if (e->commit) { + name_rev(e->commit, e->refname, e->taggerdate, + e->from_tag, e->deref); + } + } +} + static const unsigned char *nth_tip_table_ent(size_t ix, void *table_) { struct tip_table_entry *table = table_; @@ -357,11 +419,11 @@ static const char *get_exact_ref_match(const struct object *o) static const char *get_rev_name(const struct object *o, struct strbuf *buf) { struct rev_name *n; - struct commit *c; + const struct commit *c; if (o->type != OBJ_COMMIT) return get_exact_ref_match(o); - c = (struct commit *) o; + c = (const struct commit *) o; n = get_commit_rev_name(c); if (!n) return NULL; @@ -540,6 +602,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix) cutoff = TIME_MIN; } for_each_ref(name_ref, &data); + name_tips(); if (transform_stdin) { char buffer[2048]; |