analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.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.Comparator;
  17 import java.util.Iterator;
  18 import java.util.List;
  19 import java.util.concurrent.locks.ReentrantLock;
  20 import java.util.stream.Collectors;
  21
  22 import org.eclipse.jdt.annotation.NonNull;
  23 import org.eclipse.jdt.annotation.Nullable;
  24 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  25 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  26
  27 import com.google.common.collect.ImmutableList;
  28
  29 /**
  30  * Implementation of an {@link ISegmentStore} using one in-memory
  31  * {@link ArrayList}. This relatively simple implementation holds everything in
  32  * memory, and as such cannot contain too much data.
  33  *
  34  * The LazyArrayListStore itself is {@link Iterable}, and its iteration order
  35  * will be by ascending order of start times. For segments with identical start
  36  * times, the secondary comparator will be the end time. If even those are
  37  * equal, it will defer to the segments' natural ordering (
  38  * {@link ISegment#compareTo}).
  39  *
  40  * This structure sorts in a lazy way to allow faster insertions. However, if
  41  * the structure is out of order, the next read (getting intersecting elements,
  42  * iterating...) will perform a sort. It may have inconsistent performance, but
  43  * should be faster at building when receiving shuffled datasets than the
  44  * {@link ArrayListStore}.
  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 LazyArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
  54
  55     private static final String ERROR_MESSAGE = "Cannot remove from a segment store"; //$NON-NLS-1$
  56
  57     private final Comparator<E> COMPARATOR = (o1, o2) -> {
  58         int ret = Long.compare(o1.getStart(), o2.getStart());
  59         if (ret == 0) {
  60             return Long.compare(o1.getEnd(), o2.getEnd());
  61         }
  62         return ret;
  63     };
  64
  65     private final ReentrantLock fLock = new ReentrantLock(false);
  66
  67     private final @NonNull List<E> fStore = new ArrayList<>();
  68
  69     private @Nullable transient Iterable<E> fLastSnapshot = null;
  70
  71     private volatile boolean fDirty = false;
  72
  73     /**
  74      * Constructor
  75      */
  76     public LazyArrayListStore() {
  77         // do nothing
  78     }
  79
  80     /**
  81      * Constructor
  82      *
  83      * @param array
  84      *            an array of elements to wrap in the segment store
  85      *
  86      */
  87     public LazyArrayListStore(Object[] array) {
  88         for (int i = 0; i < array.length; i++) {
  89             if (array[i] instanceof ISegment) {
  90                 E element = (E) array[i];
  91                 setDirtyIfNeeded(element);
  92                 fStore.add(element);
  93             }
  94         }
  95         if (fDirty) {
  96             sortStore();
  97         }
  98     }
  99
 100     private void setDirtyIfNeeded(@NonNull E value) {
 101         if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) {
 102             fDirty = true;
 103         }
 104     }
 105     // ------------------------------------------------------------------------
 106     // Methods from Collection
 107     // ------------------------------------------------------------------------
 108
 109     @Override
 110     public Iterator<E> iterator() {
 111         fLock.lock();
 112         try {
 113             if (fDirty) {
 114                 sortStore();
 115             }
 116             Iterable<E> lastSnapshot = fLastSnapshot;
 117             if (lastSnapshot == null) {
 118                 lastSnapshot = ImmutableList.copyOf(fStore);
 119                 fLastSnapshot = lastSnapshot;
 120             }
 121             return checkNotNull(lastSnapshot.iterator());
 122         } finally {
 123             fLock.unlock();
 124         }
 125     }
 126
 127     /**
 128      * DO NOT CALL FROM OUTSIDE OF A LOCK!
 129      */
 130     private void sortStore() {
 131         fStore.sort(COMPARATOR);
 132         fDirty = false;
 133     }
 134
 135     @Override
 136     public boolean add(@Nullable E val) {
 137         if (val == null) {
 138             throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$
 139         }
 140
 141         fLock.lock();
 142         try {
 143             setDirtyIfNeeded(val);
 144             fStore.add(val);
 145             fLastSnapshot = null;
 146             return true;
 147         } finally {
 148             fLock.unlock();
 149         }
 150     }
 151
 152     @Override
 153     public int size() {
 154         return fStore.size();
 155     }
 156
 157     @Override
 158     public boolean isEmpty() {
 159         fLock.lock();
 160         try {
 161             return fStore.isEmpty();
 162         } finally {
 163             fLock.unlock();
 164         }
 165     }
 166
 167     @Override
 168     public boolean contains(@Nullable Object o) {
 169         fLock.lock();
 170         try {
 171             return fStore.contains(o);
 172         } finally {
 173             fLock.unlock();
 174         }
 175     }
 176
 177     @Override
 178     public boolean containsAll(@Nullable Collection<?> c) {
 179         fLock.lock();
 180         try {
 181             return fStore.containsAll(c);
 182         } finally {
 183             fLock.unlock();
 184         }
 185     }
 186
 187     @Override
 188     public Object[] toArray() {
 189         fLock.lock();
 190         try {
 191             if (fDirty) {
 192                 sortStore();
 193             }
 194             return fStore.toArray();
 195         } finally {
 196             fLock.unlock();
 197         }
 198     }
 199
 200     @Override
 201     public <T> T[] toArray(T[] a) {
 202         fLock.lock();
 203         try {
 204             if (fDirty) {
 205                 sortStore();
 206             }
 207             return fStore.toArray(a);
 208         } finally {
 209             fLock.unlock();
 210         }
 211     }
 212
 213     @Override
 214     public boolean addAll(@Nullable Collection<? extends E> c) {
 215         if (c == null) {
 216             throw new IllegalArgumentException();
 217         }
 218
 219         fLock.lock();
 220         try {
 221             boolean changed = false;
 222             for (E elem : c) {
 223                 if (add(elem)) {
 224                     changed = true;
 225                 }
 226             }
 227             return changed;
 228         } finally {
 229             fLock.unlock();
 230         }
 231     }
 232
 233     @Override
 234     public boolean removeAll(@Nullable Collection<?> c) {
 235         throw new UnsupportedOperationException(ERROR_MESSAGE);
 236     }
 237
 238     @Override
 239     public boolean retainAll(@Nullable Collection<?> c) {
 240         throw new UnsupportedOperationException(ERROR_MESSAGE);
 241     }
 242
 243     @Override
 244     public boolean remove(@Nullable Object o) {
 245         throw new UnsupportedOperationException(ERROR_MESSAGE);
 246     }
 247
 248     @Override
 249     public void clear() {
 250         fLock.lock();
 251         try {
 252             fStore.clear();
 253             fLastSnapshot = null;
 254             fDirty = false;
 255         } finally {
 256             fLock.unlock();
 257         }
 258     }
 259
 260     // ------------------------------------------------------------------------
 261     // Methods added by ISegmentStore
 262     // ------------------------------------------------------------------------
 263
 264     @Override
 265     public Iterable<E> getIntersectingElements(long position) {
 266         fLock.lock();
 267         if (fDirty) {
 268             sortStore();
 269         }
 270         /*
 271          * The intervals intersecting 't' are those whose 1) start time is
 272          * *lower* than 't' AND 2) end time is *higher* than 't'.
 273          */
 274         try {
 275             return fStore.stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
 276         } finally {
 277             fLock.unlock();
 278         }
 279     }
 280
 281     @Override
 282     public Iterable<E> getIntersectingElements(long start, long end) {
 283         fLock.lock();
 284         if (fDirty) {
 285             sortStore();
 286         }
 287         try {
 288             return fStore.stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
 289         } finally {
 290             fLock.unlock();
 291         }
 292     }
 293
 294     @Override
 295     public void dispose() {
 296         fLock.lock();
 297         try {
 298             fStore.clear();
 299             fDirty = false;
 300         } finally {
 301             fLock.unlock();
 302         }
 303     }
 304 }