/************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * *************************************************************/ // MARKER(update_precomp.py): autogen include statement, do not remove #include "precompiled_sfx2.hxx" #include #ifndef GCC #endif #include "bitset.hxx" #include // memset(), memcpy() #include // USHRT_MAX //==================================================================== // add nOffset to each bit-value in the set BitSet BitSet::operator<<( sal_uInt16 nOffset ) const { DBG_MEMTEST(); // create a work-copy, return it if nothing to shift BitSet aSet(*this); if ( nOffset == 0 ) return aSet; // compute the shiftment in long-words and bits sal_uInt16 nBlockDiff = nOffset / 32; sal_uIntPtr nBitValDiff = nOffset % 32; // compute the new number of bits for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock ) aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) ); aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) ); // shift complete long-words sal_uInt16 nTarget, nSource; for ( nTarget = 0, nSource = nBlockDiff; (nSource+1) < aSet.nBlocks; ++nTarget, ++nSource ) *(aSet.pBitmap+nTarget) = ( *(aSet.pBitmap+nSource) << nBitValDiff ) | ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) ); // shift the remainder (if in total minor 32 bits, only this) *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff; // determine the last used block while ( *(aSet.pBitmap+nTarget) == 0 ) --nTarget; // shorten the block-array if ( nTarget < aSet.nBlocks ) { sal_uIntPtr* pNewMap = new sal_uIntPtr[nTarget]; memcpy( pNewMap, aSet.pBitmap, 4 * nTarget ); delete [] aSet.pBitmap; aSet.pBitmap = pNewMap; aSet.nBlocks = nTarget; } return aSet; } //-------------------------------------------------------------------- // subtracts nOffset from each bit-value in the set BitSet BitSet::operator>>( sal_uInt16 ) const { DBG_MEMTEST(); return BitSet(); } //-------------------------------------------------------------------- // internal code for operator= and copy-ctor void BitSet::CopyFrom( const BitSet& rSet ) { DBG_MEMTEST(); nCount = rSet.nCount; nBlocks = rSet.nBlocks; if ( rSet.nBlocks ) { DBG_MEMTEST(); pBitmap = new sal_uIntPtr[nBlocks]; memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks ); } else pBitmap = 0; } //-------------------------------------------------------------------- // creates an empty bitset BitSet::BitSet() { DBG_MEMTEST(); nCount = 0; nBlocks = 0; pBitmap = 0; } //-------------------------------------------------------------------- // creates a copy of bitset rOrig BitSet::BitSet( const BitSet& rOrig ) { DBG_MEMTEST(); CopyFrom(rOrig); } //-------------------------------------------------------------------- // creates a bitset from an array BitSet::BitSet( sal_uInt16* pArray, sal_uInt16 nSize ): nCount(nSize) { DBG_MEMTEST(); // find the highest bit to set sal_uInt16 nMax = 0; for ( sal_uInt16 n = 0; n < nCount; ++n ) if ( pArray[n] > nMax ) nMax = pArray[n]; // if there are bits at all if ( nMax > 0 ) { // allocate memory for all blocks needed nBlocks = nMax / 32 + 1; pBitmap = new sal_uIntPtr[nBlocks]; memset( pBitmap, 0, 4 * nBlocks ); // set all the bits for ( sal_uInt16 n = 0; n < nCount; ++n ) { // compute the block no. and bitvalue sal_uInt16 nBlock = n / 32; sal_uIntPtr nBitVal = 1L << (n % 32); // set a single bit if ( ( *(pBitmap+nBlock) & nBitVal ) == 0 ) { *(pBitmap+nBlock) |= nBitVal; ++nCount; } } } else { // initialize emtpy set nBlocks = 0; pBitmap = 0; } } //-------------------------------------------------------------------- // frees the storage BitSet::~BitSet() { DBG_MEMTEST(); delete [] pBitmap; } //-------------------------------------------------------------------- // creates a bitmap with all bits in rRange set BitSet::BitSet( const Range& ) { DBG_MEMTEST(); } //-------------------------------------------------------------------- // assignment from another bitset BitSet& BitSet::operator=( const BitSet& rOrig ) { DBG_MEMTEST(); if ( this != &rOrig ) { delete [] pBitmap; CopyFrom(rOrig); } return *this; } //-------------------------------------------------------------------- // assignment from a single bit BitSet& BitSet::operator=( sal_uInt16 nBit ) { DBG_MEMTEST(); delete [] pBitmap; nBlocks = nBit / 32; sal_uIntPtr nBitVal = 1L << (nBit % 32); nCount = 1; pBitmap = new sal_uIntPtr[nBlocks]; memset( pBitmap + nBlocks, 0, 4 * nBlocks ); *(pBitmap+nBlocks) = nBitVal; return *this; } //-------------------------------------------------------------------- // creates the asymetric difference with another bitset BitSet& BitSet::operator-=(sal_uInt16 nBit) { DBG_MEMTEST(); sal_uInt16 nBlock = nBit / 32; sal_uIntPtr nBitVal = 1L << (nBit % 32); if ( nBlock >= nBlocks ) return *this; if ( (*(pBitmap+nBlock) & nBitVal) ) { *(pBitmap+nBlock) &= ~nBitVal; --nCount; } return *this; } //-------------------------------------------------------------------- // unites with the bits of rSet BitSet& BitSet::operator|=( const BitSet& rSet ) { DBG_MEMTEST(); sal_uInt16 nMax = Min(nBlocks, rSet.nBlocks); // expand the bitmap if ( nBlocks < rSet.nBlocks ) { sal_uIntPtr *pNewMap = new sal_uIntPtr[rSet.nBlocks]; memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) ); if ( pBitmap ) { memcpy( pNewMap, pBitmap, 4 * nBlocks ); delete [] pBitmap; } pBitmap = pNewMap; nBlocks = rSet.nBlocks; } // add the bits blocks by block for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock ) { // compute numberof additional bits sal_uIntPtr nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock); nCount = nCount + CountBits(nDiff); *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock); } return *this; } //-------------------------------------------------------------------- // unites with a single bit BitSet& BitSet::operator|=( sal_uInt16 nBit ) { DBG_MEMTEST(); sal_uInt16 nBlock = nBit / 32; sal_uIntPtr nBitVal = 1L << (nBit % 32); if ( nBlock >= nBlocks ) { sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1]; memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) ); if ( pBitmap ) { memcpy( pNewMap, pBitmap, 4 * nBlocks ); delete [] pBitmap; } pBitmap = pNewMap; nBlocks = nBlock+1; } if ( (*(pBitmap+nBlock) & nBitVal) == 0 ) { *(pBitmap+nBlock) |= nBitVal; ++nCount; } return *this; } //-------------------------------------------------------------------- // determines if the bit is set (may be the only one) sal_Bool BitSet::Contains( sal_uInt16 nBit ) const { DBG_MEMTEST(); sal_uInt16 nBlock = nBit / 32; sal_uIntPtr nBitVal = 1L << (nBit % 32); if ( nBlock >= nBlocks ) return sal_False; return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal; } //-------------------------------------------------------------------- // determines if the bitsets are equal sal_Bool BitSet::operator==( const BitSet& rSet ) const { DBG_MEMTEST(); if ( nBlocks != rSet.nBlocks ) return sal_False; sal_uInt16 nBlock = nBlocks; while ( nBlock-- > 0 ) if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) ) return sal_False; return sal_True; } //-------------------------------------------------------------------- // counts the number of 1-bits in the parameter sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits ) { sal_uInt16 nCount = 0; int nBit = 32; while ( nBit-- && nBits ) { if ( ( (long)nBits ) < 0 ) ++nCount; nBits = nBits << 1; } return nCount; } //-------------------------------------------------------------------- sal_uInt16 IndexBitSet::GetFreeIndex() { for(sal_uInt16 i=0;i