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

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