ctf: simplify search

The search now uses a java binary search instead of a house binary
search. This simplifies code a bit.

Change-Id: I9d9da2fff303f2492df502eeb856936ad94d5206
Signed-off-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-on: https://git.eclipse.org/r/46286
Reviewed-by: Hudson CI
Reviewed-by: Marc-Andre Laperle <marc-andre.laperle@ericsson.com>
Tested-by: Marc-Andre Laperle <marc-andre.laperle@ericsson.com>

diff --git a/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java b/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java
index f658075b529dabc9e8d8918d8aa0ebc18da98e1c..8faf38c45f58c256a0f4b16a9eb7c6100f0aa1ba 100644 (file)
--- a/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java
+++ b/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java
@@ -348,7 +348,7 @@ public class CTFStreamInputReader implements AutoCloseable {
      *             if an error occurs
      */
     private void gotoPacket(long timestamp) throws CTFException {
-        fPacketIndex = fStreamInput.getIndex().search(timestamp).previousIndex();
+        fPacketIndex = fStreamInput.getIndex().search(timestamp) - 1;
         /*
          * Switch to this packet.
          */

diff --git a/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java b/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java
index 85322216722f91dc50fe159e9fea2bb91b6e1b5a..34cd54acbcdd5198483b15681350fde79082152e 100644 (file)
--- a/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java
+++ b/ctf/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java
@@ -22,7 +22,6 @@ import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.List;
-import java.util.ListIterator;
 import java.util.TreeSet;
 
 import org.eclipse.jdt.annotation.NonNull;
@@ -117,69 +116,26 @@ public class StreamInputPacketIndex {
     }
 
     /**
-     * Returns the first PacketIndexEntry that could include the timestamp, that
-     * is the last packet with a begin timestamp smaller than the given
-     * timestamp.
+     * Returns the first packet that could include the timestamp, that is the
+     * last packet with a begin timestamp smaller than the given timestamp.
      *
      * @param timestamp
      *            The timestamp to look for.
-     * @return The StreamInputPacketEntry that corresponds to the packet that
-     *         includes the given timestamp.
+     * @return The index of the desired packet
      */
-    public ListIterator<ICTFPacketDescriptor> search(final long timestamp) {
-        /*
-         * Start with min and max covering all the elements.
-         */
-        int max = fEntries.size() - 1;
-        int min = 0;
-
-        int guessI;
-        ICTFPacketDescriptor guessEntry = null;
-
+    public int search(final long timestamp) {
         /*
-         * If the index is empty, return the iterator at the very beginning.
+         * Search using binary search.
+         *
+         * As the entries in fEntries are IndexEntries, the key to search for needs to be one too.
+         * We are looking for a timestamp though, so we use the dataOffset which is a long and use
+         * it as a timestamp holder.
          */
-        if (isEmpty()) {
-            return fEntries.listIterator();
-        }
-
-        if (timestamp < 0) {
-            throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$
-        }
-
-        /* Binary search */
-        for (;;) {
-            /*
-             * Guess in the middle of min and max.
-             */
-            guessI = min + ((max - min) / 2);
-            guessEntry = fEntries.get(guessI);
-
-            /*
-             * If we reached the point where we focus on a single packet, our
-             * search is done.
-             */
-            if (min == max) {
-                break;
-            }
-
-            if (timestamp <= guessEntry.getTimestampEnd()) {
-                /*
-                 * If the timestamp is lower or equal to the end of the guess
-                 * packet, then the guess packet becomes the new inclusive max.
-                 */
-                max = guessI;
-            } else {
-                /*
-                 * If the timestamp is greater than the end of the guess packet,
-                 * then the new inclusive min is the packet after the guess
-                 * packet.
-                 */
-                min = guessI + 1;
-            }
+        int index = Collections.binarySearch(fEntries, new StreamInputPacketIndexEntry(timestamp, 0), new FindTimestamp());
+        if (index < 0) {
+            index = -index - 1;
         }
-
-        return fEntries.listIterator(guessI);
+        return index;
     }
 
     /**
@@ -265,4 +221,33 @@ public class StreamInputPacketIndex {
         }
     }
 
+    /**
+     * Used for search, assumes that the second argument in the comparison is
+     * always the key
+     */
+    private static class FindTimestamp implements Comparator<ICTFPacketDescriptor>, Serializable {
+
+        /**
+         * UID
+         */
+        private static final long serialVersionUID = 7235997205945550341L;
+
+        @Override
+        public int compare(ICTFPacketDescriptor value, ICTFPacketDescriptor key) {
+            /*
+             * It is assumed that the second packet descriptor is the key, a wrapped timestamp in a
+             * PacketDescriptor. So we need to extract the timestamp. Then we have 3 choices, the
+             * if the timestamp is in the interval, we return 0 or found. If the timestamp is
+             * before or after, we just need to compare it to a value in the segment (like start) to
+             * know if it is greater or lesser to the current packet.
+             */
+            long ts = key.getOffsetBits();
+            if (value.includes(ts)) {
+                return 0;
+            }
+            return Long.compare(value.getTimestampBegin(), ts);
+        }
+
+    }
+
 }