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