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 int[][] names;
79
80
81 byte[][] offset32;
82
83
84 private byte[][] crc32;
85
86
87 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
168 @Override
169 public long getObjectCount() {
170 return objectCnt;
171 }
172
173
174 @Override
175 public long getOffset64Count() {
176 return offset64.length / 8;
177 }
178
179 private int findLevelOne(long nthPosition) {
180 int levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);
181 if (levelOne >= 0) {
182
183
184
185 long base = fanoutTable[levelOne];
186 while (levelOne > 0 && base == fanoutTable[levelOne - 1])
187 levelOne--;
188 } else {
189
190
191 levelOne = -(levelOne + 1);
192 }
193 return levelOne;
194 }
195
196 private int getLevelTwo(long nthPosition, int levelOne) {
197 final long base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
198 return (int) (nthPosition - base);
199 }
200
201
202 @Override
203 public ObjectId getObjectId(long nthPosition) {
204 final int levelOne = findLevelOne(nthPosition);
205 final int p = getLevelTwo(nthPosition, levelOne);
206 final int p4 = p << 2;
207 return ObjectId.fromRaw(names[levelOne], p4 + p);
208 }
209
210
211 @Override
212 public long getOffset(long nthPosition) {
213 final int levelOne = findLevelOne(nthPosition);
214 final int levelTwo = getLevelTwo(nthPosition, levelOne);
215 return getOffset(levelOne, levelTwo);
216 }
217
218
219 @Override
220 public long findOffset(AnyObjectId objId) {
221 final int levelOne = objId.getFirstByte();
222 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
223 if (levelTwo == -1)
224 return -1;
225 return getOffset(levelOne, levelTwo);
226 }
227
228 private long getOffset(int levelOne, int levelTwo) {
229 final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
230 if ((p & IS_O64) != 0)
231 return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
232 return p;
233 }
234
235
236 @Override
237 public long findCRC32(AnyObjectId objId) throws MissingObjectException {
238 final int levelOne = objId.getFirstByte();
239 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
240 if (levelTwo == -1)
241 throw new MissingObjectException(objId.copy(), "unknown");
242 return NB.decodeUInt32(crc32[levelOne], levelTwo << 2);
243 }
244
245
246 @Override
247 public boolean hasCRC32Support() {
248 return true;
249 }
250
251
252 @Override
253 public Iterator<MutableEntry> iterator() {
254 return new EntriesIteratorV2();
255 }
256
257
258 @Override
259 public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
260 int matchLimit) throws IOException {
261 int[] data = names[id.getFirstByte()];
262 int max = offset32[id.getFirstByte()].length >>> 2;
263 int high = max;
264 if (high == 0)
265 return;
266 int low = 0;
267 do {
268 int p = (low + high) >>> 1;
269 final int cmp = id.prefixCompare(data, idOffset(p));
270 if (cmp < 0)
271 high = p;
272 else if (cmp == 0) {
273
274
275
276 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
277 p--;
278 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
279 matches.add(ObjectId.fromRaw(data, idOffset(p)));
280 if (matches.size() > matchLimit)
281 break;
282 }
283 return;
284 } else
285 low = p + 1;
286 } while (low < high);
287 }
288
289 private static int idOffset(int p) {
290 return (p << 2) + p;
291 }
292
293 private int binarySearchLevelTwo(AnyObjectId objId, int levelOne) {
294 final int[] data = names[levelOne];
295 int high = offset32[levelOne].length >>> 2;
296 if (high == 0)
297 return -1;
298 int low = 0;
299 do {
300 final int mid = (low + high) >>> 1;
301 final int mid4 = mid << 2;
302 final int cmp;
303
304 cmp = objId.compareTo(data, mid4 + mid);
305 if (cmp < 0)
306 high = mid;
307 else if (cmp == 0) {
308 return mid;
309 } else
310 low = mid + 1;
311 } while (low < high);
312 return -1;
313 }
314
315 private class EntriesIteratorV2 extends EntriesIterator {
316 int levelOne;
317
318 int levelTwo;
319
320 @Override
321 protected MutableEntry initEntry() {
322 return new MutableEntry() {
323 @Override
324 protected void ensureId() {
325 idBuffer.fromRaw(names[levelOne], levelTwo
326 - Constants.OBJECT_ID_LENGTH / 4);
327 }
328 };
329 }
330
331 @Override
332 public MutableEntry next() {
333 for (; levelOne < names.length; levelOne++) {
334 if (levelTwo < names[levelOne].length) {
335 int idx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;
336 long offset = NB.decodeUInt32(offset32[levelOne], idx);
337 if ((offset & IS_O64) != 0) {
338 idx = (8 * (int) (offset & ~IS_O64));
339 offset = NB.decodeUInt64(offset64, idx);
340 }
341 entry.offset = offset;
342
343 levelTwo += Constants.OBJECT_ID_LENGTH / 4;
344 returnedNumber++;
345 return entry;
346 }
347 levelTwo = 0;
348 }
349 throw new NoSuchElementException();
350 }
351 }
352
353 }