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.ListIterator;
  26 import java.util.TreeSet;
  27
  28 import org.eclipse.jdt.annotation.NonNull;
  29 import org.eclipse.tracecompass.ctf.core.CTFException;
  30 import org.eclipse.tracecompass.ctf.core.trace.ICTFPacketDescriptor;
  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      * @throws CTFException
  81      *             If there was a problem reading the entry
  82      */
  83     public void appendAll(Collection<ICTFPacketDescriptor> preParsedIndex)
  84             throws CTFException {
  85         for (ICTFPacketDescriptor sipie : preParsedIndex) {
  86             append(checkNotNull(sipie));
  87         }
  88     }
  89
  90     /**
  91      * Appends the specified element to the end of this data structure
  92      *
  93      * @param entry
  94      *            element to be appended to this index, cannot be null
  95      * @return {@code true} (as specified by {@link Collection#add})
  96      * @throws CTFException
  97      *             If there was a problem reading the entry
  98      */
  99     public boolean append(@NonNull ICTFPacketDescriptor entry)
 100             throws CTFException {
 101
 102         /* Validate consistent entry. */
 103         if (entry.getTimestampBegin() > entry.getTimestampEnd()) {
 104             throw new CTFException("Packet begin timestamp is after end timestamp"); //$NON-NLS-1$
 105         }
 106
 107         /*
 108          * Validate entries are inserted in monotonic increasing timestamp
 109          * order.
 110          */
 111         if (!fEntries.isEmpty() && (entry.getTimestampBegin() < lastElement().getTimestampBegin())) {
 112             throw new CTFException("Packets begin timestamp decreasing"); //$NON-NLS-1$
 113         }
 114
 115         fEntries.add(entry);
 116         return true;
 117     }
 118
 119     /**
 120      * Returns the first PacketIndexEntry that could include the timestamp, that
 121      * is the last packet with a begin timestamp smaller than the given
 122      * timestamp.
 123      *
 124      * @param timestamp
 125      *            The timestamp to look for.
 126      * @return The StreamInputPacketEntry that corresponds to the packet that
 127      *         includes the given timestamp.
 128      */
 129     public ListIterator<ICTFPacketDescriptor> search(final long timestamp) {
 130         /*
 131          * Start with min and max covering all the elements.
 132          */
 133         int max = fEntries.size() - 1;
 134         int min = 0;
 135
 136         int guessI;
 137         ICTFPacketDescriptor guessEntry = null;
 138
 139         /*
 140          * If the index is empty, return the iterator at the very beginning.
 141          */
 142         if (isEmpty()) {
 143             return fEntries.listIterator();
 144         }
 145
 146         if (timestamp < 0) {
 147             throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$
 148         }
 149
 150         /* Binary search */
 151         for (;;) {
 152             /*
 153              * Guess in the middle of min and max.
 154              */
 155             guessI = min + ((max - min) / 2);
 156             guessEntry = fEntries.get(guessI);
 157
 158             /*
 159              * If we reached the point where we focus on a single packet, our
 160              * search is done.
 161              */
 162             if (min == max) {
 163                 break;
 164             }
 165
 166             if (timestamp <= guessEntry.getTimestampEnd()) {
 167                 /*
 168                  * If the timestamp is lower or equal to the end of the guess
 169                  * packet, then the guess packet becomes the new inclusive max.
 170                  */
 171                 max = guessI;
 172             } else {
 173                 /*
 174                  * If the timestamp is greater than the end of the guess packet,
 175                  * then the new inclusive min is the packet after the guess
 176                  * packet.
 177                  */
 178                 min = guessI + 1;
 179             }
 180         }
 181
 182         return fEntries.listIterator(guessI);
 183     }
 184
 185     /**
 186      * Get the last element of the index
 187      *
 188      * @return the last element in the index
 189      */
 190     public ICTFPacketDescriptor lastElement() {
 191         return fEntries.get(fEntries.size() - 1);
 192     }
 193
 194     /**
 195      * Returns the element at the specified position in this data structure.
 196      *
 197      * @param index
 198      *            index of the element to return
 199      * @return the element at the specified position in this data structure
 200      * @throws IndexOutOfBoundsException
 201      *             if the index is out of range (
 202      *             {@code index < 0 || index >= size()})
 203      */
 204     public ICTFPacketDescriptor getElement(int index) {
 205         return fEntries.get(index);
 206     }
 207
 208     /**
 209      * Returns the index of the first occurrence of the specified element in
 210      * this data structure, or -1 if this data structure does not contain the
 211      * element. More formally, returns the lowest index {@code i} such that, for
 212      * an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))},
 213      * or {@code -1} if there is no such index. This will work in log(n) time
 214      * since the data structure contains elements in a non-repeating increasing
 215      * manner.
 216      *
 217      * @param element
 218      *            element to search for
 219      * @return the index of the first occurrence of the specified element in
 220      *         this data structure, or -1 if this data structure does not
 221      *         contain the element
 222      * @throws ClassCastException
 223      *             if the type of the specified element is incompatible with
 224      *             this data structure (<a
 225      *             href="Collection.html#optional-restrictions">optional</a>)
 226      * @throws NullPointerException
 227      *             if the specified element is null and this data structure does
 228      *             not permit null elements (<a
 229      *             href="Collection.html#optional-restrictions">optional</a>)
 230      */
 231     public int indexOf(ICTFPacketDescriptor element) {
 232         int indexOf = -1;
 233         if (element != null) {
 234             indexOf = Collections.binarySearch(fEntries, element, new MonotonicComparator());
 235         }
 236         return (indexOf < 0) ? -1 : indexOf;
 237     }
 238
 239     /**
 240      * Ordering comparator for entering entries into a data structure sorted by
 241      * timestamp.
 242      */
 243     private static class MonotonicComparator implements Comparator<ICTFPacketDescriptor>, Serializable {
 244         /**
 245          * For {@link Serializable}, that way if we migrate to a {@link TreeSet}
 246          * the comparator is serializable too.
 247          */
 248         private static final long serialVersionUID = -5693064068367242076L;
 249
 250         @Override
 251         public int compare(ICTFPacketDescriptor left, ICTFPacketDescriptor right) {
 252             if (left.getTimestampBegin() > right.getTimestampBegin()) {
 253                 return 1;
 254             }
 255             if (left.getTimestampBegin() < right.getTimestampBegin()) {
 256                 return -1;
 257             }
 258             if (left.getTimestampEnd() > right.getTimestampEnd()) {
 259                 return 1;
 260             }
 261             if (left.getTimestampEnd() < right.getTimestampEnd()) {
 262                 return -1;
 263             }
 264             return 0;
 265         }
 266     }
 267
 268 }