statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java

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