Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*
3 : : * This file is part of the LibreOffice project.
4 : : *
5 : : * This Source Code Form is subject to the terms of the Mozilla Public
6 : : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : : *
9 : : * This file incorporates work covered by the following license notice:
10 : : *
11 : : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : : * contributor license agreements. See the NOTICE file distributed
13 : : * with this work for additional information regarding copyright
14 : : * ownership. The ASF licenses this file to you under the Apache
15 : : * License, Version 2.0 (the "License"); you may not use this file
16 : : * except in compliance with the License. You may obtain a copy of
17 : : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : : */
19 : :
20 : : #include <tools/debug.hxx>
21 : :
22 : : #include "bitset.hxx"
23 : :
24 : : #include <string.h> // memset(), memcpy()
25 : : #include <limits.h> // USHRT_MAX
26 : :
27 : : //====================================================================
28 : : // add nOffset to each bit-value in the set
29 : :
30 : 0 : BitSet BitSet::operator<<( sal_uInt16 nOffset ) const
31 : : {
32 : : // create a work-copy, return it if nothing to shift
33 : 0 : BitSet aSet(*this);
34 [ # # ]: 0 : if ( nOffset == 0 )
35 : 0 : return aSet;
36 : :
37 : : // compute the shiftment in long-words and bits
38 : 0 : sal_uInt16 nBlockDiff = nOffset / 32;
39 : 0 : sal_uIntPtr nBitValDiff = nOffset % 32;
40 : :
41 : : // compute the new number of bits
42 [ # # ]: 0 : for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock )
43 : 0 : aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
44 : : aSet.nCount = aSet.nCount -
45 : 0 : CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );
46 : :
47 : : // shift complete long-words
48 : : sal_uInt16 nTarget, nSource;
49 [ # # ]: 0 : for ( nTarget = 0, nSource = nBlockDiff;
50 : : (nSource+1) < aSet.nBlocks;
51 : : ++nTarget, ++nSource )
52 : 0 : *(aSet.pBitmap+nTarget) =
53 : 0 : ( *(aSet.pBitmap+nSource) << nBitValDiff ) |
54 : 0 : ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );
55 : :
56 : : // shift the remainder (if in total minor 32 bits, only this)
57 : 0 : *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;
58 : :
59 : : // determine the last used block
60 [ # # ]: 0 : while ( *(aSet.pBitmap+nTarget) == 0 )
61 : 0 : --nTarget;
62 : :
63 : : // shorten the block-array
64 [ # # ]: 0 : if ( nTarget < aSet.nBlocks )
65 : : {
66 [ # # ]: 0 : sal_uIntPtr* pNewMap = new sal_uIntPtr[nTarget];
67 : 0 : memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
68 [ # # ]: 0 : delete [] aSet.pBitmap;
69 : 0 : aSet.pBitmap = pNewMap;
70 : 0 : aSet.nBlocks = nTarget;
71 : : }
72 : :
73 : 0 : return aSet;
74 : : }
75 : :
76 : : //--------------------------------------------------------------------
77 : :
78 : : // substracts nOffset from each bit-value in the set
79 : :
80 : 0 : BitSet BitSet::operator>>( sal_uInt16 ) const
81 : : {
82 : 0 : return BitSet();
83 : : }
84 : :
85 : : //--------------------------------------------------------------------
86 : :
87 : : // internal code for operator= and copy-ctor
88 : :
89 : 0 : void BitSet::CopyFrom( const BitSet& rSet )
90 : : {
91 : 0 : nCount = rSet.nCount;
92 : 0 : nBlocks = rSet.nBlocks;
93 [ # # ]: 0 : if ( rSet.nBlocks )
94 : : {
95 : 0 : pBitmap = new sal_uIntPtr[nBlocks];
96 : 0 : memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
97 : : }
98 : : else
99 : 0 : pBitmap = 0;
100 : 0 : }
101 : :
102 : : //--------------------------------------------------------------------
103 : :
104 : : // creates an empty bitset
105 : :
106 : 4112 : BitSet::BitSet()
107 : : {
108 : 4112 : nCount = 0;
109 : 4112 : nBlocks = 0;
110 : 4112 : pBitmap = 0;
111 : 4112 : }
112 : :
113 : : //--------------------------------------------------------------------
114 : :
115 : : // creates a copy of bitset rOrig
116 : :
117 : 0 : BitSet::BitSet( const BitSet& rOrig )
118 : : {
119 : 0 : CopyFrom(rOrig);
120 : 0 : }
121 : :
122 : : //--------------------------------------------------------------------
123 : :
124 : : // frees the storage
125 : :
126 : 3470 : BitSet::~BitSet()
127 : : {
128 [ + + ]: 3470 : delete [] pBitmap;
129 : 3470 : }
130 : :
131 : : //--------------------------------------------------------------------
132 : :
133 : : // assignment from another bitset
134 : :
135 : 0 : BitSet& BitSet::operator=( const BitSet& rOrig )
136 : : {
137 [ # # ]: 0 : if ( this != &rOrig )
138 : : {
139 [ # # ]: 0 : delete [] pBitmap;
140 : 0 : CopyFrom(rOrig);
141 : : }
142 : 0 : return *this;
143 : : }
144 : :
145 : : //--------------------------------------------------------------------
146 : :
147 : : // assignment from a single bit
148 : :
149 : 0 : BitSet& BitSet::operator=( sal_uInt16 nBit )
150 : : {
151 [ # # ]: 0 : delete [] pBitmap;
152 : :
153 : 0 : nBlocks = nBit / 32;
154 : 0 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
155 : 0 : nCount = 1;
156 : :
157 : 0 : pBitmap = new sal_uIntPtr[nBlocks + 1];
158 : 0 : memset( pBitmap, 0, 4 * (nBlocks + 1) );
159 : :
160 : 0 : *(pBitmap+nBlocks) = nBitVal;
161 : :
162 : 0 : return *this;
163 : : }
164 : :
165 : : //--------------------------------------------------------------------
166 : :
167 : : // creates the asymetric difference with another bitset
168 : :
169 : 2936 : BitSet& BitSet::operator-=(sal_uInt16 nBit)
170 : : {
171 : 2936 : sal_uInt16 nBlock = nBit / 32;
172 : 2936 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
173 : :
174 [ - + ]: 2936 : if ( nBlock >= nBlocks )
175 : 0 : return *this;
176 : :
177 [ + - ]: 2936 : if ( (*(pBitmap+nBlock) & nBitVal) )
178 : : {
179 : 2936 : *(pBitmap+nBlock) &= ~nBitVal;
180 : 2936 : --nCount;
181 : : }
182 : :
183 : 2936 : return *this;
184 : : }
185 : :
186 : : //--------------------------------------------------------------------
187 : :
188 : : // unites with the bits of rSet
189 : :
190 : 0 : BitSet& BitSet::operator|=( const BitSet& rSet )
191 : : {
192 : 0 : sal_uInt16 nMax = Min(nBlocks, rSet.nBlocks);
193 : :
194 : : // expand the bitmap
195 [ # # ]: 0 : if ( nBlocks < rSet.nBlocks )
196 : : {
197 : 0 : sal_uIntPtr *pNewMap = new sal_uIntPtr[rSet.nBlocks];
198 : 0 : memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );
199 : :
200 [ # # ]: 0 : if ( pBitmap )
201 : : {
202 : 0 : memcpy( pNewMap, pBitmap, 4 * nBlocks );
203 [ # # ]: 0 : delete [] pBitmap;
204 : : }
205 : 0 : pBitmap = pNewMap;
206 : 0 : nBlocks = rSet.nBlocks;
207 : : }
208 : :
209 : : // add the bits blocks by block
210 [ # # ]: 0 : for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock )
211 : : {
212 : : // compute numberof additional bits
213 : 0 : sal_uIntPtr nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
214 : 0 : nCount = nCount + CountBits(nDiff);
215 : :
216 : 0 : *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
217 : : }
218 : :
219 : 0 : return *this;
220 : : }
221 : :
222 : : //--------------------------------------------------------------------
223 : :
224 : : // unites with a single bit
225 : :
226 : 3085 : BitSet& BitSet::operator|=( sal_uInt16 nBit )
227 : : {
228 : 3085 : sal_uInt16 nBlock = nBit / 32;
229 : 3085 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
230 : :
231 [ + + ]: 3085 : if ( nBlock >= nBlocks )
232 : : {
233 : 2052 : sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1];
234 : 2052 : memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
235 : :
236 [ - + ]: 2052 : if ( pBitmap )
237 : : {
238 : 0 : memcpy( pNewMap, pBitmap, 4 * nBlocks );
239 [ # # ]: 0 : delete [] pBitmap;
240 : : }
241 : 2052 : pBitmap = pNewMap;
242 : 2052 : nBlocks = nBlock+1;
243 : : }
244 : :
245 [ + - ]: 3085 : if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
246 : : {
247 : 3085 : *(pBitmap+nBlock) |= nBitVal;
248 : 3085 : ++nCount;
249 : : }
250 : :
251 : 3085 : return *this;
252 : : }
253 : :
254 : : //--------------------------------------------------------------------
255 : :
256 : : // determines if the bit is set (may be the only one)
257 : :
258 : 3101 : sal_Bool BitSet::Contains( sal_uInt16 nBit ) const
259 : : {
260 : 3101 : sal_uInt16 nBlock = nBit / 32;
261 : 3101 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
262 : :
263 [ + + ]: 3101 : if ( nBlock >= nBlocks )
264 : 2052 : return sal_False;
265 : 3101 : return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
266 : : }
267 : :
268 : : //--------------------------------------------------------------------
269 : :
270 : : // determines if the bitsets are equal
271 : :
272 : 0 : sal_Bool BitSet::operator==( const BitSet& rSet ) const
273 : : {
274 [ # # ]: 0 : if ( nBlocks != rSet.nBlocks )
275 : 0 : return sal_False;
276 : :
277 : 0 : sal_uInt16 nBlock = nBlocks;
278 [ # # ]: 0 : while ( nBlock-- > 0 )
279 [ # # ]: 0 : if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
280 : 0 : return sal_False;
281 : :
282 : 0 : return sal_True;
283 : : }
284 : :
285 : : //--------------------------------------------------------------------
286 : :
287 : : // counts the number of 1-bits in the parameter
288 : :
289 : 0 : sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits )
290 : : {
291 : 0 : sal_uInt16 nCount = 0;
292 : 0 : int nBit = 32;
293 [ # # ][ # # ]: 0 : while ( nBit-- && nBits )
[ # # ]
294 [ # # ]: 0 : { if ( ( (long)nBits ) < 0 )
295 : 0 : ++nCount;
296 : 0 : nBits = nBits << 1;
297 : : }
298 : 0 : return nCount;
299 : : }
300 : :
301 : : //--------------------------------------------------------------------
302 : :
303 : 3085 : sal_uInt16 IndexBitSet::GetFreeIndex()
304 : : {
305 [ + - ]: 3101 : for(sal_uInt16 i=0;i<USHRT_MAX;i++)
306 [ + + ]: 3101 : if(!Contains(i))
307 : : {
308 : 3085 : *this|=i;
309 : 3085 : return i;
310 : : }
311 : : DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
312 : 3085 : return 0;
313 : : }
314 : :
315 : :
316 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
