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 | ||
664a3a81 LPD |
59 | private final Comparator<E> COMPARATOR = Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR) |
60 | .compound(SegmentComparators.INTERVAL_END_COMPARATOR); | |
aaa6f547 MK |
61 | |
62 | private final ReentrantLock fLock = new ReentrantLock(false); | |
63 | ||
664a3a81 | 64 | private final List<E> fStore = new ArrayList<>(); |
aaa6f547 MK |
65 | |
66 | private @Nullable transient Iterable<E> fLastSnapshot = null; | |
67 | ||
68 | private volatile boolean fDirty = false; | |
69 | ||
70 | /** | |
71 | * Constructor | |
72 | */ | |
73 | public LazyArrayListStore() { | |
74 | // do nothing | |
75 | } | |
76 | ||
77 | /** | |
78 | * Constructor | |
79 | * | |
80 | * @param array | |
81 | * an array of elements to wrap in the segment store | |
82 | * | |
83 | */ | |
84 | public LazyArrayListStore(Object[] array) { | |
85 | for (int i = 0; i < array.length; i++) { | |
86 | if (array[i] instanceof ISegment) { | |
87 | E element = (E) array[i]; | |
88 | setDirtyIfNeeded(element); | |
89 | fStore.add(element); | |
90 | } | |
91 | } | |
92 | if (fDirty) { | |
93 | sortStore(); | |
94 | } | |
95 | } | |
96 | ||
97 | private void setDirtyIfNeeded(@NonNull E value) { | |
98 | if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) { | |
99 | fDirty = true; | |
100 | } | |
101 | } | |
102 | // ------------------------------------------------------------------------ | |
103 | // Methods from Collection | |
104 | // ------------------------------------------------------------------------ | |
105 | ||
106 | @Override | |
107 | public Iterator<E> iterator() { | |
108 | fLock.lock(); | |
109 | try { | |
110 | if (fDirty) { | |
111 | sortStore(); | |
112 | } | |
113 | Iterable<E> lastSnapshot = fLastSnapshot; | |
114 | if (lastSnapshot == null) { | |
115 | lastSnapshot = ImmutableList.copyOf(fStore); | |
116 | fLastSnapshot = lastSnapshot; | |
117 | } | |
118 | return checkNotNull(lastSnapshot.iterator()); | |
119 | } finally { | |
120 | fLock.unlock(); | |
121 | } | |
122 | } | |
123 | ||
124 | /** | |
125 | * DO NOT CALL FROM OUTSIDE OF A LOCK! | |
126 | */ | |
127 | private void sortStore() { | |
128 | fStore.sort(COMPARATOR); | |
129 | fDirty = false; | |
130 | } | |
131 | ||
132 | @Override | |
133 | public boolean add(@Nullable E val) { | |
134 | if (val == null) { | |
135 | throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$ | |
136 | } | |
137 | ||
138 | fLock.lock(); | |
139 | try { | |
140 | setDirtyIfNeeded(val); | |
141 | fStore.add(val); | |
142 | fLastSnapshot = null; | |
143 | return true; | |
144 | } finally { | |
145 | fLock.unlock(); | |
146 | } | |
147 | } | |
148 | ||
149 | @Override | |
150 | public int size() { | |
524fb56d MK |
151 | fLock.lock(); |
152 | try { | |
153 | return fStore.size(); | |
154 | } finally { | |
155 | fLock.unlock(); | |
156 | } | |
aaa6f547 MK |
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 | ||
aaa6f547 MK |
235 | @Override |
236 | public void clear() { | |
237 | fLock.lock(); | |
238 | try { | |
239 | fStore.clear(); | |
240 | fLastSnapshot = null; | |
241 | fDirty = false; | |
242 | } finally { | |
243 | fLock.unlock(); | |
244 | } | |
245 | } | |
246 | ||
247 | // ------------------------------------------------------------------------ | |
248 | // Methods added by ISegmentStore | |
249 | // ------------------------------------------------------------------------ | |
250 | ||
aaa6f547 MK |
251 | @Override |
252 | public Iterable<E> getIntersectingElements(long start, long end) { | |
253 | fLock.lock(); | |
254 | if (fDirty) { | |
255 | sortStore(); | |
256 | } | |
257 | try { | |
2047fe04 LPD |
258 | int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE)); |
259 | index = (index >= 0) ? index : -index - 1; | |
260 | return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList()); | |
aaa6f547 MK |
261 | } finally { |
262 | fLock.unlock(); | |
263 | } | |
264 | } | |
265 | ||
266 | @Override | |
267 | public void dispose() { | |
268 | fLock.lock(); | |
269 | try { | |
270 | fStore.clear(); | |
271 | fDirty = false; | |
272 | } finally { | |
273 | fLock.unlock(); | |
274 | } | |
275 | } | |
276 | } |