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