1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 // MARKER(update_precomp.py): autogen include statement, do not remove 25 #include "precompiled_sfx2.hxx" 26 #include <tools/debug.hxx> 27 #ifndef GCC 28 #endif 29 30 #include "bitset.hxx" 31 32 #include <string.h> // memset(), memcpy() 33 #include <limits.h> // USHRT_MAX 34 35 //==================================================================== 36 // add nOffset to each bit-value in the set 37 38 BitSet BitSet::operator<<( sal_uInt16 nOffset ) const 39 { 40 DBG_MEMTEST(); 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 DBG_MEMTEST(); 92 return BitSet(); 93 } 94 95 //-------------------------------------------------------------------- 96 97 // internal code for operator= and copy-ctor 98 99 void BitSet::CopyFrom( const BitSet& rSet ) 100 { 101 DBG_MEMTEST(); 102 nCount = rSet.nCount; 103 nBlocks = rSet.nBlocks; 104 if ( rSet.nBlocks ) 105 { 106 DBG_MEMTEST(); 107 pBitmap = new sal_uIntPtr[nBlocks]; 108 memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks ); 109 } 110 else 111 pBitmap = 0; 112 } 113 114 //-------------------------------------------------------------------- 115 116 // creates an empty bitset 117 118 BitSet::BitSet() 119 { 120 DBG_MEMTEST(); 121 nCount = 0; 122 nBlocks = 0; 123 pBitmap = 0; 124 } 125 126 //-------------------------------------------------------------------- 127 128 // creates a copy of bitset rOrig 129 130 BitSet::BitSet( const BitSet& rOrig ) 131 { 132 DBG_MEMTEST(); 133 CopyFrom(rOrig); 134 } 135 136 //-------------------------------------------------------------------- 137 138 // creates a bitset from an array 139 140 BitSet::BitSet( sal_uInt16* pArray, sal_uInt16 nSize ): 141 nCount(nSize) 142 { 143 DBG_MEMTEST(); 144 // find the highest bit to set 145 sal_uInt16 nMax = 0; 146 for ( sal_uInt16 n = 0; n < nCount; ++n ) 147 if ( pArray[n] > nMax ) 148 nMax = pArray[n]; 149 150 // if there are bits at all 151 if ( nMax > 0 ) 152 { 153 // allocate memory for all blocks needed 154 nBlocks = nMax / 32 + 1; 155 pBitmap = new sal_uIntPtr[nBlocks]; 156 memset( pBitmap, 0, 4 * nBlocks ); 157 158 // set all the bits 159 for ( sal_uInt16 n = 0; n < nCount; ++n ) 160 { 161 // compute the block no. and bitvalue 162 sal_uInt16 nBlock = n / 32; 163 sal_uIntPtr nBitVal = 1L << (n % 32); 164 165 // set a single bit 166 if ( ( *(pBitmap+nBlock) & nBitVal ) == 0 ) 167 { 168 *(pBitmap+nBlock) |= nBitVal; 169 ++nCount; 170 } 171 } 172 } 173 else 174 { 175 // initalize emtpy set 176 nBlocks = 0; 177 pBitmap = 0; 178 } 179 } 180 181 //-------------------------------------------------------------------- 182 183 // frees the storage 184 185 BitSet::~BitSet() 186 { 187 DBG_MEMTEST(); 188 delete [] pBitmap; 189 } 190 191 //-------------------------------------------------------------------- 192 193 // creates a bitmap with all bits in rRange set 194 195 BitSet::BitSet( const Range& ) 196 { 197 DBG_MEMTEST(); 198 } 199 200 //-------------------------------------------------------------------- 201 202 // assignment from another bitset 203 204 BitSet& BitSet::operator=( const BitSet& rOrig ) 205 { 206 DBG_MEMTEST(); 207 if ( this != &rOrig ) 208 { 209 delete [] pBitmap; 210 CopyFrom(rOrig); 211 } 212 return *this; 213 } 214 215 //-------------------------------------------------------------------- 216 217 // assignment from a single bit 218 219 BitSet& BitSet::operator=( sal_uInt16 nBit ) 220 { 221 DBG_MEMTEST(); 222 delete [] pBitmap; 223 224 nBlocks = nBit / 32; 225 sal_uIntPtr nBitVal = 1L << (nBit % 32); 226 nCount = 1; 227 228 pBitmap = new sal_uIntPtr[nBlocks]; 229 memset( pBitmap + nBlocks, 0, 4 * nBlocks ); 230 231 *(pBitmap+nBlocks) = nBitVal; 232 233 return *this; 234 } 235 236 //-------------------------------------------------------------------- 237 238 // creates the asymetric difference with another bitset 239 240 BitSet& BitSet::operator-=(sal_uInt16 nBit) 241 { 242 DBG_MEMTEST(); 243 sal_uInt16 nBlock = nBit / 32; 244 sal_uIntPtr nBitVal = 1L << (nBit % 32); 245 246 if ( nBlock >= nBlocks ) 247 return *this; 248 249 if ( (*(pBitmap+nBlock) & nBitVal) ) 250 { 251 *(pBitmap+nBlock) &= ~nBitVal; 252 --nCount; 253 } 254 255 return *this; 256 } 257 258 //-------------------------------------------------------------------- 259 260 // unites with the bits of rSet 261 262 BitSet& BitSet::operator|=( const BitSet& rSet ) 263 { 264 DBG_MEMTEST(); 265 sal_uInt16 nMax = Min(nBlocks, rSet.nBlocks); 266 267 // expand the bitmap 268 if ( nBlocks < rSet.nBlocks ) 269 { 270 sal_uIntPtr *pNewMap = new sal_uIntPtr[rSet.nBlocks]; 271 memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) ); 272 273 if ( pBitmap ) 274 { 275 memcpy( pNewMap, pBitmap, 4 * nBlocks ); 276 delete [] pBitmap; 277 } 278 pBitmap = pNewMap; 279 nBlocks = rSet.nBlocks; 280 } 281 282 // add the bits blocks by block 283 for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock ) 284 { 285 // compute numberof additional bits 286 sal_uIntPtr nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock); 287 nCount = nCount + CountBits(nDiff); 288 289 *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock); 290 } 291 292 return *this; 293 } 294 295 //-------------------------------------------------------------------- 296 297 // unites with a single bit 298 299 BitSet& BitSet::operator|=( sal_uInt16 nBit ) 300 { 301 DBG_MEMTEST(); 302 sal_uInt16 nBlock = nBit / 32; 303 sal_uIntPtr nBitVal = 1L << (nBit % 32); 304 305 if ( nBlock >= nBlocks ) 306 { 307 sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1]; 308 memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) ); 309 310 if ( pBitmap ) 311 { 312 memcpy( pNewMap, pBitmap, 4 * nBlocks ); 313 delete [] pBitmap; 314 } 315 pBitmap = pNewMap; 316 nBlocks = nBlock+1; 317 } 318 319 if ( (*(pBitmap+nBlock) & nBitVal) == 0 ) 320 { 321 *(pBitmap+nBlock) |= nBitVal; 322 ++nCount; 323 } 324 325 return *this; 326 } 327 328 //-------------------------------------------------------------------- 329 330 // determines if the bit is set (may be the only one) 331 332 sal_Bool BitSet::Contains( sal_uInt16 nBit ) const 333 { 334 DBG_MEMTEST(); 335 sal_uInt16 nBlock = nBit / 32; 336 sal_uIntPtr nBitVal = 1L << (nBit % 32); 337 338 if ( nBlock >= nBlocks ) 339 return sal_False; 340 return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal; 341 } 342 343 //-------------------------------------------------------------------- 344 345 // determines if the bitsets are equal 346 347 sal_Bool BitSet::operator==( const BitSet& rSet ) const 348 { 349 DBG_MEMTEST(); 350 if ( nBlocks != rSet.nBlocks ) 351 return sal_False; 352 353 sal_uInt16 nBlock = nBlocks; 354 while ( nBlock-- > 0 ) 355 if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) ) 356 return sal_False; 357 358 return sal_True; 359 } 360 361 //-------------------------------------------------------------------- 362 363 // counts the number of 1-bits in the parameter 364 365 sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits ) 366 { 367 sal_uInt16 nCount = 0; 368 int nBit = 32; 369 while ( nBit-- && nBits ) 370 { if ( ( (long)nBits ) < 0 ) 371 ++nCount; 372 nBits = nBits << 1; 373 } 374 return nCount; 375 } 376 377 //-------------------------------------------------------------------- 378 379 sal_uInt16 IndexBitSet::GetFreeIndex() 380 { 381 for(sal_uInt16 i=0;i<USHRT_MAX;i++) 382 if(!Contains(i)) 383 { 384 *this|=i; 385 return i; 386 } 387 DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege"); 388 return 0; 389 } 390 391 392