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