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