Mercurial > hg > Members > kono > jpf-core

comparison src/main/gov/nasa/jpf/util/BitSet256.java @ 0:61d41facf527

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial v8 import (history reset)
author Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
date Fri, 23 Jan 2015 10:14:01 -0800
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:61d41facf527
1 /*
2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
4 * All rights reserved.
5 *
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
8 * in compliance with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0.
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 package gov.nasa.jpf.util;
20
21
22 /**
23 * a fixed size BitSet with 256 bits.
24 *
25 * The main motivation for this class is to minimize memory size while maximizing
26 * performance and keeping a java.util.BitSet compatible interface. The only
27 * deviation from the standard BitSet is that we assume more cardinality() calls
28 * than set()/clear() calls, i.e. we want to cache this value
29 *
30 * Instances of this class do not allocate any additional memory, we keep all
31 * data in builtin type fields
32 */
33 public class BitSet256 extends AbstractFixedBitSet {
34
35 public static final int INDEX_MASK = 0xffffff00;
36
37 long l0, l1, l2, l3;
38
39 public BitSet256 (){
40 // nothing in here
41 }
42
43 public BitSet256 (int i){
44 set(i);
45 }
46
47 public BitSet256 (int... idx){
48 for (int i : idx){
49 set(i);
50 }
51 }
52
53 private final int computeCardinality (){
54 int n= Long.bitCount(l0);
55 n += Long.bitCount(l1);
56 n += Long.bitCount(l2);
57 n += Long.bitCount(l3);
58 return n;
59 }
60
61 //--- public interface (much like java.util.BitSet)
62
63 @Override
64 public void set (int i){
65 if ((i & INDEX_MASK) == 0) {
66 long bitPattern = (1L << i);
67
68 switch (i >> 6) {
69 case 0:
70 if ((l0 & bitPattern) == 0L) {
71 cardinality++;
72 l0 |= bitPattern;
73 }
74 break;
75 case 1:
76 if ((l1 & bitPattern) == 0L) {
77 cardinality++;
78 l1 |= bitPattern;
79 }
80 break;
81 case 2:
82 if ((l2 & bitPattern) == 0L) {
83 cardinality++;
84 l2 |= bitPattern;
85 }
86 break;
87 case 3:
88 if ((l3 & bitPattern) == 0L) {
89 cardinality++;
90 l3 |= bitPattern;
91 }
92 }
93 } else {
94 throw new IndexOutOfBoundsException("BitSet256 index out of range: " + i);
95 }
96 }
97
98 @Override
99 public void clear (int i){
100 if ((i & INDEX_MASK) == 0) {
101 long bitPattern = (1L << i);
102
103 switch (i >> 6) {
104 case 0:
105 if ((l0 & bitPattern) != 0L) {
106 cardinality--;
107 l0 &= ~bitPattern;
108 }
109 break;
110 case 1:
111 if ((l1 & bitPattern) != 0L) {
112 cardinality--;
113 l1 &= ~bitPattern;
114 }
115 break;
116 case 2:
117 if ((l2 & bitPattern) != 0L) {
118 cardinality--;
119 l2 &= ~bitPattern;
120 }
121 break;
122 case 3:
123 if ((l3 & bitPattern) != 0L) {
124 cardinality--;
125 l3 &= ~bitPattern;
126 }
127 }
128 } else {
129 throw new IndexOutOfBoundsException("BitSet256 index out of range: " + i);
130 }
131 }
132
133 @Override
134 public boolean get (int i){
135 if ((i & INDEX_MASK) == 0) {
136 long bitPattern = (1L << i);
137
138 switch (i >> 6) {
139 case 0:
140 return ((l0 & bitPattern) != 0);
141 case 1:
142 return ((l1 & bitPattern) != 0);
143 case 2:
144 return ((l2 & bitPattern) != 0);
145 case 3:
146 return ((l3 & bitPattern) != 0);
147 }
148 }
149
150 throw new IndexOutOfBoundsException("BitSet256 index out of range: " + i);
151 }
152
153 @Override
154 public int size() {
155 return 256;
156 }
157
158
159 /**
160 * number of bits we can store
161 */
162 @Override
163 public int capacity() {
164 return 256;
165 }
166
167 /**
168 * index of highest set bit + 1
169 */
170 @Override
171 public int length() {
172 if (l3 != 0){
173 return 256 - Long.numberOfLeadingZeros(l3);
174 } else if (l2 != 0){
175 return 192 - Long.numberOfLeadingZeros(l2);
176 } else if (l1 != 0){
177 return 128 - Long.numberOfLeadingZeros(l1);
178 } else if (l1 != 0){
179 return 64 - Long.numberOfLeadingZeros(l0);
180 } else {
181 return 0;
182 }
183 }
184
185 @Override
186 public void clear() {
187 l0 = l1 = l2 = l3 = 0L;
188 cardinality = 0;
189 }
190
191
192 @Override
193 public int nextSetBit (int fromIdx){
194 if ((fromIdx & INDEX_MASK) == 0) {
195 int i;
196 int i0 = fromIdx & 0x3f;
197 switch (fromIdx >> 6){
198 case 0:
199 if ((i=Long.numberOfTrailingZeros(l0 & (0xffffffffffffffffL << i0))) <64) return i;
200 if ((i=Long.numberOfTrailingZeros(l1)) <64) return i + 64;
201 if ((i=Long.numberOfTrailingZeros(l2)) <64) return i + 128;
202 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
203 break;
204 case 1:
205 if ((i=Long.numberOfTrailingZeros(l1 & (0xffffffffffffffffL << i0))) <64) return i + 64;
206 if ((i=Long.numberOfTrailingZeros(l2)) <64) return i + 128;
207 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
208 break;
209 case 2:
210 if ((i=Long.numberOfTrailingZeros(l2 & (0xffffffffffffffffL << i0))) <64) return i + 128;
211 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
212 break;
213 case 3:
214 if ((i=Long.numberOfTrailingZeros(l3 & (0xffffffffffffffffL << i0))) <64) return i + 192;
215 }
216
217 return -1;
218
219 } else {
220 //throw new IndexOutOfBoundsException("BitSet256 index out of range: " + fromIdx);
221 return -1;
222 }
223 }
224
225 @Override
226 public int nextClearBit (int fromIdx){
227 if ((fromIdx & INDEX_MASK) == 0) {
228 int i;
229 int i0 = fromIdx & 0x3f;
230 switch (fromIdx >> 6){
231 case 0:
232 if ((i=Long.numberOfTrailingZeros(~l0 & (0xffffffffffffffffL << i0))) <64) return i;
233 if ((i=Long.numberOfTrailingZeros(~l1)) <64) return i + 64;
234 if ((i=Long.numberOfTrailingZeros(~l2)) <64) return i + 128;
235 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
236 break;
237 case 1:
238 if ((i=Long.numberOfTrailingZeros(~l1 & (0xffffffffffffffffL << i0))) <64) return i + 64;
239 if ((i=Long.numberOfTrailingZeros(~l2)) <64) return i + 128;
240 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
241 break;
242 case 2:
243 if ((i=Long.numberOfTrailingZeros(~l2 & (0xffffffffffffffffL << i0))) <64) return i + 128;
244 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
245 break;
246 case 3:
247 if ((i=Long.numberOfTrailingZeros(~l3 & (0xffffffffffffffffL << i0))) <64) return i + 192;
248 }
249
250 return -1;
251
252 } else {
253 //throw new IndexOutOfBoundsException("BitSet256 index out of range: " + fromIdx);
254 return -1;
255 }
256 }
257
258 public void and (BitSet256 other){
259 l0 &= other.l0;
260 l1 &= other.l1;
261 l2 &= other.l2;
262 l3 &= other.l3;
263
264 cardinality = computeCardinality();
265 }
266
267 public void andNot (BitSet256 other){
268 l0 &= ~other.l0;
269 l1 &= ~other.l1;
270 l2 &= ~other.l2;
271 l3 &= ~other.l3;
272
273 cardinality = computeCardinality();
274 }
275
276 public void or (BitSet256 other){
277 l0 |= other.l0;
278 l1 |= other.l1;
279 l2 |= other.l2;
280 l3 |= other.l3;
281
282 cardinality = computeCardinality();
283 }
284
285 @Override
286 public boolean equals (Object o){
287 if (o instanceof BitSet256){
288 BitSet256 other = (BitSet256)o;
289 if (l0 != other.l0) return false;
290 if (l1 != other.l1) return false;
291 if (l2 != other.l2) return false;
292 if (l3 != other.l3) return false;
293 return true;
294 } else {
295 // <2do> we could compare to a normal java.util.BitSet here
296 return false;
297 }
298 }
299
300 /**
301 * answer the same hashCodes as java.util.BitSet
302 */
303 @Override
304 public int hashCode() {
305 long hc = 1234;
306 hc ^= l0;
307 hc ^= l1*2;
308 hc ^= l2*3;
309 hc ^= l3*4;
310 return (int) ((hc >>32) ^ hc);
311 }
312
313 @Override
314 public void hash (HashData hd){
315 hd.add(l0);
316 hd.add(l1);
317 hd.add(l2);
318 hd.add(l3);
319 }
320
321 @Override
322 public String toString() {
323 StringBuilder sb = new StringBuilder();
324 sb.append('{');
325
326 boolean first = true;
327 for (int i=nextSetBit(0); i>= 0; i = nextSetBit(i+1)){
328 if (!first){
329 sb.append(',');
330 } else {
331 first = false;
332 }
333 sb.append(i);
334 }
335
336 sb.append('}');
337
338 return sb.toString();
339 }
340 }