001: /*
002: * The Apache Software License, Version 1.1
003: *
004: *
005: * Copyright (c) 1999 The Apache Software Foundation. All rights
006: * reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Apache Software Foundation (http://www.apache.org/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Xerces" and "Apache Software Foundation" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact apache@apache.org.
031: *
032: * 5. Products derived from this software may not be called "Apache",
033: * nor may "Apache" appear in their name, without prior written
034: * permission of the Apache Software Foundation.
035: *
036: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
037: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
038: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
039: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
040: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
041: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
042: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
043: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
044: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
045: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
046: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
047: * SUCH DAMAGE.
048: * ====================================================================
049: *
050: * This software consists of voluntary contributions made by many
051: * individuals on behalf of the Apache Software Foundation and was
052: * originally based on software copyright (c) 1999, International
053: * Business Machines, Inc., http://www.apache.org. For more
054: * information on the Apache Software Foundation, please see
055: * <http://www.apache.org/>.
056: */
057:
058: package org.apache.xerces.validators.common;
059:
060: import org.apache.xerces.utils.ImplementationMessages;
061:
062: /**
063: * This class is a very simple bitset class. The DFA content model code needs
064: * to support a bit set, but the java BitSet class is way, way overkill. Our
065: * bitset never needs to be expanded after creation, hash itself, etc...
066: *
067: * Since the vast majority of content models will never require more than 64
068: * bits, and since allocation of anything in Java is expensive, this class
069: * provides a hybrid implementation that uses two ints for instances that use
070: * 64 bits or fewer. It has a byte array reference member which will only be
071: * used if more than 64 bits are required.
072: *
073: * Note that the code that uses this class will never perform operations
074: * on sets of different sizes, so that check does not have to be made here.
075: *
076: * @version
077: */
078: class CMStateSet {
079: // -------------------------------------------------------------------
080: // Constructors
081: // -------------------------------------------------------------------
082: CMStateSet(int bitCount) throws CMException {
083: // Store the required bit count and insure its legal
084: fBitCount = bitCount;
085: if (fBitCount < 0)
086: throw new CMException(ImplementationMessages.VAL_CMSI);
087:
088: //
089: // See if we need to allocate the byte array or whether we can live
090: // within the 64 bit high performance scheme.
091: //
092: if (fBitCount > 64) {
093: fByteCount = fBitCount / 8;
094: if (fBitCount % 8 != 0)
095: fByteCount++;
096: fByteArray = new byte[fByteCount];
097: }
098:
099: // Init all the bits to zero
100: zeroBits();
101: }
102:
103: // -------------------------------------------------------------------
104: // Public inherited methods
105: // -------------------------------------------------------------------
106: public String toString() {
107: StringBuffer strRet = new StringBuffer();
108: try {
109: strRet.append("{");
110: for (int index = 0; index < fBitCount; index++) {
111: if (getBit(index))
112: strRet.append(" " + index);
113: }
114: strRet.append(" }");
115: }
116:
117: catch (CMException exToCatch) {
118: //
119: // We know this won't happen but we have to catch it to avoid it
120: // having to be in our 'throws' list.
121: //
122: }
123: return strRet.toString();
124: }
125:
126: // -------------------------------------------------------------------
127: // Package final methods
128: // -------------------------------------------------------------------
129: final void intersection(CMStateSet setToAnd) {
130: if (fBitCount < 65) {
131: fBits1 &= setToAnd.fBits1;
132: fBits2 &= setToAnd.fBits2;
133: } else {
134: for (int index = fByteCount - 1; index >= 0; index--)
135: fByteArray[index] &= setToAnd.fByteArray[index];
136: }
137: }
138:
139: final boolean getBit(int bitToGet) throws CMException {
140: if (bitToGet >= fBitCount)
141: throw new CMException(ImplementationMessages.VAL_CMSI);
142:
143: if (fBitCount < 65) {
144: final int mask = (0x1 << (bitToGet % 32));
145: if (bitToGet < 32)
146: return (fBits1 & mask) != 0;
147: else
148: return (fBits2 & mask) != 0;
149: } else {
150: // Create the mask and byte values
151: final byte mask = (byte) (0x1 << (bitToGet % 8));
152: final int ofs = bitToGet >> 3;
153:
154: // And access the right bit and byte
155: return ((fByteArray[ofs] & mask) != 0);
156: }
157: }
158:
159: final boolean isEmpty() {
160: if (fBitCount < 65) {
161: return ((fBits1 == 0) && (fBits2 == 0));
162: } else {
163: for (int index = fByteCount - 1; index >= 0; index--) {
164: if (fByteArray[index] != 0)
165: return false;
166: }
167: }
168: return true;
169: }
170:
171: final boolean isSameSet(CMStateSet setToCompare) {
172: if (fBitCount != setToCompare.fBitCount)
173: return false;
174:
175: if (fBitCount < 65) {
176: return ((fBits1 == setToCompare.fBits1) && (fBits2 == setToCompare.fBits2));
177: }
178:
179: for (int index = fByteCount - 1; index >= 0; index--) {
180: if (fByteArray[index] != setToCompare.fByteArray[index])
181: return false;
182: }
183: return true;
184: }
185:
186: final void union(CMStateSet setToOr) {
187: if (fBitCount < 65) {
188: fBits1 |= setToOr.fBits1;
189: fBits2 |= setToOr.fBits2;
190: } else {
191: for (int index = fByteCount - 1; index >= 0; index--)
192: fByteArray[index] |= setToOr.fByteArray[index];
193: }
194: }
195:
196: final void setBit(int bitToSet) throws CMException {
197: if (bitToSet >= fBitCount)
198: throw new CMException(ImplementationMessages.VAL_CMSI);
199:
200: if (fBitCount < 65) {
201: final int mask = (0x1 << (bitToSet % 32));
202: if (bitToSet < 32) {
203: fBits1 &= ~mask;
204: fBits1 |= mask;
205: } else {
206: fBits2 &= ~mask;
207: fBits2 |= mask;
208: }
209: } else {
210: // Create the mask and byte values
211: final byte mask = (byte) (0x1 << (bitToSet % 8));
212: final int ofs = bitToSet >> 3;
213:
214: // And access the right bit and byte
215: fByteArray[ofs] &= ~mask;
216: fByteArray[ofs] |= mask;
217: }
218: }
219:
220: final void setTo(CMStateSet srcSet) throws CMException {
221: // They have to be the same size
222: if (fBitCount != srcSet.fBitCount)
223: throw new CMException(ImplementationMessages.VAL_CMSI);
224:
225: if (fBitCount < 65) {
226: fBits1 = srcSet.fBits1;
227: fBits2 = srcSet.fBits2;
228: } else {
229: for (int index = fByteCount - 1; index >= 0; index--)
230: fByteArray[index] = srcSet.fByteArray[index];
231: }
232: }
233:
234: final void zeroBits() {
235: if (fBitCount < 65) {
236: fBits1 = 0;
237: fBits2 = 0;
238: } else {
239: for (int index = fByteCount - 1; index >= 0; index--)
240: fByteArray[index] = 0;
241: }
242: }
243:
244: // -------------------------------------------------------------------
245: // Private data members
246: //
247: // fBitCount
248: // The count of bits that the outside world wants to support,
249: // so its the max bit index plus one.
250: //
251: // fByteCount
252: // If the bit count is > 64, then we use the fByteArray member to
253: // store the bits, and this indicates its size in bytes. Otherwise
254: // its value is meaningless.
255: //
256: // fBits1
257: // fBits2
258: // When the bit count is < 64 (very common), these hold the bits.
259: // Otherwise, the fByteArray member holds htem.
260: // -------------------------------------------------------------------
261: int fBitCount;
262: int fByteCount;
263: int fBits1;
264: int fBits2;
265: byte[] fByteArray;
266:
267: /* Optimization(Jan, 2001) */
268: public boolean equals(Object o) {
269: if (!(o instanceof CMStateSet))
270: return false;
271: return isSameSet((CMStateSet) o);
272: }
273:
274: public int hashCode() {
275: if (fBitCount < 65) {
276: return fBits1 + fBits2 * 31;
277: } else {
278: int hash = 0;
279: for (int index = fByteCount - 1; index >= 0; index--)
280: hash = fByteArray[index] + hash * 31;
281: return hash;
282: }
283: }
284: /* Optimization(Jan, 2001) */
285: };
|