Re: [PATCH 0/6] Introduce commit notes

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 16, 2007, 08:11 UTC
Message-ID: <7vbqec4vk2.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <200707160857.48725.andyparkins@gmail.com>

Andy Parkins <andyparkins@gmail.com> writes:

Show 13 quoted lines

> On Monday 2007 July 16, Johannes Schindelin wrote:
>
>> The biggest obstacle was a thinko about the scalability.  Tree objects
>> take free form name entries, and therefore a binary search by name is not
>> possible.
>
> I might be misunderstanding, but in the case of the notes tree objects isn't 
> it true that the name entries aren't free form, but are guaranteed to be of a 
> fixed length form:
>
>   XX/XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
>
> In which case you can binary search?

Hmph, you are right.  In this sequence:

	hex = sha1_to_hex(commit->object.sha1);
	snprintf(name, sizeof(name), "%s:%.*s/%.*s",
			notes_ref_name, 2, hex, 38, hex + 2);
	if (get_sha1(name, sha1))
		return;

Instead, we could read the tree object by hand in the commit that is referenced by notes_ref_name, which has uniform two letter names for subtrees which can be binary searched, open the tree for that entry, again by hand, and do another binary search because that tree has uniform 38-letter names. That certainly could be done.

Sounds like a "fun" project for some definition of the word.