xref: /aoo42x/main/sfx2/source/bastyp/bitset.cxx (revision 30acf5e8)
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