From 5d2790318fdfc4c2ef65813618c4707a731119aa Mon Sep 17 00:00:00 2001 From: =?utf8?q?Lo=C3=AFc=20Prieur-Drevon?= Date: Thu, 6 Apr 2017 10:43:27 -0400 Subject: [PATCH] ss: add 2D iterator queries to the SS API MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This patch adds 2D iterator queries to the ITmfStateSystem API, which lazily returns intervals from a list of their quarks, that intersect (a time range or a list of timestamps). Change-Id: I52d510a1c6e5d24faa2d5d5466112c70d795b39a Signed-off-by: Loïc Prieur-Drevon Signed-off-by: Alexandre Montplaisir Reviewed-on: https://git.eclipse.org/r/85962 Reviewed-by: Hudson CI Tested-by: Matthew Khouzam Reviewed-by: Matthew Khouzam Reviewed-by: Patrick Tasse Reviewed-by: Genevieve Bastien Tested-by: Genevieve Bastien --- .../annotations/java/util/Arrays.eea | 21 ++ .../DiscreteIntegerRangeConditionTest.java | 130 +++++++++++ .../DiscreteTimeRangeConditionTest.java | 131 +++++++++++ .../META-INF/MANIFEST.MF | 2 +- .../condition/ArrayIntegerRangeCondition.java | 116 +++++++++ .../condition/ArrayTimeRangeCondition.java | 116 +++++++++ .../core/condition/IntegerRangeCondition.java | 91 ++++++++ .../core/condition/TimeRangeCondition.java | 21 +- .../core/tests/StateSystem2DTest.java | 221 ++++++++++++++++++ .../.settings/.api_filters | 19 ++ .../META-INF/MANIFEST.MF | 3 +- .../statesystem/core/StateSystem.java | 49 +++- .../statesystem/core/TransientState.java | 34 +++ .../core/backend/InMemoryBackend.java | 77 +++--- .../statesystem/core/backend/NullBackend.java | 10 + .../core/backend/historytree/HTNode.java | 28 +++ .../historytree/HistoryTreeBackend.java | 44 ++++ .../core/backend/historytree/ParentNode.java | 18 ++ .../ThreadedHistoryTreeBackend.java | 19 ++ .../backend/historytree/classic/CoreNode.java | 52 +++++ .../statesystem/core/ITmfStateSystem.java | 49 ++++ .../statesystem/core/StateSystemUtils.java | 35 ++- .../core/backend/IStateHistoryBackend.java | 19 ++ 23 files changed, 1248 insertions(+), 57 deletions(-) create mode 100644 statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteIntegerRangeConditionTest.java create mode 100644 statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteTimeRangeConditionTest.java create mode 100644 statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayIntegerRangeCondition.java create mode 100644 statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayTimeRangeCondition.java create mode 100644 statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/IntegerRangeCondition.java create mode 100644 statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/StateSystem2DTest.java create mode 100644 statesystem/org.eclipse.tracecompass.statesystem.core/.settings/.api_filters diff --git a/common/org.eclipse.tracecompass.common.core/annotations/java/util/Arrays.eea b/common/org.eclipse.tracecompass.common.core/annotations/java/util/Arrays.eea index b93bc8ef91..36ef00ca87 100644 --- a/common/org.eclipse.tracecompass.common.core/annotations/java/util/Arrays.eea +++ b/common/org.eclipse.tracecompass.common.core/annotations/java/util/Arrays.eea @@ -2,6 +2,27 @@ class java/util/Arrays asList ([TT;)Ljava/util/List; ([TT;)L1java/util/List; +copyOfRange + ([BII)[B + ([BII)[1B +copyOfRange + ([CII)[C + ([CII)[1C +copyOfRange + ([DII)[D + ([DII)[1D +copyOfRange + ([FII)[F + ([FII)[1F +copyOfRange + ([III)[I + ([III)[1I +copyOfRange + ([JII)[J + ([JII)[1J +copyOfRange + ([ZII)[Z + ([ZII)[1Z stream ([D)Ljava/util/stream/DoubleStream; ([D)L1java/util/stream/DoubleStream; diff --git a/statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteIntegerRangeConditionTest.java b/statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteIntegerRangeConditionTest.java new file mode 100644 index 0000000000..0e994746bc --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteIntegerRangeConditionTest.java @@ -0,0 +1,130 @@ +/******************************************************************************* + * Copyright (c) 2017 École Polytechnique de Montréal + * + * 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.datastore.core.condition; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertTrue; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.junit.Test; + +/** + * Test the discrete integer range condition. + * + * @author Loïc Prieur-Drevon + */ +public class DiscreteIntegerRangeConditionTest { + + private static final int LOW = 0; + private static final int HIGH = 10; + private static final List VALUES = Arrays.asList(LOW, HIGH / 2, HIGH); + private static final IntegerRangeCondition CONDITION = new ArrayIntegerRangeCondition(VALUES); + + /** + * Ensure that we cannot build a condition with an empty collection. + */ + @Test(expected = IllegalArgumentException.class) + public void testConstructor() { + new ArrayIntegerRangeCondition(Collections.emptyList()); + } + + /** + * Ensure that the minimum and maximum functions return the correct values. + */ + @Test + public void testBounds() { + assertEquals(LOW, CONDITION.min()); + assertEquals(HIGH, CONDITION.max()); + } + + /** + * Test that the right elements are contained in the condition. + */ + @Test + public void testPredicate() { + assertFalse(CONDITION.test(-5)); + for (Integer v : VALUES) { + assertTrue(CONDITION.test(v)); + assertFalse(CONDITION.test(v + 1)); + } + assertFalse(CONDITION.test(15)); + } + + /** + * Test that modifying the list used to populate the condition does not + * affect the condition + */ + @Test + public void testPredicateAndAdd() { + List values = new ArrayList<>(); + values.add(1); + values.add(5); + IntegerRangeCondition condition = new ArrayIntegerRangeCondition(values); + assertFalse(condition.test(-5)); + for (Integer v : values) { + assertTrue(condition.test(v)); + assertFalse(condition.test(v + 1)); + } + assertFalse(condition.test(15)); + // Add the values to the initial set and make sure it is not part of the + // condition + values.add(15); + assertFalse(condition.test(15)); + } + + /** + * Test that the right intervals intersect the condition. + */ + @Test + public void testIntersects() { + assertFalse(CONDITION.intersects(Integer.MIN_VALUE, LOW - 1)); + assertTrue(CONDITION.intersects(0, 4)); + assertFalse(CONDITION.intersects(1, 4)); + assertTrue(CONDITION.intersects(2, 8)); + assertFalse(CONDITION.intersects(6, 9)); + assertTrue(CONDITION.intersects(5, 15)); + assertFalse(CONDITION.intersects(HIGH + 1, Integer.MAX_VALUE)); + } + + /** + * Test that the returned subcondition has the correct bounds. + */ + @Test + public void testSubCondition() { + IntegerRangeCondition sub = CONDITION.subCondition(-5, 8); + assertNotNull(sub); + assertEquals(ArrayIntegerRangeCondition.class, sub.getClass()); + int low = sub.min(); + int high = sub.max(); + assertEquals(LOW, low); + assertEquals(HIGH / 2, high); + + // For a range where no value is include, it should return null + sub = CONDITION.subCondition(LOW + 1, HIGH / 2 - 1); + assertNull(sub); + + // Test conditions for border values, sub conditions are inclusive + sub = CONDITION.subCondition(LOW, HIGH / 2); + assertNotNull(sub); + low = sub.min(); + high = sub.max(); + assertEquals(LOW, low); + assertEquals(HIGH / 2, high); + } + +} diff --git a/statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteTimeRangeConditionTest.java b/statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteTimeRangeConditionTest.java new file mode 100644 index 0000000000..5d7dd55394 --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/datastore/core/condition/DiscreteTimeRangeConditionTest.java @@ -0,0 +1,131 @@ +/******************************************************************************* + * Copyright (c) 2017 École Polytechnique de Montréal + * + * 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.datastore.core.condition; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertTrue; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; +import org.junit.Test; + +/** + * Test the discrete time range condition. + * + * @author Loïc Prieur-Drevon + */ +public class DiscreteTimeRangeConditionTest { + + private static final long LOW = 0L; + private static final long HIGH = 10L; + private static final List VALUES = Arrays.asList(LOW, HIGH / 2L, HIGH); + private static final TimeRangeCondition CONDITION = new ArrayTimeRangeCondition(VALUES); + + /** + * Ensure that we cannot build a condition with an empty collection. + */ + @Test(expected = IllegalArgumentException.class) + public void testConstructor() { + new ArrayTimeRangeCondition(Collections.emptyList()); + } + + /** + * Ensure that the minimum and maximum functions return the correct values. + */ + @Test + public void testBounds() { + assertEquals(LOW, CONDITION.min()); + assertEquals(HIGH, CONDITION.max()); + } + + /** + * Test that the right elements are contained in the condition. + */ + @Test + public void testPredicate() { + assertFalse(CONDITION.test(-5L)); + for (Long v : VALUES) { + assertTrue(CONDITION.test(v)); + assertFalse(CONDITION.test(v + 1L)); + } + assertFalse(CONDITION.test(15L)); + } + + /** + * Test that modifying the list used to populate the condition does not + * affect the condition + */ + @Test + public void testPredicateAndAdd() { + List values = new ArrayList<>(); + values.add(1L); + values.add(5L); + TimeRangeCondition condition = new ArrayTimeRangeCondition(values); + assertFalse(condition.test(-5L)); + for (Long v : values) { + assertTrue(condition.test(v)); + assertFalse(condition.test(v + 1L)); + } + assertFalse(condition.test(15L)); + // Add the values to the initial set and make sure it is not part of the + // condition + values.add(15L); + assertFalse(condition.test(15L)); + } + + /** + * Test that the right intervals intersect the condition. + */ + @Test + public void testIntersects() { + assertFalse(CONDITION.intersects(Long.MIN_VALUE, LOW - 1L)); + assertTrue(CONDITION.intersects(0L, 4L)); + assertFalse(CONDITION.intersects(1L, 4L)); + assertTrue(CONDITION.intersects(2L, 8L)); + assertFalse(CONDITION.intersects(6L, 9L)); + assertTrue(CONDITION.intersects(5L, 15L)); + assertFalse(CONDITION.intersects(HIGH + 1L, Long.MAX_VALUE)); + } + + /** + * Test that the returned subcondition has the correct bounds. + */ + @Test + public void testSubCondition() { + @Nullable TimeRangeCondition sub = CONDITION.subCondition(-5L, 8L); + assertNotNull(sub); + assertEquals(ArrayTimeRangeCondition.class, sub.getClass()); + long low = sub.min(); + long high = sub.max(); + assertEquals(LOW, low); + assertEquals(HIGH / 2, high); + + // For a range where no value is include, it should return null + sub = CONDITION.subCondition(LOW + 1L, HIGH / 2 - 1); + assertNull(sub); + + // Test conditions for border values, sub conditions are inclusive + sub = CONDITION.subCondition(LOW, HIGH / 2); + assertNotNull(sub); + low = sub.min(); + high = sub.max(); + assertEquals(LOW, low); + assertEquals(HIGH / 2, high); + } + +} diff --git a/statesystem/org.eclipse.tracecompass.datastore.core/META-INF/MANIFEST.MF b/statesystem/org.eclipse.tracecompass.datastore.core/META-INF/MANIFEST.MF index 0bd32807a4..0aaaaee320 100644 --- a/statesystem/org.eclipse.tracecompass.datastore.core/META-INF/MANIFEST.MF +++ b/statesystem/org.eclipse.tracecompass.datastore.core/META-INF/MANIFEST.MF @@ -15,7 +15,7 @@ Export-Package: org.eclipse.tracecompass.internal.datastore.core;x-internal:=tru org.eclipse.tracecompass.internal.datastore.core.condition;x-internal:=true, org.eclipse.tracecompass.internal.datastore.core.historytree;x-internal:=true, org.eclipse.tracecompass.internal.datastore.core.serialization;x-internal:=true, - org.eclipse.tracecompass.internal.provisional.datastore.core.condition;x-friends:="org.eclipse.tracecompass.segmentstore.core,org.eclipse.tracecompass.segmentstore.core.tests", + org.eclipse.tracecompass.internal.provisional.datastore.core.condition;x-friends:="org.eclipse.tracecompass.statesystem.core,org.eclipse.tracecompass.segmentstore.core,org.eclipse.tracecompass.segmentstore.core.tests", org.eclipse.tracecompass.internal.provisional.datastore.core.exceptions, org.eclipse.tracecompass.internal.provisional.datastore.core.historytree;x-friends:="org.eclipse.tracecompass.segmentstore.core,org.eclipse.tracecompass.segmentstore.core.tests", org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.classic;x-friends:="org.eclipse.tracecompass.statesystem.core,org.eclipse.tracecompass.statesystem.core.tests", diff --git a/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayIntegerRangeCondition.java b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayIntegerRangeCondition.java new file mode 100644 index 0000000000..f82d23180e --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayIntegerRangeCondition.java @@ -0,0 +1,116 @@ +/******************************************************************************* + * Copyright (c) 2017 École Polytechnique de Montréal + * + * 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.datastore.core.condition; + +import java.util.Arrays; +import java.util.Collection; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; + +/** + * Primitive array backed integer range condition + * + * @author Loic Prieur-Drevon + */ +public class ArrayIntegerRangeCondition implements IntegerRangeCondition { + + private final int[] fQuarkArray; + + /** + * {@link ArrayIntegerRangeCondition} from a collection + * + * @param quarks + * Collection of integers. + */ + public ArrayIntegerRangeCondition(Collection<@NonNull Integer> quarks) { + if (quarks.isEmpty()) { + throw new IllegalArgumentException("QuarkArrayRangeCondition requires a non empty collection"); //$NON-NLS-1$ + } + fQuarkArray = new int[quarks.size()]; + int i = 0; + for (Integer quark : quarks) { + fQuarkArray[i] = quark; + i++; + } + Arrays.sort(fQuarkArray); + } + + /** + * internal sub condition constructor + * + * @param intArray + * a sorted array of integers. + */ + private ArrayIntegerRangeCondition(int[] intArray) { + fQuarkArray = intArray; + } + + @Override + public int min() { + return fQuarkArray[0]; + } + + @Override + public int max() { + return fQuarkArray[fQuarkArray.length - 1]; + } + + @Override + public boolean test(int element) { + return Arrays.binarySearch(fQuarkArray, element) >= 0; + } + + @Override + public boolean intersects(int low, int high) { + int lowIndex = Arrays.binarySearch(fQuarkArray, low); + if (lowIndex >= 0) { + // low is one of the quarks. + return true; + } + if (lowIndex == -fQuarkArray.length - 1) { + // low is higher than the maximum quark + return false; + } + int highIndex = Arrays.binarySearch(fQuarkArray, high); + if (highIndex >= 0) { + // high is one of the quarks + return true; + } + if (highIndex == -1) { + // high is smaller than the minimum quark + return false; + } + // there is a quark between low and high + return highIndex < lowIndex; + } + + @Override + public @Nullable IntegerRangeCondition subCondition(int from, int to) { + int fromIndex = Arrays.binarySearch(fQuarkArray, from); + if (fromIndex == -fQuarkArray.length - 1) { + // from is larger than than the maximum quark + return null; + } + int toIndex = Arrays.binarySearch(fQuarkArray, to); + if (toIndex == -1) { + // to is smaller than the minimum quark + return null; + } + fromIndex = (fromIndex >= 0) ? fromIndex : -fromIndex - 1; + toIndex = (toIndex >= 0) ? toIndex + 1 : -toIndex - 1; + if (toIndex <= fromIndex) { + return null; + } + return new ArrayIntegerRangeCondition(Arrays.copyOfRange(fQuarkArray, fromIndex, toIndex)); + } + +} diff --git a/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayTimeRangeCondition.java b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayTimeRangeCondition.java new file mode 100644 index 0000000000..6f9d0171db --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/datastore/core/condition/ArrayTimeRangeCondition.java @@ -0,0 +1,116 @@ +/******************************************************************************* + * Copyright (c) 2017 École Polytechnique de Montréal + * + * 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.datastore.core.condition; + +import java.util.Arrays; +import java.util.Collection; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; + +/** + * Primitive array backed time range condition + * + * @author Loic Prieur-Drevon + */ +public class ArrayTimeRangeCondition implements TimeRangeCondition { + + private final long[] fTimeArray; + + /** + * {@link ArrayTimeRangeCondition} from a collection + * + * @param times + * Collection of longs representing times. + */ + public ArrayTimeRangeCondition(Collection<@NonNull Long> times) { + if (times.isEmpty()) { + throw new IllegalArgumentException("QuarkArrayRangeCondition requires a non empty collection"); //$NON-NLS-1$ + } + fTimeArray = new long[times.size()]; + int i = 0; + for (Long quark : times) { + fTimeArray[i] = quark; + i++; + } + Arrays.sort(fTimeArray); + } + + /** + * internal sub condition constructor + * + * @param timeArray + * a sorted array of times. + */ + private ArrayTimeRangeCondition(long[] timeArray) { + fTimeArray = timeArray; + } + + @Override + public long min() { + return fTimeArray[0]; + } + + @Override + public long max() { + return fTimeArray[fTimeArray.length - 1]; + } + + @Override + public boolean test(long element) { + return Arrays.binarySearch(fTimeArray, element) >= 0; + } + + @Override + public boolean intersects(long low, long high) { + int lowIndex = Arrays.binarySearch(fTimeArray, low); + if (lowIndex >= 0) { + // low is one of the quarks. + return true; + } + if (lowIndex == -fTimeArray.length - 1) { + // low is higher than the maximum quark + return false; + } + int highIndex = Arrays.binarySearch(fTimeArray, high); + if (highIndex >= 0) { + // high is one of the quarks + return true; + } + if (highIndex == -1) { + // high is smaller than the minimum quark + return false; + } + // there is a quark between low and high + return highIndex < lowIndex; + } + + @Override + public @Nullable TimeRangeCondition subCondition(long from, long to) { + int fromIndex = Arrays.binarySearch(fTimeArray, from); + if (fromIndex == -fTimeArray.length - 1) { + // from is larger than than the maximum quark + return null; + } + int toIndex = Arrays.binarySearch(fTimeArray, to); + if (toIndex == -1) { + // to is smaller than the minimum quark + return null; + } + fromIndex = (fromIndex >= 0) ? fromIndex : -fromIndex - 1; + toIndex = (toIndex >= 0) ? toIndex + 1 : -toIndex - 1; + if (toIndex <= fromIndex) { + return null; + } + return new ArrayTimeRangeCondition(Arrays.copyOfRange(fTimeArray, fromIndex, toIndex)); + } + +} diff --git a/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/IntegerRangeCondition.java b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/IntegerRangeCondition.java new file mode 100644 index 0000000000..41f8c7ce5c --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/IntegerRangeCondition.java @@ -0,0 +1,91 @@ +/******************************************************************************* + * Copyright (c) 2017 École Polytechnique de Montréal + * + * 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.provisional.datastore.core.condition; + +import java.util.Collection; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.internal.datastore.core.condition.ArrayIntegerRangeCondition; + +/** + * A range condition specific for integer ranges. It allows to work with int + * primitive types, which provides much better performances + * + * @author Loic Prieur-Drevon + */ +public interface IntegerRangeCondition { + + /** + * Get the lower bound of this range + * + * @return the lowest acceptable value for this condition. + */ + int min(); + + /** + * Get the upper bound of this range + * + * @return the highest acceptable value for this condition. + */ + int max(); + + /** + * Test whether a value is within this specific range boundaries. If the + * range is continuous, it will return true if the value is + * between the lower and upper bounds. If the range is discrete, it will + * return true if the requested element is one of the elements + * in the discrete range. + * + * @param element + * value that we want to test + * @return true if element is contained in this condition's set or range + */ + boolean test(int element); + + /** + * Determine if the current range intersects a ranged bounded by the values + * in parameter + * + * @param low + * interval's lower bound + * @param high + * interval's upper bound + * @return true if this element intersects the range's condition or any of + * the set's elements + */ + boolean intersects(int low, int high); + + /** + * Reduce the Condition to elements or the range within bounds from and to. + * null is returned if the resulting condition is empty. + * + * @param from + * lower bound for the condition reduction. + * @param to + * upper bound for the condition reduction. + * @return the reduced condition or null if the reduced + * condition does not contain any element + */ + @Nullable IntegerRangeCondition subCondition(int from, int to); + + /** + * Get a range condition representing a discrete quark range. + * + * @param values + * Collection of distinct integers, needs to be distinct but not + * sorted. + * @return The corresponding range condition + */ + static IntegerRangeCondition forDiscreteRange(Collection<@NonNull Integer> values) { + return new ArrayIntegerRangeCondition(values); + } + +} diff --git a/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/TimeRangeCondition.java b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/TimeRangeCondition.java index 80184b2df8..2ea492783a 100644 --- a/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/TimeRangeCondition.java +++ b/statesystem/org.eclipse.tracecompass.datastore.core/src/org/eclipse/tracecompass/internal/provisional/datastore/core/condition/TimeRangeCondition.java @@ -9,9 +9,13 @@ package org.eclipse.tracecompass.internal.provisional.datastore.core.condition; +import java.util.Collection; + +import org.eclipse.jdt.annotation.NonNull; import org.eclipse.jdt.annotation.Nullable; import org.eclipse.tracecompass.internal.datastore.core.condition.ContinuousTimeRangeCondition; import org.eclipse.tracecompass.internal.datastore.core.condition.SingletonTimeRangeCondition; +import org.eclipse.tracecompass.internal.datastore.core.condition.ArrayTimeRangeCondition; /** * A range condition specific for time ranges. It allows to work with long @@ -77,7 +81,8 @@ public interface TimeRangeCondition { /** * Get a condition of a single element. * - * @param elem The single element + * @param elem + * The single element * @return The corresponding range condition */ static TimeRangeCondition singleton(long elem) { @@ -96,9 +101,21 @@ public interface TimeRangeCondition { */ static TimeRangeCondition forContinuousRange(long bound1, long bound2) { if (bound2 < bound1) { - throw new IllegalArgumentException("Continuous time range condition: lower bound (" + bound1 +") should be <= upper bound (" + bound2 + ')'); //$NON-NLS-1$//$NON-NLS-2$ + throw new IllegalArgumentException("Continuous time range condition: lower bound (" + bound1 + ") should be <= upper bound (" + bound2 + ')'); //$NON-NLS-1$//$NON-NLS-2$ } return new ContinuousTimeRangeCondition(bound1, bound2); } + /** + * Get a range condition representing a discrete time range. + * + * @param times + * Collection of distinct time sets, needs to be distinct, not + * sorted. + * @return The corresponding range condition + */ + static TimeRangeCondition forDiscreteRange(Collection<@NonNull Long> times) { + return new ArrayTimeRangeCondition(times); + } + } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/StateSystem2DTest.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/StateSystem2DTest.java new file mode 100644 index 0000000000..3df4630d64 --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/StateSystem2DTest.java @@ -0,0 +1,221 @@ +/******************************************************************************* + * Copyright (c) 2016 École Polytechnique de Montréal + * + * 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.statesystem.core.tests; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +import java.io.File; +import java.io.IOException; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Set; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.common.core.NonNullUtils; +import org.eclipse.tracecompass.statesystem.core.ITmfStateSystem; +import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; +import org.eclipse.tracecompass.statesystem.core.StateSystemFactory; +import org.eclipse.tracecompass.statesystem.core.StateSystemUtils; +import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; +import org.eclipse.tracecompass.statesystem.core.backend.StateHistoryBackendFactory; +import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException; +import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; +import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException; +import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; +import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; + +import org.junit.After; +import org.junit.Before; +import org.junit.Test; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Multimap; +import com.google.common.collect.Ordering; +import com.google.common.collect.TreeMultimap; + +/** + * Test the 2D State System queries + * + * @author Loïc Prieur-Drevon + */ +public class StateSystem2DTest { + + private static final long START_TIME = 50L; + private static final @NonNull String STRING_ATTRIBUTE = "String"; + private static final @NonNull String INTEGER_ATTRIBUTE = "Integer"; + + private ITmfStateSystemBuilder fStateSystem; + + /** + * Build a small state history tree + */ + @Before + public void setupStateSystem() { + try { + IStateHistoryBackend backend = null; + try { + backend = StateHistoryBackendFactory.createHistoryTreeBackendNewFile("test", + NonNullUtils.checkNotNull(File.createTempFile("2Dtest", "ht")), 0, START_TIME, 0); + } catch (IOException e) { + fail(e.getMessage()); + } + fStateSystem = StateSystemFactory.newStateSystem(NonNullUtils.checkNotNull(backend)); + int stringQuark = fStateSystem.getQuarkAbsoluteAndAdd(STRING_ATTRIBUTE); + int integerQuark = fStateSystem.getQuarkAbsoluteAndAdd(INTEGER_ATTRIBUTE); + + fStateSystem.modifyAttribute(60L, TmfStateValue.newValueString("String1"), stringQuark); + fStateSystem.modifyAttribute(70L, TmfStateValue.newValueInt(0), integerQuark); + fStateSystem.modifyAttribute(80L, TmfStateValue.newValueInt(1), integerQuark); + fStateSystem.modifyAttribute(90L, TmfStateValue.newValueString("String2"), stringQuark); + fStateSystem.modifyAttribute(100L, TmfStateValue.newValueInt(2), integerQuark); + fStateSystem.modifyAttribute(110L, TmfStateValue.newValueInt(3), integerQuark); + fStateSystem.modifyAttribute(130L, TmfStateValue.newValueString("String3"), stringQuark); + fStateSystem.modifyAttribute(140L, TmfStateValue.newValueString("String4"), stringQuark); + fStateSystem.modifyAttribute(160L, TmfStateValue.newValueInt(4), integerQuark); + + fStateSystem.closeHistory(200L); + } catch (StateValueTypeException e) { + fail(e.getMessage()); + } + } + + /** + * Clean-up + */ + @After + public void tearDown() { + fStateSystem.dispose(); + fStateSystem.removeFiles(); + } + + private static void testContinuous(Iterable iterable, Collection quarks, long start, long end, int totalCount) { + Multimap treeMap = TreeMultimap.create(Comparator.naturalOrder(), + Comparator.comparing(ITmfStateInterval::getStartTime)); + + /* Assert that intervals are distinct and sort them */ + iterable.forEach(interval -> assertTrue(treeMap.put(interval.getAttribute(), interval))); + /* Check the number of distinct elements */ + assertEquals(totalCount, treeMap.size()); + /* There should only be as many Sets of intervals as quarks */ + assertEquals(quarks.size(), treeMap.keySet().size()); + + for (Integer quark : quarks) { + Collection orderedSet = treeMap.get(quark); + /* There should be intervals for this quark */ + assertTrue(!orderedSet.isEmpty()); + ITmfStateInterval previous = null; + for (ITmfStateInterval interval : orderedSet) { + if (previous == null) { + /* Assert that the first interval intersects start. */ + assertTrue(interval.intersects(start)); + } else { + /* + * Assert that this interval is contiguous to the previous + * one. + */ + assertEquals(previous.getEndTime() + 1, interval.getStartTime()); + } + previous = interval; + } + /* Assert that the last interval intersects end. */ + assertNotNull(previous); + assertTrue(previous.intersects(end)); + } + } + + /** + * Test the continuous 2D query method. + */ + @Test + public void testContinuous2DQuery() { + ITmfStateSystem ss = fStateSystem; + assertNotNull(ss); + long end = ss.getCurrentEndTime(); + + try { + /* Make sure all and only the String intervals are returned */ + int stringQuark = fStateSystem.getQuarkAbsolute(STRING_ATTRIBUTE); + Iterable iterable = ss.query2D(Collections.singleton(stringQuark), START_TIME, end); + testContinuous(iterable, Collections.singleton(stringQuark), START_TIME, end, 5); + + /* Make sure all and only the Integer intervals are returned */ + int integerQuark = fStateSystem.getQuarkAbsolute(INTEGER_ATTRIBUTE); + iterable = ss.query2D(Collections.singleton(integerQuark), START_TIME, end); + testContinuous(iterable, Collections.singleton(integerQuark), START_TIME, end, 6); + + /* Make sure all intervals are returned */ + Collection quarks = ImmutableList.of(stringQuark, integerQuark); + iterable = ss.query2D(quarks, START_TIME, end); + testContinuous(iterable, quarks, START_TIME, end, 11); + } catch (AttributeNotFoundException | StateSystemDisposedException e) { + fail(e.getMessage()); + } + } + + private static void testDiscrete(Iterable iterable, Collection quarks, Collection times, int totalCount) { + Set set = new HashSet<>(); + int countTimeStamps = 0; + + for (ITmfStateInterval interval : iterable) { + assertTrue(quarks.contains(interval.getAttribute())); + + /* Assert that intervals are distinct */ + assertTrue(set.add(interval)); + + /* Count how many time stamps this interval overlaps. */ + int timeStamps = (int) times.stream().filter(interval::intersects).count(); + assertTrue(timeStamps > 0); + countTimeStamps += timeStamps; + } + + /* Check the number of distinct elements */ + assertEquals(totalCount, set.size()); + /* Check that all time stamps are covered */ + assertEquals(times.size() * quarks.size(), countTimeStamps); + } + + /** + * Test the discrete 2D query method. + */ + @Test + public void testDiscrete2DQuery() { + ITmfStateSystem ss = fStateSystem; + assertNotNull(ss); + long end = ss.getCurrentEndTime(); + Collection times = StateSystemUtils.getTimes(START_TIME, end, 30L); + assertEquals(6, times.size()); + assertTrue(Ordering.natural().isStrictlyOrdered(times)); + + try { + /* Make sure all and only the String intervals are returned */ + int stringQuark = fStateSystem.getQuarkAbsolute(STRING_ATTRIBUTE); + Iterable iterable = ss.query2D(Collections.singleton(stringQuark), times); + testDiscrete(iterable, Collections.singleton(stringQuark), times, 4); + + /* Make sure all and only the Integer intervals are returned */ + int integerQuark = fStateSystem.getQuarkAbsolute(INTEGER_ATTRIBUTE); + iterable = ss.query2D(Collections.singleton(integerQuark), times); + testDiscrete(iterable, Collections.singleton(integerQuark), times, 4); + + /* Make sure all intervals are returned */ + Collection quarks = ImmutableList.of(stringQuark, integerQuark); + iterable = ss.query2D(quarks, times); + testDiscrete(iterable, quarks, times, 8); + } catch (AttributeNotFoundException | StateSystemDisposedException e) { + fail(e.getMessage()); + } + } + +} diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/.settings/.api_filters b/statesystem/org.eclipse.tracecompass.statesystem.core/.settings/.api_filters new file mode 100644 index 0000000000..e2661020bf --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/.settings/.api_filters @@ -0,0 +1,19 @@ + + + + + + + + + + + + + + + + + + + diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF b/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF index f8c99811c9..6ff5d6783c 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF @@ -2,7 +2,7 @@ Manifest-Version: 1.0 Bundle-ManifestVersion: 2 Bundle-Name: %Bundle-Name Bundle-Vendor: %Bundle-Vendor -Bundle-Version: 2.2.0.qualifier +Bundle-Version: 2.3.0.qualifier Bundle-Localization: plugin Bundle-SymbolicName: org.eclipse.tracecompass.statesystem.core;singleton:=true Bundle-Activator: org.eclipse.tracecompass.internal.statesystem.core.Activator @@ -23,6 +23,7 @@ Export-Package: org.eclipse.tracecompass.internal.provisional.statesystem.core.s org.eclipse.tracecompass.statesystem.core.interval, org.eclipse.tracecompass.statesystem.core.statevalue Import-Package: com.google.common.annotations;version="15.0.0", + com.google.common.base, com.google.common.cache, com.google.common.collect;version="12.0.0", org.apache.commons.lang3.builder;version="3.1.0" diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java index d2a0e55759..5c607b08ed 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java @@ -1,7 +1,5 @@ /******************************************************************************* - * Copyright (c) 2012, 2016 Ericsson - * Copyright (c) 2010, 2011 École Polytechnique de Montréal - * Copyright (c) 2010, 2011 Alexandre Montplaisir + * Copyright (c) 2012, 2017 Ericsson 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 @@ -19,6 +17,7 @@ import java.io.File; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; +import java.util.Collection; import java.util.LinkedList; import java.util.List; import java.util.concurrent.CountDownLatch; @@ -31,6 +30,8 @@ import org.eclipse.jdt.annotation.Nullable; import org.eclipse.tracecompass.common.core.log.TraceCompassLog; import org.eclipse.tracecompass.common.core.log.TraceCompassLogUtils; import org.eclipse.tracecompass.common.core.log.TraceCompassLogUtils.ScopeLog; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException; @@ -44,6 +45,7 @@ import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; import com.google.common.collect.ImmutableCollection.Builder; import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Iterables; /** * This is the core class of the Generic State System. It contains all the @@ -55,7 +57,7 @@ import com.google.common.collect.ImmutableSet; * inserting intervals, or the storage backend will have no way of knowing it * can close and write itself to disk, and its thread will keep running. * - * @author alexmont + * @author Alexandre Montplaisir * */ public class StateSystem implements ITmfStateSystemBuilder { @@ -610,6 +612,45 @@ public class StateSystem implements ITmfStateSystemBuilder { } } + @Override + public Iterable<@NonNull ITmfStateInterval> query2D(Collection<@NonNull Integer> quarks, Collection<@NonNull Long> times) + throws StateSystemDisposedException, TimeRangeException, IndexOutOfBoundsException { + if (isDisposed) { + throw new StateSystemDisposedException(); + } + + TimeRangeCondition timeCondition = TimeRangeCondition.forDiscreteRange(times); + return query2D(quarks, timeCondition); + } + + @Override + public Iterable<@NonNull ITmfStateInterval> query2D(Collection<@NonNull Integer> quarks, long start, long end) + throws StateSystemDisposedException, TimeRangeException, IndexOutOfBoundsException { + if (isDisposed) { + throw new StateSystemDisposedException(); + } + + TimeRangeCondition timeCondition = TimeRangeCondition.forContinuousRange(start, end); + return query2D(quarks, timeCondition); + } + + private Iterable<@NonNull ITmfStateInterval> query2D(@NonNull Collection<@NonNull Integer> quarks, TimeRangeCondition timeCondition) + throws TimeRangeException, IndexOutOfBoundsException { + if (timeCondition.min() < getStartTime()) { + throw new TimeRangeException(); + } + + IntegerRangeCondition quarkCondition = IntegerRangeCondition.forDiscreteRange(quarks); + if (quarkCondition.min() < 0 || quarkCondition.max() >= getNbAttributes()) { + throw new IndexOutOfBoundsException(); + } + + Iterable<@NonNull ITmfStateInterval> transStateIterable = transState.query2D(quarks, timeCondition); + Iterable<@NonNull ITmfStateInterval> backendIterable = backend.query2D(quarkCondition, timeCondition); + + return Iterables.concat(transStateIterable, backendIterable); + } + @Override public void removeFiles() { backend.removeFiles(); diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/TransientState.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/TransientState.java index 6a013366bd..c384ecbfdd 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/TransientState.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/TransientState.java @@ -17,11 +17,14 @@ package org.eclipse.tracecompass.internal.statesystem.core; import java.io.PrintWriter; import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; import java.util.List; import java.util.concurrent.locks.ReentrantReadWriteLock; import org.eclipse.jdt.annotation.NonNullByDefault; import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; @@ -355,6 +358,37 @@ public class TransientState { } } + /** + * Generalized 2D iterable query method. Iterates over intervals that match + * the conditions on quarks and times in the Transient State. + * + * @param quarks + * Collection of quarks for returned intervals. + * @param timeCondition + * Condition on the times for returned intervals + * @return An iterable over the queried intervals, ordered by quarks. + * @since 2.1 + */ + public Iterable query2D(Collection quarks, TimeRangeCondition timeCondition) { + fRWLock.readLock().lock(); + try { + if (!fIsActive) { + return Collections.EMPTY_LIST; + } + long end = timeCondition.max(); + Collection iterable = new ArrayList<>(); + for (Integer quark : quarks) { + ITmfStateInterval interval = getIntervalAt(end, quark); + if (interval != null) { + iterable.add(interval); + } + } + return iterable; + } finally { + fRWLock.readLock().unlock(); + } + } + /** * Close off the Transient State, used for example when we are done reading * a static trace file. All the information currently contained in it will diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/InMemoryBackend.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/InMemoryBackend.java index e5505c3ea5..a87272b75e 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/InMemoryBackend.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/InMemoryBackend.java @@ -20,10 +20,11 @@ import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.NavigableSet; -import java.util.SortedSet; import java.util.TreeSet; import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; @@ -31,6 +32,8 @@ import org.eclipse.tracecompass.statesystem.core.interval.TmfStateInterval; import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; +import com.google.common.collect.Iterables; + /** * State history back-end that stores its intervals in RAM only. It cannot be * saved to disk, which means we need to rebuild it every time we re-open a @@ -45,36 +48,8 @@ import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; */ public class InMemoryBackend implements IStateHistoryBackend { - /** - * We need to compare the end time and the attribute, because we can have 2 - * intervals with the same end time (for different attributes). And TreeSet - * needs a unique "key" per element. - */ - private static final Comparator END_COMPARATOR = - new Comparator() { - @Override - public int compare(ITmfStateInterval o1, ITmfStateInterval o2) { - final long e1 = o1.getEndTime(); - final long e2 = o2.getEndTime(); - final int a1 = o1.getAttribute(); - final int a2 = o2.getAttribute(); - if (e1 < e2) { - return -1; - } else if (e1 > e2) { - return 1; - } else if (a1 < a2) { - return -1; - } else if (a1 > a2) { - return 1; - } else { - return 0; - } - } - - }; - private final @NonNull String ssid; - private final NavigableSet intervals; + private final NavigableSet<@NonNull ITmfStateInterval> intervals; private final long startTime; private volatile long latestTime; @@ -91,7 +66,14 @@ public class InMemoryBackend implements IStateHistoryBackend { this.ssid = ssid; this.startTime = startTime; this.latestTime = startTime; - this.intervals = new TreeSet<>(END_COMPARATOR); + /** + * We need to compare the end time and the attribute, because we can + * have 2 intervals with the same end time (for different attributes). + * And TreeSet needs a unique "key" per element. + */ + this.intervals = new TreeSet<>(Comparator + .comparing(ITmfStateInterval::getEndTime) + .thenComparing(ITmfStateInterval::getAttribute)); } @Override @@ -142,7 +124,7 @@ public class InMemoryBackend implements IStateHistoryBackend { * the first possible interval, then only compare their start times. */ synchronized (intervals) { - Iterator iter = searchforEndTime(intervals, t); + Iterator iter = searchforEndTime(intervals, 0, t).iterator(); for (int modCount = 0; iter.hasNext() && modCount < currentStateInfo.size();) { ITmfStateInterval entry = iter.next(); final long entryStartTime = entry.getStartTime(); @@ -167,9 +149,8 @@ public class InMemoryBackend implements IStateHistoryBackend { * the first possible interval, then only compare their start times. */ synchronized (intervals) { - Iterator iter = searchforEndTime(intervals, t); - while (iter.hasNext()) { - ITmfStateInterval entry = iter.next(); + Iterable iter = searchforEndTime(intervals, attributeQuark, t); + for (ITmfStateInterval entry : iter) { final boolean attributeMatches = (entry.getAttribute() == attributeQuark); final long entryStartTime = entry.getStartTime(); if (attributeMatches) { @@ -184,10 +165,7 @@ public class InMemoryBackend implements IStateHistoryBackend { } private boolean checkValidTime(long t) { - if (t >= startTime && t <= latestTime) { - return true; - } - return false; + return (t >= startTime && t <= latestTime); } @Override @@ -223,16 +201,19 @@ public class InMemoryBackend implements IStateHistoryBackend { /* Nothing to do */ } - private static Iterator searchforEndTime(NavigableSet tree, long time) { - ITmfStateInterval dummyInterval = new TmfStateInterval(-1, time, -1, TmfStateValue.nullValue()); - ITmfStateInterval myInterval = tree.lower(dummyInterval); - if (myInterval == null) { - return tree.iterator(); + private static Iterable<@NonNull ITmfStateInterval> searchforEndTime(NavigableSet<@NonNull ITmfStateInterval> tree, int quark, long time) { + ITmfStateInterval dummyInterval = new TmfStateInterval(-1, time, quark, TmfStateValue.nullValue()); + return tree.tailSet(dummyInterval); + } + + @Override + public Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarks, TimeRangeCondition times) + throws TimeRangeException { + synchronized (intervals) { + return Iterables.filter(searchforEndTime(intervals, quarks.min(), times.min()), + interval -> quarks.test(interval.getAttribute()) + && times.intersects(interval.getStartTime(), interval.getEndTime())); } - final SortedSet tailSet = tree.tailSet(myInterval); - Iterator retVal = tailSet.iterator(); - retVal.next(); - return retVal; } } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/NullBackend.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/NullBackend.java index 33a0781d73..9fd193c026 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/NullBackend.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/NullBackend.java @@ -14,10 +14,14 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend; import java.io.File; import java.io.FileInputStream; +import java.util.Collections; import java.util.List; import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; +import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; @@ -116,4 +120,10 @@ public class NullBackend implements IStateHistoryBackend { /* Cannot do past queries */ return null; } + + @Override + public Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarks, + TimeRangeCondition times) throws TimeRangeException { + return Collections.EMPTY_LIST; + } } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java index 776dd44633..543dc55c53 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java @@ -26,6 +26,8 @@ import java.util.List; import java.util.concurrent.locks.ReentrantReadWriteLock; import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; @@ -505,6 +507,31 @@ public abstract class HTNode { } } + /** + * 2D query method, returns an iterable over the intervals for the desired + * quarks and times. + * + * @param quarks + * NumCondition on the quarks on which we want information + * @param times + * NumCondition on the times on which we want information + * @return an Iterable over intervals that match conditions. + */ + public Iterable iterable2D(IntegerRangeCondition quarks, TimeRangeCondition times) { + fRwl.readLock().lock(); + try { + if (getNodeStart() > getNodeEnd()) { + return Collections.emptyList(); + } + long start = times.min(); + return Iterables.filter(fIntervals.subList(getStartIndexFor(start), fIntervals.size()), + interval -> quarks.test(interval.getAttribute()) + && times.intersects(interval.getStartTime(), interval.getEndTime())); + } finally { + fRwl.readLock().unlock(); + } + } + private int getStartIndexFor(long t) throws TimeRangeException { /* Should only be called by methods with the readLock taken */ @@ -671,4 +698,5 @@ public abstract class HTNode { * @return A string representing the node */ protected abstract String toStringSpecific(); + } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java index 5e752deeb9..61419a7b84 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java @@ -19,6 +19,7 @@ import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.nio.channels.ClosedChannelException; +import java.util.Collections; import java.util.Deque; import java.util.LinkedList; import java.util.List; @@ -26,6 +27,8 @@ import java.util.logging.Logger; import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.common.core.log.TraceCompassLog; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.internal.statesystem.core.Activator; import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; @@ -35,6 +38,7 @@ import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; import com.google.common.annotations.VisibleForTesting; +import com.google.common.collect.Iterables; /** * History Tree backend for storing a state history. This is the basic version @@ -341,6 +345,46 @@ public class HistoryTreeBackend implements IStateHistoryBackend { return interval; } + @Override + public Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarks, TimeRangeCondition times) + throws TimeRangeException { + /* Get a flattened Iterable of nodes that match the conditions */ + Iterable nodes = flatten(getSHT().getRootNode(), quarks, times); + /* + * Transform them into the iterables over their intervals that match the + * conditions. + */ + Iterable> iterables = Iterables.transform(nodes, + n -> n.iterable2D(quarks, times)); + return Iterables.concat(iterables); + } + + private Iterable flatten(HTNode node, IntegerRangeCondition quarks, TimeRangeCondition times) { + if (node.getNodeType() == HTNode.NodeType.LEAF) { + return Collections.singleton(node); + } + ParentNode parent = (ParentNode) node; + /* Reduce the condition to this node's bounds. */ + if (node.getNodeStart() > node.getNodeEnd()) { + return Collections.emptyList(); + } + TimeRangeCondition subTimes = times.subCondition(node.getNodeStart(), node.getNodeEnd()); + /* + * Transform the children's sequence numbers into the children's + * flattened subtrees. + */ + Iterable> children = Iterables.transform(parent.selectNextChildren2D(quarks, subTimes), seqNum -> { + try { + /* Recursive call to flatten children */ + return flatten(getSHT().readNode(seqNum), quarks, subTimes); + } catch (ClosedChannelException e) { + return null; + } + }); + /* BFS */ + return Iterables.concat(Collections.singleton(node), Iterables.concat(children)); + } + /** * Return the size of the tree history file * diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java index 15003bdf4a..1c7bbc47ef 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java @@ -10,7 +10,10 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; import java.util.Collection; + import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; /** @@ -20,6 +23,7 @@ import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; * * @author Alexandre Montplaisir * @author Florian Wininger + * @author Loïc Prieur-Drevon */ public abstract class ParentNode extends HTNode { @@ -93,4 +97,18 @@ public abstract class ParentNode extends HTNode { */ public abstract @NonNull Collection<@NonNull Integer> selectNextChildren(long t); + /** + * Get a collection of sequence numbers for the children nodes that contain + * intervals with quarks from quarks, and times intersecting times from + * times. + * + * @param quarks + * NumCondition on the quarks we are interested in. + * @param subTimes + * NumCondition on the time stamps we are interested in. + * @return a collection of the sequence numbers for the children that match + * the conditions. + */ + public abstract Collection selectNextChildren2D(IntegerRangeCondition quarks, TimeRangeCondition subTimes); + } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java index f55141f01c..9f66ef0836 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java @@ -20,6 +20,8 @@ import java.util.List; import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.common.core.collect.BufferedBlockingQueue; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.internal.statesystem.core.Activator; import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; @@ -27,6 +29,8 @@ import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; +import com.google.common.collect.Iterables; + /** * Variant of the HistoryTreeBackend which runs all the interval-insertion logic * in a separate thread. @@ -288,4 +292,19 @@ public final class ThreadedHistoryTreeBackend extends HistoryTreeBackend return super.doSingularQuery(t, attributeQuark); } + @Override + public Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarks, TimeRangeCondition times) + throws TimeRangeException { + /* + * There can still be intervals in the queue, search the + * HistoryTreeBackend, then the queue for the intervals we need. + * Iterables will lazily evaluate the BBQ only once the + * HistoryTreeBackend is consumed and if the construction still isn't + * done. + */ + Iterable<@NonNull HTInterval> queuedIntervals = Iterables.filter(intervalQueue, + interval -> !isFinishedBuilding() && quarks.test(interval.getAttribute()) + && times.intersects(interval.getStartTime(), interval.getEndTime())); + return Iterables.concat(super.query2D(quarks, times), queuedIntervals); + } } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java index 946c8bffc1..f9fc14b21a 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java @@ -14,11 +14,15 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic; import java.nio.ByteBuffer; +import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; +import java.util.List; import java.util.concurrent.locks.ReentrantReadWriteLock; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.ParentNode; @@ -167,6 +171,36 @@ public final class CoreNode extends ParentNode { } } + /** + * Get the end time for this child, the last child's end time will be + * Long.MAX_VALUE if it isn't written to disk. + * + * @param index + * child position in this Parent + * @return the next child's endTime + */ + private long getChildEnd(int index) { + rwl.readLock().lock(); + try { + /* + * If this is not the last child, we can deduce its end time from + * the following child. + */ + if (index < nbChildren - 1) { + return childStart[index + 1] - 1; + } + /* + * If it is the last child, it will have the same end time as its + * parent. However that time is unknown if the node isn't written to + * disk yet, so we return MAX_VALUE instead to avoid the query + * missing something. + */ + return isOnDisk() ? getNodeEnd() : Long.MAX_VALUE; + } finally { + rwl.readLock().unlock(); + } + } + /** * Get the sequence number of the extension to this node (if there is one). * @@ -224,6 +258,24 @@ public final class CoreNode extends ParentNode { } } + @Override + public Collection selectNextChildren2D(IntegerRangeCondition quarks, TimeRangeCondition times) { + rwl.readLock().lock(); + try { + /* Selectively search children */ + List list = new ArrayList<>(); + for (int child = 0; child < nbChildren; child++) { + if (times.intersects(getChildStart(child), getChildEnd(child))) { + int potentialNextSeqNb = getChild(child); + list.add(potentialNextSeqNb); + } + } + return list; + } finally { + rwl.readLock().unlock(); + } + } + @Override public NodeType getNodeType() { return NodeType.CORE; diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java index b9e0099247..96d52689d3 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java @@ -12,6 +12,7 @@ package org.eclipse.tracecompass.statesystem.core; +import java.util.Collection; import java.util.List; import org.eclipse.jdt.annotation.NonNull; @@ -436,4 +437,52 @@ public interface ITmfStateSystem { */ @NonNull ITmfStateInterval querySingleState(long t, int attributeQuark) throws StateSystemDisposedException; + + /** + * Multiple attribute and multiple times iterable query. Iterates over + * intervals from attributes in the quarks collection that intersect + * timestamps from the times collection with no guaranteed order. There may + * be duplicates during State System construction. + * + * @param quarks + * a collection of quarks for which we want information + * @param times + * the timestamps at which we want the states + * @return a lazily evaluated un-ordered iterable over the queried intervals + * @throws StateSystemDisposedException + * If the query is sent after the state system has been disposed + * @throws IndexOutOfBoundsException + * If the smallest attribute is <0 or if the largest is >= to + * the number of attributes. + * @throws TimeRangeException + * If the smallest time is before the state system start time. + * @since 2.3 + */ + Iterable<@NonNull ITmfStateInterval> query2D(@NonNull Collection quarks, + @NonNull Collection times) throws StateSystemDisposedException, IndexOutOfBoundsException, TimeRangeException; + + /** + * Multiple attribute and time range iterable query, Iterates over intervals + * from attributes in the quarks collection that intersect the [start, end] + * timerange with no guaranteed order. There may be duplicates during State + * System construction. + * + * @param quarks + * a collection of quarks for which we want information + * @param start + * lower bound for the query + * @param end + * upper bound for the query + * @return a lazily evaluated un-ordered iterable over the queried intervals + * @throws StateSystemDisposedException + * If the query is sent after the state system has been disposed + * @throws IndexOutOfBoundsException + * If the smallest attribute is <0 or if the largest is >= to + * the number of attributes. + * @throws TimeRangeException + * If the smallest time is before the state system start time. + * @since 2.3 + */ + Iterable<@NonNull ITmfStateInterval> query2D(@NonNull Collection quarks, + long start, long end) throws StateSystemDisposedException, IndexOutOfBoundsException, TimeRangeException; } \ No newline at end of file diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/StateSystemUtils.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/StateSystemUtils.java index df9b4e7030..80a15cae11 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/StateSystemUtils.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/StateSystemUtils.java @@ -286,7 +286,7 @@ public final class StateSystemUtils { * Iterator class to allow 2-way iteration over intervals of a given * attribute. Not thread-safe! * - * @since 2.2 + * @since 2.3 */ public static class QuarkIterator implements Iterator { @@ -393,4 +393,37 @@ public final class StateSystemUtils { } } + /** + * Build a sorted list of time stamps separated by resolution between + * bounds, including the upper bound. + * + * @param from + * lower bound of the list of time stamps. + * @param to + * upper bound of the list of time stamps. + * @param resolution + * positive duration between two consecutive time stamps. + * @return a sorted list of time stamps from start to end separated by + * resolution, or consecutive timestamps if resolution == 0. + * @throws IllegalArgumentException + * if end < start or resolution < 0. + * @since 2.3 + */ + public static List getTimes(long from, long to, long resolution) { + if (to < from || resolution < 0) { + throw new IllegalArgumentException(); + } + /* + * If resolution is 0, adjust increment to return consecutive + * timestamps. + */ + long increment = Math.max(resolution, 1L); + List times = new ArrayList<>((int) ((to - from) / increment + 1)); + for (long t = from; t < to; t += increment) { + times.add(t); + } + times.add(to); + return times; + } + } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/IStateHistoryBackend.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/IStateHistoryBackend.java index b36aa86ab5..7ae4cca1d6 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/IStateHistoryBackend.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/IStateHistoryBackend.java @@ -18,6 +18,8 @@ import java.util.List; import org.eclipse.jdt.annotation.NonNull; import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; +import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; @@ -181,4 +183,21 @@ public interface IStateHistoryBackend { ITmfStateInterval doSingularQuery(long t, int attributeQuark) throws TimeRangeException, StateSystemDisposedException; + /** + * Generalized 2D iterable query method. Iterates over intervals that match + * the conditions on quarks and times with no guaranteed order. + * + * @param quarkCondition + * Condition on the quarks for returned intervals. + * @param timeCondition + * Condition on the times for returned intervals + * @return An un-ordered iterable over the queried intervals + * @throws TimeRangeException + * if the time bounds are outside the range of the HistoryTree + * @since 2.3 + */ + default Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarkCondition, TimeRangeCondition timeCondition) + throws TimeRangeException { + throw new UnsupportedOperationException("This backend does not support 2D queries"); //$NON-NLS-1$ + } } -- 2.34.1