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 import java.util.ArrayList;
  19 import java.util.Collection;
  20 import java.util.Collections;
  21 import java.util.List;
  22 import java.util.ListIterator;
  23
  24 import org.eclipse.jdt.annotation.NonNull;
  25 import org.eclipse.tracecompass.ctf.core.trace.CTFReaderException;
  26
  27 /**
  28  * <b><u>StreamInputPacketIndex</u></b>
  29  * <p>
  30  * This is a data structure containing entries, you may append to this and read
  31  * it. It is not thread safe.
  32  */
  33 public class StreamInputPacketIndex {
  34
  35     // ------------------------------------------------------------------------
  36     // Attributes
  37     // ------------------------------------------------------------------------
  38
  39     /**
  40      * Entries of the index. They are sorted by increasing begin timestamp.
  41      * index builder.
  42      */
  43     private final List<StreamInputPacketIndexEntry> fEntries = new ArrayList<>();
  44
  45     // ------------------------------------------------------------------------
  46     // Operations
  47     // ------------------------------------------------------------------------
  48
  49     /**
  50      * Returns the number of elements in this data structure. If this data
  51      * structure contains more than {@code Integer.MAX_VALUE} elements, returns
  52      * {@code Integer.MAX_VALUE}.
  53      *
  54      * @return the number of elements in this data structure
  55      */
  56     public int size() {
  57         return fEntries.size();
  58     }
  59
  60     /**
  61      * Returns {@code true} if this data structure contains no elements.
  62      *
  63      * @return {@code true} if this data structure contains no elements
  64      */
  65     public boolean isEmpty() {
  66         return fEntries.isEmpty();
  67     }
  68
  69     /**
  70      * Adds a collection of entries to the index, the entries must be sorted.
  71      *
  72      * @param preParsedIndex
  73      *            the pre-parsed index file
  74      *
  75      * @throws CTFReaderException
  76      *             If there was a problem reading the entry
  77      */
  78     public void appendAll(Collection<StreamInputPacketIndexEntry> preParsedIndex)
  79             throws CTFReaderException {
  80         for (StreamInputPacketIndexEntry sipie : preParsedIndex) {
  81             append(checkNotNull(sipie));
  82         }
  83     }
  84
  85     /**
  86      * Appends the specified element to the end of this data structure
  87      *
  88      * @param entry
  89      *            element to be appended to this index, cannot be null
  90      * @return {@code true} (as specified by {@link Collection#add})
  91      * @throws CTFReaderException
  92      *             If there was a problem reading the entry
  93      */
  94     public boolean append(@NonNull StreamInputPacketIndexEntry entry)
  95             throws CTFReaderException {
  96
  97         /* Validate consistent entry. */
  98         if (entry.getTimestampBegin() > entry.getTimestampEnd()) {
  99             throw new CTFReaderException("Packet begin timestamp is after end timestamp"); //$NON-NLS-1$
 100         }
 101
 102         /*
 103          * Validate entries are inserted in monotonic increasing timestamp
 104          * order.
 105          */
 106         if (!fEntries.isEmpty() && (entry.getTimestampBegin() < lastElement().getTimestampBegin())) {
 107             throw new CTFReaderException("Packets begin timestamp decreasing"); //$NON-NLS-1$
 108         }
 109
 110         fEntries.add(entry);
 111         return true;
 112     }
 113
 114     /**
 115      * Returns the first PacketIndexEntry that could include the timestamp, that
 116      * is the last packet with a begin timestamp smaller than the given
 117      * timestamp.
 118      *
 119      * @param timestamp
 120      *            The timestamp to look for.
 121      * @return The StreamInputPacketEntry that corresponds to the packet that
 122      *         includes the given timestamp.
 123      */
 124     public ListIterator<StreamInputPacketIndexEntry> search(final long timestamp) {
 125         /*
 126          * Start with min and max covering all the elements.
 127          */
 128         int max = fEntries.size() - 1;
 129         int min = 0;
 130
 131         int guessI;
 132         StreamInputPacketIndexEntry guessEntry = null;
 133
 134         /*
 135          * If the index is empty, return the iterator at the very beginning.
 136          */
 137         if (isEmpty()) {
 138             return fEntries.listIterator();
 139         }
 140
 141         if (timestamp < 0) {
 142             throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$
 143         }
 144
 145         /* Binary search */
 146         for (;;) {
 147             /*
 148              * Guess in the middle of min and max.
 149              */
 150             guessI = min + ((max - min) / 2);
 151             guessEntry = fEntries.get(guessI);
 152
 153             /*
 154              * If we reached the point where we focus on a single packet, our
 155              * search is done.
 156              */
 157             if (min == max) {
 158                 break;
 159             }
 160
 161             if (timestamp <= guessEntry.getTimestampEnd()) {
 162                 /*
 163                  * If the timestamp is lower or equal to the end of the guess
 164                  * packet, then the guess packet becomes the new inclusive max.
 165                  */
 166                 max = guessI;
 167             } else {
 168                 /*
 169                  * If the timestamp is greater than the end of the guess packet,
 170                  * then the new inclusive min is the packet after the guess
 171                  * packet.
 172                  */
 173                 min = guessI + 1;
 174             }
 175         }
 176
 177         return fEntries.listIterator(guessI);
 178     }
 179
 180     /**
 181      * Get the last element of the index
 182      *
 183      * @return the last element in the index
 184      */
 185     public StreamInputPacketIndexEntry lastElement() {
 186         return fEntries.get(fEntries.size() - 1);
 187     }
 188
 189     /**
 190      * Returns the element at the specified position in this data structure.
 191      *
 192      * @param index
 193      *            index of the element to return
 194      * @return the element at the specified position in this data structure
 195      * @throws IndexOutOfBoundsException
 196      *             if the index is out of range (
 197      *             {@code index < 0 || index >= size()})
 198      */
 199     public StreamInputPacketIndexEntry getElement(int index) {
 200         return fEntries.get(index);
 201     }
 202
 203     /**
 204      * Returns the index of the first occurrence of the specified element in
 205      * this data structure, or -1 if this data structure does not contain the
 206      * element. More formally, returns the lowest index {@code i} such that, for
 207      * an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))},
 208      * or {@code -1} if there is no such index. This will work in log(n) time
 209      * since the data structure contains elements in a non-repeating increasing
 210      * manner.
 211      *
 212      * @param element
 213      *            element to search for
 214      * @return the index of the first occurrence of the specified element in
 215      *         this data structure, or -1 if this data structure does not
 216      *         contain the element
 217      * @throws ClassCastException
 218      *             if the type of the specified element is incompatible with
 219      *             this data structure (<a
 220      *             href="Collection.html#optional-restrictions">optional</a>)
 221      * @throws NullPointerException
 222      *             if the specified element is null and this data structure does
 223      *             not permit null elements (<a
 224      *             href="Collection.html#optional-restrictions">optional</a>)
 225      */
 226     public int indexOf(StreamInputPacketIndexEntry element) {
 227         int indexOf = -1;
 228         if (element != null) {
 229             indexOf = Collections.binarySearch(fEntries, element);
 230         }
 231         return (indexOf < 0) ? -1 : indexOf;
 232     }
 233
 234 }