Do not use ArrayList when there will be deletions

In https://gerrithub.io/c/eclipse-jgit/jgit/+/1194015, LinkedList was
replaced with ArrayList in DfsReader and WalkFetchConnection. In this
case, the Iterator.remove() method of List is called, which is an O(n)
operation for ArrayList. This results in an O(n^2) algorithm.

Instead of reverting to LinkedList, use a HashSet and LinkedHashmap
instead. This maintains O(1) removal, and is less likely to be treated
as an antipattern than LinkedList.

A likely innocuous usage of Iterator.remove() in UnionInputStream was
also fixed.

Change-Id: I57d884440c726b2fc80c1b8b2bec9bd7e2e6e3fe

3 files changed, 30 insertions, 27 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java
index c939114f5f..9cfcbaa5f7 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java
@@ -307,7 +307,7 @@ public class DfsReader extends ObjectReader implements ObjectReuseAsIs {
 
 	private <T extends ObjectId> Iterable<FoundObject<T>> findAll(
 			Iterable<T> objectIds) throws IOException {
-		Collection<T> pending = new ArrayList<>();
+		HashSet<T> pending = new HashSet<>();
 		for (T id : objectIds) {
 			pending.add(id);
 		}
@@ -327,22 +327,21 @@ public class DfsReader extends ObjectReader implements ObjectReuseAsIs {
 	}
 
 	private <T extends ObjectId> void findAllImpl(PackList packList,
-			Collection<T> pending, List<FoundObject<T>> r) {
+			HashSet<T> pending, List<FoundObject<T>> r) {
 		DfsPackFile[] packs = packList.packs;
 		if (packs.length == 0) {
 			return;
 		}
 		int lastIdx = 0;
 		DfsPackFile lastPack = packs[lastIdx];
-
-		OBJECT_SCAN: for (Iterator<T> it = pending.iterator(); it.hasNext();) {
-			T t = it.next();
+		HashSet<T> toRemove = new HashSet<>();
+		OBJECT_SCAN: for (T t : pending) {
 			if (!skipGarbagePack(lastPack)) {
 				try {
 					long p = lastPack.findOffset(this, t);
 					if (0 < p) {
 						r.add(new FoundObject<>(t, lastIdx, lastPack, p));
-						it.remove();
+						toRemove.add(t);
 						continue;
 					}
 				} catch (IOException e) {
@@ -360,7 +359,7 @@ public class DfsReader extends ObjectReader implements ObjectReuseAsIs {
 					long p = pack.findOffset(this, t);
 					if (0 < p) {
 						r.add(new FoundObject<>(t, i, pack, p));
-						it.remove();
+						toRemove.add(t);
 						lastIdx = i;
 						lastPack = pack;
 						continue OBJECT_SCAN;
@@ -370,6 +369,7 @@ public class DfsReader extends ObjectReader implements ObjectReuseAsIs {
 				}
 			}
 		}
+		pending.removeAll(toRemove);
 
 		last = lastPack;
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java
index 3da76f38fa..ea789b1c09 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java
@@ -22,8 +22,10 @@ import java.util.Collection;
 import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.Iterator;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 import org.eclipse.jgit.errors.CompoundException;
@@ -122,7 +124,7 @@ class WalkFetchConnection extends BaseFetchConnection {
 	private final Deque<WalkRemoteObjectDatabase> noAlternatesYet;
 
 	/** Packs we have discovered, but have not yet fetched locally. */
-	private final Deque<RemotePack> unfetchedPacks;
+	private final Map<String, RemotePack> unfetchedPacks;
 
 	/**
 	 * Packs whose indexes we have looked at in {@link #unfetchedPacks}.
@@ -164,7 +166,7 @@ class WalkFetchConnection extends BaseFetchConnection {
 		remotes = new ArrayList<>();
 		remotes.add(w);
 
-		unfetchedPacks = new ArrayDeque<>();
+		unfetchedPacks = new LinkedHashMap<>();
 		packsConsidered = new HashSet<>();
 
 		noPacksYet = new ArrayDeque<>();
@@ -227,7 +229,7 @@ class WalkFetchConnection extends BaseFetchConnection {
 	public void close() {
 		inserter.close();
 		reader.close();
-		for (RemotePack p : unfetchedPacks) {
+		for (RemotePack p : unfetchedPacks.values()) {
 			if (p.tmpIdx != null)
 				p.tmpIdx.delete();
 		}
@@ -423,7 +425,7 @@ class WalkFetchConnection extends BaseFetchConnection {
 					continue;
 				for (String packName : packNameList) {
 					if (packsConsidered.add(packName))
-						unfetchedPacks.add(new RemotePack(wrr, packName));
+						unfetchedPacks.put(packName, new RemotePack(wrr, packName));
 				}
 				if (downloadPackedObject(pm, id))
 					return;
@@ -472,9 +474,12 @@ class WalkFetchConnection extends BaseFetchConnection {
 		// Search for the object in a remote pack whose index we have,
 		// but whose pack we do not yet have.
 		//
-		final Iterator<RemotePack> packItr = unfetchedPacks.iterator();
-		while (packItr.hasNext() && !monitor.isCancelled()) {
-			final RemotePack pack = packItr.next();
+		Set<String> toRemove = new HashSet<>();
+		for (Entry<String, RemotePack> entry : unfetchedPacks.entrySet()) {
+			if (monitor.isCancelled()) {
+				break;
+			}
+			final RemotePack pack = entry.getValue();
 			try {
 				pack.openIndex(monitor);
 			} catch (IOException err) {
@@ -484,7 +489,7 @@ class WalkFetchConnection extends BaseFetchConnection {
 				// another source, so don't consider it a failure.
 				//
 				recordError(id, err);
-				packItr.remove();
+				toRemove.add(entry.getKey());
 				continue;
 			}
 
@@ -535,7 +540,7 @@ class WalkFetchConnection extends BaseFetchConnection {
 					}
 					throw new TransportException(e.getMessage(), e);
 				}
-				packItr.remove();
+				toRemove.add(entry.getKey());
 			}
 
 			if (!alreadyHave(id)) {
@@ -550,11 +555,9 @@ class WalkFetchConnection extends BaseFetchConnection {
 
 			// Complete any other objects that we can.
 			//
-			final Iterator<ObjectId> pending = swapFetchQueue();
-			while (pending.hasNext()) {
-				final ObjectId p = pending.next();
+			final Deque<ObjectId> pending = swapFetchQueue();
+			for (ObjectId p : pending) {
 				if (pack.index.hasObject(p)) {
-					pending.remove();
 					process(p);
 				} else {
 					workQueue.add(p);
@@ -563,11 +566,12 @@ class WalkFetchConnection extends BaseFetchConnection {
 			return true;
 
 		}
+		toRemove.forEach(unfetchedPacks::remove);
 		return false;
 	}
 
-	private Iterator<ObjectId> swapFetchQueue() {
-		final Iterator<ObjectId> r = workQueue.iterator();
+	private Deque<ObjectId> swapFetchQueue() {
+		final Deque<ObjectId> r = workQueue;
 		workQueue = new ArrayDeque<>();
 		return r;
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/io/UnionInputStream.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/io/UnionInputStream.java
index c3a1c4e3bb..7e950f6529 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/io/UnionInputStream.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/io/UnionInputStream.java
@@ -14,7 +14,6 @@ import java.io.IOException;
 import java.io.InputStream;
 import java.util.ArrayDeque;
 import java.util.Deque;
-import java.util.Iterator;
 
 /**
  * An InputStream which reads from one or more InputStreams.
@@ -164,14 +163,14 @@ public class UnionInputStream extends InputStream {
 	public void close() throws IOException {
 		IOException err = null;
 
-		for (Iterator<InputStream> i = streams.iterator(); i.hasNext();) {
+		for (InputStream stream : streams) {
 			try {
-				i.next().close();
+				stream.close();
 			} catch (IOException closeError) {
 				err = closeError;
 			}
-			i.remove();
 		}
+		streams.clear();
 
 		if (err != null)
 			throw err;