tmf: Fix in-memory backend to use a TreeSet insead of a list

The query performance is superior and it handles receiving different
attributes with different end times out of order. (within the spec)

Change-Id: Iba72f479455facedecacaadf695f943a6572f3d2
Signed-off-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Signed-off-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im>
Reviewed-on: https://git.eclipse.org/r/16816
Tested-by: Hudson CI

4 files changed, 328 insertions, 33 deletions

diff --git a/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/AllTmfCoreTests.java b/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/AllTmfCoreTests.java
index 7723e75a80..8f188d384c 100644
--- a/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/AllTmfCoreTests.java
+++ b/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/AllTmfCoreTests.java
@@ -28,6 +28,7 @@ import org.junit.runners.Suite;
     org.eclipse.linuxtools.tmf.core.tests.request.AllTests.class,
     org.eclipse.linuxtools.tmf.core.tests.signal.AllTests.class,
     org.eclipse.linuxtools.tmf.core.tests.statesystem.AllTests.class,
+    org.eclipse.linuxtools.tmf.core.tests.statesystem.backends.AllTests.class,
     org.eclipse.linuxtools.tmf.core.tests.statistics.AllTests.class,
     org.eclipse.linuxtools.tmf.core.tests.trace.AllTests.class,
     org.eclipse.linuxtools.tmf.core.tests.uml2sd.AllTests.class,
