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 = 5;
  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.getIntervalSize() > 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
 609         /* Update the treeEnd if needed */
 610         if (startTime >= fTreeEnd) {
 611             fTreeEnd = startTime + 1;
 612         }
 613         return newNode;
 614     }
 615
 616     /**
 617      * Add a new empty leaf node to the tree.
 618      *
 619      * @param parentSeqNumber
 620      *            Sequence number of this node's parent
 621      * @param startTime
 622      *            Start time of the new node
 623      * @return The newly created node
 624      */
 625     private @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) {
 626         LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber,
 627                 startTime);
 628         fNodeCount++;
 629
 630         /* Update the treeEnd if needed */
 631         if (startTime >= fTreeEnd) {
 632             fTreeEnd = startTime + 1;
 633         }
 634         return newNode;
 635     }
 636
 637     /**
 638      * Inner method to select the next child of the current node intersecting
 639      * the given timestamp. Useful for moving down the tree following one
 640      * branch.
 641      *
 642      * @param currentNode
 643      *            The node on which the request is made
 644      * @param t
 645      *            The timestamp to choose which child is the next one
 646      * @return The child node intersecting t
 647      * @throws ClosedChannelException
 648      *             If the file channel was closed while we were reading the tree
 649      */
 650     public HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException {
 651         assert (currentNode.getNbChildren() > 0);
 652         int potentialNextSeqNb = currentNode.getSequenceNumber();
 653
 654         for (int i = 0; i < currentNode.getNbChildren(); i++) {
 655             if (t >= currentNode.getChildStart(i)) {
 656                 potentialNextSeqNb = currentNode.getChild(i);
 657             } else {
 658                 break;
 659             }
 660         }
 661
 662         /*
 663          * Once we exit this loop, we should have found a children to follow. If
 664          * we didn't, there's a problem.
 665          */
 666         if (potentialNextSeqNb == currentNode.getSequenceNumber()) {
 667             throw new IllegalStateException("No next child node found"); //$NON-NLS-1$
 668         }
 669
 670         /*
 671          * Since this code path is quite performance-critical, avoid iterating
 672          * through the whole latestBranch array if we know for sure the next
 673          * node has to be on disk
 674          */
 675         if (currentNode.isOnDisk()) {
 676             return fTreeIO.readNode(potentialNextSeqNb);
 677         }
 678         return readNode(potentialNextSeqNb);
 679     }
 680
 681     /**
 682      * Get the current size of the history file.
 683      *
 684      * @return The history file size
 685      */
 686     public long getFileSize() {
 687         return fConfig.getStateFile().length();
 688     }
 689
 690     // ------------------------------------------------------------------------
 691     // Test/debugging methods
 692     // ------------------------------------------------------------------------
 693
 694     /**
 695      * Debugging method to make sure all intervals contained in the given node
 696      * have valid start and end times.
 697      *
 698      * @param zenode
 699      *            The node to check
 700      * @return True if everything is fine, false if there is at least one
 701      *         invalid timestamp (end time < start time, time outside of the
 702      *         range of the node, etc.)
 703      */
 704     @SuppressWarnings("nls")
 705     public boolean checkNodeIntegrity(HTNode zenode) {
 706         /* Only used for debugging, shouldn't be externalized */
 707         HTNode otherNode;
 708         CoreNode node;
 709         StringBuffer buf = new StringBuffer();
 710         boolean ret = true;
 711
 712         // FIXME /* Only testing Core Nodes for now */
 713         if (!(zenode instanceof CoreNode)) {
 714             return true;
 715         }
 716
 717         node = (CoreNode) zenode;
 718
 719         try {
 720             /*
 721              * Test that this node's start and end times match the start of the
 722              * first child and the end of the last child, respectively
 723              */
 724             if (node.getNbChildren() > 0) {
 725                 otherNode = fTreeIO.readNode(node.getChild(0));
 726                 if (node.getNodeStart() != otherNode.getNodeStart()) {
 727                     buf.append("Start time of node (" + node.getNodeStart() + ") "
 728                             + "does not match start time of first child " + "("
 729                             + otherNode.getNodeStart() + "), " + "node #"
 730                             + otherNode.getSequenceNumber() + ")\n");
 731                     ret = false;
 732                 }
 733                 if (node.isOnDisk()) {
 734                     otherNode = fTreeIO.readNode(node.getLatestChild());
 735                     if (node.getNodeEnd() != otherNode.getNodeEnd()) {
 736                         buf.append("End time of node (" + node.getNodeEnd()
 737                                 + ") does not match end time of last child ("
 738                                 + otherNode.getNodeEnd() + ", node #"
 739                                 + otherNode.getSequenceNumber() + ")\n");
 740                         ret = false;
 741                     }
 742                 }
 743             }
 744
 745             /*
 746              * Test that the childStartTimes[] array matches the real nodes'
 747              * start times
 748              */
 749             for (int i = 0; i < node.getNbChildren(); i++) {
 750                 otherNode = fTreeIO.readNode(node.getChild(i));
 751                 if (otherNode.getNodeStart() != node.getChildStart(i)) {
 752                     buf.append("  Expected start time of child node #"
 753                             + node.getChild(i) + ": " + node.getChildStart(i)
 754                             + "\n" + "  Actual start time of node #"
 755                             + otherNode.getSequenceNumber() + ": "
 756                             + otherNode.getNodeStart() + "\n");
 757                     ret = false;
 758                 }
 759             }
 760
 761         } catch (ClosedChannelException e) {
 762             Activator.getDefault().logError(e.getMessage(), e);
 763         }
 764
 765         if (!ret) {
 766             Activator.getDefault().logError("SHT: Integrity check failed for node #"
 767                     + node.getSequenceNumber() + ":" + buf.toString());
 768         }
 769         return ret;
 770     }
 771
 772     /**
 773      * Check the integrity of all the nodes in the tree. Calls
 774      * {@link #checkNodeIntegrity} for every node in the tree.
 775      */
 776     public void checkIntegrity() {
 777         try {
 778             for (int i = 0; i < fNodeCount; i++) {
 779                 checkNodeIntegrity(fTreeIO.readNode(i));
 780             }
 781         } catch (ClosedChannelException e) {
 782         }
 783     }
 784
 785     /* Only used for debugging, shouldn't be externalized */
 786     @SuppressWarnings("nls")
 787     @Override
 788     public String toString() {
 789         return "Information on the current tree:\n\n" + "Blocksize: "
 790                 + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: "
 791                 + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount
 792                 + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n"
 793                 + "Size of the treefile: " + getFileSize() + "\n"
 794                 + "Root node has sequence number: "
 795                 + fLatestBranch.get(0).getSequenceNumber() + "\n"
 796                 + "'Latest leaf' has sequence number: "
 797                 + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber();
 798     }
 799
 800     /**
 801      * Start at currentNode and print the contents of all its children, in
 802      * pre-order. Give the root node in parameter to visit the whole tree, and
 803      * have a nice overview.
 804      */
 805     /* Only used for debugging, shouldn't be externalized */
 806     @SuppressWarnings("nls")
 807     private void preOrderPrint(PrintWriter writer, boolean printIntervals,
 808             HTNode currentNode, int curDepth) {
 809
 810         writer.println(currentNode.toString());
 811         if (printIntervals) {
 812             currentNode.debugPrintIntervals(writer);
 813         }
 814
 815         switch (currentNode.getNodeType()) {
 816         case LEAF:
 817             /* Stop if it's the leaf node */
 818             return;
 819
 820         case CORE:
 821             try {
 822                 final CoreNode node = (CoreNode) currentNode;
 823                 /* Print the extensions, if any */
 824                 int extension = node.getExtensionSequenceNumber();
 825                 while (extension != -1) {
 826                     HTNode nextNode = fTreeIO.readNode(extension);
 827                     preOrderPrint(writer, printIntervals, nextNode, curDepth);
 828                 }
 829
 830                 /* Print the child nodes */
 831                 for (int i = 0; i < node.getNbChildren(); i++) {
 832                     HTNode nextNode = fTreeIO.readNode(node.getChild(i));
 833                     for (int j = 0; j < curDepth; j++) {
 834                         writer.print("  ");
 835                     }
 836                     writer.print("+-");
 837                     preOrderPrint(writer, printIntervals, nextNode, curDepth + 1);
 838                 }
 839             } catch (ClosedChannelException e) {
 840                 Activator.getDefault().logError(e.getMessage());
 841             }
 842             break;
 843
 844         default:
 845             break;
 846         }
 847     }
 848
 849     /**
 850      * Print out the full tree for debugging purposes
 851      *
 852      * @param writer
 853      *            PrintWriter in which to write the output
 854      * @param printIntervals
 855      *            Flag to enable full output of the interval information
 856      */
 857     public void debugPrintFullTree(PrintWriter writer, boolean printIntervals) {
 858         /* Only used for debugging, shouldn't be externalized */
 859
 860         preOrderPrint(writer, false, fLatestBranch.get(0), 0);
 861
 862         if (printIntervals) {
 863             writer.println("\nDetails of intervals:"); //$NON-NLS-1$
 864             preOrderPrint(writer, true, fLatestBranch.get(0), 0);
 865         }
 866         writer.println('\n');
 867     }
 868
 869 }