< prev index next >

src/java.base/share/classes/java/util/BitSet.java

Print this page




  66 public class BitSet implements Cloneable, java.io.Serializable {
  67     /*
  68      * BitSets are packed into arrays of "words."  Currently a word is
  69      * a long, which consists of 64 bits, requiring 6 address bits.
  70      * The choice of word size is determined purely by performance concerns.
  71      */
  72     private static final int ADDRESS_BITS_PER_WORD = 6;
  73     private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
  74     private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1;
  75 
  76     /* Used to shift left or right for a partial word mask */
  77     private static final long WORD_MASK = 0xffffffffffffffffL;
  78 
  79     /**
  80      * @serialField bits long[]
  81      *
  82      * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
  83      * bit position i % 64 (where bit position 0 refers to the least
  84      * significant bit and 63 refers to the most significant bit).
  85      */

  86     private static final ObjectStreamField[] serialPersistentFields = {
  87         new ObjectStreamField("bits", long[].class),
  88     };
  89 
  90     /**
  91      * The internal field corresponding to the serialField "bits".
  92      */
  93     private long[] words;
  94 
  95     /**
  96      * The number of words in the logical size of this BitSet.
  97      */
  98     private transient int wordsInUse = 0;
  99 
 100     /**
 101      * Whether the size of "words" is user-specified.  If so, we assume
 102      * the user knows what he's doing and try harder to preserve it.
 103      */
 104     private transient boolean sizeIsSticky = false;
 105 
 106     /* use serialVersionUID from JDK 1.0.2 for interoperability */

 107     private static final long serialVersionUID = 7997698588986878753L;
 108 
 109     /**
 110      * Given a bit index, return word index containing it.
 111      */
 112     private static int wordIndex(int bitIndex) {
 113         return bitIndex >> ADDRESS_BITS_PER_WORD;
 114     }
 115 
 116     /**
 117      * Every public method must preserve these invariants.
 118      */
 119     private void checkInvariants() {
 120         assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
 121         assert(wordsInUse >= 0 && wordsInUse <= words.length);
 122         assert(wordsInUse == words.length || words[wordsInUse] == 0);
 123     }
 124 
 125     /**
 126      * Sets the field wordsInUse to the logical size in words of the bit set.


1107             throw new InternalError(e);
1108         }
1109     }
1110 
1111     /**
1112      * Attempts to reduce internal storage used for the bits in this bit set.
1113      * Calling this method may, but is not required to, affect the value
1114      * returned by a subsequent call to the {@link #size()} method.
1115      */
1116     private void trimToSize() {
1117         if (wordsInUse != words.length) {
1118             words = Arrays.copyOf(words, wordsInUse);
1119             checkInvariants();
1120         }
1121     }
1122 
1123     /**
1124      * Save the state of the {@code BitSet} instance to a stream (i.e.,
1125      * serialize it).
1126      */

1127     private void writeObject(ObjectOutputStream s)
1128         throws IOException {
1129 
1130         checkInvariants();
1131 
1132         if (! sizeIsSticky)
1133             trimToSize();
1134 
1135         ObjectOutputStream.PutField fields = s.putFields();
1136         fields.put("bits", words);
1137         s.writeFields();
1138     }
1139 
1140     /**
1141      * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1142      * deserialize it).
1143      */

1144     private void readObject(ObjectInputStream s)
1145         throws IOException, ClassNotFoundException {
1146 
1147         ObjectInputStream.GetField fields = s.readFields();
1148         words = (long[]) fields.get("bits", null);
1149 
1150         // Assume maximum length then find real length
1151         // because recalculateWordsInUse assumes maintenance
1152         // or reduction in logical size
1153         wordsInUse = words.length;
1154         recalculateWordsInUse();
1155         sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1156         checkInvariants();
1157     }
1158 
1159     /**
1160      * Returns a string representation of this bit set. For every index
1161      * for which this {@code BitSet} contains a bit in the set
1162      * state, the decimal representation of that index is included in
1163      * the result. Such indices are listed in order from lowest to




  66 public class BitSet implements Cloneable, java.io.Serializable {
  67     /*
  68      * BitSets are packed into arrays of "words."  Currently a word is
  69      * a long, which consists of 64 bits, requiring 6 address bits.
  70      * The choice of word size is determined purely by performance concerns.
  71      */
  72     private static final int ADDRESS_BITS_PER_WORD = 6;
  73     private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
  74     private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1;
  75 
  76     /* Used to shift left or right for a partial word mask */
  77     private static final long WORD_MASK = 0xffffffffffffffffL;
  78 
  79     /**
  80      * @serialField bits long[]
  81      *
  82      * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
  83      * bit position i % 64 (where bit position 0 refers to the least
  84      * significant bit and 63 refers to the most significant bit).
  85      */
  86     @java.io.Serial
  87     private static final ObjectStreamField[] serialPersistentFields = {
  88         new ObjectStreamField("bits", long[].class),
  89     };
  90 
  91     /**
  92      * The internal field corresponding to the serialField "bits".
  93      */
  94     private long[] words;
  95 
  96     /**
  97      * The number of words in the logical size of this BitSet.
  98      */
  99     private transient int wordsInUse = 0;
 100 
 101     /**
 102      * Whether the size of "words" is user-specified.  If so, we assume
 103      * the user knows what he's doing and try harder to preserve it.
 104      */
 105     private transient boolean sizeIsSticky = false;
 106 
 107     /* use serialVersionUID from JDK 1.0.2 for interoperability */
 108     @java.io.Serial
 109     private static final long serialVersionUID = 7997698588986878753L;
 110 
 111     /**
 112      * Given a bit index, return word index containing it.
 113      */
 114     private static int wordIndex(int bitIndex) {
 115         return bitIndex >> ADDRESS_BITS_PER_WORD;
 116     }
 117 
 118     /**
 119      * Every public method must preserve these invariants.
 120      */
 121     private void checkInvariants() {
 122         assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
 123         assert(wordsInUse >= 0 && wordsInUse <= words.length);
 124         assert(wordsInUse == words.length || words[wordsInUse] == 0);
 125     }
 126 
 127     /**
 128      * Sets the field wordsInUse to the logical size in words of the bit set.


1109             throw new InternalError(e);
1110         }
1111     }
1112 
1113     /**
1114      * Attempts to reduce internal storage used for the bits in this bit set.
1115      * Calling this method may, but is not required to, affect the value
1116      * returned by a subsequent call to the {@link #size()} method.
1117      */
1118     private void trimToSize() {
1119         if (wordsInUse != words.length) {
1120             words = Arrays.copyOf(words, wordsInUse);
1121             checkInvariants();
1122         }
1123     }
1124 
1125     /**
1126      * Save the state of the {@code BitSet} instance to a stream (i.e.,
1127      * serialize it).
1128      */
1129     @java.io.Serial
1130     private void writeObject(ObjectOutputStream s)
1131         throws IOException {
1132 
1133         checkInvariants();
1134 
1135         if (! sizeIsSticky)
1136             trimToSize();
1137 
1138         ObjectOutputStream.PutField fields = s.putFields();
1139         fields.put("bits", words);
1140         s.writeFields();
1141     }
1142 
1143     /**
1144      * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1145      * deserialize it).
1146      */
1147     @java.io.Serial
1148     private void readObject(ObjectInputStream s)
1149         throws IOException, ClassNotFoundException {
1150 
1151         ObjectInputStream.GetField fields = s.readFields();
1152         words = (long[]) fields.get("bits", null);
1153 
1154         // Assume maximum length then find real length
1155         // because recalculateWordsInUse assumes maintenance
1156         // or reduction in logical size
1157         wordsInUse = words.length;
1158         recalculateWordsInUse();
1159         sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1160         checkInvariants();
1161     }
1162 
1163     /**
1164      * Returns a string representation of this bit set. For every index
1165      * for which this {@code BitSet} contains a bit in the set
1166      * state, the decimal representation of that index is included in
1167      * the result. Such indices are listed in order from lowest to


< prev index next >