carlosmn/libgit2 — comment on commit 6f38bf6e78f21ace75998ea6ae5903ad541d86a6
File: src/tree.c line 760
By peff:

I don't get why you are doing a from-scratch binary search here. Both
tree vectors are sorted, right? So you should be able to do the
comparison as a straight-up merge sort, like this (you have the first
half in some form, which is why I'm so confused that you don't have the
second half):

if (!entry_a && !entry_b)
return; /* we are done */
if (!entry_a) {
/* only b left, so they must be additions */
signal_additions(b, ...);
return;
}
if (!entry_b) {
/* only a left, so they must be deletions */
signal_deletions(a, ...);
return;
}

cmp = strcmp(entry_a->filename, entry_b->filename);
if (cmp == 0) {
/* same filename; compare sha1 */
if (tree_entry_cmp(entry_a, entry_b))
signal_modification(...);
/* and advance both sides */
i_a++;
i_b++;
}
else if (cmp < 0) {
/* a is less than b, so we must not have it in b,
because b is sorted, and we would have seen it already
So it must be a deletion. */
signal_deletion(entry_a, ...);
/* advance only a, because we have not dealt with b yet */
i_a++;
}
else {
/* cmp > 0, which is the reverse of above. */
signal_addition_entry_b, ...);
i_b++;
}