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.text.MessageFormat;
47 import java.util.Collections;
48 import java.util.Iterator;
49 import java.util.List;
50 import java.util.NoSuchElementException;
51
52 import org.eclipse.jgit.internal.JGitText;
53 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl.CompressedBitmap;
54 import org.eclipse.jgit.internal.storage.pack.ObjectToPack;
55 import org.eclipse.jgit.lib.AnyObjectId;
56 import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
57 import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
58 import org.eclipse.jgit.lib.Constants;
59 import org.eclipse.jgit.lib.ObjectId;
60 import org.eclipse.jgit.lib.ObjectIdOwnerMap;
61 import org.eclipse.jgit.util.BlockList;
62
63 import com.googlecode.javaewah.EWAHCompressedBitmap;
64
65
66
67
68
69 public class PackBitmapIndexBuilder extends BasePackBitmapIndex {
70 private static final int MAX_XOR_OFFSET_SEARCH = 10;
71
72 private final EWAHCompressedBitmap commits;
73 private final EWAHCompressedBitmap trees;
74 private final EWAHCompressedBitmap blobs;
75 private final EWAHCompressedBitmap tags;
76 private final BlockList<PositionEntry> byOffset;
77 final BlockList<StoredBitmap>
78 byAddOrder = new BlockList<>();
79 final ObjectIdOwnerMap<PositionEntry>
80 positionEntries = new ObjectIdOwnerMap<>();
81
82
83
84
85
86
87
88
89
90 public PackBitmapIndexBuilder(List<ObjectToPack> objects) {
91 super(new ObjectIdOwnerMap<StoredBitmap>());
92 byOffset = new BlockList<>(objects.size());
93 sortByOffsetAndIndex(byOffset, positionEntries, objects);
94
95
96
97
98 int sizeInWords = Math.max(4, byOffset.size() / 64 / 3);
99 commits = new EWAHCompressedBitmap(sizeInWords);
100 trees = new EWAHCompressedBitmap(sizeInWords);
101 blobs = new EWAHCompressedBitmap(sizeInWords);
102 tags = new EWAHCompressedBitmap(sizeInWords);
103 for (int i = 0; i < objects.size(); i++) {
104 int type = objects.get(i).getType();
105 switch (type) {
106 case Constants.OBJ_COMMIT:
107 commits.set(i);
108 break;
109 case Constants.OBJ_TREE:
110 trees.set(i);
111 break;
112 case Constants.OBJ_BLOB:
113 blobs.set(i);
114 break;
115 case Constants.OBJ_TAG:
116 tags.set(i);
117 break;
118 default:
119 throw new IllegalArgumentException(MessageFormat.format(
120 JGitText.get().badObjectType, String.valueOf(type)));
121 }
122 }
123 commits.trim();
124 trees.trim();
125 blobs.trim();
126 tags.trim();
127 }
128
129 private static void sortByOffsetAndIndex(BlockList<PositionEntry> byOffset,
130 ObjectIdOwnerMap<PositionEntry> positionEntries,
131 List<ObjectToPack> entries) {
132 for (int i = 0; i < entries.size(); i++) {
133 positionEntries.add(new PositionEntry(entries.get(i), i));
134 }
135 Collections.sort(entries, (ObjectToPack"../../../../../../org/eclipse/jgit/internal/storage/pack/ObjectToPack.html#ObjectToPack">ObjectToPack a, ObjectToPack b) -> Long
136 .signum(a.getOffset() - b.getOffset()));
137 for (int i = 0; i < entries.size(); i++) {
138 PositionEntry e = positionEntries.get(entries.get(i));
139 e.offsetPosition = i;
140 byOffset.add(e);
141 }
142 }
143
144
145
146
147
148
149 public ObjectIdOwnerMap<ObjectIdOwnerMap.Entry> getObjectSet() {
150 ObjectIdOwnerMap<ObjectIdOwnerMap.Entry> r = new ObjectIdOwnerMap<>();
151 for (PositionEntry e : byOffset) {
152 r.add(new ObjectIdOwnerMap.Entry(e) {
153
154 });
155 }
156 return r;
157 }
158
159
160
161
162
163
164
165
166
167
168
169 public void addBitmap(AnyObjectId objectId, Bitmap bitmap, int flags) {
170 if (bitmap instanceof BitmapBuilder)
171 bitmap = ((BitmapBuilder) bitmap).build();
172
173 EWAHCompressedBitmap compressed;
174 if (bitmap instanceof CompressedBitmap)
175 compressed = ((CompressedBitmap) bitmap).getEwahCompressedBitmap();
176 else
177 throw new IllegalArgumentException(bitmap.getClass().toString());
178
179 addBitmap(objectId, compressed, flags);
180 }
181
182
183
184
185
186
187
188
189
190
191
192 public void addBitmap(
193 AnyObjectId objectId, EWAHCompressedBitmap bitmap, int flags) {
194 bitmap.trim();
195 StoredBitmap result = new StoredBitmap(objectId, bitmap, null, flags);
196 getBitmaps().add(result);
197 byAddOrder.add(result);
198 }
199
200
201 @Override
202 public EWAHCompressedBitmap ofObjectType(
203 EWAHCompressedBitmap bitmap, int type) {
204 switch (type) {
205 case Constants.OBJ_BLOB:
206 return getBlobs().and(bitmap);
207 case Constants.OBJ_TREE:
208 return getTrees().and(bitmap);
209 case Constants.OBJ_COMMIT:
210 return getCommits().and(bitmap);
211 case Constants.OBJ_TAG:
212 return getTags().and(bitmap);
213 }
214 throw new IllegalArgumentException();
215 }
216
217
218 @Override
219 public int findPosition(AnyObjectId objectId) {
220 PositionEntry entry = positionEntries.get(objectId);
221 if (entry == null)
222 return -1;
223 return entry.offsetPosition;
224 }
225
226
227 @Override
228 public ObjectId getObject(int position) throws IllegalArgumentException {
229 ObjectId objectId = byOffset.get(position);
230 if (objectId == null)
231 throw new IllegalArgumentException();
232 return objectId;
233 }
234
235
236
237
238
239
240 public EWAHCompressedBitmap getCommits() {
241 return commits;
242 }
243
244
245
246
247
248
249 public EWAHCompressedBitmap getTrees() {
250 return trees;
251 }
252
253
254
255
256
257
258 public EWAHCompressedBitmap getBlobs() {
259 return blobs;
260 }
261
262
263
264
265
266
267 public EWAHCompressedBitmap getTags() {
268 return tags;
269 }
270
271
272
273
274
275
276 public int getOptions() {
277 return PackBitmapIndexV1.OPT_FULL;
278 }
279
280
281 @Override
282 public int getBitmapCount() {
283 return getBitmaps().size();
284 }
285
286
287
288
289 public void clearBitmaps() {
290 byAddOrder.clear();
291 getBitmaps().clear();
292 }
293
294
295 @Override
296 public int getObjectCount() {
297 return byOffset.size();
298 }
299
300
301
302
303
304
305 public Iterable<StoredEntry> getCompressedBitmaps() {
306
307
308 return () -> new Iterator<StoredEntry>() {
309
310 private int index = byAddOrder.size() - 1;
311
312 @Override
313 public boolean hasNext() {
314 return index >= 0;
315 }
316
317 @Override
318 public StoredEntry next() {
319 if (!hasNext()) {
320 throw new NoSuchElementException();
321 }
322 StoredBitmap item = byAddOrder.get(index);
323 int bestXorOffset = 0;
324 EWAHCompressedBitmap bestBitmap = item.getBitmap();
325
326
327
328 for (int i = 1; i <= MAX_XOR_OFFSET_SEARCH; i++) {
329 int curr = i + index;
330 if (curr >= byAddOrder.size()) {
331 break;
332 }
333
334 StoredBitmap other = byAddOrder.get(curr);
335 EWAHCompressedBitmap bitmap = other.getBitmap()
336 .xor(item.getBitmap());
337
338 if (bitmap.sizeInBytes() < bestBitmap.sizeInBytes()) {
339 bestBitmap = bitmap;
340 bestXorOffset = i;
341 }
342 }
343 index--;
344
345 PositionEntry entry = positionEntries.get(item);
346 if (entry == null) {
347 throw new IllegalStateException();
348 }
349 bestBitmap.trim();
350 return new StoredEntry(entry.namePosition, bestBitmap,
351 bestXorOffset, item.getFlags());
352 }
353
354 @Override
355 public void remove() {
356 throw new UnsupportedOperationException();
357 }
358 };
359 }
360
361
362 public static final class StoredEntry {
363 private final long objectId;
364 private final EWAHCompressedBitmap bitmap;
365 private final int xorOffset;
366 private final int flags;
367
368 StoredEntry(long objectId, EWAHCompressedBitmap bitmap,
369 int xorOffset, int flags) {
370 this.objectId = objectId;
371 this.bitmap = bitmap;
372 this.xorOffset = xorOffset;
373 this.flags = flags;
374 }
375
376
377 public EWAHCompressedBitmap getBitmap() {
378 return bitmap;
379 }
380
381
382 public int getXorOffset() {
383 return xorOffset;
384 }
385
386
387 public int getFlags() {
388 return flags;
389 }
390
391
392 public long getObjectId() {
393 return objectId;
394 }
395 }
396
397 private static final class PositionEntry extends ObjectIdOwnerMap.Entry {
398 final int namePosition;
399
400 int offsetPosition;
401
402 PositionEntry(AnyObjectId objectId, int namePosition) {
403 super(objectId);
404 this.namePosition = namePosition;
405 }
406 }
407 }