diff --git a/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/statesystem/backends/AllTests.java b/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/statesystem/backends/AllTests.java
new file mode 100644
index 0000000000..8d25a09e39
--- /dev/null
+++ b/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/statesystem/backends/AllTests.java
@@ -0,0 +1,27 @@
+/*******************************************************************************
+ * Copyright (c) 2013 Ericsson
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *   Alexandre Montplaisir - Initial API and implementation
+ ******************************************************************************/
+
+package org.eclipse.linuxtools.tmf.core.tests.statesystem.backends;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.Suite;
+
+/**
+ * Test suite for org.eclipse.linuxtools.tmf.core.statesystem
+ */
+@RunWith(Suite.class)
+@Suite.SuiteClasses({
+    InMemoryBackendTest.class
+})
+public class AllTests {
+
+}
\ No newline at end of file
diff --git a/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/statesystem/backends/InMemoryBackendTest.java b/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/statesystem/backends/InMemoryBackendTest.java
new file mode 100644
index 0000000000..7a8f5e3497
--- /dev/null
+++ b/lttng/org.eclipse.linuxtools.tmf.core.tests/src/org/eclipse/linuxtools/tmf/core/tests/statesystem/backends/InMemoryBackendTest.java
@@ -0,0 +1,244 @@
+/*******************************************************************************
+ * Copyright (c) 2013 Ericsson
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *   Matthew Khouzam - Initial API and implementation
+ ******************************************************************************/
+
+package org.eclipse.linuxtools.tmf.core.tests.statesystem.backends;
+
+import static org.junit.Assert.*;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.linuxtools.internal.tmf.core.statesystem.backends.InMemoryBackend;
+import org.eclipse.linuxtools.tmf.core.exceptions.AttributeNotFoundException;
+import org.eclipse.linuxtools.tmf.core.exceptions.StateValueTypeException;
+import org.eclipse.linuxtools.tmf.core.exceptions.TimeRangeException;
+import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval;
+import org.eclipse.linuxtools.tmf.core.interval.TmfStateInterval;
+import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+/**
+ * Test cases for the in-memory backend
+ *
+ * @author Matthew Khouzam
+ */
+public class InMemoryBackendTest {
+
+    private static final int NUMBER_OF_ATTRIBUTES = 10;
+    private static InMemoryBackend fixture;
+
+    /**
+     * Test setup. make a state system that is moderately large
+     */
+    @BeforeClass
+    public static void init() {
+        fixture = new InMemoryBackend(0);
+        for (int attribute = 0; attribute < NUMBER_OF_ATTRIBUTES; attribute++) {
+            for (int timeStart = 0; timeStart < 1000; timeStart++) {
+                try {
+                    final int stateEndTime = (timeStart * 100) + 90 + attribute;
+                    final int stateStartTime = timeStart * 100 + attribute;
+                    fixture.insertPastState(stateStartTime, stateEndTime, attribute, TmfStateValue.newValueInt(timeStart % 100));
+                    if (timeStart != 999) {
+                        fixture.insertPastState(stateEndTime + 1, stateEndTime + 9, attribute, TmfStateValue.nullValue());
+                    }
+                } catch (TimeRangeException e) {
+                    /* Should not happen here */
+                    throw new IllegalStateException();
+                }
+            }
+        }
+    }
+
+    private static void testInterval(ITmfStateInterval interval, int startTime,
+            int endTime, int value) {
+        assertNotNull(interval);
+        assertEquals(startTime, interval.getStartTime());
+        assertEquals(endTime, interval.getEndTime());
+        try {
+            assertEquals(value, interval.getStateValue().unboxInt());
+        } catch (StateValueTypeException e) {
+            fail(e.getMessage());
+        }
+    }
+
+
+    /**
+     * Test at start time
+     */
+    @Test
+    public void testStartTime() {
+        assertEquals(0, fixture.getStartTime());
+    }
+
+    /**
+     * Test at end time
+     */
+    @Test
+    public void testEndTime() {
+        assertEquals(99999, fixture.getEndTime());
+    }
+
+    /**
+     * Query the state system
+     */
+    @Test
+    public void testDoQuery() {
+        List<ITmfStateInterval> interval = new ArrayList<ITmfStateInterval>(NUMBER_OF_ATTRIBUTES);
+        for (int i = 0; i < NUMBER_OF_ATTRIBUTES; i++) {
+            interval.add(null);
+        }
+        try {
+            fixture.doQuery(interval, 950);
+        } catch (TimeRangeException e) {
+            fail(e.getMessage());
+        }
+
+        assertEquals(NUMBER_OF_ATTRIBUTES, interval.size());
+        testInterval(interval.get(0), 900, 990, 9);
+        testInterval(interval.get(1), 901, 991, 9);
+        testInterval(interval.get(2), 902, 992, 9);
+        testInterval(interval.get(3), 903, 993, 9);
+        testInterval(interval.get(4), 904, 994, 9);
+        testInterval(interval.get(5), 905, 995, 9);
+        testInterval(interval.get(6), 906, 996, 9);
+        testInterval(interval.get(7), 907, 997, 9);
+        testInterval(interval.get(8), 908, 998, 9);
+        testInterval(interval.get(9), 909, 999, 9);
+    }
+
+
+    /**
+     * Test single attribute then compare it to a full query
+     */
+    @Test
+    public void testQueryAttribute() {
+        try {
+            ITmfStateInterval interval[] = new TmfStateInterval[10];
+            for (int i = 0; i < 10; i++) {
+                interval[i] = fixture.doSingularQuery(950, i);
+            }
+
+            testInterval(interval[0], 900, 990, 9);
+            testInterval(interval[1], 901, 991, 9);
+            testInterval(interval[2], 902, 992, 9);
+            testInterval(interval[3], 903, 993, 9);
+            testInterval(interval[4], 904, 994, 9);
+            testInterval(interval[5], 905, 995, 9);
+            testInterval(interval[6], 906, 996, 9);
+            testInterval(interval[7], 907, 997, 9);
+            testInterval(interval[8], 908, 998, 9);
+            testInterval(interval[9], 909, 999, 9);
+
+            List<ITmfStateInterval> intervalQuery = new ArrayList<ITmfStateInterval>(NUMBER_OF_ATTRIBUTES);
+            for (int i = 0; i < NUMBER_OF_ATTRIBUTES; i++) {
+                intervalQuery.add(null);
+            }
+
+            fixture.doQuery(intervalQuery, 950);
+            ITmfStateInterval ref[] = intervalQuery.toArray(new ITmfStateInterval[0]);
+            assertArrayEquals(ref, interval);
+
+        } catch (TimeRangeException e) {
+            fail(e.getMessage());
+        } catch (AttributeNotFoundException e) {
+            fail(e.getMessage());
+        }
+    }
+
+    /**
+     * Test single attribute that should not exist
+     */
+    @Test
+    public void testQueryAttributeEmpty() {
+        try {
+            ITmfStateInterval interval = fixture.doSingularQuery(999, 0);
+            assertEquals(TmfStateValue.nullValue(), interval.getStateValue());
+
+        } catch (TimeRangeException e) {
+            fail(e.getMessage());
+        } catch (AttributeNotFoundException e) {
+            fail(e.getMessage());
+        }
+    }
+
+    /**
+     * Test first element in ss
+     */
+    @Test
+    public void testBegin() {
+        try {
+            ITmfStateInterval interval = fixture.doSingularQuery(0, 0);
+            assertEquals(0, interval.getStartTime());
+            assertEquals(90, interval.getEndTime());
+            assertEquals(0, interval.getStateValue().unboxInt());
+
+        } catch (TimeRangeException e) {
+            fail(e.getMessage());
+        } catch (AttributeNotFoundException e) {
+            fail(e.getMessage());
+        } catch (StateValueTypeException e) {
+            fail(e.getMessage());
+        }
+    }
+
+    /**
+     * Test last element in ss
+     */
+    @Test
+    public void testEnd() {
+        try {
+            ITmfStateInterval interval = fixture.doSingularQuery(99998, 9);
+            testInterval(interval, 99909, 99999, 99);
+
+        } catch (TimeRangeException e) {
+            fail(e.getMessage());
+        } catch (AttributeNotFoundException e) {
+            fail(e.getMessage());
+        }
+    }
+
+    /**
+     * Test out of range query
+     *
+     * @throws TimeRangeException
+     *             Expected
+     */
+    @Test(expected = TimeRangeException.class)
+    public void testOutOfRange_1() throws TimeRangeException {
+        try {
+            ITmfStateInterval interval = fixture.doSingularQuery(-1, 0);
+            assertNull(interval);
+
+        } catch (AttributeNotFoundException e) {
+            fail(e.getMessage());
+        }
+    }
+
+    /**
+     * Test out of range query
+     *
+     * @throws TimeRangeException
+     *             Expected
+     */
+    @Test(expected = TimeRangeException.class)
+    public void testOutOfRange_2() throws TimeRangeException {
+        try {
+            ITmfStateInterval interval = fixture.doSingularQuery(100000, 0);
+            assertNull(interval);
+
+        } catch (AttributeNotFoundException e) {
+            fail(e.getMessage());
+        }
+    }
+}
diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/backends/InMemoryBackend.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/backends/InMemoryBackend.java
index b4eedf3d1d..61d999613e 100644
--- a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/backends/InMemoryBackend.java
+++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/backends/InMemoryBackend.java
@@ -8,6 +8,7 @@
  *
  * Contributors:
  *   Alexandre Montplaisir - Initial API and implementation
