sfx2/source/bastyp/bitset.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: bitset.cxx,v $
  10  * $Revision: 1.8 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_sfx2.hxx"
  33 #include <tools/debug.hxx>
  34 #ifndef GCC
  35 #endif
  36
  37 #include "bitset.hxx"
  38
  39 #include <string.h>             // memset(), memcpy()
  40 #include <limits.h>             // USHRT_MAX
  41
  42 //====================================================================
  43 // add nOffset to each bit-value in the set
  44
  45 BitSet BitSet::operator<<( USHORT nOffset ) const
  46 {
  47     DBG_MEMTEST();
  48     // create a work-copy, return it if nothing to shift
  49     BitSet aSet(*this);
  50     if ( nOffset == 0 )
  51         return aSet;
  52
  53     // compute the shiftment in long-words and bits
  54     USHORT nBlockDiff = nOffset / 32;
  55     ULONG nBitValDiff = nOffset % 32;
  56
  57     // compute the new number of bits
  58     for ( USHORT nBlock = 0; nBlock < nBlockDiff; ++nBlock )
  59         aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
  60     aSet.nCount = aSet.nCount -
  61         CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );
  62
  63     // shift complete long-words
  64     USHORT nTarget, nSource;
  65     for ( nTarget = 0, nSource = nBlockDiff;
  66           (nSource+1) < aSet.nBlocks;
  67           ++nTarget, ++nSource )
  68         *(aSet.pBitmap+nTarget) =
  69             ( *(aSet.pBitmap+nSource) << nBitValDiff ) |
  70             ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );
  71
  72     // shift the remainder (if in total minor 32 bits, only this)
  73     *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;
  74
  75     // determine the last used block
  76     while ( *(aSet.pBitmap+nTarget) == 0 )
  77         --nTarget;
  78
  79     // shorten the block-array
  80     if ( nTarget < aSet.nBlocks )
  81     {
  82         ULONG* pNewMap = new ULONG[nTarget];
  83         memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
  84         delete [] aSet.pBitmap;
  85         aSet.pBitmap = pNewMap;
  86         aSet.nBlocks = nTarget;
  87     }
  88
  89     return aSet;
  90 }
  91
  92 //--------------------------------------------------------------------
  93
  94 // substracts nOffset from each bit-value in the set
  95
  96 BitSet BitSet::operator>>( USHORT ) const
  97 {
  98     DBG_MEMTEST();
  99     return BitSet();
 100 }
 101
 102 //--------------------------------------------------------------------
 103
 104 // internal code for operator= and copy-ctor
 105
 106 void BitSet::CopyFrom( const BitSet& rSet )
 107 {
 108     DBG_MEMTEST();
 109     nCount = rSet.nCount;
 110     nBlocks = rSet.nBlocks;
 111     if ( rSet.nBlocks )
 112     {
 113         DBG_MEMTEST();
 114         pBitmap = new ULONG[nBlocks];
 115         memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
 116     }
 117     else
 118         pBitmap = 0;
 119 }
 120
 121 //--------------------------------------------------------------------
 122
 123 // creates an empty bitset
 124
 125 BitSet::BitSet()
 126 {
 127     DBG_MEMTEST();
 128     nCount = 0;
 129     nBlocks = 0;
 130     pBitmap = 0;
 131 }
 132
 133 //--------------------------------------------------------------------
 134
 135 // creates a copy of bitset rOrig
 136
 137 BitSet::BitSet( const BitSet& rOrig )
 138 {
 139     DBG_MEMTEST();
 140     CopyFrom(rOrig);
 141 }
 142
 143 //--------------------------------------------------------------------
 144
 145 // creates a bitset from an array
 146
 147 BitSet::BitSet( USHORT* pArray, USHORT nSize ):
 148     nCount(nSize)
 149 {
 150     DBG_MEMTEST();
 151     // find the highest bit to set
 152     USHORT nMax = 0;
 153     for ( USHORT n = 0; n < nCount; ++n )
 154         if ( pArray[n] > nMax )
 155             nMax = pArray[n];
 156
 157     // if there are bits at all
 158     if ( nMax > 0 )
 159     {
 160         // allocate memory for all blocks needed
 161         nBlocks = nMax / 32 + 1;
 162         pBitmap = new ULONG[nBlocks];
 163         memset( pBitmap, 0, 4 * nBlocks );
 164
 165         // set all the bits
 166         for ( USHORT n = 0; n < nCount; ++n )
 167         {
 168             // compute the block no. and bitvalue
 169             USHORT nBlock = n / 32;
 170             ULONG nBitVal = 1L << (n % 32);
 171
 172             // set a single bit
 173             if ( ( *(pBitmap+nBlock) & nBitVal ) == 0 )
 174             {
 175                 *(pBitmap+nBlock) |= nBitVal;
 176                 ++nCount;
 177             }
 178         }
 179     }
 180     else
 181     {
 182         // initalize emtpy set
 183         nBlocks = 0;
 184         pBitmap = 0;
 185     }
 186 }
 187
 188 //--------------------------------------------------------------------
 189
 190 // frees the storage
 191
 192 BitSet::~BitSet()
 193 {
 194     DBG_MEMTEST();
 195     delete [] pBitmap;
 196 }
 197
 198 //--------------------------------------------------------------------
 199
 200 // creates a bitmap with all bits in rRange set
 201
 202 BitSet::BitSet( const Range& )
 203 {
 204     DBG_MEMTEST();
 205 }
 206
 207 //--------------------------------------------------------------------
 208
 209 // assignment from another bitset
 210
 211 BitSet& BitSet::operator=( const BitSet& rOrig )
 212 {
 213     DBG_MEMTEST();
 214     if ( this != &rOrig )
 215     {
 216         delete [] pBitmap;
 217         CopyFrom(rOrig);
 218     }
 219     return *this;
 220 }
 221
 222 //--------------------------------------------------------------------
 223
 224 // assignment from a single bit
 225
 226 BitSet& BitSet::operator=( USHORT nBit )
 227 {
 228     DBG_MEMTEST();
 229     delete [] pBitmap;
 230
 231     nBlocks = nBit / 32;
 232     ULONG nBitVal = 1L << (nBit % 32);
 233     nCount = 1;
 234
 235     pBitmap = new ULONG[nBlocks];
 236     memset( pBitmap + nBlocks, 0, 4 * nBlocks );
 237
 238     *(pBitmap+nBlocks) = nBitVal;
 239
 240     return *this;
 241 }
 242
 243 //--------------------------------------------------------------------
 244
 245 // creates the asymetric difference with another bitset
 246
 247 BitSet& BitSet::operator-=(USHORT nBit)
 248 {
 249     DBG_MEMTEST();
 250     USHORT nBlock = nBit / 32;
 251     ULONG nBitVal = 1L << (nBit % 32);
 252
 253     if ( nBlock >= nBlocks )
 254       return *this;
 255
 256     if ( (*(pBitmap+nBlock) & nBitVal) )
 257     {
 258         *(pBitmap+nBlock) &= ~nBitVal;
 259         --nCount;
 260     }
 261
 262     return *this;
 263 }
 264
 265 //--------------------------------------------------------------------
 266
 267 // unites with the bits of rSet
 268
 269 BitSet& BitSet::operator|=( const BitSet& rSet )
 270 {
 271     DBG_MEMTEST();
 272     USHORT nMax = Min(nBlocks, rSet.nBlocks);
 273
 274     // expand the bitmap
 275     if ( nBlocks < rSet.nBlocks )
 276     {
 277         ULONG *pNewMap = new ULONG[rSet.nBlocks];
 278         memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );
 279
 280         if ( pBitmap )
 281         {
 282             memcpy( pNewMap, pBitmap, 4 * nBlocks );
 283             delete [] pBitmap;
 284         }
 285         pBitmap = pNewMap;
 286         nBlocks = rSet.nBlocks;
 287     }
 288
 289     // add the bits blocks by block
 290     for ( USHORT nBlock = 0; nBlock < nMax; ++nBlock )
 291     {
 292         // compute numberof additional bits
 293         ULONG nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
 294         nCount = nCount + CountBits(nDiff);
 295
 296         *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
 297     }
 298
 299     return *this;
 300 }
 301
 302 //--------------------------------------------------------------------
 303
 304 // unites with a single bit
 305
 306 BitSet& BitSet::operator|=( USHORT nBit )
 307 {
 308     DBG_MEMTEST();
 309     USHORT nBlock = nBit / 32;
 310     ULONG nBitVal = 1L << (nBit % 32);
 311
 312     if ( nBlock >= nBlocks )
 313     {
 314         ULONG *pNewMap = new ULONG[nBlock+1];
 315         memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
 316
 317         if ( pBitmap )
 318         {
 319             memcpy( pNewMap, pBitmap, 4 * nBlocks );
 320             delete [] pBitmap;
 321         }
 322         pBitmap = pNewMap;
 323         nBlocks = nBlock+1;
 324     }
 325
 326     if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
 327     {
 328         *(pBitmap+nBlock) |= nBitVal;
 329         ++nCount;
 330     }
 331
 332     return *this;
 333 }
 334
 335 //--------------------------------------------------------------------
 336
 337 // determines if the bit is set (may be the only one)
 338
 339 BOOL BitSet::Contains( USHORT nBit ) const
 340 {
 341     DBG_MEMTEST();
 342     USHORT nBlock = nBit / 32;
 343     ULONG nBitVal = 1L << (nBit % 32);
 344
 345     if ( nBlock >= nBlocks )
 346         return FALSE;
 347     return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
 348 }
 349
 350 //--------------------------------------------------------------------
 351
 352 // determines if the bitsets are equal
 353
 354 BOOL BitSet::operator==( const BitSet& rSet ) const
 355 {
 356     DBG_MEMTEST();
 357     if ( nBlocks != rSet.nBlocks )
 358         return FALSE;
 359
 360     USHORT nBlock = nBlocks;
 361     while ( nBlock-- > 0 )
 362         if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
 363             return FALSE;
 364
 365     return TRUE;
 366 }
 367
 368 //--------------------------------------------------------------------
 369
 370 // counts the number of 1-bits in the parameter
 371
 372 USHORT BitSet::CountBits( ULONG nBits )
 373 {
 374     USHORT nCount = 0;
 375     int nBit = 32;
 376     while ( nBit-- && nBits )
 377     {   if ( ( (long)nBits ) < 0 )
 378             ++nCount;
 379         nBits = nBits << 1;
 380     }
 381     return nCount;
 382 }
 383
 384 //--------------------------------------------------------------------
 385
 386 USHORT IndexBitSet::GetFreeIndex()
 387 {
 388   for(USHORT i=0;i<USHRT_MAX;i++)
 389     if(!Contains(i))
 390       {
 391         *this|=i;
 392         return i;
 393       }
 394   DBG_ASSERT(FALSE, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
 395   return 0;
 396 }
 397
 398