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