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

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