[JGIT PATCH 15/14] Micro-optimize the combineDF part of NameConflictTreeWalk

From: Shawn O. Pearce <spearce@spearce.org>
Date: Aug 19, 2008, 23:17 UTC
Message-ID: <1219187833-26568-1-git-send-email-spearce@spearce.org>

We can do the common case of combineDF (which requires no lookahead) during the search for the minimum entry by keeping track of the type of each entry and using the single entry lookahead inherent in the data structure.

Since this catches the most common case of "a" and "a/" with no intervening "a.foo" we can typically avoid the much more costly combineDF and skipEntry routines.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---

 This adds onto the end of my 14 patch D/F conflict series.  Last night
 it was bugging me that the common cases of all paths matching, or of
 the D/F pair being just one item apart required two loops through the
 iterators to identify the match (once in super.min, again in combineDF).

 .../jgit/treewalk/NameConflictTreeWalk.java        |   75 +++++++++++++++++++-
 1 files changed, 72 insertions(+), 3 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java
index fdfba4e..dc854d8 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java
@@ -78,6 +78,8 @@
 public class NameConflictTreeWalk extends TreeWalk {
 	private static final int TREE_MODE = FileMode.TREE.getBits();
 
+	private boolean fastMinHasMatch;
+
 	/**
 	 * Create a new tree walker for a given repository.
 	 * 
@@ -91,11 +93,11 @@ public NameConflictTreeWalk(final Repository repo) {
 	@Override
 	AbstractTreeIterator min() throws CorruptObjectException {
 		for (;;) {
-			final AbstractTreeIterator minRef = super.min();
-			if (minRef.eof())
+			final AbstractTreeIterator minRef = fastMin();
+			if (fastMinHasMatch)
 				return minRef;
 
-			if (FileMode.TREE.equals(minRef.mode)) {
+			if (isTree(minRef)) {
 				if (skipEntry(minRef)) {
 					for (final AbstractTreeIterator t : trees) {
 						if (t.matches == minRef) {
@@ -112,6 +114,73 @@ AbstractTreeIterator min() throws CorruptObjectException {
 		}
 	}
 
+	private AbstractTreeIterator fastMin() {
+		fastMinHasMatch = true;
+
+		int i = 0;
+		AbstractTreeIterator minRef = trees[i];
+		while (minRef.eof() && ++i < trees.length)
+			minRef = trees[i];
+		if (minRef.eof())
+			return minRef;
+
+		minRef.matches = minRef;
+		while (++i < trees.length) {
+			final AbstractTreeIterator t = trees[i];
+			if (t.eof())
+				continue;
+
+			final int cmp = t.pathCompare(minRef);
+			if (cmp < 0) {
+				if (fastMinHasMatch && isTree(minRef) && !isTree(t)
+						&& nameEqual(minRef, t)) {
+					// We used to be at a tree, but now we are at a file
+					// with the same name. Allow the file to match the
+					// tree anyway.
+					//
+					t.matches = minRef;
+				} else {
+					fastMinHasMatch = false;
+					t.matches = t;
+					minRef = t;
+				}
+			} else if (cmp == 0) {
+				// Exact name/mode match is best.
+				//
+				t.matches = minRef;
+			} else if (fastMinHasMatch && isTree(t) && !isTree(minRef)
+					&& nameEqual(t, minRef)) {
+				// The minimum is a file (non-tree) but the next entry
+				// of this iterator is a tree whose name matches our file.
+				// This is a classic D/F conflict and commonly occurs like
+				// this, with no gaps in between the file and directory.
+				//
+				// Use the tree as the minimum instead (see combineDF).
+				//
+
+				for (int k = 0; k < i; k++) {
+					final AbstractTreeIterator p = trees[k];
+					if (p.matches == minRef)
+						p.matches = t;
+				}
+				t.matches = t;
+				minRef = t;
+			} else
+				fastMinHasMatch = false;
+		}
+
+		return minRef;
+	}
+
+	private static boolean nameEqual(final AbstractTreeIterator a,
+			final AbstractTreeIterator b) {
+		return a.pathCompare(b, TREE_MODE) == 0;
+	}
+
+	private static boolean isTree(final AbstractTreeIterator p) {
+		return FileMode.TREE.equals(p.mode);
+	}
+
 	private boolean skipEntry(final AbstractTreeIterator minRef)
 			throws CorruptObjectException {
 		// A tree D/F may have been handled earlier. We need to

-- 
1.6.0.96.g2fad1.dirty