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