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 fEndTime;
 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 = fEndTime = 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         fEndTime = other.fEndTime;
 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 = fEndTime = startTime;
 243         fBucketDuration = 1;
 244         updateEndTime();
 245         while (endTime >= fTimeLimit) {
 246             mergeBuckets();
 247         }
 248     }
 249
 250     /**
 251      * Set the end time. Setting this ensures that the corresponding bucket is
 252      * displayed regardless of the event counts.
 253      *
 254      * @param endTime
 255      *            the time of the last used bucket
 256      * @since 2.2
 257      */
 258     public void setEndTime(long endTime) {
 259         fEndTime = endTime;
 260         fLastBucket = (int) ((endTime - fFirstBucketTime) / fBucketDuration);
 261     }
 262
 263     /**
 264      * Returns the end time.
 265      *
 266      * @return the time of the last used bucket
 267      */
 268     public long getEndTime() {
 269         return fEndTime;
 270     }
 271
 272     /**
 273      * Returns the time of the current event in the model.
 274      *
 275      * @return the time of the current event.
 276      * @deprecated As of 2.1, use {@link #getSelectionBegin()} and
 277      *             {@link #getSelectionEnd()}
 278      */
 279     @Deprecated
 280     public long getCurrentEventTime() {
 281         return fSelectionBegin;
 282     }
 283
 284     /**
 285      * Returns the begin time of the current selection in the model.
 286      *
 287      * @return the begin time of the current selection.
 288      * @since 2.1
 289      */
 290     public long getSelectionBegin() {
 291         return fSelectionBegin;
 292     }
 293
 294     /**
 295      * Returns the end time of the current selection in the model.
 296      *
 297      * @return the end time of the current selection.
 298      * @since 2.1
 299      */
 300     public long getSelectionEnd() {
 301         return fSelectionEnd;
 302     }
 303
 304     /**
 305      * Returns the time limit with is: start time + nbBuckets * bucketDuration
 306      *
 307      * @return the time limit.
 308      */
 309     public long getTimeLimit() {
 310         return fTimeLimit;
 311     }
 312
 313     // ------------------------------------------------------------------------
 314     // Listener handling
 315     // ------------------------------------------------------------------------
 316
 317     /**
 318      * Add a listener to the model to be informed about model changes.
 319      *
 320      * @param listener
 321      *            A listener to add.
 322      */
 323     public void addHistogramListener(IHistogramModelListener listener) {
 324         fModelListeners.add(listener);
 325     }
 326
 327     /**
 328      * Remove a given model listener.
 329      *
 330      * @param listener
 331      *            A listener to remove.
 332      */
 333     public void removeHistogramListener(IHistogramModelListener listener) {
 334         fModelListeners.remove(listener);
 335     }
 336
 337     // Notify listeners (always)
 338     private void fireModelUpdateNotification() {
 339         fireModelUpdateNotification(0);
 340     }
 341
 342     // Notify listener on boundary
 343     private void fireModelUpdateNotification(long count) {
 344         if ((count % REFRESH_FREQUENCY) == 0) {
 345             Object[] listeners = fModelListeners.getListeners();
 346             for (Object listener2 : listeners) {
 347                 IHistogramModelListener listener = (IHistogramModelListener) listener2;
 348                 listener.modelUpdated();
 349             }
 350         }
 351     }
 352
 353     // ------------------------------------------------------------------------
 354     // Operations
 355     // ------------------------------------------------------------------------
 356
 357     @Override
 358     public void complete() {
 359         fireModelUpdateNotification();
 360     }
 361
 362     /**
 363      * Clear the histogram model.
 364      *
 365      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
 366      */
 367     @Override
 368     public void clear() {
 369         Arrays.fill(fBuckets, 0);
 370         Arrays.fill(fLostEventsBuckets, 0);
 371         fNbEvents = 0;
 372         fFirstBucketTime = 0;
 373         fEndTime = 0;
 374         fSelectionBegin = 0;
 375         fSelectionEnd = 0;
 376         fLastBucket = 0;
 377         fBucketDuration = 1;
 378         updateEndTime();
 379         fireModelUpdateNotification();
 380     }
 381
 382     /**
 383      * Sets the current event time (no notification of listeners)
 384      *
 385      * @param timestamp
 386      *            A time stamp to set.
 387      * @deprecated As of 2.1, use {@link #setSelection(long, long)}
 388      */
 389     @Deprecated
 390     public void setCurrentEvent(long timestamp) {
 391         fSelectionBegin = timestamp;
 392         fSelectionEnd = timestamp;
 393     }
 394
 395     /**
 396      * Sets the current event time with notification of listeners
 397      *
 398      * @param timestamp
 399      *            A time stamp to set.
 400      * @deprecated As of 2.1, use
 401      *             {@link #setSelectionNotifyListeners(long, long)}
 402      */
 403     @Deprecated
 404     public void setCurrentEventNotifyListeners(long timestamp) {
 405         fSelectionBegin = timestamp;
 406         fSelectionEnd = timestamp;
 407         fireModelUpdateNotification();
 408     }
 409
 410     /**
 411      * Sets the current selection time range (no notification of listeners)
 412      *
 413      * @param beginTime
 414      *            The selection begin time.
 415      * @param endTime
 416      *            The selection end time.
 417      * @since 2.1
 418      */
 419     public void setSelection(long beginTime, long endTime) {
 420         fSelectionBegin = beginTime;
 421         fSelectionEnd = endTime;
 422     }
 423
 424     /**
 425      * Sets the current selection time range with notification of listeners
 426      *
 427      * @param beginTime
 428      *            The selection begin time.
 429      * @param endTime
 430      *            The selection end time.
 431      * @since 2.1
 432      */
 433     public void setSelectionNotifyListeners(long beginTime, long endTime) {
 434         fSelectionBegin = beginTime;
 435         fSelectionEnd = endTime;
 436         fireModelUpdateNotification();
 437     }
 438
 439     /**
 440      * Add event to the correct bucket, compacting the if needed.
 441      *
 442      * @param eventCount
 443      *            The current event Count (for notification purposes)
 444      * @param timestamp
 445      *            The timestamp of the event to count
 446      *
 447      */
 448     @Override
 449     public void countEvent(long eventCount, long timestamp) {
 450
 451         // Validate
 452         if (timestamp < 0) {
 453             return;
 454         }
 455
 456         // Set the start/end time if not already done
 457         if ((fFirstBucketTime == 0) && (fLastBucket == 0) && (fBuckets[0] == 0) && (timestamp > 0)) {
 458             fFirstBucketTime = timestamp;
 459             fFirstEventTime = timestamp;
 460             updateEndTime();
 461         }
 462
 463         if (timestamp < fFirstEventTime) {
 464             fFirstEventTime = timestamp;
 465         }
 466
 467         if (fEndTime < timestamp) {
 468             fEndTime = timestamp;
 469         }
 470
 471         if (timestamp >= fFirstBucketTime) {
 472
 473             // Compact as needed
 474             while (timestamp >= fTimeLimit) {
 475                 mergeBuckets();
 476             }
 477
 478         } else {
 479
 480             // get offset for adjustment
 481             int offset = getOffset(timestamp);
 482
 483             // Compact as needed
 484             while ((fLastBucket + offset) >= fNbBuckets) {
 485                 mergeBuckets();
 486                 offset = getOffset(timestamp);
 487             }
 488
 489             moveBuckets(offset);
 490
 491             fLastBucket = fLastBucket + offset;
 492
 493             fFirstBucketTime = fFirstBucketTime - (offset * fBucketDuration);
 494             updateEndTime();
 495         }
 496
 497         // Increment the right bucket
 498         int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
 499         fBuckets[index]++;
 500         fNbEvents++;
 501         if (fLastBucket < index) {
 502             fLastBucket = index;
 503         }
 504
 505         fireModelUpdateNotification(eventCount);
 506     }
 507
 508     /**
 509      * Add lost event to the correct bucket, compacting the if needed.
 510      *
 511      * @param timeRange
 512      *            time range of a lost event
 513      * @param nbLostEvents
 514      *            the number of lost events
 515      * @param fullRange
 516      *            Full range or time range for histogram request
 517      * @since 2.2
 518      */
 519     public void countLostEvent(TmfTimeRange timeRange, long nbLostEvents, boolean fullRange) {
 520
 521         // Validate
 522         if (timeRange.getStartTime().getValue() < 0 || timeRange.getEndTime().getValue() < 0) {
 523             return;
 524         }
 525
 526         // Compact as needed
 527         if (fullRange) {
 528             while (timeRange.getEndTime().getValue() >= fTimeLimit) {
 529                 mergeBuckets();
 530             }
 531         }
 532
 533         int indexStart = (int) ((timeRange.getStartTime().getValue() - fFirstBucketTime) / fBucketDuration);
 534         int indexEnd = (int) ((timeRange.getEndTime().getValue() - fFirstBucketTime) / fBucketDuration);
 535         int nbBucketRange = (indexEnd - indexStart) + 1;
 536
 537         int lostEventPerBucket = (int) Math.ceil((double) nbLostEvents / nbBucketRange);
 538         long lastLostCol = Math.max(1, nbLostEvents - lostEventPerBucket * (nbBucketRange - 1));
 539
 540         // Increment the right bucket, bear in mind that ranges make it almost certain that some lost events are out of range
 541         for (int index = indexStart; index <= indexEnd && index < fLostEventsBuckets.length; index++) {
 542             if (index == (indexStart + nbBucketRange - 1)) {
 543                 fLostEventsBuckets[index] += lastLostCol;
 544             } else {
 545                 fLostEventsBuckets[index] += lostEventPerBucket;
 546             }
 547         }
 548
 549         fNbEvents++;
 550
 551         fireModelUpdateNotification(nbLostEvents);
 552     }
 553
 554     /**
 555      * Scale the model data to the width, height and bar width requested.
 556      *
 557      * @param width
 558      *            A width of the histogram canvas
 559      * @param height
 560      *            A height of the histogram canvas
 561      * @param barWidth
 562      *            A width (in pixel) of a histogram bar
 563      * @return the result array of size [width] and where the highest value
 564      *         doesn't exceed [height]
 565      *
 566      * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int,
 567      *      int, int)
 568      */
 569     @Override
 570     public HistogramScaledData scaleTo(int width, int height, int barWidth) {
 571         // Basic validation
 572         if ((width <= 0) || (height <= 0) || (barWidth <= 0))
 573         {
 574             throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 575         }
 576
 577         // The result structure
 578         HistogramScaledData result = new HistogramScaledData(width, height, barWidth);
 579
 580         // Scale horizontally
 581         result.fMaxValue = 0;
 582
 583         int nbBars = width / barWidth;
 584         int bucketsPerBar = (fLastBucket / nbBars) + 1;
 585         result.fBucketDuration = Math.max(bucketsPerBar * fBucketDuration, 1);
 586         for (int i = 0; i < nbBars; i++) {
 587             int count = 0;
 588             int countLostEvent = 0;
 589             for (int j = i * bucketsPerBar; j < ((i + 1) * bucketsPerBar); j++) {
 590                 if (fNbBuckets <= j) {
 591                     break;
 592                 }
 593                 count += fBuckets[j];
 594                 countLostEvent += fLostEventsBuckets[j];
 595             }
 596             result.fData[i] = count;
 597             result.fLostEventsData[i] = countLostEvent;
 598             result.fLastBucket = i;
 599             if (result.fMaxValue < count) {
 600                 result.fMaxValue = count;
 601             }
 602             if (result.fMaxCombinedValue < count + countLostEvent) {
 603                 result.fMaxCombinedValue = count + countLostEvent;
 604             }
 605         }
 606
 607         // Scale vertically
 608         if (result.fMaxValue > 0) {
 609             result.fScalingFactor = (double) height / result.fMaxValue;
 610         }
 611         if (result.fMaxCombinedValue > 0) {
 612             result.fScalingFactorCombined = (double) height / result.fMaxCombinedValue;
 613         }
 614
 615         fBucketDuration = Math.max(fBucketDuration, 1);
 616         // Set selection begin and end index in the scaled histogram
 617         result.fSelectionBeginBucket = (int) ((fSelectionBegin - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 618         result.fSelectionEndBucket = (int) ((fSelectionEnd - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 619
 620         result.fFirstBucketTime = fFirstBucketTime;
 621         result.fFirstEventTime = fFirstEventTime;
 622         return result;
 623     }
 624
 625     // ------------------------------------------------------------------------
 626     // Helper functions
 627     // ------------------------------------------------------------------------
 628
 629     private void updateEndTime() {
 630         fTimeLimit = fFirstBucketTime + (fNbBuckets * fBucketDuration);
 631     }
 632
 633     private void mergeBuckets() {
 634         for (int i = 0; i < (fNbBuckets / 2); i++) {
 635             fBuckets[i] = fBuckets[2 * i] + fBuckets[(2 * i) + 1];
 636             fLostEventsBuckets[i] = fLostEventsBuckets[2 * i] + fLostEventsBuckets[(2 * i) + 1];
 637         }
 638         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 639         Arrays.fill(fLostEventsBuckets, fNbBuckets / 2, fNbBuckets, 0);
 640         fBucketDuration *= 2;
 641         updateEndTime();
 642         fLastBucket = (fNbBuckets / 2) - 1;
 643     }
 644
 645     private void moveBuckets(int offset) {
 646         for (int i = fNbBuckets - 1; i >= offset; i--) {
 647             fBuckets[i] = fBuckets[i - offset];
 648             fLostEventsBuckets[i] = fLostEventsBuckets[i - offset];
 649         }
 650
 651         for (int i = 0; i < offset; i++) {
 652             fBuckets[i] = 0;
 653             fLostEventsBuckets[i] = 0;
 654         }
 655     }
 656
 657     private int getOffset(long timestamp) {
 658         int offset = (int) ((fFirstBucketTime - timestamp) / fBucketDuration);
 659         if (((fFirstBucketTime - timestamp) % fBucketDuration) != 0) {
 660             offset++;
 661         }
 662         return offset;
 663     }
 664 }