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