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