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.BasicSegment;
  27 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  28 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  29
  30 import com.google.common.collect.ImmutableList;
  31
  32 /**
  33  * Implementation of an {@link ISegmentStore} using one in-memory
  34  * {@link ArrayList}. This relatively simple implementation holds everything in
  35  * memory, and as such cannot contain too much data.
  36  *
  37  * The ArrayListStore itself is {@link Iterable}, and its iteration order will
  38  * be by ascending order of start times. For segments with identical start
  39  * times, the secondary comparator will be the end time. If even those are
  40  * equal, it will defer to the segments' natural ordering (
  41  * {@link ISegment#compareTo}).
  42  *
  43  * The store's tree maps will not accept duplicate key-value pairs, which means
  44  * that if you want several segments with the same start and end times, make
  45  * sure their compareTo() differentiates them.
  46  *
  47  * Removal operations are not supported.
  48  *
  49  * @param <E>
  50  *            The type of segment held in this store
  51  *
  52  * @author Matthew Khouzam
  53  */
  54 public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
  55
  56     private final Comparator<E> COMPARATOR = (o1, o2) -> {
  57         int ret = Long.compare(o1.getStart(), o2.getStart());
  58         if (ret == 0) {
  59             return Long.compare(o1.getEnd(), o2.getEnd());
  60         }
  61         return ret;
  62     };
  63
  64     private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
  65
  66     private final List<E> fStore;
  67
  68     private @Nullable transient Iterable<E> fLastSnapshot = null;
  69
  70     /**
  71      * Constructor
  72      */
  73     public ArrayListStore() {
  74         fStore = new ArrayList<>();
  75     }
  76
  77     /**
  78      * Constructor
  79      *
  80      * @param array
  81      *            an array of elements to wrap in the segment store
  82      *
  83      */
  84     public ArrayListStore(Object[] array) {
  85         fStore = new ArrayList<>();
  86         for (int i = 0; i < array.length; i++) {
  87             if (array[i] instanceof ISegment) {
  88                 fStore.add((E) array[i]);
  89             }
  90         }
  91         fStore.sort(COMPARATOR);
  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 = ImmutableList.copyOf(fStore);
 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("Cannot add null value"); //$NON-NLS-1$
 116         }
 117
 118         fLock.writeLock().lock();
 119         try {
 120             int insertPoint = Collections.binarySearch(fStore, val);
 121             insertPoint = insertPoint >= 0 ? insertPoint : -insertPoint - 1;
 122             fStore.add(insertPoint, val);
 123             fLastSnapshot = null;
 124             return true;
 125         } finally {
 126             fLock.writeLock().unlock();
 127         }
 128     }
 129
 130     @Override
 131     public int size() {
 132         return fStore.size();
 133     }
 134
 135     @Override
 136     public boolean isEmpty() {
 137         fLock.readLock().lock();
 138         try {
 139             return fStore.isEmpty();
 140         } finally {
 141             fLock.readLock().unlock();
 142         }
 143     }
 144
 145     @Override
 146     public boolean contains(@Nullable Object o) {
 147         fLock.readLock().lock();
 148         try {
 149             return fStore.contains(o);
 150         } finally {
 151             fLock.readLock().unlock();
 152         }
 153     }
 154
 155     @Override
 156     public boolean containsAll(@Nullable Collection<?> c) {
 157         fLock.readLock().lock();
 158         try {
 159             return fStore.containsAll(c);
 160         } finally {
 161             fLock.readLock().unlock();
 162         }
 163     }
 164
 165     @Override
 166     public Object[] toArray() {
 167         fLock.readLock().lock();
 168         try {
 169             return fStore.toArray();
 170         } finally {
 171             fLock.readLock().unlock();
 172         }
 173     }
 174
 175     @Override
 176     public <T> T[] toArray(T[] a) {
 177         fLock.readLock().lock();
 178         try {
 179             return fStore.toArray(a);
 180         } finally {
 181             fLock.readLock().unlock();
 182         }
 183     }
 184
 185     @Override
 186     public boolean remove(@Nullable Object o) {
 187         throw new UnsupportedOperationException();
 188     }
 189
 190     @Override
 191     public boolean addAll(@Nullable Collection<? extends E> c) {
 192         if (c == null) {
 193             throw new IllegalArgumentException();
 194         }
 195
 196         fLock.writeLock().lock();
 197         try {
 198             boolean changed = false;
 199             for (E elem : c) {
 200                 if (this.add(elem)) {
 201                     changed = true;
 202                 }
 203             }
 204             return changed;
 205         } finally {
 206             fLock.writeLock().unlock();
 207         }
 208     }
 209
 210     @Override
 211     public boolean removeAll(@Nullable Collection<?> c) {
 212         throw new UnsupportedOperationException();
 213     }
 214
 215     @Override
 216     public boolean retainAll(@Nullable Collection<?> c) {
 217         throw new UnsupportedOperationException();
 218     }
 219
 220     @Override
 221     public void clear() {
 222         fLock.writeLock().lock();
 223         try {
 224             fStore.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             /*
 243              * as fStore is sorted by start then end times, restrict sub array
 244              * to elements whose start times <= t as stream.filter won't do it.
 245              */
 246             int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
 247             index = (index >= 0) ? index : -index - 1;
 248             return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
 249         } finally {
 250             fLock.readLock().unlock();
 251         }
 252     }
 253
 254     @Override
 255     public Iterable<E> getIntersectingElements(long start, long end) {
 256         fLock.readLock().lock();
 257         try {
 258             int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
 259             index = (index >= 0) ? index : -index - 1;
 260             return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
 261         } finally {
 262             fLock.readLock().unlock();
 263         }
 264     }
 265
 266     @Override
 267     public void dispose() {
 268         fLock.writeLock().lock();
 269         try {
 270             fStore.clear();
 271         } finally {
 272             fLock.writeLock().unlock();
 273         }
 274     }
 275 }