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