X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.databoard%2Fcpp%2FDataBoardTest%2Flibantlr3c-3.2%2Fsrc%2Fantlr3bitset.c;fp=bundles%2Forg.simantics.databoard%2Fcpp%2FDataBoardTest%2Flibantlr3c-3.2%2Fsrc%2Fantlr3bitset.c;h=37cc0ad965c414aea186ab8927c7e1fad2e9b483;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/src/antlr3bitset.c b/bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/src/antlr3bitset.c new file mode 100644 index 000000000..37cc0ad96 --- /dev/null +++ b/bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/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 + +// 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; iisMember(bitset, i) == ANTLR3_TRUE) + { + intList[index++] = i; + } + } + + // Result set + // + return intList; +} +