From 88598bff4fde87a46ad5d634967bc051e7c4385c Mon Sep 17 00:00:00 2001 From: =?utf8?q?Lo=C3=AFc=20Prieur-Drevon?= Date: Thu, 20 Oct 2016 14:55:05 -0400 Subject: [PATCH] ss: Move selectNextChildren to CoreNode and return sequenceNumber MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit SelectNextChildren was only called on CoreNodes to return their children. Returning the SequenceNumber will allow overlapping trees to read the nodes from disk when necessary and limit the footprint of the queue for large queries. Change-Id: I14ac3909bf7fb90490479d7b79cfa011c2dcb56c Signed-off-by: Loïc Prieur-Drevon Reviewed-on: https://git.eclipse.org/r/83647 Reviewed-by: Genevieve Bastien Tested-by: Genevieve Bastien Reviewed-by: Hudson CI --- .../stubs/backend/HistoryTreeClassicStub.java | 13 ++++ .../historytree/HistoryTreeBackend.java | 21 ++++--- .../backend/historytree/IHistoryTree.java | 17 ------ .../core/backend/historytree/ParentNode.java | 25 +++++--- .../backend/historytree/classic/CoreNode.java | 59 ++++++++++++------- .../classic/HistoryTreeClassic.java | 33 ----------- 6 files changed, 82 insertions(+), 86 deletions(-) diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java index 99a08f2156..2508db5374 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java @@ -18,6 +18,7 @@ import java.io.File; import java.io.IOException; import java.io.PrintWriter; import java.nio.channels.ClosedChannelException; +import java.util.Collection; import java.util.List; import org.eclipse.tracecompass.internal.statesystem.core.Activator; @@ -257,6 +258,7 @@ public class HistoryTreeClassicStub extends HistoryTreeClassic { assertTrue("Child at index " + i + " of parent " + node.getSequenceNumber() + " has correct start time", childNode.getNodeEnd() <= childNode.getNodeEnd()); } + testIntersectingChildren(node, childNode); } } catch (ClosedChannelException e) { @@ -264,4 +266,15 @@ public class HistoryTreeClassicStub extends HistoryTreeClassic { } } + private static void testIntersectingChildren(ParentNode parent, HTNode child) { + int childSequence = child.getSequenceNumber(); + boolean shouldBeInCollection; + Collection nextChildren; + for (long t = parent.getNodeStart(); t < parent.getNodeEnd(); t++) { + shouldBeInCollection = (t >= child.getNodeStart() && t <= child.getNodeEnd()); + nextChildren = parent.selectNextChildren(t); + assertEquals(shouldBeInCollection, nextChildren.contains(childSequence)); + } + } + } 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 3b021c1208..5e752deeb9 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 @@ -273,18 +273,19 @@ public class HistoryTreeBackend implements IStateHistoryBackend { checkValidTime(t); /* Queue is a stack of nodes containing nodes intersecting t */ - Deque queue = new LinkedList<>(); + Deque queue = new LinkedList<>(); /* We start by reading the information in the root node */ - queue.add(getSHT().getRootNode()); + queue.add(getSHT().getRootNode().getSequenceNumber()); /* Then we follow the down in the relevant children */ try { while (!queue.isEmpty()) { - HTNode currentNode = queue.pop(); + int sequenceNumber = queue.pop(); + HTNode currentNode = getSHT().readNode(sequenceNumber); if (currentNode.getNodeType() == HTNode.NodeType.CORE) { - /*Here we add the relevant children nodes for BFS*/ - queue.addAll(getSHT().selectNextChildren((ParentNode) currentNode, t)); + /* Here we add the relevant children nodes for BFS */ + queue.addAll(((ParentNode) currentNode).selectNextChildren(t)); } currentNode.writeInfoFromNode(stateInfo, t); } @@ -325,13 +326,15 @@ public class HistoryTreeBackend implements IStateHistoryBackend { throws TimeRangeException, ClosedChannelException { checkValidTime(t); - Deque queue = new LinkedList<>(); - queue.add(getSHT().getRootNode()); + Deque queue = new LinkedList<>(); + queue.add(getSHT().getRootNode().getSequenceNumber()); HTInterval interval = null; while (interval == null && !queue.isEmpty()) { - HTNode currentNode = queue.pop(); + int sequenceNumber = queue.pop(); + HTNode currentNode = getSHT().readNode(sequenceNumber); if (currentNode.getNodeType() == HTNode.NodeType.CORE) { - queue.addAll(getSHT().selectNextChildren((ParentNode) currentNode, t)); + /* Here we add the relevant children nodes for BFS */ + queue.addAll(((ParentNode) currentNode).selectNextChildren(t)); } interval = currentNode.getRelevantInterval(key, t); } 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 51282c0b3a..299db35370 100644 --- 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 @@ -13,8 +13,6 @@ import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.nio.channels.ClosedChannelException; -import java.util.Collection; - import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; /** @@ -191,21 +189,6 @@ public interface IHistoryTree { */ void insertInterval(HTInterval interval) throws TimeRangeException; - /** - * Inner method to select the next children of the current node intersecting - * the given timestamp. Useful for moving down the tree following one - * branch. - * - * @param currentNode - * The node on which the request is made - * @param t - * The timestamp to choose which child is the next one - * @return The child nodes intersecting t - * @throws ClosedChannelException - * If the file channel was closed while we were reading the tree - */ - Collection selectNextChildren(ParentNode currentNode, long t) throws ClosedChannelException; - /** * Get the current size of the 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 34b798d6e3..15003bdf4a 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 @@ -9,6 +9,10 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; +import java.util.Collection; +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; + /** * A Core node is a first-level node of a History Tree which is not a leaf node. * @@ -67,13 +71,6 @@ public abstract class ParentNode extends HTNode { */ public abstract long getChildStart(int index); - /** - * Get the start time of the latest (right-most) child node. - * - * @return The start time of the latest child - */ - public abstract long getLatestChildStart(); - /** * Tell this node that it has a new child (Congrats!) * @@ -82,4 +79,18 @@ public abstract class ParentNode extends HTNode { */ public abstract void linkNewChild(HTNode childNode); + /** + * Inner method to select the sequence numbers for the children of the + * current node that intersect the given timestamp. Useful for moving down + * the tree. + * + * @param t + * The timestamp to choose which child is the next one + * @return Collection of sequence numbers of the child nodes that intersect + * t, non-null empty collection if this is a Leaf Node + * @throws TimeRangeException + * If t is out of the node's range + */ + public abstract @NonNull Collection<@NonNull Integer> selectNextChildren(long t); + } 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 f70365a159..946c8bffc1 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 @@ -15,11 +15,14 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.c import java.nio.ByteBuffer; import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; import java.util.concurrent.locks.ReentrantReadWriteLock; 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; +import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; /** * A Core node is a first-level node of a History Tree which is not a leaf node. @@ -127,9 +130,11 @@ public final class CoreNode extends ParentNode { @Override public int getNbChildren() { rwl.readLock().lock(); - int ret = nbChildren; - rwl.readLock().unlock(); - return ret; + try { + return nbChildren; + } finally { + rwl.readLock().unlock(); + } } @Override @@ -162,16 +167,6 @@ public final class CoreNode extends ParentNode { } } - @Override - public long getLatestChildStart() { - rwl.readLock().lock(); - try { - return childStart[nbChildren - 1]; - } finally { - rwl.readLock().unlock(); - } - } - /** * Get the sequence number of the extension to this node (if there is one). * @@ -179,15 +174,14 @@ public final class CoreNode extends ParentNode { * there is no extension node. */ public int getExtensionSequenceNumber() { - return extension; + rwl.readLock().lock(); + try { + return extension; + } finally { + rwl.readLock().unlock(); + } } - /** - * Tell this node that it has a new child (Congrats!) - * - * @param childNode - * The SHTNode object of the new child - */ @Override public void linkNewChild(HTNode childNode) { rwl.writeLock().lock(); @@ -205,6 +199,31 @@ public final class CoreNode extends ParentNode { } } + @Override + public Collection selectNextChildren(long t) throws TimeRangeException { + if (t < getNodeStart() || (isOnDisk() && t > getNodeEnd())) { + throw new TimeRangeException("Requesting children outside the node's range: " + t); //$NON-NLS-1$ + } + rwl.readLock().lock(); + try { + int potentialNextSeqNb = -1; + for (int i = 0; i < nbChildren; i++) { + if (t >= childStart[i]) { + potentialNextSeqNb = children[i]; + } else { + break; + } + } + + if (potentialNextSeqNb == -1) { + throw new IllegalStateException("No next child node found"); //$NON-NLS-1$ + } + return Collections.singleton(potentialNextSeqNb); + } finally { + rwl.readLock().unlock(); + } + } + @Override public NodeType getNodeType() { return NodeType.CORE; diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java index 7f8c4d4d7c..a59bfe3f9e 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java @@ -22,7 +22,6 @@ 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; @@ -613,38 +612,6 @@ public class HistoryTreeClassic implements IHistoryTree { return newNode; } - @Override - public Collection selectNextChildren(ParentNode currentNode, long t) throws ClosedChannelException { - assert (currentNode.getNbChildren() > 0); - int potentialNextSeqNb = currentNode.getSequenceNumber(); - - for (int i = 0; i < currentNode.getNbChildren(); i++) { - if (t >= currentNode.getChildStart(i)) { - potentialNextSeqNb = currentNode.getChild(i); - } else { - break; - } - } - - /* - * Once we exit this loop, we should have found a children to follow. If - * we didn't, there's a problem. - */ - if (potentialNextSeqNb == currentNode.getSequenceNumber()) { - throw new IllegalStateException("No next child node found"); //$NON-NLS-1$ - } - - /* - * Since this code path is quite performance-critical, avoid iterating - * through the whole latestBranch array if we know for sure the next - * node has to be on disk - */ - if (currentNode.isOnDisk()) { - return Collections.singleton(fTreeIO.readNode(potentialNextSeqNb)); - } - return Collections.singleton(readNode(potentialNextSeqNb)); - } - @Override public long getFileSize() { return fConfig.getStateFile().length(); -- 2.34.1