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