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 | ||
367e2932 | 19 | import org.eclipse.jdt.annotation.NonNull; |
f3476b68 GB |
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"; | |
367e2932 AM |
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); | |
f3476b68 GB |
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 | ||
367e2932 | 92 | private static long fillValues(HistoryTree ht, @NonNull TmfStateValue value, int nbValues, long start) { |
f3476b68 GB |
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 | ||
7c247a0f GB |
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 | } | |
f3476b68 | 183 | } |