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  */
  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 @NonNull String ssid;
  75     private final TreeSet<ITmfStateInterval> intervals;
  76     private final long startTime;
  77
  78     private volatile long latestTime;
  79
  80     /**
  81      * Constructor
  82      *
  83      * @param ssid
  84      *            The state system's ID
  85      * @param startTime
  86      *            The start time of this interval store
  87      */
  88     public InMemoryBackend(@NonNull String ssid, long startTime) {
  89         this.ssid = ssid;
  90         this.startTime = startTime;
  91         this.latestTime = startTime;
  92         this.intervals = new TreeSet<>(END_COMPARATOR);
  93     }
  94
  95     @Override
  96     public String getSSID() {
  97         return ssid;
  98     }
  99
 100     @Override
 101     public long getStartTime() {
 102         return startTime;
 103     }
 104
 105     @Override
 106     public long getEndTime() {
 107         return latestTime;
 108     }
 109
 110     @Override
 111     public void insertPastState(long stateStartTime, long stateEndTime,
 112             int quark, ITmfStateValue value) throws TimeRangeException {
 113         /* Make sure the passed start/end times make sense */
 114         if (stateStartTime > stateEndTime || stateStartTime < startTime) {
 115             throw new TimeRangeException();
 116         }
 117
 118         ITmfStateInterval interval = new TmfStateInterval(stateStartTime, stateEndTime, quark, value);
 119
 120         /* Add the interval into the tree */
 121         synchronized (intervals) {
 122             intervals.add(interval);
 123         }
 124
 125         /* Update the "latest seen time" */
 126         if (stateEndTime > latestTime) {
 127             latestTime = stateEndTime;
 128         }
 129     }
 130
 131     @Override
 132     public void doQuery(List<ITmfStateInterval> currentStateInfo, long t)
 133             throws TimeRangeException {
 134         if (!checkValidTime(t)) {
 135             throw new TimeRangeException();
 136         }
 137
 138         /*
 139          * The intervals are sorted by end time, so we can binary search to get
 140          * the first possible interval, then only compare their start times.
 141          */
 142         synchronized (intervals) {
 143             Iterator<ITmfStateInterval> iter = serachforEndTime(intervals, t);
 144             for (int modCount = 0; iter.hasNext() && modCount < currentStateInfo.size();) {
 145                 ITmfStateInterval entry = iter.next();
 146                 final long entryStartTime = entry.getStartTime();
 147                 if (entryStartTime <= t) {
 148                     /* Add this interval to the returned values */
 149                     currentStateInfo.set(entry.getAttribute(), entry);
 150                     modCount++;
 151                 }
 152             }
 153         }
 154     }
 155
 156     @Override
 157     public ITmfStateInterval doSingularQuery(long t, int attributeQuark)
 158             throws TimeRangeException, AttributeNotFoundException {
 159         if (!checkValidTime(t)) {
 160             throw new TimeRangeException();
 161         }
 162
 163         /*
 164          * The intervals are sorted by end time, so we can binary search to get
 165          * the first possible interval, then only compare their start times.
 166          */
 167         synchronized (intervals) {
 168             Iterator<ITmfStateInterval> iter = serachforEndTime(intervals, t);
 169             while (iter.hasNext()) {
 170                 ITmfStateInterval entry = iter.next();
 171                 final boolean attributeMatches = (entry.getAttribute() == attributeQuark);
 172                 final long entryStartTime = entry.getStartTime();
 173                 if (attributeMatches) {
 174                     if (entryStartTime <= t) {
 175                         /* This is the droid we are looking for */
 176                         return entry;
 177                     }
 178                 }
 179             }
 180         }
 181         throw new AttributeNotFoundException();
 182     }
 183
 184     private boolean checkValidTime(long t) {
 185         if (t >= startTime && t <= latestTime) {
 186             return true;
 187         }
 188         return false;
 189     }
 190
 191     @Override
 192     public void finishedBuilding(long endTime) throws TimeRangeException {
 193         /* Nothing to do */
 194     }
 195
 196     @Override
 197     public FileInputStream supplyAttributeTreeReader() {
 198         /* Saving to disk not supported */
 199         return null;
 200     }
 201
 202     @Override
 203     public File supplyAttributeTreeWriterFile() {
 204         /* Saving to disk not supported */
 205         return null;
 206     }
 207
 208     @Override
 209     public long supplyAttributeTreeWriterFilePosition() {
 210         /* Saving to disk not supported */
 211         return -1;
 212     }
 213
 214     @Override
 215     public void removeFiles() {
 216         /* Nothing to do */
 217     }
 218
 219     @Override
 220     public void dispose() {
 221         /* Nothing to do */
 222     }
 223
 224     @Override
 225     public void debugPrint(PrintWriter writer) {
 226         synchronized (intervals) {
 227             writer.println(intervals.toString());
 228         }
 229     }
 230
 231     private static Iterator<ITmfStateInterval> serachforEndTime(TreeSet<ITmfStateInterval> tree, long time) {
 232         ITmfStateInterval dummyInterval = new TmfStateInterval(-1, time, -1, null);
 233         ITmfStateInterval myInterval = tree.lower(dummyInterval);
 234         if (myInterval == null) {
 235             return tree.iterator();
 236         }
 237         final SortedSet<ITmfStateInterval> tailSet = tree.tailSet(myInterval);
 238         Iterator<ITmfStateInterval> retVal = tailSet.iterator();
 239         retVal.next();
 240         return retVal;
 241     }
 242
 243 }