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