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.Collection;
  18 import java.util.Iterator;
  19 import java.util.TreeMap;
  20 import java.util.concurrent.locks.ReadWriteLock;
  21 import java.util.concurrent.locks.ReentrantReadWriteLock;
  22
  23 import org.eclipse.jdt.annotation.Nullable;
  24 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  25 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  26 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  27
  28 import com.google.common.collect.ImmutableList;
  29 import com.google.common.collect.Iterables;
  30 import com.google.common.collect.Ordering;
  31 import com.google.common.collect.Sets;
  32 import com.google.common.collect.TreeMultimap;
  33
  34 /**
  35  * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
  36  * This relatively simple implementation holds everything in memory, and as such
  37  * cannot contain too much data.
  38  *
  39  * The TreeMapStore itself is Iterable, and its iteration order will be by
  40  * ascending order of start times. For segments with identical start times, the
  41  * secondary comparator will be the end time. If even those are equal, it will
  42  * defer to the segments' natural ordering ({@link ISegment#compareTo}).
  43  *
  44  * The store's tree maps will not accept duplicate key-value pairs, which means
  45  * that if you want several segments with the same start and end times, make
  46  * sure their compareTo() differentiates them.
  47  *
  48  * Removal operations are not supported.
  49  *
  50  * @param <E>
  51  *            The type of segment held in this store
  52  *
  53  * @author Alexandre Montplaisir
  54  */
  55 public class TreeMapStore<E extends ISegment> implements ISegmentStore<E> {
  56
  57     private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
  58
  59     private final TreeMultimap<Long, E> fStartTimesIndex;
  60     private final TreeMultimap<Long, E> fEndTimesIndex;
  61
  62     private volatile long fSize;
  63
  64     private @Nullable transient Iterable<E> fLastSnapshot = null;
  65
  66     /**
  67      * Constructor
  68      */
  69     public TreeMapStore() {
  70         /*
  71          * For the start times index, the "key comparator" will compare the
  72          * start times as longs directly. This is the primary comparator for its
  73          * tree map.
  74          *
  75          * The secondary "value" comparator will check the end times first, and
  76          * in the event of a tie, defer to the ISegment's Comparable
  77          * implementation, a.k.a. its natural ordering.
  78          *
  79          * The same is done for the end times index, but swapping the first two
  80          * comparators instead.
  81          */
  82         fStartTimesIndex = checkNotNull(TreeMultimap.<Long, E> create(
  83                 SegmentComparators.LONG_COMPARATOR,
  84                 Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())));
  85
  86         fEndTimesIndex = checkNotNull(TreeMultimap.<Long, E> create(
  87                 SegmentComparators.LONG_COMPARATOR,
  88                 Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())));
  89
  90         fSize = 0;
  91     }
  92
  93     // ------------------------------------------------------------------------
  94     // Methods from Collection
  95     // ------------------------------------------------------------------------
  96
  97     @Override
  98     public Iterator<E> iterator() {
  99         fLock.readLock().lock();
 100         try {
 101             Iterable<E> lastSnapshot = fLastSnapshot;
 102             if (lastSnapshot == null) {
 103                 lastSnapshot = checkNotNull(ImmutableList.copyOf(fStartTimesIndex.values()));
 104                 fLastSnapshot = lastSnapshot;
 105             }
 106             return checkNotNull(lastSnapshot.iterator());
 107         } finally {
 108             fLock.readLock().unlock();
 109         }
 110     }
 111
 112     @Override
 113     public boolean add(@Nullable E val) {
 114         if (val == null) {
 115             throw new IllegalArgumentException();
 116         }
 117
 118         fLock.writeLock().lock();
 119         try {
 120             /* We can take a read lock while holding the write lock. */
 121             if (contains(val)) {
 122                 return false;
 123             }
 124
 125             if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) {
 126                 fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
 127                 fSize++;
 128                 fLastSnapshot = null;
 129             }
 130         } finally {
 131             fLock.writeLock().unlock();
 132         }
 133         return true;
 134     }
 135
 136     @Override
 137     public int size() {
 138         return Long.valueOf(fSize).intValue();
 139     }
 140
 141     @Override
 142     public boolean isEmpty() {
 143         return (fSize == 0);
 144     }
 145
 146     @Override
 147     public boolean contains(@Nullable Object o) {
 148         fLock.readLock().lock();
 149         try {
 150             return fStartTimesIndex.containsValue(o);
 151         } finally {
 152             fLock.readLock().unlock();
 153         }
 154     }
 155
 156
 157     @Override
 158     public boolean containsAll(@Nullable Collection<?> c) {
 159         fLock.readLock().lock();
 160         try {
 161             return fStartTimesIndex.values().containsAll(c);
 162         } finally {
 163             fLock.readLock().unlock();
 164         }
 165     }
 166
 167     @Override
 168     public Object[] toArray() {
 169         fLock.readLock().lock();
 170         try {
 171             return checkNotNull(fStartTimesIndex.values().toArray());
 172         } finally {
 173             fLock.readLock().unlock();
 174         }
 175     }
 176
 177     @Override
 178     public <T> T[] toArray(@Nullable T[] a) {
 179         fLock.readLock().lock();
 180         try {
 181             return checkNotNull(fStartTimesIndex.values().toArray(a));
 182         } finally {
 183             fLock.readLock().unlock();
 184         }
 185     }
 186
 187     @Override
 188     public boolean remove(@Nullable Object o) {
 189         throw new UnsupportedOperationException();
 190     }
 191
 192     @Override
 193     public boolean addAll(@Nullable Collection<? extends E> c) {
 194         if (c == null) {
 195             throw new IllegalArgumentException();
 196         }
 197
 198         fLock.writeLock().lock();
 199         try {
 200             boolean changed = false;
 201             for (E elem : c) {
 202                 if (this.add(elem)) {
 203                     changed = true;
 204                 }
 205             }
 206             return changed;
 207         } finally {
 208             fLock.writeLock().unlock();
 209         }
 210     }
 211
 212     @Override
 213     public boolean removeAll(@Nullable Collection<?> c) {
 214         throw new UnsupportedOperationException();
 215     }
 216
 217     @Override
 218     public boolean retainAll(@Nullable Collection<?> c) {
 219         throw new UnsupportedOperationException();
 220     }
 221
 222     @Override
 223     public void clear() {
 224         throw new UnsupportedOperationException();
 225     }
 226
 227     // ------------------------------------------------------------------------
 228     // Methods added by ISegmentStore
 229     // ------------------------------------------------------------------------
 230
 231     @Override
 232     public Iterable<E> getIntersectingElements(long position) {
 233         /*
 234          * The intervals intersecting 't' are those whose 1) start time is
 235          * *lower* than 't' AND 2) end time is *higher* than 't'.
 236          */
 237         fLock.readLock().lock();
 238         try {
 239             Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values());
 240             Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values());
 241             return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 242         } finally {
 243             fLock.readLock().unlock();
 244         }
 245     }
 246
 247     @Override
 248     public Iterable<E> getIntersectingElements(long start, long end) {
 249         fLock.readLock().lock();
 250         try {
 251             Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values());
 252             Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values());
 253             return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 254         } finally {
 255             fLock.readLock().unlock();
 256         }
 257     }
 258
 259     @Override
 260     public void dispose() {
 261         fLock.writeLock().lock();
 262         try {
 263             fStartTimesIndex.clear();
 264             fEndTimesIndex.clear();
 265             fSize = 0;
 266         } finally {
 267             fLock.writeLock().unlock();
 268         }
 269     }
 270 }