1 /*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5 /*
6 * The Apache Software License, Version 1.1
7 *
8 *
9 * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
10 * reserved.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 *
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * 2. Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in
21 * the documentation and/or other materials provided with the
22 * distribution.
23 *
24 * 3. The end-user documentation included with the redistribution,
25 * if any, must include the following acknowledgment:
26 * "This product includes software developed by the
27 * Apache Software Foundation (http://www.apache.org/)."
28 * Alternately, this acknowledgment may appear in the software itself,
29 * if and wherever such third-party acknowledgments normally appear.
30 *
31 * 4. The names "Xerces" and "Apache Software Foundation" must
32 * not be used to endorse or promote products derived from this
33 * software without prior written permission. For written
34 * permission, please contact apache@apache.org.
35 *
36 * 5. Products derived from this software may not be called "Apache",
37 * nor may "Apache" appear in their name, without prior written
38 * permission of the Apache Software Foundation.
39 *
40 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
41 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
42 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
43 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
46 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
47 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
48 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
49 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
50 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE.
52 * ====================================================================
53 *
54 * This software consists of voluntary contributions made by many
55 * individuals on behalf of the Apache Software Foundation and was
56 * originally based on software copyright (c) 1999, International
57 * Business Machines, Inc., http://www.apache.org. For more
58 * information on the Apache Software Foundation, please see
59 * <http://www.apache.org/>.
60 */
61
62 package com.sun.org.apache.xerces.internal.impl.dtd.models;
63
64
65 /**
66 * This class is a very simple bitset class. The DFA content model code needs
67 * to support a bit set, but the java BitSet class is way, way overkill. Our
68 * bitset never needs to be expanded after creation, hash itself, etc...
69 *
70 * Since the vast majority of content models will never require more than 64
71 * bits, and since allocation of anything in Java is expensive, this class
72 * provides a hybrid implementation that uses two ints for instances that use
73 * 64 bits or fewer. It has a byte array reference member which will only be
74 * used if more than 64 bits are required.
75 *
76 * Note that the code that uses this class will never perform operations
77 * on sets of different sizes, so that check does not have to be made here.
78 *
79 * @xerces.internal
80 *
81 */
82 // made this class public so it can be accessed by
83 // the XS content models from the schema package -neilg.
84 public class CMStateSet
85 {
86 // -------------------------------------------------------------------
87 // Constructors
88 // -------------------------------------------------------------------
89 public CMStateSet(int bitCount)
90 {
91 // Store the required bit count and insure its legal
92 fBitCount = bitCount;
93 if (fBitCount < 0)
94 throw new RuntimeException("ImplementationMessages.VAL_CMSI");
95
96 //
97 // See if we need to allocate the byte array or whether we can live
98 // within the 64 bit high performance scheme.
99 //
100 if (fBitCount > 64)
101 {
102 fByteCount = fBitCount / 8;
103 if (fBitCount % 8 != 0)
104 fByteCount++;
105 fByteArray = new byte[fByteCount];
106 }
107
108 // Init all the bits to zero
109 zeroBits();
110 }
111
112
113 // -------------------------------------------------------------------
114 // Public inherited methods
115 // -------------------------------------------------------------------
116 public String toString()
117 {
118 StringBuffer strRet = new StringBuffer();
119 try
120 {
121 strRet.append("{");
122 for (int index = 0; index < fBitCount; index++)
123 {
124 if (getBit(index))
125 strRet.append(" " + index);
126 }
127 strRet.append(" }");
128 }
129
130 catch(RuntimeException exToCatch)
131 {
132 //
133 // We know this won't happen but we have to catch it to avoid it
134 // having to be in our 'throws' list.
135 //
136 }
137 return strRet.toString();
138 }
139
140
141 // -------------------------------------------------------------------
142 // Package final methods
143 // -------------------------------------------------------------------
144 // the XS content models from the schema package -neilg.
145 public final void intersection(CMStateSet setToAnd)
146 {
147 if (fBitCount < 65)
148 {
149 fBits1 &= setToAnd.fBits1;
150 fBits2 &= setToAnd.fBits2;
151 }
152 else
153 {
154 for (int index = fByteCount - 1; index >= 0; index--)
155 fByteArray[index] &= setToAnd.fByteArray[index];
156 }
157 }
158
159 public final boolean getBit(int bitToGet)
160 {
161 if (bitToGet >= fBitCount)
162 throw new RuntimeException("ImplementationMessages.VAL_CMSI");
163
164 if (fBitCount < 65)
165 {
166 final int mask = (0x1 << (bitToGet % 32));
167 if (bitToGet < 32)
168 return (fBits1 & mask) != 0;
169 else
170 return (fBits2 & mask) != 0;
171 }
172 else
173 {
174 // Create the mask and byte values
175 final byte mask = (byte)(0x1 << (bitToGet % 8));
176 final int ofs = bitToGet >> 3;
177
178 // And access the right bit and byte
179 return ((fByteArray[ofs] & mask) != 0);
180 }
181 }
182
183 public final boolean isEmpty()
184 {
185 if (fBitCount < 65)
186 {
187 return ((fBits1 == 0) && (fBits2 == 0));
188 }
189 else
190 {
191 for (int index = fByteCount - 1; index >= 0; index--)
192 {
193 if (fByteArray[index] != 0)
194 return false;
195 }
196 }
197 return true;
198 }
199
200 final boolean isSameSet(CMStateSet setToCompare)
201 {
202 if (fBitCount != setToCompare.fBitCount)
203 return false;
204
205 if (fBitCount < 65)
206 {
207 return ((fBits1 == setToCompare.fBits1)
208 && (fBits2 == setToCompare.fBits2));
209 }
210
211 for (int index = fByteCount - 1; index >= 0; index--)
212 {
213 if (fByteArray[index] != setToCompare.fByteArray[index])
214 return false;
215 }
216 return true;
217 }
218
219 // the XS content models from the schema package -neilg.
220 public final void union(CMStateSet setToOr)
221 {
222 if (fBitCount < 65)
223 {
224 fBits1 |= setToOr.fBits1;
225 fBits2 |= setToOr.fBits2;
226 }
227 else
228 {
229 for (int index = fByteCount - 1; index >= 0; index--)
230 fByteArray[index] |= setToOr.fByteArray[index];
231 }
232 }
233
234 public final void setBit(int bitToSet)
235 {
236 if (bitToSet >= fBitCount)
237 throw new RuntimeException("ImplementationMessages.VAL_CMSI");
238
239 if (fBitCount < 65)
240 {
241 final int mask = (0x1 << (bitToSet % 32));
242 if (bitToSet < 32)
243 {
244 fBits1 &= ~mask;
245 fBits1 |= mask;
246 }
247 else
248 {
249 fBits2 &= ~mask;
250 fBits2 |= mask;
251 }
252 }
253 else
254 {
255 // Create the mask and byte values
256 final byte mask = (byte)(0x1 << (bitToSet % 8));
257 final int ofs = bitToSet >> 3;
258
259 // And access the right bit and byte
260 fByteArray[ofs] &= ~mask;
261 fByteArray[ofs] |= mask;
262 }
263 }
264
265 // the XS content models from the schema package -neilg.
266 public final void setTo(CMStateSet srcSet)
267 {
268 // They have to be the same size
269 if (fBitCount != srcSet.fBitCount)
270 throw new RuntimeException("ImplementationMessages.VAL_CMSI");
271
272 if (fBitCount < 65)
273 {
274 fBits1 = srcSet.fBits1;
275 fBits2 = srcSet.fBits2;
276 }
277 else
278 {
279 for (int index = fByteCount - 1; index >= 0; index--)
280 fByteArray[index] = srcSet.fByteArray[index];
281 }
282 }
283
284 // had to make this method public so it could be accessed from
285 // schema package - neilg.
286 public final void zeroBits()
287 {
288 if (fBitCount < 65)
289 {
290 fBits1 = 0;
291 fBits2 = 0;
292 }
293 else
294 {
295 for (int index = fByteCount - 1; index >= 0; index--)
296 fByteArray[index] = 0;
297 }
298 }
299
300
301 // -------------------------------------------------------------------
302 // Private data members
303 //
304 // fBitCount
305 // The count of bits that the outside world wants to support,
306 // so its the max bit index plus one.
307 //
308 // fByteCount
309 // If the bit count is > 64, then we use the fByteArray member to
310 // store the bits, and this indicates its size in bytes. Otherwise
311 // its value is meaningless.
312 //
313 // fBits1
314 // fBits2
315 // When the bit count is < 64 (very common), these hold the bits.
316 // Otherwise, the fByteArray member holds htem.
317 // -------------------------------------------------------------------
318 int fBitCount;
319 int fByteCount;
320 int fBits1;
321 int fBits2;
322 byte[] fByteArray;
323 /* Optimization(Jan, 2001) */
324 public boolean equals(Object o) {
325 if (!(o instanceof CMStateSet)) return false;
326 return isSameSet((CMStateSet)o);
327 }
328
329 public int hashCode() {
330 if (fBitCount < 65)
331 {
332 return fBits1+ fBits2 * 31;
333 }
334 else
335 {
336 int hash = 0;
337 for (int index = fByteCount - 1; index >= 0; index--)
338 hash = fByteArray[index] + hash * 31;
339 return hash;
340 }
341 }
342 /* Optimization(Jan, 2001) */
343 };