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.Iterator;
48 import java.util.NoSuchElementException;
49
50 import org.eclipse.jgit.internal.JGitText;
51 import org.eclipse.jgit.lib.AnyObjectId;
52 import org.eclipse.jgit.lib.BitmapIndex;
53 import org.eclipse.jgit.lib.BitmapObject;
54 import org.eclipse.jgit.lib.Constants;
55 import org.eclipse.jgit.lib.ObjectId;
56 import org.eclipse.jgit.lib.ObjectIdOwnerMap;
57 import org.eclipse.jgit.util.BlockList;
58
59 import com.googlecode.javaewah.EWAHCompressedBitmap;
60 import com.googlecode.javaewah.IntIterator;
61
62
63
64
65 public class BitmapIndexImpl implements BitmapIndex {
66 private static final int EXTRA_BITS = 10 * 1024;
67
68 final PackBitmapIndex packIndex;
69
70 final MutableBitmapIndex mutableIndex;
71
72 final int indexObjectCount;
73
74
75
76
77
78
79
80 public BitmapIndexImpl(PackBitmapIndex packIndex) {
81 this.packIndex = packIndex;
82 mutableIndex = new MutableBitmapIndex();
83 indexObjectCount = packIndex.getObjectCount();
84 }
85
86 PackBitmapIndex getPackBitmapIndex() {
87 return packIndex;
88 }
89
90
91 @Override
92 public CompressedBitmap getBitmap(AnyObjectId objectId) {
93 EWAHCompressedBitmap compressed = packIndex.getBitmap(objectId);
94 if (compressed == null)
95 return null;
96 return new CompressedBitmap(compressed, this);
97 }
98
99
100 @Override
101 public CompressedBitmapBuilder newBitmapBuilder() {
102 return new CompressedBitmapBuilder(this);
103 }
104
105 int findPosition(AnyObjectId objectId) {
106 int position = packIndex.findPosition(objectId);
107 if (position < 0) {
108 position = mutableIndex.findPosition(objectId);
109 if (position >= 0)
110 position += indexObjectCount;
111 }
112 return position;
113 }
114
115 int findOrInsert(AnyObjectId objectId, int type) {
116 int position = findPosition(objectId);
117 if (position < 0) {
118 position = mutableIndex.findOrInsert(objectId, type);
119 position += indexObjectCount;
120 }
121 return position;
122 }
123
124 private static final class ComboBitset {
125 private InflatingBitSet inflatingBitmap;
126
127 private BitSet toAdd;
128
129 private BitSet toRemove;
130
131 ComboBitset() {
132 this(new EWAHCompressedBitmap());
133 }
134
135 ComboBitset(EWAHCompressedBitmap bitmap) {
136 this.inflatingBitmap = new InflatingBitSet(bitmap);
137 }
138
139 EWAHCompressedBitmap combine() {
140 EWAHCompressedBitmap toAddCompressed = null;
141 if (toAdd != null) {
142 toAddCompressed = toAdd.toEWAHCompressedBitmap();
143 toAdd = null;
144 }
145
146 EWAHCompressedBitmap toRemoveCompressed = null;
147 if (toRemove != null) {
148 toRemoveCompressed = toRemove.toEWAHCompressedBitmap();
149 toRemove = null;
150 }
151
152 if (toAddCompressed != null)
153 or(toAddCompressed);
154 if (toRemoveCompressed != null)
155 andNot(toRemoveCompressed);
156 return inflatingBitmap.getBitmap();
157 }
158
159 void or(EWAHCompressedBitmap inbits) {
160 if (toRemove != null)
161 combine();
162 inflatingBitmap = inflatingBitmap.or(inbits);
163 }
164
165 void andNot(EWAHCompressedBitmap inbits) {
166 if (toAdd != null || toRemove != null)
167 combine();
168 inflatingBitmap = inflatingBitmap.andNot(inbits);
169 }
170
171 void xor(EWAHCompressedBitmap inbits) {
172 if (toAdd != null || toRemove != null)
173 combine();
174 inflatingBitmap = inflatingBitmap.xor(inbits);
175 }
176
177 boolean contains(int position) {
178 if (toRemove != null && toRemove.get(position))
179 return false;
180 if (toAdd != null && toAdd.get(position))
181 return true;
182 return inflatingBitmap.contains(position);
183 }
184
185 void remove(int position) {
186 if (toAdd != null)
187 toAdd.clear(position);
188
189 if (inflatingBitmap.maybeContains(position)) {
190 if (toRemove == null)
191 toRemove = new BitSet(position + EXTRA_BITS);
192 toRemove.set(position);
193 }
194 }
195
196 void set(int position) {
197 if (toRemove != null)
198 toRemove.clear(position);
199
200 if (toAdd == null)
201 toAdd = new BitSet(position + EXTRA_BITS);
202 toAdd.set(position);
203 }
204 }
205
206 private static final class CompressedBitmapBuilder implements BitmapBuilder {
207 private ComboBitset bitset;
208 private final BitmapIndexImpl bitmapIndex;
209
210 CompressedBitmapBuilder(BitmapIndexImpl bitmapIndex) {
211 this.bitset = new ComboBitset();
212 this.bitmapIndex = bitmapIndex;
213 }
214
215 @Override
216 public boolean contains(AnyObjectId objectId) {
217 int position = bitmapIndex.findPosition(objectId);
218 return 0 <= position && bitset.contains(position);
219 }
220
221 @Override
222 public BitmapBuilder addObject(AnyObjectId objectId, int type) {
223 bitset.set(bitmapIndex.findOrInsert(objectId, type));
224 return this;
225 }
226
227 @Override
228 public void remove(AnyObjectId objectId) {
229 int position = bitmapIndex.findPosition(objectId);
230 if (0 <= position)
231 bitset.remove(position);
232 }
233
234 @Override
235 public CompressedBitmapBuilder or(Bitmap other) {
236 bitset.or(ewahBitmap(other));
237 return this;
238 }
239
240 @Override
241 public CompressedBitmapBuilder andNot(Bitmap other) {
242 bitset.andNot(ewahBitmap(other));
243 return this;
244 }
245
246 @Override
247 public CompressedBitmapBuilder xor(Bitmap other) {
248 bitset.xor(ewahBitmap(other));
249 return this;
250 }
251
252
253 @Override
254 public CompressedBitmap build() {
255 return new CompressedBitmap(bitset.combine(), bitmapIndex);
256 }
257
258 @Override
259 public Iterator<BitmapObject> iterator() {
260 return build().iterator();
261 }
262
263 @Override
264 public int cardinality() {
265 return bitset.combine().cardinality();
266 }
267
268 @Override
269 public boolean removeAllOrNone(PackBitmapIndex index) {
270 if (!bitmapIndex.packIndex.equals(index))
271 return false;
272
273 EWAHCompressedBitmap curr = bitset.combine()
274 .xor(ones(bitmapIndex.indexObjectCount));
275
276 IntIterator ii = curr.intIterator();
277 if (ii.hasNext() && ii.next() < bitmapIndex.indexObjectCount)
278 return false;
279 bitset = new ComboBitset(curr);
280 return true;
281 }
282
283 @Override
284 public BitmapIndexImpl getBitmapIndex() {
285 return bitmapIndex;
286 }
287
288 private EWAHCompressedBitmap ewahBitmap(Bitmap other) {
289 if (other instanceof CompressedBitmap) {
290 CompressedBitmap b = (CompressedBitmap) other;
291 if (b.bitmapIndex != bitmapIndex) {
292 throw new IllegalArgumentException();
293 }
294 return b.bitmap;
295 }
296 if (other instanceof CompressedBitmapBuilder) {
297 CompressedBitmapBuilder b = (CompressedBitmapBuilder) other;
298 if (b.bitmapIndex != bitmapIndex) {
299 throw new IllegalArgumentException();
300 }
301 return b.bitset.combine();
302 }
303 throw new IllegalArgumentException();
304 }
305 }
306
307
308
309
310
311
312
313
314 public static final class CompressedBitmap implements Bitmap {
315 final EWAHCompressedBitmap bitmap;
316 final BitmapIndexImpl bitmapIndex;
317
318
319
320
321
322
323
324 public CompressedBitmap(EWAHCompressedBitmap bitmap, BitmapIndexImpl bitmapIndex) {
325 this.bitmap = bitmap;
326 this.bitmapIndex = bitmapIndex;
327 }
328
329 @Override
330 public CompressedBitmap or(Bitmap other) {
331 return new CompressedBitmap(bitmap.or(ewahBitmap(other)), bitmapIndex);
332 }
333
334 @Override
335 public CompressedBitmap andNot(Bitmap other) {
336 return new CompressedBitmap(bitmap.andNot(ewahBitmap(other)), bitmapIndex);
337 }
338
339 @Override
340 public CompressedBitmap xor(Bitmap other) {
341 return new CompressedBitmap(bitmap.xor(ewahBitmap(other)), bitmapIndex);
342 }
343
344 private final IntIterator ofObjectType(int type) {
345 return bitmapIndex.packIndex.ofObjectType(bitmap, type).intIterator();
346 }
347
348 @Override
349 public Iterator<BitmapObject> iterator() {
350 final IntIterator dynamic = bitmap.andNot(ones(bitmapIndex.indexObjectCount))
351 .intIterator();
352 final IntIterator commits = ofObjectType(Constants.OBJ_COMMIT);
353 final IntIterator trees = ofObjectType(Constants.OBJ_TREE);
354 final IntIterator blobs = ofObjectType(Constants.OBJ_BLOB);
355 final IntIterator tags = ofObjectType(Constants.OBJ_TAG);
356 return new Iterator<BitmapObject>() {
357 private final BitmapObjectImpl out = new BitmapObjectImpl();
358 private int type;
359 private IntIterator cached = dynamic;
360
361 @Override
362 public boolean hasNext() {
363 if (!cached.hasNext()) {
364 if (commits.hasNext()) {
365 type = Constants.OBJ_COMMIT;
366 cached = commits;
367 } else if (trees.hasNext()) {
368 type = Constants.OBJ_TREE;
369 cached = trees;
370 } else if (blobs.hasNext()) {
371 type = Constants.OBJ_BLOB;
372 cached = blobs;
373 } else if (tags.hasNext()) {
374 type = Constants.OBJ_TAG;
375 cached = tags;
376 } else {
377 return false;
378 }
379 }
380 return true;
381 }
382
383 @Override
384 public BitmapObject next() {
385 if (!hasNext())
386 throw new NoSuchElementException();
387
388 int position = cached.next();
389 if (position < bitmapIndex.indexObjectCount) {
390 out.type = type;
391 out.objectId = bitmapIndex.packIndex.getObject(position);
392 } else {
393 position -= bitmapIndex.indexObjectCount;
394 MutableEntry entry = bitmapIndex.mutableIndex.getObject(position);
395 out.type = entry.type;
396 out.objectId = entry;
397 }
398 return out;
399 }
400
401 @Override
402 public void remove() {
403 throw new UnsupportedOperationException();
404 }
405 };
406 }
407
408 EWAHCompressedBitmap getEwahCompressedBitmap() {
409 return bitmap;
410 }
411
412 private EWAHCompressedBitmap ewahBitmap(Bitmap other) {
413 if (other instanceof CompressedBitmap) {
414 CompressedBitmap b = (CompressedBitmap) other;
415 if (b.bitmapIndex != bitmapIndex) {
416 throw new IllegalArgumentException();
417 }
418 return b.bitmap;
419 }
420 if (other instanceof CompressedBitmapBuilder) {
421 CompressedBitmapBuilder b = (CompressedBitmapBuilder) other;
422 if (b.bitmapIndex != bitmapIndex) {
423 throw new IllegalArgumentException();
424 }
425 return b.bitset.combine();
426 }
427 throw new IllegalArgumentException();
428 }
429 }
430
431 private static final class MutableBitmapIndex {
432 private final ObjectIdOwnerMap<MutableEntry>
433 revMap = new ObjectIdOwnerMap<>();
434
435 private final BlockList<MutableEntry>
436 revList = new BlockList<>();
437
438 int findPosition(AnyObjectId objectId) {
439 MutableEntry entry = revMap.get(objectId);
440 if (entry == null)
441 return -1;
442 return entry.position;
443 }
444
445 MutableEntry getObject(int position) {
446 try {
447 MutableEntry entry = revList.get(position);
448 if (entry == null)
449 throw new IllegalArgumentException(MessageFormat.format(
450 JGitText.get().objectNotFound,
451 String.valueOf(position)));
452 return entry;
453 } catch (IndexOutOfBoundsException ex) {
454 throw new IllegalArgumentException(ex);
455 }
456 }
457
458 int findOrInsert(AnyObjectId objectId, int type) {
459 MutableEntry entry = new MutableEntry(
460 objectId, type, revList.size());
461 revList.add(entry);
462 revMap.add(entry);
463 return entry.position;
464 }
465 }
466
467 private static final class MutableEntry extends ObjectIdOwnerMap.Entry {
468 final int type;
469
470 final int position;
471
472 MutableEntry(AnyObjectId objectId, int type, int position) {
473 super(objectId);
474 this.type = type;
475 this.position = position;
476 }
477 }
478
479 private static final class BitmapObjectImpl extends BitmapObject {
480 private ObjectId objectId;
481
482 private int type;
483
484 @Override
485 public ObjectId getObjectId() {
486 return objectId;
487 }
488
489 @Override
490 public int getType() {
491 return type;
492 }
493 }
494
495 static final EWAHCompressedBitmap ones(int sizeInBits) {
496 EWAHCompressedBitmap mask = new EWAHCompressedBitmap();
497 mask.addStreamOfEmptyWords(
498 true, sizeInBits / EWAHCompressedBitmap.WORD_IN_BITS);
499 int remaining = sizeInBits % EWAHCompressedBitmap.WORD_IN_BITS;
500 if (remaining > 0)
501 mask.addWord((1L << remaining) - 1, remaining);
502 return mask;
503 }
504 }