diff options
author | isiv <isiv@yandex-team.ru> | 2022-02-10 16:47:54 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:54 +0300 |
commit | f20e3f1949626df2ef9d81d7618ec367b0c34f6b (patch) | |
tree | 36465c9262a386743fc483efb848be6d76c5ac04 /contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl | |
parent | 7a839432184dcd989efaeccf678e4238d71bd9b0 (diff) | |
download | ydb-f20e3f1949626df2ef9d81d7618ec367b0c34f6b.tar.gz |
Restoring authorship annotation for <isiv@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl')
-rw-r--r-- | contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl | 410 |
1 files changed, 205 insertions, 205 deletions
diff --git a/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl b/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl index 64318ea0ea..9d49a317dd 100644 --- a/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl +++ b/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl @@ -1,92 +1,92 @@ -namespace antlr3 { +namespace antlr3 { template <class ImplTraits> ANTLR_INLINE BitsetList<ImplTraits>::BitsetList() { - m_bits = NULL; - m_length = 0; + m_bits = NULL; + m_length = 0; } template <class ImplTraits> ANTLR_INLINE BitsetList<ImplTraits>::BitsetList( ANTLR_BITWORD* bits, ANTLR_UINT32 length ) { - m_bits = bits; - m_length = length; + m_bits = bits; + m_length = length; } template <class ImplTraits> ANTLR_INLINE ANTLR_BITWORD* BitsetList<ImplTraits>::get_bits() const { - return m_bits; + return m_bits; } template <class ImplTraits> ANTLR_INLINE ANTLR_UINT32 BitsetList<ImplTraits>::get_length() const { - return m_length; + return m_length; } template <class ImplTraits> ANTLR_INLINE void BitsetList<ImplTraits>::set_bits( ANTLR_BITWORD* bits ) { - m_bits = bits; + m_bits = bits; } template <class ImplTraits> ANTLR_INLINE void BitsetList<ImplTraits>::set_length( ANTLR_UINT32 length ) { - m_length = length; + m_length = length; } template <class ImplTraits> typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetLoad() { - // 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. - // - BitsetType* bitset = new BitsetType(); - - if (this != NULL) - { - // Now we can add the element bits into the set - // - ANTLR_UINT32 count=0; - while (count < m_length) - { - if( bitset->get_blist().get_length() <= count) - bitset->grow(count+1); - - typename ImplTraits::BitsetListType& blist = bitset->get_blist(); - blist.m_bits[count] = *(m_bits+count); - count++; - } - } - - // return the new bitset - // - return bitset; + // 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. + // + BitsetType* bitset = new BitsetType(); + + if (this != NULL) + { + // Now we can add the element bits into the set + // + ANTLR_UINT32 count=0; + while (count < m_length) + { + if( bitset->get_blist().get_length() <= count) + bitset->grow(count+1); + + typename ImplTraits::BitsetListType& blist = bitset->get_blist(); + blist.m_bits[count] = *(m_bits+count); + count++; + } + } + + // return the new bitset + // + return bitset; } template <class ImplTraits> typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetCopy() { - BitsetType* bitset; - ANTLR_UINT32 numElements = m_length; + BitsetType* bitset; + ANTLR_UINT32 numElements = m_length; // Avoid memory thrashing at the expense of a few more bytes // - if (numElements < 8) - numElements = 8; + if (numElements < 8) + numElements = 8; // Allocate memory for the bitset structure itself // bitset = new Bitset<ImplTraits>(numElements); - memcpy(bitset->get_blist().get_bits(), m_bits, numElements * sizeof(ANTLR_BITWORD)); + memcpy(bitset->get_blist().get_bits(), m_bits, numElements * sizeof(ANTLR_BITWORD)); // All seems good // @@ -96,30 +96,30 @@ typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetCopy( template <class ImplTraits> Bitset<ImplTraits>::Bitset( ANTLR_UINT32 numBits ) { - // Avoid memory thrashing at the up front expense of a few bytes - if (numBits < (8 * ANTLR_BITSET_BITS)) - numBits = 8 * ANTLR_BITSET_BITS; + // Avoid memory thrashing at the up front expense of a few bytes + if (numBits < (8 * ANTLR_BITSET_BITS)) + numBits = 8 * ANTLR_BITSET_BITS; - // No we need to allocate the memory for the number of bits asked for - // in multiples of ANTLR3_UINT64. - // - ANTLR_UINT32 numelements = ((numBits -1) >> ANTLR_BITSET_LOG_BITS) + 1; + // No we need to allocate the memory for the number of bits asked for + // in multiples of ANTLR3_UINT64. + // + ANTLR_UINT32 numelements = ((numBits -1) >> ANTLR_BITSET_LOG_BITS) + 1; - m_blist.set_bits( (ANTLR_BITWORD*) AllocPolicyType::alloc0(numelements * sizeof(ANTLR_BITWORD))); + m_blist.set_bits( (ANTLR_BITWORD*) AllocPolicyType::alloc0(numelements * sizeof(ANTLR_BITWORD))); - m_blist.set_length( numelements ); + m_blist.set_length( numelements ); } template <class ImplTraits> Bitset<ImplTraits>::Bitset( const Bitset& bitset ) - :m_blist(bitset.m_blist) + :m_blist(bitset.m_blist) { } template <class ImplTraits> ANTLR_INLINE Bitset<ImplTraits>* Bitset<ImplTraits>::clone() const { - Bitset* bitset; + Bitset* bitset; // Allocate memory for the bitset structure itself // @@ -127,8 +127,8 @@ ANTLR_INLINE Bitset<ImplTraits>* Bitset<ImplTraits>::clone() const // Install the actual bits in the source set // - memcpy(bitset->m_blist.get_bits(), m_blist.get_bits(), - m_blist.get_length() * sizeof(ANTLR_BITWORD) ); + memcpy(bitset->m_blist.get_bits(), m_blist.get_bits(), + m_blist.get_length() * sizeof(ANTLR_BITWORD) ); // All seems good // @@ -138,13 +138,13 @@ ANTLR_INLINE Bitset<ImplTraits>* Bitset<ImplTraits>::clone() const template <class ImplTraits> Bitset<ImplTraits>* Bitset<ImplTraits>::bor(Bitset* bitset2) { - Bitset* bitset; + Bitset* bitset; - if (this == NULL) - return bitset2->clone(); + if (this == NULL) + return bitset2->clone(); - if (bitset2 == NULL) - return this->clone(); + if (bitset2 == NULL) + return this->clone(); // Allocate memory for the newly ordered bitset structure itself. // @@ -154,30 +154,30 @@ Bitset<ImplTraits>* Bitset<ImplTraits>::bor(Bitset* bitset2) } template <class ImplTraits> -void Bitset<ImplTraits>::borInPlace(Bitset* bitset2) +void Bitset<ImplTraits>::borInPlace(Bitset* bitset2) { - ANTLR_UINT32 minimum; + ANTLR_UINT32 minimum; - if (bitset2 == NULL) - return; + if (bitset2 == NULL) + return; - // First make sure that the target bitset is big enough + // First make sure that the target bitset is big enough // for the new bits to be ored in. // - if ( m_blist.get_length() < bitset2->m_blist.get_length() ) - this->growToInclude( bitset2->m_blist.get_length() * sizeof(ANTLR_BITWORD) ); - + if ( m_blist.get_length() < bitset2->m_blist.get_length() ) + this->growToInclude( bitset2->m_blist.get_length() * sizeof(ANTLR_BITWORD) ); + // Or the miniimum number of bits after any resizing went on // - if ( m_blist.get_length() < bitset2->m_blist.get_length() ) - minimum = m_blist.get_length(); - else - minimum = bitset2->m_blist.get_length(); + if ( m_blist.get_length() < bitset2->m_blist.get_length() ) + minimum = m_blist.get_length(); + else + minimum = bitset2->m_blist.get_length(); - ANTLR_BITWORD* bits1 = m_blist.get_bits(); - ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits(); - for (ANTLR_UINT32 i = minimum; i > 0; i--) - bits1[i-1] |= bits2[i-1]; + ANTLR_BITWORD* bits1 = m_blist.get_bits(); + ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits(); + for (ANTLR_UINT32 i = minimum; i > 0; i--) + bits1[i-1] |= bits2[i-1]; } template <class ImplTraits> @@ -186,60 +186,60 @@ ANTLR_UINT32 Bitset<ImplTraits>::size() const ANTLR_UINT32 degree; ANTLR_INT32 i; ANTLR_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; - ANTLR_BITWORD* bits = m_blist.get_bits(); - for (i = m_blist.get_length() - 1; i>= 0; i--) + ANTLR_BITWORD* bits = m_blist.get_bits(); + for (i = m_blist.get_length() - 1; i>= 0; i--) { - if (bits[i] != 0) - { - for(bit = ANTLR_BITSET_BITS - 1; bit >= 0; bit--) - { - if((bits[i] & (((ANTLR_BITWORD)1) << bit)) != 0) - { - degree++; - } - } - } + if (bits[i] != 0) + { + for(bit = ANTLR_BITSET_BITS - 1; bit >= 0; bit--) + { + if((bits[i] & (((ANTLR_BITWORD)1) << bit)) != 0) + { + degree++; + } + } + } } return degree; } template <class ImplTraits> -ANTLR_INLINE void Bitset<ImplTraits>::add(ANTLR_INT32 bit) +ANTLR_INLINE void Bitset<ImplTraits>::add(ANTLR_INT32 bit) { - ANTLR_UINT32 word = Bitset::WordNumber(bit); + ANTLR_UINT32 word = Bitset::WordNumber(bit); - if (word >= m_blist.get_length() ) - this->growToInclude(bit); - - ANTLR_BITWORD* bits = m_blist.get_bits(); - bits[word] |= Bitset::BitMask(bit); + if (word >= m_blist.get_length() ) + this->growToInclude(bit); + + ANTLR_BITWORD* bits = m_blist.get_bits(); + bits[word] |= Bitset::BitMask(bit); } template <class ImplTraits> -void Bitset<ImplTraits>::grow(ANTLR_INT32 newSize) +void Bitset<ImplTraits>::grow(ANTLR_INT32 newSize) { - ANTLR_BITWORD* newBits; + ANTLR_BITWORD* newBits; // Space for newly sized bitset - TODO: come back to this and use realloc?, it may // be more efficient... // newBits = (ANTLR_BITWORD*) AllocPolicyType::alloc0(newSize * sizeof(ANTLR_BITWORD) ); - if ( m_blist.get_bits() != NULL) + if ( m_blist.get_bits() != NULL) { - // Copy existing bits - // - memcpy( newBits, m_blist.get_bits(), m_blist.get_length() * sizeof(ANTLR_BITWORD) ); + // Copy existing bits + // + memcpy( newBits, m_blist.get_bits(), m_blist.get_length() * sizeof(ANTLR_BITWORD) ); - // Out with the old bits... de de de derrr - // - AllocPolicyType::free( m_blist.get_bits() ); + // Out with the old bits... de de de derrr + // + AllocPolicyType::free( m_blist.get_bits() ); } // In with the new bits... keerrrang. @@ -249,81 +249,81 @@ void Bitset<ImplTraits>::grow(ANTLR_INT32 newSize) } template <class ImplTraits> -bool Bitset<ImplTraits>::equals(Bitset* bitset2) const +bool Bitset<ImplTraits>::equals(Bitset* bitset2) const { ANTLR_UINT32 minimum; ANTLR_UINT32 i; - if (this == NULL || bitset2 == NULL) - return false; + if (this == NULL || bitset2 == NULL) + return false; // Work out the minimum comparison set // - if ( m_blist.get_length() < bitset2->m_blist.get_length() ) - minimum = m_blist.get_length(); + if ( m_blist.get_length() < bitset2->m_blist.get_length() ) + minimum = m_blist.get_length(); else - minimum = bitset2->m_blist.get_length(); + minimum = bitset2->m_blist.get_length(); // Make sure explict in common bits are equal // - for (i = minimum - 1; i < minimum ; i--) + for (i = minimum - 1; i < minimum ; i--) { - ANTLR_BITWORD* bits1 = m_blist.get_bits(); - ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits(); - if ( bits1[i] != bits2[i]) - return false; + ANTLR_BITWORD* bits1 = m_blist.get_bits(); + ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits(); + if ( bits1[i] != bits2[i]) + return false; } // Now make sure the bits of the larger set are all turned // off. // - if ( m_blist.get_length() > minimum) + if ( m_blist.get_length() > minimum) { - for (i = minimum ; i < m_blist.get_length(); i++) - { - ANTLR_BITWORD* bits = m_blist.get_bits(); - if(bits[i] != 0) - return false; - } + for (i = minimum ; i < m_blist.get_length(); i++) + { + ANTLR_BITWORD* bits = m_blist.get_bits(); + if(bits[i] != 0) + return false; + } } else if (bitset2->m_blist.get_length() > minimum) { - ANTLR_BITWORD* bits = m_blist.get_bits(); - for (i = minimum; i < bitset2->m_blist.get_length(); i++) - { - if ( bits[i] != 0 ) - return false; - } + ANTLR_BITWORD* bits = m_blist.get_bits(); + for (i = minimum; i < bitset2->m_blist.get_length(); i++) + { + if ( bits[i] != 0 ) + return false; + } } return true; } template <class ImplTraits> -bool Bitset<ImplTraits>::isMember(ANTLR_UINT32 bit) const +bool Bitset<ImplTraits>::isMember(ANTLR_UINT32 bit) const { ANTLR_UINT32 wordNo = Bitset::WordNumber(bit); - if (wordNo >= m_blist.get_length()) - return false; - - ANTLR_BITWORD* bits = m_blist.get_bits(); - if ( (bits[wordNo] & Bitset::BitMask(bit)) == 0) - return false; + if (wordNo >= m_blist.get_length()) + return false; + + ANTLR_BITWORD* bits = m_blist.get_bits(); + if ( (bits[wordNo] & Bitset::BitMask(bit)) == 0) + return false; else - return true; + return true; } template <class ImplTraits> ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::numBits() const { - return m_blist.get_length() << ANTLR_BITSET_LOG_BITS; + return m_blist.get_length() << ANTLR_BITSET_LOG_BITS; } template <class ImplTraits> ANTLR_INLINE typename ImplTraits::BitsetListType& Bitset<ImplTraits>::get_blist() { - return m_blist; + return m_blist; } template <class ImplTraits> @@ -331,31 +331,31 @@ ANTLR_INLINE void Bitset<ImplTraits>::remove(ANTLR_UINT32 bit) { ANTLR_UINT32 wordNo = Bitset::WordNumber(bit); - if (wordNo < m_blist.get_length()) - { - ANTLR_BITWORD* bits = m_blist.get_bits(); - bits[wordNo] &= ~(Bitset::BitMask(bit)); - } + if (wordNo < m_blist.get_length()) + { + ANTLR_BITWORD* bits = m_blist.get_bits(); + bits[wordNo] &= ~(Bitset::BitMask(bit)); + } } template <class ImplTraits> ANTLR_INLINE bool Bitset<ImplTraits>::isNilNode() const { - ANTLR_UINT32 i; - ANTLR_BITWORD* bits = m_blist.get_bits(); - for (i = m_blist.get_length() -1 ; i < m_blist.get_length(); i--) - { - if(bits[i] != 0) - return false; - } - return true; + ANTLR_UINT32 i; + ANTLR_BITWORD* bits = m_blist.get_bits(); + for (i = m_blist.get_length() -1 ; i < m_blist.get_length(); i--) + { + if(bits[i] != 0) + return false; + } + return true; } template <class ImplTraits> ANTLR_INT32* Bitset<ImplTraits>::toIntList() const { - ANTLR_UINT32 numInts; // How many integers we will need - ANTLR_UINT32 numBits; // How many bits are in the set + ANTLR_UINT32 numInts; // How many integers we will need + ANTLR_UINT32 numBits; // How many bits are in the set ANTLR_UINT32 i; ANTLR_UINT32 index; @@ -363,17 +363,17 @@ ANTLR_INT32* Bitset<ImplTraits>::toIntList() const numInts = this->size() + 1; numBits = this->numBits(); - + intList = (ANTLR_INT32*) AllocPolicyType::alloc(numInts * sizeof(ANTLR_INT32)); - + intList[0] = numInts; // Enumerate the bits that are turned on // - for (i = 0, index = 1; i<numBits; i++) + for (i = 0, index = 1; i<numBits; i++) { - if (this->isMember(i) == true) - intList[index++] = i; + if (this->isMember(i) == true) + intList[index++] = i; } // Result set @@ -384,109 +384,109 @@ ANTLR_INT32* Bitset<ImplTraits>::toIntList() const template <class ImplTraits> ANTLR_INLINE Bitset<ImplTraits>::~Bitset() { - if (m_blist.get_bits() != NULL) - AllocPolicyType::free(m_blist.get_bits()); + if (m_blist.get_bits() != NULL) + AllocPolicyType::free(m_blist.get_bits()); return; } template <class ImplTraits> -void Bitset<ImplTraits>::growToInclude(ANTLR_INT32 bit) +void Bitset<ImplTraits>::growToInclude(ANTLR_INT32 bit) { - ANTLR_UINT32 bl; - ANTLR_UINT32 nw; + ANTLR_UINT32 bl; + ANTLR_UINT32 nw; - bl = (m_blist.get_length() << 1); - nw = Bitset::NumWordsToHold(bit); + bl = (m_blist.get_length() << 1); + nw = Bitset::NumWordsToHold(bit); - if (bl > nw) - this->grow(bl); - else - this->grow(nw); + if (bl > nw) + this->grow(bl); + else + this->grow(nw); } template <class ImplTraits> -ANTLR_INLINE ANTLR_UINT64 Bitset<ImplTraits>::BitMask(ANTLR_UINT32 bitNumber) +ANTLR_INLINE ANTLR_UINT64 Bitset<ImplTraits>::BitMask(ANTLR_UINT32 bitNumber) { - return ((ANTLR_UINT64)1) << (bitNumber & (ANTLR_BITSET_MOD_MASK)); + return ((ANTLR_UINT64)1) << (bitNumber & (ANTLR_BITSET_MOD_MASK)); } template <class ImplTraits> -ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::NumWordsToHold(ANTLR_UINT32 bit) +ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::NumWordsToHold(ANTLR_UINT32 bit) { - return (bit >> ANTLR_BITSET_LOG_BITS) + 1; + return (bit >> ANTLR_BITSET_LOG_BITS) + 1; } template <class ImplTraits> -ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::WordNumber(ANTLR_UINT32 bit) +ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::WordNumber(ANTLR_UINT32 bit) { - return bit >> ANTLR_BITSET_LOG_BITS; + return bit >> ANTLR_BITSET_LOG_BITS; } template <class ImplTraits> void Bitset<ImplTraits>::bitsetORInPlace(Bitset* bitset2) { - ANTLR_UINT32 minimum; + ANTLR_UINT32 minimum; ANTLR_UINT32 i; - if (bitset2 == NULL) - return; + if (bitset2 == NULL) + return; // First make sure that the target bitset is big enough // for the new bits to be ored in. // - if ( m_blist.get_length() < bitset2->m_blist.get_length() ) - this->growToInclude( bitset2->m_blist.get_length() * sizeof(ANTLR_BITWORD) ); - + if ( m_blist.get_length() < bitset2->m_blist.get_length() ) + this->growToInclude( bitset2->m_blist.get_length() * sizeof(ANTLR_BITWORD) ); + // Or the miniimum number of bits after any resizing went on // - if ( m_blist.get_length() < bitset2->m_blist.get_length() ) - minimum = m_blist.get_length(); - else - minimum = bitset2->m_blist.get_length(); + if ( m_blist.get_length() < bitset2->m_blist.get_length() ) + minimum = m_blist.get_length(); + else + minimum = bitset2->m_blist.get_length(); - ANTLR_BITWORD* bits1 = m_blist.get_bits(); - ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits(); - for (i = minimum; i > 0; i--) - bits1[i-1] |= bits2[i-1]; + ANTLR_BITWORD* bits1 = m_blist.get_bits(); + ANTLR_BITWORD* bits2 = bitset2->m_blist.get_bits(); + for (i = minimum; i > 0; i--) + bits1[i-1] |= bits2[i-1]; } template <class ImplTraits> Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetOf(ANTLR_INT32 bit) { - // Allocate memory for the bitset structure itself + // 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 + // 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<ImplTraits>* bitset = new Bitset<ImplTraits>(0); - bitset->add(bit); - return bitset; + Bitset<ImplTraits>* bitset = new Bitset<ImplTraits>(0); + bitset->add(bit); + return bitset; } template <class ImplTraits> Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetOf(ANTLR_INT32 bit1, ANTLR_INT32 bit2) { - Bitset<ImplTraits>* bitset = Bitset<ImplTraits>::BitsetOf(bit1); - bitset->add(bit2); - return bitset; + Bitset<ImplTraits>* bitset = Bitset<ImplTraits>::BitsetOf(bit1); + bitset->add(bit2); + return bitset; } -//static +//static template <class ImplTraits> Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetFromList(const IntListType& list) { - // We have no idea what exactly is in the list + // We have no idea what exactly is in the list // so create a default bitset and then just add stuff // as we enumerate. // Bitset<ImplTraits>* bitset = new Bitset<ImplTraits>(0); - for( int i = 0; i < list.size(); ++i ) - bitset->add( list[i] ); + for( int i = 0; i < list.size(); ++i ) + bitset->add( list[i] ); - return bitset; + return bitset; } -} +} |