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
  19 import org.eclipse.jdt.annotation.NonNull;
  20 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig;
  21 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval;
  22 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode;
  23 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTree;
  24 import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
  25 import org.eclipse.tracecompasss.statesystem.core.tests.stubs.backend.HistoryTreeStub;
  26 import org.junit.After;
  27 import org.junit.Before;
  28 import org.junit.Test;
  29
  30 /**
  31  * Tests the history tree
  32  *
  33  * @author Geneviève Bastien
  34  */
  35 public class HistoryTreeTest {
  36
  37     /* Minimal allowed blocksize */
  38     private static final int BLOCK_SIZE = HistoryTree.TREE_HEADER_SIZE;
  39     /* The extra size used by long and double values */
  40     private static final int LONG_DOUBLE_SIZE = 8;
  41     /* The number of extra characters to store a string interval */
  42     private static final int STRING_PADDING = 2;
  43
  44     /* String with 23 characters, interval in file will be 25 bytes long */
  45     private static final String TEST_STRING = "abcdefghifklmnopqrstuvw";
  46     private static final @NonNull TmfStateValue STRING_VALUE = TmfStateValue.newValueString(TEST_STRING);
  47     private static final @NonNull TmfStateValue LONG_VALUE = TmfStateValue.newValueLong(10L);
  48     private static final @NonNull TmfStateValue INT_VALUE = TmfStateValue.newValueInt(1);
  49
  50     private File fTempFile;
  51
  52     /**
  53      * Create the temporary file for this history tree
  54      */
  55     @Before
  56     public void setupTest() {
  57         try {
  58             fTempFile = File.createTempFile("tmpStateSystem", null);
  59         } catch (IOException e) {
  60             fail(e.getMessage());
  61         }
  62     }
  63
  64     /**
  65      * Delete the temporary history tree file after the test
  66      */
  67     @After
  68     public void cleanup() {
  69         fTempFile.delete();
  70     }
  71
  72     private HistoryTreeStub setupSmallTree() {
  73         HistoryTreeStub ht = null;
  74         try {
  75             File newFile = fTempFile;
  76             assertNotNull(newFile);
  77             HTConfig config = new HTConfig(newFile,
  78                     BLOCK_SIZE,
  79                     3, /* Number of children */
  80                     1, /* Provider version */
  81                     1); /* Start time */
  82             ht = new HistoryTreeStub(config);
  83
  84         } catch (IOException e) {
  85             fail(e.getMessage());
  86         }
  87
  88         assertNotNull(ht);
  89         return ht;
  90     }
  91
  92     private static long fillValues(HistoryTree ht, @NonNull TmfStateValue value, int nbValues, long start) {
  93         for (int i = 0; i < nbValues; i++) {
  94             ht.insertInterval(new HTInterval(start + i, start + i + 1, 1, value));
  95         }
  96         return start + nbValues;
  97     }
  98
  99     /**
 100      * Test that nodes are filled
 101      *
 102      * It fills nodes with sequential intervals from one attribute only, so that
 103      * leafs should be filled.
 104      */
 105     @Test
 106     public void testSequentialFill() {
 107         HistoryTreeStub ht = setupSmallTree();
 108
 109         HTNode node = ht.getLatestLeaf();
 110         assertEquals(0, node.getNodeUsagePercent());
 111
 112         /* Add null intervals up to ~10% */
 113         int nodeFreeSpace = node.getNodeFreeSpace();
 114         int nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
 115         long start = fillValues(ht, TmfStateValue.nullValue(), nbIntervals, 1);
 116         assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());
 117
 118         /* Add integer intervals up to ~20% */
 119         nodeFreeSpace = node.getNodeFreeSpace();
 120         nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
 121         start = fillValues(ht, INT_VALUE, nbIntervals, start);
 122         assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());
 123
 124         /* Add long intervals up to ~30% */
 125         nodeFreeSpace = node.getNodeFreeSpace();
 126         nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE);
 127         start = fillValues(ht, LONG_VALUE, nbIntervals, start);
 128         assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE), node.getNodeFreeSpace());
 129
 130         /* Add string intervals up to ~40% */
 131         nodeFreeSpace = node.getNodeFreeSpace();
 132         nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 133         start = fillValues(ht, STRING_VALUE, nbIntervals, start);
 134         assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING), node.getNodeFreeSpace());
 135
 136     }
 137
 138     /**
 139      * Test the addition of new nodes to the tree and make sure the tree is
 140      * built with the right structure
 141      */
 142     @Test
 143     public void testDepth() {
 144         HistoryTreeStub ht = setupSmallTree();
 145
 146         /* Fill a first node */
 147         HTNode node = ht.getLatestLeaf();
 148         int nodeFreeSpace = node.getNodeFreeSpace();
 149         int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 150         long start = fillValues(ht, STRING_VALUE, nbIntervals, 1);
 151
 152         /* Add intervals that should add a sibling to the node */
 153         assertEquals(1, ht.getNodeCount());
 154         assertEquals(1, ht.getDepth());
 155         start = fillValues(ht, STRING_VALUE, 1, start);
 156         assertEquals(3, ht.getNodeCount());
 157         assertEquals(2, ht.getDepth());
 158
 159         /* Fill the latest leaf node (2nd child) */
 160         node = ht.getLatestLeaf();
 161         nodeFreeSpace = node.getNodeFreeSpace();
 162         nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 163         start = fillValues(ht, STRING_VALUE, nbIntervals, start);
 164
 165         /*
 166          * Add an interval that should add another sibling to the previous nodes
 167          */
 168         start = fillValues(ht, STRING_VALUE, 1, start);
 169         assertEquals(4, ht.getNodeCount());
 170         assertEquals(2, ht.getDepth());
 171
 172         /* Fill the latest leaf node (3rd and last child) */
 173         node = ht.getLatestLeaf();
 174         nodeFreeSpace = node.getNodeFreeSpace();
 175         nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
 176         start = fillValues(ht, STRING_VALUE, nbIntervals, start);
 177
 178         /* The new node created here should generate a new branch */
 179         start = fillValues(ht, STRING_VALUE, 1, start);
 180         assertEquals(7, ht.getNodeCount());
 181         assertEquals(3, ht.getDepth());
 182     }
 183 }