summaryrefslogtreecommitdiff
path: root/builtin
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2020-02-17 21:22:16 (GMT)
committerJunio C Hamano <gitster@pobox.com>2020-02-17 21:22:16 (GMT)
commit0460c109c3c791ccc4860871022f2ca566a6a255 (patch)
treeccb0328098e8251aacfa0544dc97ba8abdbfd59f /builtin
parente68e29171cc2d6968902e0654b5687fbe1ccb903 (diff)
parent079f970971e8e66bdf5b67d924fc2a5177277ffd (diff)
downloadgit-0460c109c3c791ccc4860871022f2ca566a6a255.zip
git-0460c109c3c791ccc4860871022f2ca566a6a255.tar.gz
git-0460c109c3c791ccc4860871022f2ca566a6a255.tar.bz2
Merge branch 'rs/name-rev-memsave'
Memory footprint and performance of "git name-rev" has been improved. * rs/name-rev-memsave: name-rev: sort tip names before applying name-rev: release unused name strings name-rev: generate name strings only if they are better name-rev: pre-size buffer in get_parent_name() name-rev: factor out get_parent_name() name-rev: put struct rev_name into commit slab name-rev: don't _peek() in create_or_update_name() name-rev: don't leak path copy in name_ref() name-rev: respect const qualifier name-rev: remove unused typedef name-rev: rewrite create_or_update_name()
Diffstat (limited to 'builtin')
-rw-r--r--builtin/name-rev.c191
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];