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 @Override
107 public long getObjectCount() {
108 return objectCnt;
109 }
110
111 @Override
112 public long getOffset64Count() {
113 long n64 = 0;
114 for (final MutableEntry e : this) {
115 if (e.getOffset() >= Integer.MAX_VALUE)
116 n64++;
117 }
118 return n64;
119 }
120
121 private int findLevelOne(final long nthPosition) {
122 int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
123 if (levelOne >= 0) {
124
125
126
127 long base = idxHeader[levelOne];
128 while (levelOne > 0 && base == idxHeader[levelOne - 1])
129 levelOne--;
130 } else {
131
132
133 levelOne = -(levelOne + 1);
134 }
135 return levelOne;
136 }
137
138 private int getLevelTwo(final long nthPosition, final int levelOne) {
139 final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
140 return (int) (nthPosition - base);
141 }
142
143 @Override
144 public ObjectId getObjectId(final long nthPosition) {
145 final int levelOne = findLevelOne(nthPosition);
146 final int p = getLevelTwo(nthPosition, levelOne);
147 final int dataIdx = idOffset(p);
148 return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
149 }
150
151 @Override
152 long getOffset(long nthPosition) {
153 final int levelOne = findLevelOne(nthPosition);
154 final int levelTwo = getLevelTwo(nthPosition, levelOne);
155 final int p = (4 + Constants.OBJECT_ID_LENGTH) * levelTwo;
156 return NB.decodeUInt32(idxdata[levelOne], p);
157 }
158
159 @Override
160 public long findOffset(final AnyObjectId objId) {
161 final int levelOne = objId.getFirstByte();
162 byte[] data = idxdata[levelOne];
163 if (data == null)
164 return -1;
165 int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
166 int low = 0;
167 do {
168 final int mid = (low + high) >>> 1;
169 final int pos = idOffset(mid);
170 final int cmp = objId.compareTo(data, pos);
171 if (cmp < 0)
172 high = mid;
173 else if (cmp == 0) {
174 int b0 = data[pos - 4] & 0xff;
175 int b1 = data[pos - 3] & 0xff;
176 int b2 = data[pos - 2] & 0xff;
177 int b3 = data[pos - 1] & 0xff;
178 return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
179 } else
180 low = mid + 1;
181 } while (low < high);
182 return -1;
183 }
184
185 @Override
186 public long findCRC32(AnyObjectId objId) {
187 throw new UnsupportedOperationException();
188 }
189
190 @Override
191 public boolean hasCRC32Support() {
192 return false;
193 }
194
195 @Override
196 public Iterator<MutableEntry> iterator() {
197 return new IndexV1Iterator();
198 }
199
200 @Override
201 public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
202 int matchLimit) throws IOException {
203 byte[] data = idxdata[id.getFirstByte()];
204 if (data == null)
205 return;
206 int max = data.length / (4 + Constants.OBJECT_ID_LENGTH);
207 int high = max;
208 int low = 0;
209 do {
210 int p = (low + high) >>> 1;
211 final int cmp = id.prefixCompare(data, idOffset(p));
212 if (cmp < 0)
213 high = p;
214 else if (cmp == 0) {
215
216
217
218 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
219 p--;
220 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
221 matches.add(ObjectId.fromRaw(data, idOffset(p)));
222 if (matches.size() > matchLimit)
223 break;
224 }
225 return;
226 } else
227 low = p + 1;
228 } while (low < high);
229 }
230
231 private static int idOffset(int mid) {
232 return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
233 }
234
235 private class IndexV1Iterator extends EntriesIterator {
236 int levelOne;
237
238 int levelTwo;
239
240 @Override
241 protected MutableEntry initEntry() {
242 return new MutableEntry() {
243 @Override
244 protected void ensureId() {
245 idBuffer.fromRaw(idxdata[levelOne], levelTwo
246 - Constants.OBJECT_ID_LENGTH);
247 }
248 };
249 }
250
251 @Override
252 public MutableEntry next() {
253 for (; levelOne < idxdata.length; levelOne++) {
254 if (idxdata[levelOne] == null)
255 continue;
256 if (levelTwo < idxdata[levelOne].length) {
257 entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
258 levelTwo += Constants.OBJECT_ID_LENGTH + 4;
259 returnedNumber++;
260 return entry;
261 }
262 levelTwo = 0;
263 }
264 throw new NoSuchElementException();
265 }
266 }
267 }