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; |
bf7f1af6 | 25 | import java.util.TreeSet; |
866e5b51 | 26 | |
a6efddce | 27 | import org.eclipse.core.runtime.IStatus; |
3f02ac64 | 28 | import org.eclipse.jdt.annotation.NonNull; |
1d92f045 | 29 | import org.eclipse.tracecompass.ctf.core.trace.ICTFPacketDescriptor; |
a6efddce | 30 | import org.eclipse.tracecompass.internal.ctf.core.Activator; |
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 | |
9ac2eb62 | 79 | */ |
a6efddce | 80 | public void appendAll(Collection<ICTFPacketDescriptor> preParsedIndex) { |
1d92f045 | 81 | for (ICTFPacketDescriptor sipie : preParsedIndex) { |
3f02ac64 MK |
82 | append(checkNotNull(sipie)); |
83 | } | |
866e5b51 FC |
84 | } |
85 | ||
866e5b51 | 86 | /** |
3f02ac64 | 87 | * Appends the specified element to the end of this data structure |
866e5b51 FC |
88 | * |
89 | * @param entry | |
3f02ac64 MK |
90 | * element to be appended to this index, cannot be null |
91 | * @return {@code true} (as specified by {@link Collection#add}) | |
866e5b51 | 92 | */ |
a6efddce MK |
93 | public synchronized boolean append(@NonNull ICTFPacketDescriptor entry) { |
94 | ICTFPacketDescriptor entryToAdd = entry; | |
ecb12461 | 95 | /* Validate consistent entry. */ |
a6efddce MK |
96 | if (entryToAdd.getTimestampBegin() > entryToAdd.getTimestampEnd()) { |
97 | Activator.log(IStatus.WARNING, "Packet at offset " + entryToAdd.getOffsetBytes() + //$NON-NLS-1$ | |
98 | " begin timestamp is after end timestamp"); //$NON-NLS-1$ | |
99 | entryToAdd = new StreamInputPacketIndexEntry(entryToAdd, Long.MAX_VALUE); | |
866e5b51 FC |
100 | } |
101 | ||
3f02ac64 MK |
102 | /* |
103 | * Validate entries are inserted in monotonic increasing timestamp | |
104 | * order. | |
105 | */ | |
a6efddce | 106 | if (!fEntries.isEmpty() && (entryToAdd.getTimestampBegin() < lastElement().getTimestampBegin())) { |
782738a0 | 107 | return false; |
866e5b51 | 108 | } |
3f02ac64 | 109 | |
a6efddce | 110 | fEntries.add(entryToAdd); |
3f02ac64 | 111 | return true; |
866e5b51 FC |
112 | } |
113 | ||
114 | /** | |
6af89f01 MK |
115 | * Returns the first packet that could include the timestamp, that is the |
116 | * last packet with a begin timestamp smaller than the given timestamp. | |
866e5b51 FC |
117 | * |
118 | * @param timestamp | |
119 | * The timestamp to look for. | |
6af89f01 | 120 | * @return The index of the desired packet |
866e5b51 | 121 | */ |
6af89f01 | 122 | public int search(final long timestamp) { |
4a110860 | 123 | /* |
6af89f01 MK |
124 | * Search using binary search. |
125 | * | |
a6efddce MK |
126 | * As the entries in fEntries are IndexEntries, the key to search for |
127 | * needs to be one too. We are looking for a timestamp though, so we use | |
128 | * the dataOffset which is a long and use it as a timestamp holder. | |
4a110860 | 129 | */ |
6af89f01 MK |
130 | int index = Collections.binarySearch(fEntries, new StreamInputPacketIndexEntry(timestamp, 0), new FindTimestamp()); |
131 | if (index < 0) { | |
132 | index = -index - 1; | |
866e5b51 | 133 | } |
6af89f01 | 134 | return index; |
ce2388e0 | 135 | } |
3f02ac64 MK |
136 | |
137 | /** | |
138 | * Get the last element of the index | |
139 | * | |
140 | * @return the last element in the index | |
141 | */ | |
1d92f045 | 142 | public ICTFPacketDescriptor lastElement() { |
3f02ac64 MK |
143 | return fEntries.get(fEntries.size() - 1); |
144 | } | |
145 | ||
146 | /** | |
147 | * Returns the element at the specified position in this data structure. | |
148 | * | |
149 | * @param index | |
150 | * index of the element to return | |
151 | * @return the element at the specified position in this data structure | |
152 | * @throws IndexOutOfBoundsException | |
153 | * if the index is out of range ( | |
154 | * {@code index < 0 || index >= size()}) | |
155 | */ | |
1d92f045 | 156 | public ICTFPacketDescriptor getElement(int index) { |
3f02ac64 MK |
157 | return fEntries.get(index); |
158 | } | |
159 | ||
160 | /** | |
161 | * Returns the index of the first occurrence of the specified element in | |
162 | * this data structure, or -1 if this data structure does not contain the | |
163 | * element. More formally, returns the lowest index {@code i} such that, for | |
164 | * an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))}, | |
165 | * or {@code -1} if there is no such index. This will work in log(n) time | |
166 | * since the data structure contains elements in a non-repeating increasing | |
167 | * manner. | |
168 | * | |
169 | * @param element | |
170 | * element to search for | |
171 | * @return the index of the first occurrence of the specified element in | |
172 | * this data structure, or -1 if this data structure does not | |
173 | * contain the element | |
174 | * @throws ClassCastException | |
175 | * if the type of the specified element is incompatible with | |
a6efddce MK |
176 | * this data structure ( |
177 | * <a href="Collection.html#optional-restrictions">optional</a>) | |
3f02ac64 MK |
178 | * @throws NullPointerException |
179 | * if the specified element is null and this data structure does | |
a6efddce MK |
180 | * not permit null elements ( |
181 | * <a href="Collection.html#optional-restrictions">optional</a>) | |
3f02ac64 | 182 | */ |
1d92f045 | 183 | public int indexOf(ICTFPacketDescriptor element) { |
3f02ac64 MK |
184 | int indexOf = -1; |
185 | if (element != null) { | |
c1d0f6ca | 186 | indexOf = Collections.binarySearch(fEntries, element, new MonotonicComparator()); |
3f02ac64 MK |
187 | } |
188 | return (indexOf < 0) ? -1 : indexOf; | |
189 | } | |
190 | ||
c1d0f6ca | 191 | /** |
bf7f1af6 MK |
192 | * Ordering comparator for entering entries into a data structure sorted by |
193 | * timestamp. | |
c1d0f6ca | 194 | */ |
1d92f045 | 195 | private static class MonotonicComparator implements Comparator<ICTFPacketDescriptor>, Serializable { |
bf7f1af6 MK |
196 | /** |
197 | * For {@link Serializable}, that way if we migrate to a {@link TreeSet} | |
198 | * the comparator is serializable too. | |
199 | */ | |
200 | private static final long serialVersionUID = -5693064068367242076L; | |
c1d0f6ca MK |
201 | |
202 | @Override | |
1d92f045 | 203 | public int compare(ICTFPacketDescriptor left, ICTFPacketDescriptor right) { |
c1d0f6ca MK |
204 | if (left.getTimestampBegin() > right.getTimestampBegin()) { |
205 | return 1; | |
206 | } | |
207 | if (left.getTimestampBegin() < right.getTimestampBegin()) { | |
208 | return -1; | |
209 | } | |
210 | if (left.getTimestampEnd() > right.getTimestampEnd()) { | |
211 | return 1; | |
212 | } | |
213 | if (left.getTimestampEnd() < right.getTimestampEnd()) { | |
214 | return -1; | |
215 | } | |
216 | return 0; | |
217 | } | |
218 | } | |
219 | ||
6af89f01 MK |
220 | /** |
221 | * Used for search, assumes that the second argument in the comparison is | |
222 | * always the key | |
223 | */ | |
224 | private static class FindTimestamp implements Comparator<ICTFPacketDescriptor>, Serializable { | |
225 | ||
226 | /** | |
227 | * UID | |
228 | */ | |
229 | private static final long serialVersionUID = 7235997205945550341L; | |
230 | ||
231 | @Override | |
232 | public int compare(ICTFPacketDescriptor value, ICTFPacketDescriptor key) { | |
233 | /* | |
a6efddce MK |
234 | * It is assumed that the second packet descriptor is the key, a |
235 | * wrapped timestamp in a PacketDescriptor. So we need to extract | |
236 | * the timestamp. Then we have 3 choices, the if the timestamp is in | |
237 | * the interval, we return 0 or found. If the timestamp is before or | |
238 | * after, we just need to compare it to a value in the segment (like | |
239 | * start) to know if it is greater or lesser to the current packet. | |
6af89f01 MK |
240 | */ |
241 | long ts = key.getOffsetBits(); | |
242 | if (value.includes(ts)) { | |
243 | return 0; | |
244 | } | |
245 | return Long.compare(value.getTimestampBegin(), ts); | |
246 | } | |
247 | ||
248 | } | |
249 | ||
866e5b51 | 250 | } |