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