LCOV - code coverage report
Current view: top level - sfx2/source/bastyp - bitset.cxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 40 124 32.3 %
Date: 2015-06-13 12:38:46 Functions: 6 15 40.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : #include <tools/debug.hxx>
      21             : 
      22             : #include "bitset.hxx"
      23             : 
      24             : #include <string.h>
      25             : #include <limits.h>
      26             : #include <algorithm>
      27             : 
      28             : 
      29             : // add nOffset to each bit-value in the set
      30             : 
      31           0 : BitSet BitSet::operator<<( sal_uInt16 nOffset ) const
      32             : {
      33             :     // create a work-copy, return it if nothing to shift
      34           0 :     BitSet aSet(*this);
      35           0 :     if ( nOffset == 0 )
      36           0 :         return aSet;
      37             : 
      38             :     // compute the shiftment in long-words and bits
      39           0 :     sal_uInt16 nBlockDiff = nOffset / 32;
      40           0 :     sal_uInt32 nBitValDiff = nOffset % 32;
      41             : 
      42             :     // compute the new number of bits
      43           0 :     for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock )
      44           0 :         aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
      45             :     aSet.nCount = aSet.nCount -
      46           0 :         CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );
      47             : 
      48             :     // shift complete long-words
      49             :     sal_uInt16 nTarget, nSource;
      50           0 :     for ( nTarget = 0, nSource = nBlockDiff;
      51           0 :           (nSource+1) < aSet.nBlocks;
      52             :           ++nTarget, ++nSource )
      53           0 :         *(aSet.pBitmap+nTarget) =
      54           0 :             ( *(aSet.pBitmap+nSource) << nBitValDiff ) |
      55           0 :             ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );
      56             : 
      57             :     // shift the remainder (if in total minor 32 bits, only this)
      58           0 :     *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;
      59             : 
      60             :     // determine the last used block
      61           0 :     while ( *(aSet.pBitmap+nTarget) == 0 )
      62           0 :         --nTarget;
      63             : 
      64             :     // shorten the block-array
      65           0 :     if ( nTarget < aSet.nBlocks )
      66             :     {
      67           0 :         sal_uInt32* pNewMap = new sal_uInt32[nTarget];
      68           0 :         memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
      69           0 :         delete [] aSet.pBitmap;
      70           0 :         aSet.pBitmap = pNewMap;
      71           0 :         aSet.nBlocks = nTarget;
      72             :     }
      73             : 
      74           0 :     return aSet;
      75             : }
      76             : 
      77             : 
      78             : 
      79             : // subtracts nOffset from each bit-value in the set
      80             : 
      81           0 : BitSet BitSet::operator>>( sal_uInt16 ) const
      82             : {
      83           0 :     return BitSet();
      84             : }
      85             : 
      86             : 
      87             : 
      88             : // internal code for operator= and copy-ctor
      89             : 
      90           0 : void BitSet::CopyFrom( const BitSet& rSet )
      91             : {
      92           0 :     nCount = rSet.nCount;
      93           0 :     nBlocks = rSet.nBlocks;
      94           0 :     if ( rSet.nBlocks )
      95             :     {
      96           0 :         pBitmap = new sal_uInt32[nBlocks];
      97           0 :         memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
      98             :     }
      99             :     else
     100           0 :         pBitmap = 0;
     101           0 : }
     102             : 
     103             : 
     104             : 
     105             : // creates an empty bitset
     106             : 
     107        5149 : BitSet::BitSet()
     108             : {
     109        5149 :     nCount = 0;
     110        5149 :     nBlocks = 0;
     111        5149 :     pBitmap = 0;
     112        5149 : }
     113             : 
     114             : 
     115             : 
     116             : // creates a copy of bitset rOrig
     117             : 
     118           0 : BitSet::BitSet( const BitSet& rOrig )
     119             : {
     120           0 :     CopyFrom(rOrig);
     121           0 : }
     122             : 
     123             : 
     124             : 
     125             : // frees the storage
     126             : 
     127        5000 : BitSet::~BitSet()
     128             : {
     129        5000 :     delete [] pBitmap;
     130        5000 : }
     131             : 
     132             : 
     133             : 
     134             : // assignment from another bitset
     135             : 
     136           0 : BitSet& BitSet::operator=( const BitSet& rOrig )
     137             : {
     138           0 :     if ( this != &rOrig )
     139             :     {
     140           0 :         delete [] pBitmap;
     141           0 :         CopyFrom(rOrig);
     142             :     }
     143           0 :     return *this;
     144             : }
     145             : 
     146             : 
     147             : 
     148             : // assignment from a single bit
     149             : 
     150           0 : BitSet& BitSet::operator=( sal_uInt16 nBit )
     151             : {
     152           0 :     delete [] pBitmap;
     153             : 
     154           0 :     nBlocks = nBit / 32;
     155           0 :     sal_uInt32 nBitVal = 1L << (nBit % 32);
     156           0 :     nCount = 1;
     157             : 
     158           0 :     pBitmap = new sal_uInt32[nBlocks + 1];
     159           0 :     memset( pBitmap, 0, 4 * (nBlocks + 1) );
     160             : 
     161           0 :     *(pBitmap+nBlocks) = nBitVal;
     162             : 
     163           0 :     return *this;
     164             : }
     165             : 
     166             : 
     167             : 
     168             : // creates the asymetric difference with another bitset
     169             : 
     170        3871 : BitSet& BitSet::operator-=(sal_uInt16 nBit)
     171             : {
     172        3871 :     sal_uInt16 nBlock = nBit / 32;
     173        3871 :     sal_uInt32 nBitVal = 1L << (nBit % 32);
     174             : 
     175        3871 :     if ( nBlock >= nBlocks )
     176           0 :       return *this;
     177             : 
     178        3871 :     if ( (*(pBitmap+nBlock) & nBitVal) )
     179             :     {
     180        3871 :         *(pBitmap+nBlock) &= ~nBitVal;
     181        3871 :         --nCount;
     182             :     }
     183             : 
     184        3871 :     return *this;
     185             : }
     186             : 
     187             : 
     188             : 
     189             : // unites with the bits of rSet
     190             : 
     191           0 : BitSet& BitSet::operator|=( const BitSet& rSet )
     192             : {
     193           0 :     sal_uInt16 nMax = std::min(nBlocks, rSet.nBlocks);
     194             : 
     195             :     // expand the bitmap
     196           0 :     if ( nBlocks < rSet.nBlocks )
     197             :     {
     198           0 :         sal_uInt32 *pNewMap = new sal_uInt32[rSet.nBlocks];
     199           0 :         memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );
     200             : 
     201           0 :         if ( pBitmap )
     202             :         {
     203           0 :             memcpy( pNewMap, pBitmap, 4 * nBlocks );
     204           0 :             delete [] pBitmap;
     205             :         }
     206           0 :         pBitmap = pNewMap;
     207           0 :         nBlocks = rSet.nBlocks;
     208             :     }
     209             : 
     210             :     // add the bits blocks by block
     211           0 :     for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock )
     212             :     {
     213             :         // compute numberof additional bits
     214           0 :         sal_uInt32 nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
     215           0 :         nCount = nCount + CountBits(nDiff);
     216             : 
     217           0 :         *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
     218             :     }
     219             : 
     220           0 :     return *this;
     221             : }
     222             : 
     223             : 
     224             : 
     225             : // unites with a single bit
     226             : 
     227        3877 : BitSet& BitSet::operator|=( sal_uInt16 nBit )
     228             : {
     229        3877 :     sal_uInt16 nBlock = nBit / 32;
     230        3877 :     sal_uInt32 nBitVal = 1L << (nBit % 32);
     231             : 
     232        3877 :     if ( nBlock >= nBlocks )
     233             :     {
     234        3204 :         sal_uInt32 *pNewMap = new sal_uInt32[nBlock+1];
     235        3204 :         memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
     236             : 
     237        3204 :         if ( pBitmap )
     238             :         {
     239           0 :             memcpy( pNewMap, pBitmap, 4 * nBlocks );
     240           0 :             delete [] pBitmap;
     241             :         }
     242        3204 :         pBitmap = pNewMap;
     243        3204 :         nBlocks = nBlock+1;
     244             :     }
     245             : 
     246        3877 :     if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
     247             :     {
     248        3877 :         *(pBitmap+nBlock) |= nBitVal;
     249        3877 :         ++nCount;
     250             :     }
     251             : 
     252        3877 :     return *this;
     253             : }
     254             : 
     255             : 
     256             : 
     257             : // determines if the bit is set (may be the only one)
     258             : 
     259        3884 : bool BitSet::Contains( sal_uInt16 nBit ) const
     260             : {
     261        3884 :     sal_uInt16 nBlock = nBit / 32;
     262        3884 :     sal_uInt32 nBitVal = 1L << (nBit % 32);
     263             : 
     264        3884 :     if ( nBlock >= nBlocks )
     265        3204 :         return false;
     266         680 :     return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
     267             : }
     268             : 
     269             : 
     270             : 
     271             : // determines if the bitsets are equal
     272             : 
     273           0 : bool BitSet::operator==( const BitSet& rSet ) const
     274             : {
     275           0 :     if ( nBlocks != rSet.nBlocks )
     276           0 :         return false;
     277             : 
     278           0 :     sal_uInt16 nBlock = nBlocks;
     279           0 :     while ( nBlock-- > 0 )
     280           0 :         if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
     281           0 :             return false;
     282             : 
     283           0 :     return true;
     284             : }
     285             : 
     286             : // counts the number of 1-bits in the parameter
     287             : // Wegner/Kernighan/Ritchie method
     288           0 : sal_uInt16 BitSet::CountBits(sal_uInt32 nBits)
     289             : {
     290           0 :     sal_uInt32 nCount = 0;
     291           0 :     while (nBits)
     292             :     {
     293           0 :         nBits &= nBits - 1; // clear the least significant bit set
     294           0 :         ++nCount;
     295             :     }
     296           0 :     return nCount;
     297             : }
     298             : 
     299        3877 : sal_uInt16 IndexBitSet::GetFreeIndex()
     300             : {
     301        3884 :   for(int i=0;i<USHRT_MAX;i++)
     302        3884 :     if(!Contains(i))
     303             :       {
     304        3877 :         *this|=i;
     305        3877 :         return i;
     306             :       }
     307             :   DBG_ASSERT(false, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
     308           0 :   return 0;
     309             : }
     310             : 
     311             : 
     312             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.11