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

   1 /*******************************************************************************
   2  * Copyright (c) 2011, 2012 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  *   Francois Chouinard - Moved from LTTng to TMF
  14  *******************************************************************************/
  15
  16 package org.eclipse.linuxtools.tmf.ui.views.histogram;
  17
  18 import java.util.Arrays;
  19
  20 import org.eclipse.core.runtime.ListenerList;
  21
  22 /**
  23  * Histogram-independent data model.
  24  *
  25  * It has the following characteristics:
  26  * <ul>
  27  * <li>The <i>basetime</i> is the timestamp of the first event
  28  * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration
  29  * (<i>d</i>)
  30  * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
  31  * <li>Bucket <i>i</i> holds the number of events that occurred in time range:
  32  * [<i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
  33  * <i>d</i>)
  34  * </ul>
  35  * Initially, the bucket durations is set to 1ns. As the events are read, they
  36  * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
  37  * to the <i>basetime</i>).
  38  * <p>
  39  * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
  40  * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
  41  * bucket duration). At this point, the histogram needs to be compacted. This is
  42  * done by simply merging adjacent buckets by pair, in effect doubling the
  43  * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> =
  44  * 2<i>d</i>). This compaction happens as needed as the trace is read.
  45  * <p>
  46  * The model allows for timestamps in not increasing order. The timestamps can
  47  * be fed to the model in any order. If an event has a timestamp less than the
  48  * <i>basetime</i>, the buckets will be moved to the right to account for the
  49  * new smaller timestamp. The new <i>basetime</i> is a multiple of the bucket
  50  * duration smaller then the previous <i>basetime</i>. Note that the <i>basetime</i>
  51  * might not be anymore a timestamp of an event. If necessary, the buckets will
  52  * be compacted before moving to the right. This might be necessary to not
  53  * loose any event counts at the end of the buckets array.
  54  * <p>
  55  * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
  56  * method. By keeping the number of buckets <i>n</i> relatively large with
  57  * respect to to the number of pixels in the actual histogram, we should achieve
  58  * a nice result when visualizing the histogram.
  59  * <p>
  60  *
  61  * @version 1.0
  62  * @author Francois Chouinard
  63  */
  64 public class HistogramDataModel implements IHistogramDataModel {
  65
  66     // ------------------------------------------------------------------------
  67     // Constants
  68     // ------------------------------------------------------------------------
  69
  70     /**
  71      *  The default number of buckets
  72      */
  73     public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;
  74
  75     /**
  76      * Number of events after which listeners will be notified.
  77      */
  78     public static final int REFRESH_FREQUENCY = DEFAULT_NUMBER_OF_BUCKETS;
  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     // ------------------------------------------------------------------------
 102     // Constructors
 103     // ------------------------------------------------------------------------
 104
 105     /**
 106      * Default constructor with default number of buckets.
 107      */
 108     public HistogramDataModel() {
 109         this(DEFAULT_NUMBER_OF_BUCKETS);
 110     }
 111
 112     /**
 113      * Constructor with non-default number of buckets.
 114      * @param nbBuckets A number of buckets.
 115      */
 116     public HistogramDataModel(int nbBuckets) {
 117         fNbBuckets = nbBuckets;
 118         fBuckets = new long[nbBuckets];
 119         fModelListeners = new ListenerList();
 120         clear();
 121     }
 122
 123     /**
 124      * Copy constructor.
 125      * @param other A model to copy.
 126      */
 127     public HistogramDataModel(HistogramDataModel other) {
 128         fNbBuckets = other.fNbBuckets;
 129         fBuckets = Arrays.copyOf(other.fBuckets, fNbBuckets);
 130         fBucketDuration = Math.max(other.fBucketDuration,1);
 131         fNbEvents = other.fNbEvents;
 132         fLastBucket = other.fLastBucket;
 133         fFirstBucketTime = other.fFirstBucketTime;
 134         fFirstEventTime = other.fFirstEventTime;
 135         fLastEventTime = other.fLastEventTime;
 136         fCurrentEventTime = other.fCurrentEventTime;
 137         fTimeLimit = other.fTimeLimit;
 138         fModelListeners = new ListenerList();
 139         Object[] listeners = other.fModelListeners.getListeners();
 140         for (Object listener : listeners) {
 141             fModelListeners.add(listener);
 142         }
 143     }
 144
 145     // ------------------------------------------------------------------------
 146     // Accessors
 147     // ------------------------------------------------------------------------
 148
 149     /**
 150      * Returns the number of events in the data model.
 151      * @return number of events.
 152      */
 153     public long getNbEvents() {
 154         return fNbEvents;
 155     }
 156
 157     /**
 158      * Returns the number of buckets in the model.
 159      * @return number of buckets.
 160      */
 161     public int getNbBuckets() {
 162         return fNbBuckets;
 163     }
 164
 165    /**
 166     * Returns the current bucket duration.
 167     * @return bucket duration
 168     */
 169     public long getBucketDuration() {
 170         return fBucketDuration;
 171     }
 172
 173     /**
 174      * Returns the time value of the first bucket in the model.
 175      * @return time of first bucket.
 176      */
 177     public long getFirstBucketTime() {
 178         return fFirstBucketTime;
 179     }
 180
 181     /**
 182      * Returns the time of the first event in the model.
 183      * @return time of first event.
 184      */
 185     public long getStartTime() {
 186         return fFirstEventTime;
 187     }
 188
 189     /**
 190      * Returns the time of the last event in the model.
 191      * @return the time of last event.
 192      */
 193     public long getEndTime() {
 194         return fLastEventTime;
 195     }
 196
 197     /**
 198      * Returns the time of the current event in the model.
 199      * @return the time of the current event.
 200      */
 201     public long getCurrentEventTime() {
 202         return fCurrentEventTime;
 203     }
 204
 205     /**
 206      * Returns the time limit with is: start time + nbBuckets * bucketDuration
 207      * @return the time limit.
 208      */
 209     public long getTimeLimit() {
 210         return fTimeLimit;
 211     }
 212
 213     // ------------------------------------------------------------------------
 214     // Listener handling
 215     // ------------------------------------------------------------------------
 216
 217     /**
 218      * Add a listener to the model to be informed about model changes.
 219      * @param listener A listener to add.
 220      */
 221     public void addHistogramListener(IHistogramModelListener listener) {
 222         fModelListeners.add(listener);
 223     }
 224
 225     /**
 226      * Remove a given model listener.
 227      * @param listener A listener to remove.
 228      */
 229     public void removeHistogramListener(IHistogramModelListener listener) {
 230         fModelListeners.remove(listener);
 231     }
 232
 233     // Notify listeners (always)
 234     private void fireModelUpdateNotification() {
 235         fireModelUpdateNotification(0);
 236     }
 237
 238     // Notify listener on boundary
 239     private void fireModelUpdateNotification(long count) {
 240         if ((count % REFRESH_FREQUENCY) == 0) {
 241             Object[] listeners = fModelListeners.getListeners();
 242             for (Object listener2 : listeners) {
 243                 IHistogramModelListener listener = (IHistogramModelListener) listener2;
 244                 listener.modelUpdated();
 245             }
 246         }
 247     }
 248
 249     // ------------------------------------------------------------------------
 250     // Operations
 251     // ------------------------------------------------------------------------
 252
 253     /*
 254      * (non-Javadoc)
 255      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#complete()
 256      */
 257     @Override
 258     public void complete() {
 259         fireModelUpdateNotification();
 260     }
 261
 262     /**
 263      * Clear the histogram model.
 264      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
 265      */
 266     @Override
 267     public void clear() {
 268         Arrays.fill(fBuckets, 0);
 269         fNbEvents = 0;
 270         fFirstBucketTime = 0;
 271         fLastEventTime = 0;
 272         fCurrentEventTime = 0;
 273         fLastBucket = 0;
 274         fBucketDuration = 1; // 1ns
 275         updateEndTime();
 276         fireModelUpdateNotification();
 277     }
 278
 279     /**
 280      * Sets the current event time (no notification of listeners)
 281      *
 282      * @param timestamp A time stamp to set.
 283      */
 284     public void setCurrentEvent(long timestamp) {
 285         fCurrentEventTime = timestamp;
 286     }
 287
 288     /**
 289      * Sets the current event time with notification of listeners
 290      *
 291      * @param timestamp A time stamp to set.
 292      */
 293     public void setCurrentEventNotifyListeners(long timestamp) {
 294         fCurrentEventTime = timestamp;
 295         fireModelUpdateNotification();
 296     }
 297
 298     /**
 299      * Add event to the correct bucket, compacting the if needed.
 300      *
 301      * @param eventCount The current event Count (for notification purposes)
 302      * @param timestamp The timestamp of the event to count
 303      *
 304      */
 305     @Override
 306     public void countEvent(long eventCount, long timestamp) {
 307
 308         // Validate
 309         if (timestamp < 0) {
 310             return;
 311         }
 312
 313         // Set the start/end time if not already done
 314         if ((fLastBucket == 0) && (fBuckets[0] == 0) && (timestamp > 0)) {
 315             fFirstBucketTime = timestamp;
 316             fFirstEventTime = timestamp;
 317             updateEndTime();
 318         }
 319
 320         if (timestamp < fFirstEventTime) {
 321             fFirstEventTime = timestamp;
 322         }
 323
 324         if (fLastEventTime < timestamp) {
 325             fLastEventTime = timestamp;
 326         }
 327
 328         if (timestamp >= fFirstBucketTime) {
 329
 330             // Compact as needed
 331             while (timestamp >= fTimeLimit) {
 332                 mergeBuckets();
 333             }
 334
 335         } else {
 336
 337             // get offset for adjustment
 338             int offset = getOffset(timestamp);
 339
 340             // Compact as needed
 341             while((fLastBucket + offset) >= fNbBuckets) {
 342                 mergeBuckets();
 343                 offset = getOffset(timestamp);
 344             }
 345
 346             moveBuckets(offset);
 347
 348             fLastBucket = fLastBucket + offset;
 349
 350             fFirstBucketTime = fFirstBucketTime - (offset*fBucketDuration);
 351             updateEndTime();
 352         }
 353
 354         // Increment the right bucket
 355         int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
 356         fBuckets[index]++;
 357         fNbEvents++;
 358         if (fLastBucket < index) {
 359             fLastBucket = index;
 360         }
 361
 362         fireModelUpdateNotification(eventCount);
 363     }
 364
 365     /**
 366      * Scale the model data to the width, height and bar width requested.
 367      *
 368      * @param width A width of the histogram canvas
 369      * @param height A height of the histogram canvas
 370      * @param barWidth A width (in pixel) of a histogram bar
 371      * @return the result array of size [width] and where the highest value doesn't exceed [height]
 372      *
 373      * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int, int, int)
 374      */
 375     @Override
 376     public HistogramScaledData scaleTo(int width, int height, int barWidth) {
 377         // Basic validation
 378         if ((width <= 0) ||  (height <= 0) || (barWidth <= 0))
 379          {
 380             throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 381         }
 382
 383         // The result structure
 384         HistogramScaledData result = new HistogramScaledData(width, height, barWidth);
 385
 386         // Scale horizontally
 387         result.fMaxValue = 0;
 388
 389         int nbBars = width / barWidth;
 390         int bucketsPerBar = (fLastBucket / nbBars) + 1;
 391         result.fBucketDuration = Math.max(bucketsPerBar * fBucketDuration,1);
 392         for (int i = 0; i < nbBars; i++) {
 393             int count = 0;
 394             for (int j = i * bucketsPerBar; j < ((i + 1) * bucketsPerBar); j++) {
 395                 if (fNbBuckets <= j) {
 396                     break;
 397                 }
 398                 count += fBuckets[j];
 399             }
 400             result.fData[i] = count;
 401             result.fLastBucket = i;
 402             if (result.fMaxValue < count) {
 403                 result.fMaxValue = count;
 404             }
 405         }
 406
 407         // Scale vertically
 408         if (result.fMaxValue > 0) {
 409             result.fScalingFactor = (double) height / result.fMaxValue;
 410         }
 411
 412         fBucketDuration = Math.max(fBucketDuration, 1);
 413         // Set the current event index in the scaled histogram
 414         if ((fCurrentEventTime >= fFirstBucketTime) && (fCurrentEventTime <= fLastEventTime)) {
 415             result.fCurrentBucket = (int) ((fCurrentEventTime - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 416         } else {
 417             result.fCurrentBucket = HistogramScaledData.OUT_OF_RANGE_BUCKET;
 418         }
 419
 420         result.fFirstBucketTime = fFirstBucketTime;
 421         result.fFirstEventTime = fFirstEventTime;
 422         return result;
 423     }
 424
 425     // ------------------------------------------------------------------------
 426     // Helper functions
 427     // ------------------------------------------------------------------------
 428
 429     private void updateEndTime() {
 430         fTimeLimit = fFirstBucketTime + (fNbBuckets * fBucketDuration);
 431     }
 432
 433     private void mergeBuckets() {
 434         for (int i = 0; i < (fNbBuckets / 2); i++) {
 435             fBuckets[i] = fBuckets[2 * i] + fBuckets[(2 * i) + 1];
 436         }
 437         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 438         fBucketDuration *= 2;
 439         updateEndTime();
 440         fLastBucket = (fNbBuckets / 2) - 1;
 441     }
 442
 443     private void moveBuckets(int offset) {
 444         for(int i = fNbBuckets - 1; i >= offset; i--) {
 445             fBuckets[i] = fBuckets[i-offset];
 446         }
 447
 448         for (int i = 0; i < offset; i++) {
 449             fBuckets[i] = 0;
 450         }
 451     }
 452
 453     private int getOffset(long timestamp) {
 454         int offset = (int) ((fFirstBucketTime - timestamp) / fBucketDuration);
 455         if (((fFirstBucketTime - timestamp) % fBucketDuration) != 0) {
 456             offset++;
 457         }
 458         return offset;
 459     }
 460
 461 }