From 7c247a0f587ed05339b8e1e483b61dca059c1909 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Genevi=C3=A8ve=20Bastien?= Date: Tue, 27 Oct 2015 23:56:45 -0400 Subject: [PATCH] ss: Fix a bug where depth of history tree increases at each new node MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit When adding a sibling after a new root, there was one too many levels. Change-Id: I19f460347cbba91c5c1f70d9ee4566a3cb164f37 Signed-off-by: Geneviève Bastien Reviewed-on: https://git.eclipse.org/r/59076 Reviewed-by: Hudson CI --- .../core/tests/backend/HistoryTreeTest.java | 45 +++++++++++++++++++ .../tests/stubs/backend/HistoryTreeStub.java | 9 ++++ .../core/backend/historytree/HistoryTree.java | 4 +- 3 files changed, 56 insertions(+), 2 deletions(-) diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java index 350227e592..6c1ea9b717 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java @@ -134,4 +134,49 @@ public class HistoryTreeTest { } + /** + * Test the addition of new nodes to the tree and make sure the tree is + * built with the right structure + */ + @Test + public void testDepth() { + HistoryTreeStub ht = setupSmallTree(); + + /* Fill a first node */ + HTNode node = ht.getLatestLeaf(); + int nodeFreeSpace = node.getNodeFreeSpace(); + int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING); + long start = fillValues(ht, STRING_VALUE, nbIntervals, 1); + + /* Add intervals that should add a sibling to the node */ + assertEquals(1, ht.getNodeCount()); + assertEquals(1, ht.getDepth()); + start = fillValues(ht, STRING_VALUE, 1, start); + assertEquals(3, ht.getNodeCount()); + assertEquals(2, ht.getDepth()); + + /* Fill the latest leaf node (2nd child) */ + node = ht.getLatestLeaf(); + nodeFreeSpace = node.getNodeFreeSpace(); + nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING); + start = fillValues(ht, STRING_VALUE, nbIntervals, start); + + /* + * Add an interval that should add another sibling to the previous nodes + */ + start = fillValues(ht, STRING_VALUE, 1, start); + assertEquals(4, ht.getNodeCount()); + assertEquals(2, ht.getDepth()); + + /* Fill the latest leaf node (3rd and last child) */ + node = ht.getLatestLeaf(); + nodeFreeSpace = node.getNodeFreeSpace(); + nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING); + start = fillValues(ht, STRING_VALUE, nbIntervals, start); + + /* The new node created here should generate a new branch */ + start = fillValues(ht, STRING_VALUE, 1, start); + assertEquals(7, ht.getNodeCount()); + assertEquals(3, ht.getDepth()); + } } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java index 75c59294a4..b26fd53e29 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java @@ -67,4 +67,13 @@ public class HistoryTreeStub extends HistoryTree { return checkNotNull(latest.get(pos)); } + /** + * Get the depth of the tree + * + * @return The depth of the tree + */ + public int getDepth() { + return getLatestBranch().size(); + } + } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java index 1cc3785e02..ebf4765065 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java @@ -577,7 +577,7 @@ public class HistoryTree { fLatestBranch.add(newRootNode); // Create new coreNode - for (int i = 1; i < depth + 1; i++) { + for (int i = 1; i < depth; i++) { CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); CoreNode newNode = initNewCoreNode(prevNode.getParentSequenceNumber(), splitTime + 1); @@ -586,7 +586,7 @@ public class HistoryTree { } // Create the new leafNode - CoreNode prevNode = (CoreNode) fLatestBranch.get(depth); + CoreNode prevNode = (CoreNode) fLatestBranch.get(depth - 1); LeafNode newNode = initNewLeafNode(prevNode.getParentSequenceNumber(), splitTime + 1); prevNode.linkNewChild(newNode); fLatestBranch.add(newNode); -- 2.34.1