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 import java.util.concurrent.locks.ReadWriteLock;
  20 import java.util.concurrent.locks.ReentrantReadWriteLock;
  21
  22 import org.eclipse.jdt.annotation.Nullable;
  23 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  24 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  25 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  26
  27 import com.google.common.collect.ImmutableList;
  28 import com.google.common.collect.Iterables;
  29 import com.google.common.collect.Ordering;
  30 import com.google.common.collect.Sets;
  31 import com.google.common.collect.TreeMultimap;
  32
  33 /**
  34  * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
  35  * This relatively simple implementation holds everything in memory, and as such
  36  * cannot contain too much data.
  37  *
  38  * The TreeMapStore itself is Iterable, and its iteration order will be by
  39  * ascending order of start times. For segments with identical start times, the
  40  * secondary comparator will be the end time. If even those are equal, it will
  41  * defer to the segments' natural ordering ({@link ISegment#compareTo}).
  42  *
  43  * The store's tree maps will not accept duplicate key-value pairs, which means
  44  * that if you want several segments with the same start and end times, make
  45  * sure their compareTo() differentiates them.
  46  *
  47  * @param <T>
  48  *            The type of segment held in this store
  49  *
  50  * @author Alexandre Montplaisir
  51  */
  52 public class TreeMapStore<T extends ISegment> implements ISegmentStore<T> {
  53
  54     private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
  55
  56     private final TreeMultimap<Long, T> fStartTimesIndex;
  57     private final TreeMultimap<Long, T> fEndTimesIndex;
  58
  59     private long fSize;
  60
  61     private @Nullable transient Iterable<T> fLastSnapshot = null;
  62
  63     /**
  64      * Constructor
  65      */
  66     public TreeMapStore() {
  67         /*
  68          * For the start times index, the "key comparator" will compare the
  69          * start times as longs directly. This is the primary comparator for its
  70          * tree map.
  71          *
  72          * The secondary "value" comparator will check the end times first, and
  73          * in the event of a tie, defer to the ISegment's Comparable
  74          * implementation, a.k.a. its natural ordering.
  75          *
  76          * The same is done for the end times index, but swapping the first two
  77          * comparators instead.
  78          */
  79         fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(
  80                 SegmentComparators.LONG_COMPARATOR,
  81                 Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())));
  82
  83         fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(
  84                 SegmentComparators.LONG_COMPARATOR,
  85                 Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())));
  86
  87         fSize = 0;
  88     }
  89
  90     @Override
  91     public Iterator<T> iterator() {
  92         fLock.readLock().lock();
  93         try {
  94             Iterable<T> lastSnapshot = fLastSnapshot;
  95             if (lastSnapshot == null) {
  96                 lastSnapshot = checkNotNull(ImmutableList.copyOf(fStartTimesIndex.values()));
  97                 fLastSnapshot = lastSnapshot;
  98             }
  99             return checkNotNull(lastSnapshot.iterator());
 100         } finally {
 101             fLock.readLock().unlock();
 102         }
 103     }
 104
 105     @Override
 106     public void addElement(T val) {
 107         fLock.writeLock().lock();
 108         try {
 109             if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) {
 110                 fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
 111                 fSize++;
 112                 fLastSnapshot = null;
 113             }
 114         } finally {
 115             fLock.writeLock().unlock();
 116         }
 117     }
 118
 119     @Override
 120     public long getNbElements() {
 121         fLock.readLock().lock();
 122         try {
 123             return fSize;
 124         } finally {
 125             fLock.readLock().unlock();
 126         }
 127     }
 128
 129     @Override
 130     public Iterable<T> getIntersectingElements(long position) {
 131         /*
 132          * The intervals intersecting 't' are those whose 1) start time is
 133          * *lower* than 't' AND 2) end time is *higher* than 't'.
 134          */
 135         fLock.readLock().lock();
 136         try {
 137             Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values());
 138             Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values());
 139             return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 140         } finally {
 141             fLock.readLock().unlock();
 142         }
 143     }
 144
 145     @Override
 146     public Iterable<T> getIntersectingElements(long start, long end) {
 147         fLock.readLock().lock();
 148         try {
 149             Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values());
 150             Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values());
 151             return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 152         } finally {
 153             fLock.readLock().unlock();
 154         }
 155     }
 156
 157     @Override
 158     public void dispose() {
 159         fLock.writeLock().lock();
 160         try {
 161             fStartTimesIndex.clear();
 162             fEndTimesIndex.clear();
 163             fSize = 0;
 164         } finally {
 165             fLock.writeLock().unlock();
 166         }
 167     }
 168 }