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.IStateChangeInput;
+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 when breaking compatibility. */
// ------------------------------------------------------------------------
/** 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);
}
}
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();
res = buffer.getInt(); /* Event handler's version number */
if (res != expProviderVersion &&
- expProviderVersion != IStateChangeInput.IGNORE_PROVIDER_VERSION) {
+ expProviderVersion != ITmfStateProvider.IGNORE_PROVIDER_VERSION) {
/*
- * The existing history was built using a event handler that doesn't
- * match the current one in the framework. Information could be all
- * wrong, so we'll force a rebuild of the history file instead.
+ * 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();
* 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(FILE_VERSION);
- buffer.putInt(config.providerVersion);
+ 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');
}