Use binary searching on large buckets in git-describe.
authorShawn O. Pearce <spearce@spearce.org>
Sat, 13 Jan 2007 22:29:00 +0000 (17:29 -0500)
committerJunio C Hamano <junkio@cox.net>
Mon, 15 Jan 2007 05:17:27 +0000 (21:17 -0800)
commit910c0d7b5ea09d55f769062abd9b9fe3af904a23
treedb6060befb2ff6f4fa0b3ac7b4e60d923a381932
parentc3e3cd4bf8c94cc2f4fa8d8f7751553037e06004
Use binary searching on large buckets in git-describe.

If a project has a really huge number of tags (such as several
thousand tags) then we are likely to have nearly a hundred tags in
some buckets.  Scanning those buckets as linked lists could take
a large amount of time if done repeatedly during history traversal.

Since we are searching for a unique commit SHA1 we can sort all
tags by commit SHA1 and perform a binary search within the bucket.
Once we identify a particular tag as matching this commit we walk
backwards within the bucket matches to make sure we pick up the
highest priority tag for that commit, as the binary search may
have landed us in the middle of a set of tags which point at the
same commit.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
builtin-describe.c