1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.accumulo.core.trace;
18
19 import java.util.ArrayList;
20 import java.util.HashMap;
21 import java.util.HashSet;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.Set;
25
26 import org.apache.accumulo.trace.instrument.Span;
27 import org.apache.accumulo.trace.thrift.RemoteSpan;
28
29
30 public class SpanTree {
31 final Map<Long,List<Long>> parentChildren = new HashMap<Long,List<Long>>();
32 public final Map<Long,RemoteSpan> nodes = new HashMap<Long,RemoteSpan>();
33
34 public SpanTree() {}
35
36 public void addNode(RemoteSpan span) {
37 nodes.put(span.spanId, span);
38 if (parentChildren.get(span.parentId) == null)
39 parentChildren.put(span.parentId, new ArrayList<Long>());
40 parentChildren.get(span.parentId).add(span.spanId);
41 }
42
43 public Set<Long> visit(SpanTreeVisitor visitor) {
44 Set<Long> visited = new HashSet<Long>();
45 List<Long> root = parentChildren.get(new Long(Span.ROOT_SPAN_ID));
46 if (root == null || root.isEmpty())
47 return visited;
48 RemoteSpan rootSpan = nodes.get(root.iterator().next());
49 if (rootSpan == null)
50 return visited;
51 recurse(0, null, rootSpan, visitor, visited);
52 return visited;
53 }
54
55 private void recurse(int level, RemoteSpan parent, RemoteSpan node, SpanTreeVisitor visitor, Set<Long> visited) {
56
57
58 if (visited.contains(node.spanId))
59 return;
60 visited.add(node.spanId);
61 List<RemoteSpan> children = new ArrayList<RemoteSpan>();
62 List<Long> childrenIds = parentChildren.get(node.spanId);
63 if (childrenIds != null) {
64 for (Long childId : childrenIds) {
65 RemoteSpan child = nodes.get(childId);
66 if (child != null) {
67 children.add(child);
68 }
69 }
70 }
71 children = TraceDump.sortByStart(children);
72 visitor.visit(level, parent, node, children);
73 for (RemoteSpan child : children) {
74 recurse(level + 1, node, child, visitor, visited);
75 }
76 }
77 }