org.eclipse.linuxtools.lttng.ui/src/org/eclipse/linuxtools/lttng/ui/views/histogram/HistogramDataModel.java

   1 /*******************************************************************************
   2  * Copyright (c) 2011 Ericsson
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *   Francois Chouinard - Initial API and implementation
  11  *******************************************************************************/
  12
  13 package org.eclipse.linuxtools.lttng.ui.views.histogram;
  14
  15 import java.util.Arrays;
  16
  17 import org.eclipse.linuxtools.lttng.exceptions.EventOutOfSequenceException;
  18 import org.eclipse.linuxtools.lttng.ui.LTTngUILogger;
  19 import org.eclipse.linuxtools.lttng.ui.views.histogram.HistogramScaledData;
  20
  21 /**
  22  * <b><u>HistogramDataModel</u></b>
  23  * <p>
  24  * Histogram-independent data model with the following characteristics:
  25  * <ul>
  26  * <li>The <i>basetime</i> is the timestamp of the first event
  27  * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration
  28  * (<i>d</i>)
  29  * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
  30  * <li>Bucket <i>i</i> holds the number of events that occurred in time range:
  31  * [<i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
  32  * <i>d</i>)
  33  * </ul>
  34  * Initially, the bucket durations is set to 1ns. As the events are read, they
  35  * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
  36  * to the <i>basetime</i>).
  37  * <p>
  38  * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
  39  * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
  40  * bucket duration). At this point, the histogram needs to be compacted. This is
  41  * done by simply merging adjacent buckets by pair, in effect doubling the
  42  * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> =
  43  * 2<i>d</i>). This compaction happens as needed as the trace is read.
  44  * <p>
  45  * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
  46  * method. By keeping the number of buckets <i>n</i> relatively large with
  47  * respect to to the number of pixels in the actual histogram, we should achieve
  48  * a nice result when visualizing the histogram.
  49  * <p>
  50  * TODO: Add filter support for more refined event counting (e.g. by trace,
  51  * event type, etc.)
  52  * <p>
  53  * TODO: Cut-off eccentric values?
  54  * TODO: Support for going back in time?
  55  */
  56 public class HistogramDataModel {
  57
  58     // ------------------------------------------------------------------------
  59     // Constants
  60     // ------------------------------------------------------------------------
  61
  62     // The default number of buckets
  63     public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;
  64
  65 //    // The ratio where an eccentric value will be truncated
  66 //    private static final int MAX_TO_AVERAGE_CUTOFF_RATIO = 5;
  67
  68     // ------------------------------------------------------------------------
  69     // Attributes
  70     // ------------------------------------------------------------------------
  71
  72     // Bucket management
  73     private final int fNbBuckets;
  74     private final long[] fBuckets;
  75     private long fBucketDuration;
  76     private long fNbEvents;
  77     private int fLastBucket;
  78
  79     // Timestamps
  80     private long fFirstEventTime;
  81     private long fLastEventTime;
  82     private long fCurrentEventTime;
  83     private long fTimeLimit;
  84
  85     // ------------------------------------------------------------------------
  86     // Constructors
  87     // ------------------------------------------------------------------------
  88
  89     public HistogramDataModel() {
  90         this(DEFAULT_NUMBER_OF_BUCKETS);
  91     }
  92
  93     public HistogramDataModel(int nbBuckets) {
  94         fNbBuckets = nbBuckets;
  95         fBuckets = new long[nbBuckets];
  96         clear();
  97     }
  98
  99     public HistogramDataModel(HistogramDataModel other) {
 100         fNbBuckets = other.fNbBuckets;
 101         fBuckets = Arrays.copyOf(other.fBuckets, fNbBuckets);
 102         fBucketDuration = other.fBucketDuration;
 103         fNbEvents = other.fNbEvents;
 104         fLastBucket = other.fLastBucket;
 105         fFirstEventTime = other.fFirstEventTime;
 106         fLastEventTime = other.fLastEventTime;
 107         fCurrentEventTime = other.fCurrentEventTime;
 108         fTimeLimit = other.fTimeLimit;
 109     }
 110
 111     // ------------------------------------------------------------------------
 112     // Accessors
 113     // ------------------------------------------------------------------------
 114
 115     public long getNbEvents() {
 116         return fNbEvents;
 117     }
 118
 119     public int getNbBuckets() {
 120         return fNbBuckets;
 121     }
 122
 123     public long getBucketDuration() {
 124         return fBucketDuration;
 125     }
 126
 127     public long getStartTime() {
 128         return fFirstEventTime;
 129     }
 130
 131     public long getEndTime() {
 132         return fLastEventTime;
 133     }
 134
 135     public long getCurrentEventTime() {
 136         return fCurrentEventTime;
 137     }
 138
 139     public long getTimeLimit() {
 140         return fTimeLimit;
 141     }
 142
 143     // ------------------------------------------------------------------------
 144     // Operations
 145     // ------------------------------------------------------------------------
 146
 147     /**
 148      * Clear the histogram model.
 149      */
 150     public void clear() {
 151         Arrays.fill(fBuckets, 0);
 152         fNbEvents = 0;
 153         fFirstEventTime = 0;
 154         fLastEventTime = 0;
 155         fCurrentEventTime = 0;
 156         fLastBucket = 0;
 157         fBucketDuration = 1; // 1ns
 158         updateEndTime();
 159     }
 160
 161     /**
 162      * Sets the current event time
 163      *
 164      * @param timestamp
 165      */
 166     public void setCurrentEvent(long timestamp) {
 167         fCurrentEventTime = timestamp;
 168     }
 169
 170     /**
 171      * Add event to the correct bucket, compacting the if needed.
 172      *
 173      * @param timestamp the timestamp of the event to count
 174      */
 175     public void countEvent(long timestamp) {
 176         // Set the start/end time if not already done
 177         if (fLastBucket == 0 && fBuckets[0] == 0 && timestamp > 0) {
 178             fFirstEventTime = timestamp;
 179             updateEndTime();
 180         }
 181         if (fLastEventTime < timestamp) {
 182             fLastEventTime = timestamp;
 183         }
 184
 185         // Compact as needed
 186         while (timestamp >= fTimeLimit) {
 187             mergeBuckets();
 188         }
 189
 190         // Validate
 191         if (timestamp < fFirstEventTime) {
 192             String message = "Out of order timestamp. Going back in time?"; //$NON-NLS-1$
 193             EventOutOfSequenceException exception = new EventOutOfSequenceException(message);
 194             LTTngUILogger.logError(message, exception);
 195             return;
 196         }
 197
 198         // Increment the right bucket
 199         int index = (int) ((timestamp - fFirstEventTime) / fBucketDuration);
 200         fBuckets[index]++;
 201         fNbEvents++;
 202         if (fLastBucket < index)
 203             fLastBucket = index;
 204     }
 205
 206     /**
 207      * Scale the model data to the width and height requested.
 208      *
 209      * @param width
 210      * @param height
 211      * @return the result array of size [width] and where the highest value
 212      *         doesn't exceed [height]
 213      */
 214     public HistogramScaledData scaleTo(int width, int height) {
 215         // Basic validation
 216         assert width > 0 && height > 0;
 217
 218         // The result structure
 219         HistogramScaledData result = new HistogramScaledData(width, height);
 220
 221         // Scale horizontally
 222         int bucketsPerBar = fLastBucket / width + 1;
 223         result.fBucketDuration = bucketsPerBar * fBucketDuration;
 224         for (int i = 0; i < width; i++) {
 225             int count = 0;
 226             for (int j = i * bucketsPerBar; j < (i + 1) * bucketsPerBar; j++) {
 227                 if (fNbBuckets <= j)
 228                     break;
 229                 count += fBuckets[j];
 230             }
 231             result.fData[i] = count;
 232             result.fLastBucket = i;
 233             if (result.fMaxValue < count)
 234                 result.fMaxValue = count;
 235         }
 236
 237         // Scale vertically
 238         if (result.fMaxValue > 0) {
 239             result.fScalingFactor = (double) height / result.fMaxValue;
 240         }
 241
 242         // Set the current event index in the scaled histogram
 243         if (fCurrentEventTime >= fFirstEventTime && fCurrentEventTime <= fLastEventTime)
 244             result.fCurrentBucket = (int) ((fCurrentEventTime - fFirstEventTime) / fBucketDuration) / bucketsPerBar;
 245         else
 246             result.fCurrentBucket = HistogramScaledData.OUT_OF_RANGE_BUCKET;
 247
 248         return result;
 249     }
 250
 251     // ------------------------------------------------------------------------
 252     // Helper functions
 253     // ------------------------------------------------------------------------
 254
 255     private void updateEndTime() {
 256         fTimeLimit = fFirstEventTime + fNbBuckets * fBucketDuration;
 257     }
 258
 259     private void mergeBuckets() {
 260         for (int i = 0; i < fNbBuckets / 2; i++) {
 261             fBuckets[i] = fBuckets[2 * i] + fBuckets[2 * i + 1];
 262         }
 263         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 264         fBucketDuration *= 2;
 265         updateEndTime();
 266         fLastBucket = fNbBuckets / 2 - 1;
 267     }
 268
 269 }