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