org.eclipse.linuxtools.statesystem.core/src/org/eclipse/linuxtools/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.linuxtools.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.linuxtools.statesystem.core.exceptions.AttributeNotFoundException;
  26 import org.eclipse.linuxtools.statesystem.core.exceptions.TimeRangeException;
  27 import org.eclipse.linuxtools.statesystem.core.interval.ITmfStateInterval;
  28 import org.eclipse.linuxtools.statesystem.core.interval.TmfStateInterval;
  29 import org.eclipse.linuxtools.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     @Override
 175     public boolean checkValidTime(long t) {
 176         if (t >= startTime && t <= latestTime) {
 177             return true;
 178         }
 179         return false;
 180     }
 181
 182     @Override
 183     public void finishedBuilding(long endTime) throws TimeRangeException {
 184         /* Nothing to do */
 185     }
 186
 187     @Override
 188     public FileInputStream supplyAttributeTreeReader() {
 189         /* Saving to disk not supported */
 190         return null;
 191     }
 192
 193     @Override
 194     public File supplyAttributeTreeWriterFile() {
 195         /* Saving to disk not supported */
 196         return null;
 197     }
 198
 199     @Override
 200     public long supplyAttributeTreeWriterFilePosition() {
 201         /* Saving to disk not supported */
 202         return -1;
 203     }
 204
 205     @Override
 206     public void removeFiles() {
 207         /* Nothing to do */
 208     }
 209
 210     @Override
 211     public void dispose() {
 212         /* Nothing to do */
 213     }
 214
 215     @Override
 216     public void debugPrint(PrintWriter writer) {
 217         synchronized (intervals) {
 218             writer.println(intervals.toString());
 219         }
 220     }
 221
 222     private static Iterator<ITmfStateInterval> serachforEndTime(TreeSet<ITmfStateInterval> tree, long time) {
 223         ITmfStateInterval dummyInterval = new TmfStateInterval(-1, time, -1, null);
 224         ITmfStateInterval myInterval = tree.lower(dummyInterval);
 225         if (myInterval == null) {
 226             return tree.iterator();
 227         }
 228         final SortedSet<ITmfStateInterval> tailSet = tree.tailSet(myInterval);
 229         Iterator<ITmfStateInterval> retVal = tailSet.iterator();
 230         retVal.next();
 231         return retVal;
 232     }
 233
 234 }