sfx2/source/bastyp/bitset.cxx

   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>     // memset(), memcpy()
  25 #include <limits.h>     // USHRT_MAX
  26 #include <algorithm>
  27
  28 //====================================================================
  29 // add nOffset to each bit-value in the set
  30
  31 BitSet BitSet::operator<<( sal_uInt16 nOffset ) const
  32 {
  33     // create a work-copy, return it if nothing to shift
  34     BitSet aSet(*this);
  35     if ( nOffset == 0 )
  36         return aSet;
  37
  38     // compute the shiftment in long-words and bits
  39     sal_uInt16 nBlockDiff = nOffset / 32;
  40     sal_uIntPtr nBitValDiff = nOffset % 32;
  41
  42     // compute the new number of bits
  43     for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock )
  44         aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
  45     aSet.nCount = aSet.nCount -
  46         CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );
  47
  48     // shift complete long-words
  49     sal_uInt16 nTarget, nSource;
  50     for ( nTarget = 0, nSource = nBlockDiff;
  51           (nSource+1) < aSet.nBlocks;
  52           ++nTarget, ++nSource )
  53         *(aSet.pBitmap+nTarget) =
  54             ( *(aSet.pBitmap+nSource) << nBitValDiff ) |
  55             ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );
  56
  57     // shift the remainder (if in total minor 32 bits, only this)
  58     *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;
  59
  60     // determine the last used block
  61     while ( *(aSet.pBitmap+nTarget) == 0 )
  62         --nTarget;
  63
  64     // shorten the block-array
  65     if ( nTarget < aSet.nBlocks )
  66     {
  67         sal_uIntPtr* pNewMap = new sal_uIntPtr[nTarget];
  68         memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
  69         delete [] aSet.pBitmap;
  70         aSet.pBitmap = pNewMap;
  71         aSet.nBlocks = nTarget;
  72     }
  73
  74     return aSet;
  75 }
  76
  77 //--------------------------------------------------------------------
  78
  79 // substracts nOffset from each bit-value in the set
  80
  81 BitSet BitSet::operator>>( sal_uInt16 ) const
  82 {
  83     return BitSet();
  84 }
  85
  86 //--------------------------------------------------------------------
  87
  88 // internal code for operator= and copy-ctor
  89
  90 void BitSet::CopyFrom( const BitSet& rSet )
  91 {
  92     nCount = rSet.nCount;
  93     nBlocks = rSet.nBlocks;
  94     if ( rSet.nBlocks )
  95     {
  96         pBitmap = new sal_uIntPtr[nBlocks];
  97         memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
  98     }
  99     else
 100         pBitmap = 0;
 101 }
 102
 103 //--------------------------------------------------------------------
 104
 105 // creates an empty bitset
 106
 107 BitSet::BitSet()
 108 {
 109     nCount = 0;
 110     nBlocks = 0;
 111     pBitmap = 0;
 112 }
 113
 114 //--------------------------------------------------------------------
 115
 116 // creates a copy of bitset rOrig
 117
 118 BitSet::BitSet( const BitSet& rOrig )
 119 {
 120     CopyFrom(rOrig);
 121 }
 122
 123 //--------------------------------------------------------------------
 124
 125 // frees the storage
 126
 127 BitSet::~BitSet()
 128 {
 129     delete [] pBitmap;
 130 }
 131
 132 //--------------------------------------------------------------------
 133
 134 // assignment from another bitset
 135
 136 BitSet& BitSet::operator=( const BitSet& rOrig )
 137 {
 138     if ( this != &rOrig )
 139     {
 140         delete [] pBitmap;
 141         CopyFrom(rOrig);
 142     }
 143     return *this;
 144 }
 145
 146 //--------------------------------------------------------------------
 147
 148 // assignment from a single bit
 149
 150 BitSet& BitSet::operator=( sal_uInt16 nBit )
 151 {
 152     delete [] pBitmap;
 153
 154     nBlocks = nBit / 32;
 155     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 156     nCount = 1;
 157
 158     pBitmap = new sal_uIntPtr[nBlocks + 1];
 159     memset( pBitmap, 0, 4 * (nBlocks + 1) );
 160
 161     *(pBitmap+nBlocks) = nBitVal;
 162
 163     return *this;
 164 }
 165
 166 //--------------------------------------------------------------------
 167
 168 // creates the asymetric difference with another bitset
 169
 170 BitSet& BitSet::operator-=(sal_uInt16 nBit)
 171 {
 172     sal_uInt16 nBlock = nBit / 32;
 173     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 174
 175     if ( nBlock >= nBlocks )
 176       return *this;
 177
 178     if ( (*(pBitmap+nBlock) & nBitVal) )
 179     {
 180         *(pBitmap+nBlock) &= ~nBitVal;
 181         --nCount;
 182     }
 183
 184     return *this;
 185 }
 186
 187 //--------------------------------------------------------------------
 188
 189 // unites with the bits of rSet
 190
 191 BitSet& BitSet::operator|=( const BitSet& rSet )
 192 {
 193     sal_uInt16 nMax = std::min(nBlocks, rSet.nBlocks);
 194
 195     // expand the bitmap
 196     if ( nBlocks < rSet.nBlocks )
 197     {
 198         sal_uIntPtr *pNewMap = new sal_uIntPtr[rSet.nBlocks];
 199         memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );
 200
 201         if ( pBitmap )
 202         {
 203             memcpy( pNewMap, pBitmap, 4 * nBlocks );
 204             delete [] pBitmap;
 205         }
 206         pBitmap = pNewMap;
 207         nBlocks = rSet.nBlocks;
 208     }
 209
 210     // add the bits blocks by block
 211     for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock )
 212     {
 213         // compute numberof additional bits
 214         sal_uIntPtr nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
 215         nCount = nCount + CountBits(nDiff);
 216
 217         *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
 218     }
 219
 220     return *this;
 221 }
 222
 223 //--------------------------------------------------------------------
 224
 225 // unites with a single bit
 226
 227 BitSet& BitSet::operator|=( sal_uInt16 nBit )
 228 {
 229     sal_uInt16 nBlock = nBit / 32;
 230     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 231
 232     if ( nBlock >= nBlocks )
 233     {
 234         sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1];
 235         memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
 236
 237         if ( pBitmap )
 238         {
 239             memcpy( pNewMap, pBitmap, 4 * nBlocks );
 240             delete [] pBitmap;
 241         }
 242         pBitmap = pNewMap;
 243         nBlocks = nBlock+1;
 244     }
 245
 246     if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
 247     {
 248         *(pBitmap+nBlock) |= nBitVal;
 249         ++nCount;
 250     }
 251
 252     return *this;
 253 }
 254
 255 //--------------------------------------------------------------------
 256
 257 // determines if the bit is set (may be the only one)
 258
 259 sal_Bool BitSet::Contains( sal_uInt16 nBit ) const
 260 {
 261     sal_uInt16 nBlock = nBit / 32;
 262     sal_uIntPtr nBitVal = 1L << (nBit % 32);
 263
 264     if ( nBlock >= nBlocks )
 265         return sal_False;
 266     return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
 267 }
 268
 269 //--------------------------------------------------------------------
 270
 271 // determines if the bitsets are equal
 272
 273 sal_Bool BitSet::operator==( const BitSet& rSet ) const
 274 {
 275     if ( nBlocks != rSet.nBlocks )
 276         return sal_False;
 277
 278     sal_uInt16 nBlock = nBlocks;
 279     while ( nBlock-- > 0 )
 280         if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
 281             return sal_False;
 282
 283     return sal_True;
 284 }
 285
 286 //--------------------------------------------------------------------
 287
 288 // counts the number of 1-bits in the parameter
 289
 290 sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits )
 291 {
 292     sal_uInt16 nCount = 0;
 293     int nBit = 32;
 294     while ( nBit-- && nBits )
 295     {   if ( ( (long)nBits ) < 0 )
 296             ++nCount;
 297         nBits = nBits << 1;
 298     }
 299     return nCount;
 300 }
 301
 302 //--------------------------------------------------------------------
 303
 304 sal_uInt16 IndexBitSet::GetFreeIndex()
 305 {
 306   for(sal_uInt16 i=0;i<USHRT_MAX;i++)
 307     if(!Contains(i))
 308       {
 309         *this|=i;
 310         return i;
 311       }
 312   DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
 313   return 0;
 314 }
 315
 316
 317 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */