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