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