ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java

   1 /*******************************************************************************
   2  * Copyright (c) 2011, 2014 Ericsson, Ecole Polytechnique de Montreal and others
   3  *
   4  * All rights reserved. This program and the accompanying materials are made
   5  * 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: Matthew Khouzam - Initial API and implementation
  10  * Contributors: Simon Marchi - Initial API and implementation
  11  * Contributors: Etienne Bergeron <etienne.bergeron@gmail.com>
  12  * Contributors: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  13  *******************************************************************************/
  14
  15 package org.eclipse.tracecompass.internal.ctf.core.trace;
  16
  17 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  18
  19 import java.io.Serializable;
  20 import java.util.ArrayList;
  21 import java.util.Collection;
  22 import java.util.Collections;
  23 import java.util.Comparator;
  24 import java.util.List;
  25 import java.util.TreeSet;
  26
  27 import org.eclipse.core.runtime.IStatus;
  28 import org.eclipse.jdt.annotation.NonNull;
  29 import org.eclipse.tracecompass.ctf.core.trace.ICTFPacketDescriptor;
  30 import org.eclipse.tracecompass.internal.ctf.core.Activator;
  31
  32 /**
  33  * <b><u>StreamInputPacketIndex</u></b>
  34  * <p>
  35  * This is a data structure containing entries, you may append to this and read
  36  * it. It is not thread safe.
  37  */
  38 public class StreamInputPacketIndex {
  39
  40     // ------------------------------------------------------------------------
  41     // Attributes
  42     // ------------------------------------------------------------------------
  43
  44     /**
  45      * Entries of the index. They are sorted by increasing begin timestamp.
  46      * index builder.
  47      */
  48     private final List<ICTFPacketDescriptor> fEntries = new ArrayList<>();
  49
  50     // ------------------------------------------------------------------------
  51     // Operations
  52     // ------------------------------------------------------------------------
  53
  54     /**
  55      * Returns the number of elements in this data structure. If this data
  56      * structure contains more than {@code Integer.MAX_VALUE} elements, returns
  57      * {@code Integer.MAX_VALUE}.
  58      *
  59      * @return the number of elements in this data structure
  60      */
  61     public int size() {
  62         return fEntries.size();
  63     }
  64
  65     /**
  66      * Returns {@code true} if this data structure contains no elements.
  67      *
  68      * @return {@code true} if this data structure contains no elements
  69      */
  70     public boolean isEmpty() {
  71         return fEntries.isEmpty();
  72     }
  73
  74     /**
  75      * Adds a collection of entries to the index, the entries must be sorted.
  76      *
  77      * @param preParsedIndex
  78      *            the pre-parsed index file
  79      */
  80     public void appendAll(Collection<ICTFPacketDescriptor> preParsedIndex) {
  81         for (ICTFPacketDescriptor sipie : preParsedIndex) {
  82             append(checkNotNull(sipie));
  83         }
  84     }
  85
  86     /**
  87      * Appends the specified element to the end of this data structure
  88      *
  89      * @param entry
  90      *            element to be appended to this index, cannot be null
  91      * @return {@code true} (as specified by {@link Collection#add})
  92      */
  93     public synchronized boolean append(@NonNull ICTFPacketDescriptor entry) {
  94         ICTFPacketDescriptor entryToAdd = entry;
  95         /* Validate consistent entry. */
  96         if (entryToAdd.getTimestampBegin() > entryToAdd.getTimestampEnd()) {
  97             Activator.log(IStatus.WARNING, "Packet at offset " + entryToAdd.getOffsetBytes() + //$NON-NLS-1$
  98                           " begin timestamp is after end timestamp"); //$NON-NLS-1$
  99             entryToAdd = new StreamInputPacketIndexEntry(entryToAdd, Long.MAX_VALUE);
 100         }
 101
 102         /*
 103          * Validate entries are inserted in monotonic increasing timestamp
 104          * order.
 105          */
 106         if (!fEntries.isEmpty() && (entryToAdd.getTimestampBegin() < lastElement().getTimestampBegin())) {
 107             return false;
 108         }
 109
 110         fEntries.add(entryToAdd);
 111         return true;
 112     }
 113
 114     /**
 115      * Returns the first packet that could include the timestamp, that is the
 116      * last packet with a begin timestamp smaller than the given timestamp.
 117      *
 118      * @param timestamp
 119      *            The timestamp to look for.
 120      * @return The index of the desired packet
 121      */
 122     public int search(final long timestamp) {
 123         /*
 124          * Search using binary search.
 125          *
 126          * As the entries in fEntries are IndexEntries, the key to search for
 127          * needs to be one too. We are looking for a timestamp though, so we use
 128          * the dataOffset which is a long and use it as a timestamp holder.
 129          */
 130         int index = Collections.binarySearch(fEntries, new StreamInputPacketIndexEntry(timestamp, 0), new FindTimestamp());
 131         if (index < 0) {
 132             index = -index - 1;
 133         }
 134         return index;
 135     }
 136
 137     /**
 138      * Get the last element of the index
 139      *
 140      * @return the last element in the index
 141      */
 142     public ICTFPacketDescriptor lastElement() {
 143         return fEntries.get(fEntries.size() - 1);
 144     }
 145
 146     /**
 147      * Returns the element at the specified position in this data structure.
 148      *
 149      * @param index
 150      *            index of the element to return
 151      * @return the element at the specified position in this data structure
 152      * @throws IndexOutOfBoundsException
 153      *             if the index is out of range (
 154      *             {@code index < 0 || index >= size()})
 155      */
 156     public ICTFPacketDescriptor getElement(int index) {
 157         return fEntries.get(index);
 158     }
 159
 160     /**
 161      * Returns the index of the first occurrence of the specified element in
 162      * this data structure, or -1 if this data structure does not contain the
 163      * element. More formally, returns the lowest index {@code i} such that, for
 164      * an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))},
 165      * or {@code -1} if there is no such index. This will work in log(n) time
 166      * since the data structure contains elements in a non-repeating increasing
 167      * manner.
 168      *
 169      * @param element
 170      *            element to search for
 171      * @return the index of the first occurrence of the specified element in
 172      *         this data structure, or -1 if this data structure does not
 173      *         contain the element
 174      * @throws ClassCastException
 175      *             if the type of the specified element is incompatible with
 176      *             this data structure (
 177      *             <a href="Collection.html#optional-restrictions">optional</a>)
 178      * @throws NullPointerException
 179      *             if the specified element is null and this data structure does
 180      *             not permit null elements (
 181      *             <a href="Collection.html#optional-restrictions">optional</a>)
 182      */
 183     public int indexOf(ICTFPacketDescriptor element) {
 184         int indexOf = -1;
 185         if (element != null) {
 186             indexOf = Collections.binarySearch(fEntries, element, new MonotonicComparator());
 187         }
 188         return (indexOf < 0) ? -1 : indexOf;
 189     }
 190
 191     /**
 192      * Ordering comparator for entering entries into a data structure sorted by
 193      * timestamp.
 194      */
 195     private static class MonotonicComparator implements Comparator<ICTFPacketDescriptor>, Serializable {
 196         /**
 197          * For {@link Serializable}, that way if we migrate to a {@link TreeSet}
 198          * the comparator is serializable too.
 199          */
 200         private static final long serialVersionUID = -5693064068367242076L;
 201
 202         @Override
 203         public int compare(ICTFPacketDescriptor left, ICTFPacketDescriptor right) {
 204             if (left.getTimestampBegin() > right.getTimestampBegin()) {
 205                 return 1;
 206             }
 207             if (left.getTimestampBegin() < right.getTimestampBegin()) {
 208                 return -1;
 209             }
 210             if (left.getTimestampEnd() > right.getTimestampEnd()) {
 211                 return 1;
 212             }
 213             if (left.getTimestampEnd() < right.getTimestampEnd()) {
 214                 return -1;
 215             }
 216             return 0;
 217         }
 218     }
 219
 220     /**
 221      * Used for search, assumes that the second argument in the comparison is
 222      * always the key
 223      */
 224     private static class FindTimestamp implements Comparator<ICTFPacketDescriptor>, Serializable {
 225
 226         /**
 227          * UID
 228          */
 229         private static final long serialVersionUID = 7235997205945550341L;
 230
 231         @Override
 232         public int compare(ICTFPacketDescriptor value, ICTFPacketDescriptor key) {
 233             /*
 234              * It is assumed that the second packet descriptor is the key, a
 235              * wrapped timestamp in a PacketDescriptor. So we need to extract
 236              * the timestamp. Then we have 3 choices, the if the timestamp is in
 237              * the interval, we return 0 or found. If the timestamp is before or
 238              * after, we just need to compare it to a value in the segment (like
 239              * start) to know if it is greater or lesser to the current packet.
 240              */
 241             long ts = key.getOffsetBits();
 242             if (value.includes(ts)) {
 243                 return 0;
 244             }
 245             return Long.compare(value.getTimestampBegin(), ts);
 246         }
 247
 248     }
 249
 250 }