From def1d9d0cd83d812a3d19ef72860c188e1a830ba Mon Sep 17 00:00:00 2001 From: =?utf8?q?Lo=C3=AFc=20Prieur-Drevon?= Date: Tue, 27 Sep 2016 12:25:40 -0400 Subject: [PATCH] segstore: introduce sorted iterators MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit add a sorted iterator to the segment store interface. this will be useful for external memory segment stores for which the intersecting segments cannot be held and sorted in main memory, and if external memory stores have optimized sorted iteration. Change-Id: I02076daf1721cdf8bdd66f5e892f5c5280e46a3b Signed-off-by: Loïc Prieur-Drevon Reviewed-on: https://git.eclipse.org/r/82015 Reviewed-by: Genevieve Bastien Tested-by: Genevieve Bastien Reviewed-by: Matthew Khouzam Reviewed-by: Hudson CI Reviewed-by: Jean-Christian Kouame Tested-by: Jean-Christian Kouame --- .../core/tests/AbstractTestSegmentStore.java | 40 ++++++++++++ .../core/arraylist/ArrayListStore.java | 20 ------ .../core/arraylist/LazyArrayListStore.java | 23 ------- .../core/treemap/TreeMapStore.java | 16 ----- .../segmentstore/core/ISegmentStore.java | 65 ++++++++++++++++++- .../core/treemap/TreeMapStore.java | 1 + 6 files changed, 105 insertions(+), 60 deletions(-) diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core.tests/src/org/eclipse/tracecompass/segmentstore/core/tests/AbstractTestSegmentStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core.tests/src/org/eclipse/tracecompass/segmentstore/core/tests/AbstractTestSegmentStore.java index 05818af722..3fecaf97de 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core.tests/src/org/eclipse/tracecompass/segmentstore/core/tests/AbstractTestSegmentStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core.tests/src/org/eclipse/tracecompass/segmentstore/core/tests/AbstractTestSegmentStore.java @@ -17,13 +17,17 @@ import static org.junit.Assert.assertTrue; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; +import java.util.Comparator; import java.util.Iterator; +import java.util.LinkedList; import java.util.List; import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.common.core.NonNullUtils; 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 org.junit.After; import org.junit.Before; import org.junit.Test; @@ -362,4 +366,40 @@ public abstract class AbstractTestSegmentStore { assertEquals(lastExpected, fixture); } + /** + * Test to check ordered iterators + */ + @Test + public void testSortedIterator() { + List<@NonNull Comparator> comparators = new LinkedList<>(); + comparators.add(SegmentComparators.INTERVAL_END_COMPARATOR); + comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_END_COMPARATOR.reversed())); + comparators.add(SegmentComparators.INTERVAL_START_COMPARATOR); + comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_START_COMPARATOR.reversed())); + comparators.add(SegmentComparators.INTERVAL_LENGTH_COMPARATOR); + comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_LENGTH_COMPARATOR.reversed())); + + Iterable iterable; + for (Comparator comparator : comparators) { + iterable = fSegmentStore.iterator(comparator); + verifySortedIterable(iterable, 5, comparator); + iterable = fSegmentStore.getIntersectingElements(5, comparator); + verifySortedIterable(iterable, 3, comparator); + iterable = fSegmentStore.getIntersectingElements(7, 14, comparator); + verifySortedIterable(iterable, 3, comparator); + } + } + + private static void verifySortedIterable(Iterable iterable, int expectedSize, Comparator comparator) { + // check its size + assertEquals(expectedSize, Iterables.size(iterable)); + Iterator iterator = iterable.iterator(); + // check the order + ISegment prev, current = iterator.next(); + while (iterator.hasNext()) { + prev = current; + current = iterator.next(); + assertTrue(comparator.compare(prev, current) <= 0); + } + } } \ No newline at end of file diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java index 8f166f4075..60387b953b 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java @@ -233,26 +233,6 @@ public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStor // Methods added by ISegmentStore // ------------------------------------------------------------------------ - @Override - public Iterable 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 getIntersectingElements(long start, long end) { fLock.readLock().lock(); diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java index 1d6de72ec9..a9128c7b17 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java @@ -265,29 +265,6 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment // Methods added by ISegmentStore // ------------------------------------------------------------------------ - @Override - public Iterable 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 getIntersectingElements(long start, long end) { fLock.lock(); diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java index cd1882e6bd..e9a0965ff1 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java @@ -231,22 +231,6 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< // Methods added by ISegmentStore // ------------------------------------------------------------------------ - @Override - public Iterable 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 matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values()); - Iterable 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 getIntersectingElements(long start, long end) { fLock.readLock().lock(); diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java index 2e4be6a659..132f08a9a6 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java @@ -13,6 +13,14 @@ package org.eclipse.tracecompass.segmentstore.core; import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; + +import org.eclipse.jdt.annotation.NonNull; + +import com.google.common.collect.Lists; /** * Interface for segment-storing backends. @@ -25,6 +33,18 @@ import java.util.Collection; */ public interface ISegmentStore extends Collection { + /** + * Sorted Iterator + * + * @param order + * The desired order for the returned iterator + * @return An iterator over all the segments in the store in the desired order + * @since 1.1 + */ + default Iterable iterator(Comparator order){ + return getIntersectingElements(Long.MIN_VALUE, Long.MAX_VALUE, order); + } + /** * Retrieve all elements that inclusively cross the given position. * @@ -33,7 +53,25 @@ public interface ISegmentStore extends Collection { * tree's X axis represents time. * @return The intervals that cross this position */ - Iterable getIntersectingElements(long position); + default Iterable getIntersectingElements(long position){ + return getIntersectingElements(position, position); + } + + /** + * Retrieve all elements that inclusively cross the given position, sorted + * in the specified order. + * + * @param position + * The target position. This would represent a timestamp, if the + * tree's X axis represents time. + * @param order + * The desired order for the returned iterator + * @return The intervals that cross this position + * @since 1.1 + */ + default Iterable getIntersectingElements(long position, Comparator order) { + return getIntersectingElements(position, position, order); + } /** * Retrieve all elements that inclusively cross another segment. We define @@ -54,6 +92,31 @@ public interface ISegmentStore extends Collection { */ Iterable getIntersectingElements(long start, long end); + /** + * Retrieve all elements that inclusively cross another segment, sorted in + * the specified order. We define this target segment by its start and end + * positions. + * + * @param start + * The target start position + * @param end + * The target end position + * @param order + * The desired order for the returned iterator + * @return The intervals that cross this position + * @since 1.1 + */ + default Iterable getIntersectingElements(long start, long end, Comparator order){ + List list = Lists.newArrayList(getIntersectingElements(start, end)); + return new Iterable<@NonNull E>() { + @Override + public Iterator<@NonNull E> iterator() { + Collections.sort(list, order); + return list.iterator(); + } + }; + } + /** * Dispose the data structure and release any system resources associated * with it. diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/treemap/TreeMapStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/treemap/TreeMapStore.java index e8014ad292..e9a5b0d26a 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/treemap/TreeMapStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/treemap/TreeMapStore.java @@ -141,4 +141,5 @@ public class TreeMapStore<@NonNull E extends ISegment> extends org.eclipse.trace public void dispose() { super.dispose(); } + } -- 2.34.1