diff options
author | antonovvk <antonovvk@yandex-team.ru> | 2022-02-10 16:47:51 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:51 +0300 |
commit | 37a63debdc21e372d99e1808cdd31aecf75018c3 (patch) | |
tree | fd84293fb9a1b16381dd6c1a5e14c78afacb8710 /contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl | |
parent | 1fe621e70df847cc201ac942fe6d7804ea10508d (diff) | |
download | ydb-37a63debdc21e372d99e1808cdd31aecf75018c3.tar.gz |
Restoring authorship annotation for <antonovvk@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 | 582 |
1 files changed, 291 insertions, 291 deletions
diff --git a/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl b/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl index 64318ea0ea..37dfa88a1f 100644 --- a/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl +++ b/contrib/libs/antlr3_cpp_runtime/include/antlr3bitset.inl @@ -1,46 +1,46 @@ namespace antlr3 { - -template <class ImplTraits> -ANTLR_INLINE BitsetList<ImplTraits>::BitsetList() -{ + +template <class ImplTraits> +ANTLR_INLINE BitsetList<ImplTraits>::BitsetList() +{ m_bits = NULL; m_length = 0; -} - -template <class ImplTraits> -ANTLR_INLINE BitsetList<ImplTraits>::BitsetList( ANTLR_BITWORD* bits, ANTLR_UINT32 length ) -{ +} + +template <class ImplTraits> +ANTLR_INLINE BitsetList<ImplTraits>::BitsetList( ANTLR_BITWORD* bits, ANTLR_UINT32 length ) +{ m_bits = bits; m_length = length; -} - -template <class ImplTraits> -ANTLR_INLINE ANTLR_BITWORD* BitsetList<ImplTraits>::get_bits() const -{ +} + +template <class ImplTraits> +ANTLR_INLINE ANTLR_BITWORD* BitsetList<ImplTraits>::get_bits() const +{ return m_bits; -} - -template <class ImplTraits> -ANTLR_INLINE ANTLR_UINT32 BitsetList<ImplTraits>::get_length() const -{ +} + +template <class ImplTraits> +ANTLR_INLINE ANTLR_UINT32 BitsetList<ImplTraits>::get_length() const +{ return m_length; -} - -template <class ImplTraits> -ANTLR_INLINE void BitsetList<ImplTraits>::set_bits( ANTLR_BITWORD* bits ) -{ +} + +template <class ImplTraits> +ANTLR_INLINE void BitsetList<ImplTraits>::set_bits( ANTLR_BITWORD* bits ) +{ m_bits = bits; -} - -template <class ImplTraits> -ANTLR_INLINE void BitsetList<ImplTraits>::set_length( ANTLR_UINT32 length ) -{ +} + +template <class ImplTraits> +ANTLR_INLINE void BitsetList<ImplTraits>::set_length( ANTLR_UINT32 length ) +{ m_length = length; -} - -template <class ImplTraits> -typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetLoad() -{ +} + +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 @@ -50,7 +50,7 @@ typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetLoad( // of it. // BitsetType* bitset = new BitsetType(); - + if (this != NULL) { // Now we can add the element bits into the set @@ -60,142 +60,142 @@ typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetLoad( { 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() -{ +} + +template <class ImplTraits> +typename BitsetList<ImplTraits>::BitsetType* BitsetList<ImplTraits>::bitsetCopy() +{ BitsetType* bitset; ANTLR_UINT32 numElements = m_length; - - // Avoid memory thrashing at the expense of a few more bytes - // + + // Avoid memory thrashing at the expense of a few more bytes + // if (numElements < 8) numElements = 8; - - // Allocate memory for the bitset structure itself - // - bitset = new Bitset<ImplTraits>(numElements); + + // Allocate memory for the bitset structure itself + // + bitset = new Bitset<ImplTraits>(numElements); memcpy(bitset->get_blist().get_bits(), m_bits, numElements * sizeof(ANTLR_BITWORD)); - - // All seems good - // - return bitset; -} - -template <class ImplTraits> -Bitset<ImplTraits>::Bitset( ANTLR_UINT32 numBits ) -{ + + // All seems good + // + return bitset; +} + +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; - + // 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_length( numelements ); -} - -template <class ImplTraits> -Bitset<ImplTraits>::Bitset( const Bitset& bitset ) +} + +template <class ImplTraits> +Bitset<ImplTraits>::Bitset( const Bitset& bitset ) :m_blist(bitset.m_blist) -{ -} - -template <class ImplTraits> -ANTLR_INLINE Bitset<ImplTraits>* Bitset<ImplTraits>::clone() const -{ +{ +} + +template <class ImplTraits> +ANTLR_INLINE Bitset<ImplTraits>* Bitset<ImplTraits>::clone() const +{ Bitset* bitset; - - // Allocate memory for the bitset structure itself - // - bitset = new Bitset( ANTLR_BITSET_BITS * m_blist.get_length() ); - - // Install the actual bits in the source set - // + + // Allocate memory for the bitset structure itself + // + bitset = new Bitset( ANTLR_BITSET_BITS * m_blist.get_length() ); + + // 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) ); - - // All seems good - // - return bitset; -} - -template <class ImplTraits> -Bitset<ImplTraits>* Bitset<ImplTraits>::bor(Bitset* bitset2) -{ + + // All seems good + // + return bitset; +} + +template <class ImplTraits> +Bitset<ImplTraits>* Bitset<ImplTraits>::bor(Bitset* bitset2) +{ Bitset* bitset; - + if (this == NULL) return bitset2->clone(); - + if (bitset2 == NULL) return this->clone(); - - // Allocate memory for the newly ordered bitset structure itself. - // - bitset = this->clone(); - bitset->bitsetORInPlace(bitset2); - return bitset; -} - -template <class ImplTraits> + + // Allocate memory for the newly ordered bitset structure itself. + // + bitset = this->clone(); + bitset->bitsetORInPlace(bitset2); + return bitset; +} + +template <class ImplTraits> void Bitset<ImplTraits>::borInPlace(Bitset* bitset2) -{ +{ ANTLR_UINT32 minimum; - + if (bitset2 == NULL) return; - + // First make sure that the target bitset is big enough - // for the new bits to be ored in. - // + // 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) ); - // Or the miniimum number of bits after any resizing went on - // + // 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(); - + 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> -ANTLR_UINT32 Bitset<ImplTraits>::size() const -{ - ANTLR_UINT32 degree; - ANTLR_INT32 i; - ANTLR_INT8 bit; +} + +template <class ImplTraits> +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; + // 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--) - { + { if (bits[i] != 0) { for(bit = ANTLR_BITSET_BITS - 1; bit >= 0; bit--) @@ -206,141 +206,141 @@ ANTLR_UINT32 Bitset<ImplTraits>::size() const } } } - } - return degree; -} - -template <class ImplTraits> + } + return degree; +} + +template <class ImplTraits> ANTLR_INLINE void Bitset<ImplTraits>::add(ANTLR_INT32 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); -} - -template <class ImplTraits> +} + +template <class ImplTraits> void Bitset<ImplTraits>::grow(ANTLR_INT32 newSize) -{ +{ 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) ); + + // 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) - { + { // 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() ); - } - - // In with the new bits... keerrrang. - // - m_blist.set_bits(newBits); - m_blist.set_length(newSize); -} - -template <class ImplTraits> + } + + // In with the new bits... keerrrang. + // + m_blist.set_bits(newBits); + m_blist.set_length(newSize); +} + +template <class ImplTraits> bool Bitset<ImplTraits>::equals(Bitset* bitset2) const -{ - ANTLR_UINT32 minimum; - ANTLR_UINT32 i; - +{ + ANTLR_UINT32 minimum; + ANTLR_UINT32 i; + if (this == NULL || bitset2 == NULL) return false; - - // Work out the minimum comparison set - // + + // Work out the minimum comparison set + // if ( m_blist.get_length() < bitset2->m_blist.get_length() ) minimum = m_blist.get_length(); - else + else minimum = bitset2->m_blist.get_length(); - - // Make sure explict in common bits are equal - // + + // Make sure explict in common bits are equal + // 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; - } - - // Now make sure the bits of the larger set are all turned - // off. - // + } + + // Now make sure the bits of the larger set are all turned + // off. + // 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; } - } - else if (bitset2->m_blist.get_length() > minimum) - { + } + 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; } - } - - return true; -} - -template <class ImplTraits> + } + + return true; +} + +template <class ImplTraits> bool Bitset<ImplTraits>::isMember(ANTLR_UINT32 bit) const -{ - ANTLR_UINT32 wordNo = Bitset::WordNumber(bit); - +{ + 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; - else + else return true; -} - -template <class ImplTraits> -ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::numBits() const -{ +} + +template <class ImplTraits> +ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::numBits() const +{ return m_blist.get_length() << ANTLR_BITSET_LOG_BITS; -} - -template <class ImplTraits> -ANTLR_INLINE typename ImplTraits::BitsetListType& Bitset<ImplTraits>::get_blist() -{ +} + +template <class ImplTraits> +ANTLR_INLINE typename ImplTraits::BitsetListType& Bitset<ImplTraits>::get_blist() +{ return m_blist; -} - -template <class ImplTraits> -ANTLR_INLINE void Bitset<ImplTraits>::remove(ANTLR_UINT32 bit) -{ - ANTLR_UINT32 wordNo = Bitset::WordNumber(bit); - +} + +template <class ImplTraits> +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)); } -} - -template <class ImplTraits> -ANTLR_INLINE bool Bitset<ImplTraits>::isNilNode() const -{ +} + +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--) @@ -349,144 +349,144 @@ ANTLR_INLINE bool Bitset<ImplTraits>::isNilNode() const return false; } return true; -} - -template <class ImplTraits> -ANTLR_INT32* Bitset<ImplTraits>::toIntList() const -{ +} + +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 i; - ANTLR_UINT32 index; - - ANTLR_INT32* intList; - - numInts = this->size() + 1; - numBits = this->numBits(); - - intList = (ANTLR_INT32*) AllocPolicyType::alloc(numInts * sizeof(ANTLR_INT32)); + ANTLR_UINT32 i; + ANTLR_UINT32 index; + + ANTLR_INT32* intList; + + 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 - // + intList[0] = numInts; + + // Enumerate the bits that are turned on + // for (i = 0, index = 1; i<numBits; i++) - { + { if (this->isMember(i) == true) intList[index++] = i; - } - - // Result set - // - return intList; -} - -template <class ImplTraits> -ANTLR_INLINE Bitset<ImplTraits>::~Bitset() -{ + } + + // Result set + // + return intList; +} + +template <class ImplTraits> +ANTLR_INLINE Bitset<ImplTraits>::~Bitset() +{ if (m_blist.get_bits() != NULL) AllocPolicyType::free(m_blist.get_bits()); - return; -} - -template <class ImplTraits> + return; +} + +template <class ImplTraits> void Bitset<ImplTraits>::growToInclude(ANTLR_INT32 bit) -{ +{ ANTLR_UINT32 bl; ANTLR_UINT32 nw; - + bl = (m_blist.get_length() << 1); nw = Bitset::NumWordsToHold(bit); - + if (bl > nw) this->grow(bl); else this->grow(nw); -} - -template <class ImplTraits> +} + +template <class ImplTraits> ANTLR_INLINE ANTLR_UINT64 Bitset<ImplTraits>::BitMask(ANTLR_UINT32 bitNumber) -{ +{ return ((ANTLR_UINT64)1) << (bitNumber & (ANTLR_BITSET_MOD_MASK)); -} - -template <class ImplTraits> +} + +template <class ImplTraits> ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::NumWordsToHold(ANTLR_UINT32 bit) -{ +{ return (bit >> ANTLR_BITSET_LOG_BITS) + 1; -} - -template <class ImplTraits> +} + +template <class ImplTraits> ANTLR_INLINE ANTLR_UINT32 Bitset<ImplTraits>::WordNumber(ANTLR_UINT32 bit) -{ +{ return bit >> ANTLR_BITSET_LOG_BITS; -} - -template <class ImplTraits> -void Bitset<ImplTraits>::bitsetORInPlace(Bitset* bitset2) -{ +} + +template <class ImplTraits> +void Bitset<ImplTraits>::bitsetORInPlace(Bitset* bitset2) +{ ANTLR_UINT32 minimum; - ANTLR_UINT32 i; - + ANTLR_UINT32 i; + if (bitset2 == NULL) return; - - // First make sure that the target bitset is big enough - // for the new bits to be ored in. - // + + // 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) ); - // Or the miniimum number of bits after any resizing went on - // + // 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(); - + 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) -{ +} + +template <class ImplTraits> +Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetOf(ANTLR_INT32 bit) +{ // 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 + // 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. - // + // 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; -} - -template <class ImplTraits> -Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetOf(ANTLR_INT32 bit1, ANTLR_INT32 bit2) -{ +} + +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; -} - +} + //static -template <class ImplTraits> -Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetFromList(const IntListType& list) -{ +template <class ImplTraits> +Bitset<ImplTraits>* Bitset<ImplTraits>::BitsetFromList(const IntListType& 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); + // 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] ); - + return bitset; -} - +} + } |