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