package org.eclipse.tracecompass.internal.segmentstore.core.arraylist;
-import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
-
import java.util.ArrayList;
-import java.util.Collection;
import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.List;
-import java.util.concurrent.locks.ReadWriteLock;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
import org.eclipse.jdt.annotation.NonNull;
-import org.eclipse.jdt.annotation.Nullable;
-import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Ordering;
/**
* Implementation of an {@link ISegmentStore} using one in-memory
* equal, it will defer to the segments' natural ordering (
* {@link ISegment#compareTo}).
*
- * The store's tree maps will not accept duplicate key-value pairs, which means
- * that if you want several segments with the same start and end times, make
- * sure their compareTo() differentiates them.
- *
* Removal operations are not supported.
*
* @param <E>
*
* @author Matthew Khouzam
*/
-public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
-
- private final Comparator<E> COMPARATOR = Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR)
- .compound(SegmentComparators.INTERVAL_END_COMPARATOR);
-
- private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
-
- private final List<E> fStore;
-
- private @Nullable transient Iterable<E> fLastSnapshot = null;
+public class ArrayListStore<@NonNull E extends ISegment> extends LazyArrayListStore<E> {
/**
* Constructor
*/
public ArrayListStore() {
- fStore = new ArrayList<>();
+ /** Same constructor as {@link LazyArrayListStore} */
}
/**
*
* @param array
* an array of elements to wrap in the segment store
- *
*/
public ArrayListStore(Object[] array) {
- fStore = new ArrayList<>();
- for (int i = 0; i < array.length; i++) {
- if (array[i] instanceof ISegment) {
- fStore.add((E) array[i]);
- }
- }
- fStore.sort(COMPARATOR);
- }
- // ------------------------------------------------------------------------
- // Methods from Collection
- // ------------------------------------------------------------------------
-
- @Override
- public Iterator<E> iterator() {
- fLock.readLock().lock();
- try {
- Iterable<E> lastSnapshot = fLastSnapshot;
- if (lastSnapshot == null) {
- lastSnapshot = ImmutableList.copyOf(fStore);
- fLastSnapshot = lastSnapshot;
- }
- return checkNotNull(lastSnapshot.iterator());
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean add(@Nullable E val) {
- if (val == null) {
- throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$
- }
-
- fLock.writeLock().lock();
- try {
- int insertPoint = Collections.binarySearch(fStore, val);
- insertPoint = insertPoint >= 0 ? insertPoint : -insertPoint - 1;
- fStore.add(insertPoint, val);
- fLastSnapshot = null;
- return true;
- } finally {
- fLock.writeLock().unlock();
- }
- }
-
- @Override
- public int size() {
- fLock.readLock().lock();
- try {
- return fStore.size();
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean isEmpty() {
- fLock.readLock().lock();
- try {
- return fStore.isEmpty();
- } finally {
- fLock.readLock().unlock();
- }
+ super(array);
+ sortStore();
}
@Override
- public boolean contains(@Nullable Object o) {
- fLock.readLock().lock();
- try {
- return fStore.contains(o);
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean containsAll(@Nullable Collection<?> c) {
- fLock.readLock().lock();
- try {
- return fStore.containsAll(c);
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public Object[] toArray() {
- fLock.readLock().lock();
- try {
- return fStore.toArray();
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public <T> T[] toArray(T[] a) {
- fLock.readLock().lock();
- try {
- return fStore.toArray(a);
- } finally {
- fLock.readLock().unlock();
- }
- }
-
- @Override
- public boolean addAll(@Nullable Collection<? extends E> c) {
- if (c == null) {
- throw new IllegalArgumentException();
- }
-
- fLock.writeLock().lock();
- try {
- boolean changed = false;
- for (E elem : c) {
- if (this.add(elem)) {
- changed = true;
- }
- }
- return changed;
- } finally {
- fLock.writeLock().unlock();
- }
- }
-
- @Override
- public void clear() {
- fLock.writeLock().lock();
- try {
- fStore.clear();
- } finally {
- fLock.writeLock().unlock();
- }
- }
-
- // ------------------------------------------------------------------------
- // Methods added by ISegmentStore
- // ------------------------------------------------------------------------
-
- @Override
- public Iterable<E> getIntersectingElements(long start, long end) {
- fLock.readLock().lock();
- try {
- /*
- * Compute the index of the last Segment we will find in here,
- * correct the negative insertion point and add 1 for array size.
- */
- int arraySize = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
- arraySize = (arraySize >= 0) ? arraySize + 1 : -arraySize;
- /*
- * Create the ArrayList as late as possible, with size = (first
- * intersecting segment index) - (last intersecting segment index).
- */
- ArrayList<E> iterable = null;
- for (E seg : fStore) {
- if (seg.getStart() <= end && seg.getEnd() >= start) {
- if (iterable == null) {
- iterable = new ArrayList<>(arraySize);
- }
- iterable.add(seg);
- } else if (seg.getStart() > end) {
- /*
- * Since segments are sorted by start times, there is no
- * point in searching segments that start too late.
- */
- break;
- }
- arraySize--;
- }
- if (iterable != null) {
- iterable.trimToSize();
- return iterable;
- }
- return Collections.EMPTY_LIST;
- } finally {
- fLock.readLock().unlock();
- }
+ protected int getInsertionPoint(E value) {
+ /*
+ * For the ArrayListStore, insert new segments in the position that
+ * maintains the list ordered along COMPARATOR.
+ */
+ int insertPoint = Collections.binarySearch(fStore, value, COMPARATOR);
+ return insertPoint >= 0 ? insertPoint : -insertPoint - 1;
}
@Override
- public void dispose() {
- fLock.writeLock().lock();
- try {
- fStore.clear();
- } finally {
- fLock.writeLock().unlock();
- }
+ protected void setDirtyIfNeeded(@NonNull E value) {
+ /*
+ * Do nothing, ArrayListStore is never dirty as we insert the segments
+ * in sorted order.
+ */
}
}
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Function;
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
-import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Ordering;
/**
* Implementation of an {@link ISegmentStore} using one in-memory
*/
public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> {
- private final Comparator<E> COMPARATOR = Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR)
- .compound(SegmentComparators.INTERVAL_END_COMPARATOR);
+ /**
+ * Order to sort the backing array.
+ */
+ protected final Comparator<E> COMPARATOR = Comparator.comparing(E::getStart)
+ .thenComparing(E::getEnd).thenComparing(Function.identity());
private final ReentrantLock fLock = new ReentrantLock(false);
- private final List<E> fStore = new ArrayList<>();
+ /**
+ * Backing {@link ArrayList}
+ */
+ protected final List<E> fStore;
private @Nullable transient Iterable<E> fLastSnapshot = null;
* Constructor
*/
public LazyArrayListStore() {
- // do nothing
+ fStore = new ArrayList<>();
}
/**
*
* @param array
* an array of elements to wrap in the segment store
- *
*/
public LazyArrayListStore(Object[] array) {
- for (int i = 0; i < array.length; i++) {
- if (array[i] instanceof ISegment) {
- E element = (E) array[i];
+ fStore = new ArrayList<>(array.length);
+ for (Object object : array) {
+ if (object instanceof ISegment) {
+ E element = (E) object;
setDirtyIfNeeded(element);
fStore.add(element);
fStart = Math.min(fStart, element.getStart());
}
}
- private void setDirtyIfNeeded(@NonNull E value) {
+ /**
+ * Set the store as dirty after inserting a segment if it does not respect
+ * the order.
+ *
+ * @param value
+ * newly inserted segment.
+ */
+ protected void setDirtyIfNeeded(@NonNull E value) {
if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) {
fDirty = true;
}
}
/**
- * DO NOT CALL FROM OUTSIDE OF A LOCK!
+ * Sort the backing ArrayList using the order defined by the internal
+ * comparator. DO NOT CALL FROM OUTSIDE OF A LOCK!
*/
- private void sortStore() {
+ protected void sortStore() {
fStore.sort(COMPARATOR);
fDirty = false;
}
fLock.lock();
try {
setDirtyIfNeeded(val);
- fStore.add(val);
+ fStore.add(getInsertionPoint(val), val);
fLastSnapshot = null;
fStart = Math.min(fStart, val.getStart());
fEnd = Math.max(fEnd, val.getEnd());
}
}
+ /**
+ * Find at which position to insert the new element.
+ * DO NOT CALL FROM OUTSIDE OF A LOCK!
+ *
+ * @param value
+ * new Segment
+ * @return insertion position in the backing array
+ */
+ protected int getInsertionPoint(E value) {
+ /*
+ * For the LazyArrayListStore, always insert at the end, the backing
+ * ArrayList will be sorted upon reading.
+ */
+ return fStore.size();
+ }
+
@Override
public int size() {
fLock.lock();
fLock.lock();
try {
- boolean changed = false;
- for (E elem : c) {
- if (add(elem)) {
- changed = true;
- }
- }
- return changed;
+ c.forEach(this::add);
+ return true;
} finally {
fLock.unlock();
}
@Override
public void dispose() {
- fLock.lock();
- try {
- fStore.clear();
- fDirty = false;
- } finally {
- fLock.unlock();
- }
+ clear();
}
}
projects / deliverable / tracecompass.git / commitdiff
