aboutsummaryrefslogtreecommitdiff
path: root/runtime/C/src/antlr3bitset.c
diff options
context:
space:
mode:
Diffstat (limited to 'runtime/C/src/antlr3bitset.c')
-rw-r--r--runtime/C/src/antlr3bitset.c681
1 files changed, 681 insertions, 0 deletions
diff --git a/runtime/C/src/antlr3bitset.c b/runtime/C/src/antlr3bitset.c
new file mode 100644
index 0000000..4e63c79
--- /dev/null
+++ b/runtime/C/src/antlr3bitset.c
@@ -0,0 +1,681 @@
+///
+/// \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;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-18 04:06:06 +0000