001/**
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.trace;
019
020import org.apache.htrace.core.Span;
021import org.apache.htrace.core.SpanId;
022
023import java.util.Collection;
024import java.util.Collections;
025import java.util.Comparator;
026import java.util.HashMap;
027import java.util.Iterator;
028import java.util.LinkedList;
029import java.util.List;
030import java.util.TreeSet;
031
032/**
033 * Used to create the graph formed by spans.
034 */
035public class TraceTree {
036
037  public static class SpansByParent {
038    private static Comparator<Span> COMPARATOR =
039        new Comparator<Span>() {
040          @Override
041          public int compare(Span a, Span b) {
042            return a.getSpanId().compareTo(b.getSpanId());
043          }
044        };
045
046    private final TreeSet<Span> treeSet;
047
048    private final HashMap<SpanId, LinkedList<Span>> parentToSpans;
049
050    SpansByParent(Collection<Span> spans) {
051      TreeSet<Span> treeSet = new TreeSet<Span>(COMPARATOR);
052      parentToSpans = new HashMap<SpanId, LinkedList<Span>>();
053      for (Span span : spans) {
054        treeSet.add(span);
055        for (SpanId parent : span.getParents()) {
056          LinkedList<Span> list = parentToSpans.get(parent);
057          if (list == null) {
058            list = new LinkedList<Span>();
059            parentToSpans.put(parent, list);
060          }
061          list.add(span);
062        }
063        if (span.getParents().length == 0) {
064          LinkedList<Span> list = parentToSpans.get(SpanId.INVALID);
065          if (list == null) {
066            list = new LinkedList<Span>();
067            parentToSpans.put(SpanId.INVALID, list);
068          }
069          list.add(span);
070        }
071      }
072      this.treeSet = treeSet;
073    }
074
075    public List<Span> find(SpanId parentId) {
076      LinkedList<Span> spans = parentToSpans.get(parentId);
077      if (spans == null) {
078        return new LinkedList<Span>();
079      }
080      return spans;
081    }
082
083    public Iterator<Span> iterator() {
084      return Collections.unmodifiableSortedSet(treeSet).iterator();
085    }
086  }
087
088  public static class SpansByProcessId {
089    private static Comparator<Span> COMPARATOR =
090        new Comparator<Span>() {
091          @Override
092          public int compare(Span a, Span b) {
093            return a.getSpanId().compareTo(b.getSpanId());
094          }
095        };
096
097    private final TreeSet<Span> treeSet;
098
099    SpansByProcessId(Collection<Span> spans) {
100      TreeSet<Span> treeSet = new TreeSet<Span>(COMPARATOR);
101      for (Span span : spans) {
102        treeSet.add(span);
103      }
104      this.treeSet = treeSet;
105    }
106
107    public Iterator<Span> iterator() {
108      return Collections.unmodifiableSortedSet(treeSet).iterator();
109    }
110  }
111
112  private final SpansByParent spansByParent;
113  private final SpansByProcessId spansByProcessId;
114
115  /**
116   * Create a new TraceTree
117   *
118   * @param spans The collection of spans to use to create this TraceTree. Should
119   *              have at least one root span.
120   */
121  public TraceTree(Collection<Span> spans) {
122    if (spans == null) {
123      spans = Collections.emptySet();
124    }
125    this.spansByParent = new SpansByParent(spans);
126    this.spansByProcessId = new SpansByProcessId(spans);
127  }
128
129  public SpansByParent getSpansByParent() {
130    return spansByParent;
131  }
132
133  public SpansByProcessId getSpansByProcessId() {
134    return spansByProcessId;
135  }
136
137  @Override
138  public String toString() {
139    StringBuilder bld = new StringBuilder();
140    String prefix = "";
141    for (Iterator<Span> iter = spansByParent.iterator(); iter.hasNext();) {
142      Span span = iter.next();
143      bld.append(prefix).append(span.toString());
144      prefix = "\n";
145    }
146    return bld.toString();
147  }
148}