001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * // Copyright (c) 1998, 2007, Oracle. All rights reserved.
005: *
006: *
007: * The contents of this file are subject to the terms of either the GNU
008: * General Public License Version 2 only ("GPL") or the Common Development
009: * and Distribution License("CDDL") (collectively, the "License"). You
010: * may not use this file except in compliance with the License. You can obtain
011: * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
012: * or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific
013: * language governing permissions and limitations under the License.
014: *
015: * When distributing the software, include this License Header Notice in each
016: * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
017: * Sun designates this particular file as subject to the "Classpath" exception
018: * as provided by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the License
020: * Header, with the fields enclosed by brackets [] replaced by your own
021: * identifying information: "Portions Copyrighted [year]
022: * [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * If you wish your version of this file to be governed by only the CDDL or
027: * only the GPL Version 2, indicate your decision by adding "[Contributor]
028: * elects to include this software in this distribution under the [CDDL or GPL
029: * Version 2] license." If you don't indicate a single choice of license, a
030: * recipient has the option to distribute your version of this file under
031: * either the CDDL, the GPL Version 2 or to extend the choice of license to
032: * its licensees as provided above. However, if you add GPL Version 2 code
033: * and therefore, elected the GPL Version 2 license, then the option applies
034: * only if the new code is made subject to such option by the copyright
035: * holder.
036: */
037: package oracle.toplink.essentials.internal.sessions;
038:
039: import java.util.*;
040: import oracle.toplink.essentials.descriptors.ClassDescriptor;
041:
042: /**
043: * This class calculates a commit order for a series of classes
044: * based on the dependencies between them. It builds up a graph of
045: * dependencies (CommitOrderDependencyNodes) then applies topological
046: * sort to them to get an ordering.
047: * This is a throwaway class, which exists only for the lifetime of
048: * the calculation.
049: *
050: * The algorithm is descrbied in the method comment for orderCommits().
051: * This class also includes static methods for quicksort, copied from
052: * the standard libraries and adapted for these objects, since that
053: * seemed like the easiest way to sort.
054: */
055: public class CommitOrderCalculator {
056: protected int currentTime;
057: protected Vector nodes;
058: protected Vector orderedDescriptors;
059: protected AbstractSession session;
060:
061: /**
062: *
063: */
064: public CommitOrderCalculator(AbstractSession session) {
065: super ();
066: this .currentTime = 0;
067: this .nodes = new Vector(1);
068: this .session = session;
069: }
070:
071: protected void addNode(ClassDescriptor d) {
072: nodes
073: .addElement(new CommitOrderDependencyNode(this , d,
074: session));
075: }
076:
077: public void addNodes(Vector descriptors) {
078: Enumeration descriptorsEnum = descriptors.elements();
079: while (descriptorsEnum.hasMoreElements()) {
080: ClassDescriptor descriptor = (ClassDescriptor) descriptorsEnum
081: .nextElement();
082: addNode(descriptor);
083: }
084: }
085:
086: /*
087: * Add to each node the dependent nodes
088: */
089: public void calculateMappingDependencies() {
090: for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
091: CommitOrderDependencyNode node = (CommitOrderDependencyNode) e
092: .nextElement();
093: node.recordMappingDependencies();
094: }
095: }
096:
097: /*
098: * Add to each node the dependent nodes
099: */
100: public void calculateSpecifiedDependencies() {
101: for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
102: CommitOrderDependencyNode node = (CommitOrderDependencyNode) e
103: .nextElement();
104: node.recordSpecifiedDependencies();
105: }
106: }
107:
108: public void depthFirstSearch() {
109:
110: /*
111: * Traverse the entire graph in breadth-first order. When finished, every node will have a
112: * predecessor which indicates the node that came efore it in the search
113: * It will also have a discovery time (the value of the counter when we first saw it) and
114: * finishingTime (the value of the counter after we've visited all the adjacent nodes).
115: * See Cormen, Leiserson and Rivest, Section 23.3, page 477 for a full explanation of the algorithm
116: */
117:
118: //Setup
119: for (Enumeration e = getNodes().elements(); e.hasMoreElements();) {
120: CommitOrderDependencyNode node = (CommitOrderDependencyNode) e
121: .nextElement();
122: node.markNotVisited();
123: node.setPredecessor(null);
124: }
125: currentTime = 0;
126:
127: //Execution
128: for (Enumeration e = getNodes().elements(); e.hasMoreElements();) {
129: CommitOrderDependencyNode node = (CommitOrderDependencyNode) e
130: .nextElement();
131: if (node.hasNotBeenVisited()) {
132: node.visit();
133: }
134: }
135: }
136:
137: /* Support for quicksort */
138: /*
139: * Implement the doCompare method.
140: */
141: private static int doCompare(Object o1, Object o2) {
142: // I don't care if they're equal, and I want to sort largest first.
143: int first;
144:
145: // I don't care if they're equal, and I want to sort largest first.
146: int second;
147: first = ((CommitOrderDependencyNode) o1).getFinishingTime();
148: second = ((CommitOrderDependencyNode) o2).getFinishingTime();
149: if (first >= second) {
150: return 1;
151: } else {
152: return -1;
153: }
154: }
155:
156: /* Support for quicksort */
157: /*
158: * Implement the doCompare method.
159: */
160: private static int doCompare(CommitOrderDependencyNode o1,
161: CommitOrderDependencyNode o2) {
162: // I don't care if they're equal, and I want to sort largest first.
163: int first;
164:
165: // I don't care if they're equal, and I want to sort largest first.
166: int second;
167: first = o1.getFinishingTime();
168: second = o2.getFinishingTime();
169: if (first >= second) {
170: return 1;
171: } else {
172: return -1;
173: }
174: }
175:
176: public int getNextTime() {
177: int result = currentTime;
178: currentTime++;
179: return result;
180: }
181:
182: public Vector getNodes() {
183: return nodes;
184: }
185:
186: /*
187: * Return the constraint ordered classes.
188: */
189: public Vector getOrderedClasses() {
190: Vector orderedClasses = oracle.toplink.essentials.internal.helper.NonSynchronizedVector
191: .newInstance(getOrderedDescriptors().size());
192: for (Enumeration orderedDescriptorsEnum = getOrderedDescriptors()
193: .elements(); orderedDescriptorsEnum.hasMoreElements();) {
194: orderedClasses
195: .addElement(((ClassDescriptor) orderedDescriptorsEnum
196: .nextElement()).getJavaClass());
197: }
198:
199: return orderedClasses;
200: }
201:
202: /*
203: * Return the constraint ordered descriptors.
204: */
205: public Vector getOrderedDescriptors() {
206: return orderedDescriptors;
207: }
208:
209: public CommitOrderDependencyNode nodeFor(Class c) {
210: for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
211: CommitOrderDependencyNode n = (CommitOrderDependencyNode) e
212: .nextElement();
213: if (n.getDescriptor().getJavaClass() == c) {
214: return n;
215: }
216: }
217: return null;
218: }
219:
220: public CommitOrderDependencyNode nodeFor(ClassDescriptor d) {
221: for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
222: CommitOrderDependencyNode n = (CommitOrderDependencyNode) e
223: .nextElement();
224: if (n.getDescriptor() == d) {
225: return n;
226: }
227: }
228: return null;
229: }
230:
231: /*
232: * Calculate the commit order.
233: * Do a depth first search on the graph, skipping nodes that we have
234: * already visited or are in the process of visiting. Keep a counter
235: * and note when we first encounter a node and when we finish visiting
236: * it. Once we've visited everything, sort nodes by finishing time
237: */
238: public void orderCommits() {
239: depthFirstSearch();
240:
241: Object[] nodeArray = new Object[nodes.size()];
242: nodes.copyInto(nodeArray);
243:
244: quicksort(nodeArray);
245: Vector result = new Vector(nodes.size());
246: for (int i = 0; i < nodes.size(); i++) {
247: CommitOrderDependencyNode node = (CommitOrderDependencyNode) nodeArray[i];
248: result.addElement(node.getDescriptor());
249: }
250: this .orderedDescriptors = result;
251: }
252:
253: /*
254: * Preform a sort using the specified comparitor object.
255: */
256: private static void quicksort(Object[] arr) {
257: quicksort(arr, 0, arr.length - 1);
258: }
259:
260: /*
261: * quicksort the array of objects.
262: *
263: * @param arr[] - an array of objects
264: * @param left - the start index - from where to begin sorting
265: * @param right - the last index.
266: */
267: private static void quicksort(Object[] arr, int left, int right) {
268: int i;
269: int last;
270:
271: if (left >= right) {/* do nothing if array contains fewer than two */
272: return;/* two elements */
273: }
274: swap(arr, left, (left + right) / 2);
275: last = left;
276: for (i = left + 1; i <= right; i++) {
277: if (doCompare(arr[i], arr[left]) < 0) {
278: swap(arr, ++last, i);
279: }
280: }
281: swap(arr, left, last);
282: quicksort(arr, left, last - 1);
283: quicksort(arr, last + 1, right);
284: }
285:
286: private static void swap(Object[] arr, int i, int j) {
287: Object tmp;
288:
289: tmp = arr[i];
290: arr[i] = arr[j];
291: arr[j] = tmp;
292: }
293: }
|