Commit | Line | Data |
---|---|---|
866e5b51 FC |
1 | /******************************************************************************* |
2 | * Copyright (c) 2011-2012 Ericsson, Ecole Polytechnique de Montreal and others | |
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 | ||
ce2388e0 | 15 | package org.eclipse.linuxtools.internal.ctf.core.trace; |
866e5b51 | 16 | |
866e5b51 FC |
17 | import java.util.ListIterator; |
18 | import java.util.Vector; | |
19 | ||
ce2388e0 FC |
20 | import org.eclipse.linuxtools.ctf.core.trace.CTFReaderException; |
21 | ||
866e5b51 FC |
22 | /** |
23 | * <b><u>StreamInputPacketIndex</u></b> | |
24 | * <p> | |
25 | * TODO Implement me. Please. | |
26 | */ | |
27 | public class StreamInputPacketIndex { | |
28 | ||
29 | // ------------------------------------------------------------------------ | |
30 | // Attributes | |
31 | // ------------------------------------------------------------------------ | |
32 | ||
33 | /** | |
34 | * Entries of the index. They are sorted by increasing begin timestamp. | |
35 | * index builder. | |
36 | */ | |
37 | private final Vector<StreamInputPacketIndexEntry> entries = new Vector<StreamInputPacketIndexEntry>(); | |
38 | ||
39 | // ------------------------------------------------------------------------ | |
40 | // Getters/Setters/Predicates | |
41 | // ------------------------------------------------------------------------ | |
42 | ||
9ac2eb62 MK |
43 | /** |
44 | * Gets the entries | |
b73145e2 | 45 | * |
9ac2eb62 MK |
46 | * @return the entries |
47 | */ | |
ce2388e0 | 48 | public Vector<StreamInputPacketIndexEntry> getEntries() { |
866e5b51 FC |
49 | return this.entries; |
50 | } | |
51 | ||
9ac2eb62 MK |
52 | /** |
53 | * Gets an iterator to the entries | |
b73145e2 | 54 | * |
9ac2eb62 MK |
55 | * @return an iterator to the entries |
56 | */ | |
866e5b51 FC |
57 | public ListIterator<StreamInputPacketIndexEntry> listIterator() { |
58 | return this.entries.listIterator(); | |
59 | } | |
60 | ||
9ac2eb62 MK |
61 | /** |
62 | * Gets an iterator to the entries at a given position | |
b73145e2 JCK |
63 | * |
64 | * @param n | |
65 | * the position to get | |
9ac2eb62 MK |
66 | * @return the iterator |
67 | */ | |
866e5b51 FC |
68 | public ListIterator<StreamInputPacketIndexEntry> listIterator(int n) { |
69 | return this.entries.listIterator(n); | |
70 | } | |
71 | ||
72 | // ------------------------------------------------------------------------ | |
73 | // Operations | |
74 | // ------------------------------------------------------------------------ | |
75 | ||
76 | /** | |
77 | * Adds an entry to the index. | |
78 | * | |
79 | * @param entry | |
80 | * The entry to add | |
81 | * @throws CTFReaderException | |
be6df2d8 | 82 | * If there was a problem reading the entry |
866e5b51 FC |
83 | */ |
84 | public void addEntry(StreamInputPacketIndexEntry entry) | |
85 | throws CTFReaderException { | |
ce2388e0 | 86 | assert (entry.getContentSizeBits() != 0); |
866e5b51 | 87 | |
ecb12461 | 88 | /* Validate consistent entry. */ |
ce2388e0 | 89 | if (entry.getTimestampBegin() > entry.getTimestampEnd()) { |
b73145e2 | 90 | throw new CTFReaderException("Packet begin timestamp is after end timestamp"); //$NON-NLS-1$ |
866e5b51 FC |
91 | } |
92 | ||
ecb12461 | 93 | /* Validate entries are inserted in monotonic increasing timestamp order. */ |
866e5b51 | 94 | if (!this.entries.isEmpty()) { |
bfe038ff MK |
95 | if (entry.getTimestampBegin() < this.entries.lastElement() |
96 | .getTimestampBegin()) { | |
b73145e2 | 97 | throw new CTFReaderException("Packets begin timestamp decreasing"); //$NON-NLS-1$ |
866e5b51 FC |
98 | } |
99 | } | |
866e5b51 FC |
100 | this.entries.add(entry); |
101 | } | |
102 | ||
103 | /** | |
ecb12461 EB |
104 | * Returns the first PacketIndexEntry that could include the timestamp, |
105 | * that is the last packet with a begin timestamp smaller than the given timestamp. | |
866e5b51 FC |
106 | * |
107 | * @param timestamp | |
108 | * The timestamp to look for. | |
109 | * @return The StreamInputPacketEntry that corresponds to the packet that | |
110 | * includes the given timestamp. | |
111 | */ | |
112 | public ListIterator<StreamInputPacketIndexEntry> search(final long timestamp) { | |
113 | /* | |
114 | * Start with min and max covering all the elements. | |
115 | */ | |
116 | int max = this.entries.size() - 1; | |
117 | int min = 0; | |
118 | ||
119 | int guessI; | |
120 | StreamInputPacketIndexEntry guessEntry = null; | |
121 | ||
4a110860 AM |
122 | /* |
123 | * If the index is empty, return the iterator at the very beginning. | |
124 | */ | |
b73145e2 | 125 | if (this.getEntries().isEmpty()) { |
4a110860 AM |
126 | return this.getEntries().listIterator(); |
127 | } | |
128 | ||
866e5b51 FC |
129 | if (timestamp < 0) { |
130 | throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$ | |
131 | } | |
132 | ||
d68f46c2 | 133 | /* Binary search */ |
866e5b51 FC |
134 | for (;;) { |
135 | /* | |
d68f46c2 | 136 | * Guess in the middle of min and max. |
866e5b51 | 137 | */ |
d68f46c2 | 138 | guessI = min + ((max - min) / 2); |
866e5b51 FC |
139 | guessEntry = this.entries.get(guessI); |
140 | ||
141 | /* | |
142 | * If we reached the point where we focus on a single packet, our | |
143 | * search is done. | |
144 | */ | |
145 | if (min == max) { | |
146 | break; | |
147 | } | |
148 | ||
d68f46c2 | 149 | if (timestamp <= guessEntry.getTimestampEnd()) { |
866e5b51 | 150 | /* |
d68f46c2 EB |
151 | * If the timestamp is lower or equal to the end of the guess packet, |
152 | * then the guess packet becomes the new inclusive max. | |
866e5b51 | 153 | */ |
d68f46c2 EB |
154 | max = guessI; |
155 | } else { | |
866e5b51 | 156 | /* |
d68f46c2 EB |
157 | * If the timestamp is greater than the end of the guess packet, then |
158 | * the new inclusive min is the packet after the guess packet. | |
866e5b51 | 159 | */ |
d68f46c2 | 160 | min = guessI + 1; |
866e5b51 FC |
161 | } |
162 | } | |
163 | ||
ce2388e0 FC |
164 | return this.entries.listIterator(guessI); |
165 | } | |
866e5b51 | 166 | } |