Andy Parkins [off-list ref] writes:
On Monday 2007 July 16, Johannes Schindelin wrote:
quoted
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.
Hi,
On Mon, 16 Jul 2007, Junio C Hamano wrote:
Andy Parkins [off-list ref] writes:
quoted
On Monday 2007 July 16, Johannes Schindelin wrote:
quoted
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.
I disagree. One disadvantage to using tree objects is that it is much
easier to have pilot errors. You could even make a new working tree
checking out refs/notes/commits and change/add/remove files.
Ciao,
Dscho