import java.io.File;
import java.io.IOException;
+import java.nio.channels.ClosedChannelException;
+import java.util.List;
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig;
fTempFile.delete();
}
- private HistoryTreeStub setupSmallTree() {
+ /**
+ * Setup a history tree.
+ *
+ * @param maxChildren
+ * The max number of children per node in the tree (tree config
+ * option)
+ */
+ private HistoryTreeStub setupSmallTree(int maxChildren) {
HistoryTreeStub ht = null;
try {
File newFile = fTempFile;
assertNotNull(newFile);
HTConfig config = new HTConfig(newFile,
BLOCK_SIZE,
- 3, /* Number of children */
+ maxChildren, /* Number of children */
1, /* Provider version */
1); /* Start time */
ht = new HistoryTreeStub(config);
return ht;
}
+ /**
+ * Setup a history tree with config MAX_CHILDREN = 3.
+ */
+ private HistoryTreeStub setupSmallTree() {
+ return setupSmallTree(3);
+ }
+
private static long fillValues(HistoryTree ht, @NonNull TmfStateValue value, int nbValues, long start) {
for (int i = 0; i < nbValues; i++) {
ht.insertInterval(new HTInterval(start + i, start + i + 1, 1, value));
return start + nbValues;
}
+ /**
+ * Insert intervals in the tree to fill the current leaf node to capacity,
+ * without exceeding it.
+ *
+ * This guarantees that the following insertion will create new nodes.
+ *
+ * @param ht
+ * The history tree in which to insert
+ * @return Start time of the current leaf node. Future insertions should be
+ * greater than or equal to this to make sure the intervals go in
+ * the leaf node.
+ */
+ private static long fillNextLeafNode(HistoryTreeStub ht, long leafNodeStart) {
+ int prevCount = ht.getNodeCount();
+ int prevDepth = ht.getDepth();
+
+ /* Fill the following leaf node */
+ HTNode node = ht.getLatestLeaf();
+ int nodeFreeSpace = node.getNodeFreeSpace();
+ int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
+ long ret = fillValues(ht, STRING_VALUE, nbIntervals, leafNodeStart);
+
+ /* Make sure we haven't changed the depth or node count */
+ assertEquals(prevCount, ht.getNodeCount());
+ assertEquals(prevDepth, ht.getDepth());
+
+ return ret;
+ }
+
/**
* Test that nodes are filled
*
assertEquals(7, ht.getNodeCount());
assertEquals(3, ht.getDepth());
}
+
+ /**
+ * Make sure the node sequence numbers and parent pointers are set correctly
+ * when new nodes are created.
+ *
+ * <p>
+ * We are building a tree whose node sequence numbers will look like this at
+ * the end:
+ * </p>
+ *
+ * <pre>
+ * 3
+ * / \
+ * 1 4
+ * / \ \
+ * 0 2 5
+ * </pre>
+ *
+ * <p>
+ * However while building, the parent pointers may be different.
+ * </p>
+ *
+ * @throws ClosedChannelException
+ * If the test fails
+ */
+ @Test
+ public void testNodeSequenceNumbers() throws ClosedChannelException {
+ /* Represents the start time of the current leaf node */
+ long start = 1;
+
+ HistoryTreeStub ht = setupSmallTree(2);
+ start = fillNextLeafNode(ht, start);
+
+ List<HTNode> branch = ht.getLatestBranch();
+ assertEquals(1, branch.size());
+ assertEquals( 0, branch.get(0).getSequenceNumber());
+ assertEquals(-1, branch.get(0).getParentSequenceNumber());
+
+ /* Create a new branch */
+ start = fillValues(ht, STRING_VALUE, 1, start);
+ start = fillNextLeafNode(ht, start);
+ assertEquals(3, ht.getNodeCount());
+ assertEquals(2, ht.getDepth());
+
+ /* Make sure the first node's parent was updated */
+ HTNode node = ht.readNode(0);
+ assertEquals(0, node.getSequenceNumber());
+ assertEquals(1, node.getParentSequenceNumber());
+
+ /* Make sure the new branch is alright */
+ branch = ht.getLatestBranch();
+ assertEquals(2, branch.size());
+ assertEquals( 1, branch.get(0).getSequenceNumber());
+ assertEquals(-1, branch.get(0).getParentSequenceNumber());
+ assertEquals( 2, branch.get(1).getSequenceNumber());
+ assertEquals( 1, branch.get(1).getParentSequenceNumber());
+
+ /* Create a third branch */
+ start = fillValues(ht, STRING_VALUE, 1, start);
+ start = fillNextLeafNode(ht, start);
+ assertEquals(6, ht.getNodeCount());
+ assertEquals(3, ht.getDepth());
+
+ /* Make sure all previous nodes are still correct */
+ node = ht.readNode(0);
+ assertEquals(0, node.getSequenceNumber());
+ assertEquals(1, node.getParentSequenceNumber());
+ node = ht.readNode(1);
+ assertEquals(1, node.getSequenceNumber());
+ assertEquals(3, node.getParentSequenceNumber());
+ node = ht.readNode(2);
+ assertEquals(2, node.getSequenceNumber());
+ assertEquals(1, node.getParentSequenceNumber());
+
+ /* Verify the contents of the new latest branch */
+ branch = ht.getLatestBranch();
+ assertEquals(3, branch.size());
+ assertEquals( 3, branch.get(0).getSequenceNumber());
+ assertEquals(-1, branch.get(0).getParentSequenceNumber());
+ assertEquals( 4, branch.get(1).getSequenceNumber());
+ assertEquals( 3, branch.get(1).getParentSequenceNumber());
+ assertEquals( 5, branch.get(2).getSequenceNumber());
+ assertEquals( 4, branch.get(2).getParentSequenceNumber());
+ }
}
projects / deliverable / tracecompass.git / commitdiff
