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