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