ojluni/src/main/java/sun/security/jca/ProviderList.java - platform/libcore.git - Git at Google

 /*
  * Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the LICENSE file that accompanied this code.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */

 package sun.security.jca;

 import java.util.*;

 import java.security.*;
 import java.security.Provider.Service;

 /**
  * List of Providers. Used to represent the provider preferences.
  *
  * The system starts out with a ProviderList that only has the classNames
  * of the Providers. Providers are loaded on demand only when needed.
  *
  * For compatibility reasons, Providers that could not be loaded are ignored
  * and internally presented as the instance EMPTY_PROVIDER. However, those
  * objects cannot be presented to applications. Call the convert() method
  * to force all Providers to be loaded and to obtain a ProviderList with
  * invalid entries removed. All this is handled by the Security class.
  *
  * Note that all indices used by this class are 0-based per general Java
  * convention. These must be converted to the 1-based indices used by the
  * Security class externally when needed.
  *
  * Instances of this class are immutable. This eliminates the need for
  * cloning and synchronization in consumers. The add() and remove() style
  * methods are static in order to avoid confusion about the immutability.
  *
  * @author  Andreas Sterbenz
  * @since   1.5
  */
 public final class ProviderList {

     final static sun.security.util.Debug debug =
         sun.security.util.Debug.getInstance("jca", "ProviderList");

     private final static ProviderConfig[] PC0 = new ProviderConfig[0];

     private final static Provider[] P0 = new Provider[0];

     // constant for an ProviderList with no elements
     static final ProviderList EMPTY = new ProviderList(PC0, true);

     // dummy provider object to use during initialization
     // used to avoid explicit null checks in various places
     private static final Provider EMPTY_PROVIDER =
         new Provider("##Empty##", 1.0d, "initialization in progress") {
             // override getService() to return null slightly faster
             public Service getService(String type, String algorithm) {
                 return null;
             }
         };

     // construct a ProviderList from the security properties
     // (static provider configuration in the java.security file)
     static ProviderList fromSecurityProperties() {
         // doPrivileged() because of Security.getProperty()
         return AccessController.doPrivileged(
                         new PrivilegedAction<ProviderList>() {
             public ProviderList run() {
                 return new ProviderList();
             }
         });
     }

     public static ProviderList add(ProviderList providerList, Provider p) {
         return insertAt(providerList, p, -1);
     }

     public static ProviderList insertAt(ProviderList providerList, Provider p,
             int position) {
         if (providerList.getProvider(p.getName()) != null) {
             return providerList;
         }
         List<ProviderConfig> list = new ArrayList<>
                                     (Arrays.asList(providerList.configs));
         int n = list.size();
         if ((position < 0) || (position > n)) {
             position = n;
         }
         list.add(position, new ProviderConfig(p));
         return new ProviderList(list.toArray(PC0), true);
     }

     public static ProviderList remove(ProviderList providerList, String name) {
         // make sure provider exists
         if (providerList.getProvider(name) == null) {
             return providerList;
         }
         // copy all except matching to new list
         ProviderConfig[] configs = new ProviderConfig[providerList.size() - 1];
         int j = 0;
         for (ProviderConfig config : providerList.configs) {
             if (config.getProvider().getName().equals(name) == false) {
                 configs[j++] = config;
             }
         }
         return new ProviderList(configs, true);
     }

     // Create a new ProviderList from the specified Providers.
     // This method is for use by SunJSSE.
     public static ProviderList newList(Provider ... providers) {
         ProviderConfig[] configs = new ProviderConfig[providers.length];
         for (int i = 0; i < providers.length; i++) {
             configs[i] = new ProviderConfig(providers[i]);
         }
         return new ProviderList(configs, true);
     }

     // configuration of the providers
     private final ProviderConfig[] configs;

     // flag indicating whether all configs have been loaded successfully
     private volatile boolean allLoaded;

     // List returned by providers()
     private final List<Provider> userList = new AbstractList<Provider>() {
         public int size() {
             return configs.length;
         }
         public Provider get(int index) {
             return getProvider(index);
         }
     };

     /**
      * Create a new ProviderList from an array of configs
      */
     private ProviderList(ProviderConfig[] configs, boolean allLoaded) {
         this.configs = configs;
         this.allLoaded = allLoaded;
     }

     /**
      * Return a new ProviderList parsed from the java.security Properties.
      */
     private ProviderList() {
         List<ProviderConfig> configList = new ArrayList<>();
         for (int i = 1; true; i++) {
             String entry = Security.getProperty("security.provider." + i);
             if (entry == null) {
                 break;
             }
             entry = entry.trim();
             if (entry.length() == 0) {
                 System.err.println("invalid entry for " +
                                    "security.provider." + i);
                 break;
             }
             int k = entry.indexOf(' ');
             ProviderConfig config;
             if (k == -1) {
                 config = new ProviderConfig(entry);
             } else {
                 String className = entry.substring(0, k);
                 String argument = entry.substring(k + 1).trim();
                 config = new ProviderConfig(className, argument);
             }

             // Get rid of duplicate providers.
             if (configList.contains(config) == false) {
                 configList.add(config);
             }
         }
         configs = configList.toArray(PC0);
         if (debug != null) {
             debug.println("provider configuration: " + configList);
         }
     }

     /**
      * Construct a special ProviderList for JAR verification. It consists
      * of the providers specified via jarClassNames, which must be on the
      * bootclasspath and cannot be in signed JAR files. This is to avoid
      * possible recursion and deadlock during verification.
      */
     ProviderList getJarList(String[] jarClassNames) {
         List<ProviderConfig> newConfigs = new ArrayList<>();
         for (String className : jarClassNames) {
             ProviderConfig newConfig = new ProviderConfig(className);
             for (ProviderConfig config : configs) {
                 // if the equivalent object is present in this provider list,
                 // use the old object rather than the new object.
                 // this ensures that when the provider is loaded in the
                 // new thread local list, it will also become available
                 // in this provider list
                 if (config.equals(newConfig)) {
                     newConfig = config;
                     break;
                 }
             }
             newConfigs.add(newConfig);
         }
         ProviderConfig[] configArray = newConfigs.toArray(PC0);
         return new ProviderList(configArray, false);
     }

     public int size() {
         return configs.length;
     }

     /**
      * Return the Provider at the specified index. Returns EMPTY_PROVIDER
      * if the provider could not be loaded at this time.
      */
     Provider getProvider(int index) {
         Provider p = configs[index].getProvider();
         return (p != null) ? p : EMPTY_PROVIDER;
     }

     /**
      * Return an unmodifiable List of all Providers in this List. The
      * individual Providers are loaded on demand. Elements that could not
      * be initialized are replaced with EMPTY_PROVIDER.
      */
     public List<Provider> providers() {
         return userList;
     }

     private ProviderConfig getProviderConfig(String name) {
         int index = getIndex(name);
         return (index != -1) ? configs[index] : null;
     }

     // return the Provider with the specified name or null
     public Provider getProvider(String name) {
         ProviderConfig config = getProviderConfig(name);
         return (config == null) ? null : config.getProvider();
     }

     /**
      * Return the index at which the provider with the specified name is
      * installed or -1 if it is not present in this ProviderList.
      */
     public int getIndex(String name) {
         for (int i = 0; i < configs.length; i++) {
             Provider p = getProvider(i);
             if (p.getName().equals(name)) {
                 return i;
             }
         }
         return -1;
     }

     // attempt to load all Providers not already loaded
     private int loadAll() {
         if (allLoaded) {
             return configs.length;
         }
         if (debug != null) {
             debug.println("Loading all providers");
             new Exception("Call trace").printStackTrace();
         }
         int n = 0;
         for (int i = 0; i < configs.length; i++) {
             Provider p = configs[i].getProvider();
             if (p != null) {
                 n++;
             }
         }
         if (n == configs.length) {
             allLoaded = true;
         }
         return n;
     }

     /**
      * Try to load all Providers and return the ProviderList. If one or
      * more Providers could not be loaded, a new ProviderList with those
      * entries removed is returned. Otherwise, the method returns this.
      */
     ProviderList removeInvalid() {
         int n = loadAll();
         if (n == configs.length) {
             return this;
         }
         ProviderConfig[] newConfigs = new ProviderConfig[n];
         for (int i = 0, j = 0; i < configs.length; i++) {
             ProviderConfig config = configs[i];
             if (config.isLoaded()) {
                 newConfigs[j++] = config;
             }
         }
         return new ProviderList(newConfigs, true);
     }

     // return the providers as an array
     public Provider[] toArray() {
         return providers().toArray(P0);
     }

     // return a String representation of this ProviderList
     public String toString() {
         return Arrays.asList(configs).toString();
     }

     /**
      * Return a Service describing an implementation of the specified
      * algorithm from the Provider with the highest precedence that
      * supports that algorithm. Return null if no Provider supports this
      * algorithm.
      */
     public Service getService(String type, String name) {
         for (int i = 0; i < configs.length; i++) {
             Provider p = getProvider(i);
             Service s = p.getService(type, name);
             if (s != null) {
                 return s;
             }
         }
         return null;
     }

     /**
      * Return a List containing all the Services describing implementations
      * of the specified algorithms in precedence order. If no implementation
      * exists, this method returns an empty List.
      *
      * The elements of this list are determined lazily on demand.
      *
      * The List returned is NOT thread safe.
      */
     public List<Service> getServices(String type, String algorithm) {
         return new ServiceList(type, algorithm);
     }

     /**
      * This method exists for compatibility with JCE only. It will be removed
      * once JCE has been changed to use the replacement method.
      * @deprecated use getServices(List<ServiceId>) instead
      */
     @Deprecated
     public List<Service> getServices(String type, List<String> algorithms) {
         List<ServiceId> ids = new ArrayList<>();
         for (String alg : algorithms) {
             ids.add(new ServiceId(type, alg));
         }
         return getServices(ids);
     }

     public List<Service> getServices(List<ServiceId> ids) {
         return new ServiceList(ids);
     }

     /**
      * Inner class for a List of Services. Custom List implementation in
      * order to delay Provider initialization and lookup.
      * Not thread safe.
      */
     private final class ServiceList extends AbstractList<Service> {

         // type and algorithm for simple lookup
         // avoid allocating/traversing the ServiceId list for these lookups
         private final String type;
         private final String algorithm;

         // list of ids for parallel lookup
         // if ids is non-null, type and algorithm are null
         private final List<ServiceId> ids;

         // first service we have found
         // it is stored in a separate variable so that we can avoid
         // allocating the services list if we do not need the second service.
         // this is the case if we don't failover (failovers are typically rare)
         private Service firstService;

         // list of the services we have found so far
         private List<Service> services;

         // index into config[] of the next provider we need to query
         private int providerIndex;

         ServiceList(String type, String algorithm) {
             this.type = type;
             this.algorithm = algorithm;
             this.ids = null;
         }

         ServiceList(List<ServiceId> ids) {
             this.type = null;
             this.algorithm = null;
             this.ids = ids;
         }

         private void addService(Service s) {
             if (firstService == null) {
                 firstService = s;
             } else {
                 if (services == null) {
                     services = new ArrayList<Service>(4);
                     services.add(firstService);
                 }
                 services.add(s);
             }
         }

         private Service tryGet(int index) {
             while (true) {
                 if ((index == 0) && (firstService != null)) {
                     return firstService;
                 } else if ((services != null) && (services.size() > index)) {
                     return services.get(index);
                 }
                 if (providerIndex >= configs.length) {
                     return null;
                 }
                 // check all algorithms in this provider before moving on
                 Provider p = getProvider(providerIndex++);
                 if (type != null) {
                     // simple lookup
                     Service s = p.getService(type, algorithm);
                     if (s != null) {
                         addService(s);
                     }
                 } else {
                     // parallel lookup
                     for (ServiceId id : ids) {
                         Service s = p.getService(id.type, id.algorithm);
                         if (s != null) {
                             addService(s);
                         }
                     }
                 }
             }
         }

         public Service get(int index) {
             Service s = tryGet(index);
             if (s == null) {
                 throw new IndexOutOfBoundsException();
             }
             return s;
         }

         public int size() {
             int n;
             if (services != null) {
                 n = services.size();
             } else {
                 n = (firstService != null) ? 1 : 0;
             }
             while (tryGet(n) != null) {
                 n++;
             }
             return n;
         }

         // override isEmpty() and iterator() to not call size()
         // this avoids loading + checking all Providers

         public boolean isEmpty() {
             return (tryGet(0) == null);
         }

         public Iterator<Service> iterator() {
             return new Iterator<Service>() {
                 int index;

                 public boolean hasNext() {
                     return tryGet(index) != null;
                 }

                 public Service next() {
                     Service s = tryGet(index);
                     if (s == null) {
                         throw new NoSuchElementException();
                     }
                     index++;
                     return s;
                 }

                 public void remove() {
                     throw new UnsupportedOperationException();
                 }
             };
         }
     }

 }
	/*
	* Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package sun.security.jca;

	import java.util.*;

	import java.security.*;
	import java.security.Provider.Service;

	/**
	* List of Providers. Used to represent the provider preferences.
	*
	* The system starts out with a ProviderList that only has the classNames
	* of the Providers. Providers are loaded on demand only when needed.
	*
	* For compatibility reasons, Providers that could not be loaded are ignored
	* and internally presented as the instance EMPTY_PROVIDER. However, those
	* objects cannot be presented to applications. Call the convert() method
	* to force all Providers to be loaded and to obtain a ProviderList with
	* invalid entries removed. All this is handled by the Security class.
	*
	* Note that all indices used by this class are 0-based per general Java
	* convention. These must be converted to the 1-based indices used by the
	* Security class externally when needed.
	*
	* Instances of this class are immutable. This eliminates the need for
	* cloning and synchronization in consumers. The add() and remove() style
	* methods are static in order to avoid confusion about the immutability.
	*
	* @author Andreas Sterbenz
	* @since 1.5
	*/
	public final class ProviderList {

	final static sun.security.util.Debug debug =
	sun.security.util.Debug.getInstance("jca", "ProviderList");

	private final static ProviderConfig[] PC0 = new ProviderConfig[0];

	private final static Provider[] P0 = new Provider[0];

	// constant for an ProviderList with no elements
	static final ProviderList EMPTY = new ProviderList(PC0, true);

	// dummy provider object to use during initialization
	// used to avoid explicit null checks in various places
	private static final Provider EMPTY_PROVIDER =
	new Provider("##Empty##", 1.0d, "initialization in progress") {
	// override getService() to return null slightly faster
	public Service getService(String type, String algorithm) {
	return null;
	}
	};

	// construct a ProviderList from the security properties
	// (static provider configuration in the java.security file)
	static ProviderList fromSecurityProperties() {
	// doPrivileged() because of Security.getProperty()
	return AccessController.doPrivileged(
	new PrivilegedAction<ProviderList>() {
	public ProviderList run() {
	return new ProviderList();
	}
	});
	}

	public static ProviderList add(ProviderList providerList, Provider p) {
	return insertAt(providerList, p, -1);
	}

	public static ProviderList insertAt(ProviderList providerList, Provider p,
	int position) {
	if (providerList.getProvider(p.getName()) != null) {
	return providerList;
	}
	List<ProviderConfig> list = new ArrayList<>
	(Arrays.asList(providerList.configs));
	int n = list.size();
	if ((position < 0) \|\| (position > n)) {
	position = n;
	}
	list.add(position, new ProviderConfig(p));
	return new ProviderList(list.toArray(PC0), true);
	}

	public static ProviderList remove(ProviderList providerList, String name) {
	// make sure provider exists
	if (providerList.getProvider(name) == null) {
	return providerList;
	}
	// copy all except matching to new list
	ProviderConfig[] configs = new ProviderConfig[providerList.size() - 1];
	int j = 0;
	for (ProviderConfig config : providerList.configs) {
	if (config.getProvider().getName().equals(name) == false) {
	configs[j++] = config;
	}
	}
	return new ProviderList(configs, true);
	}

	// Create a new ProviderList from the specified Providers.
	// This method is for use by SunJSSE.
	public static ProviderList newList(Provider ... providers) {
	ProviderConfig[] configs = new ProviderConfig[providers.length];
	for (int i = 0; i < providers.length; i++) {
	configs[i] = new ProviderConfig(providers[i]);
	}
	return new ProviderList(configs, true);
	}

	// configuration of the providers
	private final ProviderConfig[] configs;

	// flag indicating whether all configs have been loaded successfully
	private volatile boolean allLoaded;

	// List returned by providers()
	private final List<Provider> userList = new AbstractList<Provider>() {
	public int size() {
	return configs.length;
	}
	public Provider get(int index) {
	return getProvider(index);
	}
	};

	/**
	* Create a new ProviderList from an array of configs
	*/
	private ProviderList(ProviderConfig[] configs, boolean allLoaded) {
	this.configs = configs;
	this.allLoaded = allLoaded;
	}

	/**
	* Return a new ProviderList parsed from the java.security Properties.
	*/
	private ProviderList() {
	List<ProviderConfig> configList = new ArrayList<>();
	for (int i = 1; true; i++) {
	String entry = Security.getProperty("security.provider." + i);
	if (entry == null) {
	break;
	}
	entry = entry.trim();
	if (entry.length() == 0) {
	System.err.println("invalid entry for " +
	"security.provider." + i);
	break;
	}
	int k = entry.indexOf(' ');
	ProviderConfig config;
	if (k == -1) {
	config = new ProviderConfig(entry);
	} else {
	String className = entry.substring(0, k);
	String argument = entry.substring(k + 1).trim();
	config = new ProviderConfig(className, argument);
	}

	// Get rid of duplicate providers.
	if (configList.contains(config) == false) {
	configList.add(config);
	}
	}
	configs = configList.toArray(PC0);
	if (debug != null) {
	debug.println("provider configuration: " + configList);
	}
	}

	/**
	* Construct a special ProviderList for JAR verification. It consists
	* of the providers specified via jarClassNames, which must be on the
	* bootclasspath and cannot be in signed JAR files. This is to avoid
	* possible recursion and deadlock during verification.
	*/
	ProviderList getJarList(String[] jarClassNames) {
	List<ProviderConfig> newConfigs = new ArrayList<>();
	for (String className : jarClassNames) {
	ProviderConfig newConfig = new ProviderConfig(className);
	for (ProviderConfig config : configs) {
	// if the equivalent object is present in this provider list,
	// use the old object rather than the new object.
	// this ensures that when the provider is loaded in the
	// new thread local list, it will also become available
	// in this provider list
	if (config.equals(newConfig)) {
	newConfig = config;
	break;
	}
	}
	newConfigs.add(newConfig);
	}
	ProviderConfig[] configArray = newConfigs.toArray(PC0);
	return new ProviderList(configArray, false);
	}

	public int size() {
	return configs.length;
	}

	/**
	* Return the Provider at the specified index. Returns EMPTY_PROVIDER
	* if the provider could not be loaded at this time.
	*/
	Provider getProvider(int index) {
	Provider p = configs[index].getProvider();
	return (p != null) ? p : EMPTY_PROVIDER;
	}

	/**
	* Return an unmodifiable List of all Providers in this List. The
	* individual Providers are loaded on demand. Elements that could not
	* be initialized are replaced with EMPTY_PROVIDER.
	*/
	public List<Provider> providers() {
	return userList;
	}

	private ProviderConfig getProviderConfig(String name) {
	int index = getIndex(name);
	return (index != -1) ? configs[index] : null;
	}

	// return the Provider with the specified name or null
	public Provider getProvider(String name) {
	ProviderConfig config = getProviderConfig(name);
	return (config == null) ? null : config.getProvider();
	}

	/**
	* Return the index at which the provider with the specified name is
	* installed or -1 if it is not present in this ProviderList.
	*/
	public int getIndex(String name) {
	for (int i = 0; i < configs.length; i++) {
	Provider p = getProvider(i);
	if (p.getName().equals(name)) {
	return i;
	}
	}
	return -1;
	}

	// attempt to load all Providers not already loaded
	private int loadAll() {
	if (allLoaded) {
	return configs.length;
	}
	if (debug != null) {
	debug.println("Loading all providers");
	new Exception("Call trace").printStackTrace();
	}
	int n = 0;
	for (int i = 0; i < configs.length; i++) {
	Provider p = configs[i].getProvider();
	if (p != null) {
	n++;
	}
	}
	if (n == configs.length) {
	allLoaded = true;
	}
	return n;
	}

	/**
	* Try to load all Providers and return the ProviderList. If one or
	* more Providers could not be loaded, a new ProviderList with those
	* entries removed is returned. Otherwise, the method returns this.
	*/
	ProviderList removeInvalid() {
	int n = loadAll();
	if (n == configs.length) {
	return this;
	}
	ProviderConfig[] newConfigs = new ProviderConfig[n];
	for (int i = 0, j = 0; i < configs.length; i++) {
	ProviderConfig config = configs[i];
	if (config.isLoaded()) {
	newConfigs[j++] = config;
	}
	}
	return new ProviderList(newConfigs, true);
	}

	// return the providers as an array
	public Provider[] toArray() {
	return providers().toArray(P0);
	}

	// return a String representation of this ProviderList
	public String toString() {
	return Arrays.asList(configs).toString();
	}

	/**
	* Return a Service describing an implementation of the specified
	* algorithm from the Provider with the highest precedence that
	* supports that algorithm. Return null if no Provider supports this
	* algorithm.
	*/
	public Service getService(String type, String name) {
	for (int i = 0; i < configs.length; i++) {
	Provider p = getProvider(i);
	Service s = p.getService(type, name);
	if (s != null) {
	return s;
	}
	}
	return null;
	}

	/**
	* Return a List containing all the Services describing implementations
	* of the specified algorithms in precedence order. If no implementation
	* exists, this method returns an empty List.
	*
	* The elements of this list are determined lazily on demand.
	*
	* The List returned is NOT thread safe.
	*/
	public List<Service> getServices(String type, String algorithm) {
	return new ServiceList(type, algorithm);
	}

	/**
	* This method exists for compatibility with JCE only. It will be removed
	* once JCE has been changed to use the replacement method.
	* @deprecated use getServices(List<ServiceId>) instead
	*/
	@Deprecated
	public List<Service> getServices(String type, List<String> algorithms) {
	List<ServiceId> ids = new ArrayList<>();
	for (String alg : algorithms) {
	ids.add(new ServiceId(type, alg));
	}
	return getServices(ids);
	}

	public List<Service> getServices(List<ServiceId> ids) {
	return new ServiceList(ids);
	}

	/**
	* Inner class for a List of Services. Custom List implementation in
	* order to delay Provider initialization and lookup.
	* Not thread safe.
	*/
	private final class ServiceList extends AbstractList<Service> {

	// type and algorithm for simple lookup
	// avoid allocating/traversing the ServiceId list for these lookups
	private final String type;
	private final String algorithm;

	// list of ids for parallel lookup
	// if ids is non-null, type and algorithm are null
	private final List<ServiceId> ids;

	// first service we have found
	// it is stored in a separate variable so that we can avoid
	// allocating the services list if we do not need the second service.
	// this is the case if we don't failover (failovers are typically rare)
	private Service firstService;

	// list of the services we have found so far
	private List<Service> services;

	// index into config[] of the next provider we need to query
	private int providerIndex;

	ServiceList(String type, String algorithm) {
	this.type = type;
	this.algorithm = algorithm;
	this.ids = null;
	}

	ServiceList(List<ServiceId> ids) {
	this.type = null;
	this.algorithm = null;
	this.ids = ids;
	}

	private void addService(Service s) {
	if (firstService == null) {
	firstService = s;
	} else {
	if (services == null) {
	services = new ArrayList<Service>(4);
	services.add(firstService);
	}
	services.add(s);
	}
	}

	private Service tryGet(int index) {
	while (true) {
	if ((index == 0) && (firstService != null)) {
	return firstService;
	} else if ((services != null) && (services.size() > index)) {
	return services.get(index);
	}
	if (providerIndex >= configs.length) {
	return null;
	}
	// check all algorithms in this provider before moving on
	Provider p = getProvider(providerIndex++);
	if (type != null) {
	// simple lookup
	Service s = p.getService(type, algorithm);
	if (s != null) {
	addService(s);
	}
	} else {
	// parallel lookup
	for (ServiceId id : ids) {
	Service s = p.getService(id.type, id.algorithm);
	if (s != null) {
	addService(s);
	}
	}
	}
	}
	}

	public Service get(int index) {
	Service s = tryGet(index);
	if (s == null) {
	throw new IndexOutOfBoundsException();
	}
	return s;
	}

	public int size() {
	int n;
	if (services != null) {
	n = services.size();
	} else {
	n = (firstService != null) ? 1 : 0;
	}
	while (tryGet(n) != null) {
	n++;
	}
	return n;
	}

	// override isEmpty() and iterator() to not call size()
	// this avoids loading + checking all Providers

	public boolean isEmpty() {
	return (tryGet(0) == null);
	}

	public Iterator<Service> iterator() {
	return new Iterator<Service>() {
	int index;

	public boolean hasNext() {
	return tryGet(index) != null;
	}

	public Service next() {
	Service s = tryGet(index);
	if (s == null) {
	throw new NoSuchElementException();
	}
	index++;
	return s;
	}

	public void remove() {
	throw new UnsupportedOperationException();
	}
	};
	}
	}

	}