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