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 <loic.prieurdrevon@gmail.com>
Reviewed-on: https://git.eclipse.org/r/82015
Reviewed-by: Genevieve Bastien <gbastien+lttng@versatic.net>
Tested-by: Genevieve Bastien <gbastien+lttng@versatic.net>
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-by: Hudson CI
Reviewed-by: Jean-Christian Kouame <jean-christian.kouame@ericsson.com>
Tested-by: Jean-Christian Kouame <jean-christian.kouame@ericsson.com>
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;
assertEquals(lastExpected, fixture);
}
+ /**
+ * Test to check ordered iterators
+ */
+ @Test
+ public void testSortedIterator() {
+ List<@NonNull Comparator<ISegment>> 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<ISegment> iterable;
+ for (Comparator<ISegment> 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<ISegment> iterable, int expectedSize, Comparator<ISegment> comparator) {
+ // check its size
+ assertEquals(expectedSize, Iterables.size(iterable));
+ Iterator<ISegment> 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
// 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();
// 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();
// 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();
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.
*/
public interface ISegmentStore<E extends ISegment> extends Collection<E> {
+ /**
+ * 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<E> iterator(Comparator<ISegment> order){
+ return getIntersectingElements(Long.MIN_VALUE, Long.MAX_VALUE, order);
+ }
+
/**
* Retrieve all elements that inclusively cross the given position.
*
* tree's X axis represents time.
* @return The intervals that cross this position
*/
- Iterable<E> getIntersectingElements(long position);
+ default Iterable<E> 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<E> getIntersectingElements(long position, Comparator<ISegment> order) {
+ return getIntersectingElements(position, position, order);
+ }
/**
* Retrieve all elements that inclusively cross another segment. We define
*/
Iterable<E> 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<E> getIntersectingElements(long start, long end, Comparator<ISegment> order){
+ List<E> 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.
public void dispose() {
super.dispose();
}
+
}
projects / deliverable / tracecompass.git / commitdiff
