Commit | Line | Data |
---|---|---|
a52fde77 | 1 | /******************************************************************************* |
60ae41e1 | 2 | * Copyright (c) 2012, 2014 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 */ |
412a0225 | 71 | private final 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; |
412a0225 | 99 | latestBranch = Collections.synchronizedList(new ArrayList<CoreNode>()); |
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 | 190 | |
412a0225 AM |
191 | this.latestBranch = buildLatestBranch(rootNodeSeqNb); |
192 | this.treeEnd = getRootNode().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 | */ | |
412a0225 | 198 | if (startTime != getRootNode().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 | ||
412a0225 AM |
204 | /** |
205 | * Rebuild the latestBranch "cache" object by reading the nodes from disk | |
206 | * (When we are opening an existing file on disk and want to append to it, | |
207 | * for example). | |
208 | * | |
209 | * @param rootNodeSeqNb | |
210 | * The sequence number of the root node, so we know where to | |
211 | * start | |
212 | * @throws ClosedChannelException | |
213 | */ | |
214 | private List<CoreNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { | |
215 | HTNode nextChildNode; | |
216 | ||
217 | List<CoreNode> list = new ArrayList<>(); | |
218 | ||
219 | nextChildNode = treeIO.readNode(rootNodeSeqNb); | |
220 | list.add((CoreNode) nextChildNode); | |
221 | while (list.get(list.size() - 1).getNbChildren() > 0) { | |
222 | nextChildNode = treeIO.readNode(list.get(list.size() - 1).getLatestChild()); | |
223 | list.add((CoreNode) nextChildNode); | |
224 | } | |
225 | return Collections.synchronizedList(list); | |
226 | } | |
227 | ||
a52fde77 AM |
228 | /** |
229 | * "Save" the tree to disk. This method will cause the treeIO object to | |
230 | * commit all nodes to disk and then return the RandomAccessFile descriptor | |
231 | * so the Tree object can save its configuration into the header of the | |
232 | * file. | |
3b7f5abe | 233 | * |
a52fde77 | 234 | * @param requestedEndTime |
d862bcb3 | 235 | * The greatest timestamp present in the history tree |
a52fde77 | 236 | */ |
8d47cc34 | 237 | public void closeTree(long requestedEndTime) { |
412a0225 AM |
238 | /* This is an important operation, queries can wait */ |
239 | synchronized (latestBranch) { | |
240 | /* | |
241 | * Work-around the "empty branches" that get created when the root | |
242 | * node becomes full. Overwrite the tree's end time with the | |
243 | * original wanted end-time, to ensure no queries are sent into | |
244 | * those empty nodes. | |
245 | * | |
246 | * This won't be needed once extended nodes are implemented. | |
247 | */ | |
248 | this.treeEnd = requestedEndTime; | |
6a1074ce | 249 | |
412a0225 AM |
250 | /* Close off the latest branch of the tree */ |
251 | for (int i = 0; i < latestBranch.size(); i++) { | |
252 | latestBranch.get(i).closeThisNode(treeEnd); | |
253 | treeIO.writeNode(latestBranch.get(i)); | |
254 | } | |
a52fde77 | 255 | |
412a0225 AM |
256 | try (FileChannel fc = treeIO.getFcOut();) { |
257 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); | |
258 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
259 | buffer.clear(); | |
a52fde77 | 260 | |
412a0225 AM |
261 | /* Save the config of the tree to the header of the file */ |
262 | fc.position(0); | |
a52fde77 | 263 | |
412a0225 | 264 | buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); |
a52fde77 | 265 | |
412a0225 AM |
266 | buffer.putInt(FILE_VERSION); |
267 | buffer.putInt(config.getProviderVersion()); | |
a52fde77 | 268 | |
412a0225 AM |
269 | buffer.putInt(config.getBlockSize()); |
270 | buffer.putInt(config.getMaxChildren()); | |
a52fde77 | 271 | |
412a0225 | 272 | buffer.putInt(nodeCount); |
a52fde77 | 273 | |
412a0225 AM |
274 | /* root node seq. nb */ |
275 | buffer.putInt(latestBranch.get(0).getSequenceNumber()); | |
a52fde77 | 276 | |
412a0225 AM |
277 | /* start time of this history */ |
278 | buffer.putLong(latestBranch.get(0).getNodeStart()); | |
fb12b0c2 | 279 | |
412a0225 AM |
280 | buffer.flip(); |
281 | int res = fc.write(buffer); | |
282 | assert (res <= TREE_HEADER_SIZE); | |
283 | /* done writing the file header */ | |
a52fde77 | 284 | |
412a0225 AM |
285 | } catch (IOException e) { |
286 | /* | |
287 | * If we were able to write so far, there should not be any | |
288 | * problem at this point... | |
289 | */ | |
290 | throw new RuntimeException("State system write error"); //$NON-NLS-1$ | |
291 | } | |
a52fde77 | 292 | } |
a52fde77 AM |
293 | } |
294 | ||
dbdc452f AM |
295 | // ------------------------------------------------------------------------ |
296 | // Accessors | |
297 | // ------------------------------------------------------------------------ | |
ab604305 | 298 | |
8d47cc34 AM |
299 | /** |
300 | * Get the start time of this tree. | |
301 | * | |
302 | * @return The start time | |
303 | */ | |
304 | public long getTreeStart() { | |
cb42195c | 305 | return config.getTreeStart(); |
a52fde77 AM |
306 | } |
307 | ||
8d47cc34 AM |
308 | /** |
309 | * Get the current end time of this tree. | |
310 | * | |
311 | * @return The end time | |
312 | */ | |
313 | public long getTreeEnd() { | |
a52fde77 AM |
314 | return treeEnd; |
315 | } | |
316 | ||
8d47cc34 AM |
317 | /** |
318 | * Get the number of nodes in this tree. | |
319 | * | |
320 | * @return The number of nodes | |
321 | */ | |
322 | public int getNodeCount() { | |
a52fde77 AM |
323 | return nodeCount; |
324 | } | |
325 | ||
8d47cc34 | 326 | /** |
412a0225 | 327 | * Get the current root node of this tree |
8d47cc34 | 328 | * |
412a0225 | 329 | * @return The root node |
8d47cc34 | 330 | */ |
412a0225 AM |
331 | public CoreNode getRootNode() { |
332 | return latestBranch.get(0); | |
cb42195c AM |
333 | } |
334 | ||
360f899e EB |
335 | // ------------------------------------------------------------------------ |
336 | // HT_IO interface | |
337 | // ------------------------------------------------------------------------ | |
338 | ||
8d47cc34 AM |
339 | /** |
340 | * Return the FileInputStream reader with which we will read an attribute | |
341 | * tree (it will be sought to the correct position). | |
342 | * | |
343 | * @return The FileInputStream indicating the file and position from which | |
344 | * the attribute tree can be read. | |
345 | */ | |
346 | public FileInputStream supplyATReader() { | |
347 | return treeIO.supplyATReader(getNodeCount()); | |
360f899e EB |
348 | } |
349 | ||
8d47cc34 AM |
350 | /** |
351 | * Return the file to which we will write the attribute tree. | |
352 | * | |
353 | * @return The file to which we will write the attribute tree | |
354 | */ | |
355 | public File supplyATWriterFile() { | |
356 | return config.getStateFile(); | |
360f899e EB |
357 | } |
358 | ||
8d47cc34 AM |
359 | /** |
360 | * Return the position in the file (given by {@link #supplyATWriterFile}) | |
361 | * where to start writing the attribute tree. | |
362 | * | |
363 | * @return The position in the file where to start writing | |
364 | */ | |
365 | public long supplyATWriterFilePos() { | |
360f899e EB |
366 | return HistoryTree.TREE_HEADER_SIZE |
367 | + ((long) getNodeCount() * config.getBlockSize()); | |
368 | } | |
369 | ||
8d47cc34 AM |
370 | /** |
371 | * Read a node from the tree. | |
372 | * | |
373 | * @param seqNumber | |
374 | * The sequence number of the node to read | |
375 | * @return The node | |
376 | * @throws ClosedChannelException | |
377 | * If the tree IO is unavailable | |
378 | */ | |
379 | public HTNode readNode(int seqNumber) throws ClosedChannelException { | |
360f899e | 380 | /* Try to read the node from memory */ |
412a0225 AM |
381 | synchronized (latestBranch) { |
382 | for (HTNode node : latestBranch) { | |
383 | if (node.getSequenceNumber() == seqNumber) { | |
384 | return node; | |
385 | } | |
360f899e EB |
386 | } |
387 | } | |
388 | ||
389 | /* Read the node from disk */ | |
390 | return treeIO.readNode(seqNumber); | |
391 | } | |
392 | ||
8d47cc34 AM |
393 | /** |
394 | * Write a node object to the history file. | |
395 | * | |
396 | * @param node | |
397 | * The node to write to disk | |
398 | */ | |
399 | public void writeNode(HTNode node) { | |
360f899e EB |
400 | treeIO.writeNode(node); |
401 | } | |
402 | ||
8d47cc34 AM |
403 | /** |
404 | * Close the history file. | |
405 | */ | |
406 | public void closeFile() { | |
360f899e EB |
407 | treeIO.closeFile(); |
408 | } | |
409 | ||
8d47cc34 AM |
410 | /** |
411 | * Delete the history file. | |
412 | */ | |
413 | public void deleteFile() { | |
360f899e EB |
414 | treeIO.deleteFile(); |
415 | } | |
416 | ||
dbdc452f AM |
417 | // ------------------------------------------------------------------------ |
418 | // Operations | |
419 | // ------------------------------------------------------------------------ | |
420 | ||
a52fde77 | 421 | /** |
8d47cc34 | 422 | * Insert an interval in the tree. |
3b7f5abe | 423 | * |
a52fde77 | 424 | * @param interval |
d862bcb3 | 425 | * The interval to be inserted |
8d47cc34 AM |
426 | * @throws TimeRangeException |
427 | * If the start of end time of the interval are invalid | |
a52fde77 | 428 | */ |
8d47cc34 | 429 | public void insertInterval(HTInterval interval) throws TimeRangeException { |
cb42195c | 430 | if (interval.getStartTime() < config.getTreeStart()) { |
a52fde77 AM |
431 | throw new TimeRangeException(); |
432 | } | |
433 | tryInsertAtNode(interval, latestBranch.size() - 1); | |
434 | } | |
435 | ||
436 | /** | |
437 | * Inner method to find in which node we should add the interval. | |
3b7f5abe | 438 | * |
a52fde77 AM |
439 | * @param interval |
440 | * The interval to add to the tree | |
441 | * @param indexOfNode | |
442 | * The index *in the latestBranch* where we are trying the | |
443 | * insertion | |
444 | */ | |
445 | private void tryInsertAtNode(HTInterval interval, int indexOfNode) { | |
446 | HTNode targetNode = latestBranch.get(indexOfNode); | |
447 | ||
448 | /* Verify if there is enough room in this node to store this interval */ | |
449 | if (interval.getIntervalSize() > targetNode.getNodeFreeSpace()) { | |
450 | /* Nope, not enough room. Insert in a new sibling instead. */ | |
451 | addSiblingNode(indexOfNode); | |
452 | tryInsertAtNode(interval, latestBranch.size() - 1); | |
453 | return; | |
454 | } | |
455 | ||
456 | /* Make sure the interval time range fits this node */ | |
457 | if (interval.getStartTime() < targetNode.getNodeStart()) { | |
458 | /* | |
459 | * No, this interval starts before the startTime of this node. We | |
460 | * need to check recursively in parents if it can fit. | |
461 | */ | |
462 | assert (indexOfNode >= 1); | |
463 | tryInsertAtNode(interval, indexOfNode - 1); | |
464 | return; | |
465 | } | |
466 | ||
467 | /* | |
468 | * Ok, there is room, and the interval fits in this time slot. Let's add | |
469 | * it. | |
470 | */ | |
471 | targetNode.addInterval(interval); | |
472 | ||
473 | /* Update treeEnd if needed */ | |
474 | if (interval.getEndTime() > this.treeEnd) { | |
475 | this.treeEnd = interval.getEndTime(); | |
476 | } | |
a52fde77 AM |
477 | } |
478 | ||
479 | /** | |
480 | * Method to add a sibling to any node in the latest branch. This will add | |
481 | * children back down to the leaf level, if needed. | |
3b7f5abe | 482 | * |
a52fde77 AM |
483 | * @param indexOfNode |
484 | * The index in latestBranch where we start adding | |
485 | */ | |
486 | private void addSiblingNode(int indexOfNode) { | |
412a0225 AM |
487 | synchronized (latestBranch) { |
488 | final long splitTime = treeEnd; | |
a52fde77 | 489 | |
412a0225 | 490 | assert (indexOfNode < latestBranch.size()); |
a52fde77 | 491 | |
412a0225 AM |
492 | /* Check if we need to add a new root node */ |
493 | if (indexOfNode == 0) { | |
494 | addNewRootNode(); | |
495 | return; | |
496 | } | |
a52fde77 | 497 | |
412a0225 AM |
498 | /* Check if we can indeed add a child to the target parent */ |
499 | if (latestBranch.get(indexOfNode - 1).getNbChildren() == config.getMaxChildren()) { | |
500 | /* If not, add a branch starting one level higher instead */ | |
501 | addSiblingNode(indexOfNode - 1); | |
502 | return; | |
503 | } | |
a52fde77 | 504 | |
412a0225 AM |
505 | /* Split off the new branch from the old one */ |
506 | for (int i = indexOfNode; i < latestBranch.size(); i++) { | |
507 | latestBranch.get(i).closeThisNode(splitTime); | |
508 | treeIO.writeNode(latestBranch.get(i)); | |
a52fde77 | 509 | |
412a0225 AM |
510 | CoreNode prevNode = latestBranch.get(i - 1); |
511 | CoreNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), | |
512 | splitTime + 1); | |
513 | prevNode.linkNewChild(newNode); | |
a52fde77 | 514 | |
412a0225 AM |
515 | latestBranch.set(i, newNode); |
516 | } | |
a52fde77 | 517 | } |
a52fde77 AM |
518 | } |
519 | ||
520 | /** | |
521 | * Similar to the previous method, except here we rebuild a completely new | |
522 | * latestBranch | |
523 | */ | |
524 | private void addNewRootNode() { | |
412a0225 | 525 | final long splitTime = this.treeEnd; |
a52fde77 | 526 | |
412a0225 AM |
527 | CoreNode oldRootNode = latestBranch.get(0); |
528 | CoreNode 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 */ | |
412a0225 AM |
534 | |
535 | for (int i = 0; i < latestBranch.size(); i++) { | |
a52fde77 AM |
536 | latestBranch.get(i).closeThisNode(splitTime); |
537 | treeIO.writeNode(latestBranch.get(i)); | |
538 | } | |
539 | ||
540 | /* Link the new root to its first child (the previous root node) */ | |
541 | newRootNode.linkNewChild(oldRootNode); | |
542 | ||
543 | /* Rebuild a new latestBranch */ | |
412a0225 AM |
544 | int depth = latestBranch.size(); |
545 | latestBranch.clear(); | |
a52fde77 | 546 | latestBranch.add(newRootNode); |
412a0225 AM |
547 | for (int i = 1; i < depth + 1; i++) { |
548 | CoreNode prevNode = latestBranch.get(i - 1); | |
549 | CoreNode newNode = initNewCoreNode(prevNode.getParentSequenceNumber(), | |
a52fde77 AM |
550 | splitTime + 1); |
551 | prevNode.linkNewChild(newNode); | |
552 | latestBranch.add(newNode); | |
553 | } | |
554 | } | |
555 | ||
556 | /** | |
557 | * Add a new empty node to the tree. | |
3b7f5abe | 558 | * |
a52fde77 AM |
559 | * @param parentSeqNumber |
560 | * Sequence number of this node's parent | |
561 | * @param startTime | |
562 | * Start time of the new node | |
563 | * @return The newly created node | |
564 | */ | |
565 | private CoreNode initNewCoreNode(int parentSeqNumber, long startTime) { | |
ffd0aa67 | 566 | CoreNode newNode = new CoreNode(config, this.nodeCount, parentSeqNumber, |
a52fde77 AM |
567 | startTime); |
568 | this.nodeCount++; | |
569 | ||
570 | /* Update the treeEnd if needed */ | |
571 | if (startTime >= this.treeEnd) { | |
572 | this.treeEnd = startTime + 1; | |
573 | } | |
574 | return newNode; | |
575 | } | |
576 | ||
577 | /** | |
578 | * Inner method to select the next child of the current node intersecting | |
579 | * the given timestamp. Useful for moving down the tree following one | |
580 | * branch. | |
3b7f5abe | 581 | * |
a52fde77 | 582 | * @param currentNode |
d862bcb3 | 583 | * The node on which the request is made |
a52fde77 | 584 | * @param t |
d862bcb3 | 585 | * The timestamp to choose which child is the next one |
a52fde77 | 586 | * @return The child node intersecting t |
3b7f5abe AM |
587 | * @throws ClosedChannelException |
588 | * If the file channel was closed while we were reading the tree | |
a52fde77 | 589 | */ |
8d47cc34 | 590 | public HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException { |
a52fde77 AM |
591 | assert (currentNode.getNbChildren() > 0); |
592 | int potentialNextSeqNb = currentNode.getSequenceNumber(); | |
593 | ||
594 | for (int i = 0; i < currentNode.getNbChildren(); i++) { | |
595 | if (t >= currentNode.getChildStart(i)) { | |
596 | potentialNextSeqNb = currentNode.getChild(i); | |
597 | } else { | |
598 | break; | |
599 | } | |
600 | } | |
d862bcb3 | 601 | |
a52fde77 AM |
602 | /* |
603 | * Once we exit this loop, we should have found a children to follow. If | |
604 | * we didn't, there's a problem. | |
605 | */ | |
606 | assert (potentialNextSeqNb != currentNode.getSequenceNumber()); | |
607 | ||
608 | /* | |
609 | * Since this code path is quite performance-critical, avoid iterating | |
610 | * through the whole latestBranch array if we know for sure the next | |
611 | * node has to be on disk | |
612 | */ | |
045badfe | 613 | if (currentNode.isOnDisk()) { |
360f899e | 614 | return treeIO.readNode(potentialNextSeqNb); |
a52fde77 | 615 | } |
83c31d28 | 616 | return readNode(potentialNextSeqNb); |
a52fde77 AM |
617 | } |
618 | ||
8d47cc34 AM |
619 | /** |
620 | * Get the current size of the history file. | |
621 | * | |
622 | * @return The history file size | |
623 | */ | |
624 | public long getFileSize() { | |
cb42195c | 625 | return config.getStateFile().length(); |
a52fde77 AM |
626 | } |
627 | ||
3b7f5abe AM |
628 | // ------------------------------------------------------------------------ |
629 | // Test/debugging methods | |
630 | // ------------------------------------------------------------------------ | |
a52fde77 | 631 | |
8d47cc34 AM |
632 | /** |
633 | * Debugging method to make sure all intervals contained in the given node | |
634 | * have valid start and end times. | |
635 | * | |
636 | * @param zenode | |
637 | * The node to check | |
638 | * @return True if everything is fine, false if there is at least one | |
639 | * invalid timestamp (end time < start time, time outside of the | |
640 | * range of the node, etc.) | |
641 | */ | |
a52fde77 | 642 | @SuppressWarnings("nls") |
8d47cc34 AM |
643 | public boolean checkNodeIntegrity(HTNode zenode) { |
644 | /* Only used for debugging, shouldn't be externalized */ | |
a52fde77 AM |
645 | HTNode otherNode; |
646 | CoreNode node; | |
ab604305 | 647 | StringBuffer buf = new StringBuffer(); |
a52fde77 AM |
648 | boolean ret = true; |
649 | ||
650 | // FIXME /* Only testing Core Nodes for now */ | |
651 | if (!(zenode instanceof CoreNode)) { | |
652 | return true; | |
653 | } | |
654 | ||
655 | node = (CoreNode) zenode; | |
656 | ||
3b7f5abe AM |
657 | try { |
658 | /* | |
659 | * Test that this node's start and end times match the start of the | |
660 | * first child and the end of the last child, respectively | |
661 | */ | |
662 | if (node.getNbChildren() > 0) { | |
663 | otherNode = treeIO.readNode(node.getChild(0)); | |
664 | if (node.getNodeStart() != otherNode.getNodeStart()) { | |
665 | buf.append("Start time of node (" + node.getNodeStart() + ") " | |
666 | + "does not match start time of first child " + "(" | |
667 | + otherNode.getNodeStart() + "), " + "node #" | |
ab604305 | 668 | + otherNode.getSequenceNumber() + ")\n"); |
a52fde77 AM |
669 | ret = false; |
670 | } | |
045badfe | 671 | if (node.isOnDisk()) { |
3b7f5abe AM |
672 | otherNode = treeIO.readNode(node.getLatestChild()); |
673 | if (node.getNodeEnd() != otherNode.getNodeEnd()) { | |
674 | buf.append("End time of node (" + node.getNodeEnd() | |
675 | + ") does not match end time of last child (" | |
676 | + otherNode.getNodeEnd() + ", node #" | |
677 | + otherNode.getSequenceNumber() + ")\n"); | |
678 | ret = false; | |
679 | } | |
680 | } | |
a52fde77 | 681 | } |
a52fde77 | 682 | |
3b7f5abe AM |
683 | /* |
684 | * Test that the childStartTimes[] array matches the real nodes' start | |
685 | * times | |
686 | */ | |
687 | for (int i = 0; i < node.getNbChildren(); i++) { | |
688 | otherNode = treeIO.readNode(node.getChild(i)); | |
689 | if (otherNode.getNodeStart() != node.getChildStart(i)) { | |
690 | buf.append(" Expected start time of child node #" | |
691 | + node.getChild(i) + ": " + node.getChildStart(i) | |
692 | + "\n" + " Actual start time of node #" | |
693 | + otherNode.getSequenceNumber() + ": " | |
694 | + otherNode.getNodeStart() + "\n"); | |
695 | ret = false; | |
696 | } | |
a52fde77 | 697 | } |
3b7f5abe AM |
698 | |
699 | } catch (ClosedChannelException e) { | |
700 | e.printStackTrace(); | |
a52fde77 AM |
701 | } |
702 | ||
703 | if (!ret) { | |
704 | System.out.println(""); | |
705 | System.out.println("SHT: Integrity check failed for node #" | |
706 | + node.getSequenceNumber() + ":"); | |
ab604305 | 707 | System.out.println(buf.toString()); |
a52fde77 AM |
708 | } |
709 | return ret; | |
710 | } | |
711 | ||
8d47cc34 AM |
712 | /** |
713 | * Check the integrity of all the nodes in the tree. Calls | |
714 | * {@link #checkNodeIntegrity} for every node in the tree. | |
715 | */ | |
716 | public void checkIntegrity() { | |
3b7f5abe AM |
717 | try { |
718 | for (int i = 0; i < nodeCount; i++) { | |
719 | checkNodeIntegrity(treeIO.readNode(i)); | |
720 | } | |
721 | } catch (ClosedChannelException e) { | |
a52fde77 AM |
722 | } |
723 | } | |
724 | ||
725 | /* Only used for debugging, shouldn't be externalized */ | |
726 | @SuppressWarnings("nls") | |
727 | @Override | |
728 | public String toString() { | |
729 | return "Information on the current tree:\n\n" + "Blocksize: " | |
cb42195c AM |
730 | + config.getBlockSize() + "\n" + "Max nb. of children per node: " |
731 | + config.getMaxChildren() + "\n" + "Number of nodes: " + nodeCount | |
a52fde77 AM |
732 | + "\n" + "Depth of the tree: " + latestBranch.size() + "\n" |
733 | + "Size of the treefile: " + this.getFileSize() + "\n" | |
734 | + "Root node has sequence number: " | |
cb42195c | 735 | + latestBranch.get(0).getSequenceNumber() + "\n" |
a52fde77 | 736 | + "'Latest leaf' has sequence number: " |
cb42195c | 737 | + latestBranch.get(latestBranch.size() - 1).getSequenceNumber(); |
a52fde77 AM |
738 | } |
739 | ||
a52fde77 AM |
740 | /** |
741 | * Start at currentNode and print the contents of all its children, in | |
742 | * pre-order. Give the root node in parameter to visit the whole tree, and | |
743 | * have a nice overview. | |
744 | */ | |
d862bcb3 | 745 | /* Only used for debugging, shouldn't be externalized */ |
a52fde77 AM |
746 | @SuppressWarnings("nls") |
747 | private void preOrderPrint(PrintWriter writer, boolean printIntervals, | |
d862bcb3 | 748 | CoreNode currentNode, int curDepth) { |
a52fde77 AM |
749 | |
750 | writer.println(currentNode.toString()); | |
751 | if (printIntervals) { | |
752 | currentNode.debugPrintIntervals(writer); | |
753 | } | |
a52fde77 | 754 | |
3b7f5abe | 755 | try { |
d862bcb3 EB |
756 | for (int i = 0; i < currentNode.getNbChildren(); i++) { |
757 | HTNode nextNode = treeIO.readNode(currentNode.getChild(i)); | |
3b7f5abe | 758 | assert (nextNode instanceof CoreNode); // TODO temporary |
d862bcb3 | 759 | for (int j = 0; j < curDepth; j++) { |
3b7f5abe AM |
760 | writer.print(" "); |
761 | } | |
762 | writer.print("+-"); | |
d862bcb3 EB |
763 | preOrderPrint(writer, printIntervals, (CoreNode) nextNode, |
764 | curDepth + 1); | |
a52fde77 | 765 | } |
3b7f5abe AM |
766 | } catch (ClosedChannelException e) { |
767 | e.printStackTrace(); | |
a52fde77 | 768 | } |
a52fde77 AM |
769 | } |
770 | ||
771 | /** | |
772 | * Print out the full tree for debugging purposes | |
3b7f5abe | 773 | * |
a52fde77 AM |
774 | * @param writer |
775 | * PrintWriter in which to write the output | |
776 | * @param printIntervals | |
d862bcb3 | 777 | * Flag to enable full output of the interval information |
a52fde77 | 778 | */ |
8d47cc34 | 779 | public void debugPrintFullTree(PrintWriter writer, boolean printIntervals) { |
a52fde77 | 780 | /* Only used for debugging, shouldn't be externalized */ |
d862bcb3 EB |
781 | |
782 | this.preOrderPrint(writer, false, latestBranch.get(0), 0); | |
a52fde77 AM |
783 | |
784 | if (printIntervals) { | |
785 | writer.println("\nDetails of intervals:"); //$NON-NLS-1$ | |
d862bcb3 | 786 | this.preOrderPrint(writer, true, latestBranch.get(0), 0); |
a52fde77 AM |
787 | } |
788 | writer.println('\n'); | |
789 | } | |
790 | ||
791 | } |