Commit | Line | Data |
---|---|---|
866e5b51 | 1 | /******************************************************************************* |
60ae41e1 | 2 | * Copyright (c) 2011, 2014 Ericsson, Ecole Polytechnique de Montreal and others |
866e5b51 FC |
3 | * |
4 | * All rights reserved. This program and the accompanying materials are made | |
5 | * available under the terms of the Eclipse Public License v1.0 which | |
6 | * accompanies this distribution, and is available at | |
7 | * http://www.eclipse.org/legal/epl-v10.html | |
8 | * | |
9 | * Contributors: Matthew Khouzam - Initial API and implementation | |
10 | * Contributors: Simon Marchi - Initial API and implementation | |
d68f46c2 EB |
11 | * Contributors: Etienne Bergeron <etienne.bergeron@gmail.com> |
12 | * Contributors: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
866e5b51 FC |
13 | *******************************************************************************/ |
14 | ||
f357bcd4 | 15 | package org.eclipse.tracecompass.internal.ctf.core.trace; |
866e5b51 | 16 | |
3f02ac64 | 17 | import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; |
c1d0f6ca | 18 | |
bf7f1af6 | 19 | import java.io.Serializable; |
3f02ac64 MK |
20 | import java.util.ArrayList; |
21 | import java.util.Collection; | |
22 | import java.util.Collections; | |
c1d0f6ca | 23 | import java.util.Comparator; |
3f02ac64 | 24 | import java.util.List; |
866e5b51 | 25 | import java.util.ListIterator; |
bf7f1af6 | 26 | import java.util.TreeSet; |
866e5b51 | 27 | |
3f02ac64 | 28 | import org.eclipse.jdt.annotation.NonNull; |
680f9173 | 29 | import org.eclipse.tracecompass.ctf.core.CTFException; |
1d92f045 | 30 | import org.eclipse.tracecompass.ctf.core.trace.ICTFPacketDescriptor; |
ce2388e0 | 31 | |
866e5b51 FC |
32 | /** |
33 | * <b><u>StreamInputPacketIndex</u></b> | |
34 | * <p> | |
3f02ac64 MK |
35 | * This is a data structure containing entries, you may append to this and read |
36 | * it. It is not thread safe. | |
866e5b51 FC |
37 | */ |
38 | public class StreamInputPacketIndex { | |
39 | ||
40 | // ------------------------------------------------------------------------ | |
41 | // Attributes | |
42 | // ------------------------------------------------------------------------ | |
43 | ||
44 | /** | |
45 | * Entries of the index. They are sorted by increasing begin timestamp. | |
46 | * index builder. | |
47 | */ | |
1d92f045 | 48 | private final List<ICTFPacketDescriptor> fEntries = new ArrayList<>(); |
866e5b51 FC |
49 | |
50 | // ------------------------------------------------------------------------ | |
3f02ac64 | 51 | // Operations |
866e5b51 FC |
52 | // ------------------------------------------------------------------------ |
53 | ||
9ac2eb62 | 54 | /** |
3f02ac64 MK |
55 | * Returns the number of elements in this data structure. If this data |
56 | * structure contains more than {@code Integer.MAX_VALUE} elements, returns | |
57 | * {@code Integer.MAX_VALUE}. | |
b73145e2 | 58 | * |
3f02ac64 | 59 | * @return the number of elements in this data structure |
9ac2eb62 | 60 | */ |
3f02ac64 MK |
61 | public int size() { |
62 | return fEntries.size(); | |
866e5b51 FC |
63 | } |
64 | ||
9ac2eb62 | 65 | /** |
3f02ac64 | 66 | * Returns {@code true} if this data structure contains no elements. |
b73145e2 | 67 | * |
3f02ac64 | 68 | * @return {@code true} if this data structure contains no elements |
9ac2eb62 | 69 | */ |
3f02ac64 MK |
70 | public boolean isEmpty() { |
71 | return fEntries.isEmpty(); | |
866e5b51 FC |
72 | } |
73 | ||
9ac2eb62 | 74 | /** |
3f02ac64 MK |
75 | * Adds a collection of entries to the index, the entries must be sorted. |
76 | * | |
77 | * @param preParsedIndex | |
78 | * the pre-parsed index file | |
b73145e2 | 79 | * |
680f9173 | 80 | * @throws CTFException |
3f02ac64 | 81 | * If there was a problem reading the entry |
9ac2eb62 | 82 | */ |
1d92f045 | 83 | public void appendAll(Collection<ICTFPacketDescriptor> preParsedIndex) |
680f9173 | 84 | throws CTFException { |
1d92f045 | 85 | for (ICTFPacketDescriptor sipie : preParsedIndex) { |
3f02ac64 MK |
86 | append(checkNotNull(sipie)); |
87 | } | |
866e5b51 FC |
88 | } |
89 | ||
866e5b51 | 90 | /** |
3f02ac64 | 91 | * Appends the specified element to the end of this data structure |
866e5b51 FC |
92 | * |
93 | * @param entry | |
3f02ac64 MK |
94 | * element to be appended to this index, cannot be null |
95 | * @return {@code true} (as specified by {@link Collection#add}) | |
680f9173 | 96 | * @throws CTFException |
be6df2d8 | 97 | * If there was a problem reading the entry |
866e5b51 | 98 | */ |
1d92f045 | 99 | public boolean append(@NonNull ICTFPacketDescriptor entry) |
680f9173 | 100 | throws CTFException { |
866e5b51 | 101 | |
ecb12461 | 102 | /* Validate consistent entry. */ |
ce2388e0 | 103 | if (entry.getTimestampBegin() > entry.getTimestampEnd()) { |
680f9173 | 104 | throw new CTFException("Packet begin timestamp is after end timestamp"); //$NON-NLS-1$ |
866e5b51 FC |
105 | } |
106 | ||
3f02ac64 MK |
107 | /* |
108 | * Validate entries are inserted in monotonic increasing timestamp | |
109 | * order. | |
110 | */ | |
111 | if (!fEntries.isEmpty() && (entry.getTimestampBegin() < lastElement().getTimestampBegin())) { | |
680f9173 | 112 | throw new CTFException("Packets begin timestamp decreasing"); //$NON-NLS-1$ |
866e5b51 | 113 | } |
3f02ac64 MK |
114 | |
115 | fEntries.add(entry); | |
116 | return true; | |
866e5b51 FC |
117 | } |
118 | ||
119 | /** | |
3f02ac64 MK |
120 | * Returns the first PacketIndexEntry that could include the timestamp, that |
121 | * is the last packet with a begin timestamp smaller than the given | |
122 | * timestamp. | |
866e5b51 FC |
123 | * |
124 | * @param timestamp | |
125 | * The timestamp to look for. | |
126 | * @return The StreamInputPacketEntry that corresponds to the packet that | |
127 | * includes the given timestamp. | |
128 | */ | |
1d92f045 | 129 | public ListIterator<ICTFPacketDescriptor> search(final long timestamp) { |
866e5b51 FC |
130 | /* |
131 | * Start with min and max covering all the elements. | |
132 | */ | |
3f02ac64 | 133 | int max = fEntries.size() - 1; |
866e5b51 FC |
134 | int min = 0; |
135 | ||
136 | int guessI; | |
1d92f045 | 137 | ICTFPacketDescriptor guessEntry = null; |
866e5b51 | 138 | |
4a110860 AM |
139 | /* |
140 | * If the index is empty, return the iterator at the very beginning. | |
141 | */ | |
3f02ac64 MK |
142 | if (isEmpty()) { |
143 | return fEntries.listIterator(); | |
4a110860 AM |
144 | } |
145 | ||
866e5b51 FC |
146 | if (timestamp < 0) { |
147 | throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$ | |
148 | } | |
149 | ||
d68f46c2 | 150 | /* Binary search */ |
866e5b51 FC |
151 | for (;;) { |
152 | /* | |
d68f46c2 | 153 | * Guess in the middle of min and max. |
866e5b51 | 154 | */ |
d68f46c2 | 155 | guessI = min + ((max - min) / 2); |
3f02ac64 | 156 | guessEntry = fEntries.get(guessI); |
866e5b51 FC |
157 | |
158 | /* | |
159 | * If we reached the point where we focus on a single packet, our | |
160 | * search is done. | |
161 | */ | |
162 | if (min == max) { | |
163 | break; | |
164 | } | |
165 | ||
d68f46c2 | 166 | if (timestamp <= guessEntry.getTimestampEnd()) { |
866e5b51 | 167 | /* |
3f02ac64 MK |
168 | * If the timestamp is lower or equal to the end of the guess |
169 | * packet, then the guess packet becomes the new inclusive max. | |
866e5b51 | 170 | */ |
d68f46c2 EB |
171 | max = guessI; |
172 | } else { | |
866e5b51 | 173 | /* |
3f02ac64 MK |
174 | * If the timestamp is greater than the end of the guess packet, |
175 | * then the new inclusive min is the packet after the guess | |
176 | * packet. | |
866e5b51 | 177 | */ |
d68f46c2 | 178 | min = guessI + 1; |
866e5b51 FC |
179 | } |
180 | } | |
181 | ||
3f02ac64 | 182 | return fEntries.listIterator(guessI); |
ce2388e0 | 183 | } |
3f02ac64 MK |
184 | |
185 | /** | |
186 | * Get the last element of the index | |
187 | * | |
188 | * @return the last element in the index | |
189 | */ | |
1d92f045 | 190 | public ICTFPacketDescriptor lastElement() { |
3f02ac64 MK |
191 | return fEntries.get(fEntries.size() - 1); |
192 | } | |
193 | ||
194 | /** | |
195 | * Returns the element at the specified position in this data structure. | |
196 | * | |
197 | * @param index | |
198 | * index of the element to return | |
199 | * @return the element at the specified position in this data structure | |
200 | * @throws IndexOutOfBoundsException | |
201 | * if the index is out of range ( | |
202 | * {@code index < 0 || index >= size()}) | |
203 | */ | |
1d92f045 | 204 | public ICTFPacketDescriptor getElement(int index) { |
3f02ac64 MK |
205 | return fEntries.get(index); |
206 | } | |
207 | ||
208 | /** | |
209 | * Returns the index of the first occurrence of the specified element in | |
210 | * this data structure, or -1 if this data structure does not contain the | |
211 | * element. More formally, returns the lowest index {@code i} such that, for | |
212 | * an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))}, | |
213 | * or {@code -1} if there is no such index. This will work in log(n) time | |
214 | * since the data structure contains elements in a non-repeating increasing | |
215 | * manner. | |
216 | * | |
217 | * @param element | |
218 | * element to search for | |
219 | * @return the index of the first occurrence of the specified element in | |
220 | * this data structure, or -1 if this data structure does not | |
221 | * contain the element | |
222 | * @throws ClassCastException | |
223 | * if the type of the specified element is incompatible with | |
224 | * this data structure (<a | |
225 | * href="Collection.html#optional-restrictions">optional</a>) | |
226 | * @throws NullPointerException | |
227 | * if the specified element is null and this data structure does | |
228 | * not permit null elements (<a | |
229 | * href="Collection.html#optional-restrictions">optional</a>) | |
230 | */ | |
1d92f045 | 231 | public int indexOf(ICTFPacketDescriptor element) { |
3f02ac64 MK |
232 | int indexOf = -1; |
233 | if (element != null) { | |
c1d0f6ca | 234 | indexOf = Collections.binarySearch(fEntries, element, new MonotonicComparator()); |
3f02ac64 MK |
235 | } |
236 | return (indexOf < 0) ? -1 : indexOf; | |
237 | } | |
238 | ||
c1d0f6ca | 239 | /** |
bf7f1af6 MK |
240 | * Ordering comparator for entering entries into a data structure sorted by |
241 | * timestamp. | |
c1d0f6ca | 242 | */ |
1d92f045 | 243 | private static class MonotonicComparator implements Comparator<ICTFPacketDescriptor>, Serializable { |
bf7f1af6 MK |
244 | /** |
245 | * For {@link Serializable}, that way if we migrate to a {@link TreeSet} | |
246 | * the comparator is serializable too. | |
247 | */ | |
248 | private static final long serialVersionUID = -5693064068367242076L; | |
c1d0f6ca MK |
249 | |
250 | @Override | |
1d92f045 | 251 | public int compare(ICTFPacketDescriptor left, ICTFPacketDescriptor right) { |
c1d0f6ca MK |
252 | if (left.getTimestampBegin() > right.getTimestampBegin()) { |
253 | return 1; | |
254 | } | |
255 | if (left.getTimestampBegin() < right.getTimestampBegin()) { | |
256 | return -1; | |
257 | } | |
258 | if (left.getTimestampEnd() > right.getTimestampEnd()) { | |
259 | return 1; | |
260 | } | |
261 | if (left.getTimestampEnd() < right.getTimestampEnd()) { | |
262 | return -1; | |
263 | } | |
264 | return 0; | |
265 | } | |
266 | } | |
267 | ||
866e5b51 | 268 | } |