1 /*******************************************************************************
2 * Copyright (c) 2012 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
.tmf
.core
.statesystem
.backend
.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
.interval
.ITmfStateInterval
;
25 import org
.eclipse
.linuxtools
.tmf
.core
.statesystem
.TimeRangeException
;
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
);
333 if (intervals
.size() == 0) {
337 startIndex
= getStartIndexFor(t
);
339 for (int i
= startIndex
; i
< intervals
.size(); i
++) {
340 if (intervals
.get(i
).getAttribute() == key
) {
341 if (intervals
.get(i
).getStartTime() <= t
) {
342 return intervals
.get(i
);
346 /* We didn't find the relevant information in this node */
350 private int getStartIndexFor(long t
) throws TimeRangeException
{
355 * Since the intervals are sorted by end time, we can skip all the ones
356 * at the beginning whose end times are smaller than 't'. Java does
357 * provides a .binarySearch method, but its API is quite weird...
359 dummy
= new HTInterval(0, t
, 0, TmfStateValue
.nullValue());
360 index
= Collections
.binarySearch(intervals
, dummy
);
364 * .binarySearch returns a negative number if the exact value was
365 * not found. Here we just want to know where to start searching, we
366 * don't care if the value is exact or not.
372 /* Sometimes binarySearch yields weird stuff... */
376 if (index
>= intervals
.size()) {
377 index
= intervals
.size() - 1;
381 * Another API quirkiness, the returned index is the one of the *last*
382 * element of a series of equal endtimes, which happens sometimes. We
383 * want the *first* element of such a series, to read through them
387 && intervals
.get(index
- 1).compareTo(intervals
.get(index
)) == 0) {
390 // FIXME F*ck all this, just do our own binary search in a saner way...
392 // //checks to make sure startIndex works how I think it does
393 // if ( startIndex > 0 ) { assert ( intervals.get(startIndex-1).getEnd()
395 // assert ( intervals.get(startIndex).getEnd() >= t );
396 // if ( startIndex < intervals.size()-1 ) { assert (
397 // intervals.get(startIndex+1).getEnd() >= t ); }
403 * @return The offset, within the node, where the Data section ends
405 private int getDataSectionEndOffset() {
406 return this.getTotalHeaderSize() + HTNode
.getDataEntrySize()
411 * Returns the free space in the node, which is simply put, the
412 * stringSectionOffset - dataSectionOffset
414 int getNodeFreeSpace() {
415 return stringSectionOffset
- this.getDataSectionEndOffset();
419 * Returns the current space utilisation of this node, as a percentage.
420 * (used space / total usable space, which excludes the header)
422 long getNodeUsagePRC() {
423 float freePercent
= (float) this.getNodeFreeSpace()
424 / (float) (ownerTree
.config
.blockSize
- this.getTotalHeaderSize())
426 return (long) (100L - freePercent
);
429 protected final static int getDataEntrySize() {
430 return 16 /* 2 x Timevalue/long (interval start + end) */
432 + 1 /* byte (type) */
433 + 4; /* int (valueOffset) */
437 protected final static byte boolToByte(boolean thebool
) {
444 final static boolean byteToBool(byte thebyte
) {
445 return (thebyte
== (byte) 1);
449 * @name Debugging functions
452 @SuppressWarnings("nls")
454 public String
toString() {
455 /* Only used for debugging, shouldn't be externalized */
456 StringBuffer buf
= new StringBuffer("Node #" + sequenceNumber
+ ", ");
457 buf
.append(this.toStringSpecific());
458 buf
.append(intervals
.size() + " intervals (" + this.getNodeUsagePRC()
461 buf
.append("[" + this.nodeStart
+ " - ");
463 buf
= buf
.append("" + this.nodeEnd
+ "]");
465 buf
= buf
.append("...]");
467 return buf
.toString();
471 * Debugging function that prints out the contents of this node
474 * PrintWriter in which we will print the debug output
476 @SuppressWarnings("nls")
477 void debugPrintIntervals(PrintWriter writer
) {
478 /* Only used for debugging, shouldn't be externalized */
479 writer
.println("Node #" + sequenceNumber
+ ":");
481 /* Array of children */
482 if (this.getNodeType() == 1) { /* Only Core Nodes can have children */
483 CoreNode thisNode
= (CoreNode
) this;
484 writer
.print(" " + thisNode
.getNbChildren() + " children");
485 if (thisNode
.getNbChildren() >= 1) {
486 writer
.print(": [ " + thisNode
.getChild(0));
487 for (int i
= 1; i
< thisNode
.getNbChildren(); i
++) {
488 writer
.print(", " + thisNode
.getChild(i
));
495 /* List of intervals in the node */
496 writer
.println(" Intervals contained:");
497 for (int i
= 0; i
< intervals
.size(); i
++) {
498 writer
.println(intervals
.get(i
).toString());
500 writer
.println('\n');
503 final static int getCommonHeaderSize() {
507 * 16 - 2x long (start time, end time)
509 * 16 - 4x int (seq number, parent seq number, intervalcount, strings
512 * 1 - byte (done or not)
518 * @name Abstract methods
521 protected abstract byte getNodeType();
523 protected abstract int getTotalHeaderSize();
525 protected abstract void readSpecificHeader(ByteBuffer buffer
);
527 protected abstract void writeSpecificHeader(ByteBuffer buffer
);
529 protected abstract String
toStringSpecific();
This page took 0.043066 seconds and 5 git commands to generate.