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