Package: ThreadSafeGraphNode

ThreadSafeGraphNode

nameinstructionbranchcomplexitylinemethod
ThreadSafeGraphNode(Object, Object)
M: 0 C: 19
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 6
100%
M: 0 C: 1
100%
addChild(GraphNode)
M: 0 C: 42
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 7
100%
M: 0 C: 1
100%
assertTypeAndMembership(GraphNode)
M: 0 C: 32
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 4
100%
M: 0 C: 1
100%
belongsToSameGraph(Object)
M: 0 C: 8
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
belongsToSameGraph(ThreadSafeGraphNode)
M: 0 C: 9
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
doCycleCheck(GraphNode)
M: 0 C: 27
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 5
100%
M: 0 C: 1
100%
equals(Object)
M: 37 C: 105
74%
M: 3 C: 19
86%
M: 2 C: 10
83%
M: 5 C: 25
83%
M: 0 C: 1
100%
getChild(int)
M: 5 C: 13
72%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 2 C: 2
50%
M: 0 C: 1
100%
getChildren()
M: 0 C: 15
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
getParents()
M: 0 C: 15
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
getValue()
M: 0 C: 3
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
hashCode()
M: 0 C: 32
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 5
100%
M: 0 C: 1
100%
isRootNode()
M: 0 C: 4
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
numChildren()
M: 0 C: 11
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
removeChild(GraphNode)
M: 0 C: 24
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 6
100%
M: 0 C: 1
100%
removeParent(GraphNode, GraphNode)
M: 0 C: 20
100%
M: 1 C: 1
50%
M: 1 C: 1
50%
M: 0 C: 5
100%
M: 0 C: 1
100%
size()
M: 0 C: 11
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 3
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: 58
100%
M: 0 C: 6
100%
M: 0 C: 4
100%
M: 0 C: 11
100%
M: 0 C: 1
100%
visit(GraphNode.DirectedAcyclicGraphVisitor)
M: 0 C: 7
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
visit(GraphNode.ExceptionThrowingDirectedAcyclicGraphVisitor)
M: 0 C: 7
100%
M: 0 C: 0
100%
M: 0 C: 1
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
visitInternal(GraphNode.DirectedAcyclicGraphVisitor, Map)
M: 0 C: 33
100%
M: 1 C: 7
88%
M: 1 C: 4
80%
M: 0 C: 9
100%
M: 0 C: 1
100%
visitInternal(GraphNode.ExceptionThrowingDirectedAcyclicGraphVisitor, Map)
M: 0 C: 33
100%
M: 1 C: 7
88%
M: 1 C: 4
80%
M: 0 C: 9
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.HashMap;
17: import java.util.List;
18: import java.util.Map;
19:
20: /**
21: * {@link GraphNode} is a node in a {@link DirectedAcyclicGraph}. Each node has a value.
22: * <p />
23: *
24: * <strong>Concurrent Semantics</strong><br />
25: *
26: * This class is thread safe.
27: *
28: * @param <V> type of values in the graph
29: */
30: class ThreadSafeGraphNode<V> implements GraphNode<V> {
31:
32: private final V value;
33:
34: private final Object monitor;
35:
36: private static final Object tieMonitor = new Object();
37:
38: private final List<ThreadSafeGraphNode<V>> children = new ArrayList<ThreadSafeGraphNode<V>>();
39:
40: private final List<ThreadSafeGraphNode<V>> parents = new ArrayList<ThreadSafeGraphNode<V>>();
41:
42: /**
43: * Construct a {@link ThreadSafeGraphNode} with the given value, which may be <code>null</code>.
44: *
45: * @param value the value of the node, which may be <code>null</code>
46: * @param monitor the shared monitor of the graph
47: */
48: ThreadSafeGraphNode(V value, Object monitor) {
49: this.value = value;
50: this.monitor = monitor;
51: }
52:
53: /**
54: * {@inheritDoc}
55: */
56: @Override
57: public V getValue() {
58: return this.value;
59: }
60:
61: /**
62: * Returns a list of this node's children (not copies of the children). If the node has no children, returns an
63: * empty list. Never returns <code>null</code> .
64: * <p/>
65: * The returned list is synchronized to preserve thread safety, but may still result in
66: * ConcurrentModificationException being thrown.
67: *
68: * @return this node's children
69: */
70: @Override
71: public List<GraphNode<V>> getChildren() {
72: synchronized (this.monitor) {
73: return new SynchronizedList<GraphNode<V>>(this.children, this.monitor);
74: }
75: }
76:
77: /**
78: * Adds the given node as child to this node. The child node is <strong>not</strong> copied.
79: *
80: * @param child the node to add
81: * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
82: * @throws IllegalArgumentException if the given node is already a child of this node.
83: * @throws IllegalArgumentException if the given node is not a {@link ThreadSafeGraphNode}.
84: */
85: @Override
86: public void addChild(GraphNode<V> child) {
87: ThreadSafeGraphNode<V> concreteChild = assertTypeAndMembership(child);
88: synchronized (this.monitor) {
89: Assert.isFalse(this.children.contains(child), "The node '%s' is already a child of '%s'", child, this);
90: doCycleCheck(concreteChild);
91: this.children.add(concreteChild);
92: concreteChild.parents.add(this);
93: }
94: }
95:
96: private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
97: Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
98: ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
99: Assert.isTrue(belongsToSameGraph(concreteChild), "The node '%s' does not belong to the same graph as '%s'", concreteChild, this);
100: return concreteChild;
101: }
102:
103: private boolean belongsToSameGraph(ThreadSafeGraphNode<V> other) {
104:• return this.monitor == other.monitor;
105: }
106:
107: protected boolean belongsToSameGraph(Object monitor) {
108:• return this.monitor == monitor;
109: }
110:
111: // check for cycles when adding a new child to a parent (is this node a descendant of the new child?).
112: private void doCycleCheck(GraphNode<V> child) {
113: synchronized (this.monitor) {
114: DescendentChecker<V> descendentChecker = new DescendentChecker<V>(this);
115: child.visit(descendentChecker);
116: Assert.isFalse(descendentChecker.isDescendent(), "Can't add '%s'. This node is a descendent of the new child.", child);
117: }
118: }
119:
120: /**
121: * Removes the occurrence of the given node from this node's children. Returns <code>true</code> if the child was
122: * found and removed, otherwise <code>false</code>.
123: *
124: * @param child the node to remove
125: * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
126: * @throws IllegalArgumentException if the given node is not a {@link ThreadSafeGraphNode}.
127: * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
128: * @see java.util.List#remove
129: */
130: @Override
131: public boolean removeChild(GraphNode<V> child) {
132: ThreadSafeGraphNode<V> concreteChild = assertTypeAndMembership(child);
133: synchronized (this.monitor) {
134: boolean removed = this.children.remove(concreteChild);
135:• if (removed) {
136: removeParent(child, this);
137: }
138: return removed;
139: }
140: }
141:
142: /*
143: * All the children in this.children share this.monitor.
144: */
145: private void removeParent(GraphNode<V> child, GraphNode<V> parent) {
146: synchronized (this.monitor) {
147:• if (child instanceof ThreadSafeGraphNode<?>) {
148: ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
149: concreteChild.parents.remove(parent);
150: }
151: }
152: }
153:
154: /**
155: * {@inheritDoc}
156: */
157: @Override
158: public void visit(DirectedAcyclicGraphVisitor<V> visitor) {
159: visitInternal(visitor, new HashMap<ThreadSafeGraphNode<V>, Boolean>());
160: }
161:
162: private void visitInternal(DirectedAcyclicGraphVisitor<V> visitor, Map<ThreadSafeGraphNode<V>, Boolean> visitedFlags) {
163:• if (visitedFlags.containsKey(this)) {
164: return;
165: }
166: visitedFlags.put(this, Boolean.TRUE);
167:• if (visitor.visit(this)) {
168:• for (int i = 0; i < numChildren(); i++) {
169: ThreadSafeGraphNode<V> nextChild = getChild(i);
170:• if (nextChild != null) {
171: nextChild.visitInternal(visitor, visitedFlags);
172: } else {
173: break;
174: }
175: }
176: }
177: }
178:
179: /**
180: * {@inheritDoc}
181: */
182: @Override
183: public <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor) throws E {
184: visitInternal(visitor, new HashMap<ThreadSafeGraphNode<V>, Boolean>());
185: }
186:
187: private <E extends Exception> void visitInternal(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor,
188: Map<ThreadSafeGraphNode<V>, Boolean> visitedFlags) throws E {
189:• if (visitedFlags.containsKey(this)) {
190: return;
191: }
192: visitedFlags.put(this, Boolean.TRUE);
193:• if (visitor.visit(this)) {
194:• for (int i = 0; i < numChildren(); i++) {
195: ThreadSafeGraphNode<V> nextChild = getChild(i);
196:• if (nextChild != null) {
197: nextChild.visitInternal(visitor, visitedFlags);
198: } else {
199: break;
200: }
201: }
202: }
203: }
204:
205: private ThreadSafeGraphNode<V> getChild(int i) {
206: synchronized (this.monitor) {
207: try {
208: return this.children.get(i);
209: } catch (IndexOutOfBoundsException e) {
210: return null;
211: }
212: }
213: }
214:
215: private int numChildren() {
216: synchronized (this.monitor) {
217: return this.children.size();
218: }
219: }
220:
221: private static class DescendentChecker<V> implements DirectedAcyclicGraphVisitor<V> {
222:
223: private final ThreadSafeGraphNode<V> prospect;
224:
225: private boolean descendent = false;
226:
227: public DescendentChecker(ThreadSafeGraphNode<V> prospect) {
228: this.prospect = prospect;
229: }
230:
231: @Override
232: public boolean visit(GraphNode<V> node) {
233: if (this.descendent) {
234: return false;
235: }
236: if (this.prospect == node) {
237: this.descendent = true;
238: return false;
239: }
240: return true;
241: }
242:
243: public boolean isDescendent() {
244: return this.descendent;
245: }
246:
247: }
248:
249: private static class SizeVisitor<V> implements DirectedAcyclicGraphVisitor<V> {
250:
251: private int size;
252:
253: @Override
254: public boolean visit(GraphNode<V> dag) {
255: this.size += 1;
256: return true;
257: }
258:
259: public int getSize() {
260: return this.size;
261: }
262: };
263:
264: /**
265: * {@inheritDoc}
266: */
267: @Override
268: public int size() {
269: SizeVisitor<V> sizeVisitor = new SizeVisitor<V>();
270: visit(sizeVisitor);
271: return sizeVisitor.getSize();
272: }
273:
274: /**
275: * {@inheritDoc}
276: */
277: @Override
278: public int hashCode() {
279: synchronized (this.monitor) {
280: final int prime = 31;
281: int result = 1;
282: result = prime * result + this.children.hashCode();
283:• result = prime * result + (this.value == null ? 0 : this.value.hashCode());
284: return result;
285: }
286: }
287:
288: /**
289: * {@inheritDoc}
290: */
291: // TODO TSGN.equals regards nodes as equal which have different sets of parents.
292: // TODO TSGN.equals regards distinct nodes with no children (no parents once the todo above is fixed) and the same
293: // value as equal. These nodes were created separately, possibly even from distinct DAGs as currently coded.
294: @SuppressWarnings("unchecked")
295: @Override
296: public boolean equals(Object obj) {
297:• if (this == obj) {
298: return true;
299: }
300:• if (obj == null) {
301: return false;
302: }
303:• if (getClass() != obj.getClass()) {
304: return false;
305: }
306: ThreadSafeGraphNode<V> other = (ThreadSafeGraphNode<V>) obj;
307: int thisHash = System.identityHashCode(this);
308: int otherHash = System.identityHashCode(other);
309:• if (thisHash < otherHash) {
310: synchronized (this.monitor) {
311: synchronized (other.monitor) {
312:• if (!this.children.equals(other.children)) {
313: return false;
314: }
315: }
316: }
317:• } else if (thisHash > otherHash) {
318: synchronized (other.monitor) {
319: synchronized (this.monitor) {
320:• if (!this.children.equals(other.children)) {
321: return false;
322: }
323: }
324: }
325: } else {
326: synchronized (tieMonitor) {
327: synchronized (this.monitor) {
328: synchronized (other.monitor) {
329:• if (!this.children.equals(other.children)) {
330: return false;
331: }
332: }
333: }
334: }
335: }
336:• if (this.value == null) {
337:• if (other.value != null) {
338: return false;
339: }
340:• } else if (!this.value.equals(other.value)) {
341: return false;
342: }
343: return true;
344: }
345:
346: /**
347: * {@inheritDoc}
348: */
349: @Override
350: public String toString() {
351: StringBuffer result = new StringBuffer();
352:• result.append(this.value != null ? this.value : "null").append("<");
353: synchronized (this.monitor) {
354: boolean first = true;
355:• for (ThreadSafeGraphNode<V> child : this.children) {
356:• if (!first) {
357: result.append(", ");
358: }
359: result.append(child.toString());
360: first = false;
361: }
362: }
363: result.append(">");
364: return result.toString();
365: }
366:
367: /**
368: * Returns a list of this graph's parents (not copies of the parents). If the graph has no parents, returns an empty
369: * list. Never returns <code>null</code> .
370: * <p/>
371: * The returned list is synchronized to preserve thread safety, but may still result in
372: * ConcurrentModificationException being thrown.
373: *
374: * @return this graph's parents
375: */
376: // TODO TSGN.getParents share its monitor with return values of getParents and getChildren. It feels as if the user
377: // might get some surprising deadlocks.
378: @Override
379: public List<GraphNode<V>> getParents() {
380: synchronized (this.monitor) {
381: return new SynchronizedList<GraphNode<V>>(this.parents, this.monitor);
382: }
383: }
384:
385: /**
386: * {@inheritDoc}
387: */
388: @Override
389: public boolean isRootNode() {
390: return this.parents.isEmpty();
391: }
392:
393: }