statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/treemap/TreeMapStore.java

   1 /*******************************************************************************
   2  * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others.
   3  *
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *    Alexandre Montplaisir - Initial API and implementation
  11  *******************************************************************************/
  12
  13 package org.eclipse.tracecompass.segmentstore.core.treemap;
  14
  15 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  16
  17 import java.util.Iterator;
  18 import java.util.TreeMap;
  19
  20 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  21 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  22 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  23
  24 import com.google.common.collect.Iterables;
  25 import com.google.common.collect.Ordering;
  26 import com.google.common.collect.Sets;
  27 import com.google.common.collect.TreeMultimap;
  28
  29 /**
  30  * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
  31  * This relatively simple implementation holds everything in memory, and as such
  32  * cannot contain too much data.
  33  *
  34  * The TreeMapStore itself is Iterable, and its iteration order will be by
  35  * ascending order of start times. For segments with identical start times, the
  36  * secondary comparator will be the end time. If even those are equal, it will
  37  * defer to the segments' natural ordering ({@link ISegment#compareTo}).
  38  *
  39  * The store's tree maps will not accept duplicate key-value pairs, which means
  40  * that if you want several segments with the same start and end times, make
  41  * sure their compareTo() differentiates them.
  42  *
  43  * @param <T>
  44  *            The type of segment held in this store
  45  *
  46  * @author Alexandre Montplaisir
  47  */
  48 public class TreeMapStore<T extends ISegment> implements ISegmentStore<T> {
  49
  50     private final TreeMultimap<Long, T> fStartTimesIndex;
  51     private final TreeMultimap<Long, T> fEndTimesIndex;
  52
  53     private volatile long fSize;
  54
  55     /**
  56      * Constructor
  57      */
  58     public TreeMapStore() {
  59         /*
  60          * For the start times index, the "key comparator" will compare the
  61          * start times as longs directly. This is the primary comparator for its
  62          * tree map.
  63          *
  64          * The secondary "value" comparator will check the end times first, and
  65          * in the event of a tie, defer to the ISegment's Comparable
  66          * implementation, a.k.a. its natural ordering.
  67          *
  68          * The same is done for the end times index, but swapping the first two
  69          * comparators instead.
  70          */
  71         fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(
  72                 SegmentComparators.LONG_COMPARATOR,
  73                 Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())));
  74
  75         fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(
  76                 SegmentComparators.LONG_COMPARATOR,
  77                 Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())));
  78
  79         fSize = 0;
  80     }
  81
  82     @Override
  83     public Iterator<T> iterator() {
  84         return checkNotNull(fStartTimesIndex.values().iterator());
  85     }
  86
  87     @Override
  88     public synchronized void addElement(T val) {
  89         if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) {
  90             fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
  91             fSize++;
  92         }
  93     }
  94
  95     @Override
  96     public long getNbElements() {
  97         return fSize;
  98     }
  99
 100     @Override
 101     public Iterable<T> getIntersectingElements(long position) {
 102         /*
 103          * The intervals intersecting 't' are those whose 1) start time is
 104          * *lower* than 't' AND 2) end time is *higher* than 't'.
 105          */
 106         Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values());
 107         Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values());
 108
 109         return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 110     }
 111
 112     @Override
 113     public Iterable<T> getIntersectingElements(long start, long end) {
 114         Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values());
 115         Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values());
 116
 117         return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 118     }
 119
 120     @Override
 121     public synchronized void dispose() {
 122         fStartTimesIndex.clear();
 123         fEndTimesIndex.clear();
 124         fSize = 0;
 125     }
 126 }