analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/ArrayListStore.java

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