BitArray.java revision 628:2bfaf29cc90b
1/* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5/* 6 * Copyright 2001-2004 The Apache Software Foundation. 7 * 8 * Licensed under the Apache License, Version 2.0 (the "License"); 9 * you may not use this file except in compliance with the License. 10 * You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20/* 21 * $Id: BitArray.java,v 1.2.4.1 2005/09/06 05:56:52 pvedula Exp $ 22 */ 23 24package com.sun.org.apache.xalan.internal.xsltc.dom; 25 26import java.io.Externalizable; 27import java.io.IOException; 28import java.io.ObjectInput; 29import java.io.ObjectOutput; 30 31import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator; 32 33 34/** 35 * @author Morten Jorgensen 36 */ 37public class BitArray implements Externalizable { 38 static final long serialVersionUID = -4876019880708377663L; 39 40 private int[] _bits; 41 private int _bitSize; 42 private int _intSize; 43 private int _mask; 44 45 // This table is used to prevent expensive shift operations 46 // (These operations are inexpensive on CPUs but very expensive on JVMs.) 47 private final static int[] _masks = { 48 0x80000000, 0x40000000, 0x20000000, 0x10000000, 49 0x08000000, 0x04000000, 0x02000000, 0x01000000, 50 0x00800000, 0x00400000, 0x00200000, 0x00100000, 51 0x00080000, 0x00040000, 0x00020000, 0x00010000, 52 0x00008000, 0x00004000, 0x00002000, 0x00001000, 53 0x00000800, 0x00000400, 0x00000200, 0x00000100, 54 0x00000080, 0x00000040, 0x00000020, 0x00000010, 55 0x00000008, 0x00000004, 0x00000002, 0x00000001 }; 56 57 private final static boolean DEBUG_ASSERTIONS = false; 58 59 /** 60 * Constructor. Defines the initial size of the bit array (in bits). 61 */ 62 public BitArray() { 63 this(32); 64 } 65 66 public BitArray(int size) { 67 if (size < 32) size = 32; 68 _bitSize = size; 69 _intSize = (_bitSize >>> 5) + 1; 70 _bits = new int[_intSize + 1]; 71 } 72 73 public BitArray(int size, int[] bits) { 74 if (size < 32) size = 32; 75 _bitSize = size; 76 _intSize = (_bitSize >>> 5) + 1; 77 _bits = bits; 78 } 79 80 /** 81 * Set the mask for this bit array. The upper 8 bits of this mask 82 * indicate the DOM in which the nodes in this array belong. 83 */ 84 public void setMask(int mask) { 85 _mask = mask; 86 } 87 88 /** 89 * See setMask() 90 */ 91 public int getMask() { 92 return(_mask); 93 } 94 95 /** 96 * Returns the size of this bit array (in bits). 97 */ 98 public final int size() { 99 return(_bitSize); 100 } 101 102 /** 103 * Returns true if the given bit is set 104 */ 105 public final boolean getBit(int bit) { 106 if (DEBUG_ASSERTIONS) { 107 if (bit >= _bitSize) { 108 throw new Error( 109 "Programmer's assertion in BitArray.getBit"); 110 } 111 } 112 113 return((_bits[bit>>>5] & _masks[bit%32]) != 0); 114 } 115 116 /** 117 * Returns the next set bit from a given position 118 */ 119 public final int getNextBit(int startBit) { 120 for (int i = (startBit >>> 5) ; i<=_intSize; i++) { 121 int bits = _bits[i]; 122 if (bits != 0) { 123 for (int b = (startBit % 32); b<32; b++) { 124 if ((bits & _masks[b]) != 0) { 125 return((i << 5) + b); 126 } 127 } 128 } 129 startBit = 0; 130 } 131 return(DTMAxisIterator.END); 132 } 133 134 /** 135 * This method returns the Nth bit that is set in the bit array. The 136 * current position is cached in the following 4 variables and will 137 * help speed up a sequence of next() call in an index iterator. This 138 * method is a mess, but it is fast and it works, so don't fuck with it. 139 */ 140 private int _pos = Integer.MAX_VALUE; 141 private int _node = 0; 142 private int _int = 0; 143 private int _bit = 0; 144 145 public final int getBitNumber(int pos) { 146 147 // Return last node if position we're looking for is the same 148 if (pos == _pos) return(_node); 149 150 // Start from beginning of position we're looking for is before 151 // the point where we left off the last time. 152 if (pos < _pos) { 153 _int = _bit = _pos = 0; 154 } 155 156 // Scan through the bit array - skip integers that have no bits set 157 for ( ; _int <= _intSize; _int++) { 158 int bits = _bits[_int]; 159 if (bits != 0) { // Any bits set? 160 for ( ; _bit < 32; _bit++) { 161 if ((bits & _masks[_bit]) != 0) { 162 if (++_pos == pos) { 163 _node = ((_int << 5) + _bit) - 1; 164 return (_node); 165 } 166 } 167 } 168 _bit = 0; 169 } 170 } 171 return(0); 172 } 173 174 /** 175 * Returns the integer array in which the bit array is contained 176 */ 177 public final int[] data() { 178 return(_bits); 179 } 180 181 int _first = Integer.MAX_VALUE; // The index where first set bit is 182 int _last = Integer.MIN_VALUE; // The _INTEGER INDEX_ where last set bit is 183 184 /** 185 * Sets a given bit 186 */ 187 public final void setBit(int bit) { 188 if (DEBUG_ASSERTIONS) { 189 if (bit >= _bitSize) { 190 throw new Error( 191 "Programmer's assertion in BitArray.getBit"); 192 } 193 } 194 195 if (bit >= _bitSize) return; 196 final int i = (bit >>> 5); 197 if (i < _first) _first = i; 198 if (i > _last) _last = i; 199 _bits[i] |= _masks[bit % 32]; 200 } 201 202 /** 203 * Merge two bit arrays. This currently only works for nodes from 204 * a single DOM (because there is only one _mask per array). 205 */ 206 public final BitArray merge(BitArray other) { 207 // Take other array's bits if we have node set 208 if (_last == -1) { 209 _bits = other._bits; 210 } 211 // Only merge if other array has any bits set 212 else if (other._last != -1) { 213 int start = (_first < other._first) ? _first : other._first; 214 int stop = (_last > other._last) ? _last : other._last; 215 216 // Merge these bits into other array if other array is larger 217 if (other._intSize > _intSize) { 218 if (stop > _intSize) stop = _intSize; 219 for (int i=start; i<=stop; i++) 220 other._bits[i] |= _bits[i]; 221 _bits = other._bits; 222 } 223 // Merge other bits into this array if this arrai is large/equal. 224 else { 225 if (stop > other._intSize) stop = other._intSize; 226 for (int i=start; i<=stop; i++) 227 _bits[i] |= other._bits[i]; 228 } 229 } 230 return(this); 231 } 232 233 /** 234 * Resizes the bit array - try to avoid using this method!!! 235 */ 236 public final void resize(int newSize) { 237 if (newSize > _bitSize) { 238 _intSize = (newSize >>> 5) + 1; 239 final int[] newBits = new int[_intSize + 1]; 240 System.arraycopy(_bits, 0, newBits, 0, (_bitSize>>>5) + 1); 241 _bits = newBits; 242 _bitSize = newSize; 243 } 244 } 245 246 public BitArray cloneArray() { 247 return(new BitArray(_intSize, _bits)); 248 } 249 250 public void writeExternal(ObjectOutput out) throws IOException { 251 out.writeInt(_bitSize); 252 out.writeInt(_mask); 253 out.writeObject(_bits); 254 out.flush(); 255 } 256 257 /** 258 * Read the whole tree from a file (serialized) 259 */ 260 public void readExternal(ObjectInput in) 261 throws IOException, ClassNotFoundException { 262 _bitSize = in.readInt(); 263 _intSize = (_bitSize >>> 5) + 1; 264 _mask = in.readInt(); 265 _bits = (int[])in.readObject(); 266 } 267 268} 269