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
operator <<(sal_uInt16 nOffset) const38 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 // subtracts nOffset from each bit-value in the set
88
operator >>(sal_uInt16) const89 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
CopyFrom(const BitSet & rSet)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
BitSet()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
BitSet(const BitSet & rOrig)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
BitSet(sal_uInt16 * pArray,sal_uInt16 nSize)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 // initialize emtpy set
176 nBlocks = 0;
177 pBitmap = 0;
178 }
179 }
180
181 //--------------------------------------------------------------------
182
183 // frees the storage
184
~BitSet()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
BitSet(const Range &)195 BitSet::BitSet( const Range& )
196 {
197 DBG_MEMTEST();
198 }
199
200 //--------------------------------------------------------------------
201
202 // assignment from another bitset
203
operator =(const BitSet & rOrig)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
operator =(sal_uInt16 nBit)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
operator -=(sal_uInt16 nBit)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
operator |=(const BitSet & rSet)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
operator |=(sal_uInt16 nBit)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
Contains(sal_uInt16 nBit) const332 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
operator ==(const BitSet & rSet) const347 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
CountBits(sal_uIntPtr nBits)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
GetFreeIndex()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