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 |