Initial load
diff --git a/jdk/src/share/classes/sun/security/provider/certpath/AdjacencyList.java b/jdk/src/share/classes/sun/security/provider/certpath/AdjacencyList.java
new file mode 100644
index 0000000..e31c8fc
--- /dev/null
+++ b/jdk/src/share/classes/sun/security/provider/certpath/AdjacencyList.java
@@ -0,0 +1,270 @@
+/*
+ * Copyright 2000-2006 Sun Microsystems, Inc. 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. Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+package sun.security.provider.certpath;
+
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+
+/**
+ * An AdjacencyList is used to store the history of certification paths
+ * attempted in constructing a path from an initiator to a target. The
+ * AdjacencyList is initialized with a <code>List</code> of
+ * <code>List</code>s, where each sub-<code>List</code> contains objects of
+ * type <code>Vertex</code>. A <code>Vertex</code> describes one possible or
+ * actual step in the chain building process, and the associated
+ * <code>Certificate</code>. Specifically, a <code>Vertex</code> object
+ * contains a <code>Certificate</code> and an index value referencing the
+ * next sub-list in the process. If the index value is -1 then this
+ * <code>Vertex</code> doesn't continue the attempted build path.
+ * <p>
+ * Example:
+ * <p>
+ * Attempted Paths:<ul>
+ * <li>C1->C2->C3
+ * <li>C1->C4->C5
+ * <li>C1->C4->C6
+ * <li>C1->C4->C7
+ * <li>C1->C8->C9
+ * <li>C1->C10->C11
+ * </ul>
+ * <p>
+ * AdjacencyList structure:<ul>
+ * <li>AL[0] = C1,1
+ * <li>AL[1] = C2,2 =>C4,3 =>C8,4 =>C10,5
+ * <li>AL[2] = C3,-1
+ * <li>AL[3] = C5,-1 =>C6,-1 =>C7,-1
+ * <li>AL[4] = C9,-1
+ * <li>AL[5] = C11,-1
+ * </ul>
+ * <p>
+ * The iterator method returns objects of type <code>BuildStep</code>, not
+ * objects of type <code>Vertex</code>.
+ * A <code>BuildStep</code> contains a <code>Vertex</code> and a result code,
+ * accessable via getResult method. There are five result values.
+ * <code>POSSIBLE</code> denotes that the current step represents a
+ * <code>Certificate</code> that the builder is considering at this point in
+ * the build. <code>FOLLOW</code> denotes a <code>Certificate</code> (one of
+ * those noted as <code>POSSIBLE</code>) that the builder is using to try
+ * extending the chain. <code>BACK</code> represents that a
+ * <code>FOLLOW</code> was incorrect, and is being removed from the chain.
+ * There is exactly one <code>FOLLOW</code> for each <code>BACK</code>. The
+ * values <code>SUCCEED</code> and <code>FAIL</code> mean that we've come to
+ * the end of the build process, and there will not be any more entries in
+ * the list.
+ * <p>
+ * @see sun.security.provider.certpath.BuildStep
+ * @see sun.security.provider.certpath.Vertex
+ * <p>
+ * @author seth proctor
+ * @since 1.4
+ */
+public class AdjacencyList {
+
+ // the actual set of steps the AdjacencyList represents
+ private ArrayList<BuildStep> mStepList;
+
+ // the original list, just for the toString method
+ private List<List<Vertex>> mOrigList;
+
+ /**
+ * Constructs a new <code>AdjacencyList</code> based on the specified
+ * <code>List</code>. See the example above.
+ *
+ * @param list a <code>List</code> of <code>List</code>s of
+ * <code>Vertex</code> objects
+ */
+ public AdjacencyList(List<List<Vertex>> list) {
+ mStepList = new ArrayList<BuildStep>();
+ mOrigList = list;
+ buildList(list, 0, null);
+ }
+
+ /**
+ * Gets an <code>Iterator</code> to iterate over the set of
+ * <code>BuildStep</code>s in build-order. Any attempts to change
+ * the list through the remove method will fail.
+ *
+ * @return an <code>Iterator</code> over the <code>BuildStep</code>s
+ */
+ public Iterator<BuildStep> iterator() {
+ return Collections.unmodifiableList(mStepList).iterator();
+ }
+
+ /**
+ * Recursive, private method which actually builds the step list from
+ * the given adjacency list. <code>Follow</code> is the parent BuildStep
+ * that we followed to get here, and if it's null, it means that we're
+ * at the start.
+ */
+ private boolean buildList(List<List<Vertex>> theList, int index,
+ BuildStep follow) {
+
+ // Each time this method is called, we're examining a new list
+ // from the global list. So, we have to start by getting the list
+ // that contains the set of Vertexes we're considering.
+ List<Vertex> l = theList.get(index);
+
+ try {
+ // we're interested in the case where all indexes are -1...
+ boolean allNegOne = true;
+ // ...and in the case where every entry has a Throwable
+ boolean allXcps = true;
+
+ for (Vertex v : l) {
+ if (v.getIndex() != -1) {
+ // count an empty list the same as an index of -1...this
+ // is to patch a bug somewhere in the builder
+ if (theList.get(v.getIndex()).size() != 0)
+ allNegOne = false;
+ }
+ else
+ if (v.getThrowable() == null)
+ allXcps = false;
+
+ // every entry, regardless of the final use for it, is always
+ // entered as a possible step before we take any actions
+ mStepList.add(new BuildStep(v, BuildStep.POSSIBLE));
+ }
+
+ if (allNegOne) {
+ // There are two cases that we could be looking at here. We
+ // may need to back up, or the build may have succeeded at
+ // this point. This is based on whether or not any
+ // exceptions were found in the list.
+ if (allXcps) {
+ // we need to go back...see if this is the last one
+ if (follow == null)
+ mStepList.add(new BuildStep(null, BuildStep.FAIL));
+ else
+ mStepList.add(new BuildStep(follow.getVertex(),
+ BuildStep.BACK));
+
+ return false;
+ } else {
+ // we succeeded...now the only question is which is the
+ // successful step? If there's only one entry without
+ // a throwable, then that's the successful step. Otherwise,
+ // we'll have to make some guesses...
+ List<Vertex> possibles = new ArrayList<Vertex>();
+ for (Vertex v : l) {
+ if (v.getThrowable() == null)
+ possibles.add(v);
+ }
+
+ if (possibles.size() == 1) {
+ // real easy...we've found the final Vertex
+ mStepList.add(new BuildStep(possibles.get(0),
+ BuildStep.SUCCEED));
+ } else {
+ // ok...at this point, there is more than one Cert
+ // which might be the succeed step...how do we know
+ // which it is? I'm going to assume that our builder
+ // algorithm is good enough to know which is the
+ // correct one, and put it first...but a FIXME goes
+ // here anyway, and we should be comparing to the
+ // target/initiator Cert...
+ mStepList.add(new BuildStep(possibles.get(0),
+ BuildStep.SUCCEED));
+ }
+
+ return true;
+ }
+ } else {
+ // There's at least one thing that we can try before we give
+ // up and go back. Run through the list now, and enter a new
+ // BuildStep for each path that we try to follow. If none of
+ // the paths we try produce a successful end, we're going to
+ // have to back out ourselves.
+ boolean success = false;
+
+ for (Vertex v : l) {
+
+ // Note that we'll only find a SUCCEED case when we're
+ // looking at the last possible path, so we don't need to
+ // consider success in the while loop
+
+ if (v.getIndex() != -1) {
+ if (theList.get(v.getIndex()).size() != 0) {
+ // If the entry we're looking at doesn't have an
+ // index of -1, and doesn't lead to an empty list,
+ // then it's something we follow!
+ BuildStep bs = new BuildStep(v, BuildStep.FOLLOW);
+ mStepList.add(bs);
+ success = buildList(theList, v.getIndex(), bs);
+ }
+ }
+ }
+
+ if (success) {
+ // We're already finished!
+ return true;
+ } else {
+ // We failed, and we've exhausted all the paths that we
+ // could take. The only choice is to back ourselves out.
+ if (follow == null)
+ mStepList.add(new BuildStep(null, BuildStep.FAIL));
+ else
+ mStepList.add(new BuildStep(follow.getVertex(),
+ BuildStep.BACK));
+
+ return false;
+ }
+ }
+ }
+ catch (Exception e) {}
+
+ // we'll never get here, but you know java...
+ return false;
+ }
+
+ /**
+ * Prints out a string representation of this AdjacencyList.
+ *
+ * @return String representation
+ */
+ public String toString() {
+ String out = "[\n";
+
+ int i = 0;
+ for (List<Vertex> l : mOrigList) {
+ out = out + "LinkedList[" + i++ + "]:\n";
+
+ for (Vertex step : l) {
+ try {
+ out = out + step.toString();
+ out = out + "\n";
+ }
+ catch (Exception e) { out = out + "No Such Element\n"; }
+ }
+ }
+ out = out + "]\n";
+
+ return out;
+ }
+}