3 /// Contains the C implementation of ANTLR3 bitsets as adapted from Terence Parr's
\r
4 /// Java implementation.
\r
7 // [The "BSD licence"]
\r
8 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
\r
9 // http://www.temporal-wave.com
\r
10 // http://www.linkedin.com/in/jimidle
\r
12 // All rights reserved.
\r
14 // Redistribution and use in source and binary forms, with or without
\r
15 // modification, are permitted provided that the following conditions
\r
17 // 1. Redistributions of source code must retain the above copyright
\r
18 // notice, this list of conditions and the following disclaimer.
\r
19 // 2. Redistributions in binary form must reproduce the above copyright
\r
20 // notice, this list of conditions and the following disclaimer in the
\r
21 // documentation and/or other materials provided with the distribution.
\r
22 // 3. The name of the author may not be used to endorse or promote products
\r
23 // derived from this software without specific prior written permission.
\r
25 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
\r
26 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
\r
27 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
\r
28 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
\r
29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
\r
30 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
\r
31 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
\r
32 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
\r
33 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
\r
34 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\r
36 #include <antlr3bitset.h>
\r
38 // External interface
\r
41 static pANTLR3_BITSET antlr3BitsetClone (pANTLR3_BITSET inSet);
\r
42 static pANTLR3_BITSET antlr3BitsetOR (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);
\r
43 static void antlr3BitsetORInPlace (pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2);
\r
44 static ANTLR3_UINT32 antlr3BitsetSize (pANTLR3_BITSET bitset);
\r
45 static void antlr3BitsetAdd (pANTLR3_BITSET bitset, ANTLR3_INT32 bit);
\r
46 static ANTLR3_BOOLEAN antlr3BitsetEquals (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2);
\r
47 static ANTLR3_BOOLEAN antlr3BitsetMember (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);
\r
48 static ANTLR3_UINT32 antlr3BitsetNumBits (pANTLR3_BITSET bitset);
\r
49 static void antlr3BitsetRemove (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit);
\r
50 static ANTLR3_BOOLEAN antlr3BitsetIsNil (pANTLR3_BITSET bitset);
\r
51 static pANTLR3_INT32 antlr3BitsetToIntList (pANTLR3_BITSET bitset);
\r
55 static void growToInclude (pANTLR3_BITSET bitset, ANTLR3_INT32 bit);
\r
56 static void grow (pANTLR3_BITSET bitset, ANTLR3_INT32 newSize);
\r
57 static ANTLR3_UINT64 bitMask (ANTLR3_UINT32 bitNumber);
\r
58 static ANTLR3_UINT32 numWordsToHold (ANTLR3_UINT32 bit);
\r
59 static ANTLR3_UINT32 wordNumber (ANTLR3_UINT32 bit);
\r
60 static void antlr3BitsetFree (pANTLR3_BITSET bitset);
\r
63 antlr3BitsetFree(pANTLR3_BITSET bitset)
\r
65 if (bitset->blist.bits != NULL)
\r
67 ANTLR3_FREE(bitset->blist.bits);
\r
68 bitset->blist.bits = NULL;
\r
70 ANTLR3_FREE(bitset);
\r
75 ANTLR3_API pANTLR3_BITSET
\r
76 antlr3BitsetNew(ANTLR3_UINT32 numBits)
\r
78 pANTLR3_BITSET bitset;
\r
80 ANTLR3_UINT32 numelements;
\r
82 // Allocate memory for the bitset structure itself
\r
84 bitset = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));
\r
91 // Avoid memory thrashing at the up front expense of a few bytes
\r
93 if (numBits < (8 * ANTLR3_BITSET_BITS))
\r
95 numBits = 8 * ANTLR3_BITSET_BITS;
\r
98 // No we need to allocate the memory for the number of bits asked for
\r
99 // in multiples of ANTLR3_UINT64.
\r
101 numelements = ((numBits -1) >> ANTLR3_BITSET_LOG_BITS) + 1;
\r
103 bitset->blist.bits = (pANTLR3_BITWORD) ANTLR3_MALLOC((size_t)(numelements * sizeof(ANTLR3_BITWORD)));
\r
104 memset(bitset->blist.bits, 0, (size_t)(numelements * sizeof(ANTLR3_BITWORD)));
\r
105 bitset->blist.length = numelements;
\r
107 if (bitset->blist.bits == NULL)
\r
109 ANTLR3_FREE(bitset);
\r
113 antlr3BitsetSetAPI(bitset);
\r
122 antlr3BitsetSetAPI(pANTLR3_BITSET bitset)
\r
124 bitset->clone = antlr3BitsetClone;
\r
125 bitset->bor = antlr3BitsetOR;
\r
126 bitset->borInPlace = antlr3BitsetORInPlace;
\r
127 bitset->size = antlr3BitsetSize;
\r
128 bitset->add = antlr3BitsetAdd;
\r
129 bitset->grow = grow;
\r
130 bitset->equals = antlr3BitsetEquals;
\r
131 bitset->isMember = antlr3BitsetMember;
\r
132 bitset->numBits = antlr3BitsetNumBits;
\r
133 bitset->remove = antlr3BitsetRemove;
\r
134 bitset->isNilNode = antlr3BitsetIsNil;
\r
135 bitset->toIntList = antlr3BitsetToIntList;
\r
137 bitset->free = antlr3BitsetFree;
\r
140 ANTLR3_API pANTLR3_BITSET
\r
141 antlr3BitsetCopy(pANTLR3_BITSET_LIST blist)
\r
143 pANTLR3_BITSET bitset;
\r
146 // Allocate memory for the bitset structure itself
\r
148 bitset = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET));
\r
150 if (bitset == NULL)
\r
155 numElements = blist->length;
\r
157 // Avoid memory thrashing at the expense of a few more bytes
\r
159 if (numElements < 8)
\r
164 // Install the length in ANTLR3_UINT64 units
\r
166 bitset->blist.length = numElements;
\r
168 bitset->blist.bits = (pANTLR3_BITWORD)ANTLR3_MALLOC((size_t)(numElements * sizeof(ANTLR3_BITWORD)));
\r
170 if (bitset->blist.bits == NULL)
\r
172 ANTLR3_FREE(bitset);
\r
176 ANTLR3_MEMCPY(bitset->blist.bits, blist->bits, (ANTLR3_UINT64)(numElements * sizeof(ANTLR3_BITWORD)));
\r
183 static pANTLR3_BITSET
\r
184 antlr3BitsetClone(pANTLR3_BITSET inSet)
\r
186 pANTLR3_BITSET bitset;
\r
188 // Allocate memory for the bitset structure itself
\r
190 bitset = antlr3BitsetNew(ANTLR3_BITSET_BITS * inSet->blist.length);
\r
192 if (bitset == NULL)
\r
197 // Install the actual bits in the source set
\r
199 ANTLR3_MEMCPY(bitset->blist.bits, inSet->blist.bits, (ANTLR3_UINT64)(inSet->blist.length * sizeof(ANTLR3_BITWORD)));
\r
207 ANTLR3_API pANTLR3_BITSET
\r
208 antlr3BitsetList(pANTLR3_HASH_TABLE list)
\r
210 pANTLR3_BITSET bitSet;
\r
211 pANTLR3_HASH_ENUM en;
\r
212 pANTLR3_HASH_KEY key;
\r
215 // We have no idea what exactly is in the list
\r
216 // so create a default bitset and then just add stuff
\r
217 // as we enumerate.
\r
219 bitSet = antlr3BitsetNew(0);
\r
221 en = antlr3EnumNew(list);
\r
223 while (en->next(en, &key, (void **)(&bit)) == ANTLR3_SUCCESS)
\r
225 bitSet->add(bitSet, (ANTLR3_UINT32)bit);
\r
234 /// Creates a new bitset with at least one 64 bit bset of bits, but as
\r
235 /// many 64 bit sets as are required.
\r
237 /// \param[in] bset
\r
238 /// A variable number of bits to add to the set, ending in -1 (impossible bit).
\r
241 /// A new bit set with all of the specified bitmaps in it and the API
\r
245 /// - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1);
\r
246 /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset
\r
249 /// Stdargs function - must supply -1 as last paremeter, which is NOT
\r
250 /// added to the set.
\r
253 ANTLR3_API pANTLR3_BITSET
\r
254 antlr3BitsetLoad(pANTLR3_BITSET_LIST inBits)
\r
256 pANTLR3_BITSET bitset;
\r
257 ANTLR3_UINT32 count;
\r
259 // Allocate memory for the bitset structure itself
\r
260 // the input parameter is the bit number (0 based)
\r
261 // to include in the bitset, so we need at at least
\r
262 // bit + 1 bits. If any arguments indicate a
\r
263 // a bit higher than the default number of bits (0 means default size)
\r
264 // then Add() will take care
\r
267 bitset = antlr3BitsetNew(0);
\r
269 if (bitset == NULL)
\r
274 if (inBits != NULL)
\r
276 // Now we can add the element bits into the set
\r
279 while (count < inBits->length)
\r
281 if (bitset->blist.length <= count)
\r
283 bitset->grow(bitset, count+1);
\r
286 bitset->blist.bits[count] = *((inBits->bits)+count);
\r
291 // return the new bitset
\r
298 /// Creates a new bitset with at least one element, but as
\r
299 /// many elements are required.
\r
302 /// A variable number of bits to add to the set, ending in -1 (impossible bit).
\r
305 /// A new bit set with all of the specified elements added into it.
\r
308 /// - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1);
\r
309 /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset
\r
312 /// Stdargs function - must supply -1 as last paremeter, which is NOT
\r
313 /// added to the set.
\r
316 ANTLR3_API pANTLR3_BITSET
\r
317 antlr3BitsetOf(ANTLR3_INT32 bit, ...)
\r
319 pANTLR3_BITSET bitset;
\r
323 // Allocate memory for the bitset structure itself
\r
324 // the input parameter is the bit number (0 based)
\r
325 // to include in the bitset, so we need at at least
\r
326 // bit + 1 bits. If any arguments indicate a
\r
327 // a bit higher than the default number of bits (0 menas default size)
\r
328 // then Add() will take care
\r
331 bitset = antlr3BitsetNew(0);
\r
333 if (bitset == NULL)
\r
338 // Now we can add the element bits into the set
\r
343 antlr3BitsetAdd(bitset, bit);
\r
344 bit = va_arg(ap, ANTLR3_UINT32);
\r
348 // return the new bitset
\r
353 static pANTLR3_BITSET
\r
354 antlr3BitsetOR(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)
\r
356 pANTLR3_BITSET bitset;
\r
358 if (bitset1 == NULL)
\r
360 return antlr3BitsetClone(bitset2);
\r
363 if (bitset2 == NULL)
\r
365 return antlr3BitsetClone(bitset1);
\r
368 // Allocate memory for the newly ordered bitset structure itself.
\r
370 bitset = antlr3BitsetClone(bitset1);
\r
372 antlr3BitsetORInPlace(bitset, bitset2);
\r
379 antlr3BitsetAdd(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)
\r
381 ANTLR3_UINT32 word;
\r
383 word = wordNumber(bit);
\r
385 if (word >= bitset->blist.length)
\r
387 growToInclude(bitset, bit);
\r
390 bitset->blist.bits[word] |= bitMask(bit);
\r
395 grow(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize)
\r
397 pANTLR3_BITWORD newBits;
\r
399 // Space for newly sized bitset - TODO: come back to this and use realloc?, it may
\r
400 // be more efficient...
\r
402 newBits = (pANTLR3_BITWORD) ANTLR3_CALLOC(1, (size_t)(newSize * sizeof(ANTLR3_BITWORD)));
\r
403 if (bitset->blist.bits != NULL)
\r
405 // Copy existing bits
\r
407 ANTLR3_MEMCPY((void *)newBits, (const void *)bitset->blist.bits, (size_t)(bitset->blist.length * sizeof(ANTLR3_BITWORD)));
\r
409 // Out with the old bits... de de de derrr
\r
411 ANTLR3_FREE(bitset->blist.bits);
\r
414 // In with the new bits... keerrrang.
\r
416 bitset->blist.bits = newBits;
\r
417 bitset->blist.length = newSize;
\r
421 growToInclude(pANTLR3_BITSET bitset, ANTLR3_INT32 bit)
\r
426 bl = (bitset->blist.length << 1);
\r
427 nw = numWordsToHold(bit);
\r
431 bitset->grow(bitset, bl);
\r
435 bitset->grow(bitset, nw);
\r
440 antlr3BitsetORInPlace(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2)
\r
442 ANTLR3_UINT32 minimum;
\r
445 if (bitset2 == NULL)
\r
451 // First make sure that the target bitset is big enough
\r
452 // for the new bits to be ored in.
\r
454 if (bitset->blist.length < bitset2->blist.length)
\r
456 growToInclude(bitset, (bitset2->blist.length * sizeof(ANTLR3_BITWORD)));
\r
459 // Or the miniimum number of bits after any resizing went on
\r
461 if (bitset->blist.length < bitset2->blist.length)
\r
463 minimum = bitset->blist.length;
\r
467 minimum = bitset2->blist.length;
\r
470 for (i = minimum; i > 0; i--)
\r
472 bitset->blist.bits[i-1] |= bitset2->blist.bits[i-1];
\r
476 static ANTLR3_UINT64
\r
477 bitMask(ANTLR3_UINT32 bitNumber)
\r
479 return ((ANTLR3_UINT64)1) << (bitNumber & (ANTLR3_BITSET_MOD_MASK));
\r
482 static ANTLR3_UINT32
\r
483 antlr3BitsetSize(pANTLR3_BITSET bitset)
\r
485 ANTLR3_UINT32 degree;
\r
489 // TODO: Come back to this, it may be faster to & with 0x01
\r
490 // then shift right a copy of the 4 bits, than shift left a constant of 1.
\r
491 // But then again, the optimizer might just work this out
\r
495 for (i = bitset->blist.length - 1; i>= 0; i--)
\r
497 if (bitset->blist.bits[i] != 0)
\r
499 for (bit = ANTLR3_BITSET_BITS - 1; bit >= 0; bit--)
\r
501 if ((bitset->blist.bits[i] & (((ANTLR3_BITWORD)1) << bit)) != 0)
\r
511 static ANTLR3_BOOLEAN
\r
512 antlr3BitsetEquals(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2)
\r
514 ANTLR3_INT32 minimum;
\r
517 if (bitset1 == NULL || bitset2 == NULL)
\r
519 return ANTLR3_FALSE;
\r
522 // Work out the minimum comparison set
\r
524 if (bitset1->blist.length < bitset2->blist.length)
\r
526 minimum = bitset1->blist.length;
\r
530 minimum = bitset2->blist.length;
\r
533 // Make sure explict in common bits are equal
\r
535 for (i = minimum - 1; i >=0 ; i--)
\r
537 if (bitset1->blist.bits[i] != bitset2->blist.bits[i])
\r
539 return ANTLR3_FALSE;
\r
543 // Now make sure the bits of the larger set are all turned
\r
546 if (bitset1->blist.length > (ANTLR3_UINT32)minimum)
\r
548 for (i = minimum ; (ANTLR3_UINT32)i < bitset1->blist.length; i++)
\r
550 if (bitset1->blist.bits[i] != 0)
\r
552 return ANTLR3_FALSE;
\r
556 else if (bitset2->blist.length > (ANTLR3_UINT32)minimum)
\r
558 for (i = minimum; (ANTLR3_UINT32)i < bitset2->blist.length; i++)
\r
560 if (bitset2->blist.bits[i] != 0)
\r
562 return ANTLR3_FALSE;
\r
567 return ANTLR3_TRUE;
\r
570 static ANTLR3_BOOLEAN
\r
571 antlr3BitsetMember(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)
\r
573 ANTLR3_UINT32 wordNo;
\r
575 wordNo = wordNumber(bit);
\r
577 if (wordNo >= bitset->blist.length)
\r
579 return ANTLR3_FALSE;
\r
582 if ((bitset->blist.bits[wordNo] & bitMask(bit)) == 0)
\r
584 return ANTLR3_FALSE;
\r
588 return ANTLR3_TRUE;
\r
593 antlr3BitsetRemove(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit)
\r
595 ANTLR3_UINT32 wordNo;
\r
597 wordNo = wordNumber(bit);
\r
599 if (wordNo < bitset->blist.length)
\r
601 bitset->blist.bits[wordNo] &= ~(bitMask(bit));
\r
604 static ANTLR3_BOOLEAN
\r
605 antlr3BitsetIsNil(pANTLR3_BITSET bitset)
\r
609 for (i = bitset->blist.length -1; i>= 0; i--)
\r
611 if (bitset->blist.bits[i] != 0)
\r
613 return ANTLR3_FALSE;
\r
617 return ANTLR3_TRUE;
\r
620 static ANTLR3_UINT32
\r
621 numWordsToHold(ANTLR3_UINT32 bit)
\r
623 return (bit >> ANTLR3_BITSET_LOG_BITS) + 1;
\r
626 static ANTLR3_UINT32
\r
627 wordNumber(ANTLR3_UINT32 bit)
\r
629 return bit >> ANTLR3_BITSET_LOG_BITS;
\r
632 static ANTLR3_UINT32
\r
633 antlr3BitsetNumBits(pANTLR3_BITSET bitset)
\r
635 return bitset->blist.length << ANTLR3_BITSET_LOG_BITS;
\r
638 /** Produce an integer list of all the bits that are turned on
\r
639 * in this bitset. Used for error processing in the main as the bitset
\r
640 * reresents a number of integer tokens which we use for follow sets
\r
643 * The first entry is the number of elements following in the list.
\r
645 static pANTLR3_INT32
\r
646 antlr3BitsetToIntList (pANTLR3_BITSET bitset)
\r
648 ANTLR3_UINT32 numInts; // How many integers we will need
\r
649 ANTLR3_UINT32 numBits; // How many bits are in the set
\r
651 ANTLR3_UINT32 index;
\r
653 pANTLR3_INT32 intList;
\r
655 numInts = bitset->size(bitset) + 1;
\r
656 numBits = bitset->numBits(bitset);
\r
658 intList = (pANTLR3_INT32)ANTLR3_MALLOC(numInts * sizeof(ANTLR3_INT32));
\r
660 if (intList == NULL)
\r
662 return NULL; // Out of memory
\r
665 intList[0] = numInts;
\r
667 // Enumerate the bits that are turned on
\r
669 for (i = 0, index = 1; i<numBits; i++)
\r
671 if (bitset->isMember(bitset, i) == ANTLR3_TRUE)
\r
673 intList[index++] = i;
\r