Commit | Line | Data |
---|---|---|
3dde9149 | 1 | /******************************************************************************* |
664a3a81 | 2 | * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others. |
3dde9149 MK |
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 | |
664a3a81 LPD |
8 | * |
9 | * Contributors: | |
10 | * Alexandre Montplaisir - Initial API and implementation | |
3dde9149 MK |
11 | *******************************************************************************/ |
12 | ||
664a3a81 | 13 | package org.eclipse.tracecompass.internal.segmentstore.core.treemap; |
3dde9149 MK |
14 | |
15 | import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; | |
16 | ||
3dde9149 | 17 | import java.util.Collection; |
3dde9149 | 18 | import java.util.Iterator; |
664a3a81 | 19 | import java.util.TreeMap; |
3dde9149 MK |
20 | import java.util.concurrent.locks.ReadWriteLock; |
21 | import java.util.concurrent.locks.ReentrantReadWriteLock; | |
3dde9149 MK |
22 | |
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; | |
664a3a81 | 27 | import org.eclipse.tracecompass.segmentstore.core.SegmentComparators; |
3dde9149 MK |
28 | |
29 | import com.google.common.collect.ImmutableList; | |
664a3a81 LPD |
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; | |
3dde9149 MK |
34 | |
35 | /** | |
664a3a81 LPD |
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. | |
3dde9149 | 39 | * |
664a3a81 LPD |
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}). | |
3dde9149 MK |
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 | * | |
49 | * Removal operations are not supported. | |
50 | * | |
51 | * @param <E> | |
52 | * The type of segment held in this store | |
53 | * | |
664a3a81 | 54 | * @author Alexandre Montplaisir |
3dde9149 | 55 | */ |
664a3a81 | 56 | public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore<E> { |
3dde9149 MK |
57 | |
58 | private final ReadWriteLock fLock = new ReentrantReadWriteLock(false); | |
59 | ||
664a3a81 LPD |
60 | private final TreeMultimap<Long, E> fStartTimesIndex; |
61 | private final TreeMultimap<Long, E> fEndTimesIndex; | |
62 | ||
63 | private volatile long fSize; | |
3dde9149 MK |
64 | |
65 | private @Nullable transient Iterable<E> fLastSnapshot = null; | |
66 | ||
67 | /** | |
68 | * Constructor | |
69 | */ | |
664a3a81 LPD |
70 | public TreeMapStore() { |
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 | */ | |
83 | fStartTimesIndex = TreeMultimap.create( | |
84 | SegmentComparators.LONG_COMPARATOR, | |
85 | Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())); | |
3dde9149 | 86 | |
664a3a81 LPD |
87 | fEndTimesIndex = TreeMultimap.create( |
88 | SegmentComparators.LONG_COMPARATOR, | |
89 | Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())); | |
90 | ||
91 | fSize = 0; | |
aa9082f9 | 92 | } |
664a3a81 | 93 | |
3dde9149 MK |
94 | // ------------------------------------------------------------------------ |
95 | // Methods from Collection | |
96 | // ------------------------------------------------------------------------ | |
97 | ||
98 | @Override | |
99 | public Iterator<E> iterator() { | |
100 | fLock.readLock().lock(); | |
101 | try { | |
102 | Iterable<E> lastSnapshot = fLastSnapshot; | |
103 | if (lastSnapshot == null) { | |
664a3a81 | 104 | lastSnapshot = ImmutableList.copyOf(fStartTimesIndex.values()); |
3dde9149 MK |
105 | fLastSnapshot = lastSnapshot; |
106 | } | |
107 | return checkNotNull(lastSnapshot.iterator()); | |
108 | } finally { | |
109 | fLock.readLock().unlock(); | |
110 | } | |
111 | } | |
112 | ||
113 | @Override | |
114 | public boolean add(@Nullable E val) { | |
115 | if (val == null) { | |
664a3a81 | 116 | throw new IllegalArgumentException(); |
3dde9149 MK |
117 | } |
118 | ||
119 | fLock.writeLock().lock(); | |
120 | try { | |
664a3a81 LPD |
121 | if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) { |
122 | fEndTimesIndex.put(Long.valueOf(val.getEnd()), val); | |
123 | fSize++; | |
124 | fLastSnapshot = null; | |
125 | return true; | |
126 | } | |
127 | return false; | |
3dde9149 MK |
128 | } finally { |
129 | fLock.writeLock().unlock(); | |
130 | } | |
131 | } | |
132 | ||
133 | @Override | |
134 | public int size() { | |
664a3a81 | 135 | return Long.valueOf(fSize).intValue(); |
3dde9149 MK |
136 | } |
137 | ||
138 | @Override | |
139 | public boolean isEmpty() { | |
664a3a81 | 140 | return (fSize == 0); |
3dde9149 MK |
141 | } |
142 | ||
143 | @Override | |
144 | public boolean contains(@Nullable Object o) { | |
145 | fLock.readLock().lock(); | |
146 | try { | |
664a3a81 | 147 | return fStartTimesIndex.containsValue(o); |
3dde9149 MK |
148 | } finally { |
149 | fLock.readLock().unlock(); | |
150 | } | |
151 | } | |
152 | ||
153 | @Override | |
154 | public boolean containsAll(@Nullable Collection<?> c) { | |
155 | fLock.readLock().lock(); | |
156 | try { | |
664a3a81 | 157 | return fStartTimesIndex.values().containsAll(c); |
3dde9149 MK |
158 | } finally { |
159 | fLock.readLock().unlock(); | |
160 | } | |
161 | } | |
162 | ||
163 | @Override | |
164 | public Object[] toArray() { | |
165 | fLock.readLock().lock(); | |
166 | try { | |
664a3a81 | 167 | return fStartTimesIndex.values().toArray(); |
3dde9149 MK |
168 | } finally { |
169 | fLock.readLock().unlock(); | |
170 | } | |
171 | } | |
172 | ||
173 | @Override | |
174 | public <T> T[] toArray(T[] a) { | |
175 | fLock.readLock().lock(); | |
176 | try { | |
664a3a81 | 177 | return fStartTimesIndex.values().toArray(a); |
3dde9149 MK |
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 | fLock.writeLock().lock(); | |
221 | try { | |
664a3a81 LPD |
222 | fSize = 0; |
223 | fEndTimesIndex.clear(); | |
224 | fStartTimesIndex.clear(); | |
3dde9149 MK |
225 | } finally { |
226 | fLock.writeLock().unlock(); | |
227 | } | |
228 | } | |
229 | ||
230 | // ------------------------------------------------------------------------ | |
231 | // Methods added by ISegmentStore | |
232 | // ------------------------------------------------------------------------ | |
233 | ||
3dde9149 MK |
234 | @Override |
235 | public Iterable<E> getIntersectingElements(long start, long end) { | |
236 | fLock.readLock().lock(); | |
237 | try { | |
664a3a81 LPD |
238 | Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values()); |
239 | Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values()); | |
240 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); | |
3dde9149 MK |
241 | } finally { |
242 | fLock.readLock().unlock(); | |
243 | } | |
244 | } | |
245 | ||
246 | @Override | |
247 | public void dispose() { | |
248 | fLock.writeLock().lock(); | |
249 | try { | |
664a3a81 LPD |
250 | fStartTimesIndex.clear(); |
251 | fEndTimesIndex.clear(); | |
252 | fSize = 0; | |
3dde9149 MK |
253 | } finally { |
254 | fLock.writeLock().unlock(); | |
255 | } | |
256 | } | |
257 | } |