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