You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tomee.apache.org by xu...@apache.org on 2010/09/15 08:51:34 UTC
svn commit: r997202 - in /openejb/trunk/openejb3/container/openejb-core/src:
main/java/org/apache/openejb/util/References.java
test/java/org/apache/openejb/util/ReferencesTest.java
Author: xuhaihong
Date: Wed Sep 15 06:51:33 2010
New Revision: 997202
URL: http://svn.apache.org/viewvc?rev=997202&view=rev
Log:
OPENEJB-1309 Use double-link queue to improve the sort efficiency
Modified:
openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java
openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java
Modified: openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java
URL: http://svn.apache.org/viewvc/openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java?rev=997202&r1=997201&r2=997202&view=diff
==============================================================================
--- openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java (original)
+++ openejb/trunk/openejb3/container/openejb-core/src/main/java/org/apache/openejb/util/References.java Wed Sep 15 06:51:33 2010
@@ -22,7 +22,6 @@ import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
-import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -40,6 +39,10 @@ public class References {
public static <T> List<T> sort(List<T> objects, Visitor<T> visitor) {
+ if (objects.size() <= 1) {
+ return objects;
+ }
+
final Map<String, Node> nodes = new LinkedHashMap<String, Node>();
// Create nodes
@@ -57,9 +60,7 @@ public class References {
node.references.add(ref);
node.initialReferences.add(ref);
}
-
}
-
boolean circuitFounded = false;
for (Node node : nodes.values()) {
Set<Node> visitedNodes = new HashSet<Node>();
@@ -89,16 +90,31 @@ public class References {
throw new CircularReferencesException(all);
}
- LinkedList<Node> sortedNodes = new LinkedList<Node>();
- sortedNodes.addAll(nodes.values());
+ //Build Double Link Node List
+ Node rootNode = new Node(null, null);
+ rootNode.previous = rootNode;
+ rootNode.next = nodes.values().iterator().next();
+
+ for (Node node : nodes.values()) {
+ node.previous = rootNode.previous;
+ rootNode.previous.next = node;
+ node.next = rootNode;
+ rootNode.previous = node;
+ }
for (Node node : nodes.values()) {
for (Node reference : node.references) {
- final int i = sortedNodes.indexOf(node);
- swap(node.name, reference.name, sortedNodes);
+ swap(node, reference, rootNode);
}
}
- return unwrap(sortedNodes);
+
+ List sortedList= new ArrayList(nodes.size());
+ Node currentNode = rootNode.next;
+ while(currentNode != rootNode) {
+ sortedList.add(currentNode.object);
+ currentNode = currentNode.next;
+ }
+ return sortedList;
}
private static boolean normalizeNodeReferences(Node rootNode, Node node, Set<Node> referenceNodes) {
@@ -117,27 +133,22 @@ public class References {
return true;
}
- private static void swap(String shouldAfterNodeName, String shouldBeforeNodeName, LinkedList<Node> nodes) {
- int shouldAfterIndex = -1;
- int shouldBeforeIndex = -1;
- int index = 0;
- for (Node node : nodes) {
- if (shouldAfterIndex == -1 || shouldBeforeIndex == -1) {
- if (shouldAfterNodeName.equals(node.name)) {
- shouldAfterIndex = index;
- } else if (shouldBeforeNodeName.equals(node.name)) {
- shouldBeforeIndex = index;
- }
- index++;
- } else {
- break;
- }
- }
- System.out.println(shouldAfterNodeName + "=" + shouldAfterIndex + "\t" + shouldBeforeNodeName + "=" + shouldBeforeIndex);
- if (shouldAfterIndex < shouldBeforeIndex) {
- Node node = nodes.remove(shouldAfterIndex);
- nodes.add(shouldBeforeIndex, node);
- }
+ private static void swap(Node shouldAfterNode, Node shouldBeforeNode, Node rootNode) {
+ Node currentNode = shouldBeforeNode;
+ while(currentNode.next != rootNode) {
+ if(currentNode.next == shouldAfterNode) {
+ return;
+ }
+ currentNode = currentNode.next;
+ }
+ //Remove the shouldAfterNode from list
+ shouldAfterNode.previous.next = shouldAfterNode.next;
+ shouldAfterNode.next.previous = shouldAfterNode.previous;
+ //Insert the node immediately after the shouldBeforeNode
+ shouldAfterNode.previous = shouldBeforeNode;
+ shouldAfterNode.next = shouldBeforeNode.next;
+ shouldBeforeNode.next = shouldAfterNode;
+ shouldAfterNode.next.previous = shouldAfterNode;
}
private static <T> List<T> unwrap(List<Node> nodes) {
@@ -178,7 +189,8 @@ public class References {
private Object object;
private final List<Node> initialReferences = new ArrayList<Node>();
private final Set<Node> references = new HashSet<Node>();
- //private int refernceCount;
+ private Node next;
+ private Node previous;
public Node(String name, Object object) {
this.name = name;
Modified: openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java
URL: http://svn.apache.org/viewvc/openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java?rev=997202&r1=997201&r2=997202&view=diff
==============================================================================
--- openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java (original)
+++ openejb/trunk/openejb3/container/openejb-core/src/test/java/org/apache/openejb/util/ReferencesTest.java Wed Sep 15 06:51:33 2010
@@ -17,6 +17,7 @@
package org.apache.openejb.util;
import static org.apache.openejb.util.References.sort;
+
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
@@ -34,6 +35,11 @@ public class ReferencesTest extends Test
private BeanVisitor visitor = new BeanVisitor();
private List<Bean> beans;
+ public void testEmptyList() {
+ beans = new ArrayList<Bean>();
+ assertEquals(0, sort(beans, visitor).size());
+ }
+
public void test() {
beans = new ArrayList<Bean>();
@@ -43,7 +49,6 @@ public class ReferencesTest extends Test
Bean c = bean("c", "b");
List<Bean> actual = sort(beans, visitor);
-
assertEquals(expected(a, b, c), actual);
}