1 /*******************************************************************************
2 * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others.
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
10 * Alexandre Montplaisir - Initial API and implementation
11 *******************************************************************************/
13 package org
.eclipse
.tracecompass
.segmentstore
.core
.treemap
;
15 import static org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
.checkNotNull
;
17 import java
.util
.Collection
;
18 import java
.util
.Iterator
;
19 import java
.util
.TreeMap
;
20 import java
.util
.concurrent
.locks
.ReadWriteLock
;
21 import java
.util
.concurrent
.locks
.ReentrantReadWriteLock
;
23 import org
.eclipse
.jdt
.annotation
.NonNull
;
24 import org
.eclipse
.jdt
.annotation
.Nullable
;
25 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
26 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegmentStore
;
27 import org
.eclipse
.tracecompass
.segmentstore
.core
.SegmentComparators
;
29 import com
.google
.common
.collect
.ImmutableList
;
30 import com
.google
.common
.collect
.Iterables
;
31 import com
.google
.common
.collect
.Ordering
;
32 import com
.google
.common
.collect
.Sets
;
33 import com
.google
.common
.collect
.TreeMultimap
;
36 * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
37 * This relatively simple implementation holds everything in memory, and as such
38 * cannot contain too much data.
40 * The TreeMapStore itself is Iterable, and its iteration order will be by
41 * ascending order of start times. For segments with identical start times, the
42 * secondary comparator will be the end time. If even those are equal, it will
43 * defer to the segments' natural ordering ({@link ISegment#compareTo}).
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.
49 * Removal operations are not supported.
52 * The type of segment held in this store
54 * @author Alexandre Montplaisir
56 public class TreeMapStore
<@NonNull E
extends ISegment
> implements ISegmentStore
<E
> {
58 private final ReadWriteLock fLock
= new ReentrantReadWriteLock(false);
60 private final TreeMultimap
<Long
, E
> fStartTimesIndex
;
61 private final TreeMultimap
<Long
, E
> fEndTimesIndex
;
63 private volatile long fSize
;
65 private @Nullable transient Iterable
<E
> fLastSnapshot
= null;
70 public TreeMapStore() {
72 * For the start times index, the "key comparator" will compare the
73 * start times as longs directly. This is the primary comparator for its
76 * The secondary "value" comparator will check the end times first, and
77 * in the event of a tie, defer to the ISegment's Comparable
78 * implementation, a.k.a. its natural ordering.
80 * The same is done for the end times index, but swapping the first two
81 * comparators instead.
83 fStartTimesIndex
= TreeMultimap
.create(
84 SegmentComparators
.LONG_COMPARATOR
,
85 Ordering
.from(SegmentComparators
.INTERVAL_END_COMPARATOR
).compound(Ordering
.natural()));
87 fEndTimesIndex
= TreeMultimap
.create(
88 SegmentComparators
.LONG_COMPARATOR
,
89 Ordering
.from(SegmentComparators
.INTERVAL_START_COMPARATOR
).compound(Ordering
.natural()));
94 // ------------------------------------------------------------------------
95 // Methods from Collection
96 // ------------------------------------------------------------------------
99 public Iterator
<E
> iterator() {
100 fLock
.readLock().lock();
102 Iterable
<E
> lastSnapshot
= fLastSnapshot
;
103 if (lastSnapshot
== null) {
104 lastSnapshot
= ImmutableList
.copyOf(fStartTimesIndex
.values());
105 fLastSnapshot
= lastSnapshot
;
107 return checkNotNull(lastSnapshot
.iterator());
109 fLock
.readLock().unlock();
114 public boolean add(@Nullable E val
) {
116 throw new IllegalArgumentException();
119 fLock
.writeLock().lock();
121 if (fStartTimesIndex
.put(Long
.valueOf(val
.getStart()), val
)) {
122 fEndTimesIndex
.put(Long
.valueOf(val
.getEnd()), val
);
124 fLastSnapshot
= null;
129 fLock
.writeLock().unlock();
135 return Long
.valueOf(fSize
).intValue();
139 public boolean isEmpty() {
144 public boolean contains(@Nullable Object o
) {
145 fLock
.readLock().lock();
147 return fStartTimesIndex
.containsValue(o
);
149 fLock
.readLock().unlock();
154 public boolean containsAll(@Nullable Collection
<?
> c
) {
155 fLock
.readLock().lock();
157 return fStartTimesIndex
.values().containsAll(c
);
159 fLock
.readLock().unlock();
164 public Object
[] toArray() {
165 fLock
.readLock().lock();
167 return fStartTimesIndex
.values().toArray();
169 fLock
.readLock().unlock();
174 public <T
> T
[] toArray(T
[] a
) {
175 fLock
.readLock().lock();
177 return fStartTimesIndex
.values().toArray(a
);
179 fLock
.readLock().unlock();
184 public boolean remove(@Nullable Object o
) {
185 throw new UnsupportedOperationException();
189 public boolean addAll(@Nullable Collection
<?
extends E
> c
) {
191 throw new IllegalArgumentException();
194 fLock
.writeLock().lock();
196 boolean changed
= false;
198 if (this.add(elem
)) {
204 fLock
.writeLock().unlock();
209 public boolean removeAll(@Nullable Collection
<?
> c
) {
210 throw new UnsupportedOperationException();
214 public boolean retainAll(@Nullable Collection
<?
> c
) {
215 throw new UnsupportedOperationException();
219 public void clear() {
220 fLock
.writeLock().lock();
223 fEndTimesIndex
.clear();
224 fStartTimesIndex
.clear();
226 fLock
.writeLock().unlock();
230 // ------------------------------------------------------------------------
231 // Methods added by ISegmentStore
232 // ------------------------------------------------------------------------
235 public Iterable
<E
> getIntersectingElements(long position
) {
237 * The intervals intersecting 't' are those whose 1) start time is
238 * *lower* than 't' AND 2) end time is *higher* than 't'.
240 fLock
.readLock().lock();
242 Iterable
<E
> matchStarts
= Iterables
.concat(fStartTimesIndex
.asMap().headMap(position
, true).values());
243 Iterable
<E
> matchEnds
= Iterables
.concat(fEndTimesIndex
.asMap().tailMap(position
, true).values());
244 return checkNotNull(Sets
.intersection(Sets
.newHashSet(matchStarts
), Sets
.newHashSet(matchEnds
)));
246 fLock
.readLock().unlock();
251 public Iterable
<E
> getIntersectingElements(long start
, long end
) {
252 fLock
.readLock().lock();
254 Iterable
<E
> matchStarts
= Iterables
.concat(fStartTimesIndex
.asMap().headMap(end
, true).values());
255 Iterable
<E
> matchEnds
= Iterables
.concat(fEndTimesIndex
.asMap().tailMap(start
, true).values());
256 return checkNotNull(Sets
.intersection(Sets
.newHashSet(matchStarts
), Sets
.newHashSet(matchEnds
)));
258 fLock
.readLock().unlock();
263 public void dispose() {
264 fLock
.writeLock().lock();
266 fStartTimesIndex
.clear();
267 fEndTimesIndex
.clear();
270 fLock
.writeLock().unlock();