package org.eclipse.tracecompass.ctf.core.tests.trace;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
import org.eclipse.tracecompass.ctf.core.CTFException;
+import org.eclipse.tracecompass.ctf.core.trace.ICTFPacketDescriptor;
import org.eclipse.tracecompass.internal.ctf.core.trace.StreamInputPacketIndex;
import org.eclipse.tracecompass.internal.ctf.core.trace.StreamInputPacketIndexEntry;
import org.junit.Before;
@SuppressWarnings("javadoc")
public class CTFStreamInputPacketIndexTest {
- private StreamInputPacketIndex fixture;
+ private StreamInputPacketIndex fFixture;
/**
* Perform pre-test initialization.
*/
@Before
public void setUp() {
- fixture = new StreamInputPacketIndex();
- fixture.append(new StreamInputPacketIndexEntry(1L,0L));
+ fFixture = new StreamInputPacketIndex();
+ }
+
+ @Test
+ public void testStreamInputPacketIndex() {
+ assertNotNull(fFixture);
+ assertTrue(fFixture.append(new StreamInputPacketIndexEntry(0, 1L)));
+ assertTrue(fFixture.append(new PacketStub(1, 0, 0)));
}
/**
* Run the StreamInputPacketIndex() constructor test.
*/
@Test
- public void testStreamInputPacketIndex() {
- assertNotNull(fixture);
- assertNotNull(fixture.getElement(0));
+ public void testStreamInputPacketIndexGet() {
+ assertNotNull(fFixture);
+ ICTFPacketDescriptor first = new StreamInputPacketIndexEntry(0, 1L);
+ ICTFPacketDescriptor second = new PacketStub(1, 0, 0);
+ assertTrue(fFixture.append(first));
+ assertTrue(fFixture.append(second));
+
+ assertEquals(first, fFixture.getElement(0));
+ assertEquals(second, fFixture.getElement(1));
+ }
+
+ /**
+ * Test on a contiguous set
+ */
+ @Test
+ public void testStreamInputPacketIndexContiguous() {
+ assertTrue(fFixture.append(new PacketStub(0, 0, 1)));
+ assertTrue(fFixture.append(new PacketStub(1, 2, 3)));
+ assertTrue(fFixture.append(new PacketStub(2, 4, 5)));
+ assertTrue(fFixture.append(new PacketStub(3, 6, 6)));
+
+ assertEquals(2, fFixture.search(5));
+ }
+
+ @Test
+ public void testStreamInputPacketIndexDisjoint() {
+ assertTrue(fFixture.append(new PacketStub(0, 0, 1)));
+ assertTrue(fFixture.append(new PacketStub(1, 2, 3)));
+ assertTrue(fFixture.append(new PacketStub(2, 6, 6)));
+
+ assertEquals(1, fFixture.search(5));
+ assertEquals(1, fFixture.search(3));
+ }
+
+ @Test
+ public void testStreamInputPacketIndexOverlapping() {
+ assertTrue(fFixture.append(new PacketStub(0, 0, 1)));
+ assertTrue(fFixture.append(new PacketStub(1, 2, 3)));
+ assertTrue(fFixture.append(new PacketStub(2, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(3, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(4, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(5, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(6, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(7, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(8, 6, 6)));
+ assertTrue(fFixture.append(new PacketStub(9, 6, 6)));
+
+ assertEquals(1, fFixture.search(5));
+ assertEquals(2, fFixture.search(6));
+ }
+
+ @Test
+ public void testStreamInputPacketIndexOverlappingBothSides() {
+ assertTrue(fFixture.append(new PacketStub(0, 0, 3)));
+ assertTrue(fFixture.append(new PacketStub(1, 0, 3)));
+ assertTrue(fFixture.append(new PacketStub(2, 0, 3)));
+ assertTrue(fFixture.append(new PacketStub(3, 7, 9)));
+ assertTrue(fFixture.append(new PacketStub(4, 7, 9)));
+ assertTrue(fFixture.append(new PacketStub(5, 7, 9)));
+ assertEquals(0, fFixture.search(3));
+ assertEquals(2, fFixture.search(6));
+ assertEquals(3, fFixture.search(8));
+ }
+
+ @Test
+ public void testStreamInputPacketIndexLargeOverlapping() {
+ assertTrue(fFixture.append(new PacketStub(0, Long.MIN_VALUE, Long.MAX_VALUE)));
+ assertTrue(fFixture.append(new PacketStub(1, Long.MIN_VALUE, Long.MAX_VALUE)));
+ assertTrue(fFixture.append(new PacketStub(2, Long.MIN_VALUE, Long.MAX_VALUE)));
+ assertTrue(fFixture.append(new PacketStub(3, Long.MIN_VALUE, Long.MAX_VALUE)));
+ assertTrue(fFixture.append(new PacketStub(4, Long.MIN_VALUE, Long.MAX_VALUE)));
+
+ assertEquals(0, fFixture.search(5));
+ assertEquals(0, fFixture.search(6));
+ }
+
+ @Test
+ public void testStreamInputPacketIndexInvalidAppend() {
+ fFixture = new StreamInputPacketIndex();
+ assertTrue(fFixture.append(new PacketStub(0, 0, -1)));
+ assertFalse(fFixture.append(new PacketStub(0, 0, 0)));
+ assertFalse(fFixture.append(new PacketStub(0, -1, 0)));
}
}
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2017 Ericsson
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.ctf.core.tests.trace;
+
+import java.util.Collections;
+import java.util.Map;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.ctf.core.trace.ICTFPacketDescriptor;
+
+/**
+ * Internal implementation to test packet index
+ *
+ * @author Matthew Khouzam
+ */
+class PacketStub implements ICTFPacketDescriptor {
+
+ private final long fOffsetBytes;
+ private final long fTsStart;
+ private final long fTsEnd;
+
+ public PacketStub(long offset, long start, long end) {
+ fOffsetBytes = offset;
+ fTsStart = start;
+ fTsEnd = end;
+ }
+
+ @Override
+ public boolean includes(long ts) {
+ return ts >= fTsStart && ts <= fTsEnd;
+ }
+
+ @Override
+ public long getOffsetBits() {
+ return fOffsetBytes * 8;
+ }
+
+ @Override
+ public long getPacketSizeBits() {
+ return 0;
+ }
+
+ @Override
+ public long getContentSizeBits() {
+ return 0;
+ }
+
+ @Override
+ public long getTimestampBegin() {
+ return fTsStart;
+ }
+
+ @Override
+ public long getTimestampEnd() {
+ return fTsEnd;
+ }
+
+ @Override
+ public long getLostEvents() {
+ return 0;
+ }
+
+ @Override
+ public @NonNull Map<String, Object> getAttributes() {
+ return Collections.emptyMap();
+ }
+
+ @Override
+ public String getTarget() {
+ return "";
+ }
+
+ @Override
+ public long getTargetId() {
+ return 0;
+ }
+
+ @Override
+ public long getOffsetBytes() {
+ return fOffsetBytes;
+ }
+
+ @Override
+ public long getPayloadStartBits() {
+ return 0;
+ }
+
+ @Override
+ public String toString() {
+ return "[" + fOffsetBytes + ", " + fTsStart + " - " + fTsEnd + "]";
+ }
+
+}
\ No newline at end of file
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
-import java.util.TreeSet;
import org.eclipse.core.runtime.IStatus;
import org.eclipse.jdt.annotation.NonNull;
/* Validate consistent entry. */
if (entryToAdd.getTimestampBegin() > entryToAdd.getTimestampEnd()) {
Activator.log(IStatus.WARNING, "Packet at offset " + entryToAdd.getOffsetBytes() + //$NON-NLS-1$
- " begin timestamp is after end timestamp"); //$NON-NLS-1$
+ " begin timestamp is after end timestamp"); //$NON-NLS-1$
entryToAdd = new StreamInputPacketIndexEntry(entryToAdd, Long.MAX_VALUE);
}
* Validate entries are inserted in monotonic increasing timestamp
* order.
*/
- if (!fEntries.isEmpty() && (entryToAdd.getTimestampBegin() < lastElement().getTimestampBegin())) {
+ if (!fEntries.isEmpty() &&
+ (entryToAdd.getTimestampBegin() < lastElement().getTimestampBegin() ||
+ entryToAdd.getOffsetBytes() <= lastElement().getOffsetBytes())) {
return false;
}
/**
* Returns the first packet that could include the timestamp, that is the
- * last packet with a begin timestamp smaller than the given timestamp.
+ * first packet that includes the given timestamp, or if none exist, first
+ * packet that begins before the given timestamp
*
* @param timestamp
* The timestamp to look for.
if (index < 0) {
index = -index - 1;
}
- return index;
+ if (index >= fEntries.size()) {
+ return fEntries.size() - 1;
+ }
+ for (int i = index; i > 0; i--) {
+ ICTFPacketDescriptor entry = fEntries.get(i);
+ ICTFPacketDescriptor nextEntry = fEntries.get(i - 1);
+ if (entry.getTimestampEnd() >= timestamp && nextEntry.getTimestampEnd() < timestamp) {
+ if (entry.getTimestampBegin() <= timestamp) {
+ return i;
+ }
+ return i - 1;
+ }
+ }
+ return 0;
+
}
/**
* this data structure, or -1 if this data structure does not contain the
* element. More formally, returns the lowest index {@code i} such that, for
* an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))},
- * or {@code -1} if there is no such index. This will work in log(n) time
- * since the data structure contains elements in a non-repeating increasing
- * manner.
+ * or {@code -1} if there is no such index. This will typically work in
+ * log(n) time since the data structure contains elements in a non-repeating
+ * increasing manner.
+ *
+ * Only the offset is checked in this case as there cannot be more than one
+ * packet with a given offset.
*
* @param element
* element to search for
public int indexOf(ICTFPacketDescriptor element) {
int indexOf = -1;
if (element != null) {
- indexOf = Collections.binarySearch(fEntries, element, new MonotonicComparator());
+ indexOf = Collections.binarySearch(fEntries, element, Comparator.comparingLong(ICTFPacketDescriptor::getOffsetBytes));
}
return (indexOf < 0) ? -1 : indexOf;
}
- /**
- * Ordering comparator for entering entries into a data structure sorted by
- * timestamp.
- */
- private static class MonotonicComparator implements Comparator<ICTFPacketDescriptor>, Serializable {
- /**
- * For {@link Serializable}, that way if we migrate to a {@link TreeSet}
- * the comparator is serializable too.
- */
- private static final long serialVersionUID = -5693064068367242076L;
-
- @Override
- public int compare(ICTFPacketDescriptor left, ICTFPacketDescriptor right) {
- if (left.getTimestampBegin() > right.getTimestampBegin()) {
- return 1;
- }
- if (left.getTimestampBegin() < right.getTimestampBegin()) {
- return -1;
- }
- if (left.getTimestampEnd() > right.getTimestampEnd()) {
- return 1;
- }
- if (left.getTimestampEnd() < right.getTimestampEnd()) {
- return -1;
- }
- return 0;
- }
- }
-
/**
* Used for search, assumes that the second argument in the comparison is
* always the key
projects / deliverable / tracecompass.git / commitdiff
