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

   1 /*******************************************************************************
   2  * Copyright (c) 2017 É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.io.File;
  13 import java.io.IOException;
  14 import java.nio.channels.ClosedChannelException;
  15 import java.util.Collection;
  16 import java.util.Comparator;
  17 import java.util.Deque;
  18 import java.util.Iterator;
  19 import java.util.LinkedList;
  20 import java.util.NoSuchElementException;
  21 import java.util.PriorityQueue;
  22
  23 import org.eclipse.jdt.annotation.NonNull;
  24 import org.eclipse.jdt.annotation.Nullable;
  25 import org.eclipse.tracecompass.common.core.NonNullUtils;
  26 import org.eclipse.tracecompass.datastore.core.interval.IHTIntervalReader;
  27 import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition;
  28 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.HTNode;
  29 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.IHTNode;
  30 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.overlapping.AbstractOverlappingHistoryTree;
  31 import org.eclipse.tracecompass.internal.provisional.segmentstore.core.ISegment2;
  32 import org.eclipse.tracecompass.internal.segmentstore.core.Activator;
  33 import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
  34 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  35
  36 import com.google.common.annotations.VisibleForTesting;
  37
  38 /**
  39  * Specific implementation of the history tree to save a segment store. It adds
  40  * specific methods to get the elements intersecting a given time range.
  41  *
  42  * @author Loic Prieur-Drevon
  43  * @author Geneviève Bastien
  44  * @param <E>
  45  *            type of {@link ISegment}
  46  */
  47 public class SegmentHistoryTree<E extends ISegment2> extends AbstractOverlappingHistoryTree<E, SegmentTreeNode<E>> {
  48
  49     private static final int HISTORY_MAGIC_NUMBER = 0x05FFC600;
  50
  51     /** File format version. Increment when breaking compatibility. */
  52     private static final int FILE_VERSION = 1;
  53
  54     private static final int ITERATOR_QUEUE_SIZE = 2000;
  55
  56     // ------------------------------------------------------------------------
  57     // Constructors/"Destructors"
  58     // ------------------------------------------------------------------------
  59
  60     /**
  61      * Create a new State History from scratch, specifying all configuration
  62      * parameters.
  63      *
  64      * @param stateHistoryFile
  65      *            The name of the history file
  66      * @param blockSize
  67      *            The size of each "block" on disk in bytes. One node will
  68      *            always fit in one block. It should be at least 4096.
  69      * @param maxChildren
  70      *            The maximum number of children allowed per core (non-leaf)
  71      *            node.
  72      * @param providerVersion
  73      *            The version of the state provider. If a file already exists,
  74      *            and their versions match, the history file will not be rebuilt
  75      *            uselessly.
  76      * @param treeStart
  77      *            The start time of the history
  78      * @param intervalReader
  79      *            typed ISegment to allow access to the readSegment methods
  80      * @throws IOException
  81      *             If an error happens trying to open/write to the file
  82      *             specified in the config
  83      */
  84     public SegmentHistoryTree(File stateHistoryFile,
  85             int blockSize,
  86             int maxChildren,
  87             int providerVersion,
  88             long treeStart,
  89             IHTIntervalReader<E> intervalReader) throws IOException {
  90         super(stateHistoryFile,
  91                 blockSize,
  92                 maxChildren,
  93                 providerVersion,
  94                 treeStart,
  95                 intervalReader);
  96
  97     }
  98
  99     /**
 100      * "Reader" constructor : instantiate a SHTree from an existing tree file on
 101      * disk
 102      *
 103      * @param existingStateFile
 104      *            Path/filename of the history-file we are to open
 105      * @param expProviderVersion
 106      *            The expected version of the state provider
 107      * @param intervalReader
 108      *            typed ISegment to allow access to the readSegment methods
 109      * @throws IOException
 110      *             If an error happens reading the file
 111      */
 112     public SegmentHistoryTree(File existingStateFile, int expProviderVersion, IHTIntervalReader<E> intervalReader) throws IOException {
 113         super(existingStateFile, expProviderVersion, intervalReader);
 114     }
 115
 116     @Override
 117     protected int getMagicNumber() {
 118         return HISTORY_MAGIC_NUMBER;
 119     }
 120
 121     @Override
 122     protected int getFileVersion() {
 123         return FILE_VERSION;
 124     }
 125
 126     @Override
 127     protected @NonNull IHTNodeFactory<E, SegmentTreeNode<E>> getNodeFactory() {
 128         // This cannot be defined statically because of the generic and because
 129         // this method is called from the constructor of the abstract class,
 130         // assigning it in a final field in the constructor generates a NPE. So
 131         // we return the method directly here.
 132         return (t, b, m, seq, p, start) -> new SegmentTreeNode<>(t, b, m, seq, p, start);
 133     }
 134
 135     // ------------------------------------------
 136     // Segment store specific methods
 137     // ------------------------------------------
 138
 139     /**
 140      * Get the number of elements in this history tree
 141      *
 142      * @return The number of elements in this tree
 143      */
 144     public int size() {
 145         SegmentTreeNode<E> node;
 146         long total = 0;
 147
 148         try {
 149             // Add the number of intervals of each node
 150             for (int seq = 0; seq < getNodeCount(); seq++) {
 151                 node = readNode(seq);
 152                 total += node.getNumIntervals();
 153             }
 154         } catch (ClosedChannelException e) {
 155             Activator.instance().logError(e.getMessage(), e);
 156             return 0;
 157         }
 158         return (int) total;
 159     }
 160
 161     /**
 162      * Return whether the tree is empty or not
 163      *
 164      * @return <code>true</code> if the tree is empty
 165      */
 166     public boolean isEmpty() {
 167         Iterator<E> it = iterator();
 168         if (it == null) {
 169             return true;
 170         }
 171         return !it.hasNext();
 172     }
 173
 174     // ------------------------------------------
 175     // Iterators
 176     // ------------------------------------------
 177
 178     /**
 179      * Get an iterator for the elements of this tree. It uses
 180      * {@link #getIntersectingElements(long, long)} for the full duration of the
 181      * tree.
 182      *
 183      * @return An iterator for this tree
 184      */
 185     public @Nullable Iterator<E> iterator() {
 186         return getIntersectingElements(getTreeStart(), getTreeEnd()).iterator();
 187     }
 188
 189     /**
 190      * Return an iterator for a range. It will iterate through the nodes
 191      * top-down and visit only the nodes that contain segments within this range
 192      * and for each of those nodes, it gets the segments that intersect the
 193      * range
 194      *
 195      * @param start
 196      *            The start of the range
 197      * @param end
 198      *            The end of the range
 199      * @return The iterable
 200      */
 201     public Iterable<@NonNull E> getIntersectingElements(final long start, final long end) {
 202         final TimeRangeCondition rc = TimeRangeCondition.forContinuousRange(start, end);
 203         return new Iterable<E>() {
 204
 205             @Override
 206             public Iterator<@NonNull E> iterator() {
 207                 return new Iterator<E>() {
 208
 209                     private boolean started = false;
 210                     private Deque<Integer> queue = new LinkedList<>();
 211                     private Deque<E> intersecting = new LinkedList<>();
 212
 213                     @Override
 214                     public @NonNull E next() {
 215                         hasNext();
 216                         return NonNullUtils.checkNotNull(intersecting.removeFirst());
 217                     }
 218
 219                     @Override
 220                     public boolean hasNext() {
 221                         /* Iteration has not started yet */
 222                         if (!started) {
 223                             queue.add(getRootNode().getSequenceNumber());
 224                             started = true;
 225                         }
 226
 227                         /*
 228                          * Need to read nodes until either we find more segments
 229                          * or iterate over all segments
 230                          */
 231                         while (intersecting.isEmpty() && !queue.isEmpty()) {
 232                             SegmentTreeNode<E> currentNode;
 233                             try {
 234                                 currentNode = readNode(queue.pop());
 235                             } catch (ClosedChannelException e) {
 236                                 Activator.instance().logError(e.getMessage(), e);
 237                                 return false;
 238                             }
 239                             if (currentNode.getNodeType() == IHTNode.NodeType.CORE) {
 240                                 queue.addAll(currentNode.selectNextChildren(rc));
 241                             }
 242                             intersecting.addAll(currentNode.getMatchingIntervals(rc, interval -> true));
 243                         }
 244
 245                         /* Return if we have found segments */
 246                         return !intersecting.isEmpty();
 247                     }
 248                 };
 249             }
 250         };
 251     }
 252
 253     /**
 254      * Return an iterator for a range where segments are sorted
 255      *
 256      * @param start
 257      *            The start of the range
 258      * @param end
 259      *            The end of the range
 260      * @param order
 261      *            The comparator to sort elements with
 262      * @return The iterable
 263      */
 264     public Iterable<@NonNull E> getIntersectingElements(long start, long end, Comparator<@NonNull E> order) {
 265         final TimeRangeCondition rc = TimeRangeCondition.forContinuousRange(start, end);
 266         return new Iterable<E>() {
 267
 268             @Override
 269             public Iterator<@NonNull E> iterator() {
 270                 return new Iterator<E>() {
 271
 272                     private boolean started = false;
 273                     private PriorityQueue<SegmentTreeNode.Tuple<E>> queue = new PriorityQueue<>(getNodeCount(),
 274                             Comparator.comparing(SegmentTreeNode.Tuple<E>::getSegment, order));
 275
 276                     private PriorityQueue<E> intersecting = new PriorityQueue<>(ITERATOR_QUEUE_SIZE, order);
 277
 278                     @Override
 279                     public @NonNull E next() {
 280                         if (hasNext()) {
 281                             return NonNullUtils.checkNotNull(intersecting.remove());
 282                         }
 283                         throw new NoSuchElementException();
 284                     }
 285
 286                     @Override
 287                     public boolean hasNext() {
 288                         /* Iteration has not started yet */
 289                         if (!started) {
 290                             SegmentTreeNode<E> rootNode = getRootNode();
 291
 292                             /*
 293                              * Add the root node with any segment for the tuple,
 294                              * it will always be read.
 295                              */
 296                             queue.add(new SegmentTreeNode.Tuple(new BasicSegment(0,0), rootNode.getSequenceNumber()));
 297
 298                             started = true;
 299                         }
 300
 301                         /*
 302                          * Need to read nodes until either we find more segments
 303                          * or iterate over all nodes
 304                          */
 305                         while (!queue.isEmpty() && (intersecting.isEmpty()
 306                                 || order.compare(intersecting.element(), queue.peek().getSegment()) > 0)) {
 307                             SegmentTreeNode<E> currentNode;
 308                             try {
 309                                 currentNode = readNode(queue.poll().getSequenceNumber());
 310                             } catch (ClosedChannelException e) {
 311                                 Activator.instance().logError(e.getMessage(), e);
 312                                 return false;
 313                             }
 314                             if (currentNode.getNodeType() == HTNode.NodeType.CORE) {
 315                                 queue.addAll(((SegmentTreeNode) currentNode).selectNextChildren(rc, order));
 316                             }
 317                             intersecting.addAll(currentNode.getMatchingIntervals(rc, interval -> true));
 318                         }
 319
 320                         /* Return if we have found segments */
 321                         return !intersecting.isEmpty();
 322                     }
 323                 };
 324             }
 325         };
 326     }
 327
 328     // ------------------------------------------------------------------------
 329     // Test-specific methods
 330     // ------------------------------------------------------------------------
 331
 332     @Override
 333     @VisibleForTesting
 334     protected boolean verifyChildrenSpecific(SegmentTreeNode<E> parent, int index, SegmentTreeNode<E> child) {
 335         return (parent.getMaxStart(index) >= child.getMaxStart()
 336                 && parent.getMinEnd(index) <= child.getMinEnd()
 337                 && parent.getLongest(index) >= child.getLongest()
 338                 && parent.getShortest(index) <= child.getShortest());
 339     }
 340
 341     @Override
 342     @VisibleForTesting
 343     protected boolean verifyIntersectingChildren(SegmentTreeNode<E> parent, SegmentTreeNode<E> child) {
 344         int childSequence = child.getSequenceNumber();
 345         for (long t = parent.getNodeStart(); t < parent.getNodeEnd(); t++) {
 346             TimeRangeCondition rc = TimeRangeCondition.singleton(t);
 347             boolean shouldBeInCollection = (rc.intersects(child.getNodeStart(), child.getNodeEnd()));
 348             Collection<Integer> nextChildren = parent.selectNextChildren(rc);
 349             if (shouldBeInCollection != nextChildren.contains(childSequence)) {
 350                 return false;
 351             }
 352         }
 353         return true;
 354     }
 355
 356 }