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