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
.Iterator
;
18 import java
.util
.TreeMap
;
19 import java
.util
.concurrent
.locks
.ReadWriteLock
;
20 import java
.util
.concurrent
.locks
.ReentrantReadWriteLock
;
22 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
23 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegmentStore
;
24 import org
.eclipse
.tracecompass
.segmentstore
.core
.SegmentComparators
;
26 import com
.google
.common
.collect
.Iterables
;
27 import com
.google
.common
.collect
.Ordering
;
28 import com
.google
.common
.collect
.Sets
;
29 import com
.google
.common
.collect
.TreeMultimap
;
32 * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
33 * This relatively simple implementation holds everything in memory, and as such
34 * cannot contain too much data.
36 * The TreeMapStore itself is Iterable, and its iteration order will be by
37 * ascending order of start times. For segments with identical start times, the
38 * secondary comparator will be the end time. If even those are equal, it will
39 * defer to the segments' natural ordering ({@link ISegment#compareTo}).
41 * The store's tree maps will not accept duplicate key-value pairs, which means
42 * that if you want several segments with the same start and end times, make
43 * sure their compareTo() differentiates them.
46 * The type of segment held in this store
48 * @author Alexandre Montplaisir
50 public class TreeMapStore
<T
extends ISegment
> implements ISegmentStore
<T
> {
52 private final ReadWriteLock fLock
= new ReentrantReadWriteLock(false);
54 private final TreeMultimap
<Long
, T
> fStartTimesIndex
;
55 private final TreeMultimap
<Long
, T
> fEndTimesIndex
;
62 public TreeMapStore() {
64 * For the start times index, the "key comparator" will compare the
65 * start times as longs directly. This is the primary comparator for its
68 * The secondary "value" comparator will check the end times first, and
69 * in the event of a tie, defer to the ISegment's Comparable
70 * implementation, a.k.a. its natural ordering.
72 * The same is done for the end times index, but swapping the first two
73 * comparators instead.
75 fStartTimesIndex
= checkNotNull(TreeMultimap
.<Long
, T
> create(
76 SegmentComparators
.LONG_COMPARATOR
,
77 Ordering
.from(SegmentComparators
.INTERVAL_END_COMPARATOR
).compound(Ordering
.natural())));
79 fEndTimesIndex
= checkNotNull(TreeMultimap
.<Long
, T
> create(
80 SegmentComparators
.LONG_COMPARATOR
,
81 Ordering
.from(SegmentComparators
.INTERVAL_START_COMPARATOR
).compound(Ordering
.natural())));
87 * Warning, this is not thread safe, and can cause concurrent modification
91 public Iterator
<T
> iterator() {
92 return checkNotNull(fStartTimesIndex
.values().iterator());
96 public void addElement(T val
) {
97 fLock
.writeLock().lock();
99 if (fStartTimesIndex
.put(Long
.valueOf(val
.getStart()), val
)) {
100 fEndTimesIndex
.put(Long
.valueOf(val
.getEnd()), val
);
104 fLock
.writeLock().unlock();
109 public long getNbElements() {
110 fLock
.readLock().lock();
114 fLock
.readLock().unlock();
119 public Iterable
<T
> getIntersectingElements(long position
) {
121 * The intervals intersecting 't' are those whose 1) start time is
122 * *lower* than 't' AND 2) end time is *higher* than 't'.
124 fLock
.readLock().lock();
126 Iterable
<T
> matchStarts
= Iterables
.concat(fStartTimesIndex
.asMap().headMap(position
, true).values());
127 Iterable
<T
> matchEnds
= Iterables
.concat(fEndTimesIndex
.asMap().tailMap(position
, true).values());
128 return checkNotNull(Sets
.intersection(Sets
.newHashSet(matchStarts
), Sets
.newHashSet(matchEnds
)));
130 fLock
.readLock().unlock();
135 public Iterable
<T
> getIntersectingElements(long start
, long end
) {
136 fLock
.readLock().lock();
138 Iterable
<T
> matchStarts
= Iterables
.concat(fStartTimesIndex
.asMap().headMap(end
, true).values());
139 Iterable
<T
> matchEnds
= Iterables
.concat(fEndTimesIndex
.asMap().tailMap(start
, true).values());
140 return checkNotNull(Sets
.intersection(Sets
.newHashSet(matchStarts
), Sets
.newHashSet(matchEnds
)));
142 fLock
.readLock().unlock();
147 public void dispose() {
148 fLock
.writeLock().lock();
150 fStartTimesIndex
.clear();
151 fEndTimesIndex
.clear();
154 fLock
.writeLock().unlock();