/*******************************************************************************
- * Copyright (c) 2012 Ericsson
+ * Copyright (c) 2012, 2013 Ericsson
* Copyright (c) 2010, 2011 École Polytechnique de Montréal
* Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
*
import java.nio.ByteOrder;
import java.nio.channels.ClosedChannelException;
import java.nio.channels.FileChannel;
-import java.util.Vector;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
import org.eclipse.linuxtools.tmf.core.exceptions.TimeRangeException;
+import org.eclipse.linuxtools.tmf.core.statesystem.ITmfStateProvider;
/**
* Meta-container for the History Tree. This structure contains all the
* high-level data relevant to the tree.
*
- * @author alexmont
+ * @author Alexandre Montplaisir
*
*/
class HistoryTree {
+ /**
+ * Size of the "tree header" in the tree-file The nodes will use this offset
+ * to know where they should be in the file. This should always be a
+ * multiple of 4K.
+ */
+ public static final int TREE_HEADER_SIZE = 4096;
+
private static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900;
- /*
- * File format version. Increment minor on backwards-compatible changes.
- * Increment major + set minor back to 0 when breaking compatibility.
- */
- private static final int MAJOR_VERSION = 3;
- private static final byte MINOR_VERSION = 0;
+ /** File format version. Increment when breaking compatibility. */
+ private static final int FILE_VERSION = 3;
// ------------------------------------------------------------------------
// Tree-specific configuration
// ------------------------------------------------------------------------
/** Container for all the configuration constants */
- protected final HTConfig config;
+ private final HTConfig config;
/** Reader/writer object */
private final HT_IO treeIO;
// ------------------------------------------------------------------------
- // Variable Fields (will change throughout the existance of the SHT)
+ // Variable Fields (will change throughout the existence of the SHT)
// ------------------------------------------------------------------------
/** Latest timestamp found in the tree (at any given moment) */
private long treeEnd;
- /** How many nodes exist in this tree, total */
+ /** The total number of nodes that exists in this tree */
private int nodeCount;
/** "Cache" to keep the active nodes in memory */
- protected Vector<CoreNode> latestBranch;
+ private List<CoreNode> latestBranch;
// ------------------------------------------------------------------------
// Constructors/"Destructors"
* Simple check to make sure we have enough place in the 0th block
* for the tree configuration
*/
- if (conf.blockSize < getTreeHeaderSize()) {
+ if (conf.getBlockSize() < TREE_HEADER_SIZE) {
throw new IllegalArgumentException();
}
config = conf;
- treeEnd = conf.treeStart;
+ treeEnd = conf.getTreeStart();
nodeCount = 0;
- latestBranch = new Vector<CoreNode>();
+ latestBranch = new ArrayList<CoreNode>();
/* Prepare the IO object */
- treeIO = new HT_IO(this, true);
+ treeIO = new HT_IO(config, true);
/* Add the first node to the tree */
- CoreNode firstNode = initNewCoreNode(-1, conf.treeStart);
+ CoreNode firstNode = initNewCoreNode(-1, conf.getTreeStart());
latestBranch.add(firstNode);
}
*
* @param existingFileName
* Path/filename of the history-file we are to open
+ * @param expProviderVersion
+ * The expected version of the state provider
* @throws IOException
*/
- HistoryTree(File existingStateFile) throws IOException {
+ HistoryTree(File existingStateFile, int expProviderVersion) throws IOException {
/*
* Open the file ourselves, get the tree header information we need,
* then pass on the descriptor to the TreeIO object.
throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
}
if (existingStateFile.length() <= 0) {
- throw new IOException("Invalid state file selected, " + //$NON-NLS-1$
- "target file is empty"); //$NON-NLS-1$
+ throw new IOException("Empty target file"); //$NON-NLS-1$
}
FileInputStream fis = new FileInputStream(existingStateFile);
- ByteBuffer buffer = ByteBuffer.allocate(getTreeHeaderSize());
+ ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE);
FileChannel fc = fis.getChannel();
buffer.order(ByteOrder.LITTLE_ENDIAN);
buffer.clear();
buffer.flip();
/*
- * Check the magic number,to make sure we're opening the right type of
+ * Check the magic number to make sure we're opening the right type of
* file
*/
res = buffer.getInt();
if (res != HISTORY_FILE_MAGIC_NUMBER) {
fc.close();
fis.close();
- throw new IOException("Selected file does not" + //$NON-NLS-1$
- "look like a History Tree file"); //$NON-NLS-1$
+ throw new IOException("Wrong magic number"); //$NON-NLS-1$
}
- res = buffer.getInt(); /* Major version number */
- if (res != MAJOR_VERSION) {
+ res = buffer.getInt(); /* File format version number */
+ if (res != FILE_VERSION) {
fc.close();
fis.close();
- throw new IOException("Select History Tree file is of an older " //$NON-NLS-1$
- + "format. Please use a previous version of " //$NON-NLS-1$
- + "the parser to open it."); //$NON-NLS-1$
+ throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$
}
- res = buffer.getInt(); /* Minor version number */
+ res = buffer.getInt(); /* Event handler's version number */
+ if (res != expProviderVersion &&
+ expProviderVersion != ITmfStateProvider.IGNORE_PROVIDER_VERSION) {
+ /*
+ * The existing history was built using an event handler that doesn't
+ * match the current one in the framework.
+ *
+ * Information could be all wrong. Instead of keeping an incorrect
+ * history file, a rebuild is done.
+ */
+ fc.close();
+ fis.close();
+ throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$
+ }
bs = buffer.getInt(); /* Block Size */
maxc = buffer.getInt(); /* Max nb of children per node */
rootNodeSeqNb = buffer.getInt();
startTime = buffer.getLong();
- this.config = new HTConfig(existingStateFile, bs, maxc, startTime);
+ this.config = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime);
fc.close();
fis.close();
/*
* file, not extremely elegant. But how to pass the information here to
* the SHT otherwise?
*/
- this.treeIO = new HT_IO(this, false);
+ this.treeIO = new HT_IO(config, false);
rebuildLatestBranch(rootNodeSeqNb);
- this.treeEnd = latestBranch.firstElement().getNodeEnd();
+ this.treeEnd = latestBranch.get(0).getNodeEnd();
/*
* Make sure the history start time we read previously is consistent
* with was is actually in the root node.
*/
- if (startTime != latestBranch.firstElement().getNodeStart()) {
+ if (startTime != latestBranch.get(0).getNodeStart()) {
fc.close();
fis.close();
throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
* file.
*
* @param requestedEndTime
+ * The greatest timestamp present in the history tree
*/
void closeTree(long requestedEndTime) {
FileChannel fc;
treeIO.writeNode(latestBranch.get(i));
}
- /* Only use this for debugging purposes, it's VERY slow! */
- // this.checkIntegrity();
-
fc = treeIO.getFcOut();
- buffer = ByteBuffer.allocate(getTreeHeaderSize());
+ buffer = ByteBuffer.allocate(TREE_HEADER_SIZE);
buffer.order(ByteOrder.LITTLE_ENDIAN);
buffer.clear();
buffer.putInt(HISTORY_FILE_MAGIC_NUMBER);
- buffer.putInt(MAJOR_VERSION);
- buffer.putInt(MINOR_VERSION);
+ buffer.putInt(FILE_VERSION);
+ buffer.putInt(config.getProviderVersion());
- buffer.putInt(config.blockSize);
- buffer.putInt(config.maxChildren);
+ buffer.putInt(config.getBlockSize());
+ buffer.putInt(config.getMaxChildren());
buffer.putInt(nodeCount);
/* root node seq. nb */
- buffer.putInt(latestBranch.firstElement().getSequenceNumber());
+ buffer.putInt(latestBranch.get(0).getSequenceNumber());
/* start time of this history */
- buffer.putLong(latestBranch.firstElement().getNodeStart());
+ buffer.putLong(latestBranch.get(0).getNodeStart());
buffer.flip();
res = fc.write(buffer);
- assert (res <= getTreeHeaderSize());
+ assert (res <= TREE_HEADER_SIZE);
/* done writing the file header */
} catch (IOException e) {
/* We should not have any problems at this point... */
- e.printStackTrace();
} finally {
try {
fc.close();
} catch (IOException e) {
- e.printStackTrace();
}
}
return;
// Accessors
// ------------------------------------------------------------------------
+ HTConfig getConfig() {
+ return config;
+ }
+
long getTreeStart() {
- return config.treeStart;
+ return config.getTreeStart();
}
long getTreeEnd() {
return nodeCount;
}
- HT_IO getTreeIO() {
- return treeIO;
+ List<CoreNode> getLatestBranch() {
+ return Collections.unmodifiableList(latestBranch);
+ }
+
+ // ------------------------------------------------------------------------
+ // HT_IO interface
+ // ------------------------------------------------------------------------
+
+ File supplyATWriterFile() {
+ return config.getStateFile();
+ }
+
+ FileInputStream supplyATReader() {
+ return treeIO.supplyATReader(getNodeCount());
+ }
+
+ long supplyATWriterFilePos() {
+ return HistoryTree.TREE_HEADER_SIZE
+ + ((long) getNodeCount() * config.getBlockSize());
+ }
+
+ HTNode readNode(int seqNumber) throws ClosedChannelException {
+ /* Try to read the node from memory */
+ for (HTNode node : getLatestBranch()) {
+ if (node.getSequenceNumber() == seqNumber) {
+ return node;
+ }
+ }
+
+ /* Read the node from disk */
+ return treeIO.readNode(seqNumber);
+ }
+
+ void writeNode(HTNode node) {
+ treeIO.writeNode(node);
+ }
+
+ void closeFile() {
+ treeIO.closeFile();
+ }
+
+ void deleteFile() {
+ treeIO.deleteFile();
}
// ------------------------------------------------------------------------
private void rebuildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException {
HTNode nextChildNode;
- this.latestBranch = new Vector<CoreNode>();
+ this.latestBranch = new ArrayList<CoreNode>();
- nextChildNode = treeIO.readNodeFromDisk(rootNodeSeqNb);
+ nextChildNode = treeIO.readNode(rootNodeSeqNb);
latestBranch.add((CoreNode) nextChildNode);
- while (latestBranch.lastElement().getNbChildren() > 0) {
- nextChildNode = treeIO.readNodeFromDisk(latestBranch.lastElement().getLatestChild());
+ while (latestBranch.get(latestBranch.size() - 1).getNbChildren() > 0) {
+ nextChildNode = treeIO.readNode(latestBranch.get(latestBranch.size() - 1).getLatestChild());
latestBranch.add((CoreNode) nextChildNode);
}
}
* Insert an interval in the tree
*
* @param interval
+ * The interval to be inserted
*/
void insertInterval(HTInterval interval) throws TimeRangeException {
- if (interval.getStartTime() < config.treeStart) {
+ if (interval.getStartTime() < config.getTreeStart()) {
throw new TimeRangeException();
}
tryInsertAtNode(interval, latestBranch.size() - 1);
if (interval.getEndTime() > this.treeEnd) {
this.treeEnd = interval.getEndTime();
}
- return;
}
/**
}
/* Check if we can indeed add a child to the target parent */
- if (latestBranch.get(indexOfNode - 1).getNbChildren() == config.maxChildren) {
+ if (latestBranch.get(indexOfNode - 1).getNbChildren() == config.getMaxChildren()) {
/* If not, add a branch starting one level higher instead */
addSiblingNode(indexOfNode - 1);
return;
latestBranch.set(i, newNode);
}
- return;
}
/**
CoreNode oldRootNode, newRootNode, newNode, prevNode;
long splitTime = this.treeEnd;
- oldRootNode = latestBranch.firstElement();
- newRootNode = initNewCoreNode(-1, config.treeStart);
+ oldRootNode = latestBranch.get(0);
+ newRootNode = initNewCoreNode(-1, config.getTreeStart());
/* Tell the old root node that it isn't root anymore */
oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber());
/* Rebuild a new latestBranch */
depth = latestBranch.size();
- latestBranch = new Vector<CoreNode>();
+ latestBranch = new ArrayList<CoreNode>();
latestBranch.add(newRootNode);
for (i = 1; i < depth + 1; i++) {
prevNode = latestBranch.get(i - 1);
* @return The newly created node
*/
private CoreNode initNewCoreNode(int parentSeqNumber, long startTime) {
- CoreNode newNode = new CoreNode(this, this.nodeCount, parentSeqNumber,
+ CoreNode newNode = new CoreNode(config, this.nodeCount, parentSeqNumber,
startTime);
this.nodeCount++;
* branch.
*
* @param currentNode
+ * The node on which the request is made
* @param t
+ * The timestamp to choose which child is the next one
* @return The child node intersecting t
* @throws ClosedChannelException
* If the file channel was closed while we were reading the tree
break;
}
}
+
/*
* Once we exit this loop, we should have found a children to follow. If
* we didn't, there's a problem.
* node has to be on disk
*/
if (currentNode.isDone()) {
- return treeIO.readNodeFromDisk(potentialNextSeqNb);
+ return treeIO.readNode(potentialNextSeqNb);
}
return treeIO.readNode(potentialNextSeqNb);
}
- /**
- * Helper function to get the size of the "tree header" in the tree-file The
- * nodes will use this offset to know where they should be in the file. This
- * should always be a multiple of 4K.
- */
- static int getTreeHeaderSize() {
- return 4096;
- }
-
long getFileSize() {
- return config.stateFile.length();
+ return config.getStateFile().length();
}
// ------------------------------------------------------------------------
checkNodeIntegrity(treeIO.readNode(i));
}
} catch (ClosedChannelException e) {
- e.printStackTrace();
}
}
@Override
public String toString() {
return "Information on the current tree:\n\n" + "Blocksize: "
- + config.blockSize + "\n" + "Max nb. of children per node: "
- + config.maxChildren + "\n" + "Number of nodes: " + nodeCount
+ + config.getBlockSize() + "\n" + "Max nb. of children per node: "
+ + config.getMaxChildren() + "\n" + "Number of nodes: " + nodeCount
+ "\n" + "Depth of the tree: " + latestBranch.size() + "\n"
+ "Size of the treefile: " + this.getFileSize() + "\n"
+ "Root node has sequence number: "
- + latestBranch.firstElement().getSequenceNumber() + "\n"
+ + latestBranch.get(0).getSequenceNumber() + "\n"
+ "'Latest leaf' has sequence number: "
- + latestBranch.lastElement().getSequenceNumber();
+ + latestBranch.get(latestBranch.size() - 1).getSequenceNumber();
}
- private int curDepth;
-
/**
* Start at currentNode and print the contents of all its children, in
* pre-order. Give the root node in parameter to visit the whole tree, and
* have a nice overview.
*/
+ /* Only used for debugging, shouldn't be externalized */
@SuppressWarnings("nls")
private void preOrderPrint(PrintWriter writer, boolean printIntervals,
- CoreNode currentNode) {
- /* Only used for debugging, shouldn't be externalized */
- int i, j;
- HTNode nextNode;
+ CoreNode currentNode, int curDepth) {
writer.println(currentNode.toString());
if (printIntervals) {
currentNode.debugPrintIntervals(writer);
}
- curDepth++;
try {
- for (i = 0; i < currentNode.getNbChildren(); i++) {
- nextNode = treeIO.readNode(currentNode.getChild(i));
+ for (int i = 0; i < currentNode.getNbChildren(); i++) {
+ HTNode nextNode = treeIO.readNode(currentNode.getChild(i));
assert (nextNode instanceof CoreNode); // TODO temporary
- for (j = 0; j < curDepth - 1; j++) {
+ for (int j = 0; j < curDepth; j++) {
writer.print(" ");
}
writer.print("+-");
- preOrderPrint(writer, printIntervals, (CoreNode) nextNode);
+ preOrderPrint(writer, printIntervals, (CoreNode) nextNode,
+ curDepth + 1);
}
} catch (ClosedChannelException e) {
e.printStackTrace();
}
- curDepth--;
- return;
}
/**
* @param writer
* PrintWriter in which to write the output
* @param printIntervals
- * Says if you want to output the full interval information
+ * Flag to enable full output of the interval information
*/
void debugPrintFullTree(PrintWriter writer, boolean printIntervals) {
/* Only used for debugging, shouldn't be externalized */
- curDepth = 0;
- this.preOrderPrint(writer, false, latestBranch.firstElement());
+
+ this.preOrderPrint(writer, false, latestBranch.get(0), 0);
if (printIntervals) {
writer.println("\nDetails of intervals:"); //$NON-NLS-1$
- curDepth = 0;
- this.preOrderPrint(writer, true, latestBranch.firstElement());
+ this.preOrderPrint(writer, true, latestBranch.get(0), 0);
}
writer.println('\n');
}