1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.file;
12
13 import com.googlecode.javaewah.EWAHCompressedBitmap;
14 import com.googlecode.javaewah.IntIterator;
15
16
17
18
19
20 final class InflatingBitSet {
21 private static final long[] EMPTY = new long[0];
22
23 private final EWAHCompressedBitmap bitmap;
24
25 private IntIterator iterator;
26
27 private long[] inflated;
28
29 private int nextPosition = -1;
30
31 private final int sizeInBits;
32
33 InflatingBitSet(EWAHCompressedBitmap bitmap) {
34 this(bitmap, EMPTY);
35 }
36
37 private InflatingBitSet(EWAHCompressedBitmap orBitmap, long[] inflated) {
38 this.bitmap = orBitmap;
39 this.inflated = inflated;
40 this.sizeInBits = bitmap.sizeInBits();
41 }
42
43 final boolean maybeContains(int position) {
44 if (get(position))
45 return true;
46 return nextPosition <= position && position < sizeInBits;
47 }
48
49 final boolean contains(int position) {
50 if (get(position))
51 return true;
52 if (position <= nextPosition || position >= sizeInBits)
53 return position == nextPosition;
54
55 if (iterator == null) {
56 iterator = bitmap.intIterator();
57 if (iterator.hasNext())
58 nextPosition = iterator.next();
59 else
60 return false;
61 } else if (!iterator.hasNext())
62 return false;
63
64 int positionBlock = block(position);
65 if (positionBlock >= inflated.length) {
66 long[] tmp = new long[block(sizeInBits) + 1];
67 System.arraycopy(inflated, 0, tmp, 0, inflated.length);
68 inflated = tmp;
69 }
70
71 int block = block(nextPosition);
72 long word = mask(nextPosition);
73 int end = Math.max(nextPosition, position) | 63;
74 while (iterator.hasNext()) {
75 nextPosition = iterator.next();
76 if (end < nextPosition)
77 break;
78
79 int b = block(nextPosition);
80 long m = mask(nextPosition);
81 if (block == b) {
82 word |= m;
83 } else {
84 inflated[block] = word;
85 block = b;
86 word = m;
87 }
88 }
89 inflated[block] = word;
90 return block == positionBlock && (word & mask(position)) != 0;
91 }
92
93 private final boolean get(int position) {
94 int b = block(position);
95 return b < inflated.length && (inflated[b] & mask(position)) != 0;
96 }
97
98 private static final int block(int position) {
99 return position >> 6;
100 }
101
102 private static final long mask(int position) {
103 return 1L << position;
104 }
105
106 private final boolean isEmpty() {
107 return sizeInBits == 0;
108 }
109
110 final InflatingBitSet or(EWAHCompressedBitmap other) {
111 if (other.sizeInBits() == 0)
112 return this;
113 return new InflatingBitSet(bitmap.or(other), inflated);
114 }
115
116 final InflatingBitSet andNot(EWAHCompressedBitmap other) {
117 if (isEmpty())
118 return this;
119 return new InflatingBitSet(bitmap.andNot(other));
120 }
121
122 final InflatingBitSet xor(EWAHCompressedBitmap other) {
123 if (isEmpty()) {
124 if (other.sizeInBits() == 0)
125 return this;
126 return new InflatingBitSet(other);
127 }
128 return new InflatingBitSet(bitmap.xor(other));
129 }
130
131 final EWAHCompressedBitmap getBitmap() {
132 return bitmap;
133 }
134 }