src/java.base/share/classes/jdk/internal/loader/URLClassPath.java

8198484: URLClassPath should use an ArrayDeque instead of a Stack
Reviewed-by: alanb, mchung, plevart, psandoz

@@ -44,10 +44,11 @@
 import java.security.CodeSigner;
 import java.security.Permission;
 import java.security.PrivilegedActionException;
 import java.security.PrivilegedExceptionAction;
 import java.security.cert.Certificate;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Enumeration;
 import java.util.HashMap;

@@ -55,11 +56,10 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.NoSuchElementException;
 import java.util.Properties;
 import java.util.Set;
-import java.util.Stack;
 import java.util.StringTokenizer;
 import java.util.jar.JarFile;
 import java.util.zip.ZipEntry;
 import java.util.jar.JarEntry;
 import java.util.jar.Manifest;

@@ -99,14 +99,14 @@
         p = props.getProperty("jdk.net.URLClassPath.disableRestrictedPermissions");
         DISABLE_ACC_CHECKING = p != null ? p.equals("true") || p.equals("") : false;
     }
 
     /* The original search path of URLs. */
-    private final List<URL> path;
+    private final ArrayList<URL> path;
 
-    /* The stack of unopened URLs */
-    private final Stack<URL> unopenedUrls = new Stack<>();
+    /* The deque of unopened URLs */
+    private final ArrayDeque<URL> unopenedUrls;
 
     /* The resulting search path of Loaders */
     private final ArrayList<Loader> loaders = new ArrayList<>();
 
     /* Map of each URL opened to its corresponding Loader */

@@ -136,16 +136,19 @@
      *            be null
      */
     public URLClassPath(URL[] urls,
                         URLStreamHandlerFactory factory,
                         AccessControlContext acc) {
-        List<URL> path = new ArrayList<>(urls.length);
+        ArrayList<URL> path = new ArrayList<>(urls.length);
+        ArrayDeque<URL> unopenedUrls = new ArrayDeque<>(urls.length);
         for (URL url : urls) {
             path.add(url);
+            unopenedUrls.add(url);
         }
         this.path = path;
-        push(urls);
+        this.unopenedUrls = unopenedUrls;
+
         if (factory != null) {
             jarHandler = factory.createURLStreamHandler("jar");
         } else {
             jarHandler = null;
         }

@@ -167,11 +170,11 @@
      *        treated as the current working directory
      *
      * @apiNote Used to create the application class path.
      */
     URLClassPath(String cp, boolean skipEmptyElements) {
-        List<URL> path = new ArrayList<>();
+        ArrayList<URL> path = new ArrayList<>();
         if (cp != null) {
             // map each element of class path to a file URL
             int off = 0;
             int next;
             while ((next = cp.indexOf(File.pathSeparator, off)) != -1) {

@@ -187,17 +190,20 @@
             String element = cp.substring(off);
             if (element.length() > 0 || !skipEmptyElements) {
                 URL url = toFileURL(element);
                 if (url != null) path.add(url);
             }
-
-            // push the URLs
-            for (int i = path.size() - 1; i >= 0; --i) {
-                unopenedUrls.push(path.get(i));
-            }
         }
 
+        // can't use ArrayDeque#addAll or new ArrayDeque(Collection);
+        // it's too early in the bootstrap to trigger use of lambdas
+        int size = path.size();
+        ArrayDeque<URL> unopenedUrls = new ArrayDeque<>(size);
+        for (int i = 0; i < size; i++)
+            unopenedUrls.add(path.get(i));
+
+        this.unopenedUrls = unopenedUrls;
         this.path = path;
         this.jarHandler = null;
         this.acc = null;
     }
 

@@ -223,20 +229,19 @@
      * <p>
      * If the URL specified is null or is already in the list of
      * URLs, then invoking this method has no effect.
      */
     public synchronized void addURL(URL url) {
-        if (closed)
+        if (closed || url == null)
             return;
         synchronized (unopenedUrls) {
-            if (url == null || path.contains(url))
-                return;
-
-            unopenedUrls.add(0, url);
+            if (! path.contains(url)) {
+                unopenedUrls.addLast(url);
             path.add(url);
         }
     }
+    }
 
     /**
      * Appends the specified file path as a file URL to the search path.
      */
     public void addFile(String s) {

@@ -412,20 +417,17 @@
     private synchronized Loader getLoader(int index) {
         if (closed) {
             return null;
         }
          // Expand URL search path until the request can be satisfied
-         // or the URL stack is empty.
+        // or unopenedUrls is exhausted.
         while (loaders.size() < index + 1) {
-            // Pop the next URL from the URL stack
-            URL url;
+            final URL url;
             synchronized (unopenedUrls) {
-                if (unopenedUrls.empty()) {
+                url = unopenedUrls.pollFirst();
+                if (url == null)
                     return null;
-                } else {
-                    url = unopenedUrls.pop();
-                }
             }
             // Skip this URL if it already has a Loader. (Loader
             // may be null in the case where URL has not been opened
             // but is referenced by a JAR index.)
             String urlNoFragString = URLUtil.urlNoFragString(url);

@@ -435,11 +437,11 @@
             // Otherwise, create a new Loader for the URL.
             Loader loader;
             try {
                 loader = getLoader(url);
                 // If the loader defines a local class path then add the
-                // URLs to the list of URLs to be opened.
+                // URLs as the next URLs to be opened.
                 URL[] urls = loader.getClassPath();
                 if (urls != null) {
                     push(urls);
                 }
             } catch (IOException e) {

@@ -500,16 +502,16 @@
         URLStreamHandler h = JNUA.getHandler(u);
         return h instanceof sun.net.www.protocol.jar.Handler;
     }
 
     /*
-     * Pushes the specified URLs onto the list of unopened URLs.
+     * Pushes the specified URLs onto the head of unopened URLs.
      */
     private void push(URL[] urls) {
         synchronized (unopenedUrls) {
             for (int i = urls.length - 1; i >= 0; --i) {
-                unopenedUrls.push(urls[i]);
+                unopenedUrls.addFirst(urls[i]);
             }
         }
     }
 
     /*