statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java

   1 /*******************************************************************************
   2  * Copyright (c) 2015 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *******************************************************************************/
   9
  10 package org.eclipse.tracecompass.statesystem.core.tests.backend;
  11
  12 import static org.junit.Assert.assertEquals;
  13 import static org.junit.Assert.assertNotNull;
  14 import static org.junit.Assert.fail;
  15
  16 import java.io.File;
  17 import java.io.IOException;
  18 import java.nio.channels.ClosedChannelException;
  19 import java.util.List;
  20
  21 import org.eclipse.jdt.annotation.NonNull;
  22 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig;
  23 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval;
  24 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode;
  25 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTree;
  26 import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
  27 import org.eclipse.tracecompass.statesystem.core.tests.stubs.backend.HistoryTreeStub;
  28 import org.junit.After;
  29 import org.junit.Before;
  30 import org.junit.Test;
  31
  32 /**
  33  * Tests the history tree
  34  *
  35  * @author Geneviève Bastien
  36  */
  37 public class HistoryTreeTest {
  38
  39     /* Minimal allowed blocksize */
  40     private static final int BLOCK_SIZE = HistoryTree.TREE_HEADER_SIZE;
  41     /* The extra size used by long and double values */
  42     private static final int LONG_DOUBLE_SIZE = 8;
  43     /* The number of extra characters to store a string interval */
  44     private static final int STRING_PADDING = 2;
  45
  46     /* String with 23 characters, interval in file will be 25 bytes long */
  47     private static final String TEST_STRING = "abcdefghifklmnopqrstuvw";
  48     private static final @NonNull TmfStateValue STRING_VALUE = TmfStateValue.newValueString(TEST_STRING);
  49     private static final @NonNull TmfStateValue LONG_VALUE = TmfStateValue.newValueLong(10L);
  50     private static final @NonNull TmfStateValue INT_VALUE = TmfStateValue.newValueInt(1);
  51
  52     private File fTempFile;
  53
  54     /**
  55      * Create the temporary file for this history tree
  56      */
  57     @Before
  58     public void setupTest() {
  59         try {
  60             fTempFile = File.createTempFile("tmpStateSystem", null);
  61         } catch (IOException e) {
  62             fail(e.getMessage());
  63         }
  64     }
  65
  66     /**
  67      * Delete the temporary history tree file after the test
  68      */
  69     @After
  70     public void cleanup() {
  71         fTempFile.delete();
  72     }
  73
  74     /**
  75      * Setup a history tree.
  76      *
  77      * @param maxChildren
  78      *            The max number of children per node in the tree (tree config
  79      *            option)
  80      */
  81     private HistoryTreeStub setupSmallTree(int maxChildren) {
  82         HistoryTreeStub ht = null;
  83         try {
  84             File newFile = fTempFile;
  85             assertNotNull(newFile);
  86             HTConfig config = new HTConfig(newFile,
  87                     BLOCK_SIZE,
  88                     maxChildren, /* Number of children */
  89                     1, /* Provider version */
  90                     1); /* Start time */
  91             ht = new HistoryTreeStub(config);
  92
  93         } catch (IOException e) {
  94             fail(e.getMessage());
  95         }
  96
  97         assertNotNull(ht);
  98         return ht;
  99     }
 100
 101     /**
 102      * Setup a history tree with config MAX_CHILDREN = 3.
 103      */
 104     private HistoryTreeStub setupSmallTree() {
 105         return setupSmallTree(3);
 106     }
 107
 108     private static long fillValues(HistoryTree ht, @NonNull TmfStateValue value, int nbValues, long start) {
 109         for (int i = 0; i < nbValues; i++) {
 110             ht.insertInterval(new HTInterval(start + i, start + i + 1, 1, value));
 111         }
 112         return start + nbValues;
 113     }
 114
 115     /**
 116      * Insert intervals in the tree to fill the current leaf node to capacity,
 117      * without exceeding it.
 118      *
 119      * This guarantees that the following insertion will create new nodes.
 120      *
 121      * @param ht
 122      *            The history tree in which to insert
 123      * @return Start time of the current leaf node. Future insertions should be
 124      *         greater than or equal to this to make sure the intervals go in
 125      *         the leaf node.
 126      */
 127     private static long fillNextLeafNode(HistoryTreeStub ht, long leafNodeStart) {
 128         int prevCount = ht.getNodeCount();
 129         int prevDepth = ht.getDepth();
 130
 131         /* Fill the following leaf node */
 132         HTNode node = ht.getLatestLeaf();
 133         int nodeFreeSpace = node.getNodeFreeSpace();
 134         int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 135         long ret = fillValues(ht, STRING_VALUE, nbIntervals, leafNodeStart);
 136
 137         /* Make sure we haven't changed the depth or node count */
 138         assertEquals(prevCount, ht.getNodeCount());
 139         assertEquals(prevDepth, ht.getDepth());
 140
 141         return ret;
 142     }
 143
 144     /**
 145      * Test that nodes are filled
 146      *
 147      * It fills nodes with sequential intervals from one attribute only, so that
 148      * leafs should be filled.
 149      */
 150     @Test
 151     public void testSequentialFill() {
 152         HistoryTreeStub ht = setupSmallTree();
 153
 154         HTNode node = ht.getLatestLeaf();
 155         assertEquals(0, node.getNodeUsagePercent());
 156
 157         /* Add null intervals up to ~10% */
 158         int nodeFreeSpace = node.getNodeFreeSpace();
 159         int nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
 160         long start = fillValues(ht, TmfStateValue.nullValue(), nbIntervals, 1);
 161         assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());
 162
 163         /* Add integer intervals up to ~20% */
 164         nodeFreeSpace = node.getNodeFreeSpace();
 165         nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
 166         start = fillValues(ht, INT_VALUE, nbIntervals, start);
 167         assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());
 168
 169         /* Add long intervals up to ~30% */
 170         nodeFreeSpace = node.getNodeFreeSpace();
 171         nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE);
 172         start = fillValues(ht, LONG_VALUE, nbIntervals, start);
 173         assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE), node.getNodeFreeSpace());
 174
 175         /* Add string intervals up to ~40% */
 176         nodeFreeSpace = node.getNodeFreeSpace();
 177         nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 178         start = fillValues(ht, STRING_VALUE, nbIntervals, start);
 179         assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING), node.getNodeFreeSpace());
 180
 181     }
 182
 183     /**
 184      * Test the addition of new nodes to the tree and make sure the tree is
 185      * built with the right structure
 186      */
 187     @Test
 188     public void testDepth() {
 189         HistoryTreeStub ht = setupSmallTree();
 190
 191         /* Fill a first node */
 192         HTNode node = ht.getLatestLeaf();
 193         int nodeFreeSpace = node.getNodeFreeSpace();
 194         int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 195         long start = fillValues(ht, STRING_VALUE, nbIntervals, 1);
 196
 197         /* Add intervals that should add a sibling to the node */
 198         assertEquals(1, ht.getNodeCount());
 199         assertEquals(1, ht.getDepth());
 200         start = fillValues(ht, STRING_VALUE, 1, start);
 201         assertEquals(3, ht.getNodeCount());
 202         assertEquals(2, ht.getDepth());
 203
 204         /* Fill the latest leaf node (2nd child) */
 205         node = ht.getLatestLeaf();
 206         nodeFreeSpace = node.getNodeFreeSpace();
 207         nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 208         start = fillValues(ht, STRING_VALUE, nbIntervals, start);
 209
 210         /*
 211          * Add an interval that should add another sibling to the previous nodes
 212          */
 213         start = fillValues(ht, STRING_VALUE, 1, start);
 214         assertEquals(4, ht.getNodeCount());
 215         assertEquals(2, ht.getDepth());
 216
 217         /* Fill the latest leaf node (3rd and last child) */
 218         node = ht.getLatestLeaf();
 219         nodeFreeSpace = node.getNodeFreeSpace();
 220         nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 221         start = fillValues(ht, STRING_VALUE, nbIntervals, start);
 222
 223         /* The new node created here should generate a new branch */
 224         start = fillValues(ht, STRING_VALUE, 1, start);
 225         assertEquals(7, ht.getNodeCount());
 226         assertEquals(3, ht.getDepth());
 227     }
 228
 229     /**
 230      * Make sure the node sequence numbers and parent pointers are set correctly
 231      * when new nodes are created.
 232      *
 233      * <p>
 234      * We are building a tree whose node sequence numbers will look like this at
 235      * the end:
 236      * </p>
 237      *
 238      * <pre>
 239      *     3
 240      *    / \
 241      *   1   4
 242      *  / \   \
 243      * 0   2   5
 244      * </pre>
 245      *
 246      * <p>
 247      * However while building, the parent pointers may be different.
 248      * </p>
 249      *
 250      * @throws ClosedChannelException
 251      *             If the test fails
 252      */
 253     @Test
 254     public void testNodeSequenceNumbers() throws ClosedChannelException {
 255         /* Represents the start time of the current leaf node */
 256         long start = 1;
 257
 258         HistoryTreeStub ht = setupSmallTree(2);
 259         start = fillNextLeafNode(ht, start);
 260
 261         List<HTNode> branch = ht.getLatestBranch();
 262         assertEquals(1, branch.size());
 263         assertEquals( 0, branch.get(0).getSequenceNumber());
 264         assertEquals(-1, branch.get(0).getParentSequenceNumber());
 265
 266         /* Create a new branch */
 267         start = fillValues(ht, STRING_VALUE, 1, start);
 268         start = fillNextLeafNode(ht, start);
 269         assertEquals(3, ht.getNodeCount());
 270         assertEquals(2, ht.getDepth());
 271
 272         /* Make sure the first node's parent was updated */
 273         HTNode node = ht.readNode(0);
 274         assertEquals(0, node.getSequenceNumber());
 275         assertEquals(1, node.getParentSequenceNumber());
 276
 277         /* Make sure the new branch is alright */
 278         branch = ht.getLatestBranch();
 279         assertEquals(2, branch.size());
 280         assertEquals( 1, branch.get(0).getSequenceNumber());
 281         assertEquals(-1, branch.get(0).getParentSequenceNumber());
 282         assertEquals( 2, branch.get(1).getSequenceNumber());
 283         assertEquals( 1, branch.get(1).getParentSequenceNumber());
 284
 285         /* Create a third branch */
 286         start = fillValues(ht, STRING_VALUE, 1, start);
 287         start = fillNextLeafNode(ht, start);
 288         assertEquals(6, ht.getNodeCount());
 289         assertEquals(3, ht.getDepth());
 290
 291         /* Make sure all previous nodes are still correct */
 292         node = ht.readNode(0);
 293         assertEquals(0, node.getSequenceNumber());
 294         assertEquals(1, node.getParentSequenceNumber());
 295         node = ht.readNode(1);
 296         assertEquals(1, node.getSequenceNumber());
 297         assertEquals(3, node.getParentSequenceNumber());
 298         node = ht.readNode(2);
 299         assertEquals(2, node.getSequenceNumber());
 300         assertEquals(1, node.getParentSequenceNumber());
 301
 302         /* Verify the contents of the new latest branch */
 303         branch = ht.getLatestBranch();
 304         assertEquals(3, branch.size());
 305         assertEquals( 3, branch.get(0).getSequenceNumber());
 306         assertEquals(-1, branch.get(0).getParentSequenceNumber());
 307         assertEquals( 4, branch.get(1).getSequenceNumber());
 308         assertEquals( 3, branch.get(1).getParentSequenceNumber());
 309         assertEquals( 5, branch.get(2).getSequenceNumber());
 310         assertEquals( 4, branch.get(2).getParentSequenceNumber());
 311     }
 312 }