+ *   Matthew Khouzam - Modified to use a TreeSet
  ******************************************************************************/
 
 package org.eclipse.linuxtools.internal.tmf.core.statesystem.backends;
@@ -15,15 +16,15 @@ package org.eclipse.linuxtools.internal.tmf.core.statesystem.backends;
 import java.io.File;
 import java.io.FileInputStream;
 import java.io.PrintWriter;
-import java.util.ArrayList;
-import java.util.Collections;
 import java.util.Comparator;
+import java.util.Iterator;
 import java.util.List;
+import java.util.SortedSet;
+import java.util.TreeSet;
 
 import org.eclipse.linuxtools.tmf.core.exceptions.AttributeNotFoundException;
 import org.eclipse.linuxtools.tmf.core.exceptions.TimeRangeException;
 import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval;
-import org.eclipse.linuxtools.tmf.core.interval.TmfIntervalEndComparator;
 import org.eclipse.linuxtools.tmf.core.interval.TmfStateInterval;
 import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue;
 
@@ -41,10 +42,35 @@ import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue;
  */
 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<ITmfStateInterval> END_COMPARATOR =
-            new TmfIntervalEndComparator();
+            new Comparator<ITmfStateInterval>() {
+                @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 List<ITmfStateInterval> intervals;
+            };
+
+    private final TreeSet<ITmfStateInterval> intervals;
     private final long startTime;
     private long latestTime;
 
