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