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 | ||
e894a508 | 15 | package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; |
a52fde77 AM |
16 | |
17 | import java.io.File; | |
18 | import java.io.FileInputStream; | |
19 | import java.io.IOException; | |
20 | import java.io.PrintWriter; | |
21 | import java.nio.ByteBuffer; | |
22 | import java.nio.ByteOrder; | |
3b7f5abe | 23 | import java.nio.channels.ClosedChannelException; |
a52fde77 | 24 | import java.nio.channels.FileChannel; |
cb42195c AM |
25 | import java.util.ArrayList; |
26 | import java.util.Collections; | |
27 | import java.util.List; | |
a52fde77 | 28 | |
aa353506 | 29 | import org.eclipse.jdt.annotation.NonNull; |
e894a508 AM |
30 | import org.eclipse.tracecompass.internal.statesystem.core.Activator; |
31 | import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; | |
32 | import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; | |
a52fde77 | 33 | |
a10a38ae | 34 | import com.google.common.annotations.VisibleForTesting; |
f3476b68 GB |
35 | import com.google.common.collect.ImmutableList; |
36 | ||
a52fde77 AM |
37 | /** |
38 | * Meta-container for the History Tree. This structure contains all the | |
39 | * high-level data relevant to the tree. | |
3b7f5abe | 40 | * |
ffd0aa67 | 41 | * @author Alexandre Montplaisir |
a52fde77 | 42 | */ |
8d47cc34 | 43 | public class HistoryTree { |
a52fde77 | 44 | |
cb42195c AM |
45 | /** |
46 | * Size of the "tree header" in the tree-file The nodes will use this offset | |
47 | * to know where they should be in the file. This should always be a | |
48 | * multiple of 4K. | |
49 | */ | |
50 | public static final int TREE_HEADER_SIZE = 4096; | |
51 | ||
9a4c098d GB |
52 | /** |
53 | * The magic number for this file format. Package-private for the factory | |
54 | * class. | |
55 | */ | |
56 | static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900; | |
a52fde77 | 57 | |
a96cc6be | 58 | /** File format version. Increment when breaking compatibility. */ |
8182f36f | 59 | private static final int FILE_VERSION = 7; |
a52fde77 | 60 | |
dbdc452f AM |
61 | // ------------------------------------------------------------------------ |
62 | // Tree-specific configuration | |
63 | // ------------------------------------------------------------------------ | |
64 | ||
65 | /** Container for all the configuration constants */ | |
0e9b2f07 | 66 | private final HTConfig fConfig; |
a52fde77 | 67 | |
dbdc452f | 68 | /** Reader/writer object */ |
0e9b2f07 | 69 | private final HT_IO fTreeIO; |
a52fde77 | 70 | |
dbdc452f | 71 | // ------------------------------------------------------------------------ |
ecb12461 | 72 | // Variable Fields (will change throughout the existence of the SHT) |
dbdc452f AM |
73 | // ------------------------------------------------------------------------ |
74 | ||
75 | /** Latest timestamp found in the tree (at any given moment) */ | |
0e9b2f07 | 76 | private long fTreeEnd; |
a52fde77 | 77 | |
360f899e | 78 | /** The total number of nodes that exists in this tree */ |
0e9b2f07 | 79 | private int fNodeCount; |
a52fde77 | 80 | |
dbdc452f | 81 | /** "Cache" to keep the active nodes in memory */ |
367e2932 | 82 | private final @NonNull List<@NonNull HTNode> fLatestBranch; |
a52fde77 | 83 | |
dbdc452f AM |
84 | // ------------------------------------------------------------------------ |
85 | // Constructors/"Destructors" | |
86 | // ------------------------------------------------------------------------ | |
87 | ||
a52fde77 | 88 | /** |
8d47cc34 AM |
89 | * Create a new State History from scratch, using a {@link HTConfig} object |
90 | * for configuration. | |
91 | * | |
92 | * @param conf | |
93 | * The config to use for this History Tree. | |
94 | * @throws IOException | |
95 | * If an error happens trying to open/write to the file | |
96 | * specified in the config | |
a52fde77 | 97 | */ |
8d47cc34 | 98 | public HistoryTree(HTConfig conf) throws IOException { |
a52fde77 | 99 | /* |
bb7f92ce FW |
100 | * Simple check to make sure we have enough place in the 0th block for |
101 | * the tree configuration | |
a52fde77 | 102 | */ |
cb42195c | 103 | if (conf.getBlockSize() < TREE_HEADER_SIZE) { |
dbdc452f AM |
104 | throw new IllegalArgumentException(); |
105 | } | |
a52fde77 | 106 | |
0e9b2f07 GB |
107 | fConfig = conf; |
108 | fTreeEnd = conf.getTreeStart(); | |
109 | fNodeCount = 0; | |
aa353506 | 110 | fLatestBranch = Collections.synchronizedList(new ArrayList<>()); |
a52fde77 AM |
111 | |
112 | /* Prepare the IO object */ | |
0e9b2f07 | 113 | fTreeIO = new HT_IO(fConfig, true); |
a52fde77 AM |
114 | |
115 | /* Add the first node to the tree */ | |
bb7f92ce | 116 | LeafNode firstNode = initNewLeafNode(-1, conf.getTreeStart()); |
0e9b2f07 | 117 | fLatestBranch.add(firstNode); |
a52fde77 AM |
118 | } |
119 | ||
a52fde77 AM |
120 | /** |
121 | * "Reader" constructor : instantiate a SHTree from an existing tree file on | |
122 | * disk | |
3b7f5abe | 123 | * |
8d47cc34 | 124 | * @param existingStateFile |
a52fde77 | 125 | * Path/filename of the history-file we are to open |
a96cc6be AM |
126 | * @param expProviderVersion |
127 | * The expected version of the state provider | |
a52fde77 | 128 | * @throws IOException |
8d47cc34 | 129 | * If an error happens reading the file |
a52fde77 | 130 | */ |
8d47cc34 | 131 | public HistoryTree(File existingStateFile, int expProviderVersion) throws IOException { |
a52fde77 AM |
132 | /* |
133 | * Open the file ourselves, get the tree header information we need, | |
134 | * then pass on the descriptor to the TreeIO object. | |
135 | */ | |
136 | int rootNodeSeqNb, res; | |
137 | int bs, maxc; | |
fb12b0c2 | 138 | long startTime; |
a52fde77 AM |
139 | |
140 | /* Java I/O mumbo jumbo... */ | |
fee997a5 AM |
141 | if (!existingStateFile.exists()) { |
142 | throw new IOException("Selected state file does not exist"); //$NON-NLS-1$ | |
143 | } | |
fb12b0c2 | 144 | if (existingStateFile.length() <= 0) { |
a96cc6be | 145 | throw new IOException("Empty target file"); //$NON-NLS-1$ |
a52fde77 AM |
146 | } |
147 | ||
a4524c1b AM |
148 | try (FileInputStream fis = new FileInputStream(existingStateFile); |
149 | FileChannel fc = fis.getChannel();) { | |
a52fde77 | 150 | |
a4524c1b | 151 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); |
a52fde77 | 152 | |
a4524c1b AM |
153 | buffer.order(ByteOrder.LITTLE_ENDIAN); |
154 | buffer.clear(); | |
155 | fc.read(buffer); | |
156 | buffer.flip(); | |
a52fde77 | 157 | |
a96cc6be | 158 | /* |
a4524c1b AM |
159 | * Check the magic number to make sure we're opening the right type |
160 | * of file | |
a96cc6be | 161 | */ |
a4524c1b AM |
162 | res = buffer.getInt(); |
163 | if (res != HISTORY_FILE_MAGIC_NUMBER) { | |
164 | throw new IOException("Wrong magic number"); //$NON-NLS-1$ | |
165 | } | |
166 | ||
167 | res = buffer.getInt(); /* File format version number */ | |
168 | if (res != FILE_VERSION) { | |
169 | throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$ | |
170 | } | |
171 | ||
172 | res = buffer.getInt(); /* Event handler's version number */ | |
173 | if (res != expProviderVersion && | |
bcec0116 | 174 | expProviderVersion != ITmfStateSystemBuilder.IGNORE_PROVIDER_VERSION) { |
a4524c1b AM |
175 | /* |
176 | * The existing history was built using an event handler that | |
177 | * doesn't match the current one in the framework. | |
178 | * | |
179 | * Information could be all wrong. Instead of keeping an | |
180 | * incorrect history file, a rebuild is done. | |
181 | */ | |
182 | throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$ | |
183 | } | |
184 | ||
185 | bs = buffer.getInt(); /* Block Size */ | |
186 | maxc = buffer.getInt(); /* Max nb of children per node */ | |
a52fde77 | 187 | |
0e9b2f07 | 188 | fNodeCount = buffer.getInt(); |
a4524c1b AM |
189 | rootNodeSeqNb = buffer.getInt(); |
190 | startTime = buffer.getLong(); | |
a52fde77 | 191 | |
0e9b2f07 | 192 | fConfig = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime); |
a4524c1b | 193 | } |
a52fde77 | 194 | |
a52fde77 AM |
195 | /* |
196 | * FIXME We close fis here and the TreeIO will then reopen the same | |
197 | * file, not extremely elegant. But how to pass the information here to | |
198 | * the SHT otherwise? | |
199 | */ | |
0e9b2f07 | 200 | fTreeIO = new HT_IO(fConfig, false); |
a52fde77 | 201 | |
0e9b2f07 GB |
202 | fLatestBranch = buildLatestBranch(rootNodeSeqNb); |
203 | fTreeEnd = getRootNode().getNodeEnd(); | |
fb12b0c2 AM |
204 | |
205 | /* | |
206 | * Make sure the history start time we read previously is consistent | |
207 | * with was is actually in the root node. | |
208 | */ | |
412a0225 | 209 | if (startTime != getRootNode().getNodeStart()) { |
fb12b0c2 AM |
210 | throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$ |
211 | "history file, it might be corrupted."); //$NON-NLS-1$ | |
212 | } | |
a52fde77 AM |
213 | } |
214 | ||
412a0225 AM |
215 | /** |
216 | * Rebuild the latestBranch "cache" object by reading the nodes from disk | |
217 | * (When we are opening an existing file on disk and want to append to it, | |
218 | * for example). | |
219 | * | |
220 | * @param rootNodeSeqNb | |
221 | * The sequence number of the root node, so we know where to | |
222 | * start | |
223 | * @throws ClosedChannelException | |
224 | */ | |
367e2932 | 225 | private @NonNull List<@NonNull HTNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { |
aa353506 | 226 | List<@NonNull HTNode> list = new ArrayList<>(); |
412a0225 | 227 | |
0e9b2f07 | 228 | HTNode nextChildNode = fTreeIO.readNode(rootNodeSeqNb); |
bb7f92ce | 229 | list.add(nextChildNode); |
412a0225 | 230 | |
bb7f92ce FW |
231 | /* Follow the last branch up to the leaf */ |
232 | while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) { | |
0e9b2f07 | 233 | nextChildNode = fTreeIO.readNode(((CoreNode) nextChildNode).getLatestChild()); |
bb7f92ce | 234 | list.add(nextChildNode); |
412a0225 AM |
235 | } |
236 | return Collections.synchronizedList(list); | |
237 | } | |
238 | ||
a52fde77 AM |
239 | /** |
240 | * "Save" the tree to disk. This method will cause the treeIO object to | |
241 | * commit all nodes to disk and then return the RandomAccessFile descriptor | |
242 | * so the Tree object can save its configuration into the header of the | |
243 | * file. | |
3b7f5abe | 244 | * |
a52fde77 | 245 | * @param requestedEndTime |
d862bcb3 | 246 | * The greatest timestamp present in the history tree |
a52fde77 | 247 | */ |
8d47cc34 | 248 | public void closeTree(long requestedEndTime) { |
412a0225 | 249 | /* This is an important operation, queries can wait */ |
0e9b2f07 | 250 | synchronized (fLatestBranch) { |
412a0225 AM |
251 | /* |
252 | * Work-around the "empty branches" that get created when the root | |
253 | * node becomes full. Overwrite the tree's end time with the | |
254 | * original wanted end-time, to ensure no queries are sent into | |
255 | * those empty nodes. | |
256 | * | |
257 | * This won't be needed once extended nodes are implemented. | |
258 | */ | |
0e9b2f07 | 259 | fTreeEnd = requestedEndTime; |
6a1074ce | 260 | |
412a0225 | 261 | /* Close off the latest branch of the tree */ |
0e9b2f07 GB |
262 | for (int i = 0; i < fLatestBranch.size(); i++) { |
263 | fLatestBranch.get(i).closeThisNode(fTreeEnd); | |
264 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
412a0225 | 265 | } |
a52fde77 | 266 | |
0e9b2f07 | 267 | try (FileChannel fc = fTreeIO.getFcOut();) { |
412a0225 AM |
268 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); |
269 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
270 | buffer.clear(); | |
a52fde77 | 271 | |
412a0225 AM |
272 | /* Save the config of the tree to the header of the file */ |
273 | fc.position(0); | |
a52fde77 | 274 | |
412a0225 | 275 | buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); |
a52fde77 | 276 | |
412a0225 | 277 | buffer.putInt(FILE_VERSION); |
0e9b2f07 | 278 | buffer.putInt(fConfig.getProviderVersion()); |
a52fde77 | 279 | |
0e9b2f07 GB |
280 | buffer.putInt(fConfig.getBlockSize()); |
281 | buffer.putInt(fConfig.getMaxChildren()); | |
a52fde77 | 282 | |
0e9b2f07 | 283 | buffer.putInt(fNodeCount); |
a52fde77 | 284 | |
412a0225 | 285 | /* root node seq. nb */ |
0e9b2f07 | 286 | buffer.putInt(fLatestBranch.get(0).getSequenceNumber()); |
a52fde77 | 287 | |
412a0225 | 288 | /* start time of this history */ |
0e9b2f07 | 289 | buffer.putLong(fLatestBranch.get(0).getNodeStart()); |
fb12b0c2 | 290 | |
412a0225 AM |
291 | buffer.flip(); |
292 | int res = fc.write(buffer); | |
293 | assert (res <= TREE_HEADER_SIZE); | |
294 | /* done writing the file header */ | |
a52fde77 | 295 | |
412a0225 AM |
296 | } catch (IOException e) { |
297 | /* | |
298 | * If we were able to write so far, there should not be any | |
299 | * problem at this point... | |
300 | */ | |
301 | throw new RuntimeException("State system write error"); //$NON-NLS-1$ | |
302 | } | |
a52fde77 | 303 | } |
a52fde77 AM |
304 | } |
305 | ||
dbdc452f AM |
306 | // ------------------------------------------------------------------------ |
307 | // Accessors | |
308 | // ------------------------------------------------------------------------ | |
ab604305 | 309 | |
8d47cc34 AM |
310 | /** |
311 | * Get the start time of this tree. | |
312 | * | |
313 | * @return The start time | |
314 | */ | |
315 | public long getTreeStart() { | |
0e9b2f07 | 316 | return fConfig.getTreeStart(); |
a52fde77 AM |
317 | } |
318 | ||
8d47cc34 AM |
319 | /** |
320 | * Get the current end time of this tree. | |
321 | * | |
322 | * @return The end time | |
323 | */ | |
324 | public long getTreeEnd() { | |
0e9b2f07 | 325 | return fTreeEnd; |
a52fde77 AM |
326 | } |
327 | ||
8d47cc34 AM |
328 | /** |
329 | * Get the number of nodes in this tree. | |
330 | * | |
331 | * @return The number of nodes | |
332 | */ | |
333 | public int getNodeCount() { | |
0e9b2f07 | 334 | return fNodeCount; |
a52fde77 AM |
335 | } |
336 | ||
8d47cc34 | 337 | /** |
412a0225 | 338 | * Get the current root node of this tree |
8d47cc34 | 339 | * |
412a0225 | 340 | * @return The root node |
8d47cc34 | 341 | */ |
bb7f92ce | 342 | public HTNode getRootNode() { |
0e9b2f07 | 343 | return fLatestBranch.get(0); |
cb42195c AM |
344 | } |
345 | ||
f3476b68 GB |
346 | /** |
347 | * Return the latest branch of the tree. That branch is immutable. Used for | |
348 | * unit testing and debugging. | |
349 | * | |
350 | * @return The immutable latest branch | |
351 | */ | |
a10a38ae | 352 | @VisibleForTesting |
aa353506 | 353 | protected List<@NonNull HTNode> getLatestBranch() { |
f3476b68 GB |
354 | return ImmutableList.copyOf(fLatestBranch); |
355 | } | |
356 | ||
a10a38ae GB |
357 | /** |
358 | * Read a node at sequence number | |
359 | * | |
360 | * @param seqNum | |
361 | * The sequence number of the node to read | |
362 | * @return The HTNode object | |
363 | * @throws ClosedChannelException | |
364 | * Exception thrown when reading the node | |
365 | */ | |
366 | @VisibleForTesting | |
367 | protected @NonNull HTNode getNode(int seqNum) throws ClosedChannelException { | |
368 | // First, check in the latest branch if the node is there | |
369 | for (HTNode node : fLatestBranch) { | |
370 | if (node.getSequenceNumber() == seqNum) { | |
371 | return node; | |
372 | } | |
373 | } | |
374 | return fTreeIO.readNode(seqNum); | |
375 | } | |
376 | ||
360f899e EB |
377 | // ------------------------------------------------------------------------ |
378 | // HT_IO interface | |
379 | // ------------------------------------------------------------------------ | |
380 | ||
8d47cc34 AM |
381 | /** |
382 | * Return the FileInputStream reader with which we will read an attribute | |
383 | * tree (it will be sought to the correct position). | |
384 | * | |
385 | * @return The FileInputStream indicating the file and position from which | |
386 | * the attribute tree can be read. | |
387 | */ | |
388 | public FileInputStream supplyATReader() { | |
0e9b2f07 | 389 | return fTreeIO.supplyATReader(getNodeCount()); |
360f899e EB |
390 | } |
391 | ||
8d47cc34 AM |
392 | /** |
393 | * Return the file to which we will write the attribute tree. | |
394 | * | |
395 | * @return The file to which we will write the attribute tree | |
396 | */ | |
397 | public File supplyATWriterFile() { | |
0e9b2f07 | 398 | return fConfig.getStateFile(); |
360f899e EB |
399 | } |
400 | ||
8d47cc34 AM |
401 | /** |
402 | * Return the position in the file (given by {@link #supplyATWriterFile}) | |
403 | * where to start writing the attribute tree. | |
404 | * | |
405 | * @return The position in the file where to start writing | |
406 | */ | |
407 | public long supplyATWriterFilePos() { | |
360f899e | 408 | return HistoryTree.TREE_HEADER_SIZE |
0e9b2f07 | 409 | + ((long) getNodeCount() * fConfig.getBlockSize()); |
360f899e EB |
410 | } |
411 | ||
8d47cc34 AM |
412 | /** |
413 | * Read a node from the tree. | |
414 | * | |
415 | * @param seqNumber | |
416 | * The sequence number of the node to read | |
417 | * @return The node | |
418 | * @throws ClosedChannelException | |
419 | * If the tree IO is unavailable | |
420 | */ | |
421 | public HTNode readNode(int seqNumber) throws ClosedChannelException { | |
360f899e | 422 | /* Try to read the node from memory */ |
0e9b2f07 GB |
423 | synchronized (fLatestBranch) { |
424 | for (HTNode node : fLatestBranch) { | |
412a0225 AM |
425 | if (node.getSequenceNumber() == seqNumber) { |
426 | return node; | |
427 | } | |
360f899e EB |
428 | } |
429 | } | |
430 | ||
431 | /* Read the node from disk */ | |
0e9b2f07 | 432 | return fTreeIO.readNode(seqNumber); |
360f899e EB |
433 | } |
434 | ||
8d47cc34 AM |
435 | /** |
436 | * Write a node object to the history file. | |
437 | * | |
438 | * @param node | |
439 | * The node to write to disk | |
440 | */ | |
441 | public void writeNode(HTNode node) { | |
0e9b2f07 | 442 | fTreeIO.writeNode(node); |
360f899e EB |
443 | } |
444 | ||
8d47cc34 AM |
445 | /** |
446 | * Close the history file. | |
447 | */ | |
448 | public void closeFile() { | |
0e9b2f07 | 449 | fTreeIO.closeFile(); |
360f899e EB |
450 | } |
451 | ||
8d47cc34 AM |
452 | /** |
453 | * Delete the history file. | |
454 | */ | |
455 | public void deleteFile() { | |
0e9b2f07 | 456 | fTreeIO.deleteFile(); |
360f899e EB |
457 | } |
458 | ||
dbdc452f AM |
459 | // ------------------------------------------------------------------------ |
460 | // Operations | |
461 | // ------------------------------------------------------------------------ | |
462 | ||
a52fde77 | 463 | /** |
8d47cc34 | 464 | * Insert an interval in the tree. |
3b7f5abe | 465 | * |
a52fde77 | 466 | * @param interval |
d862bcb3 | 467 | * The interval to be inserted |
8d47cc34 AM |
468 | * @throws TimeRangeException |
469 | * If the start of end time of the interval are invalid | |
a52fde77 | 470 | */ |
8d47cc34 | 471 | public void insertInterval(HTInterval interval) throws TimeRangeException { |
0e9b2f07 GB |
472 | if (interval.getStartTime() < fConfig.getTreeStart()) { |
473 | throw new TimeRangeException("Interval Start:" + interval.getStartTime() + ", Config Start:" + fConfig.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$ | |
a52fde77 | 474 | } |
0e9b2f07 | 475 | tryInsertAtNode(interval, fLatestBranch.size() - 1); |
a52fde77 AM |
476 | } |
477 | ||
478 | /** | |
479 | * Inner method to find in which node we should add the interval. | |
3b7f5abe | 480 | * |
a52fde77 AM |
481 | * @param interval |
482 | * The interval to add to the tree | |
483 | * @param indexOfNode | |
484 | * The index *in the latestBranch* where we are trying the | |
485 | * insertion | |
486 | */ | |
487 | private void tryInsertAtNode(HTInterval interval, int indexOfNode) { | |
0e9b2f07 | 488 | HTNode targetNode = fLatestBranch.get(indexOfNode); |
a52fde77 AM |
489 | |
490 | /* Verify if there is enough room in this node to store this interval */ | |
59d30d83 | 491 | if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) { |
a52fde77 AM |
492 | /* Nope, not enough room. Insert in a new sibling instead. */ |
493 | addSiblingNode(indexOfNode); | |
0e9b2f07 | 494 | tryInsertAtNode(interval, fLatestBranch.size() - 1); |
a52fde77 AM |
495 | return; |
496 | } | |
497 | ||
498 | /* Make sure the interval time range fits this node */ | |
499 | if (interval.getStartTime() < targetNode.getNodeStart()) { | |
500 | /* | |
501 | * No, this interval starts before the startTime of this node. We | |
502 | * need to check recursively in parents if it can fit. | |
503 | */ | |
a52fde77 AM |
504 | tryInsertAtNode(interval, indexOfNode - 1); |
505 | return; | |
506 | } | |
507 | ||
508 | /* | |
509 | * Ok, there is room, and the interval fits in this time slot. Let's add | |
510 | * it. | |
511 | */ | |
512 | targetNode.addInterval(interval); | |
513 | ||
514 | /* Update treeEnd if needed */ | |
0e9b2f07 GB |
515 | if (interval.getEndTime() > fTreeEnd) { |
516 | fTreeEnd = interval.getEndTime(); | |
a52fde77 | 517 | } |
a52fde77 AM |
518 | } |
519 | ||
520 | /** | |
521 | * Method to add a sibling to any node in the latest branch. This will add | |
522 | * children back down to the leaf level, if needed. | |
3b7f5abe | 523 | * |
a52fde77 AM |
524 | * @param indexOfNode |
525 | * The index in latestBranch where we start adding | |
526 | */ | |
527 | private void addSiblingNode(int indexOfNode) { | |
0e9b2f07 GB |
528 | synchronized (fLatestBranch) { |
529 | final long splitTime = fTreeEnd; | |
a52fde77 | 530 | |
0e9b2f07 | 531 | if (indexOfNode >= fLatestBranch.size()) { |
bb7f92ce FW |
532 | /* |
533 | * We need to make sure (indexOfNode - 1) doesn't get the last | |
534 | * node in the branch, because that one is a Leaf Node. | |
535 | */ | |
536 | throw new IllegalStateException(); | |
537 | } | |
a52fde77 | 538 | |
412a0225 AM |
539 | /* Check if we need to add a new root node */ |
540 | if (indexOfNode == 0) { | |
541 | addNewRootNode(); | |
542 | return; | |
543 | } | |
a52fde77 | 544 | |
412a0225 | 545 | /* Check if we can indeed add a child to the target parent */ |
0e9b2f07 | 546 | if (((CoreNode) fLatestBranch.get(indexOfNode - 1)).getNbChildren() == fConfig.getMaxChildren()) { |
412a0225 AM |
547 | /* If not, add a branch starting one level higher instead */ |
548 | addSiblingNode(indexOfNode - 1); | |
549 | return; | |
550 | } | |
a52fde77 | 551 | |
412a0225 | 552 | /* Split off the new branch from the old one */ |
0e9b2f07 GB |
553 | for (int i = indexOfNode; i < fLatestBranch.size(); i++) { |
554 | fLatestBranch.get(i).closeThisNode(splitTime); | |
555 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
a52fde77 | 556 | |
0e9b2f07 | 557 | CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); |
bb7f92ce FW |
558 | HTNode newNode; |
559 | ||
0e9b2f07 | 560 | switch (fLatestBranch.get(i).getNodeType()) { |
bb7f92ce FW |
561 | case CORE: |
562 | newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1); | |
563 | break; | |
564 | case LEAF: | |
565 | newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); | |
566 | break; | |
567 | default: | |
568 | throw new IllegalStateException(); | |
569 | } | |
a52fde77 | 570 | |
bb7f92ce | 571 | prevNode.linkNewChild(newNode); |
0e9b2f07 | 572 | fLatestBranch.set(i, newNode); |
412a0225 | 573 | } |
a52fde77 | 574 | } |
a52fde77 AM |
575 | } |
576 | ||
577 | /** | |
578 | * Similar to the previous method, except here we rebuild a completely new | |
579 | * latestBranch | |
580 | */ | |
581 | private void addNewRootNode() { | |
0e9b2f07 | 582 | final long splitTime = fTreeEnd; |
a52fde77 | 583 | |
0e9b2f07 GB |
584 | HTNode oldRootNode = fLatestBranch.get(0); |
585 | CoreNode newRootNode = initNewCoreNode(-1, fConfig.getTreeStart()); | |
a52fde77 AM |
586 | |
587 | /* Tell the old root node that it isn't root anymore */ | |
588 | oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); | |
589 | ||
590 | /* Close off the whole current latestBranch */ | |
412a0225 | 591 | |
0e9b2f07 GB |
592 | for (int i = 0; i < fLatestBranch.size(); i++) { |
593 | fLatestBranch.get(i).closeThisNode(splitTime); | |
594 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
a52fde77 AM |
595 | } |
596 | ||
597 | /* Link the new root to its first child (the previous root node) */ | |
598 | newRootNode.linkNewChild(oldRootNode); | |
599 | ||
600 | /* Rebuild a new latestBranch */ | |
0e9b2f07 GB |
601 | int depth = fLatestBranch.size(); |
602 | fLatestBranch.clear(); | |
603 | fLatestBranch.add(newRootNode); | |
bb7f92ce FW |
604 | |
605 | // Create new coreNode | |
7c247a0f | 606 | for (int i = 1; i < depth; i++) { |
0e9b2f07 | 607 | CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); |
b2ca67ca | 608 | CoreNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), |
a52fde77 AM |
609 | splitTime + 1); |
610 | prevNode.linkNewChild(newNode); | |
0e9b2f07 | 611 | fLatestBranch.add(newNode); |
a52fde77 | 612 | } |
bb7f92ce FW |
613 | |
614 | // Create the new leafNode | |
7c247a0f | 615 | CoreNode prevNode = (CoreNode) fLatestBranch.get(depth - 1); |
b2ca67ca | 616 | LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); |
bb7f92ce | 617 | prevNode.linkNewChild(newNode); |
0e9b2f07 | 618 | fLatestBranch.add(newNode); |
a52fde77 AM |
619 | } |
620 | ||
621 | /** | |
bb7f92ce | 622 | * Add a new empty core node to the tree. |
3b7f5abe | 623 | * |
a52fde77 AM |
624 | * @param parentSeqNumber |
625 | * Sequence number of this node's parent | |
626 | * @param startTime | |
627 | * Start time of the new node | |
628 | * @return The newly created node | |
629 | */ | |
aa353506 | 630 | private @NonNull CoreNode initNewCoreNode(int parentSeqNumber, long startTime) { |
0e9b2f07 | 631 | CoreNode newNode = new CoreNode(fConfig, fNodeCount, parentSeqNumber, |
a52fde77 | 632 | startTime); |
0e9b2f07 | 633 | fNodeCount++; |
a52fde77 AM |
634 | return newNode; |
635 | } | |
636 | ||
bb7f92ce FW |
637 | /** |
638 | * Add a new empty leaf node to the tree. | |
639 | * | |
640 | * @param parentSeqNumber | |
641 | * Sequence number of this node's parent | |
642 | * @param startTime | |
643 | * Start time of the new node | |
644 | * @return The newly created node | |
645 | */ | |
aa353506 | 646 | private @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) { |
0e9b2f07 | 647 | LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber, |
bb7f92ce | 648 | startTime); |
0e9b2f07 | 649 | fNodeCount++; |
bb7f92ce FW |
650 | return newNode; |
651 | } | |
652 | ||
a52fde77 AM |
653 | /** |
654 | * Inner method to select the next child of the current node intersecting | |
655 | * the given timestamp. Useful for moving down the tree following one | |
656 | * branch. | |
3b7f5abe | 657 | * |
a52fde77 | 658 | * @param currentNode |
d862bcb3 | 659 | * The node on which the request is made |
a52fde77 | 660 | * @param t |
d862bcb3 | 661 | * The timestamp to choose which child is the next one |
a52fde77 | 662 | * @return The child node intersecting t |
3b7f5abe AM |
663 | * @throws ClosedChannelException |
664 | * If the file channel was closed while we were reading the tree | |
a52fde77 | 665 | */ |
8d47cc34 | 666 | public HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException { |
a52fde77 AM |
667 | assert (currentNode.getNbChildren() > 0); |
668 | int potentialNextSeqNb = currentNode.getSequenceNumber(); | |
669 | ||
670 | for (int i = 0; i < currentNode.getNbChildren(); i++) { | |
671 | if (t >= currentNode.getChildStart(i)) { | |
672 | potentialNextSeqNb = currentNode.getChild(i); | |
673 | } else { | |
674 | break; | |
675 | } | |
676 | } | |
d862bcb3 | 677 | |
a52fde77 AM |
678 | /* |
679 | * Once we exit this loop, we should have found a children to follow. If | |
680 | * we didn't, there's a problem. | |
681 | */ | |
822798a3 GB |
682 | if (potentialNextSeqNb == currentNode.getSequenceNumber()) { |
683 | throw new IllegalStateException("No next child node found"); //$NON-NLS-1$ | |
684 | } | |
a52fde77 AM |
685 | |
686 | /* | |
687 | * Since this code path is quite performance-critical, avoid iterating | |
688 | * through the whole latestBranch array if we know for sure the next | |
689 | * node has to be on disk | |
690 | */ | |
045badfe | 691 | if (currentNode.isOnDisk()) { |
0e9b2f07 | 692 | return fTreeIO.readNode(potentialNextSeqNb); |
a52fde77 | 693 | } |
83c31d28 | 694 | return readNode(potentialNextSeqNb); |
a52fde77 AM |
695 | } |
696 | ||
8d47cc34 AM |
697 | /** |
698 | * Get the current size of the history file. | |
699 | * | |
700 | * @return The history file size | |
701 | */ | |
702 | public long getFileSize() { | |
0e9b2f07 | 703 | return fConfig.getStateFile().length(); |
a52fde77 AM |
704 | } |
705 | ||
3b7f5abe AM |
706 | // ------------------------------------------------------------------------ |
707 | // Test/debugging methods | |
708 | // ------------------------------------------------------------------------ | |
a52fde77 | 709 | |
a52fde77 AM |
710 | /* Only used for debugging, shouldn't be externalized */ |
711 | @SuppressWarnings("nls") | |
712 | @Override | |
713 | public String toString() { | |
714 | return "Information on the current tree:\n\n" + "Blocksize: " | |
0e9b2f07 GB |
715 | + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: " |
716 | + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount | |
717 | + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n" | |
718 | + "Size of the treefile: " + getFileSize() + "\n" | |
a52fde77 | 719 | + "Root node has sequence number: " |
0e9b2f07 | 720 | + fLatestBranch.get(0).getSequenceNumber() + "\n" |
a52fde77 | 721 | + "'Latest leaf' has sequence number: " |
0e9b2f07 | 722 | + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber(); |
a52fde77 AM |
723 | } |
724 | ||
a52fde77 AM |
725 | /** |
726 | * Start at currentNode and print the contents of all its children, in | |
727 | * pre-order. Give the root node in parameter to visit the whole tree, and | |
728 | * have a nice overview. | |
729 | */ | |
d862bcb3 | 730 | /* Only used for debugging, shouldn't be externalized */ |
a52fde77 AM |
731 | @SuppressWarnings("nls") |
732 | private void preOrderPrint(PrintWriter writer, boolean printIntervals, | |
dbf883bb | 733 | HTNode currentNode, int curDepth, long ts) { |
a52fde77 AM |
734 | |
735 | writer.println(currentNode.toString()); | |
dbf883bb GB |
736 | /* Print intervals only if timestamp is negative or within the range of the node */ |
737 | if (printIntervals && | |
738 | (ts <= 0 || | |
739 | (ts >= currentNode.getNodeStart() && ts <= currentNode.getNodeEnd()))) { | |
a52fde77 AM |
740 | currentNode.debugPrintIntervals(writer); |
741 | } | |
a52fde77 | 742 | |
bb7f92ce FW |
743 | switch (currentNode.getNodeType()) { |
744 | case LEAF: | |
745 | /* Stop if it's the leaf node */ | |
746 | return; | |
747 | ||
748 | case CORE: | |
749 | try { | |
750 | final CoreNode node = (CoreNode) currentNode; | |
751 | /* Print the extensions, if any */ | |
752 | int extension = node.getExtensionSequenceNumber(); | |
753 | while (extension != -1) { | |
0e9b2f07 | 754 | HTNode nextNode = fTreeIO.readNode(extension); |
dbf883bb | 755 | preOrderPrint(writer, printIntervals, nextNode, curDepth, ts); |
bb7f92ce FW |
756 | } |
757 | ||
758 | /* Print the child nodes */ | |
759 | for (int i = 0; i < node.getNbChildren(); i++) { | |
0e9b2f07 | 760 | HTNode nextNode = fTreeIO.readNode(node.getChild(i)); |
bb7f92ce FW |
761 | for (int j = 0; j < curDepth; j++) { |
762 | writer.print(" "); | |
763 | } | |
764 | writer.print("+-"); | |
dbf883bb | 765 | preOrderPrint(writer, printIntervals, nextNode, curDepth + 1, ts); |
3b7f5abe | 766 | } |
bb7f92ce | 767 | } catch (ClosedChannelException e) { |
bcec0116 | 768 | Activator.getDefault().logError(e.getMessage()); |
a52fde77 | 769 | } |
bb7f92ce FW |
770 | break; |
771 | ||
772 | default: | |
773 | break; | |
a52fde77 | 774 | } |
a52fde77 AM |
775 | } |
776 | ||
777 | /** | |
778 | * Print out the full tree for debugging purposes | |
3b7f5abe | 779 | * |
a52fde77 AM |
780 | * @param writer |
781 | * PrintWriter in which to write the output | |
782 | * @param printIntervals | |
d862bcb3 | 783 | * Flag to enable full output of the interval information |
dbf883bb GB |
784 | * @param ts |
785 | * The timestamp that nodes have to intersect for intervals to be | |
786 | * printed. A negative value will print intervals for all nodes. | |
787 | * The timestamp only applies if printIntervals is true. | |
a52fde77 | 788 | */ |
dbf883bb | 789 | public void debugPrintFullTree(PrintWriter writer, boolean printIntervals, long ts) { |
a52fde77 | 790 | /* Only used for debugging, shouldn't be externalized */ |
d862bcb3 | 791 | |
dbf883bb | 792 | preOrderPrint(writer, false, fLatestBranch.get(0), 0, ts); |
a52fde77 AM |
793 | |
794 | if (printIntervals) { | |
dbf883bb | 795 | preOrderPrint(writer, true, fLatestBranch.get(0), 0, ts); |
a52fde77 AM |
796 | } |
797 | writer.println('\n'); | |
798 | } | |
799 | ||
800 | } |