Merge branch 'master' of ssh://git.eclipse.org/gitroot/virgo/org.eclipse.virgo.util into 369907-rework-dag-interface
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
index 7bec6d7..bb84056 100644
--- a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
@@ -8,12 +8,11 @@
* Contributors:
* VMware Inc. - initial contribution (Tree.java)
* EclipseSource - reworked from generic tree to DAG (Bug 358697)
+ * EclipseSource - removed internal root node list (Bug 369907)
*******************************************************************************/
package org.eclipse.virgo.util.common;
-import java.util.List;
-
/**
* {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
* to each other in a way that it is impossible to start at a node n and follow a child relationship that loops back to
@@ -31,35 +30,11 @@
public interface DirectedAcyclicGraph<V> {
/**
- * Create a new {@link GraphNode} and add it to this {@link DirectedAcyclicGraph}'s root nodes. The value is not
- * copied.
+ * Create a new {@link GraphNode} for this {@link DirectedAcyclicGraph}. The value is not copied.
*
* @param value of the node to create
* @return a node with the given value
*/
- GraphNode<V> createRootNode(V value);
-
- /**
- * Removes the occurrence of the given {@link GraphNode} from this {@link DirectedAcyclicGraph}'s root nodes.
- * Returns <code>true</code> if the node was found and removed, otherwise <code>false</code>.
- *
- * <strong>Note</strong>: Removal is only allowed if the root node has no children.
- *
- * @param node the node to remove
- * @throws IllegalArgumentException if the given node is not a root node (the node has one or more parents)
- * @throws IllegalArgumentException if the given node has children
- * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
- * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
- * @see java.util.List#remove
- */
- boolean deleteRootNode(GraphNode<V> node);
-
- /**
- * Returns a list of this {@link DirectedAcyclicGraph}'s root nodes (not copies of the nodes). If the graph has no
- * root nodes (and is therefore empty), returns an empty list. Never returns <code>null</code>.
- *
- * @return this graph's root nodes
- */
- List<GraphNode<V>> getRootNodes();
+ GraphNode<V> createNode(V value);
}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
index 03aa4da..e149fe7 100644
--- a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
@@ -8,12 +8,11 @@
* Contributors:
* VMware Inc. - initial contribution (ThreadSafeArrayListTree.java)
* EclipseSource - reworked from generic tree to DAG (Bug 358697)
+ * EclipseSource - removed internal root node list (Bug 369907)
*******************************************************************************/
package org.eclipse.virgo.util.common;
-import java.util.ArrayList;
-import java.util.List;
/**
* {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
@@ -33,140 +32,12 @@
private final Object monitor = new Object();
- private static final Object tieMonitor = new Object();
-
- private final List<ThreadSafeGraphNode<V>> nodes = new ArrayList<ThreadSafeGraphNode<V>>();
-
/**
* {@inheritDoc}
*/
@Override
- public ThreadSafeGraphNode<V> createRootNode(V value) {
- synchronized (this.monitor) {
- ThreadSafeGraphNode<V> node = new ThreadSafeGraphNode<V>(value, this.monitor);
- this.nodes.add(node);
- return node;
- }
- }
-
- /**
- * {@inheritDoc}
- */
- @Override
- public boolean deleteRootNode(GraphNode<V> node) {
- assertTypeAndMembership(node);
- synchronized (this.monitor) {
- Assert.isTrue(node.getChildren().isEmpty(), "Cannot delete node '%s'. Node has children. Please remove the children first.", node);
- Assert.isTrue(node.getParents().isEmpty(),
- "Cannot delete node '%s'. Node is still in use. Please remove it from the other node(s) first.", node);
- boolean removed = this.nodes.remove(node);
- return removed;
- }
- }
-
- private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
- Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
- ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
- Assert.isTrue(concreteChild.belongsToSameGraph(this.monitor), "The node '%s' does not belong to the graph '%s'", concreteChild, this);
- return concreteChild;
- }
-
- /**
- * {@inheritDoc}
- */
- @Override
- public List<GraphNode<V>> getRootNodes() {
- List<GraphNode<V>> rootNodes = new ArrayList<GraphNode<V>>();
- synchronized (this.monitor) {
- for (GraphNode<V> node : this.nodes) {
- if (node.isRootNode()) {
- rootNodes.add(node);
- }
- }
- return rootNodes;
- }
- }
-
- /**
- * {@inheritDoc}
- */
- @Override
- public String toString() {
- StringBuffer result = new StringBuffer();
- result.append("<");
- synchronized (this.monitor) {
- boolean first = true;
- for (GraphNode<V> child : getRootNodes()) {
- if (!first) {
- result.append(", ");
- }
- result.append(child.toString());
- first = false;
- }
- }
- result.append(">");
- return result.toString();
- }
-
- /**
- * {@inheritDoc}
- */
- @Override
- public int hashCode() {
- synchronized (this.monitor) {
- final int prime = 31;
- int result = 1;
- result = prime * result + this.nodes.hashCode();
- return result;
- }
- }
-
- /**
- * {@inheritDoc}
- */
- @SuppressWarnings("unchecked")
- @Override
- public boolean equals(Object obj) {
- if (this == obj) {
- return true;
- }
- if (obj == null) {
- return false;
- }
- if (getClass() != obj.getClass()) {
- return false;
- }
- ThreadSafeDirectedAcyclicGraph<V> other = (ThreadSafeDirectedAcyclicGraph<V>) obj;
- int thisHash = System.identityHashCode(this);
- int otherHash = System.identityHashCode(other);
- if (thisHash < otherHash) {
- synchronized (this.monitor) {
- synchronized (other.monitor) {
- if (!this.nodes.equals(other.nodes)) {
- return false;
- }
- }
- }
- } else if (thisHash > otherHash) {
- synchronized (other.monitor) {
- synchronized (this.monitor) {
- if (!this.nodes.equals(other.nodes)) {
- return false;
- }
- }
- }
- } else {
- synchronized (tieMonitor) {
- synchronized (this.monitor) {
- synchronized (other.monitor) {
- if (!this.nodes.equals(other.nodes)) {
- return false;
- }
- }
- }
- }
- }
- return true;
+ public ThreadSafeGraphNode<V> createNode(V value) {
+ return new ThreadSafeGraphNode<V>(value, this.monitor);
}
}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java
deleted file mode 100644
index f181dd2..0000000
--- a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java
+++ /dev/null
@@ -1,347 +0,0 @@
-/*******************************************************************************
- * Copyright (c) 2011 VMware Inc. and others
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License v1.0
- * which accompanies this distribution, and is available at
- * http://www.eclipse.org/legal/epl-v10.html
- *
- * Contributors:
- * VMware Inc. - initial contribution (ThreadSafeArrayListTreeTests.java)
- * EclipseSource - reworked from generic tree to DAG (Bug 358697)
- *******************************************************************************/
-
-package org.eclipse.virgo.util.common;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertNotNull;
-import static org.junit.Assert.assertTrue;
-import static org.junit.Assert.fail;
-
-import java.util.concurrent.CyclicBarrier;
-
-import org.junit.Before;
-import org.junit.Test;
-
-public class ThreadSafeAcyclicDirectedGraphTests {
-
- private DirectedAcyclicGraph<String> graph;
-
- private static DirectedAcyclicGraph<String> getDAG() {
- return getDAG("We");
- }
-
- private static DirectedAcyclicGraph<String> getDAG(String rootValue) {
- DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
-
- // shared nodes
- GraphNode<String> lo = graph.createRootNode("Lo");
- GraphNode<String> fi = graph.createRootNode("Fi");
-
- // We.add(Pa)
- GraphNode<String> we = graph.createRootNode("We");
- GraphNode<String> pa = graph.createRootNode("Pa");
- we.addChild(pa);
- // Pa.add(Cr)
- GraphNode<String> cr = graph.createRootNode("Cr");
- pa.addChild(cr);
- // Cr.add(B1,Lo,Fi)
- cr.addChild(graph.createRootNode("B1"));
- cr.addChild(lo);
- cr.addChild(fi);
-
- // Pa.add(Cu)
- GraphNode<String> cu = graph.createRootNode("Cu");
- pa.addChild(cu);
- cu.addChild(graph.createRootNode("B2"));
- cu.addChild(lo);
- cu.addChild(fi);
-
- // Pa.add(B3)
- pa.addChild(graph.createRootNode("B3"));
- // Pa.add(Lo)
- pa.addChild(lo);
-
- return graph;
- }
-
- @Before
- public void setUp() {
- this.graph = getDAG();
- }
-
- @Test
- public void testEmptyGraph() throws Exception {
- DirectedAcyclicGraph<String> emptyGraph = new ThreadSafeDirectedAcyclicGraph<String>();
-
- assertNotNull(emptyGraph);
- assertNotNull(emptyGraph.getRootNodes());
- assertEquals("<>", emptyGraph.toString());
- assertTrue(emptyGraph.getRootNodes().isEmpty());
- }
-
- @Test
- public void testGraphWithSingleRootNode() throws Exception {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
-
- GraphNode<String> rootNode = smallGraph.createRootNode("root");
-
- assertEquals("<root<>>", smallGraph.toString());
- assertEquals(1, smallGraph.getRootNodes().size());
-
- smallGraph.deleteRootNode(rootNode);
-
- assertEquals(0, smallGraph.getRootNodes().size());
- }
-
- @Test
- public void testGraphWithSingleNullRootNode() throws Exception {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
-
- GraphNode<String> rootNode = smallGraph.createRootNode(null);
-
- assertEquals("<null<>>", smallGraph.toString());
- assertEquals(1, smallGraph.getRootNodes().size());
-
- smallGraph.deleteRootNode(rootNode);
-
- assertEquals(0, smallGraph.getRootNodes().size());
- }
-
- @Test
- public void testGraphWithOnlyChildren() throws Exception {
- DirectedAcyclicGraph<String> onlyChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
-
- GraphNode<String> rootNode = onlyChildGraph.createRootNode("root");
- assertEquals("<root<>>", onlyChildGraph.toString());
- assertEquals(1, onlyChildGraph.getRootNodes().size());
-
- GraphNode<String> child = onlyChildGraph.createRootNode("child");
- rootNode.addChild(child);
- assertEquals("<root<child<>>>", onlyChildGraph.toString());
-
- GraphNode<String> grandchild = onlyChildGraph.createRootNode("grandchild");
- child.addChild(grandchild);
- assertEquals("<root<child<grandchild<>>>>", onlyChildGraph.toString());
- assertEquals(1, onlyChildGraph.getRootNodes().size());
-
- assertTrue(child.removeChild(grandchild));
- onlyChildGraph.deleteRootNode(grandchild);
- assertTrue(rootNode.removeChild(child));
- onlyChildGraph.deleteRootNode(child);
- onlyChildGraph.deleteRootNode(rootNode);
- assertEquals(0, onlyChildGraph.getRootNodes().size());
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testDirectCycle() throws Exception {
- DirectedAcyclicGraph<Integer> smallGraph = new ThreadSafeDirectedAcyclicGraph<Integer>();
- GraphNode<Integer> root = smallGraph.createRootNode(Integer.valueOf(42));
-
- root.addChild(root);
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testParentNodeIsNotADescendantOfTheNewChild() throws Exception {
- DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> rootNode = dag.createRootNode("root");
- GraphNode<String> child = dag.createRootNode("child");
-
- rootNode.addChild(child);
- child.addChild(rootNode);
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testParentIsNotADescendantOfTheNewChildDistanceTwo() throws Exception {
- DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> rootNode = dag.createRootNode("root");
-
- GraphNode<String> child = dag.createRootNode("child");
- rootNode.addChild(child);
- GraphNode<String> child2 = dag.createRootNode("child2");
- rootNode.addChild(child2);
- GraphNode<String> grandchild = dag.createRootNode("grandchild");
- child.addChild(grandchild);
-
- grandchild.addChild(rootNode);
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testDeleteRootNodeFromOtherGraph() {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> r1 = smallGraph.createRootNode("R1");
-
- this.graph.deleteRootNode(r1);
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testDeleteRootNodeOfWrongType() {
- this.graph.deleteRootNode(new ThreadSafeGraphNodeTests.NoopGraphNode());
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testDeleteRootNodeWithChildren() {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> r1 = smallGraph.createRootNode("R1");
- GraphNode<String> c1 = smallGraph.createRootNode("C1");
- r1.addChild(c1);
-
- this.graph.deleteRootNode(r1);
- }
-
- @Test(expected = IllegalArgumentException.class)
- public void testDeleteNonRootNode() {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> r1 = smallGraph.createRootNode("R1");
- GraphNode<String> c1 = smallGraph.createRootNode("C1");
- r1.addChild(c1);
-
- this.graph.deleteRootNode(c1);
- }
-
- @Test
- public void testAddSharedChildWithMultipleThreads() throws Exception {
-
- final DirectedAcyclicGraph<String> sharedChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- final int THREAD_COUNT = 150;
- final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
- final GraphNode<String> sharedChild = sharedChildGraph.createRootNode("shared child");
- assertEquals(0, sharedChild.getParents().size());
- assertEquals(1, sharedChildGraph.getRootNodes().size());
-
- class AddChildThread extends Thread {
-
- private final int counter;
-
- public AddChildThread(int counter) {
- this.counter = counter;
- }
-
- @Override
- public void run() {
- try {
- barrier.await(); // 1
- GraphNode<String> root = sharedChildGraph.createRootNode("root" + this.counter);
- root.addChild(sharedChild);
- barrier.await(); // 2
- barrier.await();
- assertTrue(root.removeChild(sharedChild));
- barrier.await(); // 3
- barrier.await();
- sharedChildGraph.deleteRootNode(root);
- barrier.await();
- } catch (Exception e) {
- fail();
- }
- }
- }
-
- for (int i = 0; i < THREAD_COUNT; i++) {
- new AddChildThread(i).start();
- }
- barrier.await(); // 1 - wait for all threads to be ready
- barrier.await(); // 2 - wait for all threads to create and add the nodes
- assertEquals(THREAD_COUNT, sharedChild.getParents().size());
- assertEquals(THREAD_COUNT, sharedChildGraph.getRootNodes().size());
- barrier.await(); //
- barrier.await(); // 3 - wait for all threads to be finish
- assertEquals(0, sharedChild.getParents().size());
- assertEquals(THREAD_COUNT + 1, sharedChildGraph.getRootNodes().size());
- barrier.await(); // wait for all threads to be finish
- assertEquals(0, sharedChild.getParents().size());
- }
-
- @Test
- public void testGraphWithSharedNodes() throws Exception {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
-
- GraphNode<String> r1 = smallGraph.createRootNode("R1");
- GraphNode<String> c1 = smallGraph.createRootNode("C1");
- GraphNode<String> c2 = smallGraph.createRootNode("C2");
- smallGraph.createRootNode("C3");
- assertEquals(4, smallGraph.getRootNodes().size());
- assertEquals("<R1<>, C1<>, C2<>, C3<>>", smallGraph.toString());
-
- r1.addChild(c1);
- assertEquals(3, smallGraph.getRootNodes().size());
- r1.addChild(c2);
- assertEquals(2, smallGraph.getRootNodes().size());
- assertEquals("<R1<C1<>, C2<>>, C3<>>", smallGraph.toString());
-
- GraphNode<String> r2 = smallGraph.createRootNode("R2");
- assertEquals(3, smallGraph.getRootNodes().size());
- assertEquals("<R1<C1<>, C2<>>, C3<>, R2<>>", smallGraph.toString());
-
- r2.addChild(c1);
- assertEquals(3, smallGraph.getRootNodes().size());
- assertEquals("<R1<C1<>, C2<>>, C3<>, R2<C1<>>>", smallGraph.toString());
- }
-
- @Test
- public void testDisassembleGraphWithSharedNodes() throws Exception {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> r1 = smallGraph.createRootNode("R1");
- GraphNode<String> c1 = smallGraph.createRootNode("C1");
- GraphNode<String> c2 = smallGraph.createRootNode("C2");
- GraphNode<String> c3 = smallGraph.createRootNode("C3");
- r1.addChild(c1);
- r1.addChild(c2);
- GraphNode<String> r2 = smallGraph.createRootNode("R2");
- r2.addChild(c1);
- assertEquals("<R1<C1<>, C2<>>, C3<>, R2<C1<>>>", smallGraph.toString());
- assertEquals(3, smallGraph.getRootNodes().size());
-
- // remove shared node
- assertTrue(r2.removeChild(c1));
- assertEquals("<R1<C1<>, C2<>>, C3<>, R2<>>", smallGraph.toString());
- assertEquals(3, smallGraph.getRootNodes().size());
- assertTrue(r1.removeChild(c2));
- assertEquals(4, smallGraph.getRootNodes().size());
- assertTrue(r1.removeChild(c1));
- assertEquals(5, smallGraph.getRootNodes().size());
- assertEquals("<R1<>, C1<>, C2<>, C3<>, R2<>>", smallGraph.toString());
- assertTrue(smallGraph.deleteRootNode(r2));
- assertEquals(4, smallGraph.getRootNodes().size());
- assertEquals("<R1<>, C1<>, C2<>, C3<>>", smallGraph.toString());
- assertTrue(smallGraph.deleteRootNode(r1));
- assertEquals(3, smallGraph.getRootNodes().size());
- assertEquals("<C1<>, C2<>, C3<>>", smallGraph.toString());
- smallGraph.deleteRootNode(smallGraph.getRootNodes().get(0));
- assertEquals(2, smallGraph.getRootNodes().size());
- assertEquals("<C2<>, C3<>>", smallGraph.toString());
- assertTrue(smallGraph.deleteRootNode(c2));
- assertEquals(1, smallGraph.getRootNodes().size());
- assertTrue(smallGraph.deleteRootNode(c3));
- assertTrue(smallGraph.getRootNodes().isEmpty());
- }
-
- @Test
- public void testRemovalOfAnAlreadyRemovedRootNode() throws Exception {
- DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> r1 = smallGraph.createRootNode("R1");
-
- assertTrue(smallGraph.deleteRootNode(r1));
-
- assertFalse(smallGraph.deleteRootNode(r1));
- }
-
- @Test
- public void testHashCodeEquals() {
- assertFalse(this.graph.equals(null));
-
- assertFalse(this.graph.equals(new Object()));
-
- DirectedAcyclicGraph<String> graph2 = getDAG();
- assertEquals(this.graph.hashCode(), graph2.hashCode());
- assertEquals(this.graph, this.graph);
- assertEquals(graph2, this.graph);
- assertEquals(this.graph, graph2);
-
- DirectedAcyclicGraph<String> g1 = new ThreadSafeDirectedAcyclicGraph<String>();
- assertFalse(this.graph.equals(g1));
- assertFalse(g1.equals(this.graph));
-
- assertTrue(new ThreadSafeDirectedAcyclicGraph<String>().equals(new ThreadSafeDirectedAcyclicGraph<String>()));
- }
-
-}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraphTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraphTests.java
new file mode 100644
index 0000000..77ef324
--- /dev/null
+++ b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraphTests.java
@@ -0,0 +1,243 @@
+/*******************************************************************************
+ * Copyright (c) 2011 VMware Inc. and others
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VMware Inc. - initial contribution (ThreadSafeArrayListTreeTests.java)
+ * EclipseSource - reworked from generic tree to DAG (Bug 358697)
+ * EclipseSource - removed internal root node list from TSDAG (Bug 369907)
+ *******************************************************************************/
+
+package org.eclipse.virgo.util.common;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.concurrent.CyclicBarrier;
+
+import org.junit.Before;
+import org.junit.Test;
+
+public class ThreadSafeDirectedAcyclicGraphTests {
+
+ private DirectedAcyclicGraph<String> graph;
+
+ private static DirectedAcyclicGraph<String> getDAG() {
+ return getDAG("We");
+ }
+
+ private static DirectedAcyclicGraph<String> getDAG(String rootValue) {
+ DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ // shared nodes
+ GraphNode<String> lo = graph.createNode("Lo");
+ GraphNode<String> fi = graph.createNode("Fi");
+
+ // We.add(Pa)
+ GraphNode<String> we = graph.createNode("We");
+ GraphNode<String> pa = graph.createNode("Pa");
+ we.addChild(pa);
+ // Pa.add(Cr)
+ GraphNode<String> cr = graph.createNode("Cr");
+ pa.addChild(cr);
+ // Cr.add(B1,Lo,Fi)
+ cr.addChild(graph.createNode("B1"));
+ cr.addChild(lo);
+ cr.addChild(fi);
+
+ // Pa.add(Cu)
+ GraphNode<String> cu = graph.createNode("Cu");
+ pa.addChild(cu);
+ cu.addChild(graph.createNode("B2"));
+ cu.addChild(lo);
+ cu.addChild(fi);
+
+ // Pa.add(B3)
+ pa.addChild(graph.createNode("B3"));
+ // Pa.add(Lo)
+ pa.addChild(lo);
+
+ return graph;
+ }
+
+ @Before
+ public void setUp() {
+ this.graph = getDAG();
+ }
+
+ @Test
+ public void testEmptyGraph() throws Exception {
+ DirectedAcyclicGraph<String> emptyGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ assertNotNull(emptyGraph);
+ }
+
+ @Test
+ public void testGraphWithSingleRootNode() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> rootNode = smallGraph.createNode("root");
+
+ assertNotNull(rootNode);
+ }
+
+ @Test
+ public void testGraphWithSingleNullRootNode() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> rootNode = smallGraph.createNode(null);
+
+ assertNotNull(rootNode);
+ }
+
+ @Test
+ public void testGraphWithOnlyChildren() throws Exception {
+ DirectedAcyclicGraph<String> onlyChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> rootNode = onlyChildGraph.createNode("root");
+
+ GraphNode<String> child = onlyChildGraph.createNode("child");
+ rootNode.addChild(child);
+
+ GraphNode<String> grandchild = onlyChildGraph.createNode("grandchild");
+ child.addChild(grandchild);
+
+ assertTrue(child.removeChild(grandchild));
+ assertTrue(rootNode.removeChild(child));
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testDirectCycle() throws Exception {
+ DirectedAcyclicGraph<Integer> smallGraph = new ThreadSafeDirectedAcyclicGraph<Integer>();
+ GraphNode<Integer> root = smallGraph.createNode(Integer.valueOf(42));
+
+ root.addChild(root);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testParentNodeIsNotADescendantOfTheNewChild() throws Exception {
+ DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> rootNode = dag.createNode("root");
+ GraphNode<String> child = dag.createNode("child");
+
+ rootNode.addChild(child);
+ child.addChild(rootNode);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testParentIsNotADescendantOfTheNewChildDistanceTwo() throws Exception {
+ DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> rootNode = dag.createNode("root");
+
+ GraphNode<String> child = dag.createNode("child");
+ rootNode.addChild(child);
+ GraphNode<String> child2 = dag.createNode("child2");
+ rootNode.addChild(child2);
+ GraphNode<String> grandchild = dag.createNode("grandchild");
+ child.addChild(grandchild);
+
+ grandchild.addChild(rootNode);
+ }
+
+ @Test
+ public void testAddSharedChildWithMultipleThreads() throws Exception {
+
+ final DirectedAcyclicGraph<String> sharedChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ final int THREAD_COUNT = 150;
+ final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
+ final GraphNode<String> sharedChild = sharedChildGraph.createNode("shared child");
+ assertEquals(0, sharedChild.getParents().size());
+
+ class AddChildThread extends Thread {
+
+ private final int counter;
+
+ public AddChildThread(int counter) {
+ this.counter = counter;
+ }
+
+ @Override
+ public void run() {
+ try {
+ barrier.await(); // 1
+ GraphNode<String> root = sharedChildGraph.createNode("root" + this.counter);
+ root.addChild(sharedChild);
+ barrier.await(); // 2
+ barrier.await();
+ assertTrue(root.removeChild(sharedChild));
+ barrier.await(); // 3
+ barrier.await();
+ } catch (Exception e) {
+ fail();
+ }
+ }
+ }
+
+ for (int i = 0; i < THREAD_COUNT; i++) {
+ new AddChildThread(i).start();
+ }
+ barrier.await(); // 1 - wait for all threads to be ready
+ barrier.await(); // 2 - wait for all threads to create and add the nodes
+ assertEquals(THREAD_COUNT, sharedChild.getParents().size());
+ barrier.await(); //
+ barrier.await(); // 3 - wait for all threads to be finish
+ assertEquals(0, sharedChild.getParents().size());
+ barrier.await(); // wait for all threads to be finish
+ assertEquals(0, sharedChild.getParents().size());
+ }
+
+ @Test
+ public void testGraphWithSharedNodes() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+ GraphNode<String> r1 = smallGraph.createNode("R1");
+ GraphNode<String> c1 = smallGraph.createNode("C1");
+ GraphNode<String> c2 = smallGraph.createNode("C2");
+ smallGraph.createNode("C3");
+
+ r1.addChild(c1);
+ r1.addChild(c2);
+ assertEquals("R1<C1<>, C2<>>", r1.toString());
+
+ GraphNode<String> r2 = smallGraph.createNode("R2");
+
+ r2.addChild(c1);
+ assertEquals("R2<C1<>>", r2.toString());
+ }
+
+ @Test
+ public void testDisassembleGraphWithSharedNodes() throws Exception {
+ DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+ GraphNode<String> r1 = smallGraph.createNode("R1");
+ GraphNode<String> c1 = smallGraph.createNode("C1");
+ GraphNode<String> c2 = smallGraph.createNode("C2");
+ r1.addChild(c1);
+ r1.addChild(c2);
+ GraphNode<String> r2 = smallGraph.createNode("R2");
+ r2.addChild(c1);
+ assertEquals("R1<C1<>, C2<>>", r1.toString());
+ assertEquals("R2<C1<>>", r2.toString());
+
+ // remove shared node
+ assertTrue(r2.removeChild(c1));
+ assertEquals("R1<C1<>, C2<>>", r1.toString());
+ assertTrue(r1.removeChild(c2));
+ assertTrue(r1.removeChild(c1));
+ }
+
+ @Test
+ public void testHashCodeEquals() {
+ assertFalse(this.graph.equals(null));
+
+ assertFalse(this.graph.equals(new Object()));
+
+ assertFalse(new ThreadSafeDirectedAcyclicGraph<String>().equals(new ThreadSafeDirectedAcyclicGraph<String>()));
+ }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
index 6632cac..ca34167 100644
--- a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
+++ b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
@@ -8,6 +8,7 @@
* Contributors:
* VMware Inc. - initial contribution (ThreadSafeArrayListTreeTests.java)
* EclipseSource - reworked from generic tree to DAG (Bug 358697)
+ * EclipseSource - removed internal root node list from TSDAG (Bug 369907)
*******************************************************************************/
package org.eclipse.virgo.util.common;
@@ -52,31 +53,31 @@
}
private GraphNode<String> buildTestGraphAndReturnRootNode(DirectedAcyclicGraph<String> graph, String rootValue) {
- GraphNode<String> top = graph.createRootNode(rootValue);
+ GraphNode<String> top = graph.createNode(rootValue);
// shared nodes
- GraphNode<String> lo = graph.createRootNode("Lo");
- GraphNode<String> fi = graph.createRootNode("Fi");
+ GraphNode<String> lo = graph.createNode("Lo");
+ GraphNode<String> fi = graph.createNode("Fi");
// We.add(Pa)
- top.addChild(graph.createRootNode("Pa"));
+ top.addChild(graph.createNode("Pa"));
GraphNode<String> pa = top.getChildren().get(0);
// Pa.add(Cr)
- pa.addChild(graph.createRootNode("Cr"));
+ pa.addChild(graph.createNode("Cr"));
GraphNode<String> cr = pa.getChildren().get(0);
- cr.addChild(graph.createRootNode("B1"));
+ cr.addChild(graph.createNode("B1"));
cr.addChild(lo);
cr.addChild(fi);
// Pa.add(Cu)
- pa.addChild(graph.createRootNode("Cu"));
+ pa.addChild(graph.createNode("Cu"));
GraphNode<String> cu = pa.getChildren().get(1);
- cu.addChild(graph.createRootNode("B2"));
+ cu.addChild(graph.createNode("B2"));
cu.addChild(lo);
cu.addChild(fi);
// Pa.add(B3)
- pa.addChild(graph.createRootNode("B3"));
+ pa.addChild(graph.createNode("B3"));
// Pa.add(Lo)
pa.addChild(lo);
@@ -84,9 +85,9 @@
}
private GraphNode<String> addFluffyToGraph(DirectedAcyclicGraph<String> graph) {
- GraphNode<String> body = graph.createRootNode("Fluffy's body");
+ GraphNode<String> body = graph.createNode("Fluffy's body");
for (int i = 0; i < 3; i++) {
- GraphNode<String> head = graph.createRootNode("head " + i);
+ GraphNode<String> head = graph.createNode("head " + i);
head.addChild(body);
}
return body;
@@ -96,7 +97,7 @@
public void testEmptyNode() throws Exception {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> nullGraph = graph.createRootNode(null);
+ GraphNode<String> nullGraph = graph.createNode(null);
assertNull(nullGraph.getValue());
assertEquals("null<>", nullGraph.toString());
@@ -105,10 +106,10 @@
@Test
public void testDepthTwo() throws Exception {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> root = graph.createRootNode("root");
+ GraphNode<String> root = graph.createNode("root");
- root.addChild(graph.createRootNode("C1"));
- root.addChild(graph.createRootNode("C2"));
+ root.addChild(graph.createNode("C1"));
+ root.addChild(graph.createNode("C2"));
assertEquals("root<C1<>, C2<>>", root.toString());
}
@@ -116,9 +117,9 @@
@Test
public void testDepthThree() throws Exception {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> we = graph.createRootNode("We");
- GraphNode<String> pa = graph.createRootNode("Pa");
- GraphNode<String> cr = graph.createRootNode("Cr");
+ GraphNode<String> we = graph.createNode("We");
+ GraphNode<String> pa = graph.createNode("Pa");
+ GraphNode<String> cr = graph.createNode("Cr");
we.addChild(pa);
pa.addChild(cr);
@@ -130,7 +131,7 @@
public void testToString() {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- assertEquals("null<>", graph.createRootNode(null).toString());
+ assertEquals("null<>", graph.createNode(null).toString());
GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
@@ -140,13 +141,13 @@
@Test
public void testHashCodeEquals() {
DirectedAcyclicGraph<String> graphA = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> topA = graphA.createRootNode("root");
+ GraphNode<String> topA = graphA.createNode("root");
assertFalse(topA.equals(null));
assertFalse(topA.equals(new Object()));
DirectedAcyclicGraph<String> graphB = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> topB = graphB.createRootNode("root");
+ GraphNode<String> topB = graphB.createNode("root");
assertEquals(topA.hashCode(), topB.hashCode());
assertEquals(topB.hashCode(), topA.hashCode());
@@ -154,7 +155,7 @@
assertEquals(topA, topB);
assertEquals(topB, topA);
- GraphNode<String> t1 = graphA.createRootNode("a");
+ GraphNode<String> t1 = graphA.createNode("a");
{
GraphNode<String> a = t1;
assertFalse(topA.equals(a));
@@ -162,17 +163,17 @@
}
{
- GraphNode<String> a = graphA.createRootNode(null);
+ GraphNode<String> a = graphA.createNode(null);
a.hashCode();
assertFalse(topA.equals(a));
assertFalse(a.equals(topA));
}
- assertTrue(graphA.createRootNode(null).equals(graphA.createRootNode(null)));
- assertFalse(graphA.createRootNode(null).equals(graphA.createRootNode("a")));
- assertFalse(graphA.createRootNode("a").equals(graphA.createRootNode(null)));
+ assertTrue(graphA.createNode(null).equals(graphA.createNode(null)));
+ assertFalse(graphA.createNode(null).equals(graphA.createNode("a")));
+ assertFalse(graphA.createNode("a").equals(graphA.createNode(null)));
- GraphNode<String> t2 = graphA.createRootNode("b");
+ GraphNode<String> t2 = graphA.createNode("b");
assertFalse(t1.equals(t2));
assertFalse(t2.equals(t1));
}
@@ -196,16 +197,16 @@
public void testSizeWithNullNodes() throws Exception {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> graphWithNullNodes = graph.createRootNode("with null values");
+ GraphNode<String> graphWithNullNodes = graph.createNode("with null values");
assertEquals(1, graphWithNullNodes.size());
- graphWithNullNodes.addChild(graph.createRootNode("first"));
+ graphWithNullNodes.addChild(graph.createNode("first"));
assertEquals(2, graphWithNullNodes.size());
- graphWithNullNodes.addChild(graph.createRootNode(null));
+ graphWithNullNodes.addChild(graph.createNode(null));
assertEquals(3, graphWithNullNodes.size());
- graphWithNullNodes.addChild(graph.createRootNode("third"));
+ graphWithNullNodes.addChild(graph.createNode("third"));
assertEquals(4, graphWithNullNodes.size());
}
@@ -229,7 +230,7 @@
List<GraphNode<String>> children = top.getChildren();
assertEquals(1, children.size());
- GraphNode<String> newChild = graph.createRootNode("newChild");
+ GraphNode<String> newChild = graph.createNode("newChild");
top.addChild(newChild);
assertEquals(2, children.size());
@@ -240,7 +241,7 @@
public void testDAGWithNoChilds() throws Exception {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> solo = graph.createRootNode("solo");
+ GraphNode<String> solo = graph.createNode("solo");
assertNotNull(solo.getChildren());
assertTrue(solo.getChildren().isEmpty());
@@ -251,19 +252,18 @@
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
GraphNode<String> child = new NoopGraphNode();
- graph.createRootNode("foo").addChild(child);
+ graph.createNode("foo").addChild(child);
}
@Test(expected = IllegalArgumentException.class)
public void testDuplicateInsertionOfAChild() throws Exception {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- buildTestGraphAndReturnRootNode(graph);
- GraphNode<String> node = graph.getRootNodes().get(0);
- GraphNode<String> child = graph.createRootNode("child");
+ GraphNode<String> rootNode = buildTestGraphAndReturnRootNode(graph);
+ GraphNode<String> child = graph.createNode("child");
- node.addChild(child);
- node.addChild(child);
+ rootNode.addChild(child);
+ rootNode.addChild(child);
}
@Test(expected = IllegalArgumentException.class)
@@ -272,7 +272,7 @@
GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
DirectedAcyclicGraph<String> secondGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> alienNode = secondGraph.createRootNode("alien");
+ GraphNode<String> alienNode = secondGraph.createNode("alien");
top.addChild(alienNode);
}
@@ -280,9 +280,9 @@
@Test
public void testAddSharedChild() {
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> cr = graph.createRootNode("cr");
- GraphNode<String> cu = graph.createRootNode("cu");
- GraphNode<String> lo = graph.createRootNode("lo");
+ GraphNode<String> cr = graph.createNode("cr");
+ GraphNode<String> cu = graph.createNode("cu");
+ GraphNode<String> lo = graph.createNode("lo");
cr.addChild(lo);
cu.addChild(lo);
@@ -302,7 +302,7 @@
final int THREAD_COUNT = 150;
final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
final DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
- final GraphNode<String> sharedChild = graph.createRootNode("shared child");
+ final GraphNode<String> sharedChild = graph.createNode("shared child");
class AddChildThread extends Thread {
@@ -316,7 +316,7 @@
public void run() {
try {
barrier.await();
- GraphNode<String> root = graph.createRootNode("root" + this.counter);
+ GraphNode<String> root = graph.createNode("root" + this.counter);
root.addChild(sharedChild);
barrier.await();
} catch (Exception e) {
@@ -383,7 +383,7 @@
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
GraphNode<String> child = new NoopGraphNode();
- graph.createRootNode("foo").removeChild(child);
+ graph.createNode("foo").removeChild(child);
}
@Test(expected = IllegalArgumentException.class)
@@ -392,7 +392,7 @@
GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
DirectedAcyclicGraph<String> secondGraph = new ThreadSafeDirectedAcyclicGraph<String>();
- GraphNode<String> alienNode = secondGraph.createRootNode("alien");
+ GraphNode<String> alienNode = secondGraph.createNode("alien");
top.removeChild(alienNode);
}
@@ -430,7 +430,7 @@
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
- GraphNode<String> t = graph.createRootNode("-");
+ GraphNode<String> t = graph.createNode("-");
t.visit(visitor);
List<String> visited = visitor.getVisited();
@@ -444,10 +444,10 @@
GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
- top.addChild(graph.createRootNode("-"));
+ top.addChild(graph.createNode("-"));
GraphNode<String> t = top.getChildren().get(1);
- t.addChild(graph.createRootNode("foo"));
- t.addChild(graph.createRootNode("bar"));
+ t.addChild(graph.createNode("foo"));
+ t.addChild(graph.createNode("bar"));
assertEquals(12, top.size());
top.visit(visitor);
@@ -471,7 +471,7 @@
DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
- GraphNode<String> t = graph.createRootNode("-");
+ GraphNode<String> t = graph.createNode("-");
t.visit(visitor);
List<String> visited = visitor.getVisited();
@@ -485,10 +485,10 @@
GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
- top.addChild(graph.createRootNode("-"));
+ top.addChild(graph.createNode("-"));
GraphNode<String> t = top.getChildren().get(1);
- t.addChild(graph.createRootNode("foo"));
- t.addChild(graph.createRootNode("bar"));
+ t.addChild(graph.createNode("foo"));
+ t.addChild(graph.createNode("bar"));
assertEquals(12, top.size());
top.visit(visitor);
@@ -502,10 +502,10 @@
GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
- top.addChild(graph.createRootNode("*"));
+ top.addChild(graph.createNode("*"));
GraphNode<String> t = top.getChildren().get(1);
- t.addChild(graph.createRootNode("foo"));
- t.addChild(graph.createRootNode("bar"));
+ t.addChild(graph.createNode("foo"));
+ t.addChild(graph.createNode("bar"));
assertEquals(12, top.size());
try {
