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

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