xref: /aosp_15_r20/external/antlr/runtime/C/src/antlr3bitset.c (revision 16467b971bd3e2009fad32dd79016f2c7e421deb)
1*16467b97STreehugger Robot ///
2*16467b97STreehugger Robot /// \file
3*16467b97STreehugger Robot /// Contains the C implementation of ANTLR3 bitsets as adapted from Terence Parr's
4*16467b97STreehugger Robot /// Java implementation.
5*16467b97STreehugger Robot ///
6*16467b97STreehugger Robot 
7*16467b97STreehugger Robot // [The "BSD licence"]
8*16467b97STreehugger Robot // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
9*16467b97STreehugger Robot // http://www.temporal-wave.com
10*16467b97STreehugger Robot // http://www.linkedin.com/in/jimidle
11*16467b97STreehugger Robot //
12*16467b97STreehugger Robot // All rights reserved.
13*16467b97STreehugger Robot //
14*16467b97STreehugger Robot // Redistribution and use in source and binary forms, with or without
15*16467b97STreehugger Robot // modification, are permitted provided that the following conditions
16*16467b97STreehugger Robot // are met:
17*16467b97STreehugger Robot // 1. Redistributions of source code must retain the above copyright
18*16467b97STreehugger Robot //    notice, this list of conditions and the following disclaimer.
19*16467b97STreehugger Robot // 2. Redistributions in binary form must reproduce the above copyright
20*16467b97STreehugger Robot //    notice, this list of conditions and the following disclaimer in the
21*16467b97STreehugger Robot //    documentation and/or other materials provided with the distribution.
22*16467b97STreehugger Robot // 3. The name of the author may not be used to endorse or promote products
23*16467b97STreehugger Robot //    derived from this software without specific prior written permission.
24*16467b97STreehugger Robot //
25*16467b97STreehugger Robot // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
26*16467b97STreehugger Robot // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
27*16467b97STreehugger Robot // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
28*16467b97STreehugger Robot // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
29*16467b97STreehugger Robot // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
30*16467b97STreehugger Robot // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31*16467b97STreehugger Robot // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32*16467b97STreehugger Robot // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33*16467b97STreehugger Robot // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
34*16467b97STreehugger Robot // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35*16467b97STreehugger Robot 
36*16467b97STreehugger Robot #include    <antlr3bitset.h>
37*16467b97STreehugger Robot 
38*16467b97STreehugger Robot // External interface
39*16467b97STreehugger Robot //
40*16467b97STreehugger Robot 
41*16467b97STreehugger Robot static	pANTLR3_BITSET  antlr3BitsetClone		(pANTLR3_BITSET inSet);
42*16467b97STreehugger Robot static	pANTLR3_BITSET  antlr3BitsetOR			(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);
43*16467b97STreehugger Robot static	void			antlr3BitsetORInPlace	(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2);
44*16467b97STreehugger Robot static	ANTLR3_UINT32	antlr3BitsetSize		(pANTLR3_BITSET bitset);
45*16467b97STreehugger Robot static	void			antlr3BitsetAdd			(pANTLR3_BITSET bitset, ANTLR3_INT32 bit);
46*16467b97STreehugger Robot static	ANTLR3_BOOLEAN	antlr3BitsetEquals		(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);
47*16467b97STreehugger Robot static	ANTLR3_BOOLEAN	antlr3BitsetMember		(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);
48*16467b97STreehugger Robot static	ANTLR3_UINT32	antlr3BitsetNumBits		(pANTLR3_BITSET bitset);
49*16467b97STreehugger Robot static	void			antlr3BitsetRemove		(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);
50*16467b97STreehugger Robot static	ANTLR3_BOOLEAN	antlr3BitsetIsNil		(pANTLR3_BITSET bitset);
51*16467b97STreehugger Robot static	pANTLR3_INT32	antlr3BitsetToIntList	(pANTLR3_BITSET bitset);
52*16467b97STreehugger Robot 
53*16467b97STreehugger Robot // Local functions
54*16467b97STreehugger Robot //
55*16467b97STreehugger Robot static	void			growToInclude		(pANTLR3_BITSET bitset, ANTLR3_INT32 bit);
56*16467b97STreehugger Robot static	void			grow				(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize);
57*16467b97STreehugger Robot static	ANTLR3_UINT64	bitMask				(ANTLR3_UINT32 bitNumber);
58*16467b97STreehugger Robot static	ANTLR3_UINT32	numWordsToHold		(ANTLR3_UINT32 bit);
59*16467b97STreehugger Robot static	ANTLR3_UINT32	wordNumber			(ANTLR3_UINT32 bit);
60*16467b97STreehugger Robot static	void			antlr3BitsetFree	(pANTLR3_BITSET bitset);
61*16467b97STreehugger Robot 
62*16467b97STreehugger Robot static void
antlr3BitsetFree(pANTLR3_BITSET bitset)63*16467b97STreehugger Robot antlr3BitsetFree(pANTLR3_BITSET bitset)
64*16467b97STreehugger Robot {
65*16467b97STreehugger Robot     if	(bitset->blist.bits != NULL)
66*16467b97STreehugger Robot     {
67*16467b97STreehugger Robot 		ANTLR3_FREE(bitset->blist.bits);
68*16467b97STreehugger Robot 		bitset->blist.bits = NULL;
69*16467b97STreehugger Robot     }
70*16467b97STreehugger Robot     ANTLR3_FREE(bitset);
71*16467b97STreehugger Robot 
72*16467b97STreehugger Robot     return;
73*16467b97STreehugger Robot }
74*16467b97STreehugger Robot 
75*16467b97STreehugger Robot ANTLR3_API pANTLR3_BITSET
antlr3BitsetNew(ANTLR3_UINT32 numBits)76*16467b97STreehugger Robot antlr3BitsetNew(ANTLR3_UINT32 numBits)
77*16467b97STreehugger Robot {
78*16467b97STreehugger Robot 	pANTLR3_BITSET  bitset;
79*16467b97STreehugger Robot 
80*16467b97STreehugger Robot 	ANTLR3_UINT32   numelements;
81*16467b97STreehugger Robot 
82*16467b97STreehugger Robot 	// Allocate memory for the bitset structure itself
83*16467b97STreehugger Robot 	//
84*16467b97STreehugger Robot 	bitset  = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));
85*16467b97STreehugger Robot 
86*16467b97STreehugger Robot 	if	(bitset == NULL)
87*16467b97STreehugger Robot 	{
88*16467b97STreehugger Robot 		return	NULL;
89*16467b97STreehugger Robot 	}
90*16467b97STreehugger Robot 
91*16467b97STreehugger Robot 	// Avoid memory thrashing at the up front expense of a few bytes
92*16467b97STreehugger Robot 	//
93*16467b97STreehugger Robot 	if	(numBits < (8 * ANTLR3_BITSET_BITS))
94*16467b97STreehugger Robot 	{
95*16467b97STreehugger Robot 		numBits = 8 * ANTLR3_BITSET_BITS;
96*16467b97STreehugger Robot 	}
97*16467b97STreehugger Robot 
98*16467b97STreehugger Robot 	// No we need to allocate the memory for the number of bits asked for
99*16467b97STreehugger Robot 	// in multiples of ANTLR3_UINT64.
100*16467b97STreehugger Robot 	//
101*16467b97STreehugger Robot 	numelements	= ((numBits -1) >> ANTLR3_BITSET_LOG_BITS) + 1;
102*16467b97STreehugger Robot 
103*16467b97STreehugger Robot 	bitset->blist.bits    = (pANTLR3_BITWORD) ANTLR3_MALLOC((size_t)(numelements * sizeof(ANTLR3_BITWORD)));
104*16467b97STreehugger Robot 	if	(bitset->blist.bits == NULL)
105*16467b97STreehugger Robot 	{
106*16467b97STreehugger Robot 		ANTLR3_FREE(bitset);
107*16467b97STreehugger Robot 		return	NULL;
108*16467b97STreehugger Robot 	}
109*16467b97STreehugger Robot 	memset(bitset->blist.bits, 0, (size_t)(numelements * sizeof(ANTLR3_BITWORD)));
110*16467b97STreehugger Robot 	bitset->blist.length  = numelements;
111*16467b97STreehugger Robot 
112*16467b97STreehugger Robot 	antlr3BitsetSetAPI(bitset);
113*16467b97STreehugger Robot 
114*16467b97STreehugger Robot 
115*16467b97STreehugger Robot 	// All seems good
116*16467b97STreehugger Robot 	//
117*16467b97STreehugger Robot 	return  bitset;
118*16467b97STreehugger Robot }
119*16467b97STreehugger Robot 
120*16467b97STreehugger Robot ANTLR3_API void
antlr3BitsetSetAPI(pANTLR3_BITSET bitset)121*16467b97STreehugger Robot antlr3BitsetSetAPI(pANTLR3_BITSET bitset)
122*16467b97STreehugger Robot {
123*16467b97STreehugger Robot     bitset->clone		=    antlr3BitsetClone;
124*16467b97STreehugger Robot     bitset->bor			=    antlr3BitsetOR;
125*16467b97STreehugger Robot     bitset->borInPlace	=    antlr3BitsetORInPlace;
126*16467b97STreehugger Robot     bitset->size		=    antlr3BitsetSize;
127*16467b97STreehugger Robot     bitset->add			=    antlr3BitsetAdd;
128*16467b97STreehugger Robot     bitset->grow		=    grow;
129*16467b97STreehugger Robot     bitset->equals		=    antlr3BitsetEquals;
130*16467b97STreehugger Robot     bitset->isMember	=    antlr3BitsetMember;
131*16467b97STreehugger Robot     bitset->numBits		=    antlr3BitsetNumBits;
132*16467b97STreehugger Robot     bitset->remove		=    antlr3BitsetRemove;
133*16467b97STreehugger Robot     bitset->isNilNode		=    antlr3BitsetIsNil;
134*16467b97STreehugger Robot     bitset->toIntList	=    antlr3BitsetToIntList;
135*16467b97STreehugger Robot 
136*16467b97STreehugger Robot     bitset->free		=    antlr3BitsetFree;
137*16467b97STreehugger Robot }
138*16467b97STreehugger Robot 
139*16467b97STreehugger Robot ANTLR3_API pANTLR3_BITSET
antlr3BitsetCopy(pANTLR3_BITSET_LIST blist)140*16467b97STreehugger Robot antlr3BitsetCopy(pANTLR3_BITSET_LIST blist)
141*16467b97STreehugger Robot {
142*16467b97STreehugger Robot     pANTLR3_BITSET  bitset;
143*16467b97STreehugger Robot 	int				numElements;
144*16467b97STreehugger Robot 
145*16467b97STreehugger Robot     // Allocate memory for the bitset structure itself
146*16467b97STreehugger Robot     //
147*16467b97STreehugger Robot     bitset  = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));
148*16467b97STreehugger Robot 
149*16467b97STreehugger Robot     if	(bitset == NULL)
150*16467b97STreehugger Robot     {
151*16467b97STreehugger Robot 		return	NULL;
152*16467b97STreehugger Robot     }
153*16467b97STreehugger Robot 
154*16467b97STreehugger Robot 	numElements = blist->length;
155*16467b97STreehugger Robot 
156*16467b97STreehugger Robot     // Avoid memory thrashing at the expense of a few more bytes
157*16467b97STreehugger Robot     //
158*16467b97STreehugger Robot     if	(numElements < 8)
159*16467b97STreehugger Robot     {
160*16467b97STreehugger Robot 		numElements = 8;
161*16467b97STreehugger Robot     }
162*16467b97STreehugger Robot 
163*16467b97STreehugger Robot     // Install the length in ANTLR3_UINT64 units
164*16467b97STreehugger Robot     //
165*16467b97STreehugger Robot     bitset->blist.length  = numElements;
166*16467b97STreehugger Robot 
167*16467b97STreehugger Robot     bitset->blist.bits    = (pANTLR3_BITWORD)ANTLR3_MALLOC((size_t)(numElements * sizeof(ANTLR3_BITWORD)));
168*16467b97STreehugger Robot 
169*16467b97STreehugger Robot     if	(bitset->blist.bits == NULL)
170*16467b97STreehugger Robot     {
171*16467b97STreehugger Robot 		ANTLR3_FREE(bitset);
172*16467b97STreehugger Robot 		return	NULL;
173*16467b97STreehugger Robot     }
174*16467b97STreehugger Robot 
175*16467b97STreehugger Robot 	ANTLR3_MEMCPY(bitset->blist.bits, blist->bits, (ANTLR3_UINT64)(numElements * sizeof(ANTLR3_BITWORD)));
176*16467b97STreehugger Robot 
177*16467b97STreehugger Robot     // All seems good
178*16467b97STreehugger Robot     //
179*16467b97STreehugger Robot     return  bitset;
180*16467b97STreehugger Robot }
181*16467b97STreehugger Robot 
182*16467b97STreehugger Robot static pANTLR3_BITSET
antlr3BitsetClone(pANTLR3_BITSET inSet)183*16467b97STreehugger Robot antlr3BitsetClone(pANTLR3_BITSET inSet)
184*16467b97STreehugger Robot {
185*16467b97STreehugger Robot     pANTLR3_BITSET  bitset;
186*16467b97STreehugger Robot 
187*16467b97STreehugger Robot     // Allocate memory for the bitset structure itself
188*16467b97STreehugger Robot     //
189*16467b97STreehugger Robot     bitset  = antlr3BitsetNew(ANTLR3_BITSET_BITS * inSet->blist.length);
190*16467b97STreehugger Robot 
191*16467b97STreehugger Robot     if	(bitset == NULL)
192*16467b97STreehugger Robot     {
193*16467b97STreehugger Robot 		return	NULL;
194*16467b97STreehugger Robot     }
195*16467b97STreehugger Robot 
196*16467b97STreehugger Robot     // Install the actual bits in the source set
197*16467b97STreehugger Robot     //
198*16467b97STreehugger Robot     ANTLR3_MEMCPY(bitset->blist.bits, inSet->blist.bits, (ANTLR3_UINT64)(inSet->blist.length * sizeof(ANTLR3_BITWORD)));
199*16467b97STreehugger Robot 
200*16467b97STreehugger Robot     // All seems good
201*16467b97STreehugger Robot     //
202*16467b97STreehugger Robot     return  bitset;
203*16467b97STreehugger Robot }
204*16467b97STreehugger Robot 
205*16467b97STreehugger Robot 
206*16467b97STreehugger Robot ANTLR3_API pANTLR3_BITSET
antlr3BitsetList(pANTLR3_HASH_TABLE list)207*16467b97STreehugger Robot antlr3BitsetList(pANTLR3_HASH_TABLE list)
208*16467b97STreehugger Robot {
209*16467b97STreehugger Robot     pANTLR3_BITSET		bitSet;
210*16467b97STreehugger Robot     pANTLR3_HASH_ENUM	en;
211*16467b97STreehugger Robot     pANTLR3_HASH_KEY	key;
212*16467b97STreehugger Robot     ANTLR3_UINT64		bit;
213*16467b97STreehugger Robot 
214*16467b97STreehugger Robot     // We have no idea what exactly is in the list
215*16467b97STreehugger Robot     // so create a default bitset and then just add stuff
216*16467b97STreehugger Robot     // as we enumerate.
217*16467b97STreehugger Robot     //
218*16467b97STreehugger Robot     bitSet  = antlr3BitsetNew(0);
219*16467b97STreehugger Robot 
220*16467b97STreehugger Robot     en		= antlr3EnumNew(list);
221*16467b97STreehugger Robot 
222*16467b97STreehugger Robot     while   (en->next(en, &key, (void **)(&bit)) == ANTLR3_SUCCESS)
223*16467b97STreehugger Robot     {
224*16467b97STreehugger Robot 		bitSet->add(bitSet, (ANTLR3_UINT32)bit);
225*16467b97STreehugger Robot     }
226*16467b97STreehugger Robot     en->free(en);
227*16467b97STreehugger Robot 
228*16467b97STreehugger Robot     return NULL;
229*16467b97STreehugger Robot }
230*16467b97STreehugger Robot 
231*16467b97STreehugger Robot ///
232*16467b97STreehugger Robot /// \brief
233*16467b97STreehugger Robot /// Creates a new bitset with at least one 64 bit bset of bits, but as
234*16467b97STreehugger Robot /// many 64 bit sets as are required.
235*16467b97STreehugger Robot ///
236*16467b97STreehugger Robot /// \param[in] bset
237*16467b97STreehugger Robot /// A variable number of bits to add to the set, ending in -1 (impossible bit).
238*16467b97STreehugger Robot ///
239*16467b97STreehugger Robot /// \returns
240*16467b97STreehugger Robot /// A new bit set with all of the specified bitmaps in it and the API
241*16467b97STreehugger Robot /// initialized.
242*16467b97STreehugger Robot ///
243*16467b97STreehugger Robot /// Call as:
244*16467b97STreehugger Robot ///  - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1);
245*16467b97STreehugger Robot ///  - pANTLR3_BITSET = antlrBitsetOf(-1);  Create empty bitset
246*16467b97STreehugger Robot ///
247*16467b97STreehugger Robot /// \remarks
248*16467b97STreehugger Robot /// Stdargs function - must supply -1 as last paremeter, which is NOT
249*16467b97STreehugger Robot /// added to the set.
250*16467b97STreehugger Robot ///
251*16467b97STreehugger Robot ///
252*16467b97STreehugger Robot ANTLR3_API pANTLR3_BITSET
antlr3BitsetLoad(pANTLR3_BITSET_LIST inBits)253*16467b97STreehugger Robot antlr3BitsetLoad(pANTLR3_BITSET_LIST inBits)
254*16467b97STreehugger Robot {
255*16467b97STreehugger Robot 	pANTLR3_BITSET  bitset;
256*16467b97STreehugger Robot 	ANTLR3_UINT32  count;
257*16467b97STreehugger Robot 
258*16467b97STreehugger Robot 	// Allocate memory for the bitset structure itself
259*16467b97STreehugger Robot 	// the input parameter is the bit number (0 based)
260*16467b97STreehugger Robot 	// to include in the bitset, so we need at at least
261*16467b97STreehugger Robot 	// bit + 1 bits. If any arguments indicate a
262*16467b97STreehugger Robot 	// a bit higher than the default number of bits (0 means default size)
263*16467b97STreehugger Robot 	// then Add() will take care
264*16467b97STreehugger Robot 	// of it.
265*16467b97STreehugger Robot 	//
266*16467b97STreehugger Robot 	bitset  = antlr3BitsetNew(0);
267*16467b97STreehugger Robot 
268*16467b97STreehugger Robot 	if	(bitset == NULL)
269*16467b97STreehugger Robot 	{
270*16467b97STreehugger Robot 		return	NULL;
271*16467b97STreehugger Robot 	}
272*16467b97STreehugger Robot 
273*16467b97STreehugger Robot 	if	(inBits != NULL)
274*16467b97STreehugger Robot 	{
275*16467b97STreehugger Robot 		// Now we can add the element bits into the set
276*16467b97STreehugger Robot 		//
277*16467b97STreehugger Robot 		count=0;
278*16467b97STreehugger Robot 		while (count < inBits->length)
279*16467b97STreehugger Robot 		{
280*16467b97STreehugger Robot 			if  (bitset->blist.length <= count)
281*16467b97STreehugger Robot 			{
282*16467b97STreehugger Robot 				bitset->grow(bitset, count+1);
283*16467b97STreehugger Robot 			}
284*16467b97STreehugger Robot 
285*16467b97STreehugger Robot 			bitset->blist.bits[count] = *((inBits->bits)+count);
286*16467b97STreehugger Robot 			count++;
287*16467b97STreehugger Robot 		}
288*16467b97STreehugger Robot 	}
289*16467b97STreehugger Robot 
290*16467b97STreehugger Robot 	// return the new bitset
291*16467b97STreehugger Robot 	//
292*16467b97STreehugger Robot 	return  bitset;
293*16467b97STreehugger Robot }
294*16467b97STreehugger Robot 
295*16467b97STreehugger Robot ///
296*16467b97STreehugger Robot /// \brief
297*16467b97STreehugger Robot /// Creates a new bitset with at least one element, but as
298*16467b97STreehugger Robot /// many elements are required.
299*16467b97STreehugger Robot ///
300*16467b97STreehugger Robot /// \param[in] bit
301*16467b97STreehugger Robot /// A variable number of bits to add to the set, ending in -1 (impossible bit).
302*16467b97STreehugger Robot ///
303*16467b97STreehugger Robot /// \returns
304*16467b97STreehugger Robot /// A new bit set with all of the specified elements added into it.
305*16467b97STreehugger Robot ///
306*16467b97STreehugger Robot /// Call as:
307*16467b97STreehugger Robot ///  - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1);
308*16467b97STreehugger Robot ///  - pANTLR3_BITSET = antlrBitsetOf(-1);  Create empty bitset
309*16467b97STreehugger Robot ///
310*16467b97STreehugger Robot /// \remarks
311*16467b97STreehugger Robot /// Stdargs function - must supply -1 as last paremeter, which is NOT
312*16467b97STreehugger Robot /// added to the set.
313*16467b97STreehugger Robot ///
314*16467b97STreehugger Robot ///
315*16467b97STreehugger Robot ANTLR3_API pANTLR3_BITSET
antlr3BitsetOf(ANTLR3_INT32 bit,...)316*16467b97STreehugger Robot antlr3BitsetOf(ANTLR3_INT32 bit, ...)
317*16467b97STreehugger Robot {
318*16467b97STreehugger Robot     pANTLR3_BITSET  bitset;
319*16467b97STreehugger Robot 
320*16467b97STreehugger Robot     va_list ap;
321*16467b97STreehugger Robot 
322*16467b97STreehugger Robot     // Allocate memory for the bitset structure itself
323*16467b97STreehugger Robot     // the input parameter is the bit number (0 based)
324*16467b97STreehugger Robot     // to include in the bitset, so we need at at least
325*16467b97STreehugger Robot     // bit + 1 bits. If any arguments indicate a
326*16467b97STreehugger Robot     // a bit higher than the default number of bits (0 menas default size)
327*16467b97STreehugger Robot     // then Add() will take care
328*16467b97STreehugger Robot     // of it.
329*16467b97STreehugger Robot     //
330*16467b97STreehugger Robot     bitset  = antlr3BitsetNew(0);
331*16467b97STreehugger Robot 
332*16467b97STreehugger Robot     if	(bitset == NULL)
333*16467b97STreehugger Robot     {
334*16467b97STreehugger Robot 		return	NULL;
335*16467b97STreehugger Robot     }
336*16467b97STreehugger Robot 
337*16467b97STreehugger Robot     // Now we can add the element bits into the set
338*16467b97STreehugger Robot     //
339*16467b97STreehugger Robot     va_start(ap, bit);
340*16467b97STreehugger Robot     while   (bit != -1)
341*16467b97STreehugger Robot     {
342*16467b97STreehugger Robot 		antlr3BitsetAdd(bitset, bit);
343*16467b97STreehugger Robot 		bit = va_arg(ap, ANTLR3_UINT32);
344*16467b97STreehugger Robot     }
345*16467b97STreehugger Robot     va_end(ap);
346*16467b97STreehugger Robot 
347*16467b97STreehugger Robot     // return the new bitset
348*16467b97STreehugger Robot     //
349*16467b97STreehugger Robot     return  bitset;
350*16467b97STreehugger Robot }
351*16467b97STreehugger Robot 
352*16467b97STreehugger Robot static pANTLR3_BITSET
antlr3BitsetOR(pANTLR3_BITSET bitset1,pANTLR3_BITSET bitset2)353*16467b97STreehugger Robot antlr3BitsetOR(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)
354*16467b97STreehugger Robot {
355*16467b97STreehugger Robot     pANTLR3_BITSET  bitset;
356*16467b97STreehugger Robot 
357*16467b97STreehugger Robot     if	(bitset1 == NULL)
358*16467b97STreehugger Robot     {
359*16467b97STreehugger Robot 		return antlr3BitsetClone(bitset2);
360*16467b97STreehugger Robot     }
361*16467b97STreehugger Robot 
362*16467b97STreehugger Robot     if	(bitset2 == NULL)
363*16467b97STreehugger Robot     {
364*16467b97STreehugger Robot 		return	antlr3BitsetClone(bitset1);
365*16467b97STreehugger Robot     }
366*16467b97STreehugger Robot 
367*16467b97STreehugger Robot     // Allocate memory for the newly ordered bitset structure itself.
368*16467b97STreehugger Robot     //
369*16467b97STreehugger Robot     bitset  = antlr3BitsetClone(bitset1);
370*16467b97STreehugger Robot 
371*16467b97STreehugger Robot     antlr3BitsetORInPlace(bitset, bitset2);
372*16467b97STreehugger Robot 
373*16467b97STreehugger Robot     return  bitset;
374*16467b97STreehugger Robot 
375*16467b97STreehugger Robot }
376*16467b97STreehugger Robot 
377*16467b97STreehugger Robot static void
antlr3BitsetAdd(pANTLR3_BITSET bitset,ANTLR3_INT32 bit)378*16467b97STreehugger Robot antlr3BitsetAdd(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)
379*16467b97STreehugger Robot {
380*16467b97STreehugger Robot     ANTLR3_UINT32   word;
381*16467b97STreehugger Robot 
382*16467b97STreehugger Robot     word    = wordNumber(bit);
383*16467b97STreehugger Robot 
384*16467b97STreehugger Robot     if	(word	>= bitset->blist.length)
385*16467b97STreehugger Robot     {
386*16467b97STreehugger Robot 		growToInclude(bitset, bit);
387*16467b97STreehugger Robot     }
388*16467b97STreehugger Robot 
389*16467b97STreehugger Robot     bitset->blist.bits[word] |= bitMask(bit);
390*16467b97STreehugger Robot 
391*16467b97STreehugger Robot }
392*16467b97STreehugger Robot 
393*16467b97STreehugger Robot static void
grow(pANTLR3_BITSET bitset,ANTLR3_INT32 newSize)394*16467b97STreehugger Robot grow(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize)
395*16467b97STreehugger Robot {
396*16467b97STreehugger Robot     pANTLR3_BITWORD   newBits;
397*16467b97STreehugger Robot 
398*16467b97STreehugger Robot     // Space for newly sized bitset - TODO: come back to this and use realloc?, it may
399*16467b97STreehugger Robot     // be more efficient...
400*16467b97STreehugger Robot     //
401*16467b97STreehugger Robot     newBits = (pANTLR3_BITWORD) ANTLR3_CALLOC(1, (size_t)(newSize * sizeof(ANTLR3_BITWORD)));
402*16467b97STreehugger Robot     if	(bitset->blist.bits != NULL)
403*16467b97STreehugger Robot     {
404*16467b97STreehugger Robot 		// Copy existing bits
405*16467b97STreehugger Robot 		//
406*16467b97STreehugger Robot 		ANTLR3_MEMCPY((void *)newBits, (const void *)bitset->blist.bits, (size_t)(bitset->blist.length * sizeof(ANTLR3_BITWORD)));
407*16467b97STreehugger Robot 
408*16467b97STreehugger Robot 		// Out with the old bits... de de de derrr
409*16467b97STreehugger Robot 		//
410*16467b97STreehugger Robot 		ANTLR3_FREE(bitset->blist.bits);
411*16467b97STreehugger Robot     }
412*16467b97STreehugger Robot 
413*16467b97STreehugger Robot     // In with the new bits... keerrrang.
414*16467b97STreehugger Robot     //
415*16467b97STreehugger Robot     bitset->blist.bits      = newBits;
416*16467b97STreehugger Robot     bitset->blist.length    = newSize;
417*16467b97STreehugger Robot }
418*16467b97STreehugger Robot 
419*16467b97STreehugger Robot static void
growToInclude(pANTLR3_BITSET bitset,ANTLR3_INT32 bit)420*16467b97STreehugger Robot growToInclude(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)
421*16467b97STreehugger Robot {
422*16467b97STreehugger Robot 	ANTLR3_UINT32	bl;
423*16467b97STreehugger Robot 	ANTLR3_UINT32	nw;
424*16467b97STreehugger Robot 
425*16467b97STreehugger Robot 	bl = (bitset->blist.length << 1);
426*16467b97STreehugger Robot 	nw = numWordsToHold(bit);
427*16467b97STreehugger Robot 
428*16467b97STreehugger Robot 	if	(bl > nw)
429*16467b97STreehugger Robot 	{
430*16467b97STreehugger Robot 		bitset->grow(bitset, bl);
431*16467b97STreehugger Robot 	}
432*16467b97STreehugger Robot 	else
433*16467b97STreehugger Robot 	{
434*16467b97STreehugger Robot 		bitset->grow(bitset, nw);
435*16467b97STreehugger Robot 	}
436*16467b97STreehugger Robot }
437*16467b97STreehugger Robot 
438*16467b97STreehugger Robot static void
antlr3BitsetORInPlace(pANTLR3_BITSET bitset,pANTLR3_BITSET bitset2)439*16467b97STreehugger Robot antlr3BitsetORInPlace(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2)
440*16467b97STreehugger Robot {
441*16467b97STreehugger Robot     ANTLR3_UINT32   minimum;
442*16467b97STreehugger Robot     ANTLR3_UINT32   i;
443*16467b97STreehugger Robot 
444*16467b97STreehugger Robot     if	(bitset2 == NULL)
445*16467b97STreehugger Robot     {
446*16467b97STreehugger Robot 		return;
447*16467b97STreehugger Robot     }
448*16467b97STreehugger Robot 
449*16467b97STreehugger Robot 
450*16467b97STreehugger Robot     // First make sure that the target bitset is big enough
451*16467b97STreehugger Robot     // for the new bits to be ored in.
452*16467b97STreehugger Robot     //
453*16467b97STreehugger Robot     if	(bitset->blist.length < bitset2->blist.length)
454*16467b97STreehugger Robot     {
455*16467b97STreehugger Robot 		growToInclude(bitset, (bitset2->blist.length * sizeof(ANTLR3_BITWORD)));
456*16467b97STreehugger Robot     }
457*16467b97STreehugger Robot 
458*16467b97STreehugger Robot     // Or the miniimum number of bits after any resizing went on
459*16467b97STreehugger Robot     //
460*16467b97STreehugger Robot     if	(bitset->blist.length < bitset2->blist.length)
461*16467b97STreehugger Robot 	{
462*16467b97STreehugger Robot 		minimum = bitset->blist.length;
463*16467b97STreehugger Robot 	}
464*16467b97STreehugger Robot 	else
465*16467b97STreehugger Robot 	{
466*16467b97STreehugger Robot 		minimum = bitset2->blist.length;
467*16467b97STreehugger Robot 	}
468*16467b97STreehugger Robot 
469*16467b97STreehugger Robot     for	(i = minimum; i > 0; i--)
470*16467b97STreehugger Robot     {
471*16467b97STreehugger Robot 		bitset->blist.bits[i-1] |= bitset2->blist.bits[i-1];
472*16467b97STreehugger Robot     }
473*16467b97STreehugger Robot }
474*16467b97STreehugger Robot 
475*16467b97STreehugger Robot static ANTLR3_UINT64
bitMask(ANTLR3_UINT32 bitNumber)476*16467b97STreehugger Robot bitMask(ANTLR3_UINT32 bitNumber)
477*16467b97STreehugger Robot {
478*16467b97STreehugger Robot     return  ((ANTLR3_UINT64)1) << (bitNumber & (ANTLR3_BITSET_MOD_MASK));
479*16467b97STreehugger Robot }
480*16467b97STreehugger Robot 
481*16467b97STreehugger Robot static ANTLR3_UINT32
antlr3BitsetSize(pANTLR3_BITSET bitset)482*16467b97STreehugger Robot antlr3BitsetSize(pANTLR3_BITSET bitset)
483*16467b97STreehugger Robot {
484*16467b97STreehugger Robot     ANTLR3_UINT32   degree;
485*16467b97STreehugger Robot     ANTLR3_INT32   i;
486*16467b97STreehugger Robot     ANTLR3_INT8    bit;
487*16467b97STreehugger Robot 
488*16467b97STreehugger Robot     // TODO: Come back to this, it may be faster to & with 0x01
489*16467b97STreehugger Robot     // then shift right a copy of the 4 bits, than shift left a constant of 1.
490*16467b97STreehugger Robot     // But then again, the optimizer might just work this out
491*16467b97STreehugger Robot     // anyway.
492*16467b97STreehugger Robot     //
493*16467b97STreehugger Robot     degree  = 0;
494*16467b97STreehugger Robot     for	(i = bitset->blist.length - 1; i>= 0; i--)
495*16467b97STreehugger Robot     {
496*16467b97STreehugger Robot 		if  (bitset->blist.bits[i] != 0)
497*16467b97STreehugger Robot 		{
498*16467b97STreehugger Robot 			for	(bit = ANTLR3_BITSET_BITS - 1; bit >= 0; bit--)
499*16467b97STreehugger Robot 			{
500*16467b97STreehugger Robot 				if  ((bitset->blist.bits[i] & (((ANTLR3_BITWORD)1) << bit)) != 0)
501*16467b97STreehugger Robot 				{
502*16467b97STreehugger Robot 					degree++;
503*16467b97STreehugger Robot 				}
504*16467b97STreehugger Robot 			}
505*16467b97STreehugger Robot 		}
506*16467b97STreehugger Robot     }
507*16467b97STreehugger Robot     return degree;
508*16467b97STreehugger Robot }
509*16467b97STreehugger Robot 
510*16467b97STreehugger Robot static ANTLR3_BOOLEAN
antlr3BitsetEquals(pANTLR3_BITSET bitset1,pANTLR3_BITSET bitset2)511*16467b97STreehugger Robot antlr3BitsetEquals(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)
512*16467b97STreehugger Robot {
513*16467b97STreehugger Robot     ANTLR3_INT32   minimum;
514*16467b97STreehugger Robot     ANTLR3_INT32   i;
515*16467b97STreehugger Robot 
516*16467b97STreehugger Robot     if	(bitset1 == NULL || bitset2 == NULL)
517*16467b97STreehugger Robot     {
518*16467b97STreehugger Robot 	return	ANTLR3_FALSE;
519*16467b97STreehugger Robot     }
520*16467b97STreehugger Robot 
521*16467b97STreehugger Robot     // Work out the minimum comparison set
522*16467b97STreehugger Robot     //
523*16467b97STreehugger Robot     if	(bitset1->blist.length < bitset2->blist.length)
524*16467b97STreehugger Robot     {
525*16467b97STreehugger Robot 		minimum = bitset1->blist.length;
526*16467b97STreehugger Robot     }
527*16467b97STreehugger Robot     else
528*16467b97STreehugger Robot     {
529*16467b97STreehugger Robot 		minimum = bitset2->blist.length;
530*16467b97STreehugger Robot     }
531*16467b97STreehugger Robot 
532*16467b97STreehugger Robot     // Make sure explict in common bits are equal
533*16467b97STreehugger Robot     //
534*16467b97STreehugger Robot     for	(i = minimum - 1; i >=0 ; i--)
535*16467b97STreehugger Robot     {
536*16467b97STreehugger Robot 		if  (bitset1->blist.bits[i] != bitset2->blist.bits[i])
537*16467b97STreehugger Robot 		{
538*16467b97STreehugger Robot 			return  ANTLR3_FALSE;
539*16467b97STreehugger Robot 		}
540*16467b97STreehugger Robot     }
541*16467b97STreehugger Robot 
542*16467b97STreehugger Robot     // Now make sure the bits of the larger set are all turned
543*16467b97STreehugger Robot     // off.
544*16467b97STreehugger Robot     //
545*16467b97STreehugger Robot     if	(bitset1->blist.length > (ANTLR3_UINT32)minimum)
546*16467b97STreehugger Robot     {
547*16467b97STreehugger Robot 		for (i = minimum ; (ANTLR3_UINT32)i < bitset1->blist.length; i++)
548*16467b97STreehugger Robot 		{
549*16467b97STreehugger Robot 			if	(bitset1->blist.bits[i] != 0)
550*16467b97STreehugger Robot 			{
551*16467b97STreehugger Robot 				return	ANTLR3_FALSE;
552*16467b97STreehugger Robot 			}
553*16467b97STreehugger Robot 		}
554*16467b97STreehugger Robot     }
555*16467b97STreehugger Robot     else if (bitset2->blist.length > (ANTLR3_UINT32)minimum)
556*16467b97STreehugger Robot     {
557*16467b97STreehugger Robot 		for (i = minimum; (ANTLR3_UINT32)i < bitset2->blist.length; i++)
558*16467b97STreehugger Robot 		{
559*16467b97STreehugger Robot 			if	(bitset2->blist.bits[i] != 0)
560*16467b97STreehugger Robot 			{
561*16467b97STreehugger Robot 				return	ANTLR3_FALSE;
562*16467b97STreehugger Robot 			}
563*16467b97STreehugger Robot 		}
564*16467b97STreehugger Robot     }
565*16467b97STreehugger Robot 
566*16467b97STreehugger Robot     return  ANTLR3_TRUE;
567*16467b97STreehugger Robot }
568*16467b97STreehugger Robot 
569*16467b97STreehugger Robot static ANTLR3_BOOLEAN
antlr3BitsetMember(pANTLR3_BITSET bitset,ANTLR3_UINT32 bit)570*16467b97STreehugger Robot antlr3BitsetMember(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)
571*16467b97STreehugger Robot {
572*16467b97STreehugger Robot     ANTLR3_UINT32    wordNo;
573*16467b97STreehugger Robot 
574*16467b97STreehugger Robot     wordNo  = wordNumber(bit);
575*16467b97STreehugger Robot 
576*16467b97STreehugger Robot     if	(wordNo >= bitset->blist.length)
577*16467b97STreehugger Robot     {
578*16467b97STreehugger Robot 		return	ANTLR3_FALSE;
579*16467b97STreehugger Robot     }
580*16467b97STreehugger Robot 
581*16467b97STreehugger Robot     if	((bitset->blist.bits[wordNo] & bitMask(bit)) == 0)
582*16467b97STreehugger Robot     {
583*16467b97STreehugger Robot 		return	ANTLR3_FALSE;
584*16467b97STreehugger Robot     }
585*16467b97STreehugger Robot     else
586*16467b97STreehugger Robot     {
587*16467b97STreehugger Robot 		return	ANTLR3_TRUE;
588*16467b97STreehugger Robot     }
589*16467b97STreehugger Robot }
590*16467b97STreehugger Robot 
591*16467b97STreehugger Robot static void
antlr3BitsetRemove(pANTLR3_BITSET bitset,ANTLR3_UINT32 bit)592*16467b97STreehugger Robot antlr3BitsetRemove(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)
593*16467b97STreehugger Robot {
594*16467b97STreehugger Robot     ANTLR3_UINT32    wordNo;
595*16467b97STreehugger Robot 
596*16467b97STreehugger Robot     wordNo  = wordNumber(bit);
597*16467b97STreehugger Robot 
598*16467b97STreehugger Robot     if	(wordNo < bitset->blist.length)
599*16467b97STreehugger Robot     {
600*16467b97STreehugger Robot 		bitset->blist.bits[wordNo] &= ~(bitMask(bit));
601*16467b97STreehugger Robot     }
602*16467b97STreehugger Robot }
603*16467b97STreehugger Robot static ANTLR3_BOOLEAN
antlr3BitsetIsNil(pANTLR3_BITSET bitset)604*16467b97STreehugger Robot antlr3BitsetIsNil(pANTLR3_BITSET bitset)
605*16467b97STreehugger Robot {
606*16467b97STreehugger Robot    ANTLR3_INT32    i;
607*16467b97STreehugger Robot 
608*16467b97STreehugger Robot    for	(i = bitset->blist.length -1; i>= 0; i--)
609*16467b97STreehugger Robot    {
610*16467b97STreehugger Robot        if   (bitset->blist.bits[i] != 0)
611*16467b97STreehugger Robot        {
612*16467b97STreehugger Robot 			return ANTLR3_FALSE;
613*16467b97STreehugger Robot        }
614*16467b97STreehugger Robot    }
615*16467b97STreehugger Robot 
616*16467b97STreehugger Robot    return   ANTLR3_TRUE;
617*16467b97STreehugger Robot }
618*16467b97STreehugger Robot 
619*16467b97STreehugger Robot static ANTLR3_UINT32
numWordsToHold(ANTLR3_UINT32 bit)620*16467b97STreehugger Robot numWordsToHold(ANTLR3_UINT32 bit)
621*16467b97STreehugger Robot {
622*16467b97STreehugger Robot     return  (bit >> ANTLR3_BITSET_LOG_BITS) + 1;
623*16467b97STreehugger Robot }
624*16467b97STreehugger Robot 
625*16467b97STreehugger Robot static	ANTLR3_UINT32
wordNumber(ANTLR3_UINT32 bit)626*16467b97STreehugger Robot wordNumber(ANTLR3_UINT32 bit)
627*16467b97STreehugger Robot {
628*16467b97STreehugger Robot     return  bit >> ANTLR3_BITSET_LOG_BITS;
629*16467b97STreehugger Robot }
630*16467b97STreehugger Robot 
631*16467b97STreehugger Robot static ANTLR3_UINT32
antlr3BitsetNumBits(pANTLR3_BITSET bitset)632*16467b97STreehugger Robot antlr3BitsetNumBits(pANTLR3_BITSET bitset)
633*16467b97STreehugger Robot {
634*16467b97STreehugger Robot     return  bitset->blist.length << ANTLR3_BITSET_LOG_BITS;
635*16467b97STreehugger Robot }
636*16467b97STreehugger Robot 
637*16467b97STreehugger Robot /** Produce an integer list of all the bits that are turned on
638*16467b97STreehugger Robot  *  in this bitset. Used for error processing in the main as the bitset
639*16467b97STreehugger Robot  *  reresents a number of integer tokens which we use for follow sets
640*16467b97STreehugger Robot  *  and so on.
641*16467b97STreehugger Robot  *
642*16467b97STreehugger Robot  *  The first entry is the number of elements following in the list.
643*16467b97STreehugger Robot  */
644*16467b97STreehugger Robot static	pANTLR3_INT32
antlr3BitsetToIntList(pANTLR3_BITSET bitset)645*16467b97STreehugger Robot antlr3BitsetToIntList	(pANTLR3_BITSET bitset)
646*16467b97STreehugger Robot {
647*16467b97STreehugger Robot     ANTLR3_UINT32   numInts;	    // How many integers we will need
648*16467b97STreehugger Robot     ANTLR3_UINT32   numBits;	    // How many bits are in the set
649*16467b97STreehugger Robot     ANTLR3_UINT32   i;
650*16467b97STreehugger Robot     ANTLR3_UINT32   index;
651*16467b97STreehugger Robot 
652*16467b97STreehugger Robot     pANTLR3_INT32  intList;
653*16467b97STreehugger Robot 
654*16467b97STreehugger Robot     numInts = bitset->size(bitset) + 1;
655*16467b97STreehugger Robot     numBits = bitset->numBits(bitset);
656*16467b97STreehugger Robot 
657*16467b97STreehugger Robot     intList = (pANTLR3_INT32)ANTLR3_MALLOC(numInts * sizeof(ANTLR3_INT32));
658*16467b97STreehugger Robot 
659*16467b97STreehugger Robot     if	(intList == NULL)
660*16467b97STreehugger Robot     {
661*16467b97STreehugger Robot 		return NULL;	// Out of memory
662*16467b97STreehugger Robot     }
663*16467b97STreehugger Robot 
664*16467b97STreehugger Robot     intList[0] = numInts;
665*16467b97STreehugger Robot 
666*16467b97STreehugger Robot     // Enumerate the bits that are turned on
667*16467b97STreehugger Robot     //
668*16467b97STreehugger Robot     for	(i = 0, index = 1; i<numBits; i++)
669*16467b97STreehugger Robot     {
670*16467b97STreehugger Robot 		if  (bitset->isMember(bitset, i) == ANTLR3_TRUE)
671*16467b97STreehugger Robot 		{
672*16467b97STreehugger Robot 			intList[index++]    = i;
673*16467b97STreehugger Robot 		}
674*16467b97STreehugger Robot     }
675*16467b97STreehugger Robot 
676*16467b97STreehugger Robot     // Result set
677*16467b97STreehugger Robot     //
678*16467b97STreehugger Robot     return  intList;
679*16467b97STreehugger Robot }
680*16467b97STreehugger Robot 
681