1 /*******************************************************************************
2 * Copyright (c) 2012, 2013 Ericsson
3 * Copyright (c) 2010, 2011 École Polytechnique de Montréal
4 * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
6 * All rights reserved. This program and the accompanying materials are
7 * made available under the terms of the Eclipse Public License v1.0 which
8 * accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
11 *******************************************************************************/
13 package org
.eclipse
.linuxtools
.internal
.tmf
.core
.statesystem
.backends
.historytree
;
15 import java
.io
.IOException
;
16 import java
.io
.PrintWriter
;
17 import java
.nio
.ByteBuffer
;
18 import java
.nio
.ByteOrder
;
19 import java
.nio
.channels
.FileChannel
;
20 import java
.util
.ArrayList
;
21 import java
.util
.Collections
;
22 import java
.util
.List
;
24 import org
.eclipse
.linuxtools
.tmf
.core
.exceptions
.TimeRangeException
;
25 import org
.eclipse
.linuxtools
.tmf
.core
.interval
.ITmfStateInterval
;
26 import org
.eclipse
.linuxtools
.tmf
.core
.statevalue
.TmfStateValue
;
29 * The base class for all the types of nodes that go in the History Tree.
34 abstract class HTNode
{
36 /* Reference to the History Tree to whom this node belongs */
37 protected final HistoryTree ownerTree
;
39 /* Time range of this node */
40 private final long nodeStart
;
43 /* Sequence number = position in the node section of the file */
44 private final int sequenceNumber
;
45 private int parentSequenceNumber
; /* = -1 if this node is the root node */
47 /* Where the Strings section begins (from the start of the node */
48 private int stringSectionOffset
;
50 /* True if this node is closed (and to be committed to disk) */
51 private boolean isDone
;
53 /* Vector containing all the intervals contained in this node */
54 private final ArrayList
<HTInterval
> intervals
;
56 HTNode(HistoryTree tree
, int seqNumber
, int parentSeqNumber
, long start
) {
57 this.ownerTree
= tree
;
58 this.nodeStart
= start
;
59 this.sequenceNumber
= seqNumber
;
60 this.parentSequenceNumber
= parentSeqNumber
;
62 this.stringSectionOffset
= ownerTree
.config
.blockSize
;
64 this.intervals
= new ArrayList
<HTInterval
>();
68 * Reader factory constructor. Build a Node object (of the right type) by
69 * reading a block in the file.
72 * Reference to the HT which will own this node
74 * FileChannel to the history file, ALREADY SEEKED at the start
78 final static HTNode
readNode(HistoryTree tree
, FileChannel fc
)
80 HTNode newNode
= null;
83 ByteBuffer buffer
= ByteBuffer
.allocate(tree
.config
.blockSize
);
84 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
86 res
= fc
.read(buffer
);
87 assert (res
== tree
.config
.blockSize
);
88 // This often breaks, so might as well keep this code not too far...
89 // if ( res != tree.config.blockSize ) {
90 // tree.debugPrintFullTree(new PrintWriter(System.out, true), null,
96 /* Read the common header part */
97 byte type
= buffer
.get();
98 long start
= buffer
.getLong();
99 long end
= buffer
.getLong();
100 int seqNb
= buffer
.getInt();
101 int parentSeqNb
= buffer
.getInt();
102 int intervalCount
= buffer
.getInt();
103 int stringSectionOffset
= buffer
.getInt();
104 boolean done
= byteToBool(buffer
.get());
106 /* Now the rest of the header depends on the node type */
110 newNode
= new CoreNode(tree
, seqNb
, parentSeqNb
, start
);
111 newNode
.readSpecificHeader(buffer
);
114 // TODO implement other node types
122 // /* "Claudette" (extended) nodes */
127 /* Unrecognized node type */
128 throw new IOException();
132 * At this point, we should be done reading the header and 'buffer'
133 * should only have the intervals left
135 for (i
= 0; i
< intervalCount
; i
++) {
136 newNode
.intervals
.add(HTInterval
.readFrom(buffer
));
139 /* Assign the node's other information we have read previously */
140 newNode
.nodeEnd
= end
;
141 newNode
.stringSectionOffset
= stringSectionOffset
;
142 newNode
.isDone
= done
;
147 final void writeSelf(FileChannel fc
) throws IOException
{
149 int curStringsEntryEndPos
= ownerTree
.config
.blockSize
;
151 ByteBuffer buffer
= ByteBuffer
.allocate(ownerTree
.config
.blockSize
);
152 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
155 /* Write the common header part */
156 buffer
.put(this.getNodeType());
157 buffer
.putLong(nodeStart
);
158 buffer
.putLong(nodeEnd
);
159 buffer
.putInt(sequenceNumber
);
160 buffer
.putInt(parentSequenceNumber
);
161 buffer
.putInt(intervals
.size());
162 buffer
.putInt(stringSectionOffset
);
163 buffer
.put(boolToByte(isDone
));
165 /* Now call the inner method to write the specific header part */
166 this.writeSpecificHeader(buffer
);
168 /* Back to us, we write the intervals */
169 for (HTInterval interval
: intervals
) {
170 size
= interval
.writeInterval(buffer
, curStringsEntryEndPos
);
171 curStringsEntryEndPos
-= size
;
175 * Write padding between the end of the Data section and the start of
176 * the Strings section (needed to fill the node in case there is no
179 while (buffer
.position() < stringSectionOffset
) {
180 buffer
.put((byte) 0);
184 * If the offsets were right, the size of the Strings section should be
185 * == to the expected size
187 assert (curStringsEntryEndPos
== stringSectionOffset
);
189 /* Finally, write everything in the Buffer to disk */
191 // if we don't do this, flip() will lose what's after.
192 buffer
.position(ownerTree
.config
.blockSize
);
195 res
= fc
.write(buffer
);
196 assert (res
== ownerTree
.config
.blockSize
);
202 long getNodeStart() {
213 int getSequenceNumber() {
214 return sequenceNumber
;
217 int getParentSequenceNumber() {
218 return parentSequenceNumber
;
222 * Change this node's parent. Used when we create a new root node for
225 void setParentSequenceNumber(int newParent
) {
226 parentSequenceNumber
= newParent
;
234 * Add an interval to this node
238 void addInterval(HTInterval newInterval
) {
239 /* Just in case, but should be checked before even calling this function */
240 assert (newInterval
.getIntervalSize() <= this.getNodeFreeSpace());
242 intervals
.add(newInterval
);
244 /* Update the in-node offset "pointer" */
245 stringSectionOffset
-= (newInterval
.getStringsEntrySize());
249 * We've received word from the containerTree that newest nodes now exist to
250 * our right. (Puts isDone = true and sets the endtime)
253 * The nodeEnd time that the node will have
254 * @throws TimeRangeException
256 void closeThisNode(long endtime
) {
257 assert (endtime
>= this.nodeStart
);
258 // /* This also breaks often too */
259 // if ( endtime.getValue() <= this.nodeStart.getValue() ) {
260 // ownerTree.debugPrintFullTree(new PrintWriter(System.out, true), null,
265 if (intervals
.size() > 0) {
267 * Sort the intervals by ascending order of their end time. This
268 * speeds up lookups a bit
270 Collections
.sort(intervals
);
273 * Make sure there are no intervals in this node with their EndTime
274 * > the one requested. Only need to check the last one since they
277 assert (endtime
>= intervals
.get(intervals
.size() - 1).getEndTime());
281 this.nodeEnd
= endtime
;
286 * The method to fill up the stateInfo (passed on from the Current State
287 * Tree when it does a query on the SHT). We'll replace the data in that
288 * vector with whatever relevant we can find from this node
291 * The same stateInfo that comes from SHT's doQuery()
293 * The timestamp for which the query is for. Only return
294 * intervals that intersect t.
295 * @throws TimeRangeException
297 void writeInfoFromNode(List
<ITmfStateInterval
> stateInfo
, long t
)
298 throws TimeRangeException
{
299 assert (this.isDone
); // not sure this will always be the case...
302 if (intervals
.size() == 0) {
305 startIndex
= getStartIndexFor(t
);
307 for (int i
= startIndex
; i
< intervals
.size(); i
++) {
309 * Now we only have to compare the Start times, since we now the End
310 * times necessarily fit
312 if (intervals
.get(i
).getStartTime() <= t
) {
313 stateInfo
.set(intervals
.get(i
).getAttribute(), intervals
.get(i
));
320 * Get a single Interval from the information in this node If the
321 * key/timestamp pair cannot be found, we return null.
325 * @return The Interval containing the information we want, or null if it
327 * @throws TimeRangeException
329 HTInterval
getRelevantInterval(int key
, long t
) throws TimeRangeException
{
330 assert (this.isDone
);
332 HTInterval curInterval
;
334 if (intervals
.size() == 0) {
338 startIndex
= getStartIndexFor(t
);
340 for (int i
= startIndex
; i
< intervals
.size(); i
++) {
341 curInterval
= intervals
.get(i
);
342 if (curInterval
.getAttribute() == key
343 && curInterval
.getStartTime() <= t
344 && curInterval
.getEndTime() >= t
) {
348 /* We didn't find the relevant information in this node */
352 private int getStartIndexFor(long t
) throws TimeRangeException
{
357 * Since the intervals are sorted by end time, we can skip all the ones
358 * at the beginning whose end times are smaller than 't'. Java does
359 * provides a .binarySearch method, but its API is quite weird...
361 dummy
= new HTInterval(0, t
, 0, TmfStateValue
.nullValue());
362 index
= Collections
.binarySearch(intervals
, dummy
);
366 * .binarySearch returns a negative number if the exact value was
367 * not found. Here we just want to know where to start searching, we
368 * don't care if the value is exact or not.
374 /* Sometimes binarySearch yields weird stuff... */
378 if (index
>= intervals
.size()) {
379 index
= intervals
.size() - 1;
383 * Another API quirkiness, the returned index is the one of the *last*
384 * element of a series of equal endtimes, which happens sometimes. We
385 * want the *first* element of such a series, to read through them
389 && intervals
.get(index
- 1).compareTo(intervals
.get(index
)) == 0) {
392 // FIXME F*ck all this, just do our own binary search in a saner way...
394 // //checks to make sure startIndex works how I think it does
395 // if ( startIndex > 0 ) { assert ( intervals.get(startIndex-1).getEnd()
397 // assert ( intervals.get(startIndex).getEnd() >= t );
398 // if ( startIndex < intervals.size()-1 ) { assert (
399 // intervals.get(startIndex+1).getEnd() >= t ); }
405 * @return The offset, within the node, where the Data section ends
407 private int getDataSectionEndOffset() {
408 return this.getTotalHeaderSize() + HTNode
.getDataEntrySize()
413 * Returns the free space in the node, which is simply put, the
414 * stringSectionOffset - dataSectionOffset
416 int getNodeFreeSpace() {
417 return stringSectionOffset
- this.getDataSectionEndOffset();
421 * Returns the current space utilisation of this node, as a percentage.
422 * (used space / total usable space, which excludes the header)
424 long getNodeUsagePRC() {
425 float freePercent
= (float) this.getNodeFreeSpace()
426 / (float) (ownerTree
.config
.blockSize
- this.getTotalHeaderSize())
428 return (long) (100L - freePercent
);
431 protected final static int getDataEntrySize() {
432 return 16 /* 2 x Timevalue/long (interval start + end) */
434 + 1 /* byte (type) */
435 + 4; /* int (valueOffset) */
439 protected final static byte boolToByte(boolean thebool
) {
446 final static boolean byteToBool(byte thebyte
) {
447 return (thebyte
== (byte) 1);
451 * @name Debugging functions
454 @SuppressWarnings("nls")
456 public String
toString() {
457 /* Only used for debugging, shouldn't be externalized */
458 StringBuffer buf
= new StringBuffer("Node #" + sequenceNumber
+ ", ");
459 buf
.append(this.toStringSpecific());
460 buf
.append(intervals
.size() + " intervals (" + this.getNodeUsagePRC()
463 buf
.append("[" + this.nodeStart
+ " - ");
465 buf
= buf
.append("" + this.nodeEnd
+ "]");
467 buf
= buf
.append("...]");
469 return buf
.toString();
473 * Debugging function that prints out the contents of this node
476 * PrintWriter in which we will print the debug output
478 @SuppressWarnings("nls")
479 void debugPrintIntervals(PrintWriter writer
) {
480 /* Only used for debugging, shouldn't be externalized */
481 writer
.println("Node #" + sequenceNumber
+ ":");
483 /* Array of children */
484 if (this.getNodeType() == 1) { /* Only Core Nodes can have children */
485 CoreNode thisNode
= (CoreNode
) this;
486 writer
.print(" " + thisNode
.getNbChildren() + " children");
487 if (thisNode
.getNbChildren() >= 1) {
488 writer
.print(": [ " + thisNode
.getChild(0));
489 for (int i
= 1; i
< thisNode
.getNbChildren(); i
++) {
490 writer
.print(", " + thisNode
.getChild(i
));
497 /* List of intervals in the node */
498 writer
.println(" Intervals contained:");
499 for (int i
= 0; i
< intervals
.size(); i
++) {
500 writer
.println(intervals
.get(i
).toString());
502 writer
.println('\n');
505 final static int getCommonHeaderSize() {
509 * 16 - 2x long (start time, end time)
511 * 16 - 4x int (seq number, parent seq number, intervalcount, strings
514 * 1 - byte (done or not)
519 // ------------------------------------------------------------------------
521 // ------------------------------------------------------------------------
523 protected abstract byte getNodeType();
525 protected abstract int getTotalHeaderSize();
527 protected abstract void readSpecificHeader(ByteBuffer buffer
);
529 protected abstract void writeSpecificHeader(ByteBuffer buffer
);
531 protected abstract String
toStringSpecific();
This page took 0.043502 seconds and 6 git commands to generate.