ss: Have IHistoryTree#selectNextChild return a Collection instead

This is more generic for multiple implementations of IHistoryTree.

From running the state system benchmarks, there was no performance impact
with this patch by returning a Collection instead of a single element.

Change-Id: I9775c856e5e30d94eba01af001495dbd61191b22
Signed-off-by: Loïc Prieur-Drevon <loic.prieurdrevon@gmail.com>
Signed-off-by: Geneviève Bastien <gbastien+lttng@versatic.net>
Reviewed-on: https://git.eclipse.org/r/78279
Reviewed-by: Alexandre Montplaisir <alexmonthy@efficios.com>
Tested-by: Alexandre Montplaisir <alexmonthy@efficios.com>
Reviewed-by: Hudson CI

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 188c9da8be29dafaefc7492d592b66dafef5781e..1f5f12a3440b169e0bc7cfeee723ae2d333e1f45 100644 (file)
--- 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,8 @@ import java.io.File;
 import java.io.FileInputStream;
 import java.io.IOException;
 import java.nio.channels.ClosedChannelException;
+import java.util.Deque;
+import java.util.LinkedList;
 import java.util.List;
 
 import org.eclipse.jdt.annotation.NonNull;
@@ -265,14 +267,20 @@ public class HistoryTreeBackend implements IStateHistoryBackend {
             throws TimeRangeException, StateSystemDisposedException {
         checkValidTime(t);
 
+        /* Queue is a stack of nodes containing nodes intersecting t */
+        Deque<HTNode> queue = new LinkedList<>();
+
         /* We start by reading the information in the root node */
-        HTNode currentNode = getSHT().getRootNode();
-        currentNode.writeInfoFromNode(stateInfo, t);
+        queue.add(getSHT().getRootNode());
 
-        /* Then we follow the branch down in the relevant children */
+        /* Then we follow the down in the relevant children */
         try {
-            while (currentNode.getNodeType() == HTNode.NodeType.CORE) {
-                currentNode = getSHT().selectNextChild((CoreNode) currentNode, t);
+            while (!queue.isEmpty()) {
+                HTNode currentNode = queue.pop();
+                if (currentNode.getNodeType() == HTNode.NodeType.CORE) {
+                    /* Here we add the relevant children nodes for BFS */
+                    queue.addAll(getSHT().selectNextChildren((CoreNode) currentNode, t));
+                }
                 currentNode.writeInfoFromNode(stateInfo, t);
             }
         } catch (ClosedChannelException e) {
@@ -288,7 +296,11 @@ public class HistoryTreeBackend implements IStateHistoryBackend {
     @Override
     public ITmfStateInterval doSingularQuery(long t, int attributeQuark)
             throws TimeRangeException, StateSystemDisposedException {
-        return getRelevantInterval(t, attributeQuark);
+        try {
+            return getRelevantInterval(t, attributeQuark);
+        } catch (ClosedChannelException e) {
+            throw new StateSystemDisposedException(e);
+        }
     }
 
     private void checkValidTime(long t) {
@@ -303,25 +315,20 @@ public class HistoryTreeBackend implements IStateHistoryBackend {
     /**
      * Inner method to find the interval in the tree containing the requested
      * key/timestamp pair, wherever in which node it is.
-     *
-     * @param t
-     * @param key
-     * @return The node containing the information we want
      */
     private HTInterval getRelevantInterval(long t, int key)
-            throws TimeRangeException, StateSystemDisposedException {
+            throws TimeRangeException, ClosedChannelException {
         checkValidTime(t);
 
-        HTNode currentNode = getSHT().getRootNode();
-        HTInterval interval = currentNode.getRelevantInterval(key, t);
-
-        try {
-            while (interval == null && currentNode.getNodeType() == HTNode.NodeType.CORE) {
-                currentNode = getSHT().selectNextChild((CoreNode) currentNode, t);
-                interval = currentNode.getRelevantInterval(key, t);
+        Deque<HTNode> queue = new LinkedList<>();
+        queue.add(getSHT().getRootNode());
+        HTInterval interval = null;
+        while (interval == null && !queue.isEmpty()) {
+            HTNode currentNode = queue.pop();
+            if (currentNode.getNodeType() == HTNode.NodeType.CORE) {
+                queue.addAll(getSHT().selectNextChildren((CoreNode) currentNode, t));
             }
-        } catch (ClosedChannelException e) {
-            throw new StateSystemDisposedException(e);
+            interval = currentNode.getRelevantInterval(key, t);
         }
         return interval;
     }

diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java
index 54b8793543aa4e9fe78254e33ec4851b135b8bb8..29f62481c04ba90eef281732e882936349da837c 100644 (file)
--- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java
+++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java
@@ -22,6 +22,7 @@ import java.nio.ByteOrder;
 import java.nio.channels.ClosedChannelException;
 import java.nio.channels.FileChannel;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 
@@ -589,7 +590,7 @@ public class HistoryTreeClassic implements IHistoryTree {
     }
 
     @Override
-    public HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException {
+    public Collection<HTNode> selectNextChildren(CoreNode currentNode, long t) throws ClosedChannelException {
         assert (currentNode.getNbChildren() > 0);
         int potentialNextSeqNb = currentNode.getSequenceNumber();
 
@@ -615,9 +616,9 @@ public class HistoryTreeClassic implements IHistoryTree {
          * node has to be on disk
          */
         if (currentNode.isOnDisk()) {
-            return fTreeIO.readNode(potentialNextSeqNb);
+            return Collections.singleton(fTreeIO.readNode(potentialNextSeqNb));
         }
-        return readNode(potentialNextSeqNb);
+        return Collections.singleton(readNode(potentialNextSeqNb));
     }
 
     @Override

diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java
index 46263744d9eca6c110563d59fd770e9abc6d11f2..f1d09a8e5e6aff4674eec70950e64cf39291233f 100644 (file)
--- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java
+++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java
@@ -12,6 +12,7 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree;
 import java.io.File;
 import java.io.FileInputStream;
 import java.nio.channels.ClosedChannelException;
+import java.util.Collection;
 
 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
 
@@ -145,7 +146,7 @@ public interface IHistoryTree {
     void insertInterval(HTInterval interval) throws TimeRangeException;
 
     /**
-     * Inner method to select the next child of the current node intersecting
+     * Inner method to select the next children of the current node intersecting
      * the given timestamp. Useful for moving down the tree following one
      * branch.
      *
@@ -153,11 +154,11 @@ public interface IHistoryTree {
      *            The node on which the request is made
      * @param t
      *            The timestamp to choose which child is the next one
-     * @return The child node intersecting t
+     * @return The child nodes intersecting t
      * @throws ClosedChannelException
      *             If the file channel was closed while we were reading the tree
      */
-    HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException;
+    Collection<HTNode> selectNextChildren(CoreNode currentNode, long t) throws ClosedChannelException;
 
     /**
      * Get the current size of the history file.