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