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  *   Bernd Hufmann - Implementation of new interfaces /listeners and support for
  12  *                   time stamp in any order
  13  *******************************************************************************/
  14
  15 package org.eclipse.linuxtools.lttng.ui.views.histogram;
  16
  17 import java.util.Arrays;
  18
  19 import org.eclipse.core.runtime.ListenerList;
  20 import org.eclipse.linuxtools.lttng.core.exceptions.EventOutOfSequenceException;
  21 import org.eclipse.linuxtools.lttng.ui.LTTngUILogger;
  22
  23 /**
  24  * <b><u>HistogramDataModel</u></b>
  25  * <p>
  26  * Histogram-independent data model with the following characteristics:
  27  * <ul>
  28  * <li>The <i>basetime</i> is the timestamp of the first event
  29  * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration
  30  * (<i>d</i>)
  31  * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
  32  * <li>Bucket <i>i</i> holds the number of events that occurred in time range:
  33  * [<i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
  34  * <i>d</i>)
  35  * </ul>
  36  * Initially, the bucket durations is set to 1ns. As the events are read, they
  37  * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
  38  * to the <i>basetime</i>).
  39  * <p>
  40  * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
  41  * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
  42  * bucket duration). At this point, the histogram needs to be compacted. This is
  43  * done by simply merging adjacent buckets by pair, in effect doubling the
  44  * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> =
  45  * 2<i>d</i>). This compaction happens as needed as the trace is read.
  46  * <p>
  47  * The model allows for timestamps in not increasing order. The timestamps can
  48  * be fed to the model in any order. If an event has a timestamp less than the
  49  * <i>basetime</i>, the buckets will be moved to the right to account for the
  50  * new smaller timestamp. The new <i>basetime</i> is a multiple of the bucket
  51  * duration smaller then the previous <i>basetime</i>. Note that the <i>basetime</i>
  52  * might not be anymore a timestamp of an event. If necessary, the buckets will
  53  * be compacted before moving to the right. This might be necessary to not
  54  * loose any event counts at the end of the buckets array.
  55  * <p>
  56  * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
  57  * method. By keeping the number of buckets <i>n</i> relatively large with
  58  * respect to to the number of pixels in the actual histogram, we should achieve
  59  * a nice result when visualizing the histogram.
  60  * <p>
  61  * TODO: Add filter support for more refined event counting (e.g. by trace,
  62  * event type, etc.)
  63  * <p>
  64  * TODO: Cut-off eccentric values? TODO: Support for going back in time?
  65  */
  66 public class HistogramDataModel implements IHistogramDataModel {
  67
  68     // ------------------------------------------------------------------------
  69     // Constants
  70     // ------------------------------------------------------------------------
  71
  72     // The default number of buckets
  73     public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;
  74
  75     public static final int REFRESH_FREQUENCY = DEFAULT_NUMBER_OF_BUCKETS;
  76
  77 //    // The ratio where an eccentric value will be truncated
  78 //    private static final int MAX_TO_AVERAGE_CUTOFF_RATIO = 5;
  79
  80     // ------------------------------------------------------------------------
  81     // Attributes
  82     // ------------------------------------------------------------------------
  83
  84     // Bucket management
  85     private final int fNbBuckets;
  86     private final long[] fBuckets;
  87     private long fBucketDuration;
  88     private long fNbEvents;
  89     private int fLastBucket;
  90
  91     // Timestamps
  92     private long fFirstBucketTime; // could be negative when analyzing events with descending order!!!
  93     private long fFirstEventTime;
  94     private long fLastEventTime;
  95     private long fCurrentEventTime;
  96     private long fTimeLimit;
  97
  98     // private listener lists
  99     private final ListenerList fModelListeners;
 100
 101     public HistogramDataModel() {
 102         this(DEFAULT_NUMBER_OF_BUCKETS);
 103     }
 104
 105     public HistogramDataModel(int nbBuckets) {
 106         fNbBuckets = nbBuckets;
 107         fBuckets = new long[nbBuckets];
 108         fModelListeners = new ListenerList();
 109         clear();
 110     }
 111
 112     public HistogramDataModel(HistogramDataModel other) {
 113         fNbBuckets = other.fNbBuckets;
 114         fBuckets = Arrays.copyOf(other.fBuckets, fNbBuckets);
 115         fBucketDuration = other.fBucketDuration;
 116         fNbEvents = other.fNbEvents;
 117         fLastBucket = other.fLastBucket;
 118         fFirstBucketTime = other.fFirstBucketTime;
 119         fFirstEventTime = other.fFirstEventTime;
 120         fLastEventTime = other.fLastEventTime;
 121         fCurrentEventTime = other.fCurrentEventTime;
 122         fTimeLimit = other.fTimeLimit;
 123         fModelListeners = new ListenerList();
 124         Object[] listeners = other.fModelListeners.getListeners();
 125         for (Object listener : listeners) {
 126             fModelListeners.add(listener);
 127         }
 128     }
 129
 130     // ------------------------------------------------------------------------
 131     // Accessors
 132     // ------------------------------------------------------------------------
 133
 134     public long getNbEvents() {
 135         return fNbEvents;
 136     }
 137
 138     public int getNbBuckets() {
 139         return fNbBuckets;
 140     }
 141
 142     public long getBucketDuration() {
 143         return fBucketDuration;
 144     }
 145
 146     public long getFirstBucketTime() {
 147         return fFirstBucketTime;
 148     }
 149
 150     public long getStartTime() {
 151         return fFirstEventTime;
 152     }
 153
 154     public long getEndTime() {
 155         return fLastEventTime;
 156     }
 157
 158     public long getCurrentEventTime() {
 159         return fCurrentEventTime;
 160     }
 161
 162     public long getTimeLimit() {
 163         return fTimeLimit;
 164     }
 165
 166     // ------------------------------------------------------------------------
 167     // Listener handling
 168     // ------------------------------------------------------------------------
 169
 170     public void addHistogramListener(IHistogramModelListener listener) {
 171         fModelListeners.add(listener);
 172     }
 173
 174     public void removeHistogramListener(IHistogramModelListener listener) {
 175         fModelListeners.remove(listener);
 176     }
 177
 178     private void fireModelUpdateNotification() {
 179         fireModelUpdateNotification(0);
 180     }
 181
 182     private void fireModelUpdateNotification(long count) {
 183         if (count % REFRESH_FREQUENCY == 0) {
 184             Object[] listeners = fModelListeners.getListeners();
 185             for (int i = 0; i < listeners.length; i++) {
 186                 IHistogramModelListener listener = (IHistogramModelListener) listeners[i];
 187                 listener.modelUpdated();
 188             }
 189         }
 190     }
 191
 192     // ------------------------------------------------------------------------
 193     // Operations
 194     // ------------------------------------------------------------------------
 195     @Override
 196     public void complete() {
 197         fireModelUpdateNotification();
 198     }
 199
 200     /**
 201      * Clear the histogram model.
 202      */
 203     @Override
 204     public void clear() {
 205         Arrays.fill(fBuckets, 0);
 206         fNbEvents = 0;
 207         fFirstBucketTime = 0;
 208         fLastEventTime = 0;
 209         fCurrentEventTime = 0;
 210         fLastBucket = 0;
 211         fBucketDuration = 1; // 1ns
 212         updateEndTime();
 213         fireModelUpdateNotification();
 214     }
 215
 216     /**
 217      * Sets the current event time
 218      *
 219      * @param timestamp
 220      */
 221     public void setCurrentEvent(long timestamp) {
 222         fCurrentEventTime = timestamp;
 223     }
 224
 225     /**
 226      * Sets the current event time
 227      *
 228      * @param timestamp
 229      */
 230     public void setCurrentEventNotifyListeners(long timestamp) {
 231         fCurrentEventTime = timestamp;
 232         fireModelUpdateNotification();
 233     }
 234
 235     /**
 236      * Add event to the correct bucket, compacting the if needed.
 237      *
 238      * @param timestamp the timestamp of the event to count
 239      */
 240     @Override
 241     public void countEvent(long eventCount, long timestamp) {
 242
 243         // Validate
 244         if (timestamp < 0) {
 245             String message = "Negative time value"; //$NON-NLS-1$
 246             EventOutOfSequenceException exception = new EventOutOfSequenceException(message);
 247             LTTngUILogger.logError(message, exception);
 248             return;
 249         }
 250
 251         // Set the start/end time if not already done
 252         if (fLastBucket == 0 && fBuckets[0] == 0 && timestamp > 0) {
 253             fFirstBucketTime = timestamp;
 254             fFirstEventTime = timestamp;
 255             updateEndTime();
 256         }
 257
 258         if (timestamp < fFirstEventTime) {
 259             fFirstEventTime = timestamp;
 260         }
 261
 262         if (fLastEventTime < timestamp) {
 263             fLastEventTime = timestamp;
 264         }
 265
 266         if (timestamp >= fFirstBucketTime) {
 267
 268             // Compact as needed
 269             while (timestamp >= fTimeLimit) {
 270                 mergeBuckets();
 271             }
 272
 273         } else {
 274
 275             // get offset for adjustment
 276             int offset = getOffset(timestamp);
 277
 278             // Compact as needed
 279             while(fLastBucket + offset >= fNbBuckets) {
 280                 mergeBuckets();
 281                 offset = getOffset(timestamp);
 282             }
 283
 284             moveBuckets(offset);
 285
 286             fLastBucket = fLastBucket + offset;
 287
 288             fFirstBucketTime = fFirstBucketTime - offset*fBucketDuration;
 289             updateEndTime();
 290         }
 291
 292         // Increment the right bucket
 293         int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
 294         fBuckets[index]++;
 295         fNbEvents++;
 296         if (fLastBucket < index)
 297             fLastBucket = index;
 298
 299         fireModelUpdateNotification(eventCount);
 300     }
 301
 302     /**
 303      * Scale the model data to the width, height and bar width requested.
 304      *
 305      * @param width
 306      * @param height
 307      * @param bar width
 308      * @return the result array of size [width] and where the highest value
 309      *         doesn't exceed [height]
 310      */
 311     @Override
 312     public HistogramScaledData scaleTo(int width, int height, int barWidth) {
 313         // Basic validation
 314         if (width <= 0 ||  height <= 0 || barWidth <= 0)
 315             throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 316
 317         // The result structure
 318         HistogramScaledData result = new HistogramScaledData(width, height, barWidth);
 319
 320         // Scale horizontally
 321         result.fMaxValue = 0;
 322
 323         int nbBars = width / barWidth;
 324         int bucketsPerBar = fLastBucket / nbBars + 1;
 325         result.fBucketDuration = bucketsPerBar * fBucketDuration;
 326         for (int i = 0; i < nbBars; i++) {
 327             int count = 0;
 328             for (int j = i * bucketsPerBar; j < (i + 1) * bucketsPerBar; j++) {
 329                 if (fNbBuckets <= j)
 330                     break;
 331                 count += fBuckets[j];
 332             }
 333             result.fData[i] = count;
 334             result.fLastBucket = i;
 335             if (result.fMaxValue < count)
 336                 result.fMaxValue = count;
 337         }
 338
 339         // Scale vertically
 340         if (result.fMaxValue > 0) {
 341             result.fScalingFactor = (double) height / result.fMaxValue;
 342         }
 343
 344         // Set the current event index in the scaled histogram
 345         if (fCurrentEventTime >= fFirstBucketTime && fCurrentEventTime <= fLastEventTime)
 346             result.fCurrentBucket = (int) ((fCurrentEventTime - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 347         else
 348             result.fCurrentBucket = HistogramScaledData.OUT_OF_RANGE_BUCKET;
 349
 350         result.fFirstBucketTime = fFirstBucketTime;
 351         result.fFirstEventTime = fFirstEventTime;
 352         return result;
 353     }
 354
 355     // ------------------------------------------------------------------------
 356     // Helper functions
 357     // ------------------------------------------------------------------------
 358
 359     private void updateEndTime() {
 360         fTimeLimit = fFirstBucketTime + fNbBuckets * fBucketDuration;
 361     }
 362
 363     private void mergeBuckets() {
 364         for (int i = 0; i < fNbBuckets / 2; i++) {
 365             fBuckets[i] = fBuckets[2 * i] + fBuckets[2 * i + 1];
 366         }
 367         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 368         fBucketDuration *= 2;
 369         updateEndTime();
 370         fLastBucket = fNbBuckets / 2 - 1;
 371     }
 372
 373     private void moveBuckets(int offset) {
 374         for(int i = fNbBuckets - 1; i >= offset; i--) {
 375             fBuckets[i] = fBuckets[i-offset];
 376         }
 377
 378         for (int i = 0; i < offset; i++) {
 379             fBuckets[i] = 0;
 380         }
 381     }
 382
 383     private int getOffset(long timestamp) {
 384         int offset = (int) ((fFirstBucketTime - timestamp) / fBucketDuration);
 385         if ((fFirstBucketTime - timestamp) % fBucketDuration != 0) {
 386             offset++;
 387         }
 388         return offset;
 389     }
 390
 391 }