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  *   Francois Chouinard - Added support for empty initial buckets
  15  *******************************************************************************/
  16
  17 package org.eclipse.linuxtools.tmf.ui.views.histogram;
  18
  19 import java.util.Arrays;
  20
  21 import org.eclipse.core.runtime.ListenerList;
  22
  23 /**
  24  * Histogram-independent data model.
  25  *
  26  * It has 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  *
  62  * @version 2.0
  63  * @author Francois Chouinard
  64  */
  65 public class HistogramDataModel implements IHistogramDataModel {
  66
  67     // ------------------------------------------------------------------------
  68     // Constants
  69     // ------------------------------------------------------------------------
  70
  71     /**
  72      *  The default number of buckets
  73      */
  74     public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;
  75
  76     /**
  77      * Number of events after which listeners will be notified.
  78      */
  79     public static final int REFRESH_FREQUENCY = DEFAULT_NUMBER_OF_BUCKETS;
  80
  81     // ------------------------------------------------------------------------
  82     // Attributes
  83     // ------------------------------------------------------------------------
  84
  85     // Bucket management
  86     private final int fNbBuckets;
  87     private final long[] fBuckets;
  88     private long fBucketDuration;
  89     private long fNbEvents;
  90     private int fLastBucket;
  91
  92     // Timestamps
  93     private long fFirstBucketTime; // could be negative when analyzing events with descending order!!!
  94     private long fFirstEventTime;
  95     private long fLastEventTime;
  96     private long fCurrentEventTime;
  97     private long fTimeLimit;
  98
  99     // Private listener lists
 100     private final ListenerList fModelListeners;
 101
 102     // ------------------------------------------------------------------------
 103     // Constructors
 104     // ------------------------------------------------------------------------
 105
 106     /**
 107      * Default constructor with default number of buckets.
 108      */
 109     public HistogramDataModel() {
 110         this(0, DEFAULT_NUMBER_OF_BUCKETS);
 111     }
 112
 113     /**
 114      * Default constructor with default number of buckets.
 115      * @param startTime The histogram start time
 116      * @since 2.0
 117      */
 118     public HistogramDataModel(long startTime) {
 119         this(startTime, DEFAULT_NUMBER_OF_BUCKETS);
 120     }
 121
 122     /**
 123      * Constructor with non-default number of buckets.
 124      * @param nbBuckets A number of buckets.
 125      */
 126     public HistogramDataModel(int nbBuckets) {
 127         this(0, nbBuckets);
 128     }
 129
 130     /**
 131      * Constructor with non-default number of buckets.
 132      * @param startTime the histogram start time
 133      * @param nbBuckets A number of buckets.
 134      * @since 2.0
 135      */
 136     public HistogramDataModel(long startTime, int nbBuckets) {
 137         fFirstBucketTime = fFirstEventTime = fLastEventTime = startTime;
 138         fNbBuckets = nbBuckets;
 139         fBuckets = new long[nbBuckets];
 140         fModelListeners = new ListenerList();
 141         clear();
 142     }
 143
 144     /**
 145      * Copy constructor.
 146      * @param other A model to copy.
 147      */
 148     public HistogramDataModel(HistogramDataModel other) {
 149         fNbBuckets = other.fNbBuckets;
 150         fBuckets = Arrays.copyOf(other.fBuckets, fNbBuckets);
 151         fBucketDuration = Math.max(other.fBucketDuration, 1);
 152         fNbEvents = other.fNbEvents;
 153         fLastBucket = other.fLastBucket;
 154         fFirstBucketTime = other.fFirstBucketTime;
 155         fFirstEventTime = other.fFirstEventTime;
 156         fLastEventTime = other.fLastEventTime;
 157         fCurrentEventTime = other.fCurrentEventTime;
 158         fTimeLimit = other.fTimeLimit;
 159         fModelListeners = new ListenerList();
 160         Object[] listeners = other.fModelListeners.getListeners();
 161         for (Object listener : listeners) {
 162             fModelListeners.add(listener);
 163         }
 164     }
 165
 166     // ------------------------------------------------------------------------
 167     // Accessors
 168     // ------------------------------------------------------------------------
 169
 170     /**
 171      * Returns the number of events in the data model.
 172      * @return number of events.
 173      */
 174     public long getNbEvents() {
 175         return fNbEvents;
 176     }
 177
 178     /**
 179      * Returns the number of buckets in the model.
 180      * @return number of buckets.
 181      */
 182     public int getNbBuckets() {
 183         return fNbBuckets;
 184     }
 185
 186    /**
 187     * Returns the current bucket duration.
 188     * @return bucket duration
 189     */
 190     public long getBucketDuration() {
 191         return fBucketDuration;
 192     }
 193
 194     /**
 195      * Returns the time value of the first bucket in the model.
 196      * @return time of first bucket.
 197      */
 198     public long getFirstBucketTime() {
 199         return fFirstBucketTime;
 200     }
 201
 202     /**
 203      * Returns the time of the first event in the model.
 204      * @return time of first event.
 205      */
 206     public long getStartTime() {
 207         return fFirstEventTime;
 208     }
 209
 210     /**
 211      * Sets the model start time
 212      * @param startTime the histogram range start time
 213      * @param endTime the histogram range end time
 214      * @since 2.0
 215      */
 216     public void setTimeRange(long startTime, long endTime) {
 217         fFirstBucketTime = fFirstEventTime = fLastEventTime = startTime;
 218         fBucketDuration = 1;
 219         updateEndTime();
 220         while (endTime >= fTimeLimit) {
 221             mergeBuckets();
 222         }
 223     }
 224
 225     /**
 226      * Returns the time of the last event in the model.
 227      * @return the time of last event.
 228      */
 229     public long getEndTime() {
 230         return fLastEventTime;
 231     }
 232
 233     /**
 234      * Returns the time of the current event in the model.
 235      * @return the time of the current event.
 236      */
 237     public long getCurrentEventTime() {
 238         return fCurrentEventTime;
 239     }
 240
 241     /**
 242      * Returns the time limit with is: start time + nbBuckets * bucketDuration
 243      * @return the time limit.
 244      */
 245     public long getTimeLimit() {
 246         return fTimeLimit;
 247     }
 248
 249     // ------------------------------------------------------------------------
 250     // Listener handling
 251     // ------------------------------------------------------------------------
 252
 253     /**
 254      * Add a listener to the model to be informed about model changes.
 255      * @param listener A listener to add.
 256      */
 257     public void addHistogramListener(IHistogramModelListener listener) {
 258         fModelListeners.add(listener);
 259     }
 260
 261     /**
 262      * Remove a given model listener.
 263      * @param listener A listener to remove.
 264      */
 265     public void removeHistogramListener(IHistogramModelListener listener) {
 266         fModelListeners.remove(listener);
 267     }
 268
 269     // Notify listeners (always)
 270     private void fireModelUpdateNotification() {
 271         fireModelUpdateNotification(0);
 272     }
 273
 274     // Notify listener on boundary
 275     private void fireModelUpdateNotification(long count) {
 276         if ((count % REFRESH_FREQUENCY) == 0) {
 277             Object[] listeners = fModelListeners.getListeners();
 278             for (Object listener2 : listeners) {
 279                 IHistogramModelListener listener = (IHistogramModelListener) listener2;
 280                 listener.modelUpdated();
 281             }
 282         }
 283     }
 284
 285     // ------------------------------------------------------------------------
 286     // Operations
 287     // ------------------------------------------------------------------------
 288
 289     /*
 290      * (non-Javadoc)
 291      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#complete()
 292      */
 293     @Override
 294     public void complete() {
 295         fireModelUpdateNotification();
 296     }
 297
 298     /**
 299      * Clear the histogram model.
 300      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
 301      */
 302     @Override
 303     public void clear() {
 304         Arrays.fill(fBuckets, 0);
 305         fNbEvents = 0;
 306         fFirstBucketTime = 0;
 307         fLastEventTime = 0;
 308         fCurrentEventTime = 0;
 309         fLastBucket = 0;
 310         fBucketDuration = 1;
 311         updateEndTime();
 312         fireModelUpdateNotification();
 313     }
 314
 315     /**
 316      * Sets the current event time (no notification of listeners)
 317      *
 318      * @param timestamp A time stamp to set.
 319      */
 320     public void setCurrentEvent(long timestamp) {
 321         fCurrentEventTime = timestamp;
 322     }
 323
 324     /**
 325      * Sets the current event time with notification of listeners
 326      *
 327      * @param timestamp A time stamp to set.
 328      */
 329     public void setCurrentEventNotifyListeners(long timestamp) {
 330         fCurrentEventTime = timestamp;
 331         fireModelUpdateNotification();
 332     }
 333
 334     /**
 335      * Add event to the correct bucket, compacting the if needed.
 336      *
 337      * @param eventCount The current event Count (for notification purposes)
 338      * @param timestamp The timestamp of the event to count
 339      *
 340      */
 341     @Override
 342     public void countEvent(long eventCount, long timestamp) {
 343
 344         // Validate
 345         if (timestamp < 0) {
 346             return;
 347         }
 348
 349         // Set the start/end time if not already done
 350         if ((fFirstBucketTime == 0) && (fLastBucket == 0) && (fBuckets[0] == 0) && (timestamp > 0)) {
 351             fFirstBucketTime = timestamp;
 352             fFirstEventTime = timestamp;
 353             updateEndTime();
 354         }
 355
 356         if (timestamp < fFirstEventTime) {
 357             fFirstEventTime = timestamp;
 358         }
 359
 360         if (fLastEventTime < timestamp) {
 361             fLastEventTime = timestamp;
 362         }
 363
 364         if (timestamp >= fFirstBucketTime) {
 365
 366             // Compact as needed
 367             while (timestamp >= fTimeLimit) {
 368                 mergeBuckets();
 369             }
 370
 371         } else {
 372
 373             // get offset for adjustment
 374             int offset = getOffset(timestamp);
 375
 376             // Compact as needed
 377             while((fLastBucket + offset) >= fNbBuckets) {
 378                 mergeBuckets();
 379                 offset = getOffset(timestamp);
 380             }
 381
 382             moveBuckets(offset);
 383
 384             fLastBucket = fLastBucket + offset;
 385
 386             fFirstBucketTime = fFirstBucketTime - (offset*fBucketDuration);
 387             updateEndTime();
 388         }
 389
 390         // Increment the right bucket
 391         int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
 392         fBuckets[index]++;
 393         fNbEvents++;
 394         if (fLastBucket < index) {
 395             fLastBucket = index;
 396         }
 397
 398         fireModelUpdateNotification(eventCount);
 399     }
 400
 401     /**
 402      * Scale the model data to the width, height and bar width requested.
 403      *
 404      * @param width A width of the histogram canvas
 405      * @param height A height of the histogram canvas
 406      * @param barWidth A width (in pixel) of a histogram bar
 407      * @return the result array of size [width] and where the highest value doesn't exceed [height]
 408      *
 409      * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int, int, int)
 410      */
 411     @Override
 412     public HistogramScaledData scaleTo(int width, int height, int barWidth) {
 413         // Basic validation
 414         if ((width <= 0) ||  (height <= 0) || (barWidth <= 0))
 415          {
 416             throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 417         }
 418
 419         // The result structure
 420         HistogramScaledData result = new HistogramScaledData(width, height, barWidth);
 421
 422         // Scale horizontally
 423         result.fMaxValue = 0;
 424
 425         int nbBars = width / barWidth;
 426         int bucketsPerBar = (fLastBucket / nbBars) + 1;
 427         result.fBucketDuration = Math.max(bucketsPerBar * fBucketDuration,1);
 428         for (int i = 0; i < nbBars; i++) {
 429             int count = 0;
 430             for (int j = i * bucketsPerBar; j < ((i + 1) * bucketsPerBar); j++) {
 431                 if (fNbBuckets <= j) {
 432                     break;
 433                 }
 434                 count += fBuckets[j];
 435             }
 436             result.fData[i] = count;
 437             result.fLastBucket = i;
 438             if (result.fMaxValue < count) {
 439                 result.fMaxValue = count;
 440             }
 441         }
 442
 443         // Scale vertically
 444         if (result.fMaxValue > 0) {
 445             result.fScalingFactor = (double) height / result.fMaxValue;
 446         }
 447
 448         fBucketDuration = Math.max(fBucketDuration, 1);
 449         // Set the current event index in the scaled histogram
 450         if ((fCurrentEventTime >= fFirstBucketTime) && (fCurrentEventTime <= fLastEventTime)) {
 451             result.fCurrentBucket = (int) ((fCurrentEventTime - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 452         } else {
 453             result.fCurrentBucket = HistogramScaledData.OUT_OF_RANGE_BUCKET;
 454         }
 455
 456         result.fFirstBucketTime = fFirstBucketTime;
 457         result.fFirstEventTime = fFirstEventTime;
 458         return result;
 459     }
 460
 461     // ------------------------------------------------------------------------
 462     // Helper functions
 463     // ------------------------------------------------------------------------
 464
 465     private void updateEndTime() {
 466         fTimeLimit = fFirstBucketTime + (fNbBuckets * fBucketDuration);
 467     }
 468
 469     private void mergeBuckets() {
 470         for (int i = 0; i < (fNbBuckets / 2); i++) {
 471             fBuckets[i] = fBuckets[2 * i] + fBuckets[(2 * i) + 1];
 472         }
 473         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 474         fBucketDuration *= 2;
 475         updateEndTime();
 476         fLastBucket = (fNbBuckets / 2) - 1;
 477     }
 478
 479     private void moveBuckets(int offset) {
 480         for(int i = fNbBuckets - 1; i >= offset; i--) {
 481             fBuckets[i] = fBuckets[i-offset];
 482         }
 483
 484         for (int i = 0; i < offset; i++) {
 485             fBuckets[i] = 0;
 486         }
 487     }
 488
 489     private int getOffset(long timestamp) {
 490         int offset = (int) ((fFirstBucketTime - timestamp) / fBucketDuration);
 491         if (((fFirstBucketTime - timestamp) % fBucketDuration) != 0) {
 492             offset++;
 493         }
 494         return offset;
 495     }
 496
 497 }