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
45
46
47 package org.eclipse.jgit.internal.storage.file;
48
49 import java.io.IOException;
50 import java.io.InputStream;
51 import java.util.Arrays;
52 import java.util.Iterator;
53 import java.util.NoSuchElementException;
54 import java.util.Set;
55
56 import org.eclipse.jgit.errors.CorruptObjectException;
57 import org.eclipse.jgit.internal.JGitText;
58 import org.eclipse.jgit.lib.AbbreviatedObjectId;
59 import org.eclipse.jgit.lib.AnyObjectId;
60 import org.eclipse.jgit.lib.Constants;
61 import org.eclipse.jgit.lib.ObjectId;
62 import org.eclipse.jgit.util.IO;
63 import org.eclipse.jgit.util.NB;
64
65 class PackIndexV1 extends PackIndex {
66 private static final int IDX_HDR_LEN = 256 * 4;
67
68 private final long[] idxHeader;
69
70 byte[][] idxdata;
71
72 private long objectCnt;
73
74 PackIndexV1(final InputStream fd, final byte[] hdr)
75 throws CorruptObjectException, IOException {
76 final byte[] fanoutTable = new byte[IDX_HDR_LEN];
77 System.arraycopy(hdr, 0, fanoutTable, 0, hdr.length);
78 IO.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length);
79
80 idxHeader = new long[256];
81 for (int k = 0; k < idxHeader.length; k++)
82 idxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4);
83 idxdata = new byte[idxHeader.length][];
84 for (int k = 0; k < idxHeader.length; k++) {
85 int n;
86 if (k == 0) {
87 n = (int) (idxHeader[k]);
88 } else {
89 n = (int) (idxHeader[k] - idxHeader[k - 1]);
90 }
91 if (n > 0) {
92 final long len = n * (Constants.OBJECT_ID_LENGTH + 4);
93 if (len > Integer.MAX_VALUE - 8)
94 throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);
95
96 idxdata[k] = new byte[(int) len];
97 IO.readFully(fd, idxdata[k], 0, idxdata[k].length);
98 }
99 }
100 objectCnt = idxHeader[255];
101
102 packChecksum = new byte[20];
103 IO.readFully(fd, packChecksum, 0, packChecksum.length);
104 }
105
106
107 @Override
108 public long getObjectCount() {
109 return objectCnt;
110 }
111
112
113 @Override
114 public long getOffset64Count() {
115 long n64 = 0;
116 for (MutableEntry e : this) {
117 if (e.getOffset() >= Integer.MAX_VALUE)
118 n64++;
119 }
120 return n64;
121 }
122
123 private int findLevelOne(long nthPosition) {
124 int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
125 if (levelOne >= 0) {
126
127
128
129 long base = idxHeader[levelOne];
130 while (levelOne > 0 && base == idxHeader[levelOne - 1])
131 levelOne--;
132 } else {
133
134
135 levelOne = -(levelOne + 1);
136 }
137 return levelOne;
138 }
139
140 private int getLevelTwo(long nthPosition, int levelOne) {
141 final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
142 return (int) (nthPosition - base);
143 }
144
145
146 @Override
147 public ObjectId getObjectId(long nthPosition) {
148 final int levelOne = findLevelOne(nthPosition);
149 final int p = getLevelTwo(nthPosition, levelOne);
150 final int dataIdx = idOffset(p);
151 return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
152 }
153
154 @Override
155 long getOffset(long nthPosition) {
156 final int levelOne = findLevelOne(nthPosition);
157 final int levelTwo = getLevelTwo(nthPosition, levelOne);
158 final int p = (4 + Constants.OBJECT_ID_LENGTH) * levelTwo;
159 return NB.decodeUInt32(idxdata[levelOne], p);
160 }
161
162
163 @Override
164 public long findOffset(AnyObjectId objId) {
165 final int levelOne = objId.getFirstByte();
166 byte[] data = idxdata[levelOne];
167 if (data == null)
168 return -1;
169 int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
170 int low = 0;
171 do {
172 final int mid = (low + high) >>> 1;
173 final int pos = idOffset(mid);
174 final int cmp = objId.compareTo(data, pos);
175 if (cmp < 0)
176 high = mid;
177 else if (cmp == 0) {
178 int b0 = data[pos - 4] & 0xff;
179 int b1 = data[pos - 3] & 0xff;
180 int b2 = data[pos - 2] & 0xff;
181 int b3 = data[pos - 1] & 0xff;
182 return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
183 } else
184 low = mid + 1;
185 } while (low < high);
186 return -1;
187 }
188
189
190 @Override
191 public long findCRC32(AnyObjectId objId) {
192 throw new UnsupportedOperationException();
193 }
194
195
196 @Override
197 public boolean hasCRC32Support() {
198 return false;
199 }
200
201
202 @Override
203 public Iterator<MutableEntry> iterator() {
204 return new IndexV1Iterator();
205 }
206
207
208 @Override
209 public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
210 int matchLimit) throws IOException {
211 byte[] data = idxdata[id.getFirstByte()];
212 if (data == null)
213 return;
214 int max = data.length / (4 + Constants.OBJECT_ID_LENGTH);
215 int high = max;
216 int low = 0;
217 do {
218 int p = (low + high) >>> 1;
219 final int cmp = id.prefixCompare(data, idOffset(p));
220 if (cmp < 0)
221 high = p;
222 else if (cmp == 0) {
223
224
225
226 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
227 p--;
228 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
229 matches.add(ObjectId.fromRaw(data, idOffset(p)));
230 if (matches.size() > matchLimit)
231 break;
232 }
233 return;
234 } else
235 low = p + 1;
236 } while (low < high);
237 }
238
239 private static int idOffset(int mid) {
240 return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
241 }
242
243 private class IndexV1Iterator extends EntriesIterator {
244 int levelOne;
245
246 int levelTwo;
247
248 @Override
249 protected MutableEntry initEntry() {
250 return new MutableEntry() {
251 @Override
252 protected void ensureId() {
253 idBuffer.fromRaw(idxdata[levelOne], levelTwo
254 - Constants.OBJECT_ID_LENGTH);
255 }
256 };
257 }
258
259 @Override
260 public MutableEntry next() {
261 for (; levelOne < idxdata.length; levelOne++) {
262 if (idxdata[levelOne] == null)
263 continue;
264 if (levelTwo < idxdata[levelOne].length) {
265 entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
266 levelTwo += Constants.OBJECT_ID_LENGTH + 4;
267 returnedNumber++;
268 return entry;
269 }
270 levelTwo = 0;
271 }
272 throw new NoSuchElementException();
273 }
274 }
275 }