@@ -57,7 +83,7 @@ public class InMemoryBackend implements IStateHistoryBackend {
     public InMemoryBackend(long startTime) {
         this.startTime = startTime;
         this.latestTime = startTime;
-        this.intervals = new ArrayList<ITmfStateInterval>();
+        this.intervals = new TreeSet<ITmfStateInterval>(END_COMPARATOR);
     }
 
     @Override
@@ -85,11 +111,10 @@ public class InMemoryBackend implements IStateHistoryBackend {
             latestTime = stateEndTime;
         }
 
-        /* Add the interval into the-array */
+        /* Add the interval into the tree */
         intervals.add(interval);
     }
 
-
     @Override
     public void doQuery(List<ITmfStateInterval> currentStateInfo, long t)
             throws TimeRangeException {
@@ -101,12 +126,15 @@ public class InMemoryBackend implements IStateHistoryBackend {
          * The intervals are sorted by end time, so we can binary search to get
          * the first possible interval, then only compare their start times.
          */
-        ITmfStateInterval entry;
-        for (int i = binarySearchEndTime(intervals, t); i < intervals.size(); i++) {
-            entry = intervals.get(i);
-            if (entry.getStartTime() <= t) {
+
+        Iterator<ITmfStateInterval> iter = serachforEndTime(intervals, t);
+        for (int modCount = 0; iter.hasNext() && modCount < currentStateInfo.size();) {
+            ITmfStateInterval entry = iter.next();
+            final long entryStartTime = entry.getStartTime();
+            if (entryStartTime <= t) {
                 /* Add this interval to the returned values */
                 currentStateInfo.set(entry.getAttribute(), entry);
+                modCount++;
             }
         }
     }
@@ -122,13 +150,17 @@ public class InMemoryBackend implements IStateHistoryBackend {
          * The intervals are sorted by end time, so we can binary search to get
          * the first possible interval, then only compare their start times.
          */
-        ITmfStateInterval entry;
-        for (int i = binarySearchEndTime(intervals, t); i < intervals.size(); i++) {
-            entry = intervals.get(i);
-            if (entry.getStartTime() <= t && entry.getAttribute() == attributeQuark) {
+        Iterator<ITmfStateInterval> iter = serachforEndTime(intervals, t);
+        while (iter.hasNext()) {
+            ITmfStateInterval entry = iter.next();
+            final boolean attributeMatches = (entry.getAttribute() == attributeQuark);
+            final long entryStartTime = entry.getStartTime();
+            if (attributeMatches) {
+                if (entryStartTime <= t) {
                     /* This is the droid we are looking for */
                     return entry;
                 }
+            }
         }
         throw new AttributeNotFoundException();
     }
@@ -179,25 +211,16 @@ public class InMemoryBackend implements IStateHistoryBackend {
         writer.println(intervals.toString());
     }
 
-    private static int binarySearchEndTime(List<ITmfStateInterval> list, long time) {
+    private static Iterator<ITmfStateInterval> serachforEndTime(TreeSet<ITmfStateInterval> tree, long time) {
         ITmfStateInterval dummyInterval = new TmfStateInterval(-1, time, -1, null);
-        int mid = Collections.binarySearch(list, dummyInterval, END_COMPARATOR);
-
-        /* The returned value is < 0 if the exact key was not found. */
-        if (mid < 0) {
-            mid = -mid - 1;
-        }
-
-        /*
-         * Collections.binarySearch doesn't guarantee which element is returned
-         * if it falls on one of many equal ones. So make sure we are at the
-         * first one provided.
-         */
-        while ((mid > 0) &&
-                (list.get(mid).getEndTime() == list.get(mid-1).getEndTime())) {
-            mid--;
+        ITmfStateInterval myInterval = tree.lower(dummyInterval);
+        if (myInterval == null) {
+            return tree.iterator();
         }
-        return mid;
+        final SortedSet<ITmfStateInterval> tailSet = tree.tailSet(myInterval);
+        Iterator<ITmfStateInterval> retVal = tailSet.iterator();
+        retVal.next();
+        return retVal;
     }
 
 }