1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 package org.eclipse.jgit.internal.storage.file;
45
46 import java.io.IOException;
47 import java.io.InputStream;
48 import java.text.MessageFormat;
49 import java.util.Arrays;
50 import java.util.Iterator;
51 import java.util.NoSuchElementException;
52 import java.util.Set;
53
54 import org.eclipse.jgit.errors.MissingObjectException;
55 import org.eclipse.jgit.internal.JGitText;
56 import org.eclipse.jgit.lib.AbbreviatedObjectId;
57 import org.eclipse.jgit.lib.AnyObjectId;
58 import org.eclipse.jgit.lib.Constants;
59 import org.eclipse.jgit.lib.ObjectId;
60 import org.eclipse.jgit.util.IO;
61 import org.eclipse.jgit.util.NB;
62
63
64 class PackIndexV2 extends PackIndex {
65 private static final long IS_O64 = 1L << 31;
66
67 private static final int FANOUT = 256;
68
69 private static final int[] NO_INTS = {};
70
71 private static final byte[] NO_BYTES = {};
72
73 private long objectCnt;
74
75 private final long[] fanoutTable;
76
77
78 private int[][] names;
79
80
81 private byte[][] offset32;
82
83
84 private byte[][] crc32;
85
86
87 private byte[] offset64;
88
89 PackIndexV2(final InputStream fd) throws IOException {
90 final byte[] fanoutRaw = new byte[4 * FANOUT];
91 IO.readFully(fd, fanoutRaw, 0, fanoutRaw.length);
92 fanoutTable = new long[FANOUT];
93 for (int k = 0; k < FANOUT; k++)
94 fanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);
95 objectCnt = fanoutTable[FANOUT - 1];
96
97 names = new int[FANOUT][];
98 offset32 = new byte[FANOUT][];
99 crc32 = new byte[FANOUT][];
100
101
102
103
104
105 for (int k = 0; k < FANOUT; k++) {
106 final long bucketCnt;
107 if (k == 0)
108 bucketCnt = fanoutTable[k];
109 else
110 bucketCnt = fanoutTable[k] - fanoutTable[k - 1];
111
112 if (bucketCnt == 0) {
113 names[k] = NO_INTS;
114 offset32[k] = NO_BYTES;
115 crc32[k] = NO_BYTES;
116 continue;
117 } else if (bucketCnt < 0)
118 throw new IOException(MessageFormat.format(
119 JGitText.get().indexFileCorruptedNegativeBucketCount,
120 Long.valueOf(bucketCnt)));
121
122 final long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
123 if (nameLen > Integer.MAX_VALUE - 8)
124 throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);
125
126 final int intNameLen = (int) nameLen;
127 final byte[] raw = new byte[intNameLen];
128 final int[] bin = new int[intNameLen >>> 2];
129 IO.readFully(fd, raw, 0, raw.length);
130 for (int i = 0; i < bin.length; i++)
131 bin[i] = NB.decodeInt32(raw, i << 2);
132
133 names[k] = bin;
134 offset32[k] = new byte[(int) (bucketCnt * 4)];
135 crc32[k] = new byte[(int) (bucketCnt * 4)];
136 }
137
138
139 for (int k = 0; k < FANOUT; k++)
140 IO.readFully(fd, crc32[k], 0, crc32[k].length);
141
142
143
144
145 int o64cnt = 0;
146 for (int k = 0; k < FANOUT; k++) {
147 final byte[] ofs = offset32[k];
148 IO.readFully(fd, ofs, 0, ofs.length);
149 for (int p = 0; p < ofs.length; p += 4)
150 if (ofs[p] < 0)
151 o64cnt++;
152 }
153
154
155
156 if (o64cnt > 0) {
157 offset64 = new byte[o64cnt * 8];
158 IO.readFully(fd, offset64, 0, offset64.length);
159 } else {
160 offset64 = NO_BYTES;
161 }
162
163 packChecksum = new byte[20];
164 IO.readFully(fd, packChecksum, 0, packChecksum.length);
165 }
166
167 @Override
168 public long getObjectCount() {
169 return objectCnt;
170 }
171
172 @Override
173 public long getOffset64Count() {
174 return offset64.length / 8;
175 }
176
177 private int findLevelOne(final long nthPosition) {
178 int levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);
179 if (levelOne >= 0) {
180
181
182
183 long base = fanoutTable[levelOne];
184 while (levelOne > 0 && base == fanoutTable[levelOne - 1])
185 levelOne--;
186 } else {
187
188
189 levelOne = -(levelOne + 1);
190 }
191 return levelOne;
192 }
193
194 private int getLevelTwo(final long nthPosition, final int levelOne) {
195 final long base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
196 return (int) (nthPosition - base);
197 }
198
199 @Override
200 public ObjectId getObjectId(final long nthPosition) {
201 final int levelOne = findLevelOne(nthPosition);
202 final int p = getLevelTwo(nthPosition, levelOne);
203 final int p4 = p << 2;
204 return ObjectId.fromRaw(names[levelOne], p4 + p);
205 }
206
207 @Override
208 public long getOffset(final long nthPosition) {
209 final int levelOne = findLevelOne(nthPosition);
210 final int levelTwo = getLevelTwo(nthPosition, levelOne);
211 return getOffset(levelOne, levelTwo);
212 }
213
214 @Override
215 public long findOffset(final AnyObjectId objId) {
216 final int levelOne = objId.getFirstByte();
217 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
218 if (levelTwo == -1)
219 return -1;
220 return getOffset(levelOne, levelTwo);
221 }
222
223 private long getOffset(final int levelOne, final int levelTwo) {
224 final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
225 if ((p & IS_O64) != 0)
226 return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
227 return p;
228 }
229
230 @Override
231 public long findCRC32(AnyObjectId objId) throws MissingObjectException {
232 final int levelOne = objId.getFirstByte();
233 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
234 if (levelTwo == -1)
235 throw new MissingObjectException(objId.copy(), "unknown");
236 return NB.decodeUInt32(crc32[levelOne], levelTwo << 2);
237 }
238
239 @Override
240 public boolean hasCRC32Support() {
241 return true;
242 }
243
244 @Override
245 public Iterator<MutableEntry> iterator() {
246 return new EntriesIteratorV2();
247 }
248
249 @Override
250 public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
251 int matchLimit) throws IOException {
252 int[] data = names[id.getFirstByte()];
253 int max = offset32[id.getFirstByte()].length >>> 2;
254 int high = max;
255 if (high == 0)
256 return;
257 int low = 0;
258 do {
259 int p = (low + high) >>> 1;
260 final int cmp = id.prefixCompare(data, idOffset(p));
261 if (cmp < 0)
262 high = p;
263 else if (cmp == 0) {
264
265
266
267 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
268 p--;
269 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
270 matches.add(ObjectId.fromRaw(data, idOffset(p)));
271 if (matches.size() > matchLimit)
272 break;
273 }
274 return;
275 } else
276 low = p + 1;
277 } while (low < high);
278 }
279
280 private static int idOffset(int p) {
281 return (p << 2) + p;
282 }
283
284 private int binarySearchLevelTwo(final AnyObjectId objId, final int levelOne) {
285 final int[] data = names[levelOne];
286 int high = offset32[levelOne].length >>> 2;
287 if (high == 0)
288 return -1;
289 int low = 0;
290 do {
291 final int mid = (low + high) >>> 1;
292 final int mid4 = mid << 2;
293 final int cmp;
294
295 cmp = objId.compareTo(data, mid4 + mid);
296 if (cmp < 0)
297 high = mid;
298 else if (cmp == 0) {
299 return mid;
300 } else
301 low = mid + 1;
302 } while (low < high);
303 return -1;
304 }
305
306 private class EntriesIteratorV2 extends EntriesIterator {
307 private int levelOne;
308
309 private int levelTwo;
310
311 @Override
312 protected MutableEntry initEntry() {
313 return new MutableEntry() {
314 protected void ensureId() {
315 idBuffer.fromRaw(names[levelOne], levelTwo
316 - Constants.OBJECT_ID_LENGTH / 4);
317 }
318 };
319 }
320
321 public MutableEntry next() {
322 for (; levelOne < names.length; levelOne++) {
323 if (levelTwo < names[levelOne].length) {
324 int idx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;
325 long offset = NB.decodeUInt32(offset32[levelOne], idx);
326 if ((offset & IS_O64) != 0) {
327 idx = (8 * (int) (offset & ~IS_O64));
328 offset = NB.decodeUInt64(offset64, idx);
329 }
330 entry.offset = offset;
331
332 levelTwo += Constants.OBJECT_ID_LENGTH / 4;
333 returnedNumber++;
334 return entry;
335 }
336 levelTwo = 0;
337 }
338 throw new NoSuchElementException();
339 }
340 }
341
342 }