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

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