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