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 @Override
256 public EWAHCompressedBitmap retrieveCompressed() {
257 return build().retrieveCompressed();
258 }
259
260 private EWAHCompressedBitmap ewahBitmap(Bitmap other) {
261 if (other instanceof CompressedBitmap) {
262 CompressedBitmap b = (CompressedBitmap) other;
263 if (b.bitmapIndex != bitmapIndex) {
264 throw new IllegalArgumentException();
265 }
266 return b.bitmap;
267 }
268 if (other instanceof CompressedBitmapBuilder) {
269 CompressedBitmapBuilder b = (CompressedBitmapBuilder) other;
270 if (b.bitmapIndex != bitmapIndex) {
271 throw new IllegalArgumentException();
272 }
273 return b.bitset.combine();
274 }
275 throw new IllegalArgumentException();
276 }
277 }
278
279
280
281
282
283
284
285
286 public static final class CompressedBitmap implements Bitmap {
287 final EWAHCompressedBitmap bitmap;
288 final BitmapIndexImpl bitmapIndex;
289
290
291
292
293
294
295
296 public CompressedBitmap(EWAHCompressedBitmap bitmap, BitmapIndexImpl bitmapIndex) {
297 this.bitmap = bitmap;
298 this.bitmapIndex = bitmapIndex;
299 }
300
301 @Override
302 public CompressedBitmap or(Bitmap other) {
303 return new CompressedBitmap(bitmap.or(ewahBitmap(other)), bitmapIndex);
304 }
305
306 @Override
307 public CompressedBitmap andNot(Bitmap other) {
308 return new CompressedBitmap(bitmap.andNot(ewahBitmap(other)), bitmapIndex);
309 }
310
311 @Override
312 public CompressedBitmap xor(Bitmap other) {
313 return new CompressedBitmap(bitmap.xor(ewahBitmap(other)), bitmapIndex);
314 }
315
316 private final IntIterator ofObjectType(int type) {
317 return bitmapIndex.packIndex.ofObjectType(bitmap, type).intIterator();
318 }
319
320 @Override
321 public Iterator<BitmapObject> iterator() {
322 final IntIterator dynamic = bitmap.andNot(ones(bitmapIndex.indexObjectCount))
323 .intIterator();
324 final IntIterator commits = ofObjectType(Constants.OBJ_COMMIT);
325 final IntIterator trees = ofObjectType(Constants.OBJ_TREE);
326 final IntIterator blobs = ofObjectType(Constants.OBJ_BLOB);
327 final IntIterator tags = ofObjectType(Constants.OBJ_TAG);
328 return new Iterator<BitmapObject>() {
329 private final BitmapObjectImpl out = new BitmapObjectImpl();
330 private int type;
331 private IntIterator cached = dynamic;
332
333 @Override
334 public boolean hasNext() {
335 if (!cached.hasNext()) {
336 if (commits.hasNext()) {
337 type = Constants.OBJ_COMMIT;
338 cached = commits;
339 } else if (trees.hasNext()) {
340 type = Constants.OBJ_TREE;
341 cached = trees;
342 } else if (blobs.hasNext()) {
343 type = Constants.OBJ_BLOB;
344 cached = blobs;
345 } else if (tags.hasNext()) {
346 type = Constants.OBJ_TAG;
347 cached = tags;
348 } else {
349 return false;
350 }
351 }
352 return true;
353 }
354
355 @Override
356 public BitmapObject next() {
357 if (!hasNext())
358 throw new NoSuchElementException();
359
360 int position = cached.next();
361 if (position < bitmapIndex.indexObjectCount) {
362 out.type = type;
363 out.objectId = bitmapIndex.packIndex.getObject(position);
364 } else {
365 position -= bitmapIndex.indexObjectCount;
366 MutableEntry entry = bitmapIndex.mutableIndex.getObject(position);
367 out.type = entry.type;
368 out.objectId = entry;
369 }
370 return out;
371 }
372
373 @Override
374 public void remove() {
375 throw new UnsupportedOperationException();
376 }
377 };
378 }
379
380 @Override
381 public EWAHCompressedBitmap retrieveCompressed() {
382 return bitmap;
383 }
384
385 private EWAHCompressedBitmap ewahBitmap(Bitmap other) {
386 if (other instanceof CompressedBitmap) {
387 CompressedBitmap b = (CompressedBitmap) other;
388 if (b.bitmapIndex != bitmapIndex) {
389 throw new IllegalArgumentException();
390 }
391 return b.bitmap;
392 }
393 if (other instanceof CompressedBitmapBuilder) {
394 CompressedBitmapBuilder b = (CompressedBitmapBuilder) other;
395 if (b.bitmapIndex != bitmapIndex) {
396 throw new IllegalArgumentException();
397 }
398 return b.bitset.combine();
399 }
400 throw new IllegalArgumentException();
401 }
402 }
403
404 private static final class MutableBitmapIndex {
405 private final ObjectIdOwnerMap<MutableEntry>
406 revMap = new ObjectIdOwnerMap<>();
407
408 private final BlockList<MutableEntry>
409 revList = new BlockList<>();
410
411 int findPosition(AnyObjectId objectId) {
412 MutableEntry entry = revMap.get(objectId);
413 if (entry == null)
414 return -1;
415 return entry.position;
416 }
417
418 MutableEntry getObject(int position) {
419 try {
420 MutableEntry entry = revList.get(position);
421 if (entry == null)
422 throw new IllegalArgumentException(MessageFormat.format(
423 JGitText.get().objectNotFound,
424 String.valueOf(position)));
425 return entry;
426 } catch (IndexOutOfBoundsException ex) {
427 throw new IllegalArgumentException(ex);
428 }
429 }
430
431 int findOrInsert(AnyObjectId objectId, int type) {
432 MutableEntry entry = new MutableEntry(
433 objectId, type, revList.size());
434 revList.add(entry);
435 revMap.add(entry);
436 return entry.position;
437 }
438 }
439
440 private static final class MutableEntry extends ObjectIdOwnerMap.Entry {
441 final int type;
442
443 final int position;
444
445 MutableEntry(AnyObjectId objectId, int type, int position) {
446 super(objectId);
447 this.type = type;
448 this.position = position;
449 }
450 }
451
452 private static final class BitmapObjectImpl extends BitmapObject {
453 private ObjectId objectId;
454
455 private int type;
456
457 @Override
458 public ObjectId getObjectId() {
459 return objectId;
460 }
461
462 @Override
463 public int getType() {
464 return type;
465 }
466 }
467
468 static final EWAHCompressedBitmap ones(int sizeInBits) {
469 EWAHCompressedBitmap mask = new EWAHCompressedBitmap();
470 mask.addStreamOfEmptyWords(
471 true, sizeInBits / EWAHCompressedBitmap.WORD_IN_BITS);
472 int remaining = sizeInBits % EWAHCompressedBitmap.WORD_IN_BITS;
473 if (remaining > 0)
474 mask.addWord((1L << remaining) - 1, remaining);
475 return mask;
476 }
477 }