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

   1 /*******************************************************************************
   2  * Copyright (c) 2011, 2013 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  *   Patrick Tasse - Support selection range
  16  *   Jean-Christian Kouamé, Simon Delisle - Added support to manage lost events
  17  *******************************************************************************/
  18
  19 package org.eclipse.linuxtools.tmf.ui.views.histogram;
  20
  21 import java.util.Arrays;
  22
  23 import org.eclipse.core.runtime.ListenerList;
  24 import org.eclipse.linuxtools.tmf.core.timestamp.TmfTimeRange;
  25
  26 /**
  27  * Histogram-independent data model.
  28  *
  29  * It has the following characteristics:
  30  * <ul>
  31  * <li>The <i>basetime</i> is the timestamp of the first event
  32  * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration
  33  * (<i>d</i>)
  34  * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
  35  * <li>Bucket <i>i</i> holds the number of events that occurred in time range:
  36  * [<i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
  37  * <i>d</i>)
  38  * </ul>
  39  * Initially, the bucket durations is set to 1ns. As the events are read, they
  40  * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
  41  * to the <i>basetime</i>).
  42  * <p>
  43  * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
  44  * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
  45  * bucket duration). At this point, the histogram needs to be compacted. This is
  46  * done by simply merging adjacent buckets by pair, in effect doubling the
  47  * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> =
  48  * 2<i>d</i>). This compaction happens as needed as the trace is read.
  49  * <p>
  50  * The model allows for timestamps in not increasing order. The timestamps can
  51  * be fed to the model in any order. If an event has a timestamp less than the
  52  * <i>basetime</i>, the buckets will be moved to the right to account for the
  53  * new smaller timestamp. The new <i>basetime</i> is a multiple of the bucket
  54  * duration smaller then the previous <i>basetime</i>. Note that the
  55  * <i>basetime</i> might no longer be the timestamp of an event. If necessary,
  56  * the buckets will be compacted before moving to the right. This might be
  57  * necessary to not lose any event counts at the end of the buckets array.
  58  * <p>
  59  * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
  60  * method. By keeping the number of buckets <i>n</i> relatively large with
  61  * respect to to the number of pixels in the actual histogram, we should achieve
  62  * a nice result when visualizing the histogram.
  63  * <p>
  64  *
  65  * @version 2.0
  66  * @author Francois Chouinard
  67  */
  68 public class HistogramDataModel implements IHistogramDataModel {
  69
  70     // ------------------------------------------------------------------------
  71     // Constants
  72     // ------------------------------------------------------------------------
  73
  74     /**
  75      * The default number of buckets
  76      */
  77     public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;
  78
  79     /**
  80      * Number of events after which listeners will be notified.
  81      */
  82     public static final int REFRESH_FREQUENCY = DEFAULT_NUMBER_OF_BUCKETS;
  83
  84     // ------------------------------------------------------------------------
  85     // Attributes
  86     // ------------------------------------------------------------------------
  87
  88     // Bucket management
  89     private final int fNbBuckets;
  90     private final long[] fBuckets;
  91     private final long[] fLostEventsBuckets;
  92     private long fBucketDuration;
  93     private long fNbEvents;
  94     private int fLastBucket;
  95
  96     // Timestamps
  97     private long fFirstBucketTime; // could be negative when analyzing events with descending order!!!
  98     private long fFirstEventTime;
  99     private long fLastEventTime;
 100     private long fSelectionBegin;
 101     private long fSelectionEnd;
 102     private long fTimeLimit;
 103
 104     // Private listener lists
 105     private final ListenerList fModelListeners;
 106
 107     // ------------------------------------------------------------------------
 108     // Constructors
 109     // ------------------------------------------------------------------------
 110
 111     /**
 112      * Default constructor with default number of buckets.
 113      */
 114     public HistogramDataModel() {
 115         this(0, DEFAULT_NUMBER_OF_BUCKETS);
 116     }
 117
 118     /**
 119      * Default constructor with default number of buckets.
 120      *
 121      * @param startTime
 122      *            The histogram start time
 123      * @since 2.0
 124      */
 125     public HistogramDataModel(long startTime) {
 126         this(startTime, DEFAULT_NUMBER_OF_BUCKETS);
 127     }
 128
 129     /**
 130      * Constructor with non-default number of buckets.
 131      *
 132      * @param nbBuckets
 133      *            A number of buckets.
 134      */
 135     public HistogramDataModel(int nbBuckets) {
 136         this(0, nbBuckets);
 137     }
 138
 139     /**
 140      * Constructor with non-default number of buckets.
 141      *
 142      * @param startTime
 143      *            the histogram start time
 144      * @param nbBuckets
 145      *            A number of buckets.
 146      * @since 2.0
 147      */
 148     public HistogramDataModel(long startTime, int nbBuckets) {
 149         fFirstBucketTime = fFirstEventTime = fLastEventTime = startTime;
 150         fNbBuckets = nbBuckets;
 151         fBuckets = new long[nbBuckets];
 152         fLostEventsBuckets = new long[nbBuckets];
 153         fModelListeners = new ListenerList();
 154         clear();
 155     }
 156
 157     /**
 158      * Copy constructor.
 159      *
 160      * @param other
 161      *            A model to copy.
 162      */
 163     public HistogramDataModel(HistogramDataModel other) {
 164         fNbBuckets = other.fNbBuckets;
 165         fBuckets = Arrays.copyOf(other.fBuckets, fNbBuckets);
 166         fLostEventsBuckets = Arrays.copyOf(other.fLostEventsBuckets, fNbBuckets);
 167         fBucketDuration = Math.max(other.fBucketDuration, 1);
 168         fNbEvents = other.fNbEvents;
 169         fLastBucket = other.fLastBucket;
 170         fFirstBucketTime = other.fFirstBucketTime;
 171         fFirstEventTime = other.fFirstEventTime;
 172         fLastEventTime = other.fLastEventTime;
 173         fSelectionBegin = other.fSelectionBegin;
 174         fSelectionEnd = other.fSelectionEnd;
 175         fTimeLimit = other.fTimeLimit;
 176         fModelListeners = new ListenerList();
 177         Object[] listeners = other.fModelListeners.getListeners();
 178         for (Object listener : listeners) {
 179             fModelListeners.add(listener);
 180         }
 181     }
 182
 183     // ------------------------------------------------------------------------
 184     // Accessors
 185     // ------------------------------------------------------------------------
 186
 187     /**
 188      * Returns the number of events in the data model.
 189      *
 190      * @return number of events.
 191      */
 192     public long getNbEvents() {
 193         return fNbEvents;
 194     }
 195
 196     /**
 197      * Returns the number of buckets in the model.
 198      *
 199      * @return number of buckets.
 200      */
 201     public int getNbBuckets() {
 202         return fNbBuckets;
 203     }
 204
 205     /**
 206      * Returns the current bucket duration.
 207      *
 208      * @return bucket duration
 209      */
 210     public long getBucketDuration() {
 211         return fBucketDuration;
 212     }
 213
 214     /**
 215      * Returns the time value of the first bucket in the model.
 216      *
 217      * @return time of first bucket.
 218      */
 219     public long getFirstBucketTime() {
 220         return fFirstBucketTime;
 221     }
 222
 223     /**
 224      * Returns the time of the first event in the model.
 225      *
 226      * @return time of first event.
 227      */
 228     public long getStartTime() {
 229         return fFirstEventTime;
 230     }
 231
 232     /**
 233      * Sets the model start time
 234      *
 235      * @param startTime
 236      *            the histogram range start time
 237      * @param endTime
 238      *            the histogram range end time
 239      * @since 2.0
 240      */
 241     public void setTimeRange(long startTime, long endTime) {
 242         fFirstBucketTime = fFirstEventTime = fLastEventTime = startTime;
 243         fBucketDuration = 1;
 244         updateEndTime();
 245         while (endTime >= fTimeLimit) {
 246             mergeBuckets();
 247         }
 248     }
 249
 250     /**
 251      * Returns the time of the last event in the model.
 252      *
 253      * @return the time of last event.
 254      */
 255     public long getEndTime() {
 256         return fLastEventTime;
 257     }
 258
 259     /**
 260      * Returns the time of the current event in the model.
 261      *
 262      * @return the time of the current event.
 263      * @deprecated As of 2.1, use {@link #getSelectionBegin()} and
 264      *             {@link #getSelectionEnd()}
 265      */
 266     @Deprecated
 267     public long getCurrentEventTime() {
 268         return fSelectionBegin;
 269     }
 270
 271     /**
 272      * Returns the begin time of the current selection in the model.
 273      *
 274      * @return the begin time of the current selection.
 275      * @since 2.1
 276      */
 277     public long getSelectionBegin() {
 278         return fSelectionBegin;
 279     }
 280
 281     /**
 282      * Returns the end time of the current selection in the model.
 283      *
 284      * @return the end time of the current selection.
 285      * @since 2.1
 286      */
 287     public long getSelectionEnd() {
 288         return fSelectionEnd;
 289     }
 290
 291     /**
 292      * Returns the time limit with is: start time + nbBuckets * bucketDuration
 293      *
 294      * @return the time limit.
 295      */
 296     public long getTimeLimit() {
 297         return fTimeLimit;
 298     }
 299
 300     // ------------------------------------------------------------------------
 301     // Listener handling
 302     // ------------------------------------------------------------------------
 303
 304     /**
 305      * Add a listener to the model to be informed about model changes.
 306      *
 307      * @param listener
 308      *            A listener to add.
 309      */
 310     public void addHistogramListener(IHistogramModelListener listener) {
 311         fModelListeners.add(listener);
 312     }
 313
 314     /**
 315      * Remove a given model listener.
 316      *
 317      * @param listener
 318      *            A listener to remove.
 319      */
 320     public void removeHistogramListener(IHistogramModelListener listener) {
 321         fModelListeners.remove(listener);
 322     }
 323
 324     // Notify listeners (always)
 325     private void fireModelUpdateNotification() {
 326         fireModelUpdateNotification(0);
 327     }
 328
 329     // Notify listener on boundary
 330     private void fireModelUpdateNotification(long count) {
 331         if ((count % REFRESH_FREQUENCY) == 0) {
 332             Object[] listeners = fModelListeners.getListeners();
 333             for (Object listener2 : listeners) {
 334                 IHistogramModelListener listener = (IHistogramModelListener) listener2;
 335                 listener.modelUpdated();
 336             }
 337         }
 338     }
 339
 340     // ------------------------------------------------------------------------
 341     // Operations
 342     // ------------------------------------------------------------------------
 343
 344     @Override
 345     public void complete() {
 346         fireModelUpdateNotification();
 347     }
 348
 349     /**
 350      * Clear the histogram model.
 351      *
 352      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
 353      */
 354     @Override
 355     public void clear() {
 356         Arrays.fill(fBuckets, 0);
 357         Arrays.fill(fLostEventsBuckets, 0);
 358         fNbEvents = 0;
 359         fFirstBucketTime = 0;
 360         fLastEventTime = 0;
 361         fSelectionBegin = 0;
 362         fSelectionEnd = 0;
 363         fLastBucket = 0;
 364         fBucketDuration = 1;
 365         updateEndTime();
 366         fireModelUpdateNotification();
 367     }
 368
 369     /**
 370      * Sets the current event time (no notification of listeners)
 371      *
 372      * @param timestamp
 373      *            A time stamp to set.
 374      * @deprecated As of 2.1, use {@link #setSelection(long, long)}
 375      */
 376     @Deprecated
 377     public void setCurrentEvent(long timestamp) {
 378         fSelectionBegin = timestamp;
 379         fSelectionEnd = timestamp;
 380     }
 381
 382     /**
 383      * Sets the current event time with notification of listeners
 384      *
 385      * @param timestamp
 386      *            A time stamp to set.
 387      * @deprecated As of 2.1, use
 388      *             {@link #setSelectionNotifyListeners(long, long)}
 389      */
 390     @Deprecated
 391     public void setCurrentEventNotifyListeners(long timestamp) {
 392         fSelectionBegin = timestamp;
 393         fSelectionEnd = timestamp;
 394         fireModelUpdateNotification();
 395     }
 396
 397     /**
 398      * Sets the current selection time range (no notification of listeners)
 399      *
 400      * @param beginTime
 401      *            The selection begin time.
 402      * @param endTime
 403      *            The selection end time.
 404      * @since 2.1
 405      */
 406     public void setSelection(long beginTime, long endTime) {
 407         fSelectionBegin = beginTime;
 408         fSelectionEnd = endTime;
 409     }
 410
 411     /**
 412      * Sets the current selection time range with notification of listeners
 413      *
 414      * @param beginTime
 415      *            The selection begin time.
 416      * @param endTime
 417      *            The selection end time.
 418      * @since 2.1
 419      */
 420     public void setSelectionNotifyListeners(long beginTime, long endTime) {
 421         fSelectionBegin = beginTime;
 422         fSelectionEnd = endTime;
 423         fireModelUpdateNotification();
 424     }
 425
 426     /**
 427      * Add event to the correct bucket, compacting the if needed.
 428      *
 429      * @param eventCount
 430      *            The current event Count (for notification purposes)
 431      * @param timestamp
 432      *            The timestamp of the event to count
 433      *
 434      */
 435     @Override
 436     public void countEvent(long eventCount, long timestamp) {
 437
 438         // Validate
 439         if (timestamp < 0) {
 440             return;
 441         }
 442
 443         // Set the start/end time if not already done
 444         if ((fFirstBucketTime == 0) && (fLastBucket == 0) && (fBuckets[0] == 0) && (timestamp > 0)) {
 445             fFirstBucketTime = timestamp;
 446             fFirstEventTime = timestamp;
 447             updateEndTime();
 448         }
 449
 450         if (timestamp < fFirstEventTime) {
 451             fFirstEventTime = timestamp;
 452         }
 453
 454         if (fLastEventTime < timestamp) {
 455             fLastEventTime = timestamp;
 456         }
 457
 458         if (timestamp >= fFirstBucketTime) {
 459
 460             // Compact as needed
 461             while (timestamp >= fTimeLimit) {
 462                 mergeBuckets();
 463             }
 464
 465         } else {
 466
 467             // get offset for adjustment
 468             int offset = getOffset(timestamp);
 469
 470             // Compact as needed
 471             while ((fLastBucket + offset) >= fNbBuckets) {
 472                 mergeBuckets();
 473                 offset = getOffset(timestamp);
 474             }
 475
 476             moveBuckets(offset);
 477
 478             fLastBucket = fLastBucket + offset;
 479
 480             fFirstBucketTime = fFirstBucketTime - (offset * fBucketDuration);
 481             updateEndTime();
 482         }
 483
 484         // Increment the right bucket
 485         int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
 486         fBuckets[index]++;
 487         fNbEvents++;
 488         if (fLastBucket < index) {
 489             fLastBucket = index;
 490         }
 491
 492         fireModelUpdateNotification(eventCount);
 493     }
 494
 495     /**
 496      * Add lost event to the correct bucket, compacting the if needed.
 497      *
 498      * @param timeRange
 499      *            time range of a lost event
 500      * @param nbLostEvents
 501      *            the number of lost events
 502      * @param fullRange
 503      *            Full range or time range for histogram request
 504      * @since 2.2
 505      */
 506     public void countLostEvent(TmfTimeRange timeRange, long nbLostEvents, boolean fullRange) {
 507
 508         // Validate
 509         if (timeRange.getStartTime().getValue() < 0 || timeRange.getEndTime().getValue() < 0) {
 510             return;
 511         }
 512
 513         // Compact as needed
 514         if (fullRange) {
 515             while (timeRange.getEndTime().getValue() >= fTimeLimit) {
 516                 mergeBuckets();
 517             }
 518         }
 519
 520         int indexStart = (int) ((timeRange.getStartTime().getValue() - fFirstBucketTime) / fBucketDuration);
 521         int indexEnd = (int) ((timeRange.getEndTime().getValue() - fFirstBucketTime) / fBucketDuration);
 522         int nbBucketRange = (indexEnd - indexStart) + 1;
 523
 524         int lostEventPerBucket = (int) Math.ceil((double) nbLostEvents / nbBucketRange);
 525         long lastLostCol = Math.max(1, nbLostEvents - lostEventPerBucket * (nbBucketRange - 1));
 526
 527         // Increment the right bucket, bear in mind that ranges make it almost certain that some lost events are out of range
 528         for (int index = indexStart; index <= indexEnd && index < fLostEventsBuckets.length; index++) {
 529             if (index == (indexStart + nbBucketRange - 1)) {
 530                 fLostEventsBuckets[index] += lastLostCol;
 531             } else {
 532                 fLostEventsBuckets[index] += lostEventPerBucket;
 533             }
 534         }
 535
 536         fNbEvents++;
 537
 538         fireModelUpdateNotification(nbLostEvents);
 539     }
 540
 541     /**
 542      * Scale the model data to the width, height and bar width requested.
 543      *
 544      * @param width
 545      *            A width of the histogram canvas
 546      * @param height
 547      *            A height of the histogram canvas
 548      * @param barWidth
 549      *            A width (in pixel) of a histogram bar
 550      * @return the result array of size [width] and where the highest value
 551      *         doesn't exceed [height]
 552      *
 553      * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int,
 554      *      int, int)
 555      */
 556     @Override
 557     public HistogramScaledData scaleTo(int width, int height, int barWidth) {
 558         // Basic validation
 559         if ((width <= 0) || (height <= 0) || (barWidth <= 0))
 560         {
 561             throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 562         }
 563
 564         // The result structure
 565         HistogramScaledData result = new HistogramScaledData(width, height, barWidth);
 566
 567         // Scale horizontally
 568         result.fMaxValue = 0;
 569
 570         int nbBars = width / barWidth;
 571         int bucketsPerBar = (fLastBucket / nbBars) + 1;
 572         result.fBucketDuration = Math.max(bucketsPerBar * fBucketDuration, 1);
 573         for (int i = 0; i < nbBars; i++) {
 574             int count = 0;
 575             int countLostEvent = 0;
 576             for (int j = i * bucketsPerBar; j < ((i + 1) * bucketsPerBar); j++) {
 577                 if (fNbBuckets <= j) {
 578                     break;
 579                 }
 580                 count += fBuckets[j];
 581                 countLostEvent += fLostEventsBuckets[j];
 582             }
 583             result.fData[i] = count;
 584             result.fLostEventsData[i] = countLostEvent;
 585             result.fLastBucket = i;
 586             if (result.fMaxValue < count) {
 587                 result.fMaxValue = count;
 588             }
 589             if (result.fMaxCombinedValue < count + countLostEvent) {
 590                 result.fMaxCombinedValue = count + countLostEvent;
 591             }
 592         }
 593
 594         // Scale vertically
 595         if (result.fMaxValue > 0) {
 596             result.fScalingFactor = (double) height / result.fMaxValue;
 597         }
 598         if (result.fMaxCombinedValue > 0) {
 599             result.fScalingFactorCombined = (double) height / result.fMaxCombinedValue;
 600         }
 601
 602         fBucketDuration = Math.max(fBucketDuration, 1);
 603         // Set selection begin and end index in the scaled histogram
 604         if (fSelectionBegin < fFirstBucketTime) {
 605             result.fSelectionBeginBucket = -1;
 606         } else if (fSelectionBegin > fLastEventTime) {
 607             result.fSelectionBeginBucket = fLastBucket;
 608         } else {
 609             result.fSelectionBeginBucket = (int) ((fSelectionBegin - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 610         }
 611         if (fSelectionEnd < fFirstBucketTime) {
 612             result.fSelectionEndBucket = -1;
 613         } else if (fSelectionEnd > fLastEventTime) {
 614             result.fSelectionEndBucket = fLastBucket;
 615         } else {
 616             result.fSelectionEndBucket = (int) ((fSelectionEnd - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 617         }
 618
 619         result.fFirstBucketTime = fFirstBucketTime;
 620         result.fFirstEventTime = fFirstEventTime;
 621         return result;
 622     }
 623
 624     // ------------------------------------------------------------------------
 625     // Helper functions
 626     // ------------------------------------------------------------------------
 627
 628     private void updateEndTime() {
 629         fTimeLimit = fFirstBucketTime + (fNbBuckets * fBucketDuration);
 630     }
 631
 632     private void mergeBuckets() {
 633         for (int i = 0; i < (fNbBuckets / 2); i++) {
 634             fBuckets[i] = fBuckets[2 * i] + fBuckets[(2 * i) + 1];
 635             fLostEventsBuckets[i] = fLostEventsBuckets[2 * i] + fLostEventsBuckets[(2 * i) + 1];
 636         }
 637         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 638         Arrays.fill(fLostEventsBuckets, fNbBuckets / 2, fNbBuckets, 0);
 639         fBucketDuration *= 2;
 640         updateEndTime();
 641         fLastBucket = (fNbBuckets / 2) - 1;
 642     }
 643
 644     private void moveBuckets(int offset) {
 645         for (int i = fNbBuckets - 1; i >= offset; i--) {
 646             fBuckets[i] = fBuckets[i - offset];
 647             fLostEventsBuckets[i] = fLostEventsBuckets[i - offset];
 648         }
 649
 650         for (int i = 0; i < offset; i++) {
 651             fBuckets[i] = 0;
 652             fLostEventsBuckets[i] = 0;
 653         }
 654     }
 655
 656     private int getOffset(long timestamp) {
 657         int offset = (int) ((fFirstBucketTime - timestamp) / fBucketDuration);
 658         if (((fFirstBucketTime - timestamp) % fBucketDuration) != 0) {
 659             offset++;
 660         }
 661         return offset;
 662     }
 663 }