From e7eb50347bba54ab52f9740a3bbb6e833bdadf6e Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Sun, 14 Jan 2007 22:16:55 -0500 Subject: [PATCH] Remove hash in git-describe in favor of util slot. Currently we don't use the util field of struct commit but we want fast access to the highest priority name that references any given commit object during our matching loop. A really simple approach is to just store the name directly in the util field. Signed-off-by: Shawn O. Pearce Signed-off-by: Junio C Hamano --- builtin-describe.c | 76 ++++++++-------------------------------------- 1 file changed, 12 insertions(+), 64 deletions(-) diff --git a/builtin-describe.c b/builtin-describe.c index e38c89925..e7b8f95c8 100644 --- a/builtin-describe.c +++ b/builtin-describe.c @@ -16,60 +16,27 @@ static int tags; /* But allow any tags if --tags is specified */ static int abbrev = DEFAULT_ABBREV; static int max_candidates = 10; -static unsigned int names[256], allocs[256]; -static struct commit_name { - struct commit *commit; +struct commit_name { int prio; /* annotated tag = 2, tag = 1, head = 0 */ char path[FLEX_ARRAY]; /* more */ -} **name_array[256]; +}; static const char *prio_names[] = { "head", "lightweight", "annotated", }; -static struct commit_name *match(struct commit *cmit) -{ - unsigned char level0 = cmit->object.sha1[0]; - struct commit_name **p = name_array[level0]; - unsigned int hi = names[level0]; - unsigned int lo = 0; - - while (lo < hi) { - unsigned int mi = (lo + hi) / 2; - int cmp = hashcmp(p[mi]->commit->object.sha1, - cmit->object.sha1); - if (!cmp) { - while (mi && p[mi - 1]->commit == cmit) - mi--; - return p[mi]; - } - if (cmp > 0) - hi = mi; - else - lo = mi+1; - } - return NULL; -} - static void add_to_known_names(const char *path, struct commit *commit, int prio) { - int idx; - int len = strlen(path)+1; - struct commit_name *name = xmalloc(sizeof(struct commit_name) + len); - unsigned char m = commit->object.sha1[0]; - - name->commit = commit; - name->prio = prio; - memcpy(name->path, path, len); - idx = names[m]; - if (idx >= allocs[m]) { - allocs[m] = (idx + 50) * 3 / 2; - name_array[m] = xrealloc(name_array[m], - allocs[m] * sizeof(*name_array)); + struct commit_name *e = commit->util; + if (!e || e->prio < prio) { + size_t len = strlen(path)+1; + free(e); + e = xmalloc(sizeof(struct commit_name) + len); + e->prio = prio; + memcpy(e->path, path, len); + commit->util = e; } - name_array[m][idx] = name; - names[m] = ++idx; } static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data) @@ -104,21 +71,6 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void return 0; } -static int compare_names(const void *_a, const void *_b) -{ - struct commit_name *a = *(struct commit_name **)_a; - struct commit_name *b = *(struct commit_name **)_b; - unsigned long a_date = a->commit->date; - unsigned long b_date = b->commit->date; - int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1); - - if (cmp) - return cmp; - if (a->prio != b->prio) - return b->prio - a->prio; - return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1; -} - struct possible_tag { struct commit_name *name; int depth; @@ -158,15 +110,11 @@ static void describe(const char *arg, int last_one) die("%s is not a valid '%s' object", arg, commit_type); if (!initialized) { - unsigned int m; initialized = 1; for_each_ref(get_name, NULL); - for (m = 0; m < ARRAY_SIZE(name_array); m++) - qsort(name_array[m], names[m], - sizeof(*name_array[m]), compare_names); } - n = match(cmit); + n = cmit->util; if (n) { printf("%s\n", n->path); return; @@ -182,7 +130,7 @@ static void describe(const char *arg, int last_one) struct commit *c = pop_commit(&list); struct commit_list *parents = c->parents; seen_commits++; - n = match(c); + n = c->util; if (n) { if (match_cnt < max_candidates) { struct possible_tag *t = &all_matches[match_cnt++]; -- 2.30.2