2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
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
10 * http://www.apache.org/licenses/LICENSE-2.0.
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.
19 package gov.nasa.jpf.util;
23 * a fixed size BitSet with 256 bits.
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
30 * Instances of this class do not allocate any additional memory, we keep all
31 * data in builtin type fields
33 public class BitSet256 extends AbstractFixedBitSet {
35 public static final int INDEX_MASK = 0xffffff00;
43 public BitSet256 (int i){
47 public BitSet256 (int... idx){
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);
61 //--- public interface (much like java.util.BitSet)
64 public void set (int i){
65 if ((i & INDEX_MASK) == 0) {
66 long bitPattern = (1L << i);
70 if ((l0 & bitPattern) == 0L) {
76 if ((l1 & bitPattern) == 0L) {
82 if ((l2 & bitPattern) == 0L) {
88 if ((l3 & bitPattern) == 0L) {
94 throw new IndexOutOfBoundsException("BitSet256 index out of range: " + i);
99 public void clear (int i){
100 if ((i & INDEX_MASK) == 0) {
101 long bitPattern = (1L << i);
105 if ((l0 & bitPattern) != 0L) {
111 if ((l1 & bitPattern) != 0L) {
117 if ((l2 & bitPattern) != 0L) {
123 if ((l3 & bitPattern) != 0L) {
129 throw new IndexOutOfBoundsException("BitSet256 index out of range: " + i);
134 public boolean get (int i){
135 if ((i & INDEX_MASK) == 0) {
136 long bitPattern = (1L << i);
140 return ((l0 & bitPattern) != 0);
142 return ((l1 & bitPattern) != 0);
144 return ((l2 & bitPattern) != 0);
146 return ((l3 & bitPattern) != 0);
150 throw new IndexOutOfBoundsException("BitSet256 index out of range: " + i);
160 * number of bits we can store
163 public int capacity() {
168 * index of highest set bit + 1
171 public int length() {
173 return 256 - Long.numberOfLeadingZeros(l3);
175 return 192 - Long.numberOfLeadingZeros(l2);
177 return 128 - Long.numberOfLeadingZeros(l1);
179 return 64 - Long.numberOfLeadingZeros(l0);
186 public void clear() {
187 l0 = l1 = l2 = l3 = 0L;
193 public int nextSetBit (int fromIdx){
194 if ((fromIdx & INDEX_MASK) == 0) {
196 int i0 = fromIdx & 0x3f;
197 switch (fromIdx >> 6){
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;
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;
210 if ((i=Long.numberOfTrailingZeros(l2 & (0xffffffffffffffffL << i0))) <64) return i + 128;
211 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
214 if ((i=Long.numberOfTrailingZeros(l3 & (0xffffffffffffffffL << i0))) <64) return i + 192;
220 //throw new IndexOutOfBoundsException("BitSet256 index out of range: " + fromIdx);
226 public int nextClearBit (int fromIdx){
227 if ((fromIdx & INDEX_MASK) == 0) {
229 int i0 = fromIdx & 0x3f;
230 switch (fromIdx >> 6){
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;
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;
243 if ((i=Long.numberOfTrailingZeros(~l2 & (0xffffffffffffffffL << i0))) <64) return i + 128;
244 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
247 if ((i=Long.numberOfTrailingZeros(~l3 & (0xffffffffffffffffL << i0))) <64) return i + 192;
253 //throw new IndexOutOfBoundsException("BitSet256 index out of range: " + fromIdx);
258 public void and (BitSet256 other){
264 cardinality = computeCardinality();
267 public void andNot (BitSet256 other){
273 cardinality = computeCardinality();
276 public void or (BitSet256 other){
282 cardinality = computeCardinality();
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;
295 // <2do> we could compare to a normal java.util.BitSet here
301 * answer the same hashCodes as java.util.BitSet
304 public int hashCode() {
310 return (int) ((hc >>32) ^ hc);
314 public void hash (HashData hd){
322 public String toString() {
323 StringBuilder sb = new StringBuilder();
326 boolean first = true;
327 for (int i=nextSetBit(0); i>= 0; i = nextSetBit(i+1)){
338 return sb.toString();