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