| /// |
| /// \file |
| /// Contains the C implementation of ANTLR3 bitsets as adapted from Terence Parr's |
| /// Java implementation. |
| /// |
| |
| // [The "BSD licence"] |
| // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC |
| // http://www.temporal-wave.com |
| // http://www.linkedin.com/in/jimidle |
| // |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions |
| // are met: |
| // 1. Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // 2. Redistributions in binary form must reproduce the above copyright |
| // notice, this list of conditions and the following disclaimer in the |
| // documentation and/or other materials provided with the distribution. |
| // 3. The name of the author may not be used to endorse or promote products |
| // derived from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #include <antlr3bitset.h> |
| |
| // External interface |
| // |
| |
| static pANTLR3_BITSET antlr3BitsetClone (pANTLR3_BITSET inSet); |
| static pANTLR3_BITSET antlr3BitsetOR (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2); |
| static void antlr3BitsetORInPlace (pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2); |
| static ANTLR3_UINT32 antlr3BitsetSize (pANTLR3_BITSET bitset); |
| static void antlr3BitsetAdd (pANTLR3_BITSET bitset, ANTLR3_INT32 bit); |
| static ANTLR3_BOOLEAN antlr3BitsetEquals (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2); |
| static ANTLR3_BOOLEAN antlr3BitsetMember (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit); |
| static ANTLR3_UINT32 antlr3BitsetNumBits (pANTLR3_BITSET bitset); |
| static void antlr3BitsetRemove (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit); |
| static ANTLR3_BOOLEAN antlr3BitsetIsNil (pANTLR3_BITSET bitset); |
| static pANTLR3_INT32 antlr3BitsetToIntList (pANTLR3_BITSET bitset); |
| |
| // Local functions |
| // |
| static void growToInclude (pANTLR3_BITSET bitset, ANTLR3_INT32 bit); |
| static void grow (pANTLR3_BITSET bitset, ANTLR3_INT32 newSize); |
| static ANTLR3_UINT64 bitMask (ANTLR3_UINT32 bitNumber); |
| static ANTLR3_UINT32 numWordsToHold (ANTLR3_UINT32 bit); |
| static ANTLR3_UINT32 wordNumber (ANTLR3_UINT32 bit); |
| static void antlr3BitsetFree (pANTLR3_BITSET bitset); |
| |
| static void |
| antlr3BitsetFree(pANTLR3_BITSET bitset) |
| { |
| if (bitset->blist.bits != NULL) |
| { |
| ANTLR3_FREE(bitset->blist.bits); |
| bitset->blist.bits = NULL; |
| } |
| ANTLR3_FREE(bitset); |
| |
| return; |
| } |
| |
| ANTLR3_API pANTLR3_BITSET |
| antlr3BitsetNew(ANTLR3_UINT32 numBits) |
| { |
| pANTLR3_BITSET bitset; |
| |
| ANTLR3_UINT32 numelements; |
| |
| // Allocate memory for the bitset structure itself |
| // |
| bitset = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET)); |
| |
| if (bitset == NULL) |
| { |
| return NULL; |
| } |
| |
| // Avoid memory thrashing at the up front expense of a few bytes |
| // |
| if (numBits < (8 * ANTLR3_BITSET_BITS)) |
| { |
| numBits = 8 * ANTLR3_BITSET_BITS; |
| } |
| |
| // No we need to allocate the memory for the number of bits asked for |
| // in multiples of ANTLR3_UINT64. |
| // |
| numelements = ((numBits -1) >> ANTLR3_BITSET_LOG_BITS) + 1; |
| |
| bitset->blist.bits = (pANTLR3_BITWORD) ANTLR3_MALLOC((size_t)(numelements * sizeof(ANTLR3_BITWORD))); |
| memset(bitset->blist.bits, 0, (size_t)(numelements * sizeof(ANTLR3_BITWORD))); |
| bitset->blist.length = numelements; |
| |
| if (bitset->blist.bits == NULL) |
| { |
| ANTLR3_FREE(bitset); |
| return NULL; |
| } |
| |
| antlr3BitsetSetAPI(bitset); |
| |
| |
| // All seems good |
| // |
| return bitset; |
| } |
| |
| ANTLR3_API void |
| antlr3BitsetSetAPI(pANTLR3_BITSET bitset) |
| { |
| bitset->clone = antlr3BitsetClone; |
| bitset->bor = antlr3BitsetOR; |
| bitset->borInPlace = antlr3BitsetORInPlace; |
| bitset->size = antlr3BitsetSize; |
| bitset->add = antlr3BitsetAdd; |
| bitset->grow = grow; |
| bitset->equals = antlr3BitsetEquals; |
| bitset->isMember = antlr3BitsetMember; |
| bitset->numBits = antlr3BitsetNumBits; |
| bitset->remove = antlr3BitsetRemove; |
| bitset->isNilNode = antlr3BitsetIsNil; |
| bitset->toIntList = antlr3BitsetToIntList; |
| |
| bitset->free = antlr3BitsetFree; |
| } |
| |
| ANTLR3_API pANTLR3_BITSET |
| antlr3BitsetCopy(pANTLR3_BITSET_LIST blist) |
| { |
| pANTLR3_BITSET bitset; |
| int numElements; |
| |
| // Allocate memory for the bitset structure itself |
| // |
| bitset = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET)); |
| |
| if (bitset == NULL) |
| { |
| return NULL; |
| } |
| |
| numElements = blist->length; |
| |
| // Avoid memory thrashing at the expense of a few more bytes |
| // |
| if (numElements < 8) |
| { |
| numElements = 8; |
| } |
| |
| // Install the length in ANTLR3_UINT64 units |
| // |
| bitset->blist.length = numElements; |
| |
| bitset->blist.bits = (pANTLR3_BITWORD)ANTLR3_MALLOC((size_t)(numElements * sizeof(ANTLR3_BITWORD))); |
| |
| if (bitset->blist.bits == NULL) |
| { |
| ANTLR3_FREE(bitset); |
| return NULL; |
| } |
| |
| ANTLR3_MEMCPY(bitset->blist.bits, blist->bits, (ANTLR3_UINT64)(numElements * sizeof(ANTLR3_BITWORD))); |
| |
| // All seems good |
| // |
| return bitset; |
| } |
| |
| static pANTLR3_BITSET |
| antlr3BitsetClone(pANTLR3_BITSET inSet) |
| { |
| pANTLR3_BITSET bitset; |
| |
| // Allocate memory for the bitset structure itself |
| // |
| bitset = antlr3BitsetNew(ANTLR3_BITSET_BITS * inSet->blist.length); |
| |
| if (bitset == NULL) |
| { |
| return NULL; |
| } |
| |
| // Install the actual bits in the source set |
| // |
| ANTLR3_MEMCPY(bitset->blist.bits, inSet->blist.bits, (ANTLR3_UINT64)(inSet->blist.length * sizeof(ANTLR3_BITWORD))); |
| |
| // All seems good |
| // |
| return bitset; |
| } |
| |
| |
| ANTLR3_API pANTLR3_BITSET |
| antlr3BitsetList(pANTLR3_HASH_TABLE list) |
| { |
| pANTLR3_BITSET bitSet; |
| pANTLR3_HASH_ENUM en; |
| pANTLR3_HASH_KEY key; |
| ANTLR3_UINT64 bit; |
| |
| // We have no idea what exactly is in the list |
| // so create a default bitset and then just add stuff |
| // as we enumerate. |
| // |
| bitSet = antlr3BitsetNew(0); |
| |
| en = antlr3EnumNew(list); |
| |
| while (en->next(en, &key, (void **)(&bit)) == ANTLR3_SUCCESS) |
| { |
| bitSet->add(bitSet, (ANTLR3_UINT32)bit); |
| } |
| en->free(en); |
| |
| return NULL; |
| } |
| |
| /// |
| /// \brief |
| /// Creates a new bitset with at least one 64 bit bset of bits, but as |
| /// many 64 bit sets as are required. |
| /// |
| /// \param[in] bset |
| /// A variable number of bits to add to the set, ending in -1 (impossible bit). |
| /// |
| /// \returns |
| /// A new bit set with all of the specified bitmaps in it and the API |
| /// initialized. |
| /// |
| /// Call as: |
| /// - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1); |
| /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset |
| /// |
| /// \remarks |
| /// Stdargs function - must supply -1 as last paremeter, which is NOT |
| /// added to the set. |
| /// |
| /// |
| ANTLR3_API pANTLR3_BITSET |
| antlr3BitsetLoad(pANTLR3_BITSET_LIST inBits) |
| { |
| pANTLR3_BITSET bitset; |
| ANTLR3_UINT32 count; |
| |
| // Allocate memory for the bitset structure itself |
| // the input parameter is the bit number (0 based) |
| // to include in the bitset, so we need at at least |
| // bit + 1 bits. If any arguments indicate a |
| // a bit higher than the default number of bits (0 means default size) |
| // then Add() will take care |
| // of it. |
| // |
| bitset = antlr3BitsetNew(0); |
| |
| if (bitset == NULL) |
| { |
| return NULL; |
| } |
| |
| if (inBits != NULL) |
| { |
| // Now we can add the element bits into the set |
| // |
| count=0; |
| while (count < inBits->length) |
| { |
| if (bitset->blist.length <= count) |
| { |
| bitset->grow(bitset, count+1); |
| } |
| |
| bitset->blist.bits[count] = *((inBits->bits)+count); |
| count++; |
| } |
| } |
| |
| // return the new bitset |
| // |
| return bitset; |
| } |
| |
| /// |
| /// \brief |
| /// Creates a new bitset with at least one element, but as |
| /// many elements are required. |
| /// |
| /// \param[in] bit |
| /// A variable number of bits to add to the set, ending in -1 (impossible bit). |
| /// |
| /// \returns |
| /// A new bit set with all of the specified elements added into it. |
| /// |
| /// Call as: |
| /// - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1); |
| /// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset |
| /// |
| /// \remarks |
| /// Stdargs function - must supply -1 as last paremeter, which is NOT |
| /// added to the set. |
| /// |
| /// |
| ANTLR3_API pANTLR3_BITSET |
| antlr3BitsetOf(ANTLR3_INT32 bit, ...) |
| { |
| pANTLR3_BITSET bitset; |
| |
| va_list ap; |
| |
| // Allocate memory for the bitset structure itself |
| // the input parameter is the bit number (0 based) |
| // to include in the bitset, so we need at at least |
| // bit + 1 bits. If any arguments indicate a |
| // a bit higher than the default number of bits (0 menas default size) |
| // then Add() will take care |
| // of it. |
| // |
| bitset = antlr3BitsetNew(0); |
| |
| if (bitset == NULL) |
| { |
| return NULL; |
| } |
| |
| // Now we can add the element bits into the set |
| // |
| va_start(ap, bit); |
| while (bit != -1) |
| { |
| antlr3BitsetAdd(bitset, bit); |
| bit = va_arg(ap, ANTLR3_UINT32); |
| } |
| va_end(ap); |
| |
| // return the new bitset |
| // |
| return bitset; |
| } |
| |
| static pANTLR3_BITSET |
| antlr3BitsetOR(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2) |
| { |
| pANTLR3_BITSET bitset; |
| |
| if (bitset1 == NULL) |
| { |
| return antlr3BitsetClone(bitset2); |
| } |
| |
| if (bitset2 == NULL) |
| { |
| return antlr3BitsetClone(bitset1); |
| } |
| |
| // Allocate memory for the newly ordered bitset structure itself. |
| // |
| bitset = antlr3BitsetClone(bitset1); |
| |
| antlr3BitsetORInPlace(bitset, bitset2); |
| |
| return bitset; |
| |
| } |
| |
| static void |
| antlr3BitsetAdd(pANTLR3_BITSET bitset, ANTLR3_INT32 bit) |
| { |
| ANTLR3_UINT32 word; |
| |
| word = wordNumber(bit); |
| |
| if (word >= bitset->blist.length) |
| { |
| growToInclude(bitset, bit); |
| } |
| |
| bitset->blist.bits[word] |= bitMask(bit); |
| |
| } |
| |
| static void |
| grow(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize) |
| { |
| pANTLR3_BITWORD newBits; |
| |
| // Space for newly sized bitset - TODO: come back to this and use realloc?, it may |
| // be more efficient... |
| // |
| newBits = (pANTLR3_BITWORD) ANTLR3_CALLOC(1, (size_t)(newSize * sizeof(ANTLR3_BITWORD))); |
| if (bitset->blist.bits != NULL) |
| { |
| // Copy existing bits |
| // |
| ANTLR3_MEMCPY((void *)newBits, (const void *)bitset->blist.bits, (size_t)(bitset->blist.length * sizeof(ANTLR3_BITWORD))); |
| |
| // Out with the old bits... de de de derrr |
| // |
| ANTLR3_FREE(bitset->blist.bits); |
| } |
| |
| // In with the new bits... keerrrang. |
| // |
| bitset->blist.bits = newBits; |
| bitset->blist.length = newSize; |
| } |
| |
| static void |
| growToInclude(pANTLR3_BITSET bitset, ANTLR3_INT32 bit) |
| { |
| ANTLR3_UINT32 bl; |
| ANTLR3_UINT32 nw; |
| |
| bl = (bitset->blist.length << 1); |
| nw = numWordsToHold(bit); |
| |
| if (bl > nw) |
| { |
| bitset->grow(bitset, bl); |
| } |
| else |
| { |
| bitset->grow(bitset, nw); |
| } |
| } |
| |
| static void |
| antlr3BitsetORInPlace(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2) |
| { |
| ANTLR3_UINT32 minimum; |
| ANTLR3_UINT32 i; |
| |
| if (bitset2 == NULL) |
| { |
| return; |
| } |
| |
| |
| // First make sure that the target bitset is big enough |
| // for the new bits to be ored in. |
| // |
| if (bitset->blist.length < bitset2->blist.length) |
| { |
| growToInclude(bitset, (bitset2->blist.length * sizeof(ANTLR3_BITWORD))); |
| } |
| |
| // Or the miniimum number of bits after any resizing went on |
| // |
| if (bitset->blist.length < bitset2->blist.length) |
| { |
| minimum = bitset->blist.length; |
| } |
| else |
| { |
| minimum = bitset2->blist.length; |
| } |
| |
| for (i = minimum; i > 0; i--) |
| { |
| bitset->blist.bits[i-1] |= bitset2->blist.bits[i-1]; |
| } |
| } |
| |
| static ANTLR3_UINT64 |
| bitMask(ANTLR3_UINT32 bitNumber) |
| { |
| return ((ANTLR3_UINT64)1) << (bitNumber & (ANTLR3_BITSET_MOD_MASK)); |
| } |
| |
| static ANTLR3_UINT32 |
| antlr3BitsetSize(pANTLR3_BITSET bitset) |
| { |
| ANTLR3_UINT32 degree; |
| ANTLR3_INT32 i; |
| ANTLR3_INT8 bit; |
| |
| // TODO: Come back to this, it may be faster to & with 0x01 |
| // then shift right a copy of the 4 bits, than shift left a constant of 1. |
| // But then again, the optimizer might just work this out |
| // anyway. |
| // |
| degree = 0; |
| for (i = bitset->blist.length - 1; i>= 0; i--) |
| { |
| if (bitset->blist.bits[i] != 0) |
| { |
| for (bit = ANTLR3_BITSET_BITS - 1; bit >= 0; bit--) |
| { |
| if ((bitset->blist.bits[i] & (((ANTLR3_BITWORD)1) << bit)) != 0) |
| { |
| degree++; |
| } |
| } |
| } |
| } |
| return degree; |
| } |
| |
| static ANTLR3_BOOLEAN |
| antlr3BitsetEquals(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2) |
| { |
| ANTLR3_INT32 minimum; |
| ANTLR3_INT32 i; |
| |
| if (bitset1 == NULL || bitset2 == NULL) |
| { |
| return ANTLR3_FALSE; |
| } |
| |
| // Work out the minimum comparison set |
| // |
| if (bitset1->blist.length < bitset2->blist.length) |
| { |
| minimum = bitset1->blist.length; |
| } |
| else |
| { |
| minimum = bitset2->blist.length; |
| } |
| |
| // Make sure explict in common bits are equal |
| // |
| for (i = minimum - 1; i >=0 ; i--) |
| { |
| if (bitset1->blist.bits[i] != bitset2->blist.bits[i]) |
| { |
| return ANTLR3_FALSE; |
| } |
| } |
| |
| // Now make sure the bits of the larger set are all turned |
| // off. |
| // |
| if (bitset1->blist.length > (ANTLR3_UINT32)minimum) |
| { |
| for (i = minimum ; (ANTLR3_UINT32)i < bitset1->blist.length; i++) |
| { |
| if (bitset1->blist.bits[i] != 0) |
| { |
| return ANTLR3_FALSE; |
| } |
| } |
| } |
| else if (bitset2->blist.length > (ANTLR3_UINT32)minimum) |
| { |
| for (i = minimum; (ANTLR3_UINT32)i < bitset2->blist.length; i++) |
| { |
| if (bitset2->blist.bits[i] != 0) |
| { |
| return ANTLR3_FALSE; |
| } |
| } |
| } |
| |
| return ANTLR3_TRUE; |
| } |
| |
| static ANTLR3_BOOLEAN |
| antlr3BitsetMember(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit) |
| { |
| ANTLR3_UINT32 wordNo; |
| |
| wordNo = wordNumber(bit); |
| |
| if (wordNo >= bitset->blist.length) |
| { |
| return ANTLR3_FALSE; |
| } |
| |
| if ((bitset->blist.bits[wordNo] & bitMask(bit)) == 0) |
| { |
| return ANTLR3_FALSE; |
| } |
| else |
| { |
| return ANTLR3_TRUE; |
| } |
| } |
| |
| static void |
| antlr3BitsetRemove(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit) |
| { |
| ANTLR3_UINT32 wordNo; |
| |
| wordNo = wordNumber(bit); |
| |
| if (wordNo < bitset->blist.length) |
| { |
| bitset->blist.bits[wordNo] &= ~(bitMask(bit)); |
| } |
| } |
| static ANTLR3_BOOLEAN |
| antlr3BitsetIsNil(pANTLR3_BITSET bitset) |
| { |
| ANTLR3_INT32 i; |
| |
| for (i = bitset->blist.length -1; i>= 0; i--) |
| { |
| if (bitset->blist.bits[i] != 0) |
| { |
| return ANTLR3_FALSE; |
| } |
| } |
| |
| return ANTLR3_TRUE; |
| } |
| |
| static ANTLR3_UINT32 |
| numWordsToHold(ANTLR3_UINT32 bit) |
| { |
| return (bit >> ANTLR3_BITSET_LOG_BITS) + 1; |
| } |
| |
| static ANTLR3_UINT32 |
| wordNumber(ANTLR3_UINT32 bit) |
| { |
| return bit >> ANTLR3_BITSET_LOG_BITS; |
| } |
| |
| static ANTLR3_UINT32 |
| antlr3BitsetNumBits(pANTLR3_BITSET bitset) |
| { |
| return bitset->blist.length << ANTLR3_BITSET_LOG_BITS; |
| } |
| |
| /** Produce an integer list of all the bits that are turned on |
| * in this bitset. Used for error processing in the main as the bitset |
| * reresents a number of integer tokens which we use for follow sets |
| * and so on. |
| * |
| * The first entry is the number of elements following in the list. |
| */ |
| static pANTLR3_INT32 |
| antlr3BitsetToIntList (pANTLR3_BITSET bitset) |
| { |
| ANTLR3_UINT32 numInts; // How many integers we will need |
| ANTLR3_UINT32 numBits; // How many bits are in the set |
| ANTLR3_UINT32 i; |
| ANTLR3_UINT32 index; |
| |
| pANTLR3_INT32 intList; |
| |
| numInts = bitset->size(bitset) + 1; |
| numBits = bitset->numBits(bitset); |
| |
| intList = (pANTLR3_INT32)ANTLR3_MALLOC(numInts * sizeof(ANTLR3_INT32)); |
| |
| if (intList == NULL) |
| { |
| return NULL; // Out of memory |
| } |
| |
| intList[0] = numInts; |
| |
| // Enumerate the bits that are turned on |
| // |
| for (i = 0, index = 1; i<numBits; i++) |
| { |
| if (bitset->isMember(bitset, i) == ANTLR3_TRUE) |
| { |
| intList[index++] = i; |
| } |
| } |
| |
| // Result set |
| // |
| return intList; |
| } |
| |