sfx2/source/bastyp/bitset.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*************************************************************************
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * Copyright 2000, 2010 Oracle and/or its affiliates.
   7  *
   8  * OpenOffice.org - a multi-platform office productivity suite
   9  *
  10  * This file is part of OpenOffice.org.
  11  *
  12  * OpenOffice.org is free software: you can redistribute it and/or modify
  13  * it under the terms of the GNU Lesser General Public License version 3
  14  * only, as published by the Free Software Foundation.
  15  *
  16  * OpenOffice.org is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU Lesser General Public License version 3 for more details
  20  * (a copy is included in the LICENSE file that accompanied this code).
  21  *
  22  * You should have received a copy of the GNU Lesser General Public License
  23  * version 3 along with OpenOffice.org.  If not, see
  24  * <http://www.openoffice.org/license.html>
  25  * for a copy of the LGPLv3 License.
  26  *
  27  ************************************************************************/
  28
  29 #include <tools/debug.hxx>
  30
  31 #include "bitset.hxx"
  32
  33 #include <string.h>     // memset(), memcpy()
  34 #include <limits.h>     // USHRT_MAX
  35
  36 //====================================================================
  37 // add nOffset to each bit-value in the set
  38
  39 BitSet BitSet::operator<<( sal_uInt16 nOffset ) const
  40 {
  41     // create a work-copy, return it if nothing to shift
  42     BitSet aSet(*this);
  43     if ( nOffset == 0 )
  44         return aSet;
  45
  46     // compute the shiftment in long-words and bits
  47     sal_uInt16 nBlockDiff = nOffset / 32;
  48     sal_uIntPtr nBitValDiff = nOffset % 32;
  49
  50     // compute the new number of bits
  51     for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock )
  52         aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
  53     aSet.nCount = aSet.nCount -
  54         CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );
  55
  56     // shift complete long-words
  57     sal_uInt16 nTarget, nSource;
  58     for ( nTarget = 0, nSource = nBlockDiff;
  59           (nSource+1) < aSet.nBlocks;
  60           ++nTarget, ++nSource )
  61         *(aSet.pBitmap+nTarget) =
  62             ( *(aSet.pBitmap+nSource) << nBitValDiff ) |
  63             ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );
  64
  65     // shift the remainder (if in total minor 32 bits, only this)
  66     *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;
  67
  68     // determine the last used block
  69     while ( *(aSet.pBitmap+nTarget) == 0 )
  70         --nTarget;
  71
  72     // shorten the block-array
  73     if ( nTarget < aSet.nBlocks )
  74     {
  75         sal_uIntPtr* pNewMap = new sal_uIntPtr[nTarget];
  76         memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
  77         delete [] aSet.pBitmap;
  78         aSet.pBitmap = pNewMap;
  79         aSet.nBlocks = nTarget;
  80     }
  81
  82     return aSet;
  83 }
  84
  85 //--------------------------------------------------------------------
  86
  87 // substracts nOffset from each bit-value in the set
  88
  89 BitSet BitSet::operator>>( sal_uInt16 ) const
  90 {
  91     return BitSet();
  92 }
  93
  94 //--------------------------------------------------------------------
  95
  96 // internal code for operator= and copy-ctor
  97
  98 void BitSet::CopyFrom( const BitSet& rSet )
  99 {
 100     nCount = rSet.nCount;
 101     nBlocks = rSet.nBlocks;
 102     if ( rSet.nBlocks )
 103     {
 104         pBitmap = new sal_uIntPtr[nBlocks];
 105         memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
 106     }
 107     else
 108         pBitmap = 0;
 109 }
 110
 111 //--------------------------------------------------------------------
 112
 113 // creates an empty bitset
 114
 115 BitSet::BitSet()
 116 {
 117     nCount = 0;
 118     nBlocks = 0;
 119     pBitmap = 0;
 120 }
 121
 122 //--------------------------------------------------------------------
 123
 124 // creates a copy of bitset rOrig
 125
 126 BitSet::BitSet( const BitSet& rOrig )
 127 {
 128     CopyFrom(rOrig);
 129 }
 130
 131 //--------------------------------------------------------------------
 132
 133 // frees the storage
 134
 135 BitSet::~BitSet()
 136 {
 137     delete [] pBitmap;
 138 }
 139
 140 //--------------------------------------------------------------------
 141
 142 // assignment from another bitset
 143
 144 BitSet& BitSet::operator=( const BitSet& rOrig )
 145 {
 146     if ( this != &rOrig )
 147     {
 148         delete [] pBitmap;
 149         CopyFrom(rOrig);
 150     }
 151     return *this;
 152 }
 153
 154 //--------------------------------------------------------------------
 155
 156 // assignment from a single bit
 157
 158 BitSet& BitSet::operator=( sal_uInt16 nBit )
 159 {
 160     delete [] pBitmap;
 161
 162     nBlocks = nBit / 32;
 163     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 164     nCount = 1;
 165
 166     pBitmap = new sal_uIntPtr[nBlocks + 1];
 167     memset( pBitmap, 0, 4 * (nBlocks + 1) );
 168
 169     *(pBitmap+nBlocks) = nBitVal;
 170
 171     return *this;
 172 }
 173
 174 //--------------------------------------------------------------------
 175
 176 // creates the asymetric difference with another bitset
 177
 178 BitSet& BitSet::operator-=(sal_uInt16 nBit)
 179 {
 180     sal_uInt16 nBlock = nBit / 32;
 181     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 182
 183     if ( nBlock >= nBlocks )
 184       return *this;
 185
 186     if ( (*(pBitmap+nBlock) & nBitVal) )
 187     {
 188         *(pBitmap+nBlock) &= ~nBitVal;
 189         --nCount;
 190     }
 191
 192     return *this;
 193 }
 194
 195 //--------------------------------------------------------------------
 196
 197 // unites with the bits of rSet
 198
 199 BitSet& BitSet::operator|=( const BitSet& rSet )
 200 {
 201     sal_uInt16 nMax = Min(nBlocks, rSet.nBlocks);
 202
 203     // expand the bitmap
 204     if ( nBlocks < rSet.nBlocks )
 205     {
 206         sal_uIntPtr *pNewMap = new sal_uIntPtr[rSet.nBlocks];
 207         memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );
 208
 209         if ( pBitmap )
 210         {
 211             memcpy( pNewMap, pBitmap, 4 * nBlocks );
 212             delete [] pBitmap;
 213         }
 214         pBitmap = pNewMap;
 215         nBlocks = rSet.nBlocks;
 216     }
 217
 218     // add the bits blocks by block
 219     for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock )
 220     {
 221         // compute numberof additional bits
 222         sal_uIntPtr nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
 223         nCount = nCount + CountBits(nDiff);
 224
 225         *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
 226     }
 227
 228     return *this;
 229 }
 230
 231 //--------------------------------------------------------------------
 232
 233 // unites with a single bit
 234
 235 BitSet& BitSet::operator|=( sal_uInt16 nBit )
 236 {
 237     sal_uInt16 nBlock = nBit / 32;
 238     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 239
 240     if ( nBlock >= nBlocks )
 241     {
 242         sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1];
 243         memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
 244
 245         if ( pBitmap )
 246         {
 247             memcpy( pNewMap, pBitmap, 4 * nBlocks );
 248             delete [] pBitmap;
 249         }
 250         pBitmap = pNewMap;
 251         nBlocks = nBlock+1;
 252     }
 253
 254     if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
 255     {
 256         *(pBitmap+nBlock) |= nBitVal;
 257         ++nCount;
 258     }
 259
 260     return *this;
 261 }
 262
 263 //--------------------------------------------------------------------
 264
 265 // determines if the bit is set (may be the only one)
 266
 267 sal_Bool BitSet::Contains( sal_uInt16 nBit ) const
 268 {
 269     sal_uInt16 nBlock = nBit / 32;
 270     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 271
 272     if ( nBlock >= nBlocks )
 273         return sal_False;
 274     return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
 275 }
 276
 277 //--------------------------------------------------------------------
 278
 279 // determines if the bitsets are equal
 280
 281 sal_Bool BitSet::operator==( const BitSet& rSet ) const
 282 {
 283     if ( nBlocks != rSet.nBlocks )
 284         return sal_False;
 285
 286     sal_uInt16 nBlock = nBlocks;
 287     while ( nBlock-- > 0 )
 288         if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
 289             return sal_False;
 290
 291     return sal_True;
 292 }
 293
 294 //--------------------------------------------------------------------
 295
 296 // counts the number of 1-bits in the parameter
 297
 298 sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits )
 299 {
 300     sal_uInt16 nCount = 0;
 301     int nBit = 32;
 302     while ( nBit-- && nBits )
 303     {   if ( ( (long)nBits ) < 0 )
 304             ++nCount;
 305         nBits = nBits << 1;
 306     }
 307     return nCount;
 308 }
 309
 310 //--------------------------------------------------------------------
 311
 312 sal_uInt16 IndexBitSet::GetFreeIndex()
 313 {
 314   for(sal_uInt16 i=0;i<USHRT_MAX;i++)
 315     if(!Contains(i))
 316       {
 317         *this|=i;
 318         return i;
 319       }
 320   DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
 321   return 0;
 322 }
 323
 324
 325 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */