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 | |
4dafe201 | 23 | import org.eclipse.jdt.annotation.Nullable; |
26a6a7eb AM |
24 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
25 | import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; | |
e5083481 | 26 | import org.eclipse.tracecompass.segmentstore.core.SegmentComparators; |
26a6a7eb | 27 | |
4dafe201 | 28 | import com.google.common.collect.ImmutableList; |
26a6a7eb | 29 | import com.google.common.collect.Iterables; |
e5083481 | 30 | import com.google.common.collect.Ordering; |
26a6a7eb AM |
31 | import com.google.common.collect.Sets; |
32 | import com.google.common.collect.TreeMultimap; | |
33 | ||
34 | /** | |
35 | * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s. | |
36 | * This relatively simple implementation holds everything in memory, and as such | |
37 | * cannot contain too much data. | |
38 | * | |
e5083481 PT |
39 | * The TreeMapStore itself is Iterable, and its iteration order will be by |
40 | * ascending order of start times. For segments with identical start times, the | |
41 | * secondary comparator will be the end time. If even those are equal, it will | |
42 | * defer to the segments' natural ordering ({@link ISegment#compareTo}). | |
43 | * | |
44 | * The store's tree maps will not accept duplicate key-value pairs, which means | |
45 | * that if you want several segments with the same start and end times, make | |
46 | * sure their compareTo() differentiates them. | |
47 | * | |
1a9cb076 AM |
48 | * Removal operations are not supported. |
49 | * | |
50 | * @param <E> | |
e5083481 | 51 | * The type of segment held in this store |
26a6a7eb AM |
52 | * |
53 | * @author Alexandre Montplaisir | |
54 | */ | |
1a9cb076 | 55 | public class TreeMapStore<E extends ISegment> implements ISegmentStore<E> { |
26a6a7eb | 56 | |
71e78f69 MK |
57 | private final ReadWriteLock fLock = new ReentrantReadWriteLock(false); |
58 | ||
1a9cb076 AM |
59 | private final TreeMultimap<Long, E> fStartTimesIndex; |
60 | private final TreeMultimap<Long, E> fEndTimesIndex; | |
26a6a7eb | 61 | |
1a9cb076 | 62 | private volatile long fSize; |
26a6a7eb | 63 | |
1a9cb076 | 64 | private @Nullable transient Iterable<E> fLastSnapshot = null; |
4dafe201 | 65 | |
26a6a7eb | 66 | /** |
e5083481 | 67 | * Constructor |
26a6a7eb AM |
68 | */ |
69 | public TreeMapStore() { | |
e5083481 PT |
70 | /* |
71 | * For the start times index, the "key comparator" will compare the | |
72 | * start times as longs directly. This is the primary comparator for its | |
73 | * tree map. | |
74 | * | |
75 | * The secondary "value" comparator will check the end times first, and | |
76 | * in the event of a tie, defer to the ISegment's Comparable | |
77 | * implementation, a.k.a. its natural ordering. | |
78 | * | |
79 | * The same is done for the end times index, but swapping the first two | |
80 | * comparators instead. | |
81 | */ | |
1a9cb076 | 82 | fStartTimesIndex = checkNotNull(TreeMultimap.<Long, E> create( |
e5083481 PT |
83 | SegmentComparators.LONG_COMPARATOR, |
84 | Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural()))); | |
85 | ||
1a9cb076 | 86 | fEndTimesIndex = checkNotNull(TreeMultimap.<Long, E> create( |
e5083481 PT |
87 | SegmentComparators.LONG_COMPARATOR, |
88 | Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural()))); | |
89 | ||
26a6a7eb AM |
90 | fSize = 0; |
91 | } | |
92 | ||
1a9cb076 AM |
93 | // ------------------------------------------------------------------------ |
94 | // Methods from Collection | |
95 | // ------------------------------------------------------------------------ | |
96 | ||
26a6a7eb | 97 | @Override |
1a9cb076 | 98 | public Iterator<E> iterator() { |
4dafe201 MK |
99 | fLock.readLock().lock(); |
100 | try { | |
1a9cb076 | 101 | Iterable<E> lastSnapshot = fLastSnapshot; |
4dafe201 MK |
102 | if (lastSnapshot == null) { |
103 | lastSnapshot = checkNotNull(ImmutableList.copyOf(fStartTimesIndex.values())); | |
104 | fLastSnapshot = lastSnapshot; | |
105 | } | |
106 | return checkNotNull(lastSnapshot.iterator()); | |
107 | } finally { | |
108 | fLock.readLock().unlock(); | |
109 | } | |
26a6a7eb AM |
110 | } |
111 | ||
112 | @Override | |
1a9cb076 AM |
113 | public boolean add(@Nullable E val) { |
114 | if (val == null) { | |
115 | throw new IllegalArgumentException(); | |
116 | } | |
117 | ||
71e78f69 MK |
118 | fLock.writeLock().lock(); |
119 | try { | |
120 | if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) { | |
121 | fEndTimesIndex.put(Long.valueOf(val.getEnd()), val); | |
122 | fSize++; | |
4dafe201 | 123 | fLastSnapshot = null; |
8b246d45 | 124 | return true; |
71e78f69 | 125 | } |
8b246d45 | 126 | return false; |
71e78f69 MK |
127 | } finally { |
128 | fLock.writeLock().unlock(); | |
e5083481 | 129 | } |
1a9cb076 AM |
130 | } |
131 | ||
132 | @Override | |
133 | public int size() { | |
134 | return Long.valueOf(fSize).intValue(); | |
135 | } | |
136 | ||
137 | @Override | |
138 | public boolean isEmpty() { | |
139 | return (fSize == 0); | |
26a6a7eb AM |
140 | } |
141 | ||
142 | @Override | |
1a9cb076 | 143 | public boolean contains(@Nullable Object o) { |
71e78f69 MK |
144 | fLock.readLock().lock(); |
145 | try { | |
1a9cb076 | 146 | return fStartTimesIndex.containsValue(o); |
71e78f69 MK |
147 | } finally { |
148 | fLock.readLock().unlock(); | |
149 | } | |
26a6a7eb AM |
150 | } |
151 | ||
1a9cb076 AM |
152 | |
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 { | |
167 | return checkNotNull(fStartTimesIndex.values().toArray()); | |
168 | } finally { | |
169 | fLock.readLock().unlock(); | |
170 | } | |
171 | } | |
172 | ||
173 | @Override | |
4c4e2816 | 174 | public <T> T[] toArray(T @Nullable[] a) { |
1a9cb076 AM |
175 | fLock.readLock().lock(); |
176 | try { | |
177 | return checkNotNull(fStartTimesIndex.values().toArray(a)); | |
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() { | |
220 | throw new UnsupportedOperationException(); | |
221 | } | |
222 | ||
223 | // ------------------------------------------------------------------------ | |
224 | // Methods added by ISegmentStore | |
225 | // ------------------------------------------------------------------------ | |
226 | ||
26a6a7eb | 227 | @Override |
1a9cb076 | 228 | public Iterable<E> getIntersectingElements(long position) { |
26a6a7eb AM |
229 | /* |
230 | * The intervals intersecting 't' are those whose 1) start time is | |
231 | * *lower* than 't' AND 2) end time is *higher* than 't'. | |
232 | */ | |
71e78f69 MK |
233 | fLock.readLock().lock(); |
234 | try { | |
1a9cb076 AM |
235 | Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values()); |
236 | Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values()); | |
71e78f69 MK |
237 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); |
238 | } finally { | |
239 | fLock.readLock().unlock(); | |
240 | } | |
26a6a7eb AM |
241 | } |
242 | ||
243 | @Override | |
1a9cb076 | 244 | public Iterable<E> getIntersectingElements(long start, long end) { |
71e78f69 MK |
245 | fLock.readLock().lock(); |
246 | try { | |
1a9cb076 AM |
247 | Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values()); |
248 | Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values()); | |
71e78f69 MK |
249 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); |
250 | } finally { | |
251 | fLock.readLock().unlock(); | |
252 | } | |
26a6a7eb AM |
253 | } |
254 | ||
255 | @Override | |
71e78f69 MK |
256 | public void dispose() { |
257 | fLock.writeLock().lock(); | |
258 | try { | |
259 | fStartTimesIndex.clear(); | |
260 | fEndTimesIndex.clear(); | |
261 | fSize = 0; | |
262 | } finally { | |
263 | fLock.writeLock().unlock(); | |
264 | } | |
26a6a7eb | 265 | } |
26a6a7eb | 266 | } |