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