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;
assertTrue("Child at index " + i + " of parent " + node.getSequenceNumber() + " has correct start time",
childNode.getNodeEnd() <= childNode.getNodeEnd());
}
+ testIntersectingChildren(node, childNode);
}
} catch (ClosedChannelException e) {
}
}
+ private static void testIntersectingChildren(ParentNode parent, HTNode child) {
+ int childSequence = child.getSequenceNumber();
+ boolean shouldBeInCollection;
+ Collection<Integer> 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));
+ }
+ }
+
}
checkValidTime(t);
/* Queue is a stack of nodes containing nodes intersecting t */
- Deque<HTNode> queue = new LinkedList<>();
+ Deque<Integer> 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);
}
throws TimeRangeException, ClosedChannelException {
checkValidTime(t);
- Deque<HTNode> queue = new LinkedList<>();
- queue.add(getSHT().getRootNode());
+ Deque<Integer> 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);
}
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;
/**
*/
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<HTNode> selectNextChildren(ParentNode currentNode, long t) throws ClosedChannelException;
-
/**
* Get the current size of the history file.
*
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.
*
*/
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!)
*
*/
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);
+
}
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.
@Override
public int getNbChildren() {
rwl.readLock().lock();
- int ret = nbChildren;
- rwl.readLock().unlock();
- return ret;
+ try {
+ return nbChildren;
+ } finally {
+ rwl.readLock().unlock();
+ }
}
@Override
}
}
- @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).
*
* 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();
}
}
+ @Override
+ public Collection<Integer> 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;
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;
return newNode;
}
- @Override
- public Collection<HTNode> 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();
projects / deliverable / tracecompass.git / commitdiff
