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 com.googlecode.javaewah.EWAHCompressedBitmap;
47 import com.googlecode.javaewah.IntIterator;
48
49
50
51
52
53 final class InflatingBitSet {
54 private static final long[] EMPTY = new long[0];
55
56 private final EWAHCompressedBitmap bitmap;
57
58 private IntIterator iterator;
59
60 private long[] inflated;
61
62 private int nextPosition = -1;
63
64 private final int sizeInBits;
65
66 InflatingBitSet(EWAHCompressedBitmap bitmap) {
67 this(bitmap, EMPTY);
68 }
69
70 private InflatingBitSet(EWAHCompressedBitmap orBitmap, long[] inflated) {
71 this.bitmap = orBitmap;
72 this.inflated = inflated;
73 this.sizeInBits = bitmap.sizeInBits();
74 }
75
76 final boolean maybeContains(int position) {
77 if (get(position))
78 return true;
79 return nextPosition <= position && position < sizeInBits;
80 }
81
82 final boolean contains(int position) {
83 if (get(position))
84 return true;
85 if (position <= nextPosition || position >= sizeInBits)
86 return position == nextPosition;
87
88 if (iterator == null) {
89 iterator = bitmap.intIterator();
90 if (iterator.hasNext())
91 nextPosition = iterator.next();
92 else
93 return false;
94 } else if (!iterator.hasNext())
95 return false;
96
97 int positionBlock = block(position);
98 if (positionBlock >= inflated.length) {
99 long[] tmp = new long[block(sizeInBits) + 1];
100 System.arraycopy(inflated, 0, tmp, 0, inflated.length);
101 inflated = tmp;
102 }
103
104 int block = block(nextPosition);
105 long word = mask(nextPosition);
106 int end = Math.max(nextPosition, position) | 63;
107 while (iterator.hasNext()) {
108 nextPosition = iterator.next();
109 if (end < nextPosition)
110 break;
111
112 int b = block(nextPosition);
113 long m = mask(nextPosition);
114 if (block == b) {
115 word |= m;
116 } else {
117 inflated[block] = word;
118 block = b;
119 word = m;
120 }
121 }
122 inflated[block] = word;
123 return block == positionBlock && (word & mask(position)) != 0;
124 }
125
126 private final boolean get(int position) {
127 int b = block(position);
128 return b < inflated.length && (inflated[b] & mask(position)) != 0;
129 }
130
131 private static final int block(int position) {
132 return position >> 6;
133 }
134
135 private static final long mask(int position) {
136 return 1L << position;
137 }
138
139 private final boolean isEmpty() {
140 return sizeInBits == 0;
141 }
142
143 final InflatingBitSet or(EWAHCompressedBitmap other) {
144 if (other.sizeInBits() == 0)
145 return this;
146 return new InflatingBitSet(bitmap.or(other), inflated);
147 }
148
149 final InflatingBitSet andNot(EWAHCompressedBitmap other) {
150 if (isEmpty())
151 return this;
152 return new InflatingBitSet(bitmap.andNot(other));
153 }
154
155 final InflatingBitSet xor(EWAHCompressedBitmap other) {
156 if (isEmpty()) {
157 if (other.sizeInBits() == 0)
158 return this;
159 return new InflatingBitSet(other);
160 }
161 return new InflatingBitSet(bitmap.xor(other));
162 }
163
164 final EWAHCompressedBitmap getBitmap() {
165 return bitmap;
166 }
167 }