Commit | Line | Data |
---|---|---|
a52fde77 | 1 | /******************************************************************************* |
b2ca67ca | 2 | * Copyright (c) 2010, 2016 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; | |
a52fde77 AM |
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 | 24 | import java.util.ArrayList; |
588f11a1 | 25 | import java.util.Collection; |
cb42195c AM |
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.statesystem.core.ITmfStateSystemBuilder; |
31 | import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; | |
a52fde77 | 32 | |
a10a38ae | 33 | import com.google.common.annotations.VisibleForTesting; |
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 | */ |
3a081e85 | 42 | public class HistoryTreeClassic implements IHistoryTree { |
cb42195c | 43 | |
9a4c098d GB |
44 | /** |
45 | * The magic number for this file format. Package-private for the factory | |
46 | * class. | |
47 | */ | |
48 | static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900; | |
a52fde77 | 49 | |
a96cc6be | 50 | /** File format version. Increment when breaking compatibility. */ |
8182f36f | 51 | private static final int FILE_VERSION = 7; |
a52fde77 | 52 | |
dbdc452f AM |
53 | // ------------------------------------------------------------------------ |
54 | // Tree-specific configuration | |
55 | // ------------------------------------------------------------------------ | |
56 | ||
57 | /** Container for all the configuration constants */ | |
0e9b2f07 | 58 | private final HTConfig fConfig; |
a52fde77 | 59 | |
dbdc452f | 60 | /** Reader/writer object */ |
0e4eaca8 | 61 | private final @NonNull HT_IO fTreeIO; |
a52fde77 | 62 | |
dbdc452f | 63 | // ------------------------------------------------------------------------ |
ecb12461 | 64 | // Variable Fields (will change throughout the existence of the SHT) |
dbdc452f AM |
65 | // ------------------------------------------------------------------------ |
66 | ||
67 | /** Latest timestamp found in the tree (at any given moment) */ | |
0e9b2f07 | 68 | private long fTreeEnd; |
a52fde77 | 69 | |
360f899e | 70 | /** The total number of nodes that exists in this tree */ |
0e9b2f07 | 71 | private int fNodeCount; |
a52fde77 | 72 | |
dbdc452f | 73 | /** "Cache" to keep the active nodes in memory */ |
367e2932 | 74 | private final @NonNull List<@NonNull HTNode> fLatestBranch; |
a52fde77 | 75 | |
dbdc452f AM |
76 | // ------------------------------------------------------------------------ |
77 | // Constructors/"Destructors" | |
78 | // ------------------------------------------------------------------------ | |
79 | ||
a52fde77 | 80 | /** |
8d47cc34 AM |
81 | * Create a new State History from scratch, using a {@link HTConfig} object |
82 | * for configuration. | |
83 | * | |
84 | * @param conf | |
85 | * The config to use for this History Tree. | |
86 | * @throws IOException | |
87 | * If an error happens trying to open/write to the file | |
88 | * specified in the config | |
a52fde77 | 89 | */ |
3a081e85 | 90 | public HistoryTreeClassic(HTConfig conf) throws IOException { |
a52fde77 | 91 | /* |
bb7f92ce FW |
92 | * Simple check to make sure we have enough place in the 0th block for |
93 | * the tree configuration | |
a52fde77 | 94 | */ |
cb42195c | 95 | if (conf.getBlockSize() < TREE_HEADER_SIZE) { |
dbdc452f AM |
96 | throw new IllegalArgumentException(); |
97 | } | |
a52fde77 | 98 | |
0e9b2f07 GB |
99 | fConfig = conf; |
100 | fTreeEnd = conf.getTreeStart(); | |
101 | fNodeCount = 0; | |
aa353506 | 102 | fLatestBranch = Collections.synchronizedList(new ArrayList<>()); |
a52fde77 AM |
103 | |
104 | /* Prepare the IO object */ | |
0e9b2f07 | 105 | fTreeIO = new HT_IO(fConfig, true); |
a52fde77 AM |
106 | |
107 | /* Add the first node to the tree */ | |
bb7f92ce | 108 | LeafNode firstNode = initNewLeafNode(-1, conf.getTreeStart()); |
0e9b2f07 | 109 | fLatestBranch.add(firstNode); |
a52fde77 AM |
110 | } |
111 | ||
a52fde77 AM |
112 | /** |
113 | * "Reader" constructor : instantiate a SHTree from an existing tree file on | |
114 | * disk | |
3b7f5abe | 115 | * |
8d47cc34 | 116 | * @param existingStateFile |
a52fde77 | 117 | * Path/filename of the history-file we are to open |
a96cc6be AM |
118 | * @param expProviderVersion |
119 | * The expected version of the state provider | |
a52fde77 | 120 | * @throws IOException |
8d47cc34 | 121 | * If an error happens reading the file |
a52fde77 | 122 | */ |
3a081e85 | 123 | public HistoryTreeClassic(File existingStateFile, int expProviderVersion) throws IOException { |
a52fde77 AM |
124 | /* |
125 | * Open the file ourselves, get the tree header information we need, | |
126 | * then pass on the descriptor to the TreeIO object. | |
127 | */ | |
128 | int rootNodeSeqNb, res; | |
129 | int bs, maxc; | |
fb12b0c2 | 130 | long startTime; |
a52fde77 AM |
131 | |
132 | /* Java I/O mumbo jumbo... */ | |
fee997a5 AM |
133 | if (!existingStateFile.exists()) { |
134 | throw new IOException("Selected state file does not exist"); //$NON-NLS-1$ | |
135 | } | |
fb12b0c2 | 136 | if (existingStateFile.length() <= 0) { |
a96cc6be | 137 | throw new IOException("Empty target file"); //$NON-NLS-1$ |
a52fde77 AM |
138 | } |
139 | ||
a4524c1b AM |
140 | try (FileInputStream fis = new FileInputStream(existingStateFile); |
141 | FileChannel fc = fis.getChannel();) { | |
a52fde77 | 142 | |
a4524c1b | 143 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); |
a4524c1b AM |
144 | buffer.order(ByteOrder.LITTLE_ENDIAN); |
145 | buffer.clear(); | |
75409043 AM |
146 | |
147 | res = fc.read(buffer); | |
148 | if (res != TREE_HEADER_SIZE) { | |
149 | throw new IOException("Invalid header size"); //$NON-NLS-1$ | |
150 | } | |
151 | ||
a4524c1b | 152 | buffer.flip(); |
a52fde77 | 153 | |
a96cc6be | 154 | /* |
a4524c1b AM |
155 | * Check the magic number to make sure we're opening the right type |
156 | * of file | |
a96cc6be | 157 | */ |
a4524c1b AM |
158 | res = buffer.getInt(); |
159 | if (res != HISTORY_FILE_MAGIC_NUMBER) { | |
160 | throw new IOException("Wrong magic number"); //$NON-NLS-1$ | |
161 | } | |
162 | ||
163 | res = buffer.getInt(); /* File format version number */ | |
164 | if (res != FILE_VERSION) { | |
165 | throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$ | |
166 | } | |
167 | ||
168 | res = buffer.getInt(); /* Event handler's version number */ | |
169 | if (res != expProviderVersion && | |
bcec0116 | 170 | expProviderVersion != ITmfStateSystemBuilder.IGNORE_PROVIDER_VERSION) { |
a4524c1b AM |
171 | /* |
172 | * The existing history was built using an event handler that | |
173 | * doesn't match the current one in the framework. | |
174 | * | |
175 | * Information could be all wrong. Instead of keeping an | |
176 | * incorrect history file, a rebuild is done. | |
177 | */ | |
178 | throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$ | |
179 | } | |
180 | ||
181 | bs = buffer.getInt(); /* Block Size */ | |
182 | maxc = buffer.getInt(); /* Max nb of children per node */ | |
a52fde77 | 183 | |
0e9b2f07 | 184 | fNodeCount = buffer.getInt(); |
a4524c1b AM |
185 | rootNodeSeqNb = buffer.getInt(); |
186 | startTime = buffer.getLong(); | |
a52fde77 | 187 | |
0e9b2f07 | 188 | fConfig = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime); |
a4524c1b | 189 | } |
a52fde77 | 190 | |
a52fde77 AM |
191 | /* |
192 | * FIXME We close fis here and the TreeIO will then reopen the same | |
193 | * file, not extremely elegant. But how to pass the information here to | |
194 | * the SHT otherwise? | |
195 | */ | |
0e9b2f07 | 196 | fTreeIO = new HT_IO(fConfig, false); |
a52fde77 | 197 | |
0e9b2f07 GB |
198 | fLatestBranch = buildLatestBranch(rootNodeSeqNb); |
199 | fTreeEnd = getRootNode().getNodeEnd(); | |
fb12b0c2 AM |
200 | |
201 | /* | |
202 | * Make sure the history start time we read previously is consistent | |
203 | * with was is actually in the root node. | |
204 | */ | |
412a0225 | 205 | if (startTime != getRootNode().getNodeStart()) { |
fb12b0c2 AM |
206 | throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$ |
207 | "history file, it might be corrupted."); //$NON-NLS-1$ | |
208 | } | |
a52fde77 AM |
209 | } |
210 | ||
412a0225 AM |
211 | /** |
212 | * Rebuild the latestBranch "cache" object by reading the nodes from disk | |
213 | * (When we are opening an existing file on disk and want to append to it, | |
214 | * for example). | |
215 | * | |
216 | * @param rootNodeSeqNb | |
217 | * The sequence number of the root node, so we know where to | |
218 | * start | |
219 | * @throws ClosedChannelException | |
220 | */ | |
367e2932 | 221 | private @NonNull List<@NonNull HTNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { |
aa353506 | 222 | List<@NonNull HTNode> list = new ArrayList<>(); |
412a0225 | 223 | |
0e9b2f07 | 224 | HTNode nextChildNode = fTreeIO.readNode(rootNodeSeqNb); |
bb7f92ce | 225 | list.add(nextChildNode); |
412a0225 | 226 | |
bb7f92ce FW |
227 | /* Follow the last branch up to the leaf */ |
228 | while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) { | |
0e9b2f07 | 229 | nextChildNode = fTreeIO.readNode(((CoreNode) nextChildNode).getLatestChild()); |
bb7f92ce | 230 | list.add(nextChildNode); |
412a0225 AM |
231 | } |
232 | return Collections.synchronizedList(list); | |
233 | } | |
234 | ||
3a081e85 | 235 | @Override |
8d47cc34 | 236 | public void closeTree(long requestedEndTime) { |
412a0225 | 237 | /* This is an important operation, queries can wait */ |
0e9b2f07 | 238 | synchronized (fLatestBranch) { |
412a0225 AM |
239 | /* |
240 | * Work-around the "empty branches" that get created when the root | |
241 | * node becomes full. Overwrite the tree's end time with the | |
242 | * original wanted end-time, to ensure no queries are sent into | |
243 | * those empty nodes. | |
244 | * | |
245 | * This won't be needed once extended nodes are implemented. | |
246 | */ | |
0e9b2f07 | 247 | fTreeEnd = requestedEndTime; |
6a1074ce | 248 | |
412a0225 | 249 | /* Close off the latest branch of the tree */ |
0e9b2f07 GB |
250 | for (int i = 0; i < fLatestBranch.size(); i++) { |
251 | fLatestBranch.get(i).closeThisNode(fTreeEnd); | |
252 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
412a0225 | 253 | } |
a52fde77 | 254 | |
0e9b2f07 | 255 | try (FileChannel fc = fTreeIO.getFcOut();) { |
412a0225 AM |
256 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); |
257 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
258 | buffer.clear(); | |
a52fde77 | 259 | |
412a0225 AM |
260 | /* Save the config of the tree to the header of the file */ |
261 | fc.position(0); | |
a52fde77 | 262 | |
412a0225 | 263 | buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); |
a52fde77 | 264 | |
412a0225 | 265 | buffer.putInt(FILE_VERSION); |
0e9b2f07 | 266 | buffer.putInt(fConfig.getProviderVersion()); |
a52fde77 | 267 | |
0e9b2f07 GB |
268 | buffer.putInt(fConfig.getBlockSize()); |
269 | buffer.putInt(fConfig.getMaxChildren()); | |
a52fde77 | 270 | |
0e9b2f07 | 271 | buffer.putInt(fNodeCount); |
a52fde77 | 272 | |
412a0225 | 273 | /* root node seq. nb */ |
0e9b2f07 | 274 | buffer.putInt(fLatestBranch.get(0).getSequenceNumber()); |
a52fde77 | 275 | |
412a0225 | 276 | /* start time of this history */ |
0e9b2f07 | 277 | buffer.putLong(fLatestBranch.get(0).getNodeStart()); |
fb12b0c2 | 278 | |
412a0225 AM |
279 | buffer.flip(); |
280 | int res = fc.write(buffer); | |
281 | assert (res <= TREE_HEADER_SIZE); | |
282 | /* done writing the file header */ | |
a52fde77 | 283 | |
412a0225 AM |
284 | } catch (IOException e) { |
285 | /* | |
286 | * If we were able to write so far, there should not be any | |
287 | * problem at this point... | |
288 | */ | |
289 | throw new RuntimeException("State system write error"); //$NON-NLS-1$ | |
290 | } | |
a52fde77 | 291 | } |
a52fde77 AM |
292 | } |
293 | ||
dbdc452f AM |
294 | // ------------------------------------------------------------------------ |
295 | // Accessors | |
296 | // ------------------------------------------------------------------------ | |
ab604305 | 297 | |
3a081e85 | 298 | @Override |
8d47cc34 | 299 | public long getTreeStart() { |
0e9b2f07 | 300 | return fConfig.getTreeStart(); |
a52fde77 AM |
301 | } |
302 | ||
3a081e85 | 303 | @Override |
8d47cc34 | 304 | public long getTreeEnd() { |
0e9b2f07 | 305 | return fTreeEnd; |
a52fde77 AM |
306 | } |
307 | ||
3a081e85 | 308 | @Override |
8d47cc34 | 309 | public int getNodeCount() { |
0e9b2f07 | 310 | return fNodeCount; |
a52fde77 AM |
311 | } |
312 | ||
3a081e85 | 313 | @Override |
bb7f92ce | 314 | public HTNode getRootNode() { |
0e9b2f07 | 315 | return fLatestBranch.get(0); |
cb42195c AM |
316 | } |
317 | ||
f3476b68 GB |
318 | /** |
319 | * Return the latest branch of the tree. That branch is immutable. Used for | |
320 | * unit testing and debugging. | |
321 | * | |
322 | * @return The immutable latest branch | |
323 | */ | |
a10a38ae | 324 | @VisibleForTesting |
aa353506 | 325 | protected List<@NonNull HTNode> getLatestBranch() { |
f3476b68 GB |
326 | return ImmutableList.copyOf(fLatestBranch); |
327 | } | |
328 | ||
a10a38ae GB |
329 | /** |
330 | * Read a node at sequence number | |
331 | * | |
332 | * @param seqNum | |
333 | * The sequence number of the node to read | |
334 | * @return The HTNode object | |
335 | * @throws ClosedChannelException | |
336 | * Exception thrown when reading the node | |
337 | */ | |
338 | @VisibleForTesting | |
339 | protected @NonNull HTNode getNode(int seqNum) throws ClosedChannelException { | |
340 | // First, check in the latest branch if the node is there | |
341 | for (HTNode node : fLatestBranch) { | |
342 | if (node.getSequenceNumber() == seqNum) { | |
343 | return node; | |
344 | } | |
345 | } | |
346 | return fTreeIO.readNode(seqNum); | |
347 | } | |
348 | ||
0e4eaca8 AM |
349 | /** |
350 | * Retrieve the TreeIO object. Should only be used for testing. | |
351 | * | |
352 | * @return The TreeIO | |
353 | */ | |
354 | @VisibleForTesting | |
355 | protected @NonNull HT_IO getTreeIO() { | |
356 | return fTreeIO; | |
357 | } | |
358 | ||
360f899e EB |
359 | // ------------------------------------------------------------------------ |
360 | // HT_IO interface | |
361 | // ------------------------------------------------------------------------ | |
362 | ||
3a081e85 | 363 | @Override |
8d47cc34 | 364 | public FileInputStream supplyATReader() { |
0e9b2f07 | 365 | return fTreeIO.supplyATReader(getNodeCount()); |
360f899e EB |
366 | } |
367 | ||
3a081e85 | 368 | @Override |
8d47cc34 | 369 | public File supplyATWriterFile() { |
0e9b2f07 | 370 | return fConfig.getStateFile(); |
360f899e EB |
371 | } |
372 | ||
3a081e85 | 373 | @Override |
8d47cc34 | 374 | public long supplyATWriterFilePos() { |
3a081e85 | 375 | return IHistoryTree.TREE_HEADER_SIZE |
0e9b2f07 | 376 | + ((long) getNodeCount() * fConfig.getBlockSize()); |
360f899e EB |
377 | } |
378 | ||
3a081e85 | 379 | @Override |
8d47cc34 | 380 | public HTNode readNode(int seqNumber) throws ClosedChannelException { |
360f899e | 381 | /* Try to read the node from memory */ |
0e9b2f07 GB |
382 | synchronized (fLatestBranch) { |
383 | for (HTNode node : fLatestBranch) { | |
412a0225 AM |
384 | if (node.getSequenceNumber() == seqNumber) { |
385 | return node; | |
386 | } | |
360f899e EB |
387 | } |
388 | } | |
389 | ||
390 | /* Read the node from disk */ | |
0e9b2f07 | 391 | return fTreeIO.readNode(seqNumber); |
360f899e EB |
392 | } |
393 | ||
3a081e85 | 394 | @Override |
8d47cc34 | 395 | public void writeNode(HTNode node) { |
0e9b2f07 | 396 | fTreeIO.writeNode(node); |
360f899e EB |
397 | } |
398 | ||
3a081e85 | 399 | @Override |
8d47cc34 | 400 | public void closeFile() { |
0e9b2f07 | 401 | fTreeIO.closeFile(); |
360f899e EB |
402 | } |
403 | ||
3a081e85 | 404 | @Override |
8d47cc34 | 405 | public void deleteFile() { |
0e9b2f07 | 406 | fTreeIO.deleteFile(); |
360f899e EB |
407 | } |
408 | ||
dbdc452f AM |
409 | // ------------------------------------------------------------------------ |
410 | // Operations | |
411 | // ------------------------------------------------------------------------ | |
412 | ||
3a081e85 | 413 | @Override |
8d47cc34 | 414 | public void insertInterval(HTInterval interval) throws TimeRangeException { |
0e9b2f07 GB |
415 | if (interval.getStartTime() < fConfig.getTreeStart()) { |
416 | throw new TimeRangeException("Interval Start:" + interval.getStartTime() + ", Config Start:" + fConfig.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$ | |
a52fde77 | 417 | } |
0e9b2f07 | 418 | tryInsertAtNode(interval, fLatestBranch.size() - 1); |
a52fde77 AM |
419 | } |
420 | ||
421 | /** | |
422 | * Inner method to find in which node we should add the interval. | |
3b7f5abe | 423 | * |
a52fde77 AM |
424 | * @param interval |
425 | * The interval to add to the tree | |
426 | * @param indexOfNode | |
427 | * The index *in the latestBranch* where we are trying the | |
428 | * insertion | |
429 | */ | |
430 | private void tryInsertAtNode(HTInterval interval, int indexOfNode) { | |
0e9b2f07 | 431 | HTNode targetNode = fLatestBranch.get(indexOfNode); |
a52fde77 AM |
432 | |
433 | /* Verify if there is enough room in this node to store this interval */ | |
59d30d83 | 434 | if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) { |
a52fde77 AM |
435 | /* Nope, not enough room. Insert in a new sibling instead. */ |
436 | addSiblingNode(indexOfNode); | |
0e9b2f07 | 437 | tryInsertAtNode(interval, fLatestBranch.size() - 1); |
a52fde77 AM |
438 | return; |
439 | } | |
440 | ||
441 | /* Make sure the interval time range fits this node */ | |
442 | if (interval.getStartTime() < targetNode.getNodeStart()) { | |
443 | /* | |
444 | * No, this interval starts before the startTime of this node. We | |
445 | * need to check recursively in parents if it can fit. | |
446 | */ | |
a52fde77 AM |
447 | tryInsertAtNode(interval, indexOfNode - 1); |
448 | return; | |
449 | } | |
450 | ||
451 | /* | |
452 | * Ok, there is room, and the interval fits in this time slot. Let's add | |
453 | * it. | |
454 | */ | |
455 | targetNode.addInterval(interval); | |
456 | ||
457 | /* Update treeEnd if needed */ | |
0e9b2f07 GB |
458 | if (interval.getEndTime() > fTreeEnd) { |
459 | fTreeEnd = interval.getEndTime(); | |
a52fde77 | 460 | } |
a52fde77 AM |
461 | } |
462 | ||
463 | /** | |
464 | * Method to add a sibling to any node in the latest branch. This will add | |
465 | * children back down to the leaf level, if needed. | |
3b7f5abe | 466 | * |
a52fde77 AM |
467 | * @param indexOfNode |
468 | * The index in latestBranch where we start adding | |
469 | */ | |
470 | private void addSiblingNode(int indexOfNode) { | |
0e9b2f07 GB |
471 | synchronized (fLatestBranch) { |
472 | final long splitTime = fTreeEnd; | |
a52fde77 | 473 | |
0e9b2f07 | 474 | if (indexOfNode >= fLatestBranch.size()) { |
bb7f92ce FW |
475 | /* |
476 | * We need to make sure (indexOfNode - 1) doesn't get the last | |
477 | * node in the branch, because that one is a Leaf Node. | |
478 | */ | |
479 | throw new IllegalStateException(); | |
480 | } | |
a52fde77 | 481 | |
412a0225 AM |
482 | /* Check if we need to add a new root node */ |
483 | if (indexOfNode == 0) { | |
484 | addNewRootNode(); | |
485 | return; | |
486 | } | |
a52fde77 | 487 | |
412a0225 | 488 | /* Check if we can indeed add a child to the target parent */ |
0e9b2f07 | 489 | if (((CoreNode) fLatestBranch.get(indexOfNode - 1)).getNbChildren() == fConfig.getMaxChildren()) { |
412a0225 AM |
490 | /* If not, add a branch starting one level higher instead */ |
491 | addSiblingNode(indexOfNode - 1); | |
492 | return; | |
493 | } | |
a52fde77 | 494 | |
412a0225 | 495 | /* Split off the new branch from the old one */ |
0e9b2f07 GB |
496 | for (int i = indexOfNode; i < fLatestBranch.size(); i++) { |
497 | fLatestBranch.get(i).closeThisNode(splitTime); | |
498 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
a52fde77 | 499 | |
0e9b2f07 | 500 | CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); |
bb7f92ce FW |
501 | HTNode newNode; |
502 | ||
0e9b2f07 | 503 | switch (fLatestBranch.get(i).getNodeType()) { |
bb7f92ce FW |
504 | case CORE: |
505 | newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1); | |
506 | break; | |
507 | case LEAF: | |
508 | newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); | |
509 | break; | |
510 | default: | |
511 | throw new IllegalStateException(); | |
512 | } | |
a52fde77 | 513 | |
bb7f92ce | 514 | prevNode.linkNewChild(newNode); |
0e9b2f07 | 515 | fLatestBranch.set(i, newNode); |
412a0225 | 516 | } |
a52fde77 | 517 | } |
a52fde77 AM |
518 | } |
519 | ||
520 | /** | |
521 | * Similar to the previous method, except here we rebuild a completely new | |
522 | * latestBranch | |
523 | */ | |
524 | private void addNewRootNode() { | |
0e9b2f07 | 525 | final long splitTime = fTreeEnd; |
a52fde77 | 526 | |
0e9b2f07 GB |
527 | HTNode oldRootNode = fLatestBranch.get(0); |
528 | CoreNode newRootNode = initNewCoreNode(-1, fConfig.getTreeStart()); | |
a52fde77 AM |
529 | |
530 | /* Tell the old root node that it isn't root anymore */ | |
531 | oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); | |
532 | ||
533 | /* Close off the whole current latestBranch */ | |
412a0225 | 534 | |
0e9b2f07 GB |
535 | for (int i = 0; i < fLatestBranch.size(); i++) { |
536 | fLatestBranch.get(i).closeThisNode(splitTime); | |
537 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
a52fde77 AM |
538 | } |
539 | ||
540 | /* Link the new root to its first child (the previous root node) */ | |
541 | newRootNode.linkNewChild(oldRootNode); | |
542 | ||
543 | /* Rebuild a new latestBranch */ | |
0e9b2f07 GB |
544 | int depth = fLatestBranch.size(); |
545 | fLatestBranch.clear(); | |
546 | fLatestBranch.add(newRootNode); | |
bb7f92ce FW |
547 | |
548 | // Create new coreNode | |
7c247a0f | 549 | for (int i = 1; i < depth; i++) { |
0e9b2f07 | 550 | CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); |
b2ca67ca | 551 | CoreNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), |
a52fde77 AM |
552 | splitTime + 1); |
553 | prevNode.linkNewChild(newNode); | |
0e9b2f07 | 554 | fLatestBranch.add(newNode); |
a52fde77 | 555 | } |
bb7f92ce FW |
556 | |
557 | // Create the new leafNode | |
7c247a0f | 558 | CoreNode prevNode = (CoreNode) fLatestBranch.get(depth - 1); |
b2ca67ca | 559 | LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); |
bb7f92ce | 560 | prevNode.linkNewChild(newNode); |
0e9b2f07 | 561 | fLatestBranch.add(newNode); |
a52fde77 AM |
562 | } |
563 | ||
564 | /** | |
bb7f92ce | 565 | * Add a new empty core node to the tree. |
3b7f5abe | 566 | * |
a52fde77 AM |
567 | * @param parentSeqNumber |
568 | * Sequence number of this node's parent | |
569 | * @param startTime | |
570 | * Start time of the new node | |
571 | * @return The newly created node | |
572 | */ | |
aa353506 | 573 | private @NonNull CoreNode initNewCoreNode(int parentSeqNumber, long startTime) { |
0e9b2f07 | 574 | CoreNode newNode = new CoreNode(fConfig, fNodeCount, parentSeqNumber, |
a52fde77 | 575 | startTime); |
0e9b2f07 | 576 | fNodeCount++; |
a52fde77 AM |
577 | return newNode; |
578 | } | |
579 | ||
bb7f92ce FW |
580 | /** |
581 | * Add a new empty leaf node to the tree. | |
582 | * | |
583 | * @param parentSeqNumber | |
584 | * Sequence number of this node's parent | |
585 | * @param startTime | |
586 | * Start time of the new node | |
587 | * @return The newly created node | |
588 | */ | |
aa353506 | 589 | private @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) { |
0e9b2f07 | 590 | LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber, |
bb7f92ce | 591 | startTime); |
0e9b2f07 | 592 | fNodeCount++; |
bb7f92ce FW |
593 | return newNode; |
594 | } | |
595 | ||
3a081e85 | 596 | @Override |
588f11a1 | 597 | public Collection<HTNode> selectNextChildren(CoreNode currentNode, long t) throws ClosedChannelException { |
a52fde77 AM |
598 | assert (currentNode.getNbChildren() > 0); |
599 | int potentialNextSeqNb = currentNode.getSequenceNumber(); | |
600 | ||
601 | for (int i = 0; i < currentNode.getNbChildren(); i++) { | |
602 | if (t >= currentNode.getChildStart(i)) { | |
603 | potentialNextSeqNb = currentNode.getChild(i); | |
604 | } else { | |
605 | break; | |
606 | } | |
607 | } | |
d862bcb3 | 608 | |
a52fde77 AM |
609 | /* |
610 | * Once we exit this loop, we should have found a children to follow. If | |
611 | * we didn't, there's a problem. | |
612 | */ | |
822798a3 GB |
613 | if (potentialNextSeqNb == currentNode.getSequenceNumber()) { |
614 | throw new IllegalStateException("No next child node found"); //$NON-NLS-1$ | |
615 | } | |
a52fde77 AM |
616 | |
617 | /* | |
618 | * Since this code path is quite performance-critical, avoid iterating | |
619 | * through the whole latestBranch array if we know for sure the next | |
620 | * node has to be on disk | |
621 | */ | |
045badfe | 622 | if (currentNode.isOnDisk()) { |
588f11a1 | 623 | return Collections.singleton(fTreeIO.readNode(potentialNextSeqNb)); |
a52fde77 | 624 | } |
588f11a1 | 625 | return Collections.singleton(readNode(potentialNextSeqNb)); |
a52fde77 AM |
626 | } |
627 | ||
3a081e85 | 628 | @Override |
8d47cc34 | 629 | public long getFileSize() { |
0e9b2f07 | 630 | return fConfig.getStateFile().length(); |
a52fde77 AM |
631 | } |
632 | ||
3b7f5abe AM |
633 | // ------------------------------------------------------------------------ |
634 | // Test/debugging methods | |
635 | // ------------------------------------------------------------------------ | |
a52fde77 | 636 | |
a52fde77 AM |
637 | /* Only used for debugging, shouldn't be externalized */ |
638 | @SuppressWarnings("nls") | |
639 | @Override | |
640 | public String toString() { | |
641 | return "Information on the current tree:\n\n" + "Blocksize: " | |
0e9b2f07 GB |
642 | + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: " |
643 | + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount | |
644 | + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n" | |
645 | + "Size of the treefile: " + getFileSize() + "\n" | |
a52fde77 | 646 | + "Root node has sequence number: " |
0e9b2f07 | 647 | + fLatestBranch.get(0).getSequenceNumber() + "\n" |
a52fde77 | 648 | + "'Latest leaf' has sequence number: " |
0e9b2f07 | 649 | + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber(); |
a52fde77 AM |
650 | } |
651 | ||
a52fde77 | 652 | } |