path: root/tree-diff.c
diff options
authorKirill Smelkov <>2014-02-24 16:21:44 (GMT)
committerJunio C Hamano <>2014-03-26 21:25:11 (GMT)
commit6ca844e9f5ca93efd0a1323a9c9aaa882c0043e8 (patch)
tree4a3307900a698b40727b14df07249279d841a0fa /tree-diff.c
parent1a27a1545230a5a19a3c05ed41efb8530d2fd2cd (diff)
tree-diff: remove special-case diff-emitting code for empty-tree cases
While walking trees, we iterate their entries from lowest to highest in sort order, so empty tree means all entries were already went over. If we artificially assign +infinity value to such tree "entry", it will go after all usual entries, and through the usual driver loop we will be taking the same actions, which were hand-coded for special cases, i.e. t1 empty, t2 non-empty pathcmp(+∞, t2) -> +1 show_path(/*t1=*/NULL, t2); /* = t1 > t2 case in main loop */ t1 non-empty, t2-empty pathcmp(t1, +∞) -> -1 show_path(t1, /*t2=*/NULL); /* = t1 < t2 case in main loop */ In other words when we have t1 and t2, we return a sign that tells the caller to indicate the "earlier" one to be emitted, and by returning the sign that causes the non-empty side to be emitted, we will automatically cause the entries from the remaining side to be emitted, without attempting to touch the empty side at all. We can teach tree_entry_pathcmp() to pretend that an empty tree has an element that sorts after anything else to achieve this. Right now we never go to when compared tree descriptors are both infinity, as this condition is checked in the loop beginning as finishing criteria, but will do so in the future, when there will be several parents iterated simultaneously, and some pair of them would run to the end. Signed-off-by: Kirill Smelkov <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 'tree-diff.c')
1 files changed, 14 insertions, 12 deletions
diff --git a/tree-diff.c b/tree-diff.c
index f8b2607..8e04002 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -12,12 +12,24 @@
* NOTE files and directories *always* compare differently, even when having
* the same name - thanks to base_name_compare().
+ *
+ * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
+ * so that they sort *after* valid tree entries.
+ *
+ * Due to this convention, if trees are scanned in sorted order, all
+ * non-empty descriptors will be processed first.
static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
struct name_entry *e1, *e2;
int cmp;
+ /* empty descriptors sort after valid tree entries */
+ if (!t1->size)
+ return t2->size ? 1 : 0;
+ else if (!t2->size)
+ return -1;
e1 = &t1->entry;
e2 = &t2->entry;
cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
@@ -150,18 +162,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
skip_uninteresting(t1, &base, opt);
skip_uninteresting(t2, &base, opt);
- if (!t1->size) {
- if (!t2->size)
- break;
- show_path(&base, opt, /*t1=*/NULL, t2);
- update_tree_entry(t2);
- continue;
- }
- if (!t2->size) {
- show_path(&base, opt, t1, /*t2=*/NULL);
- update_tree_entry(t1);
- continue;
- }
+ if (!t1->size && !t2->size)
+ break;
cmp = tree_entry_pathcmp(t1, t2);