org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/InMemoryBackend.java

   1 /*******************************************************************************
   2  * Copyright (c) 2013, 2015 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  *   Alexandre Montplaisir - Initial API and implementation
  11  *   Matthew Khouzam - Modified to use a TreeSet
  12  *   Patrick Tasse - Add message to exceptions
  13  ******************************************************************************/
  14
  15 package org.eclipse.tracecompass.internal.statesystem.core.backend;
  16
  17 import java.io.File;
  18 import java.io.FileInputStream;
  19 import java.io.PrintWriter;
  20 import java.util.Comparator;
  21 import java.util.Iterator;
  22 import java.util.List;
  23 import java.util.SortedSet;
  24 import java.util.TreeSet;
  25
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend;
  28 import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException;
  29 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  30 import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval;
  31 import org.eclipse.tracecompass.statesystem.core.interval.TmfStateInterval;
  32 import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue;
  33
  34 /**
  35  * State history back-end that stores its intervals in RAM only. It cannot be
  36  * saved to disk, which means we need to rebuild it every time we re-open a
  37  * trace. But it's relatively quick to build, so this shouldn't be a problem in
  38  * most cases.
  39  *
  40  * This should only be used with very small state histories (and/or, very small
  41  * traces). Since it's stored in standard Collections, it's limited to 2^31
  42  * intervals.
  43  *
  44  * @author Alexandre Montplaisir
  45  */
  46 public class InMemoryBackend implements IStateHistoryBackend {
  47
  48     /**
  49      * We need to compare the end time and the attribute, because we can have 2
  50      * intervals with the same end time (for different attributes). And TreeSet
  51      * needs a unique "key" per element.
  52      */
  53     private static final Comparator<ITmfStateInterval> END_COMPARATOR =
  54             new Comparator<ITmfStateInterval>() {
  55                 @Override
  56                 public int compare(ITmfStateInterval o1, ITmfStateInterval o2) {
  57                     final long e1 = o1.getEndTime();
  58                     final long e2 = o2.getEndTime();
  59                     final int a1 = o1.getAttribute();
  60                     final int a2 = o2.getAttribute();
  61                     if (e1 < e2) {
  62                         return -1;
  63                     } else if (e1 > e2) {
  64                         return 1;
  65                     } else if (a1 < a2) {
  66                         return -1;
  67                     } else if (a1 > a2) {
  68                         return 1;
  69                     } else {
  70                         return 0;
  71                     }
  72                 }
  73
  74             };
  75
  76     private final @NonNull String ssid;
  77     private final TreeSet<ITmfStateInterval> intervals;
  78     private final long startTime;
  79
  80     private volatile long latestTime;
  81
  82     /**
  83      * Constructor
  84      *
  85      * @param ssid
  86      *            The state system's ID
  87      * @param startTime
  88      *            The start time of this interval store
  89      */
  90     public InMemoryBackend(@NonNull String ssid, long startTime) {
  91         this.ssid = ssid;
  92         this.startTime = startTime;
  93         this.latestTime = startTime;
  94         this.intervals = new TreeSet<>(END_COMPARATOR);
  95     }
  96
  97     @Override
  98     public String getSSID() {
  99         return ssid;
 100     }
 101
 102     @Override
 103     public long getStartTime() {
 104         return startTime;
 105     }
 106
 107     @Override
 108     public long getEndTime() {
 109         return latestTime;
 110     }
 111
 112     @Override
 113     public void insertPastState(long stateStartTime, long stateEndTime,
 114             int quark, ITmfStateValue value) throws TimeRangeException {
 115         /* Make sure the passed start/end times make sense */
 116         if (stateStartTime > stateEndTime || stateStartTime < startTime) {
 117             throw new TimeRangeException(ssid + " Interval Start:" + stateStartTime + ", Interval End:" + stateEndTime + ", Backend Start:" + startTime); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 118         }
 119
 120         ITmfStateInterval interval = new TmfStateInterval(stateStartTime, stateEndTime, quark, value);
 121
 122         /* Add the interval into the tree */
 123         synchronized (intervals) {
 124             intervals.add(interval);
 125         }
 126
 127         /* Update the "latest seen time" */
 128         if (stateEndTime > latestTime) {
 129             latestTime = stateEndTime;
 130         }
 131     }
 132
 133     @Override
 134     public void doQuery(List<ITmfStateInterval> currentStateInfo, long t)
 135             throws TimeRangeException {
 136         if (!checkValidTime(t)) {
 137             throw new TimeRangeException(ssid + " Time:" + t + ", Start:" + startTime + ", End:" + latestTime); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 138         }
 139
 140         /*
 141          * The intervals are sorted by end time, so we can binary search to get
 142          * the first possible interval, then only compare their start times.
 143          */
 144         synchronized (intervals) {
 145             Iterator<ITmfStateInterval> iter = serachforEndTime(intervals, t);
 146             for (int modCount = 0; iter.hasNext() && modCount < currentStateInfo.size();) {
 147                 ITmfStateInterval entry = iter.next();
 148                 final long entryStartTime = entry.getStartTime();
 149                 if (entryStartTime <= t) {
 150                     /* Add this interval to the returned values */
 151                     currentStateInfo.set(entry.getAttribute(), entry);
 152                     modCount++;
 153                 }
 154             }
 155         }
 156     }
 157
 158     @Override
 159     public ITmfStateInterval doSingularQuery(long t, int attributeQuark)
 160             throws TimeRangeException, AttributeNotFoundException {
 161         if (!checkValidTime(t)) {
 162             throw new TimeRangeException(ssid + " Time:" + t + ", Start:" + startTime + ", End:" + latestTime); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 163         }
 164
 165         /*
 166          * The intervals are sorted by end time, so we can binary search to get
 167          * the first possible interval, then only compare their start times.
 168          */
 169         synchronized (intervals) {
 170             Iterator<ITmfStateInterval> iter = serachforEndTime(intervals, t);
 171             while (iter.hasNext()) {
 172                 ITmfStateInterval entry = iter.next();
 173                 final boolean attributeMatches = (entry.getAttribute() == attributeQuark);
 174                 final long entryStartTime = entry.getStartTime();
 175                 if (attributeMatches) {
 176                     if (entryStartTime <= t) {
 177                         /* This is the droid we are looking for */
 178                         return entry;
 179                     }
 180                 }
 181             }
 182         }
 183         throw new AttributeNotFoundException(ssid + " Quark:" + attributeQuark); //$NON-NLS-1$
 184     }
 185
 186     private boolean checkValidTime(long t) {
 187         if (t >= startTime && t <= latestTime) {
 188             return true;
 189         }
 190         return false;
 191     }
 192
 193     @Override
 194     public void finishedBuilding(long endTime) throws TimeRangeException {
 195         /* Nothing to do */
 196     }
 197
 198     @Override
 199     public FileInputStream supplyAttributeTreeReader() {
 200         /* Saving to disk not supported */
 201         return null;
 202     }
 203
 204     @Override
 205     public File supplyAttributeTreeWriterFile() {
 206         /* Saving to disk not supported */
 207         return null;
 208     }
 209
 210     @Override
 211     public long supplyAttributeTreeWriterFilePosition() {
 212         /* Saving to disk not supported */
 213         return -1;
 214     }
 215
 216     @Override
 217     public void removeFiles() {
 218         /* Nothing to do */
 219     }
 220
 221     @Override
 222     public void dispose() {
 223         /* Nothing to do */
 224     }
 225
 226     @Override
 227     public void debugPrint(PrintWriter writer) {
 228         synchronized (intervals) {
 229             writer.println(intervals.toString());
 230         }
 231     }
 232
 233     private static Iterator<ITmfStateInterval> serachforEndTime(TreeSet<ITmfStateInterval> tree, long time) {
 234         ITmfStateInterval dummyInterval = new TmfStateInterval(-1, time, -1, null);
 235         ITmfStateInterval myInterval = tree.lower(dummyInterval);
 236         if (myInterval == null) {
 237             return tree.iterator();
 238         }
 239         final SortedSet<ITmfStateInterval> tailSet = tree.tailSet(myInterval);
 240         Iterator<ITmfStateInterval> retVal = tailSet.iterator();
 241         retVal.next();
 242         return retVal;
 243     }
 244
 245 }