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