PackWriter: Make want/have actual sets

During parsing these are used with contains(). If they are a List
type, the contains operation is not efficient. Some callers such
as UploadPack often pass a List here, so convert to Set when the
type isn't efficient for contains().

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

5 files changed, 113 insertions, 31 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/storage/file/PackWriterTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/storage/file/PackWriterTest.java
index fb78ec02c7..b609b4766b 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/storage/file/PackWriterTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/storage/file/PackWriterTest.java
@@ -55,11 +55,11 @@ import java.io.FileOutputStream;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.LinkedList;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.junit.JGitTestUtil;
@@ -79,8 +79,8 @@ import org.junit.Test;
 
 public class PackWriterTest extends SampleDataRepositoryTestCase {
 
-	private static final List<ObjectId> EMPTY_LIST_OBJECT = Collections
-			.<ObjectId> emptyList();
+	private static final Set<ObjectId> EMPTY_SET_OBJECT = Collections
+			.<ObjectId> emptySet();
 
 	private static final List<RevObject> EMPTY_LIST_REVS = Collections
 			.<RevObject> emptyList();
@@ -162,7 +162,7 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 	 */
 	@Test
 	public void testWriteEmptyPack1() throws IOException {
-		createVerifyOpenPack(EMPTY_LIST_OBJECT, EMPTY_LIST_OBJECT, false, false);
+		createVerifyOpenPack(EMPTY_SET_OBJECT, EMPTY_SET_OBJECT, false, false);
 
 		assertEquals(0, writer.getObjectCount());
 		assertEquals(0, pack.getObjectCount());
@@ -195,7 +195,7 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 		final ObjectId nonExisting = ObjectId
 				.fromString("0000000000000000000000000000000000000001");
 		try {
-			createVerifyOpenPack(EMPTY_LIST_OBJECT, Collections.nCopies(1,
+			createVerifyOpenPack(EMPTY_SET_OBJECT, Collections.singleton(
 					nonExisting), false, false);
 			fail("Should have thrown MissingObjectException");
 		} catch (MissingObjectException x) {
@@ -212,7 +212,7 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 	public void testIgnoreNonExistingObjects() throws IOException {
 		final ObjectId nonExisting = ObjectId
 				.fromString("0000000000000000000000000000000000000001");
-		createVerifyOpenPack(EMPTY_LIST_OBJECT, Collections.nCopies(1,
+		createVerifyOpenPack(EMPTY_SET_OBJECT, Collections.singleton(
 				nonExisting), false, true);
 		// shouldn't throw anything
 	}
@@ -451,10 +451,10 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 	// TODO: testWritePackDeltasDepth()
 
 	private void writeVerifyPack1() throws IOException {
-		final LinkedList<ObjectId> interestings = new LinkedList<ObjectId>();
+		final HashSet<ObjectId> interestings = new HashSet<ObjectId>();
 		interestings.add(ObjectId
 				.fromString("82c6b885ff600be425b4ea96dee75dca255b69e7"));
-		createVerifyOpenPack(interestings, EMPTY_LIST_OBJECT, false, false);
+		createVerifyOpenPack(interestings, EMPTY_SET_OBJECT, false, false);
 
 		final ObjectId expectedOrder[] = new ObjectId[] {
 				ObjectId.fromString("82c6b885ff600be425b4ea96dee75dca255b69e7"),
@@ -474,10 +474,10 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 
 	private void writeVerifyPack2(boolean deltaReuse) throws IOException {
 		config.setReuseDeltas(deltaReuse);
-		final LinkedList<ObjectId> interestings = new LinkedList<ObjectId>();
+		final HashSet<ObjectId> interestings = new HashSet<ObjectId>();
 		interestings.add(ObjectId
 				.fromString("82c6b885ff600be425b4ea96dee75dca255b69e7"));
-		final LinkedList<ObjectId> uninterestings = new LinkedList<ObjectId>();
+		final HashSet<ObjectId> uninterestings = new HashSet<ObjectId>();
 		uninterestings.add(ObjectId
 				.fromString("540a36d136cf413e4b064c2b0e0a4db60f77feab"));
 		createVerifyOpenPack(interestings, uninterestings, false, false);
@@ -502,10 +502,10 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 	}
 
 	private void writeVerifyPack4(final boolean thin) throws IOException {
-		final LinkedList<ObjectId> interestings = new LinkedList<ObjectId>();
+		final HashSet<ObjectId> interestings = new HashSet<ObjectId>();
 		interestings.add(ObjectId
 				.fromString("82c6b885ff600be425b4ea96dee75dca255b69e7"));
-		final LinkedList<ObjectId> uninterestings = new LinkedList<ObjectId>();
+		final HashSet<ObjectId> uninterestings = new HashSet<ObjectId>();
 		uninterestings.add(ObjectId
 				.fromString("c59759f143fb1fe21c197981df75a7ee00290799"));
 		createVerifyOpenPack(interestings, uninterestings, thin, false);
@@ -531,8 +531,8 @@ public class PackWriterTest extends SampleDataRepositoryTestCase {
 				.computeName().name());
 	}
 
-	private void createVerifyOpenPack(final Collection<ObjectId> interestings,
-			final Collection<ObjectId> uninterestings, final boolean thin,
+	private void createVerifyOpenPack(final Set<ObjectId> interestings,
+			final Set<ObjectId> uninterestings, final boolean thin,
 			final boolean ignoreMissingUninteresting)
 			throws MissingObjectException, IOException {
 		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
index 8c3d52afcd..766f0dfc7a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
@@ -477,12 +477,13 @@ public class PackWriter {
 	 *            points of graph traversal).
 	 * @throws IOException
 	 *             when some I/O problem occur during reading objects.
+	 * @deprecated to be removed in 2.0; use the Set version of this method.
 	 */
+	@Deprecated
 	public void preparePack(ProgressMonitor countingMonitor,
 			final Collection<? extends ObjectId> want,
 			final Collection<? extends ObjectId> have) throws IOException {
-		ObjectWalk ow = new ObjectWalk(reader);
-		preparePack(countingMonitor, ow, want, have);
+		preparePack(countingMonitor, ensureSet(want), ensureSet(have));
 	}
 
 	/**
@@ -509,12 +510,91 @@ public class PackWriter {
 	 *            points of graph traversal).
 	 * @throws IOException
 	 *             when some I/O problem occur during reading objects.
+	 * @deprecated to be removed in 2.0; use the Set version of this method.
 	 */
+	@Deprecated
 	public void preparePack(ProgressMonitor countingMonitor,
 			final ObjectWalk walk,
 			final Collection<? extends ObjectId> interestingObjects,
 			final Collection<? extends ObjectId> uninterestingObjects)
 			throws IOException {
+		preparePack(countingMonitor, walk,
+				ensureSet(interestingObjects),
+				ensureSet(uninterestingObjects));
+	}
+
+	@SuppressWarnings("unchecked")
+	private static Set<ObjectId> ensureSet(Collection<? extends ObjectId> objs) {
+		Set<ObjectId> set;
+		if (objs instanceof Set<?>)
+			set = (Set<ObjectId>) objs;
+		else if (objs == null)
+			set = Collections.emptySet();
+		else
+			set = new HashSet<ObjectId>(objs);
+		return set;
+	}
+
+	/**
+	 * Prepare the list of objects to be written to the pack stream.
+	 * <p>
+	 * Basing on these 2 sets, another set of objects to put in a pack file is
+	 * created: this set consists of all objects reachable (ancestors) from
+	 * interesting objects, except uninteresting objects and their ancestors.
+	 * This method uses class {@link ObjectWalk} extensively to find out that
+	 * appropriate set of output objects and their optimal order in output pack.
+	 * Order is consistent with general git in-pack rules: sort by object type,
+	 * recency, path and delta-base first.
+	 * </p>
+	 *
+	 * @param countingMonitor
+	 *            progress during object enumeration.
+	 * @param want
+	 *            collection of objects to be marked as interesting (start
+	 *            points of graph traversal).
+	 * @param have
+	 *            collection of objects to be marked as uninteresting (end
+	 *            points of graph traversal).
+	 * @throws IOException
+	 *             when some I/O problem occur during reading objects.
+	 */
+	public void preparePack(ProgressMonitor countingMonitor,
+			Set<? extends ObjectId> want,
+			Set<? extends ObjectId> have) throws IOException {
+		ObjectWalk ow = new ObjectWalk(reader);
+		preparePack(countingMonitor, ow, want, have);
+	}
+
+	/**
+	 * Prepare the list of objects to be written to the pack stream.
+	 * <p>
+	 * Basing on these 2 sets, another set of objects to put in a pack file is
+	 * created: this set consists of all objects reachable (ancestors) from
+	 * interesting objects, except uninteresting objects and their ancestors.
+	 * This method uses class {@link ObjectWalk} extensively to find out that
+	 * appropriate set of output objects and their optimal order in output pack.
+	 * Order is consistent with general git in-pack rules: sort by object type,
+	 * recency, path and delta-base first.
+	 * </p>
+	 *
+	 * @param countingMonitor
+	 *            progress during object enumeration.
+	 * @param walk
+	 *            ObjectWalk to perform enumeration.
+	 * @param interestingObjects
+	 *            collection of objects to be marked as interesting (start
+	 *            points of graph traversal).
+	 * @param uninterestingObjects
+	 *            collection of objects to be marked as uninteresting (end
+	 *            points of graph traversal).
+	 * @throws IOException
+	 *             when some I/O problem occur during reading objects.
+	 */
+	public void preparePack(ProgressMonitor countingMonitor,
+			final ObjectWalk walk,
+			final Set<? extends ObjectId> interestingObjects,
+			final Set<? extends ObjectId> uninterestingObjects)
+			throws IOException {
 		if (countingMonitor == null)
 			countingMonitor = NullProgressMonitor.INSTANCE;
 		findObjectsToPack(countingMonitor, walk, interestingObjects,
@@ -566,10 +646,10 @@ public class PackWriter {
 	/**
 	 * Create an index file to match the pack file just written.
 	 * <p>
-	 * This method can only be invoked after {@link #preparePack(Iterator)} or
-	 * {@link #preparePack(ProgressMonitor, Collection, Collection)} has been
-	 * invoked and completed successfully. Writing a corresponding index is an
-	 * optional feature that not all pack users may require.
+	 * This method can only be invoked after
+	 * {@link #writePack(ProgressMonitor, ProgressMonitor, OutputStream)} has
+	 * been invoked and completed successfully. Writing a corresponding index is
+	 * an optional feature that not all pack users may require.
 	 *
 	 * @param indexStream
 	 *            output for the index data. Caller is responsible for closing
@@ -1256,8 +1336,8 @@ public class PackWriter {
 	}
 
 	private void findObjectsToPack(final ProgressMonitor countingMonitor,
-			final ObjectWalk walker, final Collection<? extends ObjectId> want,
-			Collection<? extends ObjectId> have)
+			final ObjectWalk walker, final Set<? extends ObjectId> want,
+			Set<? extends ObjectId> have)
 			throws MissingObjectException, IOException,
 			IncorrectObjectTypeException {
 		final long countingStart = System.currentTimeMillis();
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/BasePackPushConnection.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/BasePackPushConnection.java
index 4e0536d0cd..61f3df1fc4 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/BasePackPushConnection.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/BasePackPushConnection.java
@@ -46,10 +46,10 @@ package org.eclipse.jgit.transport;
 
 import java.io.IOException;
 import java.text.MessageFormat;
-import java.util.ArrayList;
 import java.util.Collection;
-import java.util.List;
+import java.util.HashSet;
 import java.util.Map;
+import java.util.Set;
 
 import org.eclipse.jgit.JGitText;
 import org.eclipse.jgit.errors.NoRemoteRepositoryException;
@@ -243,8 +243,8 @@ public abstract class BasePackPushConnection extends BasePackConnection implemen
 
 	private void writePack(final Map<String, RemoteRefUpdate> refUpdates,
 			final ProgressMonitor monitor) throws IOException {
-		List<ObjectId> remoteObjects = new ArrayList<ObjectId>(getRefs().size());
-		List<ObjectId> newObjects = new ArrayList<ObjectId>(refUpdates.size());
+		Set<ObjectId> remoteObjects = new HashSet<ObjectId>();
+		Set<ObjectId> newObjects = new HashSet<ObjectId>();
 
 		final PackWriter writer = new PackWriter(transport.getPackConfig(),
 				local.newObjectReader());
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
index 41f64a163c..a9921fd8c3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
@@ -155,10 +155,10 @@ public class UploadPack {
 	private final Set<ObjectId> wantIds = new HashSet<ObjectId>();
 
 	/** Objects the client wants to obtain. */
-	private final List<RevObject> wantAll = new ArrayList<RevObject>();
+	private final Set<RevObject> wantAll = new HashSet<RevObject>();
 
 	/** Objects on both sides, these don't have to be sent. */
-	private final List<RevObject> commonBase = new ArrayList<RevObject>();
+	private final Set<RevObject> commonBase = new HashSet<RevObject>();
 
 	/** Commit time of the oldest common commit, in seconds. */
 	private int oldestTime;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java
index 1d1e67402f..ce710b5e11 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java
@@ -50,9 +50,11 @@ import java.io.IOException;
 import java.io.OutputStream;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.TreeMap;
 
 import org.eclipse.jgit.JGitText;
@@ -215,8 +217,8 @@ class WalkPushConnection extends BaseConnection implements PushConnection {
 		final PackWriter writer = new PackWriter(transport.getPackConfig(),
 				local.newObjectReader());
 		try {
-			final List<ObjectId> need = new ArrayList<ObjectId>();
-			final List<ObjectId> have = new ArrayList<ObjectId>();
+			final Set<ObjectId> need = new HashSet<ObjectId>();
+			final Set<ObjectId> have = new HashSet<ObjectId>();
 			for (final RemoteRefUpdate r : updates)
 				need.add(r.getNewObjectId());
 			for (final Ref r : getRefs()) {