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