Commit | Line | Data |
---|---|---|
aaa6f547 MK |
1 | /******************************************************************************* |
2 | * Copyright (c) 2016 Ericsson | |
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 | ||
664a3a81 | 10 | package org.eclipse.tracecompass.internal.segmentstore.core.arraylist; |
aaa6f547 MK |
11 | |
12 | import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; | |
13 | ||
14 | import java.util.ArrayList; | |
15 | import java.util.Collection; | |
2047fe04 | 16 | import java.util.Collections; |
aaa6f547 MK |
17 | import java.util.Comparator; |
18 | import java.util.Iterator; | |
19 | import java.util.List; | |
20 | import java.util.concurrent.locks.ReentrantLock; | |
21 | import java.util.stream.Collectors; | |
22 | ||
23 | import org.eclipse.jdt.annotation.NonNull; | |
24 | import org.eclipse.jdt.annotation.Nullable; | |
2047fe04 | 25 | import org.eclipse.tracecompass.segmentstore.core.BasicSegment; |
aaa6f547 MK |
26 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
27 | import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; | |
664a3a81 | 28 | import org.eclipse.tracecompass.segmentstore.core.SegmentComparators; |
aaa6f547 MK |
29 | |
30 | import com.google.common.collect.ImmutableList; | |
664a3a81 | 31 | import com.google.common.collect.Ordering; |
aaa6f547 MK |
32 | |
33 | /** | |
34 | * Implementation of an {@link ISegmentStore} using one in-memory | |
35 | * {@link ArrayList}. This relatively simple implementation holds everything in | |
36 | * memory, and as such cannot contain too much data. | |
37 | * | |
38 | * The LazyArrayListStore itself is {@link Iterable}, and its iteration order | |
39 | * will be by ascending order of start times. For segments with identical start | |
40 | * times, the secondary comparator will be the end time. If even those are | |
41 | * equal, it will defer to the segments' natural ordering ( | |
42 | * {@link ISegment#compareTo}). | |
43 | * | |
44 | * This structure sorts in a lazy way to allow faster insertions. However, if | |
45 | * the structure is out of order, the next read (getting intersecting elements, | |
46 | * iterating...) will perform a sort. It may have inconsistent performance, but | |
47 | * should be faster at building when receiving shuffled datasets than the | |
48 | * {@link ArrayListStore}. | |
49 | * | |
50 | * Removal operations are not supported. | |
51 | * | |
52 | * @param <E> | |
53 | * The type of segment held in this store | |
54 | * | |
55 | * @author Matthew Khouzam | |
56 | */ | |
57 | public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegmentStore<E> { | |
58 | ||
59 | private static final String ERROR_MESSAGE = "Cannot remove from a segment store"; //$NON-NLS-1$ | |
60 | ||
664a3a81 LPD |
61 | private final Comparator<E> COMPARATOR = Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR) |
62 | .compound(SegmentComparators.INTERVAL_END_COMPARATOR); | |
aaa6f547 MK |
63 | |
64 | private final ReentrantLock fLock = new ReentrantLock(false); | |
65 | ||
664a3a81 | 66 | private final List<E> fStore = new ArrayList<>(); |
aaa6f547 MK |
67 | |
68 | private @Nullable transient Iterable<E> fLastSnapshot = null; | |
69 | ||
70 | private volatile boolean fDirty = false; | |
71 | ||
72 | /** | |
73 | * Constructor | |
74 | */ | |
75 | public LazyArrayListStore() { | |
76 | // do nothing | |
77 | } | |
78 | ||
79 | /** | |
80 | * Constructor | |
81 | * | |
82 | * @param array | |
83 | * an array of elements to wrap in the segment store | |
84 | * | |
85 | */ | |
86 | public LazyArrayListStore(Object[] array) { | |
87 | for (int i = 0; i < array.length; i++) { | |
88 | if (array[i] instanceof ISegment) { | |
89 | E element = (E) array[i]; | |
90 | setDirtyIfNeeded(element); | |
91 | fStore.add(element); | |
92 | } | |
93 | } | |
94 | if (fDirty) { | |
95 | sortStore(); | |
96 | } | |
97 | } | |
98 | ||
99 | private void setDirtyIfNeeded(@NonNull E value) { | |
100 | if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) { | |
101 | fDirty = true; | |
102 | } | |
103 | } | |
104 | // ------------------------------------------------------------------------ | |
105 | // Methods from Collection | |
106 | // ------------------------------------------------------------------------ | |
107 | ||
108 | @Override | |
109 | public Iterator<E> iterator() { | |
110 | fLock.lock(); | |
111 | try { | |
112 | if (fDirty) { | |
113 | sortStore(); | |
114 | } | |
115 | Iterable<E> lastSnapshot = fLastSnapshot; | |
116 | if (lastSnapshot == null) { | |
117 | lastSnapshot = ImmutableList.copyOf(fStore); | |
118 | fLastSnapshot = lastSnapshot; | |
119 | } | |
120 | return checkNotNull(lastSnapshot.iterator()); | |
121 | } finally { | |
122 | fLock.unlock(); | |
123 | } | |
124 | } | |
125 | ||
126 | /** | |
127 | * DO NOT CALL FROM OUTSIDE OF A LOCK! | |
128 | */ | |
129 | private void sortStore() { | |
130 | fStore.sort(COMPARATOR); | |
131 | fDirty = false; | |
132 | } | |
133 | ||
134 | @Override | |
135 | public boolean add(@Nullable E val) { | |
136 | if (val == null) { | |
137 | throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$ | |
138 | } | |
139 | ||
140 | fLock.lock(); | |
141 | try { | |
142 | setDirtyIfNeeded(val); | |
143 | fStore.add(val); | |
144 | fLastSnapshot = null; | |
145 | return true; | |
146 | } finally { | |
147 | fLock.unlock(); | |
148 | } | |
149 | } | |
150 | ||
151 | @Override | |
152 | public int size() { | |
524fb56d MK |
153 | fLock.lock(); |
154 | try { | |
155 | return fStore.size(); | |
156 | } finally { | |
157 | fLock.unlock(); | |
158 | } | |
aaa6f547 MK |
159 | } |
160 | ||
161 | @Override | |
162 | public boolean isEmpty() { | |
163 | fLock.lock(); | |
164 | try { | |
165 | return fStore.isEmpty(); | |
166 | } finally { | |
167 | fLock.unlock(); | |
168 | } | |
169 | } | |
170 | ||
171 | @Override | |
172 | public boolean contains(@Nullable Object o) { | |
173 | fLock.lock(); | |
174 | try { | |
175 | return fStore.contains(o); | |
176 | } finally { | |
177 | fLock.unlock(); | |
178 | } | |
179 | } | |
180 | ||
181 | @Override | |
182 | public boolean containsAll(@Nullable Collection<?> c) { | |
183 | fLock.lock(); | |
184 | try { | |
185 | return fStore.containsAll(c); | |
186 | } finally { | |
187 | fLock.unlock(); | |
188 | } | |
189 | } | |
190 | ||
191 | @Override | |
192 | public Object[] toArray() { | |
193 | fLock.lock(); | |
194 | try { | |
195 | if (fDirty) { | |
196 | sortStore(); | |
197 | } | |
198 | return fStore.toArray(); | |
199 | } finally { | |
200 | fLock.unlock(); | |
201 | } | |
202 | } | |
203 | ||
204 | @Override | |
205 | public <T> T[] toArray(T[] a) { | |
206 | fLock.lock(); | |
207 | try { | |
208 | if (fDirty) { | |
209 | sortStore(); | |
210 | } | |
211 | return fStore.toArray(a); | |
212 | } finally { | |
213 | fLock.unlock(); | |
214 | } | |
215 | } | |
216 | ||
217 | @Override | |
218 | public boolean addAll(@Nullable Collection<? extends E> c) { | |
219 | if (c == null) { | |
220 | throw new IllegalArgumentException(); | |
221 | } | |
222 | ||
223 | fLock.lock(); | |
224 | try { | |
225 | boolean changed = false; | |
226 | for (E elem : c) { | |
227 | if (add(elem)) { | |
228 | changed = true; | |
229 | } | |
230 | } | |
231 | return changed; | |
232 | } finally { | |
233 | fLock.unlock(); | |
234 | } | |
235 | } | |
236 | ||
237 | @Override | |
238 | public boolean removeAll(@Nullable Collection<?> c) { | |
239 | throw new UnsupportedOperationException(ERROR_MESSAGE); | |
240 | } | |
241 | ||
242 | @Override | |
243 | public boolean retainAll(@Nullable Collection<?> c) { | |
244 | throw new UnsupportedOperationException(ERROR_MESSAGE); | |
245 | } | |
246 | ||
247 | @Override | |
248 | public boolean remove(@Nullable Object o) { | |
249 | throw new UnsupportedOperationException(ERROR_MESSAGE); | |
250 | } | |
251 | ||
252 | @Override | |
253 | public void clear() { | |
254 | fLock.lock(); | |
255 | try { | |
256 | fStore.clear(); | |
257 | fLastSnapshot = null; | |
258 | fDirty = false; | |
259 | } finally { | |
260 | fLock.unlock(); | |
261 | } | |
262 | } | |
263 | ||
264 | // ------------------------------------------------------------------------ | |
265 | // Methods added by ISegmentStore | |
266 | // ------------------------------------------------------------------------ | |
267 | ||
268 | @Override | |
269 | public Iterable<E> getIntersectingElements(long position) { | |
270 | fLock.lock(); | |
271 | if (fDirty) { | |
272 | sortStore(); | |
273 | } | |
274 | /* | |
275 | * The intervals intersecting 't' are those whose 1) start time is | |
276 | * *lower* than 't' AND 2) end time is *higher* than 't'. | |
277 | */ | |
278 | try { | |
2047fe04 LPD |
279 | /* |
280 | * as fStore is sorted by start then end times, restrict sub array | |
281 | * to elements whose start times <= t as stream.filter won't do it. | |
282 | */ | |
283 | int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE)); | |
284 | index = (index >= 0) ? index : -index - 1; | |
285 | return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList()); | |
aaa6f547 MK |
286 | } finally { |
287 | fLock.unlock(); | |
288 | } | |
289 | } | |
290 | ||
291 | @Override | |
292 | public Iterable<E> getIntersectingElements(long start, long end) { | |
293 | fLock.lock(); | |
294 | if (fDirty) { | |
295 | sortStore(); | |
296 | } | |
297 | try { | |
2047fe04 LPD |
298 | int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE)); |
299 | index = (index >= 0) ? index : -index - 1; | |
300 | return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList()); | |
aaa6f547 MK |
301 | } finally { |
302 | fLock.unlock(); | |
303 | } | |
304 | } | |
305 | ||
306 | @Override | |
307 | public void dispose() { | |
308 | fLock.lock(); | |
309 | try { | |
310 | fStore.clear(); | |
311 | fDirty = false; | |
312 | } finally { | |
313 | fLock.unlock(); | |
314 | } | |
315 | } | |
316 | } |