View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *     http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
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      // improbable case: duplicate spanId in a trace tree: prevent
57      // infinite recursion
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  }