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