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.
31 * @author Alexandre Montplaisir
33 public abstract class HTNode
{
36 * Size of an entry in the data section.
38 * 16 2 x Timevalue/long (interval start + end)
41 * + 4 int (valueOffset)
43 protected static final int DATA_ENTRY_SIZE
= 25;
45 /* Configuration of the History Tree to which belongs this node */
46 private final HTConfig config
;
48 /* Time range of this node */
49 private final long nodeStart
;
52 /* Sequence number = position in the node section of the file */
53 private final int sequenceNumber
;
54 private int parentSequenceNumber
; /* = -1 if this node is the root node */
56 /* Where the Strings section begins (from the start of the node */
57 private int stringSectionOffset
;
59 /* True if this node is closed (and to be committed to disk) */
60 private boolean isDone
;
62 /* Vector containing all the intervals contained in this node */
63 private final List
<HTInterval
> intervals
;
69 * Configuration of the History Tree
71 * The (unique) sequence number assigned to this particular node
72 * @param parentSeqNumber
73 * The sequence number of this node's parent node
75 * The earliest timestamp stored in this node
77 protected HTNode(HTConfig config
, int seqNumber
, int parentSeqNumber
, long start
) {
79 this.nodeStart
= start
;
80 this.sequenceNumber
= seqNumber
;
81 this.parentSequenceNumber
= parentSeqNumber
;
83 this.stringSectionOffset
= config
.getBlockSize();
85 this.intervals
= new ArrayList
<>();
89 * Reader factory method. Build a Node object (of the right type) by reading
90 * a block in the file.
93 * Configuration of the History Tree
95 * FileChannel to the history file, ALREADY SEEKED at the start
97 * @return The node object
99 * If there was an error reading from the file channel
101 public static final HTNode
readNode(HTConfig config
, FileChannel fc
)
103 HTNode newNode
= null;
106 ByteBuffer buffer
= ByteBuffer
.allocate(config
.getBlockSize());
107 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
109 res
= fc
.read(buffer
);
110 assert (res
== config
.getBlockSize());
113 /* Read the common header part */
114 byte type
= buffer
.get();
115 long start
= buffer
.getLong();
116 long end
= buffer
.getLong();
117 int seqNb
= buffer
.getInt();
118 int parentSeqNb
= buffer
.getInt();
119 int intervalCount
= buffer
.getInt();
120 int stringSectionOffset
= buffer
.getInt();
121 boolean done
= byteToBool(buffer
.get());
123 /* Now the rest of the header depends on the node type */
127 newNode
= new CoreNode(config
, seqNb
, parentSeqNb
, start
);
128 newNode
.readSpecificHeader(buffer
);
131 // TODO implement other node types
138 // /* "Claudette" (extended) nodes */
142 /* Unrecognized node type */
143 throw new IOException();
147 * At this point, we should be done reading the header and 'buffer'
148 * should only have the intervals left
150 for (i
= 0; i
< intervalCount
; i
++) {
151 newNode
.intervals
.add(HTInterval
.readFrom(buffer
));
154 /* Assign the node's other information we have read previously */
155 newNode
.nodeEnd
= end
;
156 newNode
.stringSectionOffset
= stringSectionOffset
;
157 newNode
.isDone
= done
;
163 * Write this node to the given file channel.
166 * The file channel to write to (should be sought to be correct
168 * @throws IOException
169 * If there was an error writing
171 public final void writeSelf(FileChannel fc
) throws IOException
{
172 final int blockSize
= config
.getBlockSize();
173 int curStringsEntryEndPos
= blockSize
;
175 ByteBuffer buffer
= ByteBuffer
.allocate(blockSize
);
176 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
179 /* Write the common header part */
180 buffer
.put(this.getNodeType());
181 buffer
.putLong(nodeStart
);
182 buffer
.putLong(nodeEnd
);
183 buffer
.putInt(sequenceNumber
);
184 buffer
.putInt(parentSequenceNumber
);
185 buffer
.putInt(intervals
.size());
186 buffer
.putInt(stringSectionOffset
);
187 buffer
.put(boolToByte(isDone
));
189 /* Now call the inner method to write the specific header part */
190 this.writeSpecificHeader(buffer
);
192 /* Back to us, we write the intervals */
193 for (HTInterval interval
: intervals
) {
194 int size
= interval
.writeInterval(buffer
, curStringsEntryEndPos
);
195 curStringsEntryEndPos
-= size
;
199 * Write padding between the end of the Data section and the start of
200 * the Strings section (needed to fill the node in case there is no
203 while (buffer
.position() < stringSectionOffset
) {
204 buffer
.put((byte) 0);
208 * If the offsets were right, the size of the Strings section should be
209 * == to the expected size
211 assert (curStringsEntryEndPos
== stringSectionOffset
);
213 /* Finally, write everything in the Buffer to disk */
215 // if we don't do this, flip() will lose what's after.
216 buffer
.position(blockSize
);
219 int res
= fc
.write(buffer
);
220 assert (res
== blockSize
);
223 // ------------------------------------------------------------------------
225 // ------------------------------------------------------------------------
228 * Retrieve the history tree configuration used for this node.
230 * @return The history tree config
232 protected HTConfig
getConfig() {
237 * Get the start time of this node.
239 * @return The start time of this node
241 public long getNodeStart() {
246 * Get the end time of this node.
248 * @return The end time of this node
250 public long getNodeEnd() {
258 * Get the sequence number of this node.
260 * @return The sequence number of this node
262 public int getSequenceNumber() {
263 return sequenceNumber
;
267 * Get the sequence number of this node's parent.
269 * @return The parent sequence number
271 public int getParentSequenceNumber() {
272 return parentSequenceNumber
;
276 * Change this node's parent. Used when we create a new root node for
280 * The sequence number of the node that is the new parent
282 public void setParentSequenceNumber(int newParent
) {
283 parentSequenceNumber
= newParent
;
287 * Return if this node is "done" (full and written to disk).
289 * @return If this node is done or not
291 public boolean isDone() {
296 * Add an interval to this node
299 * Interval to add to this node
301 public void addInterval(HTInterval newInterval
) {
302 /* Just in case, but should be checked before even calling this function */
303 assert (newInterval
.getIntervalSize() <= this.getNodeFreeSpace());
305 intervals
.add(newInterval
);
307 /* Update the in-node offset "pointer" */
308 stringSectionOffset
-= (newInterval
.getStringsEntrySize());
312 * We've received word from the containerTree that newest nodes now exist to
313 * our right. (Puts isDone = true and sets the endtime)
316 * The nodeEnd time that the node will have
318 public void closeThisNode(long endtime
) {
319 assert (endtime
>= this.nodeStart
);
321 if (intervals
.size() > 0) {
323 * Sort the intervals by ascending order of their end time. This
324 * speeds up lookups a bit
326 Collections
.sort(intervals
);
329 * Make sure there are no intervals in this node with their EndTime
330 * > the one requested. Only need to check the last one since they
333 assert (endtime
>= intervals
.get(intervals
.size() - 1).getEndTime());
337 this.nodeEnd
= endtime
;
342 * The method to fill up the stateInfo (passed on from the Current State
343 * Tree when it does a query on the SHT). We'll replace the data in that
344 * vector with whatever relevant we can find from this node
347 * The same stateInfo that comes from SHT's doQuery()
349 * The timestamp for which the query is for. Only return
350 * intervals that intersect t.
351 * @throws TimeRangeException
354 public void writeInfoFromNode(List
<ITmfStateInterval
> stateInfo
, long t
)
355 throws TimeRangeException
{
356 assert (this.isDone
); // not sure this will always be the case...
359 if (intervals
.size() == 0) {
362 startIndex
= getStartIndexFor(t
);
364 for (int i
= startIndex
; i
< intervals
.size(); i
++) {
366 * Now we only have to compare the Start times, since we now the End
367 * times necessarily fit
369 if (intervals
.get(i
).getStartTime() <= t
) {
370 stateInfo
.set(intervals
.get(i
).getAttribute(), intervals
.get(i
));
377 * Get a single Interval from the information in this node If the
378 * key/timestamp pair cannot be found, we return null.
381 * The attribute quark to look for
384 * @return The Interval containing the information we want, or null if it
386 * @throws TimeRangeException If 't' is invalid
388 public HTInterval
getRelevantInterval(int key
, long t
) throws TimeRangeException
{
389 assert (this.isDone
);
391 HTInterval curInterval
;
393 if (intervals
.size() == 0) {
397 startIndex
= getStartIndexFor(t
);
399 for (int i
= startIndex
; i
< intervals
.size(); i
++) {
400 curInterval
= intervals
.get(i
);
401 if (curInterval
.getAttribute() == key
402 && curInterval
.getStartTime() <= t
403 && curInterval
.getEndTime() >= t
) {
407 /* We didn't find the relevant information in this node */
411 private int getStartIndexFor(long t
) throws TimeRangeException
{
416 * Since the intervals are sorted by end time, we can skip all the ones
417 * at the beginning whose end times are smaller than 't'. Java does
418 * provides a .binarySearch method, but its API is quite weird...
420 dummy
= new HTInterval(0, t
, 0, TmfStateValue
.nullValue());
421 index
= Collections
.binarySearch(intervals
, dummy
);
425 * .binarySearch returns a negative number if the exact value was
426 * not found. Here we just want to know where to start searching, we
427 * don't care if the value is exact or not.
433 /* Sometimes binarySearch yields weird stuff... */
437 if (index
>= intervals
.size()) {
438 index
= intervals
.size() - 1;
442 * Another API quirkiness, the returned index is the one of the *last*
443 * element of a series of equal endtimes, which happens sometimes. We
444 * want the *first* element of such a series, to read through them
448 && intervals
.get(index
- 1).compareTo(intervals
.get(index
)) == 0) {
456 * @return The offset, within the node, where the Data section ends
458 private int getDataSectionEndOffset() {
459 return this.getTotalHeaderSize() + HTNode
.DATA_ENTRY_SIZE
* intervals
.size();
463 * Returns the free space in the node, which is simply put, the
464 * stringSectionOffset - dataSectionOffset
466 * @return The amount of free space in the node (in bytes)
468 public int getNodeFreeSpace() {
469 return stringSectionOffset
- this.getDataSectionEndOffset();
473 * Returns the current space utilization of this node, as a percentage.
474 * (used space / total usable space, which excludes the header)
476 * @return The percentage (value between 0 and 100) of space utilization in
479 public long getNodeUsagePercent() {
480 final int blockSize
= config
.getBlockSize();
481 float freePercent
= (float) this.getNodeFreeSpace()
482 / (float) (blockSize
- this.getTotalHeaderSize())
484 return (long) (100L - freePercent
);
488 * Convert from a boolean to a byte primitive.
491 * The boolean to convert
492 * @return A byte worth 0 (false) or 1 (true)
494 protected static final byte boolToByte(boolean thebool
) {
502 * Convert from a byte primitive (0 or 1) to a boolean.
505 * The byte to convert
506 * @return True if 'thebyte' is 1, false otherwise
508 protected static final boolean byteToBool(byte thebyte
) {
509 return (thebyte
== (byte) 1);
513 * @name Debugging functions
516 @SuppressWarnings("nls")
518 public String
toString() {
519 /* Only used for debugging, shouldn't be externalized */
520 StringBuffer buf
= new StringBuffer("Node #" + sequenceNumber
+ ", ");
521 buf
.append(this.toStringSpecific());
522 buf
.append(intervals
.size() + " intervals (" + this.getNodeUsagePercent()
525 buf
.append("[" + this.nodeStart
+ " - ");
527 buf
= buf
.append("" + this.nodeEnd
+ "]");
529 buf
= buf
.append("...]");
531 return buf
.toString();
535 * Debugging function that prints out the contents of this node
538 * PrintWriter in which we will print the debug output
540 @SuppressWarnings("nls")
541 public void debugPrintIntervals(PrintWriter writer
) {
542 /* Only used for debugging, shouldn't be externalized */
543 writer
.println("Node #" + sequenceNumber
+ ":");
545 /* Array of children */
546 if (this.getNodeType() == 1) { /* Only Core Nodes can have children */
547 CoreNode thisNode
= (CoreNode
) this;
548 writer
.print(" " + thisNode
.getNbChildren() + " children");
549 if (thisNode
.getNbChildren() >= 1) {
550 writer
.print(": [ " + thisNode
.getChild(0));
551 for (int i
= 1; i
< thisNode
.getNbChildren(); i
++) {
552 writer
.print(", " + thisNode
.getChild(i
));
559 /* List of intervals in the node */
560 writer
.println(" Intervals contained:");
561 for (int i
= 0; i
< intervals
.size(); i
++) {
562 writer
.println(intervals
.get(i
).toString());
564 writer
.println('\n');
570 * 16 - 2x long (start time, end time)
572 * 16 - 4x int (seq number, parent seq number, intervalcount, strings
575 * 1 - byte (done or not)
577 protected static final int COMMON_HEADER_SIZE
= 34;
579 // ------------------------------------------------------------------------
581 // ------------------------------------------------------------------------
584 * Get the byte value representing the node type.
586 * @return The node type
588 public abstract byte getNodeType();
591 * Return the total header size of this node type.
593 * @return The total header size
595 public abstract int getTotalHeaderSize();
598 * Read the type-specific part of the node header from a byte buffer.
601 * The byte buffer to read from. It should be already positioned
604 public abstract void readSpecificHeader(ByteBuffer buffer
);
607 * Write the type-specific part of the header in a byte buffer.
610 * The buffer to write to. It should already be at the correct
613 public abstract void writeSpecificHeader(ByteBuffer buffer
);
616 * Node-type-specific toString method. Used for debugging.
618 * @return A string representing the node
620 public abstract String
toStringSpecific();
This page took 0.046835 seconds and 5 git commands to generate.