[PATCH] Remove hash in git-describe in favor of util slot.

["Shawn O. Pearce" <spearce@spearce.org>]

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 <spearce@spearce.org>
---

 This removes more lines than it adds, so it must be good, right?
 :-)

 builtin-describe.c |   76 ++++++++-------------------------------------------
 1 files changed, 12 insertions(+), 64 deletions(-)

diff --git a/builtin-describe.c b/builtin-describe.c
index e38c899..e7b8f95 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++];
-- 
1.5.0.rc1.g4494