Commit | Line | Data |
---|---|---|
26a6a7eb | 1 | /******************************************************************************* |
e5083481 | 2 | * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others. |
26a6a7eb AM |
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 | * Contributors: | |
10 | * Alexandre Montplaisir - Initial API and implementation | |
11 | *******************************************************************************/ | |
12 | ||
13 | package org.eclipse.tracecompass.segmentstore.core.treemap; | |
14 | ||
15 | import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; | |
16 | ||
1a9cb076 | 17 | import java.util.Collection; |
26a6a7eb | 18 | import java.util.Iterator; |
26a6a7eb | 19 | import java.util.TreeMap; |
71e78f69 MK |
20 | import java.util.concurrent.locks.ReadWriteLock; |
21 | import java.util.concurrent.locks.ReentrantReadWriteLock; | |
26a6a7eb | 22 | |
c66ca500 | 23 | import org.eclipse.jdt.annotation.NonNull; |
4dafe201 | 24 | import org.eclipse.jdt.annotation.Nullable; |
26a6a7eb AM |
25 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
26 | import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; | |
e5083481 | 27 | import org.eclipse.tracecompass.segmentstore.core.SegmentComparators; |
26a6a7eb | 28 | |
4dafe201 | 29 | import com.google.common.collect.ImmutableList; |
26a6a7eb | 30 | import com.google.common.collect.Iterables; |
e5083481 | 31 | import com.google.common.collect.Ordering; |
26a6a7eb AM |
32 | import com.google.common.collect.Sets; |
33 | import com.google.common.collect.TreeMultimap; | |
34 | ||
35 | /** | |
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. | |
39 | * | |
e5083481 PT |
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}). | |
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 | * | |
1a9cb076 AM |
49 | * Removal operations are not supported. |
50 | * | |
51 | * @param <E> | |
e5083481 | 52 | * The type of segment held in this store |
26a6a7eb AM |
53 | * |
54 | * @author Alexandre Montplaisir | |
55 | */ | |
c66ca500 | 56 | public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore<E> { |
26a6a7eb | 57 | |
71e78f69 MK |
58 | private final ReadWriteLock fLock = new ReentrantReadWriteLock(false); |
59 | ||
1a9cb076 AM |
60 | private final TreeMultimap<Long, E> fStartTimesIndex; |
61 | private final TreeMultimap<Long, E> fEndTimesIndex; | |
26a6a7eb | 62 | |
1a9cb076 | 63 | private volatile long fSize; |
26a6a7eb | 64 | |
1a9cb076 | 65 | private @Nullable transient Iterable<E> fLastSnapshot = null; |
4dafe201 | 66 | |
26a6a7eb | 67 | /** |
e5083481 | 68 | * Constructor |
26a6a7eb AM |
69 | */ |
70 | public TreeMapStore() { | |
e5083481 PT |
71 | /* |
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 | |
74 | * tree map. | |
75 | * | |
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. | |
79 | * | |
80 | * The same is done for the end times index, but swapping the first two | |
81 | * comparators instead. | |
82 | */ | |
df2597e0 | 83 | fStartTimesIndex = checkNotNull(TreeMultimap.create( |
e5083481 PT |
84 | SegmentComparators.LONG_COMPARATOR, |
85 | Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural()))); | |
86 | ||
df2597e0 | 87 | fEndTimesIndex = checkNotNull(TreeMultimap.create( |
e5083481 PT |
88 | SegmentComparators.LONG_COMPARATOR, |
89 | Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural()))); | |
90 | ||
26a6a7eb AM |
91 | fSize = 0; |
92 | } | |
93 | ||
1a9cb076 AM |
94 | // ------------------------------------------------------------------------ |
95 | // Methods from Collection | |
96 | // ------------------------------------------------------------------------ | |
97 | ||
26a6a7eb | 98 | @Override |
1a9cb076 | 99 | public Iterator<E> iterator() { |
4dafe201 MK |
100 | fLock.readLock().lock(); |
101 | try { | |
1a9cb076 | 102 | Iterable<E> lastSnapshot = fLastSnapshot; |
4dafe201 MK |
103 | if (lastSnapshot == null) { |
104 | lastSnapshot = checkNotNull(ImmutableList.copyOf(fStartTimesIndex.values())); | |
105 | fLastSnapshot = lastSnapshot; | |
106 | } | |
107 | return checkNotNull(lastSnapshot.iterator()); | |
108 | } finally { | |
109 | fLock.readLock().unlock(); | |
110 | } | |
26a6a7eb AM |
111 | } |
112 | ||
113 | @Override | |
1a9cb076 AM |
114 | public boolean add(@Nullable E val) { |
115 | if (val == null) { | |
116 | throw new IllegalArgumentException(); | |
117 | } | |
118 | ||
71e78f69 MK |
119 | fLock.writeLock().lock(); |
120 | try { | |
121 | if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) { | |
122 | fEndTimesIndex.put(Long.valueOf(val.getEnd()), val); | |
123 | fSize++; | |
4dafe201 | 124 | fLastSnapshot = null; |
8b246d45 | 125 | return true; |
71e78f69 | 126 | } |
8b246d45 | 127 | return false; |
71e78f69 MK |
128 | } finally { |
129 | fLock.writeLock().unlock(); | |
e5083481 | 130 | } |
1a9cb076 AM |
131 | } |
132 | ||
133 | @Override | |
134 | public int size() { | |
135 | return Long.valueOf(fSize).intValue(); | |
136 | } | |
137 | ||
138 | @Override | |
139 | public boolean isEmpty() { | |
140 | return (fSize == 0); | |
26a6a7eb AM |
141 | } |
142 | ||
143 | @Override | |
1a9cb076 | 144 | public boolean contains(@Nullable Object o) { |
71e78f69 MK |
145 | fLock.readLock().lock(); |
146 | try { | |
1a9cb076 | 147 | return fStartTimesIndex.containsValue(o); |
71e78f69 MK |
148 | } finally { |
149 | fLock.readLock().unlock(); | |
150 | } | |
26a6a7eb AM |
151 | } |
152 | ||
1a9cb076 AM |
153 | @Override |
154 | public boolean containsAll(@Nullable Collection<?> c) { | |
155 | fLock.readLock().lock(); | |
156 | try { | |
157 | return fStartTimesIndex.values().containsAll(c); | |
158 | } finally { | |
159 | fLock.readLock().unlock(); | |
160 | } | |
161 | } | |
162 | ||
163 | @Override | |
164 | public Object[] toArray() { | |
165 | fLock.readLock().lock(); | |
166 | try { | |
df2597e0 | 167 | return fStartTimesIndex.values().toArray(); |
1a9cb076 AM |
168 | } finally { |
169 | fLock.readLock().unlock(); | |
170 | } | |
171 | } | |
172 | ||
173 | @Override | |
95bcb6c4 | 174 | public <T> T[] toArray(T[] a) { |
1a9cb076 AM |
175 | fLock.readLock().lock(); |
176 | try { | |
df2597e0 | 177 | return fStartTimesIndex.values().toArray(a); |
1a9cb076 AM |
178 | } finally { |
179 | fLock.readLock().unlock(); | |
180 | } | |
181 | } | |
182 | ||
183 | @Override | |
184 | public boolean remove(@Nullable Object o) { | |
185 | throw new UnsupportedOperationException(); | |
186 | } | |
187 | ||
188 | @Override | |
189 | public boolean addAll(@Nullable Collection<? extends E> c) { | |
190 | if (c == null) { | |
191 | throw new IllegalArgumentException(); | |
192 | } | |
193 | ||
194 | fLock.writeLock().lock(); | |
195 | try { | |
196 | boolean changed = false; | |
197 | for (E elem : c) { | |
198 | if (this.add(elem)) { | |
199 | changed = true; | |
200 | } | |
201 | } | |
202 | return changed; | |
203 | } finally { | |
204 | fLock.writeLock().unlock(); | |
205 | } | |
206 | } | |
207 | ||
208 | @Override | |
209 | public boolean removeAll(@Nullable Collection<?> c) { | |
210 | throw new UnsupportedOperationException(); | |
211 | } | |
212 | ||
213 | @Override | |
214 | public boolean retainAll(@Nullable Collection<?> c) { | |
215 | throw new UnsupportedOperationException(); | |
216 | } | |
217 | ||
218 | @Override | |
219 | public void clear() { | |
0f769d2b MK |
220 | fLock.writeLock().lock(); |
221 | try { | |
222 | fSize = 0; | |
223 | fEndTimesIndex.clear(); | |
224 | fStartTimesIndex.clear(); | |
225 | } finally { | |
226 | fLock.writeLock().unlock(); | |
227 | } | |
1a9cb076 AM |
228 | } |
229 | ||
230 | // ------------------------------------------------------------------------ | |
231 | // Methods added by ISegmentStore | |
232 | // ------------------------------------------------------------------------ | |
233 | ||
26a6a7eb | 234 | @Override |
1a9cb076 | 235 | public Iterable<E> getIntersectingElements(long position) { |
26a6a7eb AM |
236 | /* |
237 | * The intervals intersecting 't' are those whose 1) start time is | |
238 | * *lower* than 't' AND 2) end time is *higher* than 't'. | |
239 | */ | |
71e78f69 MK |
240 | fLock.readLock().lock(); |
241 | try { | |
1a9cb076 AM |
242 | Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values()); |
243 | Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values()); | |
71e78f69 MK |
244 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); |
245 | } finally { | |
246 | fLock.readLock().unlock(); | |
247 | } | |
26a6a7eb AM |
248 | } |
249 | ||
250 | @Override | |
1a9cb076 | 251 | public Iterable<E> getIntersectingElements(long start, long end) { |
71e78f69 MK |
252 | fLock.readLock().lock(); |
253 | try { | |
1a9cb076 AM |
254 | Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values()); |
255 | Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values()); | |
71e78f69 MK |
256 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); |
257 | } finally { | |
258 | fLock.readLock().unlock(); | |
259 | } | |
26a6a7eb AM |
260 | } |
261 | ||
262 | @Override | |
71e78f69 MK |
263 | public void dispose() { |
264 | fLock.writeLock().lock(); | |
265 | try { | |
266 | fStartTimesIndex.clear(); | |
267 | fEndTimesIndex.clear(); | |
268 | fSize = 0; | |
269 | } finally { | |
270 | fLock.writeLock().unlock(); | |
271 | } | |
26a6a7eb | 272 | } |
26a6a7eb | 273 | } |