Package: ThreadSafeDirectedAcyclicGraph

ThreadSafeDirectedAcyclicGraph

nameinstructionbranchcomplexitylinemethod
ThreadSafeDirectedAcyclicGraph()
M: 0 C: 13
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 3
100%
M: 0 C: 1
100%
assertTypeAndMembership(GraphNode)
M: 0 C: 33
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 4
100%
M: 0 C: 1
100%
createRootNode(Object)
M: 0 C: 21
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 4
100%
M: 0 C: 1
100%
deleteRootNode(GraphNode)
M: 0 C: 40
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 7
100%
M: 0 C: 1
100%
equals(Object)
M: 37 C: 89
71%
M: 3 C: 13
81%
M: 2 C: 7
78%
M: 5 C: 20
80%
M: 0 C: 1
100%
getRootNodes()
M: 0 C: 32
100%
M: 0 C: 4
100%
M: 0 C: 3
100%
M: 0 C: 6
100%
M: 0 C: 1
100%
hashCode()
M: 0 C: 19
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 4
100%
M: 0 C: 1
100%
static {...}
M: 0 C: 5
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
toString()
M: 0 C: 50
100%
M: 0 C: 4
100%
M: 0 C: 3
100%
M: 0 C: 11
100%
M: 0 C: 1
100%

Coverage

1: /*******************************************************************************
2: * Copyright (c) 2011 VMware Inc. and others
3: * All rights reserved. This program and the accompanying materials
4: * are made available under the terms of the Eclipse Public License v1.0
5: * which accompanies this distribution, and is available at
6: * http://www.eclipse.org/legal/epl-v10.html
7: *
8: * Contributors:
9: * VMware Inc. - initial contribution (ThreadSafeArrayListTree.java)
10: * EclipseSource - reworked from generic tree to DAG (Bug 358697)
11: *******************************************************************************/
12:
13: package org.eclipse.virgo.util.common;
14:
15: import java.util.ArrayList;
16: import java.util.List;
17:
18: /**
19: * {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
20: * 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
21: * n. The DAG may have multiple root nodes (nodes with no parents) and nodes may share children.
22: * <p />
23: * Once created a root node can become a non-root node by adding the node as a child to another node. This can be done
24: * by calling the method addChild on a node. All nodes of a DAG are reachable from its root nodes.
25: *
26: * <strong>Concurrent Semantics</strong><br />
27: *
28: * This class is thread safe.
29: *
30: * @param <V> type of values in the graph
31: */
32: public class ThreadSafeDirectedAcyclicGraph<V> implements DirectedAcyclicGraph<V> {
33:
34: private final Object monitor = new Object();
35:
36: private static final Object tieMonitor = new Object();
37:
38: private final List<ThreadSafeGraphNode<V>> nodes = new ArrayList<ThreadSafeGraphNode<V>>();
39:
40: /**
41: * {@inheritDoc}
42: */
43: @Override
44: public ThreadSafeGraphNode<V> createRootNode(V value) {
45: synchronized (this.monitor) {
46: ThreadSafeGraphNode<V> node = new ThreadSafeGraphNode<V>(value, this.monitor);
47: this.nodes.add(node);
48: return node;
49: }
50: }
51:
52: /**
53: * {@inheritDoc}
54: */
55: @Override
56: public boolean deleteRootNode(GraphNode<V> node) {
57: assertTypeAndMembership(node);
58: synchronized (this.monitor) {
59: Assert.isTrue(node.getChildren().isEmpty(), "Cannot delete node '%s'. Node has children. Please remove the children first.", node);
60: Assert.isTrue(node.getParents().isEmpty(),
61: "Cannot delete node '%s'. Node is still in use. Please remove it from the other node(s) first.", node);
62: boolean removed = this.nodes.remove(node);
63: return removed;
64: }
65: }
66:
67: private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
68: Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
69: ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
70: Assert.isTrue(concreteChild.belongsToSameGraph(this.monitor), "The node '%s' does not belong to the graph '%s'", concreteChild, this);
71: return concreteChild;
72: }
73:
74: /**
75: * {@inheritDoc}
76: */
77: @Override
78: public List<GraphNode<V>> getRootNodes() {
79: List<GraphNode<V>> rootNodes = new ArrayList<GraphNode<V>>();
80: synchronized (this.monitor) {
81:• for (GraphNode<V> node : this.nodes) {
82:• if (node.isRootNode()) {
83: rootNodes.add(node);
84: }
85: }
86: return rootNodes;
87: }
88: }
89:
90: /**
91: * {@inheritDoc}
92: */
93: @Override
94: public String toString() {
95: StringBuffer result = new StringBuffer();
96: result.append("<");
97: synchronized (this.monitor) {
98: boolean first = true;
99:• for (GraphNode<V> child : getRootNodes()) {
100:• if (!first) {
101: result.append(", ");
102: }
103: result.append(child.toString());
104: first = false;
105: }
106: }
107: result.append(">");
108: return result.toString();
109: }
110:
111: /**
112: * {@inheritDoc}
113: */
114: @Override
115: public int hashCode() {
116: synchronized (this.monitor) {
117: final int prime = 31;
118: int result = 1;
119: result = prime * result + this.nodes.hashCode();
120: return result;
121: }
122: }
123:
124: /**
125: * {@inheritDoc}
126: */
127: @SuppressWarnings("unchecked")
128: @Override
129: public boolean equals(Object obj) {
130:• if (this == obj) {
131: return true;
132: }
133:• if (obj == null) {
134: return false;
135: }
136:• if (getClass() != obj.getClass()) {
137: return false;
138: }
139: ThreadSafeDirectedAcyclicGraph<V> other = (ThreadSafeDirectedAcyclicGraph<V>) obj;
140: int thisHash = System.identityHashCode(this);
141: int otherHash = System.identityHashCode(other);
142:• if (thisHash < otherHash) {
143: synchronized (this.monitor) {
144: synchronized (other.monitor) {
145:• if (!this.nodes.equals(other.nodes)) {
146: return false;
147: }
148: }
149: }
150:• } else if (thisHash > otherHash) {
151: synchronized (other.monitor) {
152: synchronized (this.monitor) {
153:• if (!this.nodes.equals(other.nodes)) {
154: return false;
155: }
156: }
157: }
158: } else {
159: synchronized (tieMonitor) {
160: synchronized (this.monitor) {
161: synchronized (other.monitor) {
162:• if (!this.nodes.equals(other.nodes)) {
163: return false;
164: }
165: }
166: }
167: }
168: }
169: return true;
170: }
171:
172: }