Commit | Line | Data |
---|---|---|
a52fde77 | 1 | /******************************************************************************* |
b2ca67ca | 2 | * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others |
3b7f5abe | 3 | * |
a52fde77 AM |
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 | |
3b7f5abe | 8 | * |
bb7f92ce FW |
9 | * Contributors: |
10 | * Alexandre Montplaisir - Initial API and implementation | |
11 | * Florian Wininger - Add Extension and Leaf Node | |
e13bd4cd | 12 | * Patrick Tasse - Add message to exceptions |
a52fde77 AM |
13 | *******************************************************************************/ |
14 | ||
f4baf640 | 15 | package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic; |
a52fde77 AM |
16 | |
17 | import java.io.File; | |
18 | import java.io.FileInputStream; | |
19 | import java.io.IOException; | |
a52fde77 AM |
20 | import java.nio.ByteBuffer; |
21 | import java.nio.ByteOrder; | |
3b7f5abe | 22 | import java.nio.channels.ClosedChannelException; |
a52fde77 | 23 | import java.nio.channels.FileChannel; |
cb42195c AM |
24 | import java.util.ArrayList; |
25 | import java.util.Collections; | |
26 | import java.util.List; | |
a52fde77 | 27 | |
aa353506 | 28 | import org.eclipse.jdt.annotation.NonNull; |
f4baf640 GB |
29 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig; |
30 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval; | |
31 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode; | |
32 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HT_IO; | |
33 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.IHistoryTree; | |
34 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.LeafNode; | |
35 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.ParentNode; | |
e894a508 AM |
36 | import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; |
37 | import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; | |
a52fde77 | 38 | |
a10a38ae | 39 | import com.google.common.annotations.VisibleForTesting; |
f3476b68 GB |
40 | import com.google.common.collect.ImmutableList; |
41 | ||
a52fde77 AM |
42 | /** |
43 | * Meta-container for the History Tree. This structure contains all the | |
44 | * high-level data relevant to the tree. | |
3b7f5abe | 45 | * |
ffd0aa67 | 46 | * @author Alexandre Montplaisir |
a52fde77 | 47 | */ |
3a081e85 | 48 | public class HistoryTreeClassic implements IHistoryTree { |
cb42195c | 49 | |
9a4c098d | 50 | /** |
f4baf640 | 51 | * The magic number for this file format. |
9a4c098d | 52 | */ |
f4baf640 | 53 | public static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900; |
a52fde77 | 54 | |
a96cc6be | 55 | /** File format version. Increment when breaking compatibility. */ |
8182f36f | 56 | private static final int FILE_VERSION = 7; |
a52fde77 | 57 | |
f4baf640 GB |
58 | private static final IHTNodeFactory CLASSIC_NODE_FACTORY = new IHTNodeFactory() { |
59 | ||
60 | @Override | |
61 | public HTNode createCoreNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) { | |
62 | return new CoreNode(config, seqNumber, parentSeqNumber, start); | |
63 | } | |
64 | ||
65 | @Override | |
66 | public HTNode createLeafNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) { | |
67 | return new LeafNode(config, seqNumber, parentSeqNumber, start); | |
68 | } | |
69 | ||
70 | }; | |
71 | ||
dbdc452f AM |
72 | // ------------------------------------------------------------------------ |
73 | // Tree-specific configuration | |
74 | // ------------------------------------------------------------------------ | |
75 | ||
76 | /** Container for all the configuration constants */ | |
0e9b2f07 | 77 | private final HTConfig fConfig; |
a52fde77 | 78 | |
dbdc452f | 79 | /** Reader/writer object */ |
0e4eaca8 | 80 | private final @NonNull HT_IO fTreeIO; |
a52fde77 | 81 | |
dbdc452f | 82 | // ------------------------------------------------------------------------ |
ecb12461 | 83 | // Variable Fields (will change throughout the existence of the SHT) |
dbdc452f AM |
84 | // ------------------------------------------------------------------------ |
85 | ||
86 | /** Latest timestamp found in the tree (at any given moment) */ | |
0e9b2f07 | 87 | private long fTreeEnd; |
a52fde77 | 88 | |
360f899e | 89 | /** The total number of nodes that exists in this tree */ |
0e9b2f07 | 90 | private int fNodeCount; |
a52fde77 | 91 | |
dbdc452f | 92 | /** "Cache" to keep the active nodes in memory */ |
367e2932 | 93 | private final @NonNull List<@NonNull HTNode> fLatestBranch; |
a52fde77 | 94 | |
dbdc452f AM |
95 | // ------------------------------------------------------------------------ |
96 | // Constructors/"Destructors" | |
97 | // ------------------------------------------------------------------------ | |
98 | ||
a52fde77 | 99 | /** |
8d47cc34 AM |
100 | * Create a new State History from scratch, using a {@link HTConfig} object |
101 | * for configuration. | |
102 | * | |
103 | * @param conf | |
104 | * The config to use for this History Tree. | |
105 | * @throws IOException | |
106 | * If an error happens trying to open/write to the file | |
107 | * specified in the config | |
a52fde77 | 108 | */ |
3a081e85 | 109 | public HistoryTreeClassic(HTConfig conf) throws IOException { |
a52fde77 | 110 | /* |
bb7f92ce FW |
111 | * Simple check to make sure we have enough place in the 0th block for |
112 | * the tree configuration | |
a52fde77 | 113 | */ |
cb42195c | 114 | if (conf.getBlockSize() < TREE_HEADER_SIZE) { |
dbdc452f AM |
115 | throw new IllegalArgumentException(); |
116 | } | |
a52fde77 | 117 | |
0e9b2f07 GB |
118 | fConfig = conf; |
119 | fTreeEnd = conf.getTreeStart(); | |
120 | fNodeCount = 0; | |
aa353506 | 121 | fLatestBranch = Collections.synchronizedList(new ArrayList<>()); |
a52fde77 AM |
122 | |
123 | /* Prepare the IO object */ | |
f4baf640 | 124 | fTreeIO = new HT_IO(fConfig, true, CLASSIC_NODE_FACTORY); |
a52fde77 AM |
125 | |
126 | /* Add the first node to the tree */ | |
bb7f92ce | 127 | LeafNode firstNode = initNewLeafNode(-1, conf.getTreeStart()); |
0e9b2f07 | 128 | fLatestBranch.add(firstNode); |
a52fde77 AM |
129 | } |
130 | ||
a52fde77 AM |
131 | /** |
132 | * "Reader" constructor : instantiate a SHTree from an existing tree file on | |
133 | * disk | |
3b7f5abe | 134 | * |
8d47cc34 | 135 | * @param existingStateFile |
a52fde77 | 136 | * Path/filename of the history-file we are to open |
a96cc6be AM |
137 | * @param expProviderVersion |
138 | * The expected version of the state provider | |
a52fde77 | 139 | * @throws IOException |
8d47cc34 | 140 | * If an error happens reading the file |
a52fde77 | 141 | */ |
3a081e85 | 142 | public HistoryTreeClassic(File existingStateFile, int expProviderVersion) throws IOException { |
a52fde77 AM |
143 | /* |
144 | * Open the file ourselves, get the tree header information we need, | |
145 | * then pass on the descriptor to the TreeIO object. | |
146 | */ | |
147 | int rootNodeSeqNb, res; | |
148 | int bs, maxc; | |
fb12b0c2 | 149 | long startTime; |
a52fde77 AM |
150 | |
151 | /* Java I/O mumbo jumbo... */ | |
fee997a5 AM |
152 | if (!existingStateFile.exists()) { |
153 | throw new IOException("Selected state file does not exist"); //$NON-NLS-1$ | |
154 | } | |
fb12b0c2 | 155 | if (existingStateFile.length() <= 0) { |
a96cc6be | 156 | throw new IOException("Empty target file"); //$NON-NLS-1$ |
a52fde77 AM |
157 | } |
158 | ||
a4524c1b AM |
159 | try (FileInputStream fis = new FileInputStream(existingStateFile); |
160 | FileChannel fc = fis.getChannel();) { | |
a52fde77 | 161 | |
a4524c1b | 162 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); |
a4524c1b AM |
163 | buffer.order(ByteOrder.LITTLE_ENDIAN); |
164 | buffer.clear(); | |
75409043 AM |
165 | |
166 | res = fc.read(buffer); | |
167 | if (res != TREE_HEADER_SIZE) { | |
168 | throw new IOException("Invalid header size"); //$NON-NLS-1$ | |
169 | } | |
170 | ||
a4524c1b | 171 | buffer.flip(); |
a52fde77 | 172 | |
a96cc6be | 173 | /* |
a4524c1b AM |
174 | * Check the magic number to make sure we're opening the right type |
175 | * of file | |
a96cc6be | 176 | */ |
a4524c1b AM |
177 | res = buffer.getInt(); |
178 | if (res != HISTORY_FILE_MAGIC_NUMBER) { | |
179 | throw new IOException("Wrong magic number"); //$NON-NLS-1$ | |
180 | } | |
181 | ||
182 | res = buffer.getInt(); /* File format version number */ | |
183 | if (res != FILE_VERSION) { | |
184 | throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$ | |
185 | } | |
186 | ||
187 | res = buffer.getInt(); /* Event handler's version number */ | |
188 | if (res != expProviderVersion && | |
bcec0116 | 189 | expProviderVersion != ITmfStateSystemBuilder.IGNORE_PROVIDER_VERSION) { |
a4524c1b AM |
190 | /* |
191 | * The existing history was built using an event handler that | |
192 | * doesn't match the current one in the framework. | |
193 | * | |
194 | * Information could be all wrong. Instead of keeping an | |
195 | * incorrect history file, a rebuild is done. | |
196 | */ | |
197 | throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$ | |
198 | } | |
199 | ||
200 | bs = buffer.getInt(); /* Block Size */ | |
201 | maxc = buffer.getInt(); /* Max nb of children per node */ | |
a52fde77 | 202 | |
0e9b2f07 | 203 | fNodeCount = buffer.getInt(); |
a4524c1b AM |
204 | rootNodeSeqNb = buffer.getInt(); |
205 | startTime = buffer.getLong(); | |
a52fde77 | 206 | |
0e9b2f07 | 207 | fConfig = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime); |
a4524c1b | 208 | } |
a52fde77 | 209 | |
a52fde77 AM |
210 | /* |
211 | * FIXME We close fis here and the TreeIO will then reopen the same | |
212 | * file, not extremely elegant. But how to pass the information here to | |
213 | * the SHT otherwise? | |
214 | */ | |
f4baf640 | 215 | fTreeIO = new HT_IO(fConfig, false, CLASSIC_NODE_FACTORY); |
a52fde77 | 216 | |
0e9b2f07 GB |
217 | fLatestBranch = buildLatestBranch(rootNodeSeqNb); |
218 | fTreeEnd = getRootNode().getNodeEnd(); | |
fb12b0c2 AM |
219 | |
220 | /* | |
221 | * Make sure the history start time we read previously is consistent | |
222 | * with was is actually in the root node. | |
223 | */ | |
412a0225 | 224 | if (startTime != getRootNode().getNodeStart()) { |
fb12b0c2 AM |
225 | throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$ |
226 | "history file, it might be corrupted."); //$NON-NLS-1$ | |
227 | } | |
a52fde77 AM |
228 | } |
229 | ||
412a0225 AM |
230 | /** |
231 | * Rebuild the latestBranch "cache" object by reading the nodes from disk | |
232 | * (When we are opening an existing file on disk and want to append to it, | |
233 | * for example). | |
234 | * | |
235 | * @param rootNodeSeqNb | |
236 | * The sequence number of the root node, so we know where to | |
237 | * start | |
238 | * @throws ClosedChannelException | |
239 | */ | |
367e2932 | 240 | private @NonNull List<@NonNull HTNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { |
aa353506 | 241 | List<@NonNull HTNode> list = new ArrayList<>(); |
412a0225 | 242 | |
0e9b2f07 | 243 | HTNode nextChildNode = fTreeIO.readNode(rootNodeSeqNb); |
bb7f92ce | 244 | list.add(nextChildNode); |
412a0225 | 245 | |
bb7f92ce FW |
246 | /* Follow the last branch up to the leaf */ |
247 | while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) { | |
0e9b2f07 | 248 | nextChildNode = fTreeIO.readNode(((CoreNode) nextChildNode).getLatestChild()); |
bb7f92ce | 249 | list.add(nextChildNode); |
412a0225 AM |
250 | } |
251 | return Collections.synchronizedList(list); | |
252 | } | |
253 | ||
3a081e85 | 254 | @Override |
8d47cc34 | 255 | public void closeTree(long requestedEndTime) { |
412a0225 | 256 | /* This is an important operation, queries can wait */ |
0e9b2f07 | 257 | synchronized (fLatestBranch) { |
412a0225 AM |
258 | /* |
259 | * Work-around the "empty branches" that get created when the root | |
260 | * node becomes full. Overwrite the tree's end time with the | |
261 | * original wanted end-time, to ensure no queries are sent into | |
262 | * those empty nodes. | |
263 | * | |
264 | * This won't be needed once extended nodes are implemented. | |
265 | */ | |
0e9b2f07 | 266 | fTreeEnd = requestedEndTime; |
6a1074ce | 267 | |
412a0225 | 268 | /* Close off the latest branch of the tree */ |
0e9b2f07 GB |
269 | for (int i = 0; i < fLatestBranch.size(); i++) { |
270 | fLatestBranch.get(i).closeThisNode(fTreeEnd); | |
271 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
412a0225 | 272 | } |
a52fde77 | 273 | |
0e9b2f07 | 274 | try (FileChannel fc = fTreeIO.getFcOut();) { |
412a0225 AM |
275 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); |
276 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
277 | buffer.clear(); | |
a52fde77 | 278 | |
412a0225 AM |
279 | /* Save the config of the tree to the header of the file */ |
280 | fc.position(0); | |
a52fde77 | 281 | |
412a0225 | 282 | buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); |
a52fde77 | 283 | |
412a0225 | 284 | buffer.putInt(FILE_VERSION); |
0e9b2f07 | 285 | buffer.putInt(fConfig.getProviderVersion()); |
a52fde77 | 286 | |
0e9b2f07 GB |
287 | buffer.putInt(fConfig.getBlockSize()); |
288 | buffer.putInt(fConfig.getMaxChildren()); | |
a52fde77 | 289 | |
0e9b2f07 | 290 | buffer.putInt(fNodeCount); |
a52fde77 | 291 | |
412a0225 | 292 | /* root node seq. nb */ |
0e9b2f07 | 293 | buffer.putInt(fLatestBranch.get(0).getSequenceNumber()); |
a52fde77 | 294 | |
412a0225 | 295 | /* start time of this history */ |
0e9b2f07 | 296 | buffer.putLong(fLatestBranch.get(0).getNodeStart()); |
fb12b0c2 | 297 | |
412a0225 AM |
298 | buffer.flip(); |
299 | int res = fc.write(buffer); | |
300 | assert (res <= TREE_HEADER_SIZE); | |
301 | /* done writing the file header */ | |
a52fde77 | 302 | |
412a0225 AM |
303 | } catch (IOException e) { |
304 | /* | |
305 | * If we were able to write so far, there should not be any | |
306 | * problem at this point... | |
307 | */ | |
308 | throw new RuntimeException("State system write error"); //$NON-NLS-1$ | |
309 | } | |
a52fde77 | 310 | } |
a52fde77 AM |
311 | } |
312 | ||
dbdc452f AM |
313 | // ------------------------------------------------------------------------ |
314 | // Accessors | |
315 | // ------------------------------------------------------------------------ | |
ab604305 | 316 | |
3a081e85 | 317 | @Override |
8d47cc34 | 318 | public long getTreeStart() { |
0e9b2f07 | 319 | return fConfig.getTreeStart(); |
a52fde77 AM |
320 | } |
321 | ||
3a081e85 | 322 | @Override |
8d47cc34 | 323 | public long getTreeEnd() { |
0e9b2f07 | 324 | return fTreeEnd; |
a52fde77 AM |
325 | } |
326 | ||
3a081e85 | 327 | @Override |
8d47cc34 | 328 | public int getNodeCount() { |
0e9b2f07 | 329 | return fNodeCount; |
a52fde77 AM |
330 | } |
331 | ||
3a081e85 | 332 | @Override |
bb7f92ce | 333 | public HTNode getRootNode() { |
0e9b2f07 | 334 | return fLatestBranch.get(0); |
cb42195c AM |
335 | } |
336 | ||
f3476b68 GB |
337 | /** |
338 | * Return the latest branch of the tree. That branch is immutable. Used for | |
339 | * unit testing and debugging. | |
340 | * | |
341 | * @return The immutable latest branch | |
342 | */ | |
a10a38ae | 343 | @VisibleForTesting |
aa353506 | 344 | protected List<@NonNull HTNode> getLatestBranch() { |
f3476b68 GB |
345 | return ImmutableList.copyOf(fLatestBranch); |
346 | } | |
347 | ||
a10a38ae GB |
348 | /** |
349 | * Read a node at sequence number | |
350 | * | |
351 | * @param seqNum | |
352 | * The sequence number of the node to read | |
353 | * @return The HTNode object | |
354 | * @throws ClosedChannelException | |
355 | * Exception thrown when reading the node | |
356 | */ | |
357 | @VisibleForTesting | |
358 | protected @NonNull HTNode getNode(int seqNum) throws ClosedChannelException { | |
359 | // First, check in the latest branch if the node is there | |
360 | for (HTNode node : fLatestBranch) { | |
361 | if (node.getSequenceNumber() == seqNum) { | |
362 | return node; | |
363 | } | |
364 | } | |
365 | return fTreeIO.readNode(seqNum); | |
366 | } | |
367 | ||
0e4eaca8 AM |
368 | /** |
369 | * Retrieve the TreeIO object. Should only be used for testing. | |
370 | * | |
371 | * @return The TreeIO | |
372 | */ | |
373 | @VisibleForTesting | |
374 | protected @NonNull HT_IO getTreeIO() { | |
375 | return fTreeIO; | |
376 | } | |
377 | ||
360f899e EB |
378 | // ------------------------------------------------------------------------ |
379 | // HT_IO interface | |
380 | // ------------------------------------------------------------------------ | |
381 | ||
3a081e85 | 382 | @Override |
8d47cc34 | 383 | public FileInputStream supplyATReader() { |
0e9b2f07 | 384 | return fTreeIO.supplyATReader(getNodeCount()); |
360f899e EB |
385 | } |
386 | ||
3a081e85 | 387 | @Override |
8d47cc34 | 388 | public File supplyATWriterFile() { |
0e9b2f07 | 389 | return fConfig.getStateFile(); |
360f899e EB |
390 | } |
391 | ||
3a081e85 | 392 | @Override |
8d47cc34 | 393 | public long supplyATWriterFilePos() { |
3a081e85 | 394 | return IHistoryTree.TREE_HEADER_SIZE |
0e9b2f07 | 395 | + ((long) getNodeCount() * fConfig.getBlockSize()); |
360f899e EB |
396 | } |
397 | ||
3a081e85 | 398 | @Override |
8d47cc34 | 399 | public HTNode readNode(int seqNumber) throws ClosedChannelException { |
360f899e | 400 | /* Try to read the node from memory */ |
0e9b2f07 GB |
401 | synchronized (fLatestBranch) { |
402 | for (HTNode node : fLatestBranch) { | |
412a0225 AM |
403 | if (node.getSequenceNumber() == seqNumber) { |
404 | return node; | |
405 | } | |
360f899e EB |
406 | } |
407 | } | |
408 | ||
409 | /* Read the node from disk */ | |
0e9b2f07 | 410 | return fTreeIO.readNode(seqNumber); |
360f899e EB |
411 | } |
412 | ||
3a081e85 | 413 | @Override |
8d47cc34 | 414 | public void writeNode(HTNode node) { |
0e9b2f07 | 415 | fTreeIO.writeNode(node); |
360f899e EB |
416 | } |
417 | ||
3a081e85 | 418 | @Override |
8d47cc34 | 419 | public void closeFile() { |
0e9b2f07 | 420 | fTreeIO.closeFile(); |
360f899e EB |
421 | } |
422 | ||
3a081e85 | 423 | @Override |
8d47cc34 | 424 | public void deleteFile() { |
0e9b2f07 | 425 | fTreeIO.deleteFile(); |
360f899e EB |
426 | } |
427 | ||
dbdc452f AM |
428 | // ------------------------------------------------------------------------ |
429 | // Operations | |
430 | // ------------------------------------------------------------------------ | |
431 | ||
3a081e85 | 432 | @Override |
8d47cc34 | 433 | public void insertInterval(HTInterval interval) throws TimeRangeException { |
0e9b2f07 GB |
434 | if (interval.getStartTime() < fConfig.getTreeStart()) { |
435 | throw new TimeRangeException("Interval Start:" + interval.getStartTime() + ", Config Start:" + fConfig.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$ | |
a52fde77 | 436 | } |
0e9b2f07 | 437 | tryInsertAtNode(interval, fLatestBranch.size() - 1); |
a52fde77 AM |
438 | } |
439 | ||
440 | /** | |
441 | * Inner method to find in which node we should add the interval. | |
3b7f5abe | 442 | * |
a52fde77 AM |
443 | * @param interval |
444 | * The interval to add to the tree | |
445 | * @param indexOfNode | |
446 | * The index *in the latestBranch* where we are trying the | |
447 | * insertion | |
448 | */ | |
449 | private void tryInsertAtNode(HTInterval interval, int indexOfNode) { | |
0e9b2f07 | 450 | HTNode targetNode = fLatestBranch.get(indexOfNode); |
a52fde77 AM |
451 | |
452 | /* Verify if there is enough room in this node to store this interval */ | |
59d30d83 | 453 | if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) { |
a52fde77 AM |
454 | /* Nope, not enough room. Insert in a new sibling instead. */ |
455 | addSiblingNode(indexOfNode); | |
0e9b2f07 | 456 | tryInsertAtNode(interval, fLatestBranch.size() - 1); |
a52fde77 AM |
457 | return; |
458 | } | |
459 | ||
460 | /* Make sure the interval time range fits this node */ | |
461 | if (interval.getStartTime() < targetNode.getNodeStart()) { | |
462 | /* | |
463 | * No, this interval starts before the startTime of this node. We | |
464 | * need to check recursively in parents if it can fit. | |
465 | */ | |
a52fde77 AM |
466 | tryInsertAtNode(interval, indexOfNode - 1); |
467 | return; | |
468 | } | |
469 | ||
470 | /* | |
471 | * Ok, there is room, and the interval fits in this time slot. Let's add | |
472 | * it. | |
473 | */ | |
474 | targetNode.addInterval(interval); | |
475 | ||
476 | /* Update treeEnd if needed */ | |
0e9b2f07 GB |
477 | if (interval.getEndTime() > fTreeEnd) { |
478 | fTreeEnd = interval.getEndTime(); | |
a52fde77 | 479 | } |
a52fde77 AM |
480 | } |
481 | ||
482 | /** | |
483 | * Method to add a sibling to any node in the latest branch. This will add | |
484 | * children back down to the leaf level, if needed. | |
3b7f5abe | 485 | * |
a52fde77 AM |
486 | * @param indexOfNode |
487 | * The index in latestBranch where we start adding | |
488 | */ | |
489 | private void addSiblingNode(int indexOfNode) { | |
0e9b2f07 GB |
490 | synchronized (fLatestBranch) { |
491 | final long splitTime = fTreeEnd; | |
a52fde77 | 492 | |
0e9b2f07 | 493 | if (indexOfNode >= fLatestBranch.size()) { |
bb7f92ce FW |
494 | /* |
495 | * We need to make sure (indexOfNode - 1) doesn't get the last | |
496 | * node in the branch, because that one is a Leaf Node. | |
497 | */ | |
498 | throw new IllegalStateException(); | |
499 | } | |
a52fde77 | 500 | |
412a0225 AM |
501 | /* Check if we need to add a new root node */ |
502 | if (indexOfNode == 0) { | |
503 | addNewRootNode(); | |
504 | return; | |
505 | } | |
a52fde77 | 506 | |
412a0225 | 507 | /* Check if we can indeed add a child to the target parent */ |
f4baf640 | 508 | if (((ParentNode) fLatestBranch.get(indexOfNode - 1)).getNbChildren() == fConfig.getMaxChildren()) { |
412a0225 AM |
509 | /* If not, add a branch starting one level higher instead */ |
510 | addSiblingNode(indexOfNode - 1); | |
511 | return; | |
512 | } | |
a52fde77 | 513 | |
412a0225 | 514 | /* Split off the new branch from the old one */ |
0e9b2f07 GB |
515 | for (int i = indexOfNode; i < fLatestBranch.size(); i++) { |
516 | fLatestBranch.get(i).closeThisNode(splitTime); | |
517 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
a52fde77 | 518 | |
f4baf640 | 519 | ParentNode prevNode = (ParentNode) fLatestBranch.get(i - 1); |
bb7f92ce FW |
520 | HTNode newNode; |
521 | ||
0e9b2f07 | 522 | switch (fLatestBranch.get(i).getNodeType()) { |
bb7f92ce FW |
523 | case CORE: |
524 | newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1); | |
525 | break; | |
526 | case LEAF: | |
527 | newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); | |
528 | break; | |
529 | default: | |
530 | throw new IllegalStateException(); | |
531 | } | |
a52fde77 | 532 | |
bb7f92ce | 533 | prevNode.linkNewChild(newNode); |
0e9b2f07 | 534 | fLatestBranch.set(i, newNode); |
412a0225 | 535 | } |
a52fde77 | 536 | } |
a52fde77 AM |
537 | } |
538 | ||
539 | /** | |
540 | * Similar to the previous method, except here we rebuild a completely new | |
541 | * latestBranch | |
542 | */ | |
543 | private void addNewRootNode() { | |
0e9b2f07 | 544 | final long splitTime = fTreeEnd; |
a52fde77 | 545 | |
0e9b2f07 | 546 | HTNode oldRootNode = fLatestBranch.get(0); |
f4baf640 | 547 | ParentNode newRootNode = initNewCoreNode(-1, fConfig.getTreeStart()); |
a52fde77 AM |
548 | |
549 | /* Tell the old root node that it isn't root anymore */ | |
550 | oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); | |
551 | ||
552 | /* Close off the whole current latestBranch */ | |
412a0225 | 553 | |
0e9b2f07 GB |
554 | for (int i = 0; i < fLatestBranch.size(); i++) { |
555 | fLatestBranch.get(i).closeThisNode(splitTime); | |
556 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
a52fde77 AM |
557 | } |
558 | ||
559 | /* Link the new root to its first child (the previous root node) */ | |
560 | newRootNode.linkNewChild(oldRootNode); | |
561 | ||
562 | /* Rebuild a new latestBranch */ | |
0e9b2f07 GB |
563 | int depth = fLatestBranch.size(); |
564 | fLatestBranch.clear(); | |
565 | fLatestBranch.add(newRootNode); | |
bb7f92ce FW |
566 | |
567 | // Create new coreNode | |
7c247a0f | 568 | for (int i = 1; i < depth; i++) { |
f4baf640 GB |
569 | ParentNode prevNode = (ParentNode) fLatestBranch.get(i - 1); |
570 | ParentNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), | |
a52fde77 AM |
571 | splitTime + 1); |
572 | prevNode.linkNewChild(newNode); | |
0e9b2f07 | 573 | fLatestBranch.add(newNode); |
a52fde77 | 574 | } |
bb7f92ce FW |
575 | |
576 | // Create the new leafNode | |
f4baf640 | 577 | ParentNode prevNode = (ParentNode) fLatestBranch.get(depth - 1); |
b2ca67ca | 578 | LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); |
bb7f92ce | 579 | prevNode.linkNewChild(newNode); |
0e9b2f07 | 580 | fLatestBranch.add(newNode); |
a52fde77 AM |
581 | } |
582 | ||
583 | /** | |
bb7f92ce | 584 | * Add a new empty core node to the tree. |
3b7f5abe | 585 | * |
a52fde77 AM |
586 | * @param parentSeqNumber |
587 | * Sequence number of this node's parent | |
588 | * @param startTime | |
589 | * Start time of the new node | |
590 | * @return The newly created node | |
591 | */ | |
f4baf640 GB |
592 | private @NonNull ParentNode initNewCoreNode(int parentSeqNumber, long startTime) { |
593 | ParentNode newNode = new CoreNode(fConfig, fNodeCount, parentSeqNumber, | |
a52fde77 | 594 | startTime); |
0e9b2f07 | 595 | fNodeCount++; |
a52fde77 AM |
596 | return newNode; |
597 | } | |
598 | ||
bb7f92ce FW |
599 | /** |
600 | * Add a new empty leaf node to the tree. | |
601 | * | |
602 | * @param parentSeqNumber | |
603 | * Sequence number of this node's parent | |
604 | * @param startTime | |
605 | * Start time of the new node | |
606 | * @return The newly created node | |
607 | */ | |
aa353506 | 608 | private @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) { |
0e9b2f07 | 609 | LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber, |
bb7f92ce | 610 | startTime); |
0e9b2f07 | 611 | fNodeCount++; |
bb7f92ce FW |
612 | return newNode; |
613 | } | |
614 | ||
3a081e85 | 615 | @Override |
8d47cc34 | 616 | public long getFileSize() { |
0e9b2f07 | 617 | return fConfig.getStateFile().length(); |
a52fde77 AM |
618 | } |
619 | ||
3b7f5abe AM |
620 | // ------------------------------------------------------------------------ |
621 | // Test/debugging methods | |
622 | // ------------------------------------------------------------------------ | |
a52fde77 | 623 | |
a52fde77 AM |
624 | /* Only used for debugging, shouldn't be externalized */ |
625 | @SuppressWarnings("nls") | |
626 | @Override | |
627 | public String toString() { | |
628 | return "Information on the current tree:\n\n" + "Blocksize: " | |
0e9b2f07 GB |
629 | + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: " |
630 | + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount | |
631 | + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n" | |
632 | + "Size of the treefile: " + getFileSize() + "\n" | |
a52fde77 | 633 | + "Root node has sequence number: " |
0e9b2f07 | 634 | + fLatestBranch.get(0).getSequenceNumber() + "\n" |
a52fde77 | 635 | + "'Latest leaf' has sequence number: " |
0e9b2f07 | 636 | + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber(); |
a52fde77 AM |
637 | } |
638 | ||
a52fde77 | 639 | } |