org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/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.linuxtools.internal.ctf.core.trace;
  16
  17 import java.util.ListIterator;
  18 import java.util.Vector;
  19
  20 import org.eclipse.linuxtools.ctf.core.trace.CTFReaderException;
  21
  22 /**
  23  * <b><u>StreamInputPacketIndex</u></b>
  24  * <p>
  25  * TODO Implement me. Please.
  26  */
  27 public class StreamInputPacketIndex {
  28
  29     // ------------------------------------------------------------------------
  30     // Attributes
  31     // ------------------------------------------------------------------------
  32
  33     /**
  34      * Entries of the index. They are sorted by increasing begin timestamp.
  35      * index builder.
  36      */
  37     private final Vector<StreamInputPacketIndexEntry> entries = new Vector<>();
  38
  39     // ------------------------------------------------------------------------
  40     // Getters/Setters/Predicates
  41     // ------------------------------------------------------------------------
  42
  43     /**
  44      * Gets the entries
  45      *
  46      * @return the entries
  47      */
  48     public Vector<StreamInputPacketIndexEntry> getEntries() {
  49         return this.entries;
  50     }
  51
  52     /**
  53      * Gets an iterator to the entries
  54      *
  55      * @return an iterator to the entries
  56      */
  57     public ListIterator<StreamInputPacketIndexEntry> listIterator() {
  58         return this.entries.listIterator();
  59     }
  60
  61     /**
  62      * Gets an iterator to the entries at a given position
  63      *
  64      * @param n
  65      *            the position to get
  66      * @return the iterator
  67      */
  68     public ListIterator<StreamInputPacketIndexEntry> listIterator(int n) {
  69         return this.entries.listIterator(n);
  70     }
  71
  72     // ------------------------------------------------------------------------
  73     // Operations
  74     // ------------------------------------------------------------------------
  75
  76     /**
  77      * Adds an entry to the index.
  78      *
  79      * @param entry
  80      *            The entry to add
  81      * @throws CTFReaderException
  82      *             If there was a problem reading the entry
  83      */
  84     public void addEntry(StreamInputPacketIndexEntry entry)
  85             throws CTFReaderException {
  86         assert (entry.getContentSizeBits() != 0);
  87
  88         /* Validate consistent entry. */
  89         if (entry.getTimestampBegin() > entry.getTimestampEnd()) {
  90             throw new CTFReaderException("Packet begin timestamp is after end timestamp"); //$NON-NLS-1$
  91         }
  92
  93         /* Validate entries are inserted in monotonic increasing timestamp order. */
  94         if (!this.entries.isEmpty()) {
  95             if (entry.getTimestampBegin() < this.entries.lastElement()
  96                     .getTimestampBegin()) {
  97                 throw new CTFReaderException("Packets begin timestamp decreasing"); //$NON-NLS-1$
  98             }
  99         }
 100         this.entries.add(entry);
 101     }
 102
 103     /**
 104      * Returns the first PacketIndexEntry that could include the timestamp,
 105      * that is the last packet with a begin timestamp smaller than the given timestamp.
 106      *
 107      * @param timestamp
 108      *            The timestamp to look for.
 109      * @return The StreamInputPacketEntry that corresponds to the packet that
 110      *         includes the given timestamp.
 111      */
 112     public ListIterator<StreamInputPacketIndexEntry> search(final long timestamp) {
 113         /*
 114          * Start with min and max covering all the elements.
 115          */
 116         int max = this.entries.size() - 1;
 117         int min = 0;
 118
 119         int guessI;
 120         StreamInputPacketIndexEntry guessEntry = null;
 121
 122         /*
 123          * If the index is empty, return the iterator at the very beginning.
 124          */
 125         if (this.getEntries().isEmpty()) {
 126             return this.getEntries().listIterator();
 127         }
 128
 129         if (timestamp < 0) {
 130             throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$
 131         }
 132
 133         /* Binary search */
 134         for (;;) {
 135             /*
 136              * Guess in the middle of min and max.
 137              */
 138             guessI = min + ((max - min) / 2);
 139             guessEntry = this.entries.get(guessI);
 140
 141             /*
 142              * If we reached the point where we focus on a single packet, our
 143              * search is done.
 144              */
 145             if (min == max) {
 146                 break;
 147             }
 148
 149             if (timestamp <= guessEntry.getTimestampEnd()) {
 150                 /*
 151                  * If the timestamp is lower or equal to the end of the guess packet,
 152                  * then the guess packet becomes the new inclusive max.
 153                  */
 154                 max = guessI;
 155             } else {
 156                 /*
 157                  * If the timestamp is greater than the end of the guess packet, then
 158                  * the new inclusive min is the packet after the guess packet.
 159                  */
 160                 min = guessI + 1;
 161             }
 162         }
 163
 164         return this.entries.listIterator(guessI);
 165     }
 166 }