statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/segmentHistoryTree/SegmentTreeNode.java

   1 /*******************************************************************************
   2  * Copyright (c) 2016 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *******************************************************************************/
   9
  10 package org.eclipse.tracecompass.internal.segmentstore.core.segmentHistoryTree;
  11
  12 import java.nio.ByteBuffer;
  13 import java.util.Collection;
  14 import java.util.Collections;
  15 import java.util.Comparator;
  16 import java.util.HashSet;
  17 import java.util.Set;
  18
  19 import org.eclipse.jdt.annotation.NonNull;
  20 import org.eclipse.jdt.annotation.Nullable;
  21 import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition;
  22 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.IHTNode;
  23 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.overlapping.OverlappingNode;
  24 import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
  25 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  26 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  27
  28 /**
  29  * The history tree node class for segment history tree. This is an extension of
  30  * the {@link OverlappingNode} class and keeps more information about the
  31  * children of a node, that will help for sorting segments, one of the specific
  32  * functionalities of the segment stores.
  33  *
  34  * @author Loic Prieur-Drevon
  35  * @author Geneviève Bastien
  36  * @param <E>
  37  *            type of {@link ISegment}
  38  */
  39 public class SegmentTreeNode<E extends ISegment> extends OverlappingNode<E> {
  40
  41     // These values represent the values for the current node only, not its
  42     // children
  43     private long fMaxStart = 0;
  44     private long fMinEnd = Long.MAX_VALUE;
  45     private long fShortest = Long.MAX_VALUE;
  46     private long fLongest = 0;
  47
  48     /**
  49      * Constructor
  50      *
  51      * @param type
  52      *            The type of this node
  53      * @param blockSize
  54      *            The size (in bytes) of a serialized node on disk
  55      * @param maxChildren
  56      *            The maximum allowed number of children per node
  57      * @param seqNumber
  58      *            The (unique) sequence number assigned to this particular node
  59      * @param parentSeqNumber
  60      *            The sequence number of this node's parent node
  61      * @param start
  62      *            The earliest timestamp stored in this node
  63      */
  64     public SegmentTreeNode(NodeType type, int blockSize, int maxChildren, int seqNumber, int parentSeqNumber, long start) {
  65         super(type, blockSize, maxChildren, seqNumber, parentSeqNumber, start);
  66         fMaxStart = start;
  67     }
  68
  69     /**
  70      * Adds the data concerning the segment nodes, max start/min end and
  71      * durations
  72      *
  73      * @param <E>  type of {@link ISegment}
  74      */
  75     protected static class OverlappingSegmentCoreData<E extends ISegment> extends OverlappingExtraData {
  76
  77         // These values cover the full subtrees of the child nodes
  78         // Max start of an interval
  79         private final long[] fChildMaxStart;
  80         // minimum end of an interval
  81         private final long[] fChildMinEnd;
  82         // minimum length
  83         private final long[] fMinLength;
  84         // maximum length
  85         private final long[] fMaxLength;
  86
  87         /**
  88          * Segment history tree node data constructor
  89          *
  90          * @param node
  91          *            The node containing this extra data.
  92          */
  93         public OverlappingSegmentCoreData(SegmentTreeNode<?> node) {
  94             super(node);
  95             int size = getNode().getMaxChildren();
  96             /*
  97              * We instantiate the following arrays at full size right away,
  98              * since we want to reserve that space in the node's header.
  99              * "this.nbChildren" will tell us how many relevant entries there
 100              * are in those tables.
 101              */
 102             fChildMaxStart = new long[size];
 103             fChildMinEnd = new long[size];
 104             fMinLength = new long[size];
 105             fMaxLength = new long[size];
 106             for (int i = 0; i < size; i++) {
 107                 fChildMaxStart[i] = 0;
 108                 fChildMinEnd[i] = Long.MAX_VALUE;
 109                 fMinLength[i] = Long.MAX_VALUE;
 110                 fMaxLength[i] = Long.MIN_VALUE;
 111             }
 112         }
 113
 114         @Override
 115         protected SegmentTreeNode<?> getNode() {
 116             /* Type enforced by constructor */
 117             return (SegmentTreeNode<?>) super.getNode();
 118         }
 119
 120         @Override
 121         public void readSpecificHeader(@NonNull ByteBuffer buffer) {
 122             super.readSpecificHeader(buffer);
 123             int size = getNode().getMaxChildren();
 124
 125             for (int i = 0; i < size; i++) {
 126                 fChildMaxStart[i] = buffer.getLong();
 127                 fChildMinEnd[i] = buffer.getLong();
 128                 fMinLength[i] = buffer.getLong();
 129                 fMaxLength[i] = buffer.getLong();
 130             }
 131         }
 132
 133         @Override
 134         protected void writeSpecificHeader(@NonNull ByteBuffer buffer) {
 135             getNode().takeReadLock();
 136             try {
 137                 super.writeSpecificHeader(buffer);
 138
 139                 int size = getNode().getMaxChildren();
 140
 141                 /*
 142                  * Write the children array
 143                  */
 144                 for (int i = 0; i < size; i++) {
 145                     buffer.putLong(fChildMaxStart[i]);
 146                     buffer.putLong(fChildMinEnd[i]);
 147                     buffer.putLong(fMinLength[i]);
 148                     buffer.putLong(fMaxLength[i]);
 149                 }
 150             } finally {
 151                 getNode().releaseReadLock();
 152             }
 153         }
 154
 155         @Override
 156         protected int getSpecificHeaderSize() {
 157             int maxChildren = getNode().getMaxChildren();
 158             int specificSize = super.getSpecificHeaderSize();
 159             /*
 160              * MAX_NB * Timevalue (max starts, min ends, min length, max length
 161              * table)
 162              */
 163             specificSize += 4 * Long.BYTES * maxChildren;
 164
 165             return specificSize;
 166         }
 167
 168         @Override
 169         public void linkNewChild(IHTNode<?> childNode) {
 170             // The child node should be a SegmentTreeNode
 171             if (!(childNode instanceof SegmentTreeNode)) {
 172                 throw new IllegalArgumentException("Adding a node that is not an segment tree node to an segment tree!"); //$NON-NLS-1$
 173             }
 174             getNode().takeWriteLock();
 175             try {
 176
 177                 super.linkNewChild(childNode);
 178                 final int childIndex = getNbChildren() - 1;
 179
 180                 // The child node should be a SegmentTreeNode, but in case it
 181                 // isn't, just return here
 182                 if (!(childNode instanceof SegmentTreeNode<?>)) {
 183                     return;
 184                 }
 185
 186                 SegmentTreeNode<E> segmentNode = (SegmentTreeNode<E>) childNode;
 187                 // The child node may already have segments, so we update
 188                 // child's data with what is already in there
 189                 updateChild(segmentNode, childIndex);
 190
 191                 // Add a listener on the child node to update its data in the
 192                 // children's arrays
 193                 segmentNode.addListener((node, endtime) -> updateChild((SegmentTreeNode<E>) node, childIndex));
 194
 195             } finally {
 196                 getNode().releaseWriteLock();
 197             }
 198         }
 199
 200         private void updateChild(SegmentTreeNode<E> child, int childIndex) {
 201             fChildMaxStart[childIndex] = child.getMaxStart();
 202             fChildMinEnd[childIndex] = child.getMinEnd();
 203             fMinLength[childIndex] = child.getShortest();
 204             fMaxLength[childIndex] = child.getLongest();
 205             // The child node's extra data applies to the child and its subtree,
 206             // so also update with the child's children
 207             for (int i = 0; i < child.getNbChildren(); i++) {
 208                 fChildMaxStart[childIndex] = Math.max(fChildMaxStart[childIndex], child.getMaxStart(i));
 209                 fChildMinEnd[childIndex] = Math.min(fChildMinEnd[childIndex], child.getMinEnd(i));
 210                 fMinLength[childIndex] = Math.min(fMinLength[childIndex], child.getShortest(i));
 211                 fMaxLength[childIndex] = Math.max(fMaxLength[childIndex], child.getLongest(i));
 212             }
 213         }
 214
 215         /* Make sure it is visible to the enclosing class */
 216         @Override
 217         protected Collection<Integer> selectNextIndices(TimeRangeCondition rc) {
 218             return super.selectNextIndices(rc);
 219         }
 220
 221         /**
 222          * Get the maximum start value of a child and its subtree
 223          *
 224          * @param index
 225          *            The child index
 226          * @return The maximum start value of the child at index and its subtree
 227          */
 228         public long getMaxStart(int index) {
 229             getNode().takeReadLock();
 230             try {
 231                 if (index >= getNbChildren()) {
 232                     throw new IndexOutOfBoundsException("The child at index " + index + " does not exist"); //$NON-NLS-1$ //$NON-NLS-2$
 233                 }
 234                 return fChildMaxStart[index];
 235             } finally {
 236                 getNode().releaseReadLock();
 237             }
 238         }
 239
 240         /**
 241          * Get the minimum end value of a child and its subtree
 242          *
 243          * @param index
 244          *            The child index
 245          * @return The minimum end value of the child at index and its subtree
 246          */
 247         public long getMinEnd(int index) {
 248             getNode().takeReadLock();
 249             try {
 250                 if (index >= getNbChildren()) {
 251                     throw new IndexOutOfBoundsException("The child at index " + index + " does not exist"); //$NON-NLS-1$ //$NON-NLS-2$
 252                 }
 253                 return fChildMinEnd[index];
 254             } finally {
 255                 getNode().releaseReadLock();
 256             }
 257         }
 258
 259         /**
 260          * Get the shortest element length of a child and its subtree
 261          *
 262          * @param index
 263          *            The child index
 264          * @return The shortest length of the child at index and its subtree
 265          */
 266         public long getShortest(int index) {
 267             getNode().takeReadLock();
 268             try {
 269                 if (index >= getNbChildren()) {
 270                     throw new IndexOutOfBoundsException("The child at index " + index + " does not exist"); //$NON-NLS-1$ //$NON-NLS-2$
 271                 }
 272                 return fMinLength[index];
 273             } finally {
 274                 getNode().releaseReadLock();
 275             }
 276         }
 277
 278         /**
 279          * Get the longest element length of a child and its subtree
 280          *
 281          * @param index
 282          *            The child index
 283          * @return The longest length of the child at index and its subtree
 284          */
 285         public long getLongest(int index) {
 286             getNode().takeReadLock();
 287             try {
 288                 if (index >= getNbChildren()) {
 289                     throw new IndexOutOfBoundsException("The child at index " + index + " does not exist"); //$NON-NLS-1$ //$NON-NLS-2$
 290                 }
 291                 return fMaxLength[index];
 292             } finally {
 293                 getNode().releaseReadLock();
 294             }
 295         }
 296
 297         /**
 298          * Get the segment for a child node with the least value for the field
 299          * corresponding to the comparator's field.
 300          *
 301          * @param index
 302          *            The index of the child node
 303          * @param order
 304          *            The comparator with which to sort segments
 305          * @return A segment whose value for the field that correspond to the
 306          *         comparator is the least value of the child node
 307          */
 308         public ISegment getIndex(int index, Comparator<E> order) {
 309             if (order.equals(SegmentComparators.INTERVAL_START_COMPARATOR)) {
 310                 return new BasicSegment(getChildStart(index), getChildStart(index));
 311             } else if (order.equals(SegmentComparators.INTERVAL_START_COMPARATOR.reversed())) {
 312                 return new BasicSegment(fChildMaxStart[index], fChildMaxStart[index]);
 313             } else if (order.equals(SegmentComparators.INTERVAL_END_COMPARATOR)) {
 314                 return new BasicSegment(fChildMinEnd[index], fChildMinEnd[index]);
 315             } else if (order.equals(SegmentComparators.INTERVAL_END_COMPARATOR.reversed())) {
 316                 return new BasicSegment(getChildEnd(index), getChildEnd(index));
 317             } else if (order.equals(SegmentComparators.INTERVAL_LENGTH_COMPARATOR)) {
 318                 return new BasicSegment(0, fMinLength[index]);
 319             } else if (order.equals(SegmentComparators.INTERVAL_LENGTH_COMPARATOR.reversed())) {
 320                 return new BasicSegment(0, fMaxLength[index]);
 321             }
 322             // TODO: Don't know what to do with other comparators yet
 323             return new BasicSegment(getChild(index), getChild(index));
 324         }
 325
 326     }
 327
 328     @Override
 329     protected @Nullable OverlappingSegmentCoreData<E> createNodeExtraData(final NodeType type) {
 330         if (type == NodeType.CORE) {
 331             return new OverlappingSegmentCoreData<>(this);
 332         }
 333         return null;
 334     }
 335
 336     /**
 337      * Get the number of intervals in this node
 338      *
 339      * @return The number of intervals
 340      */
 341     public int getNumIntervals() {
 342         return getIntervals().size();
 343     }
 344
 345     @Override
 346     public void add(E newInterval) {
 347         super.add(newInterval);
 348         updateBoundaries(newInterval);
 349     }
 350
 351     /**
 352      * Get the maximum start time of an interval in this node
 353      *
 354      * @return the latest start time of this node's intervals
 355      */
 356     public long getMaxStart() {
 357         return fMaxStart;
 358     }
 359
 360     /**
 361      * Get the earliest end time of an interval in this node
 362      *
 363      * @return the earliest end time of this node's intervals
 364      */
 365     public long getMinEnd() {
 366         return fMinEnd;
 367     }
 368
 369     /**
 370      * Get the shortest duration of the intervals of this node
 371      *
 372      * @return the shortest duration of this node's intervals
 373      */
 374     public long getShortest() {
 375         return fShortest;
 376     }
 377
 378     /**
 379      * Get the longest duration of the intervals of this node
 380      *
 381      * @return the longest duration of this node's intervals
 382      */
 383     public long getLongest() {
 384         return fLongest;
 385     }
 386
 387     /**
 388      * Get the children intersecting the given time range, and return the least
 389      * element for each child wrt to the comparator
 390      *
 391      * @param range
 392      *            The range condition (start, end times) of the children
 393      * @param order
 394      *            The comparator to use to compare segments in child nodes
 395      * @return For each intersecting child, a Tuple with the segment with the
 396      *         least value for the comparator
 397      */
 398     public Set<Tuple<ISegment>> selectNextChildren(TimeRangeCondition range, Comparator<E> order) {
 399         OverlappingSegmentCoreData<E> extraData = getCoreNodeData();
 400         if (extraData != null) {
 401             Set<Tuple<ISegment>> set = new HashSet<>();
 402             for (Integer index : extraData.selectNextIndices(range)) {
 403                 set.add(new Tuple<>(extraData.getIndex(index, order), extraData.getChild(index)));
 404             }
 405             return set;
 406         }
 407         return Collections.emptySet();
 408     }
 409
 410     @Override
 411     protected @Nullable OverlappingSegmentCoreData<E> getCoreNodeData() {
 412         return (OverlappingSegmentCoreData<E>) super.getCoreNodeData();
 413     }
 414
 415     /**
 416      * Get the maximum start value of a child subtree of this node
 417      *
 418      * @param index
 419      *            The index of the child subtree
 420      * @return The child subtree's maximal start value
 421      */
 422     protected long getMaxStart(int index) {
 423         OverlappingSegmentCoreData<E> extraData = getCoreNodeData();
 424         if (extraData != null) {
 425             return extraData.getMaxStart(index);
 426         }
 427         throw new UnsupportedOperationException("A leaf node does not have children"); //$NON-NLS-1$
 428     }
 429
 430     /**
 431      * Get the minimum end value of a child subtree of this node
 432      *
 433      * @param index
 434      *            The index of the child subtree
 435      * @return The child subtree's minimum end value
 436      */
 437     protected long getMinEnd(int index) {
 438         OverlappingSegmentCoreData<E> extraData = getCoreNodeData();
 439         if (extraData != null) {
 440             return extraData.getMinEnd(index);
 441         }
 442         throw new UnsupportedOperationException("A leaf node does not have children"); //$NON-NLS-1$
 443     }
 444
 445     /**
 446      * Get the length of the shortest element of a child subtree of this node
 447      *
 448      * @param index
 449      *            The index of the child subtree
 450      * @return The child subtree's shortest element length
 451      */
 452     protected long getShortest(int index) {
 453         OverlappingSegmentCoreData<E> extraData = getCoreNodeData();
 454         if (extraData != null) {
 455             return extraData.getShortest(index);
 456         }
 457         throw new UnsupportedOperationException("A leaf node does not have children"); //$NON-NLS-1$
 458     }
 459
 460     /**
 461      * Get the length of the longest element of a child subtree of this node
 462      *
 463      * @param index
 464      *            The index of the child subtree
 465      * @return The child subtree's longest element length
 466      */
 467     protected long getLongest(int index) {
 468         OverlappingSegmentCoreData<E> extraData = getCoreNodeData();
 469         if (extraData != null) {
 470             return extraData.getLongest(index);
 471         }
 472         throw new UnsupportedOperationException("A leaf node does not have children"); //$NON-NLS-1$
 473     }
 474
 475     /**
 476      * Class to store the node sequence numbers and Index element for
 477      * sortedIterators PriorityQueue
 478      */
 479     static class Tuple<E> {
 480         private final E fSegment;
 481         private final int fNodeSequenceNumber;
 482
 483         /**
 484          * @param segment
 485          *            segment to use to order nodes in PriorityQueue
 486          * @param nodeSequenceNumber
 487          *            sequence number of the node we want to read
 488          */
 489         public Tuple(E segment, int nodeSequenceNumber) {
 490             fSegment = segment;
 491             fNodeSequenceNumber = nodeSequenceNumber;
 492         }
 493
 494         /**
 495          * @return the element to compare or <code>null</code> if this node is
 496          *         empty
 497          */
 498         public E getSegment() {
 499             return fSegment;
 500         }
 501
 502         /**
 503          * @return the sequence number to read the node
 504          */
 505         public int getSequenceNumber() {
 506             return fNodeSequenceNumber;
 507         }
 508     }
 509
 510     /**
 511      * Get the tuples of minimal segments and sequence number for this node. If
 512      * the current node is empty, <code>null</code> is returned.
 513      *
 514      * @param order
 515      *            Comparator for which we need the key
 516      * @return Tuple to sort nodes in iterator, <code>null</code> if not is
 517      *         empty
 518      */
 519     @Nullable Tuple<E> key(Comparator<@NonNull E> order) {
 520         if (isEmpty()) {
 521             return null;
 522         }
 523         return new Tuple<>(Collections.min(this.getIntervals(), order), getSequenceNumber());
 524     }
 525
 526     private void updateBoundaries(E segment) {
 527         fMaxStart = Math.max(fMaxStart, segment.getStart());
 528         fMinEnd = Math.min(fMinEnd, segment.getEnd());
 529         fShortest = Math.min(fShortest, segment.getLength());
 530         fLongest = Math.max(fLongest, segment.getLength());
 531     }
 532
 533 }