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

1 files changed, 3 insertions, 4 deletions

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;