| /************************************************************** |
| * |
| * 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 <tools/debug.hxx> |
| #ifndef GCC |
| #endif |
| |
| #include "bitset.hxx" |
| |
| #include <string.h> // memset(), memcpy() |
| #include <limits.h> // 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; |
| } |
| |
| //-------------------------------------------------------------------- |
| |
| // substracts 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 |
| { |
| // initalize 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<USHRT_MAX;i++) |
| if(!Contains(i)) |
| { |
| *this|=i; |
| return i; |
| } |
| DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege"); |
| return 0; |
| } |
| |
| |
