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