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