</attributes>
</classpathentry>
<classpathentry kind="src" path="src"/>
- <classpathentry kind="src" path="perf"/>
<classpathentry kind="output" path="bin"/>
</classpath>
Export-Package: org.eclipse.tracecompass.analysis.timing.core.tests,
org.eclipse.tracecompass.analysis.timing.core.tests.callgraph,
org.eclipse.tracecompass.analysis.timing.core.tests.flamegraph,
- org.eclipse.tracecompass.analysis.timing.core.tests.segmentstore.statistics,
- org.eclipse.tracecompass.analysis.timing.core.tests.store
+ org.eclipse.tracecompass.analysis.timing.core.tests.segmentstore.statistics
Bundle-Activator: org.eclipse.tracecompass.analysis.timing.core.tests.Activator
# http://www.eclipse.org/legal/epl-v10.html
###############################################################################
-source.. = src/,\
- perf/
+source.. = src/
output.. = bin/
bin.includes = META-INF/,\
.,\
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2016 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.analysis.timing.core.tests.store;
-
-import static org.junit.Assert.assertNotNull;
-
-import java.util.Random;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.ArrayListStore;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.LazyArrayListStore;
-import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-import org.eclipse.tracecompass.segmentstore.core.treemap.TreeMapStore;
-import org.junit.FixMethodOrder;
-import org.junit.Test;
-import org.junit.runners.MethodSorters;
-
-/**
- * Segmentstore benchmarks, tests the performance for loads and reads.
- *
- * NOTE : Do not add this to isTracecompassFastYet, it is not information that
- * is interesting for users, it is for developpers.
- *
- * @category benchmark
- *
- * @author Matthew Khouzam
- *
- */
-@FixMethodOrder(MethodSorters.NAME_ASCENDING)
-public class SegmentStoreBenchmark {
-
- private ISegmentStore<@NonNull ISegment> fALS = new ArrayListStore<>();
- private ISegmentStore<@NonNull ISegment> fLALS = new LazyArrayListStore<>();
- private ISegmentStore<@NonNull ISegment> fTMS = new TreeMapStore<>();
-
- /**
- * Add elements in order
- */
- @Test
- public void test1AddInOrder() {
- int size = 1;
- int[] fuzz = { 0 };
- run(size, fuzz, new Object() {
- }.getClass().getEnclosingMethod().getName());
- }
-
- /**
- * Add elements almost in order, this represents a typical degenerate use
- * case.
- */
- @Test
- public void test2AddFuzzyOrder() {
- int size = 1000;
- int[] fuzz = new int[size];
- Random rng = new Random(10);
- for (int i = 0; i < size; i++) {
- fuzz[i] = rng.nextInt(1000);
- }
- String name = new Object() {
- }.getClass().getEnclosingMethod().getName();
- assertNotNull(name);
- run(size, fuzz, name);
- }
-
- /**
- * Add elements almost in order, this represents a typical degenerate use
- * case, then iterate over the list.
- */
- @Test
- public void test3AddFuzzyOrderThenIterate() {
- int size = 1000;
- int[] fuzz = new int[size];
- Random rng = new Random(10);
- for (int i = 0; i < size; i++) {
- fuzz[i] = rng.nextInt(1000);
- }
- String name = new Object() {
- }.getClass().getEnclosingMethod().getName();
- assertNotNull(name);
- runIterate(size, fuzz, name);
- }
-
- /**
- * Add elements almost in order, this represents a typical degenerate use
- * case, and iterate while building then when done.
- */
- @Test
- public void test4AddFuzzyOrderThenIterateThenAddThenIterate() {
- int size = 1000;
- int[] fuzz = new int[size];
- Random rng = new Random(10);
- for (int i = 0; i < size; i++) {
- fuzz[i] = rng.nextInt(1000);
- }
- String name = new Object() {
- }.getClass().getEnclosingMethod().getName();
- assertNotNull(name);
- runIterateAddIterate(size, fuzz, name);
- }
-
- /**
- * Test adding elements in a random order, this is an atypical degenerate
- * use case.
- */
- @Test
- public void test5AddRandomOrder() {
- int size = 1000;
- int[] fuzz = new int[size];
- Random rng = new Random(10);
- for (int i = 0; i < size; i++) {
- fuzz[i] = rng.nextInt();
- }
- String name = new Object() {
- }.getClass().getEnclosingMethod().getName();
- assertNotNull(name);
- runIterate(size, fuzz, name);
- }
-
- /**
- * Test adding elements in a random order then iterate over the list, this
- * is an atypical degenerate use case.
- */
- @Test
- public void test6AddRandomOrderThenIterate() {
- int size = 1000;
- int[] fuzz = new int[size];
- Random rng = new Random(10);
- for (int i = 0; i < size; i++) {
- fuzz[i] = rng.nextInt();
- }
- String name = new Object() {
- }.getClass().getEnclosingMethod().getName();
- assertNotNull(name);
- runIterate(size, fuzz, name);
- }
-
- /**
- * Test adding elements in a random order then iterate over the list then
- * add more then iterate again, this is an atypical degenerate use case.
- */
- @Test
- public void test7AddRandomOrderThenIterateThenAddThenIterate() {
- int size = 1000;
- int[] fuzz = new int[size];
- Random rng = new Random(10);
- for (int i = 0; i < size; i++) {
- fuzz[i] = rng.nextInt(1000);
- }
- String name = new Object() {
- }.getClass().getEnclosingMethod().getName();
- assertNotNull(name);
- runIterateAddIterate(size, fuzz, name);
- }
-
- private void run(int size, int[] fuzz, String method) {
- long durationA = populate(size, fuzz, fALS);
- long durationL = populate(size, fuzz, fLALS);
- long durationT = populate(size, fuzz, fTMS);
- outputResults(durationA, durationL, durationT, method);
- }
-
- private static long populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
- store.clear();
- long start = System.nanoTime();
- populate(size, fuzz, store, 1000000);
- long end = System.nanoTime();
- return end - start;
- }
-
- private void runIterate(int size, int[] fuzz, String method) {
- long durationA = addAndIterate(size, fuzz, fALS);
- long durationL = addAndIterate(size, fuzz, fLALS);
- long durationT = addAndIterate(size, fuzz, fTMS);
-
- outputResults(durationA, durationL, durationT, method);
- }
-
- private static long addAndIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
- long start = System.nanoTime();
- populate(size, fuzz, store);
- iterate(store);
- long end = System.nanoTime();
- return end - start;
- }
-
- private void runIterateAddIterate(int size, int[] fuzz, String method) {
- long durationA = runIterateAddIterate(size, fuzz, fALS);
- long durationL = runIterateAddIterate(size, fuzz, fLALS);
- long durationT = runIterateAddIterate(size, fuzz, fTMS);
- outputResults(durationA, durationL, durationT, method);
- }
-
- private static long runIterateAddIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
- store.clear();
- long start = System.nanoTime();
- for (int i = 0; i < 50000; i++) {
- long startTime = i + fuzz[i % size];
- store.add(new BasicSegment(startTime, startTime + 10));
- }
- iterate(store);
- for (int i = 50000; i < 100000; i++) {
- long startTime = i + fuzz[i % size];
- store.add(new BasicSegment(startTime, startTime + 10));
- }
- iterate(store);
- long end = System.nanoTime();
- return end - start;
- }
-
- private static Object iterate(ISegmentStore<@NonNull ISegment> store) {
- Object shutupCompilerWarnings = null;
- for (ISegment elem : store) {
- shutupCompilerWarnings = elem;
- }
- return shutupCompilerWarnings;
- }
-
- private static void populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store, int count) {
- for (int i = 0; i < count; i++) {
- int start = i + fuzz[i % size];
- store.add(new BasicSegment(start, start + 10));
- }
- }
-
- private static void outputResults(long durationA, long durationL, long durationT, String method) {
- System.out.println("Time taken for test " + method + "\n ArrayList " + String.format("%12d", durationA) + "\n LazyArrayList " + String.format("%12d", durationL) + "\n TreeMapStore " + String.format("%12d", durationT));
- }
-}
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2016 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.analysis.timing.core.tests.store;
-
-import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertTrue;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collection;
-import java.util.Iterator;
-import java.util.List;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-import org.junit.After;
-import org.junit.Before;
-import org.junit.Test;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
-
-/**
- * Unit tests for intersecting elements in an SegmentStore
- *
- * Originally the TreeMapStoreTest, copied for this internal implementation. The
- * test was barely changed as it tests the interface and not the internals.
- *
- * @author Matthew Khouzam
- */
-public abstract class AbstractTestSegmentStore {
-
- private ISegmentStore<@NonNull ISegment> fSegmentStore;
-
- /**
- * Get the segment store to test
- *
- * @return the segment store
- */
- protected abstract ISegmentStore<@NonNull ISegment> getSegmentStore();
-
- private static final @NonNull ISegment SEGMENT_2_6 = new BasicSegment(2, 6);
- private static final @NonNull ISegment SEGMENT_4_6 = new BasicSegment(4, 6);
- private static final @NonNull ISegment SEGMENT_4_8 = new BasicSegment(4, 8);
- private static final @NonNull ISegment SEGMENT_6_8 = new BasicSegment(6, 8);
- private static final @NonNull ISegment SEGMENT_10_14 = new BasicSegment(10, 14);
- private static final @NonNull List<@NonNull ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14);
- private static final List<@NonNull ISegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS);
-
- /**
- * Constructor
- */
- public AbstractTestSegmentStore() {
- super();
- }
-
- /**
- * Initialize data (test vector) that will be tested
- */
- @Before
- public void setup() {
- fSegmentStore = getSegmentStore();
- for (ISegment segment : SEGMENTS) {
- fSegmentStore.add(segment);
- }
- }
-
- /**
- * Dispose of the segment store
- */
- @After
- public void teardown() {
- fSegmentStore.dispose();
- }
-
- /**
- * Testing method size()
- */
- @Test
- public void testSize() {
- assertEquals(SEGMENTS.size(), fSegmentStore.size());
- }
-
- /**
- * Test the contains() method.
- */
- @Test
- public void testContains() {
- ISegment otherSegment = new BasicSegment(0, 20);
-
- assertTrue(fSegmentStore.contains(SEGMENT_2_6));
- assertTrue(fSegmentStore.contains(SEGMENT_4_8));
- assertFalse(fSegmentStore.contains(otherSegment));
- }
-
- /**
- * Test the toArray() method.
- */
- @Test
- public void testToObjectArray() {
- Object[] array = fSegmentStore.toArray();
-
- assertEquals(SEGMENTS.size(), array.length);
- assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
- }
-
- /**
- * Test the toArray(T[]) method.
- */
- @Test
- public void testToSpecificArray() {
- ISegment[] array = fSegmentStore.toArray(new ISegment[0]);
-
- assertEquals(SEGMENTS.size(), array.length);
- assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
- }
-
- /**
- * Test the toArray(T[]) method with a subtype of ISegment.
- */
- @Test
- public void testToSpecifyArraySubtype() {
- ISegmentStore<@NonNull ISegment> tms2 = getSegmentStore();
- BasicSegment otherSegment = new BasicSegment(2, 6);
- tms2.add(otherSegment);
- BasicSegment[] array = tms2.toArray(new BasicSegment[0]);
-
- assertEquals(1, array.length);
- assertTrue(Arrays.asList(array).contains(otherSegment));
-
- tms2.dispose();
- }
-
- /**
- * Test the iteration order of the complete segment store.
- */
- @Test
- public void testIterationOrder() {
- int i = 0;
- for (ISegment segment : fSegmentStore) {
- assertEquals(SEGMENTS.get(i++), segment);
- }
- }
-
- /**
- * Test the iteration order when the elements are not inserted in sorted
- * order.
- */
- @Test
- public void testIterationOrderNonSortedInsertion() {
- /* Prepare the segment store, we don't use the 'fixture' in this test */
- ISegmentStore<@NonNull ISegment> store = getSegmentStore();
- for (ISegment segment : REVERSE_SEGMENTS) {
- store.add(checkNotNull(segment));
- }
-
- /*
- * Test each element one by one, the iteration order should follow the
- * start times, not the insertion order.
- */
- int i = 0;
- for (ISegment segment : store) {
- assertEquals(SEGMENTS.get(i++), segment);
- }
-
- /* Manually dispose our own store */
- store.dispose();
- }
-
- /**
- * Testing method
- * {@link ISegmentStore#getIntersectingElements(long start, long end)}
- */
- @Test
- public void testGetIntersectingElementsRange() {
-
- Iterable<ISegment> intersectingElements;
-
- /*
- * Range that does not include any segment
- */
- intersectingElements = fSegmentStore.getIntersectingElements(16, 20);
- assertEquals(0, Iterables.size(intersectingElements));
-
- /*
- * Range start time : Before first segment start time Range end time :
- * After last segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(1, 15);
- assertEquals(5, Iterables.size(intersectingElements));
-
- /*
- * Range start time : On first segment start time Range end time : On
- * last segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(2, 14);
- assertEquals(5, Iterables.size(intersectingElements));
-
- /*
- * Range start time : After one segment start time Range end time :
- * Before one segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(11, 13);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Range start time : On one segment start time Range end time : On one
- * segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(10, 14);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Range start time : On last segment end time Range end time : After
- * last segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(14, 18);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Range start time : Before first segment start time Range end time :
- * On first segment start time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(1, 2);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
- }
-
- /**
- * Testing method {@link ISegmentStore#getIntersectingElements(long time)}
- */
- @Test
- public void testGetIntersectingElementsTime() {
-
- Iterable<ISegment> intersectingElements;
-
- /*
- * Time between segment start time and end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(3);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Time on segment start time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(2);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Time on segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(14);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Time overlapping many segments
- */
- intersectingElements = fSegmentStore.getIntersectingElements(6);
- assertEquals(4, Iterables.size(intersectingElements));
-
- /*
- * Time between segments
- */
- intersectingElements = fSegmentStore.getIntersectingElements(9);
- assertEquals(0, Iterables.size(intersectingElements));
-
- /*
- * Time before all segment start time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(1);
- assertEquals(0, Iterables.size(intersectingElements));
-
- /*
- * Time after all segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(15);
- assertEquals(0, Iterables.size(intersectingElements));
- }
-
- /**
- * Testing method {@link ISegmentStore#dispose()}
- */
- @Test
- public void testDispose() {
- ISegmentStore<@NonNull ISegment> store = getSegmentStore();
- store.add(SEGMENT_2_6);
- store.dispose();
- assertEquals(0, store.size());
- }
-
- /**
- * Test iterating over a store being built.
- *
- * bug 500607
- */
- @Test
- public void testIterator() {
- Collection<@NonNull ISegment> beforeExpected = ImmutableList.of(SEGMENT_2_6);
- Collection<@NonNull ISegment> afterExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8);
- Collection<@NonNull ISegment> lastExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8, SEGMENT_6_8);
- Collection<@NonNull ISegment> fixture = new ArrayList<>();
- ISegmentStore<@NonNull ISegment> store = getSegmentStore();
-
- // Add one segment to the segment store and iterate
- store.add(SEGMENT_2_6);
- for (ISegment item : store) {
- fixture.add(item);
- }
- assertEquals(beforeExpected, fixture);
-
- // Add a second segment to the store and iterate
- fixture.clear();
- store.add(SEGMENT_4_8);
- for (ISegment item : store) {
- fixture.add(item);
- }
- assertEquals(afterExpected, fixture);
-
- fixture.clear();
- // Take an iterator
- Iterator<@NonNull ISegment> iter = store.iterator();
-
- // Add a third segment to the store and iterate
- store.add(SEGMENT_6_8);
- Iterator<@NonNull ISegment> iter2 = store.iterator();
- fixture.clear();
-
- // Make sure the first iterator take has only 2 elements and the second
- // has 3 elements
- while (iter.hasNext()) {
- fixture.add(iter.next());
- }
- assertEquals(afterExpected, fixture);
- fixture.clear();
- while (iter2.hasNext()) {
- fixture.add(iter2.next());
- }
- assertEquals(lastExpected, fixture);
- }
-
-}
\ No newline at end of file
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2016 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.analysis.timing.core.tests.store;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.ArrayListStore;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-
-/**
- * Unit tests for intersecting elements in an ArrayListStore
- *
- * @author France Lapointe Nguyen
- * @author Matthew Khouzam
- */
-public class ArrayListStoreTest extends AbstractTestSegmentStore {
-
- @Override
- protected ISegmentStore<@NonNull ISegment> getSegmentStore() {
- return new ArrayListStore<>();
- }
-}
\ No newline at end of file
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2016 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.analysis.timing.core.tests.store;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.LazyArrayListStore;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-
-/**
- * Unit tests for intersecting elements in an LazyArrayListStore
- *
- * @author Matthew Khouzam
- */
-public class LazyArrayListStoreTest extends AbstractTestSegmentStore {
-
- @Override
- protected ISegmentStore<@NonNull ISegment> getSegmentStore() {
- return new LazyArrayListStore<>();
- }
-}
\ No newline at end of file
Export-Package: org.eclipse.tracecompass.analysis.timing.core.segmentstore,
org.eclipse.tracecompass.analysis.timing.core.segmentstore.statistics,
org.eclipse.tracecompass.internal.analysis.timing.core,
- org.eclipse.tracecompass.internal.analysis.timing.core.callgraph;x-friends:="org.eclipse.tracecompass.analysis.timing.ui,org.eclipse.tracecompass.analysis.timing.core.tests",
- org.eclipse.tracecompass.internal.analysis.timing.core.store;x-friends:="org.eclipse.tracecompass.analysis.timing.core.tests,org.eclipse.tracecompass.tmf.analysis.xml.core"
+ org.eclipse.tracecompass.internal.analysis.timing.core.callgraph;x-friends:="org.eclipse.tracecompass.analysis.timing.ui,org.eclipse.tracecompass.analysis.timing.core.tests"
Import-Package: com.google.common.annotations;version="15.0.0",
com.google.common.collect,
com.google.common.hash
import org.eclipse.core.runtime.ListenerList;
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.common.core.NonNullUtils;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.ArrayListStore;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory;
import org.eclipse.tracecompass.tmf.core.analysis.TmfAbstractAnalysisModule;
import org.eclipse.tracecompass.tmf.core.exceptions.TmfAnalysisException;
import org.eclipse.tracecompass.tmf.core.segment.ISegmentAspect;
/* Attempt to read the existing file */
try (ObjectInputStream ois = new ObjectInputStream(Files.newInputStream(file))) {
Object[] segmentArray = readObject(ois);
- ISegmentStore<ISegment> store = new ArrayListStore<>(NonNullUtils.checkNotNullContents(segmentArray));
+ ISegmentStore<ISegment> store = SegmentStoreFactory.createSegmentStore(NonNullUtils.checkNotNullContents(segmentArray));
fSegmentStore = store;
sendUpdate(store);
return true;
}
}
- ISegmentStore<ISegment> segmentStore = new ArrayListStore<>();
+ ISegmentStore<ISegment> segmentStore = SegmentStoreFactory.createSegmentStore();
boolean completed = buildAnalysisSegments(segmentStore, monitor);
if (!completed) {
return false;
import org.eclipse.tracecompass.analysis.timing.core.segmentstore.ISegmentStoreProvider;
import org.eclipse.tracecompass.common.core.StreamUtils;
import org.eclipse.tracecompass.internal.analysis.timing.core.Activator;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.LazyArrayListStore;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory.SegmentStoreType;
import org.eclipse.tracecompass.statesystem.core.ITmfStateSystem;
import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException;
import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException;
/**
* Segment store
*/
- private final ISegmentStore<@NonNull ISegment> fStore = new LazyArrayListStore<>();
+ private final ISegmentStore<@NonNull ISegment> fStore;
/**
* Listeners
*/
public CallGraphAnalysis() {
super();
+ fStore = SegmentStoreFactory.createSegmentStore(SegmentStoreType.Fast);
}
@Override
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2016 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.internal.analysis.timing.core.store;
-
-import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.List;
-import java.util.concurrent.locks.ReadWriteLock;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
-import java.util.stream.Collectors;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.jdt.annotation.Nullable;
-import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * Implementation of an {@link ISegmentStore} using one in-memory
- * {@link ArrayList}. This relatively simple implementation holds everything in
- * memory, and as such cannot contain too much data.
- *
- * The ArrayListStore itself is {@link Iterable}, and its iteration order will
- * be by ascending order of start times. For segments with identical start
- * times, the secondary comparator will be the end time. If even those are
- * equal, it will defer to the segments' natural ordering (
- * {@link ISegment#compareTo}).
- *
- * The store's tree maps will not accept duplicate key-value pairs, which means
- * that if you want several segments with the same start and end times, make
- * sure their compareTo() differentiates them.
- *
- * Removal operations are not supported.
- *
- * @param <E>
- * The type of segment held in this store
- *
- * @author Matthew Khouzam
- */
-public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
-
- private final Comparator<E> COMPARATOR = (o1, o2) -> {
- int ret = Long.compare(o1.getStart(), o2.getStart());
- if (ret == 0) {
- return Long.compare(o1.getEnd(), o2.getEnd());
- }
- return ret;
- };
-
- private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
-
- private final List<E> fStore;
-
- private @Nullable transient Iterable<E> fLastSnapshot = null;
-
- /**
- * Constructor
- */
- public ArrayListStore() {
- fStore = new ArrayList<>();
- }
-
- /**
- * Constructor
- *
- * @param array
- * an array of elements to wrap in the segment store
- *
- */
- public ArrayListStore(Object[] array) {
- fStore = new ArrayList<>();
- for (int i = 0; i < array.length; i++) {
- if (array[i] instanceof ISegment) {
- fStore.add((E) array[i]);
- }
- }
- fStore.sort(COMPARATOR);
- }
- // ------------------------------------------------------------------------
- // Methods from Collection
- // ------------------------------------------------------------------------
-
- @Override
- public Iterator<E> iterator() {
- fLock.readLock().lock();
- try {
- Iterable<E> lastSnapshot = fLastSnapshot;
- if (lastSnapshot == null) {
- lastSnapshot = ImmutableList.copyOf(fStore);
- fLastSnapshot = lastSnapshot;
- }
- return checkNotNull(lastSnapshot.iterator());
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean add(@Nullable E val) {
- if (val == null) {
- throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$
- }
-
- fLock.writeLock().lock();
- try {
- int insertPoint = Collections.binarySearch(fStore, val);
- insertPoint = insertPoint >= 0 ? insertPoint : -insertPoint - 1;
- fStore.add(insertPoint, val);
- fLastSnapshot = null;
- return true;
- } finally {
- fLock.writeLock().unlock();
- }
- }
-
- @Override
- public int size() {
- return fStore.size();
- }
-
- @Override
- public boolean isEmpty() {
- fLock.readLock().lock();
- try {
- return fStore.isEmpty();
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean contains(@Nullable Object o) {
- fLock.readLock().lock();
- try {
- return fStore.contains(o);
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean containsAll(@Nullable Collection<?> c) {
- fLock.readLock().lock();
- try {
- return fStore.containsAll(c);
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public Object[] toArray() {
- fLock.readLock().lock();
- try {
- return fStore.toArray();
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public <T> T[] toArray(T[] a) {
- fLock.readLock().lock();
- try {
- return fStore.toArray(a);
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean remove(@Nullable Object o) {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public boolean addAll(@Nullable Collection<? extends E> c) {
- if (c == null) {
- throw new IllegalArgumentException();
- }
-
- fLock.writeLock().lock();
- try {
- boolean changed = false;
- for (E elem : c) {
- if (this.add(elem)) {
- changed = true;
- }
- }
- return changed;
- } finally {
- fLock.writeLock().unlock();
- }
- }
-
- @Override
- public boolean removeAll(@Nullable Collection<?> c) {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public boolean retainAll(@Nullable Collection<?> c) {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public void clear() {
- fLock.writeLock().lock();
- try {
- fStore.clear();
- } finally {
- fLock.writeLock().unlock();
- }
- }
-
- // ------------------------------------------------------------------------
- // Methods added by ISegmentStore
- // ------------------------------------------------------------------------
-
- @Override
- public Iterable<E> getIntersectingElements(long position) {
- /*
- * The intervals intersecting 't' are those whose 1) start time is
- * *lower* than 't' AND 2) end time is *higher* than 't'.
- */
- fLock.readLock().lock();
- try {
- /*
- * as fStore is sorted by start then end times, restrict sub array
- * to elements whose start times <= t as stream.filter won't do it.
- */
- int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
- index = (index >= 0) ? index : -index - 1;
- return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public Iterable<E> getIntersectingElements(long start, long end) {
- fLock.readLock().lock();
- try {
- int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
- index = (index >= 0) ? index : -index - 1;
- return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public void dispose() {
- fLock.writeLock().lock();
- try {
- fStore.clear();
- } finally {
- fLock.writeLock().unlock();
- }
- }
-}
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2016 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.internal.analysis.timing.core.store;
-
-import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.List;
-import java.util.concurrent.locks.ReentrantLock;
-import java.util.stream.Collectors;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.jdt.annotation.Nullable;
-import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * Implementation of an {@link ISegmentStore} using one in-memory
- * {@link ArrayList}. This relatively simple implementation holds everything in
- * memory, and as such cannot contain too much data.
- *
- * The LazyArrayListStore itself is {@link Iterable}, and its iteration order
- * will be by ascending order of start times. For segments with identical start
- * times, the secondary comparator will be the end time. If even those are
- * equal, it will defer to the segments' natural ordering (
- * {@link ISegment#compareTo}).
- *
- * This structure sorts in a lazy way to allow faster insertions. However, if
- * the structure is out of order, the next read (getting intersecting elements,
- * iterating...) will perform a sort. It may have inconsistent performance, but
- * should be faster at building when receiving shuffled datasets than the
- * {@link ArrayListStore}.
- *
- * Removal operations are not supported.
- *
- * @param <E>
- * The type of segment held in this store
- *
- * @author Matthew Khouzam
- */
-public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
-
- private static final String ERROR_MESSAGE = "Cannot remove from a segment store"; //$NON-NLS-1$
-
- private final Comparator<E> COMPARATOR = (o1, o2) -> {
- int ret = Long.compare(o1.getStart(), o2.getStart());
- if (ret == 0) {
- return Long.compare(o1.getEnd(), o2.getEnd());
- }
- return ret;
- };
-
- private final ReentrantLock fLock = new ReentrantLock(false);
-
- private final @NonNull List<E> fStore = new ArrayList<>();
-
- private @Nullable transient Iterable<E> fLastSnapshot = null;
-
- private volatile boolean fDirty = false;
-
- /**
- * Constructor
- */
- public LazyArrayListStore() {
- // do nothing
- }
-
- /**
- * Constructor
- *
- * @param array
- * an array of elements to wrap in the segment store
- *
- */
- public LazyArrayListStore(Object[] array) {
- for (int i = 0; i < array.length; i++) {
- if (array[i] instanceof ISegment) {
- E element = (E) array[i];
- setDirtyIfNeeded(element);
- fStore.add(element);
- }
- }
- if (fDirty) {
- sortStore();
- }
- }
-
- private void setDirtyIfNeeded(@NonNull E value) {
- if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) {
- fDirty = true;
- }
- }
- // ------------------------------------------------------------------------
- // Methods from Collection
- // ------------------------------------------------------------------------
-
- @Override
- public Iterator<E> iterator() {
- fLock.lock();
- try {
- if (fDirty) {
- sortStore();
- }
- Iterable<E> lastSnapshot = fLastSnapshot;
- if (lastSnapshot == null) {
- lastSnapshot = ImmutableList.copyOf(fStore);
- fLastSnapshot = lastSnapshot;
- }
- return checkNotNull(lastSnapshot.iterator());
- } finally {
- fLock.unlock();
- }
- }
-
- /**
- * DO NOT CALL FROM OUTSIDE OF A LOCK!
- */
- private void sortStore() {
- fStore.sort(COMPARATOR);
- fDirty = false;
- }
-
- @Override
- public boolean add(@Nullable E val) {
- if (val == null) {
- throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$
- }
-
- fLock.lock();
- try {
- setDirtyIfNeeded(val);
- fStore.add(val);
- fLastSnapshot = null;
- return true;
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public int size() {
- return fStore.size();
- }
-
- @Override
- public boolean isEmpty() {
- fLock.lock();
- try {
- return fStore.isEmpty();
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public boolean contains(@Nullable Object o) {
- fLock.lock();
- try {
- return fStore.contains(o);
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public boolean containsAll(@Nullable Collection<?> c) {
- fLock.lock();
- try {
- return fStore.containsAll(c);
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public Object[] toArray() {
- fLock.lock();
- try {
- if (fDirty) {
- sortStore();
- }
- return fStore.toArray();
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public <T> T[] toArray(T[] a) {
- fLock.lock();
- try {
- if (fDirty) {
- sortStore();
- }
- return fStore.toArray(a);
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public boolean addAll(@Nullable Collection<? extends E> c) {
- if (c == null) {
- throw new IllegalArgumentException();
- }
-
- fLock.lock();
- try {
- boolean changed = false;
- for (E elem : c) {
- if (add(elem)) {
- changed = true;
- }
- }
- return changed;
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public boolean removeAll(@Nullable Collection<?> c) {
- throw new UnsupportedOperationException(ERROR_MESSAGE);
- }
-
- @Override
- public boolean retainAll(@Nullable Collection<?> c) {
- throw new UnsupportedOperationException(ERROR_MESSAGE);
- }
-
- @Override
- public boolean remove(@Nullable Object o) {
- throw new UnsupportedOperationException(ERROR_MESSAGE);
- }
-
- @Override
- public void clear() {
- fLock.lock();
- try {
- fStore.clear();
- fLastSnapshot = null;
- fDirty = false;
- } finally {
- fLock.unlock();
- }
- }
-
- // ------------------------------------------------------------------------
- // Methods added by ISegmentStore
- // ------------------------------------------------------------------------
-
- @Override
- public Iterable<E> getIntersectingElements(long position) {
- fLock.lock();
- if (fDirty) {
- sortStore();
- }
- /*
- * The intervals intersecting 't' are those whose 1) start time is
- * *lower* than 't' AND 2) end time is *higher* than 't'.
- */
- try {
- /*
- * as fStore is sorted by start then end times, restrict sub array
- * to elements whose start times <= t as stream.filter won't do it.
- */
- int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
- index = (index >= 0) ? index : -index - 1;
- return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public Iterable<E> getIntersectingElements(long start, long end) {
- fLock.lock();
- if (fDirty) {
- sortStore();
- }
- try {
- int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
- index = (index >= 0) ? index : -index - 1;
- return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
- } finally {
- fLock.unlock();
- }
- }
-
- @Override
- public void dispose() {
- fLock.lock();
- try {
- fStore.clear();
- fDirty = false;
- } finally {
- fLock.unlock();
- }
- }
-}
</attributes>
</classpathentry>
<classpathentry kind="src" path="src"/>
+ <classpathentry kind="src" path="perf"/>
<classpathentry kind="output" path="bin"/>
</classpath>
org.eclipse.core.resources,
org.eclipse.tracecompass.common.core,
org.eclipse.tracecompass.segmentstore.core
-Export-Package: org.eclipse.tracecompass.segmentstore.core.tests.treemap;x-internal:=true
Import-Package: com.google.common.collect
# Alexandre Montplaisir - Initial API and implementation
###############################################################################
-source.. = src/
+source.. = src/,\
+ perf/
output.. = bin/
bin.includes = META-INF/,\
.,\
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.analysis.timing.core.tests.store;
+
+import static org.junit.Assert.assertNotNull;
+
+import java.util.Random;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.ArrayListStore;
+import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.LazyArrayListStore;
+import org.eclipse.tracecompass.internal.segmentstore.core.treemap.TreeMapStore;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.junit.FixMethodOrder;
+import org.junit.Test;
+import org.junit.runners.MethodSorters;
+
+/**
+ * Segmentstore benchmarks, tests the performance for loads and reads.
+ *
+ * NOTE : Do not add this to isTracecompassFastYet, it is not information that
+ * is interesting for users, it is for developpers.
+ *
+ * @category benchmark
+ *
+ * @author Matthew Khouzam
+ *
+ */
+@FixMethodOrder(MethodSorters.NAME_ASCENDING)
+public class SegmentStoreBenchmark {
+
+ private ISegmentStore<@NonNull ISegment> fALS = new ArrayListStore<>();
+ private ISegmentStore<@NonNull ISegment> fLALS = new LazyArrayListStore<>();
+ private ISegmentStore<@NonNull ISegment> fTMS = new TreeMapStore<>();
+
+ /**
+ * Add elements in order
+ */
+ @Test
+ public void test1AddInOrder() {
+ int size = 1;
+ int[] fuzz = { 0 };
+ run(size, fuzz, new Object() {
+ }.getClass().getEnclosingMethod().getName());
+ }
+
+ /**
+ * Add elements almost in order, this represents a typical degenerate use
+ * case.
+ */
+ @Test
+ public void test2AddFuzzyOrder() {
+ int size = 1000;
+ int[] fuzz = new int[size];
+ Random rng = new Random(10);
+ for (int i = 0; i < size; i++) {
+ fuzz[i] = rng.nextInt(1000);
+ }
+ String name = new Object() {
+ }.getClass().getEnclosingMethod().getName();
+ assertNotNull(name);
+ run(size, fuzz, name);
+ }
+
+ /**
+ * Add elements almost in order, this represents a typical degenerate use
+ * case, then iterate over the list.
+ */
+ @Test
+ public void test3AddFuzzyOrderThenIterate() {
+ int size = 1000;
+ int[] fuzz = new int[size];
+ Random rng = new Random(10);
+ for (int i = 0; i < size; i++) {
+ fuzz[i] = rng.nextInt(1000);
+ }
+ String name = new Object() {
+ }.getClass().getEnclosingMethod().getName();
+ assertNotNull(name);
+ runIterate(size, fuzz, name);
+ }
+
+ /**
+ * Add elements almost in order, this represents a typical degenerate use
+ * case, and iterate while building then when done.
+ */
+ @Test
+ public void test4AddFuzzyOrderThenIterateThenAddThenIterate() {
+ int size = 1000;
+ int[] fuzz = new int[size];
+ Random rng = new Random(10);
+ for (int i = 0; i < size; i++) {
+ fuzz[i] = rng.nextInt(1000);
+ }
+ String name = new Object() {
+ }.getClass().getEnclosingMethod().getName();
+ assertNotNull(name);
+ runIterateAddIterate(size, fuzz, name);
+ }
+
+ /**
+ * Test adding elements in a random order, this is an atypical degenerate
+ * use case.
+ */
+ @Test
+ public void test5AddRandomOrder() {
+ int size = 1000;
+ int[] fuzz = new int[size];
+ Random rng = new Random(10);
+ for (int i = 0; i < size; i++) {
+ fuzz[i] = rng.nextInt();
+ }
+ String name = new Object() {
+ }.getClass().getEnclosingMethod().getName();
+ assertNotNull(name);
+ runIterate(size, fuzz, name);
+ }
+
+ /**
+ * Test adding elements in a random order then iterate over the list, this
+ * is an atypical degenerate use case.
+ */
+ @Test
+ public void test6AddRandomOrderThenIterate() {
+ int size = 1000;
+ int[] fuzz = new int[size];
+ Random rng = new Random(10);
+ for (int i = 0; i < size; i++) {
+ fuzz[i] = rng.nextInt();
+ }
+ String name = new Object() {
+ }.getClass().getEnclosingMethod().getName();
+ assertNotNull(name);
+ runIterate(size, fuzz, name);
+ }
+
+ /**
+ * Test adding elements in a random order then iterate over the list then
+ * add more then iterate again, this is an atypical degenerate use case.
+ */
+ @Test
+ public void test7AddRandomOrderThenIterateThenAddThenIterate() {
+ int size = 1000;
+ int[] fuzz = new int[size];
+ Random rng = new Random(10);
+ for (int i = 0; i < size; i++) {
+ fuzz[i] = rng.nextInt(1000);
+ }
+ String name = new Object() {
+ }.getClass().getEnclosingMethod().getName();
+ assertNotNull(name);
+ runIterateAddIterate(size, fuzz, name);
+ }
+
+ private void run(int size, int[] fuzz, String method) {
+ long durationA = populate(size, fuzz, fALS);
+ long durationL = populate(size, fuzz, fLALS);
+ long durationT = populate(size, fuzz, fTMS);
+ outputResults(durationA, durationL, durationT, method);
+ }
+
+ private static long populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
+ store.clear();
+ long start = System.nanoTime();
+ populate(size, fuzz, store, 1000000);
+ long end = System.nanoTime();
+ return end - start;
+ }
+
+ private void runIterate(int size, int[] fuzz, String method) {
+ long durationA = addAndIterate(size, fuzz, fALS);
+ long durationL = addAndIterate(size, fuzz, fLALS);
+ long durationT = addAndIterate(size, fuzz, fTMS);
+
+ outputResults(durationA, durationL, durationT, method);
+ }
+
+ private static long addAndIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
+ long start = System.nanoTime();
+ populate(size, fuzz, store);
+ iterate(store);
+ long end = System.nanoTime();
+ return end - start;
+ }
+
+ private void runIterateAddIterate(int size, int[] fuzz, String method) {
+ long durationA = runIterateAddIterate(size, fuzz, fALS);
+ long durationL = runIterateAddIterate(size, fuzz, fLALS);
+ long durationT = runIterateAddIterate(size, fuzz, fTMS);
+ outputResults(durationA, durationL, durationT, method);
+ }
+
+ private static long runIterateAddIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
+ store.clear();
+ long start = System.nanoTime();
+ for (int i = 0; i < 50000; i++) {
+ long startTime = i + fuzz[i % size];
+ store.add(new BasicSegment(startTime, startTime + 10));
+ }
+ iterate(store);
+ for (int i = 50000; i < 100000; i++) {
+ long startTime = i + fuzz[i % size];
+ store.add(new BasicSegment(startTime, startTime + 10));
+ }
+ iterate(store);
+ long end = System.nanoTime();
+ return end - start;
+ }
+
+ private static Object iterate(ISegmentStore<@NonNull ISegment> store) {
+ Object shutupCompilerWarnings = null;
+ for (ISegment elem : store) {
+ shutupCompilerWarnings = elem;
+ }
+ return shutupCompilerWarnings;
+ }
+
+ private static void populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store, int count) {
+ for (int i = 0; i < count; i++) {
+ int start = i + fuzz[i % size];
+ store.add(new BasicSegment(start, start + 10));
+ }
+ }
+
+ private static void outputResults(long durationA, long durationL, long durationT, String method) {
+ System.out.println("Time taken for test " + method + "\n ArrayList " + String.format("%12d", durationA) + "\n LazyArrayList " + String.format("%12d", durationL) + "\n TreeMapStore " + String.format("%12d", durationT));
+ }
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.segmentstore.core.tests;
+
+import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+
+/**
+ * Unit tests for intersecting elements in an SegmentStore
+ *
+ * Originally the TreeMapStoreTest, copied for this internal implementation. The
+ * test was barely changed as it tests the interface and not the internals.
+ *
+ * @author Matthew Khouzam
+ */
+public abstract class AbstractTestSegmentStore {
+
+ /**
+ * The segment store
+ */
+ protected ISegmentStore<@NonNull ISegment> fSegmentStore;
+
+ /**
+ * Get the segment store to test
+ *
+ * @return the segment store
+ */
+ protected abstract ISegmentStore<@NonNull ISegment> getSegmentStore();
+
+ private static final @NonNull ISegment SEGMENT_2_6 = new BasicSegment(2, 6);
+ private static final @NonNull ISegment SEGMENT_4_6 = new BasicSegment(4, 6);
+ private static final @NonNull ISegment SEGMENT_4_8 = new BasicSegment(4, 8);
+ private static final @NonNull ISegment SEGMENT_6_8 = new BasicSegment(6, 8);
+ private static final @NonNull ISegment SEGMENT_10_14 = new BasicSegment(10, 14);
+ /**
+ * A sample segment list
+ */
+ protected static final List<@NonNull ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14);
+ private static final List<@NonNull ISegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS);
+
+ /**
+ * Constructor
+ */
+ public AbstractTestSegmentStore() {
+ super();
+ }
+
+ /**
+ * Initialize data (test vector) that will be tested
+ */
+ @Before
+ public void setup() {
+ fSegmentStore = getSegmentStore();
+ for (ISegment segment : SEGMENTS) {
+ fSegmentStore.add(segment);
+ }
+ }
+
+ /**
+ * Dispose of the segment store
+ */
+ @After
+ public void teardown() {
+ fSegmentStore.dispose();
+ }
+
+ /**
+ * Testing method size()
+ */
+ @Test
+ public void testSize() {
+ assertEquals(SEGMENTS.size(), fSegmentStore.size());
+ }
+
+ /**
+ * Test the contains() method.
+ */
+ @Test
+ public void testContains() {
+ ISegment otherSegment = new BasicSegment(0, 20);
+
+ assertTrue(fSegmentStore.contains(SEGMENT_2_6));
+ assertTrue(fSegmentStore.contains(SEGMENT_4_8));
+ assertFalse(fSegmentStore.contains(otherSegment));
+ }
+
+ /**
+ * Test the toArray() method.
+ */
+ @Test
+ public void testToObjectArray() {
+ Object[] array = fSegmentStore.toArray();
+
+ assertEquals(SEGMENTS.size(), array.length);
+ assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
+ }
+
+ /**
+ * Test the toArray(T[]) method.
+ */
+ @Test
+ public void testToSpecificArray() {
+ ISegment[] array = fSegmentStore.toArray(new ISegment[0]);
+
+ assertEquals(SEGMENTS.size(), array.length);
+ assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
+ }
+
+ /**
+ * Test the toArray(T[]) method with a subtype of ISegment.
+ */
+ @Test
+ public void testToSpecifyArraySubtype() {
+ ISegmentStore<@NonNull ISegment> tms2 = getSegmentStore();
+ BasicSegment otherSegment = new BasicSegment(2, 6);
+ tms2.add(otherSegment);
+ BasicSegment[] array = tms2.toArray(new BasicSegment[0]);
+
+ assertEquals(1, array.length);
+ assertTrue(Arrays.asList(array).contains(otherSegment));
+
+ tms2.dispose();
+ }
+
+ /**
+ * Test the iteration order of the complete segment store.
+ */
+ @Test
+ public void testIterationOrder() {
+ int i = 0;
+ for (ISegment segment : fSegmentStore) {
+ assertEquals(SEGMENTS.get(i++), segment);
+ }
+ }
+
+ /**
+ * Test the iteration order when the elements are not inserted in sorted
+ * order.
+ */
+ @Test
+ public void testIterationOrderNonSortedInsertion() {
+ /* Prepare the segment store, we don't use the 'fixture' in this test */
+ ISegmentStore<@NonNull ISegment> store = getSegmentStore();
+ for (ISegment segment : REVERSE_SEGMENTS) {
+ store.add(checkNotNull(segment));
+ }
+
+ /*
+ * Test each element one by one, the iteration order should follow the
+ * start times, not the insertion order.
+ */
+ int i = 0;
+ for (ISegment segment : store) {
+ assertEquals(SEGMENTS.get(i++), segment);
+ }
+
+ /* Manually dispose our own store */
+ store.dispose();
+ }
+
+ /**
+ * Testing method
+ * {@link ISegmentStore#getIntersectingElements(long start, long end)}
+ */
+ @Test
+ public void testGetIntersectingElementsRange() {
+
+ Iterable<ISegment> intersectingElements;
+
+ /*
+ * Range that does not include any segment
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(16, 20);
+ assertEquals(0, Iterables.size(intersectingElements));
+
+ /*
+ * Range start time : Before first segment start time Range end time :
+ * After last segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(1, 15);
+ assertEquals(5, Iterables.size(intersectingElements));
+
+ /*
+ * Range start time : On first segment start time Range end time : On
+ * last segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(2, 14);
+ assertEquals(5, Iterables.size(intersectingElements));
+
+ /*
+ * Range start time : After one segment start time Range end time :
+ * Before one segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(11, 13);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Range start time : On one segment start time Range end time : On one
+ * segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(10, 14);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Range start time : On last segment end time Range end time : After
+ * last segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(14, 18);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Range start time : Before first segment start time Range end time :
+ * On first segment start time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(1, 2);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
+ }
+
+ /**
+ * Testing method {@link ISegmentStore#getIntersectingElements(long time)}
+ */
+ @Test
+ public void testGetIntersectingElementsTime() {
+
+ Iterable<ISegment> intersectingElements;
+
+ /*
+ * Time between segment start time and end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(3);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Time on segment start time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(2);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Time on segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(14);
+ assertEquals(1, Iterables.size(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Time overlapping many segments
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(6);
+ assertEquals(4, Iterables.size(intersectingElements));
+
+ /*
+ * Time between segments
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(9);
+ assertEquals(0, Iterables.size(intersectingElements));
+
+ /*
+ * Time before all segment start time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(1);
+ assertEquals(0, Iterables.size(intersectingElements));
+
+ /*
+ * Time after all segment end time
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(15);
+ assertEquals(0, Iterables.size(intersectingElements));
+ }
+
+ /**
+ * Testing method {@link ISegmentStore#dispose()}
+ */
+ @Test
+ public void testDispose() {
+ ISegmentStore<@NonNull ISegment> store = getSegmentStore();
+ store.add(SEGMENT_2_6);
+ store.dispose();
+ assertEquals(0, store.size());
+ }
+
+ /**
+ * Test iterating over a store being built.
+ *
+ * bug 500607
+ */
+ @Test
+ public void testIterator() {
+ Collection<@NonNull ISegment> beforeExpected = ImmutableList.of(SEGMENT_2_6);
+ Collection<@NonNull ISegment> afterExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8);
+ Collection<@NonNull ISegment> lastExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8, SEGMENT_6_8);
+ Collection<@NonNull ISegment> fixture = new ArrayList<>();
+ ISegmentStore<@NonNull ISegment> store = getSegmentStore();
+
+ // Add one segment to the segment store and iterate
+ store.add(SEGMENT_2_6);
+ for (ISegment item : store) {
+ fixture.add(item);
+ }
+ assertEquals(beforeExpected, fixture);
+
+ // Add a second segment to the store and iterate
+ fixture.clear();
+ store.add(SEGMENT_4_8);
+ for (ISegment item : store) {
+ fixture.add(item);
+ }
+ assertEquals(afterExpected, fixture);
+
+ fixture.clear();
+ // Take an iterator
+ Iterator<@NonNull ISegment> iter = store.iterator();
+
+ // Add a third segment to the store and iterate
+ store.add(SEGMENT_6_8);
+ Iterator<@NonNull ISegment> iter2 = store.iterator();
+ fixture.clear();
+
+ // Make sure the first iterator take has only 2 elements and the second
+ // has 3 elements
+ while (iter.hasNext()) {
+ fixture.add(iter.next());
+ }
+ assertEquals(afterExpected, fixture);
+ fixture.clear();
+ while (iter2.hasNext()) {
+ fixture.add(iter2.next());
+ }
+ assertEquals(lastExpected, fixture);
+ }
+
+}
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.segmentstore.core.tests;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.ArrayListStore;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+
+/**
+ * Unit tests for intersecting elements in an ArrayListStore
+ *
+ * @author France Lapointe Nguyen
+ * @author Matthew Khouzam
+ */
+public class ArrayListStoreTest extends AbstractTestSegmentStore {
+
+ @Override
+ protected ISegmentStore<@NonNull ISegment> getSegmentStore() {
+ return new ArrayListStore<>();
+ }
+}
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.segmentstore.core.tests;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.LazyArrayListStore;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+
+/**
+ * Unit tests for intersecting elements in an LazyArrayListStore
+ *
+ * @author Matthew Khouzam
+ */
+public class LazyArrayListStoreTest extends AbstractTestSegmentStore {
+
+ @Override
+ protected ISegmentStore<@NonNull ISegment> getSegmentStore() {
+ return new LazyArrayListStore<>();
+ }
+
+}
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.segmentstore.core.tests;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.segmentstore.core.treemap.TreeMapStore;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.junit.Test;
+
+/**
+ * Unit tests for intersecting elements in a TreeMapStore
+ *
+ * @author France Lapointe Nguyen
+ * @deprecated the test is deprecated as the store is deprecated
+ */
+@Deprecated
+public class OldTreeMapStoreTest extends AbstractTestSegmentStore {
+
+ @Override
+ protected ISegmentStore<@NonNull ISegment> getSegmentStore() {
+ return new TreeMapStore<>();
+ }
+
+ /**
+ * Try adding duplicate elements, they should be ignored
+ */
+ @Test
+ public void testNoDuplicateElements() {
+ for (ISegment segment : SEGMENTS) {
+ boolean ret = fSegmentStore.add(new BasicSegment(segment.getStart(), segment.getEnd()));
+ assertFalse(ret);
+ }
+ assertEquals(SEGMENTS.size(), fSegmentStore.size());
+ }
+}
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.segmentstore.core.tests;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory.SegmentStoreType;
+import org.junit.Test;
+
+/**
+ * Segment Store factory test
+ *
+ * @author Matthew Khouzam
+ *
+ */
+public class SegmentStoreFactoryTest {
+
+ /**
+ * Simplest create function, should always work
+ */
+ @Test
+ public void simpleCreate() {
+ assertNotNull(SegmentStoreFactory.createSegmentStore());
+ }
+
+ /**
+ * Create a fast segment store. Should always return the fastest
+ * implementation available
+ */
+ @Test
+ public void createFast() {
+ assertNotNull(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Fast));
+ }
+
+ /**
+ * Create a stable segment store, should always return a segment store that
+ * does not change much its performance memory or cpu
+ */
+ @Test
+ public void createStable() {
+ assertNotNull(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Stable));
+ }
+
+ /**
+ * Create a "set" like segment store
+ */
+ @Test
+ public void createDistinct() {
+ ISegmentStore<@NonNull ISegment> fixture = SegmentStoreFactory.createSegmentStore(SegmentStoreType.Distinct);
+ assertNotNull(fixture);
+ testDistinct(fixture);
+ }
+
+ /**
+ * Make sure mixing flags works
+ */
+ @Test
+ public void createDistinctFast() {
+ ISegmentStore<@NonNull ISegment> fixture = SegmentStoreFactory.createSegmentStore(SegmentStoreType.Distinct, SegmentStoreType.Fast);
+ testDistinct(fixture);
+ }
+
+ /**
+ * Make sure mixing flags works
+ */
+ @Test
+ public void createDistinctStable() {
+ ISegmentStore<@NonNull ISegment> fixture = SegmentStoreFactory.createSegmentStore(SegmentStoreType.Distinct, SegmentStoreType.Stable);
+ testDistinct(fixture);
+ }
+
+ /**
+ * Make sure mixing flags works
+ */
+ @Test
+ public void createDoubleDistinct() {
+ ISegmentStore<@NonNull ISegment> fixture = SegmentStoreFactory.createSegmentStore(SegmentStoreType.Distinct, SegmentStoreType.Distinct);
+ assertNotNull(fixture);
+ testDistinct(fixture);
+ }
+
+ /**
+ * Make sure mixing flags works (power set of all types)
+ */
+ @Test
+ public void createAllDressed() {
+ testDistinct(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Distinct, SegmentStoreType.Stable, SegmentStoreType.Fast));
+ testDistinct(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Distinct, SegmentStoreType.Fast, SegmentStoreType.Stable));
+ testDistinct(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Stable, SegmentStoreType.Distinct, SegmentStoreType.Fast));
+ testDistinct(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Stable, SegmentStoreType.Fast, SegmentStoreType.Distinct));
+ testDistinct(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Fast, SegmentStoreType.Distinct, SegmentStoreType.Stable));
+ testDistinct(SegmentStoreFactory.createSegmentStore(SegmentStoreType.Fast, SegmentStoreType.Stable, SegmentStoreType.Distinct));
+ }
+
+ /**
+ * Torture test, add many redundant flags
+ */
+ @SuppressWarnings("null")
+ @Test
+ public void createTortureTest() {
+ Random rnd = new Random();
+ List<@NonNull SegmentStoreType> args = new ArrayList<>();
+ rnd.setSeed(1234);
+ int nbValues = SegmentStoreType.values().length;
+ args.add(SegmentStoreType.Distinct);
+ for (int i = 0; i < 1000; i++) {
+ int nextInt = rnd.nextInt(nbValues);
+ args.add(SegmentStoreType.values()[nextInt]);
+ }
+ SegmentStoreType @NonNull [] array = args.toArray(new SegmentStoreType[args.size()]);
+ assertNotNull(array);
+ testDistinct(SegmentStoreFactory.createSegmentStore(array));
+ }
+
+ /**
+ * Create a pre-loaded fast segment store
+ */
+ @Test
+ public void createPreloaded() {
+ ISegment[] data = new ISegment[1];
+ data[0] = new BasicSegment(0, 0);
+ ISegmentStore<@NonNull ISegment> segmentStore;
+ segmentStore = SegmentStoreFactory.createSegmentStore(data);
+ assertNotNull(segmentStore);
+ assertEquals(1, segmentStore.size());
+ segmentStore = SegmentStoreFactory.createSegmentStore(data, SegmentStoreType.Fast);
+ assertNotNull(segmentStore);
+ assertEquals(1, segmentStore.size());
+ segmentStore = SegmentStoreFactory.createSegmentStore(data, SegmentStoreType.Stable);
+ assertNotNull(segmentStore);
+ assertEquals(1, segmentStore.size());
+ segmentStore = SegmentStoreFactory.createSegmentStore(data, SegmentStoreType.Distinct);
+ assertNotNull(segmentStore);
+ assertEquals(1, segmentStore.size());
+ }
+
+ private static void testDistinct(ISegmentStore<@NonNull ISegment> fixture) {
+ // test adding the same object
+ ISegment seg = new BasicSegment(0, 0);
+ fixture.add(seg);
+ fixture.add(seg);
+ assertEquals(1, fixture.size());
+ fixture.clear();
+ // test different equal objects
+ fixture.add(new BasicSegment(0, 0));
+ fixture.add(new BasicSegment(0, 0));
+ assertEquals(1, fixture.size());
+ }
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 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.segmentstore.core.tests;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.internal.segmentstore.core.treemap.TreeMapStore;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.junit.Test;
+
+/**
+ * Test specific behavior for a TreeMapStore segment store.
+ *
+ * @author France Lapointe Nguyen
+ */
+public class TreeMapStoreTest extends AbstractTestSegmentStore {
+
+ @Override
+ protected ISegmentStore<@NonNull ISegment> getSegmentStore() {
+ return new TreeMapStore<>();
+ }
+
+ /**
+ * Try adding duplicate elements, they should be ignored
+ */
+ @Test
+ public void testNoDuplicateElements() {
+ for (ISegment segment : SEGMENTS) {
+ boolean ret = fSegmentStore.add(new BasicSegment(segment.getStart(), segment.getEnd()));
+ assertFalse(ret);
+ }
+ assertEquals(SEGMENTS.size(), fSegmentStore.size());
+ }
+}
\ No newline at end of file
+++ /dev/null
-/*******************************************************************************
- * Copyright (c) 2015 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.segmentstore.core.tests.treemap;
-
-import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertTrue;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
-import org.eclipse.tracecompass.segmentstore.core.ISegment;
-import org.eclipse.tracecompass.segmentstore.core.treemap.TreeMapStore;
-import org.junit.After;
-import org.junit.Before;
-import org.junit.Test;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
-
-/**
- * Unit tests for intersecting elements in a TreeMapStore
- *
- * @author France Lapointe Nguyen
- */
-public class TreeMapStoreTest {
-
- private TreeMapStore<@NonNull ISegment> fSegmentStore;
-
- private static final @NonNull ISegment SEGMENT_2_6 = new BasicSegment(2, 6);
- private static final @NonNull ISegment SEGMENT_4_6 = new BasicSegment(4, 6);
- private static final @NonNull ISegment SEGMENT_4_8 = new BasicSegment(4, 8);
- private static final @NonNull ISegment SEGMENT_6_8 = new BasicSegment(6, 8);
- private static final @NonNull ISegment SEGMENT_10_14 = new BasicSegment(10, 14);
-
- private static final List<ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14);
- private static final List<ISegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS);
-
- /**
- * Initialize data (test vector) that will be tested
- */
- @Before
- public void setup() {
- fSegmentStore = new TreeMapStore<>();
- for (ISegment segment : SEGMENTS) {
- fSegmentStore.add(checkNotNull(segment));
- }
- }
-
- /**
- * Dispose of the segment store
- */
- @After
- public void teardown() {
- fSegmentStore.dispose();
- }
-
- /**
- * Testing method size()
- */
- @Test
- public void testSize() {
- assertEquals(SEGMENTS.size(), fSegmentStore.size());
- }
-
- /**
- * Test the contains() method.
- */
- @Test
- public void testContains() {
- ISegment otherSegment = new BasicSegment(0, 20);
-
- assertTrue(fSegmentStore.contains(SEGMENT_2_6));
- assertTrue(fSegmentStore.contains(SEGMENT_4_8));
- assertFalse(fSegmentStore.contains(otherSegment));
- }
-
- /**
- * Test the toArray() method.
- */
- @Test
- public void testToObjectArray() {
- Object[] array = fSegmentStore.toArray();
-
- assertEquals(SEGMENTS.size(), array.length);
- assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
- }
-
- /**
- * Test the toArray(T[]) method.
- */
- @Test
- public void testToSpecificArray() {
- ISegment[] array = fSegmentStore.toArray(new ISegment[0]);
-
- assertEquals(SEGMENTS.size(), array.length);
- assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
- }
-
- /**
- * Test the toArray(T[]) method with a subtype of ISegment.
- */
- @Test
- public void testToSpecifyArraySubtype() {
- TreeMapStore<@NonNull BasicSegment> tms2 = new TreeMapStore<>();
- BasicSegment otherSegment = new BasicSegment(2, 6);
- tms2.add(otherSegment);
- BasicSegment[] array = tms2.toArray(new BasicSegment[0]);
-
- assertEquals(1, array.length);
- assertTrue(Arrays.asList(array).contains(otherSegment));
-
- tms2.dispose();
- }
-
- /**
- * Try adding duplicate elements, they should be ignored
- */
- @Test
- public void testNoDuplicateElements() {
- for (ISegment segment : SEGMENTS) {
- boolean ret = fSegmentStore.add(new BasicSegment(segment.getStart(), segment.getEnd()));
- assertFalse(ret);
- }
- assertEquals(SEGMENTS.size(), fSegmentStore.size());
- }
-
- /**
- * Test the iteration order of the complete segment store.
- */
- @Test
- public void testIterationOrder() {
- int i = 0;
- for (ISegment segment : fSegmentStore) {
- assertEquals(SEGMENTS.get(i++), segment);
- }
- }
-
- /**
- * Test the iteration order when the elements are not inserted in sorted
- * order.
- */
- @Test
- public void testIterationOrderNonSortedInsertion() {
- /* Prepare the segment store, we don't use the 'fixture' in this test */
- TreeMapStore<@NonNull ISegment> store = new TreeMapStore<>();
- for (ISegment segment : REVERSE_SEGMENTS) {
- store.add(checkNotNull(segment));
- }
-
- /*
- * Test each element one by one, the iteration order should follow the
- * start times, not the insertion order.
- */
- int i = 0;
- for (ISegment segment : store) {
- assertEquals(SEGMENTS.get(i++), segment);
- }
-
- /* Manually dispose our own store */
- store.dispose();
- }
-
- /**
- * Testing method getIntersectingElements(long start, long end)
- */
- @Test
- public void testGetIntersectingElementsRange() {
-
- Iterable<ISegment> intersectingElements;
-
- /*
- * Range that does not include any segment
- */
- intersectingElements = fSegmentStore.getIntersectingElements(16, 20);
- assertEquals(0, Iterables.size(intersectingElements));
-
- /*
- * Range start time : Before first segment start time
- * Range end time : After last segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(1, 15);
- assertEquals(5, Iterables.size(intersectingElements));
-
- /*
- * Range start time : On first segment start time
- * Range end time : On last segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(2, 14);
- assertEquals(5, Iterables.size(intersectingElements));
-
- /*
- * Range start time : After one segment start time
- * Range end time : Before one segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(11, 13);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Range start time : On one segment start time
- * Range end time : On one segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(10, 14);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Range start time : On last segment end time
- * Range end time : After last segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(14, 18);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Range start time : Before first segment start time
- * Range end time : On first segment start time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(1, 2);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
- }
-
- /**
- * Testing method getIntersectingElements(long start, long end)
- */
- @Test
- public void testGetIntersectingElementsTime() {
-
- Iterable<ISegment> intersectingElements;
-
- /*
- * Time between segment start time and end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(3);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Time on segment start time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(2);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Time on segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(14);
- assertEquals(1, Iterables.size(intersectingElements));
- assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
-
- /*
- * Time overlapping many segments
- */
- intersectingElements = fSegmentStore.getIntersectingElements(6);
- assertEquals(4, Iterables.size(intersectingElements));
-
- /*
- * Time between segments
- */
- intersectingElements = fSegmentStore.getIntersectingElements(9);
- assertEquals(0, Iterables.size(intersectingElements));
-
- /*
- * Time before all segment start time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(1);
- assertEquals(0, Iterables.size(intersectingElements));
-
- /*
- * Time after all segment end time
- */
- intersectingElements = fSegmentStore.getIntersectingElements(15);
- assertEquals(0, Iterables.size(intersectingElements));
- }
-
- /**
- * Testing method getIntersectingElements(long start, long end)
- */
- @Test
- public void testDispose() {
- TreeMapStore<@NonNull ISegment> store = new TreeMapStore<>();
- store.add(SEGMENT_2_6);
- store.dispose();
- assertEquals(0, store.size());
- }
-}
\ No newline at end of file
Bundle-ManifestVersion: 2
Bundle-Name: %Bundle-Name
Bundle-Vendor: %Bundle-Vendor
-Bundle-Version: 1.0.0.qualifier
+Bundle-Version: 1.1.0.qualifier
Bundle-Localization: plugin
Bundle-SymbolicName: org.eclipse.tracecompass.segmentstore.core;singleton:=true
Bundle-Activator: org.eclipse.tracecompass.internal.segmentstore.core.Activator
org.eclipse.core.resources,
org.eclipse.tracecompass.common.core
Export-Package: org.eclipse.tracecompass.internal.segmentstore.core;x-internal:=true,
+ org.eclipse.tracecompass.internal.segmentstore.core.arraylist;x-friends:="org.eclipse.tracecompass.segmentstore.core.tests",
+ org.eclipse.tracecompass.internal.segmentstore.core.treemap;x-friends:="org.eclipse.tracecompass.segmentstore.core.tests",
org.eclipse.tracecompass.segmentstore.core,
org.eclipse.tracecompass.segmentstore.core.treemap
Import-Package: com.google.common.collect;version="12.0.0"
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.internal.segmentstore.core.arraylist;
+
+import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import java.util.stream.Collectors;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Ordering;
+
+/**
+ * Implementation of an {@link ISegmentStore} using one in-memory
+ * {@link ArrayList}. This relatively simple implementation holds everything in
+ * memory, and as such cannot contain too much data.
+ *
+ * The ArrayListStore itself is {@link Iterable}, and its iteration order will
+ * be by ascending order of start times. For segments with identical start
+ * times, the secondary comparator will be the end time. If even those are
+ * equal, it will defer to the segments' natural ordering (
+ * {@link ISegment#compareTo}).
+ *
+ * The store's tree maps will not accept duplicate key-value pairs, which means
+ * that if you want several segments with the same start and end times, make
+ * sure their compareTo() differentiates them.
+ *
+ * Removal operations are not supported.
+ *
+ * @param <E>
+ * The type of segment held in this store
+ *
+ * @author Matthew Khouzam
+ */
+public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
+
+ private final Comparator<E> COMPARATOR = Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR)
+ .compound(SegmentComparators.INTERVAL_END_COMPARATOR);
+
+ private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
+
+ private final List<E> fStore;
+
+ private @Nullable transient Iterable<E> fLastSnapshot = null;
+
+ /**
+ * Constructor
+ */
+ public ArrayListStore() {
+ fStore = new ArrayList<>();
+ }
+
+ /**
+ * Constructor
+ *
+ * @param array
+ * an array of elements to wrap in the segment store
+ *
+ */
+ public ArrayListStore(Object[] array) {
+ fStore = new ArrayList<>();
+ for (int i = 0; i < array.length; i++) {
+ if (array[i] instanceof ISegment) {
+ fStore.add((E) array[i]);
+ }
+ }
+ fStore.sort(COMPARATOR);
+ }
+ // ------------------------------------------------------------------------
+ // Methods from Collection
+ // ------------------------------------------------------------------------
+
+ @Override
+ public Iterator<E> iterator() {
+ fLock.readLock().lock();
+ try {
+ Iterable<E> lastSnapshot = fLastSnapshot;
+ if (lastSnapshot == null) {
+ lastSnapshot = ImmutableList.copyOf(fStore);
+ fLastSnapshot = lastSnapshot;
+ }
+ return checkNotNull(lastSnapshot.iterator());
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean add(@Nullable E val) {
+ if (val == null) {
+ throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$
+ }
+
+ fLock.writeLock().lock();
+ try {
+ int insertPoint = Collections.binarySearch(fStore, val);
+ insertPoint = insertPoint >= 0 ? insertPoint : -insertPoint - 1;
+ fStore.add(insertPoint, val);
+ fLastSnapshot = null;
+ return true;
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+
+ @Override
+ public int size() {
+ return fStore.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ fLock.readLock().lock();
+ try {
+ return fStore.isEmpty();
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean contains(@Nullable Object o) {
+ fLock.readLock().lock();
+ try {
+ return fStore.contains(o);
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean containsAll(@Nullable Collection<?> c) {
+ fLock.readLock().lock();
+ try {
+ return fStore.containsAll(c);
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public Object[] toArray() {
+ fLock.readLock().lock();
+ try {
+ return fStore.toArray();
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a) {
+ fLock.readLock().lock();
+ try {
+ return fStore.toArray(a);
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean remove(@Nullable Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean addAll(@Nullable Collection<? extends E> c) {
+ if (c == null) {
+ throw new IllegalArgumentException();
+ }
+
+ fLock.writeLock().lock();
+ try {
+ boolean changed = false;
+ for (E elem : c) {
+ if (this.add(elem)) {
+ changed = true;
+ }
+ }
+ return changed;
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean removeAll(@Nullable Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean retainAll(@Nullable Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void clear() {
+ fLock.writeLock().lock();
+ try {
+ fStore.clear();
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+
+ // ------------------------------------------------------------------------
+ // Methods added by ISegmentStore
+ // ------------------------------------------------------------------------
+
+ @Override
+ public Iterable<E> getIntersectingElements(long position) {
+ /*
+ * The intervals intersecting 't' are those whose 1) start time is
+ * *lower* than 't' AND 2) end time is *higher* than 't'.
+ */
+ fLock.readLock().lock();
+ try {
+ /*
+ * as fStore is sorted by start then end times, restrict sub array
+ * to elements whose start times <= t as stream.filter won't do it.
+ */
+ int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
+ index = (index >= 0) ? index : -index - 1;
+ return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public Iterable<E> getIntersectingElements(long start, long end) {
+ fLock.readLock().lock();
+ try {
+ int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
+ index = (index >= 0) ? index : -index - 1;
+ return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public void dispose() {
+ fLock.writeLock().lock();
+ try {
+ fStore.clear();
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 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.internal.segmentstore.core.arraylist;
+
+import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.stream.Collectors;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Ordering;
+
+/**
+ * Implementation of an {@link ISegmentStore} using one in-memory
+ * {@link ArrayList}. This relatively simple implementation holds everything in
+ * memory, and as such cannot contain too much data.
+ *
+ * The LazyArrayListStore itself is {@link Iterable}, and its iteration order
+ * will be by ascending order of start times. For segments with identical start
+ * times, the secondary comparator will be the end time. If even those are
+ * equal, it will defer to the segments' natural ordering (
+ * {@link ISegment#compareTo}).
+ *
+ * This structure sorts in a lazy way to allow faster insertions. However, if
+ * the structure is out of order, the next read (getting intersecting elements,
+ * iterating...) will perform a sort. It may have inconsistent performance, but
+ * should be faster at building when receiving shuffled datasets than the
+ * {@link ArrayListStore}.
+ *
+ * Removal operations are not supported.
+ *
+ * @param <E>
+ * The type of segment held in this store
+ *
+ * @author Matthew Khouzam
+ */
+public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
+
+ private static final String ERROR_MESSAGE = "Cannot remove from a segment store"; //$NON-NLS-1$
+
+ private final Comparator<E> COMPARATOR = Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR)
+ .compound(SegmentComparators.INTERVAL_END_COMPARATOR);
+
+ private final ReentrantLock fLock = new ReentrantLock(false);
+
+ private final List<E> fStore = new ArrayList<>();
+
+ private @Nullable transient Iterable<E> fLastSnapshot = null;
+
+ private volatile boolean fDirty = false;
+
+ /**
+ * Constructor
+ */
+ public LazyArrayListStore() {
+ // do nothing
+ }
+
+ /**
+ * Constructor
+ *
+ * @param array
+ * an array of elements to wrap in the segment store
+ *
+ */
+ public LazyArrayListStore(Object[] array) {
+ for (int i = 0; i < array.length; i++) {
+ if (array[i] instanceof ISegment) {
+ E element = (E) array[i];
+ setDirtyIfNeeded(element);
+ fStore.add(element);
+ }
+ }
+ if (fDirty) {
+ sortStore();
+ }
+ }
+
+ private void setDirtyIfNeeded(@NonNull E value) {
+ if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) {
+ fDirty = true;
+ }
+ }
+ // ------------------------------------------------------------------------
+ // Methods from Collection
+ // ------------------------------------------------------------------------
+
+ @Override
+ public Iterator<E> iterator() {
+ fLock.lock();
+ try {
+ if (fDirty) {
+ sortStore();
+ }
+ Iterable<E> lastSnapshot = fLastSnapshot;
+ if (lastSnapshot == null) {
+ lastSnapshot = ImmutableList.copyOf(fStore);
+ fLastSnapshot = lastSnapshot;
+ }
+ return checkNotNull(lastSnapshot.iterator());
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ /**
+ * DO NOT CALL FROM OUTSIDE OF A LOCK!
+ */
+ private void sortStore() {
+ fStore.sort(COMPARATOR);
+ fDirty = false;
+ }
+
+ @Override
+ public boolean add(@Nullable E val) {
+ if (val == null) {
+ throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$
+ }
+
+ fLock.lock();
+ try {
+ setDirtyIfNeeded(val);
+ fStore.add(val);
+ fLastSnapshot = null;
+ return true;
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public int size() {
+ return fStore.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ fLock.lock();
+ try {
+ return fStore.isEmpty();
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean contains(@Nullable Object o) {
+ fLock.lock();
+ try {
+ return fStore.contains(o);
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean containsAll(@Nullable Collection<?> c) {
+ fLock.lock();
+ try {
+ return fStore.containsAll(c);
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public Object[] toArray() {
+ fLock.lock();
+ try {
+ if (fDirty) {
+ sortStore();
+ }
+ return fStore.toArray();
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a) {
+ fLock.lock();
+ try {
+ if (fDirty) {
+ sortStore();
+ }
+ return fStore.toArray(a);
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean addAll(@Nullable Collection<? extends E> c) {
+ if (c == null) {
+ throw new IllegalArgumentException();
+ }
+
+ fLock.lock();
+ try {
+ boolean changed = false;
+ for (E elem : c) {
+ if (add(elem)) {
+ changed = true;
+ }
+ }
+ return changed;
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean removeAll(@Nullable Collection<?> c) {
+ throw new UnsupportedOperationException(ERROR_MESSAGE);
+ }
+
+ @Override
+ public boolean retainAll(@Nullable Collection<?> c) {
+ throw new UnsupportedOperationException(ERROR_MESSAGE);
+ }
+
+ @Override
+ public boolean remove(@Nullable Object o) {
+ throw new UnsupportedOperationException(ERROR_MESSAGE);
+ }
+
+ @Override
+ public void clear() {
+ fLock.lock();
+ try {
+ fStore.clear();
+ fLastSnapshot = null;
+ fDirty = false;
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ // ------------------------------------------------------------------------
+ // Methods added by ISegmentStore
+ // ------------------------------------------------------------------------
+
+ @Override
+ public Iterable<E> getIntersectingElements(long position) {
+ fLock.lock();
+ if (fDirty) {
+ sortStore();
+ }
+ /*
+ * The intervals intersecting 't' are those whose 1) start time is
+ * *lower* than 't' AND 2) end time is *higher* than 't'.
+ */
+ try {
+ /*
+ * as fStore is sorted by start then end times, restrict sub array
+ * to elements whose start times <= t as stream.filter won't do it.
+ */
+ int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
+ index = (index >= 0) ? index : -index - 1;
+ return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public Iterable<E> getIntersectingElements(long start, long end) {
+ fLock.lock();
+ if (fDirty) {
+ sortStore();
+ }
+ try {
+ int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
+ index = (index >= 0) ? index : -index - 1;
+ return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
+ } finally {
+ fLock.unlock();
+ }
+ }
+
+ @Override
+ public void dispose() {
+ fLock.lock();
+ try {
+ fStore.clear();
+ fDirty = false;
+ } finally {
+ fLock.unlock();
+ }
+ }
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 Polytechnique
+ *
+ * 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
+ *******************************************************************************/
+
+@org.eclipse.jdt.annotation.NonNullByDefault
+package org.eclipse.tracecompass.internal.segmentstore.core.arraylist;
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others.
+ *
+ * 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
+ *
+ * Contributors:
+ * Alexandre Montplaisir - Initial API and implementation
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.internal.segmentstore.core.treemap;
+
+import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.TreeMap;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.segmentstore.core.ISegment;
+import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Ordering;
+import com.google.common.collect.Sets;
+import com.google.common.collect.TreeMultimap;
+
+/**
+ * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
+ * This relatively simple implementation holds everything in memory, and as such
+ * cannot contain too much data.
+ *
+ * The TreeMapStore itself is Iterable, and its iteration order will be by
+ * ascending order of start times. For segments with identical start times, the
+ * secondary comparator will be the end time. If even those are equal, it will
+ * defer to the segments' natural ordering ({@link ISegment#compareTo}).
+ *
+ * The store's tree maps will not accept duplicate key-value pairs, which means
+ * that if you want several segments with the same start and end times, make
+ * sure their compareTo() differentiates them.
+ *
+ * Removal operations are not supported.
+ *
+ * @param <E>
+ * The type of segment held in this store
+ *
+ * @author Alexandre Montplaisir
+ */
+public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
+
+ private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
+
+ private final TreeMultimap<Long, E> fStartTimesIndex;
+ private final TreeMultimap<Long, E> fEndTimesIndex;
+
+ private volatile long fSize;
+
+ private @Nullable transient Iterable<E> fLastSnapshot = null;
+
+ /**
+ * Constructor
+ */
+ public TreeMapStore() {
+ /*
+ * For the start times index, the "key comparator" will compare the
+ * start times as longs directly. This is the primary comparator for its
+ * tree map.
+ *
+ * The secondary "value" comparator will check the end times first, and
+ * in the event of a tie, defer to the ISegment's Comparable
+ * implementation, a.k.a. its natural ordering.
+ *
+ * The same is done for the end times index, but swapping the first two
+ * comparators instead.
+ */
+ fStartTimesIndex = TreeMultimap.create(
+ SegmentComparators.LONG_COMPARATOR,
+ Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural()));
+
+ fEndTimesIndex = TreeMultimap.create(
+ SegmentComparators.LONG_COMPARATOR,
+ Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural()));
+
+ fSize = 0;
+ }
+
+ // ------------------------------------------------------------------------
+ // Methods from Collection
+ // ------------------------------------------------------------------------
+
+ @Override
+ public Iterator<E> iterator() {
+ fLock.readLock().lock();
+ try {
+ Iterable<E> lastSnapshot = fLastSnapshot;
+ if (lastSnapshot == null) {
+ lastSnapshot = ImmutableList.copyOf(fStartTimesIndex.values());
+ fLastSnapshot = lastSnapshot;
+ }
+ return checkNotNull(lastSnapshot.iterator());
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean add(@Nullable E val) {
+ if (val == null) {
+ throw new IllegalArgumentException();
+ }
+
+ fLock.writeLock().lock();
+ try {
+ if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) {
+ fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
+ fSize++;
+ fLastSnapshot = null;
+ return true;
+ }
+ return false;
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+
+ @Override
+ public int size() {
+ return Long.valueOf(fSize).intValue();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return (fSize == 0);
+ }
+
+ @Override
+ public boolean contains(@Nullable Object o) {
+ fLock.readLock().lock();
+ try {
+ return fStartTimesIndex.containsValue(o);
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean containsAll(@Nullable Collection<?> c) {
+ fLock.readLock().lock();
+ try {
+ return fStartTimesIndex.values().containsAll(c);
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public Object[] toArray() {
+ fLock.readLock().lock();
+ try {
+ return fStartTimesIndex.values().toArray();
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a) {
+ fLock.readLock().lock();
+ try {
+ return fStartTimesIndex.values().toArray(a);
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean remove(@Nullable Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean addAll(@Nullable Collection<? extends E> c) {
+ if (c == null) {
+ throw new IllegalArgumentException();
+ }
+
+ fLock.writeLock().lock();
+ try {
+ boolean changed = false;
+ for (E elem : c) {
+ if (this.add(elem)) {
+ changed = true;
+ }
+ }
+ return changed;
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+
+ @Override
+ public boolean removeAll(@Nullable Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean retainAll(@Nullable Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void clear() {
+ fLock.writeLock().lock();
+ try {
+ fSize = 0;
+ fEndTimesIndex.clear();
+ fStartTimesIndex.clear();
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+
+ // ------------------------------------------------------------------------
+ // Methods added by ISegmentStore
+ // ------------------------------------------------------------------------
+
+ @Override
+ public Iterable<E> getIntersectingElements(long position) {
+ /*
+ * The intervals intersecting 't' are those whose 1) start time is
+ * *lower* than 't' AND 2) end time is *higher* than 't'.
+ */
+ fLock.readLock().lock();
+ try {
+ Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values());
+ Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values());
+ return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public Iterable<E> getIntersectingElements(long start, long end) {
+ fLock.readLock().lock();
+ try {
+ Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values());
+ Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values());
+ return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
+ } finally {
+ fLock.readLock().unlock();
+ }
+ }
+
+ @Override
+ public void dispose() {
+ fLock.writeLock().lock();
+ try {
+ fStartTimesIndex.clear();
+ fEndTimesIndex.clear();
+ fSize = 0;
+ } finally {
+ fLock.writeLock().unlock();
+ }
+ }
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 EfficiOS Inc. and others
+ *
+ * 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
+ *
+ * Contributors:
+ * Alexandre Montplaisir - Initial API and implementation
+ *******************************************************************************/
+
+@org.eclipse.jdt.annotation.NonNullByDefault
+package org.eclipse.tracecompass.internal.segmentstore.core.treemap;
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 Polytechnique
+ *
+ * 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
+ *
+ * Contributors:
+ * Loïc Prieur-Drevon - Initial API and implementation
+ ******************************************************************************/
+
+package org.eclipse.tracecompass.segmentstore.core;
+
+import java.util.HashSet;
+import java.util.Set;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.ArrayListStore;
+import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.LazyArrayListStore;
+import org.eclipse.tracecompass.internal.segmentstore.core.treemap.TreeMapStore;
+
+/**
+ * Factory to create Segment Stores.
+ *
+ * Since segment stores are meant to be accessed using the {@link ISegmentStore}
+ * interface, you can use this factory to instantiate new ones.
+ *
+ * @author Loïc Prieur-Drevon
+ * @param <E>
+ * The type of segment held in this store
+ * @since 1.1
+ */
+public final class SegmentStoreFactory<E> {
+ /**
+ * Flags to determine the type of SegmentStore to use.
+ */
+ public enum SegmentStoreType {
+ /**
+ * Segment Store should be as fast as possible to build and read.
+ * Performance of individual operations may be slower, but overall the
+ * speed should be faster.
+ */
+ Fast,
+ /**
+ * Segment Store based should have predictable performance. This does
+ * not mean it's faster, it should not give a surprise random slow down
+ * though. If it slows down, it will be on the {@link ISegment} that
+ * slows it down.
+ */
+ Stable,
+ /**
+ * Segment Store should contain no duplicate segments
+ */
+ Distinct
+ }
+
+ private SegmentStoreFactory() {
+ // Do nothing
+ }
+
+ /**
+ * New SegmentStore factory method
+ *
+ * @param segmentTypes
+ * Flags used to determine the type of Segment Store that will be
+ * created
+ *
+ * @return a new {@link ISegmentStore}
+ */
+ public static <E extends ISegment> ISegmentStore<E> createSegmentStore(@Nullable SegmentStoreType... segmentTypes) {
+ Set<@NonNull SegmentStoreType> segments = getListOfFlags(segmentTypes);
+ if (segments.contains(SegmentStoreType.Distinct)) {
+ return createTreeMapStore();
+ }
+ if (segments.contains(SegmentStoreType.Stable)) {
+ return createArrayListStore();
+ }
+ // default option is the fastest
+ return createLazyArrayListStore();
+
+ }
+
+ /**
+ * New SegmentStore factory method to create store from an array of Objects
+ *
+ * @param segmentTypes
+ * Flags used to determine the type of Segment Store that will be
+ * created
+ * @param array
+ * the {@link Object} array we want the returned segment store to
+ * contain, {@link Object} are only inserted if they extend
+ * {@link ISegment}
+ * @return an {@link ISegmentStore} containing the {@link ISegment}s from
+ * array.
+ */
+ public static <E extends ISegment> ISegmentStore<E> createSegmentStore(Object[] array, SegmentStoreType... segmentTypes) {
+ Set<@NonNull SegmentStoreType> segments = getListOfFlags(segmentTypes);
+ if (segments.contains(SegmentStoreType.Distinct)) {
+ ISegmentStore<E> store = createTreeMapStore();
+ for (Object elem : array) {
+ if (elem instanceof ISegment) {
+ store.add((E) elem); // warning from type, it should be fine
+ }
+ }
+ return store;
+ }
+ if (segments.contains(SegmentStoreType.Stable)) {
+ return new ArrayListStore<>(array);
+ }
+ // default option is the fastest
+ return new LazyArrayListStore<>(array);
+ }
+
+ private static Set<@NonNull SegmentStoreType> getListOfFlags(SegmentStoreType... segmentTypes) {
+ Set<@NonNull SegmentStoreType> segments = new HashSet<>();
+ for(@Nullable SegmentStoreType segmentType : segmentTypes ) {
+ if(segmentType != null) {
+ segments.add(segmentType);
+ }
+ }
+ return segments;
+ }
+
+ /**
+ * New {@link TreeMapStore} factory method
+ *
+ * @return the new Segment Store
+ */
+ private static <E extends ISegment> ISegmentStore<E> createTreeMapStore() {
+ return new TreeMapStore<>();
+ }
+
+ /**
+ * New {@link ArrayListStore} factory method
+ *
+ * @return the new Segment Store
+ */
+ private static <E extends ISegment> ISegmentStore<E> createArrayListStore() {
+ return new ArrayListStore<>();
+ }
+
+ /**
+ * New {@link LazyArrayListStore} factory method
+ *
+ * @return the new Segment Store
+ */
+ private static <E extends ISegment> ISegmentStore<E> createLazyArrayListStore() {
+ return new LazyArrayListStore<>();
+ }
+
+}
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
* The type of segment held in this store
*
* @author Alexandre Montplaisir
+ * @deprecated Use the {@link SegmentStoreFactory} to create a new segment store
*/
+@Deprecated
public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.analysis.timing.core.segmentstore.AbstractSegmentStoreAnalysisModule;
import org.eclipse.tracecompass.analysis.timing.core.segmentstore.IAnalysisProgressListener;
-import org.eclipse.tracecompass.internal.analysis.timing.core.store.ArrayListStore;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory;
import org.eclipse.tracecompass.tmf.core.exceptions.TmfAnalysisException;
import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
* Fake segment indicated that the last segment have been received
*/
public static final @NonNull EndSegment END_SEGMENT = new EndSegment();
- private final ISegmentStore<@NonNull ISegment> fSegments = new ArrayListStore<>();
+ private final ISegmentStore<@NonNull ISegment> fSegments = SegmentStoreFactory.createSegmentStore();
private final CountDownLatch fFinished = new CountDownLatch(1);
private final @NonNull XmlPatternAnalysis fParent;
private boolean fSegmentStoreCompleted;