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