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>
25 : #include <limits.h>
26 : #include <algorithm>
27 :
28 :
29 : // add nOffset to each bit-value in the set
30 :
31 0 : BitSet BitSet::operator<<( sal_uInt16 nOffset ) const
32 : {
33 : // create a work-copy, return it if nothing to shift
34 0 : BitSet aSet(*this);
35 0 : if ( nOffset == 0 )
36 0 : return aSet;
37 :
38 : // compute the shiftment in long-words and bits
39 0 : sal_uInt16 nBlockDiff = nOffset / 32;
40 0 : sal_uInt32 nBitValDiff = nOffset % 32;
41 :
42 : // compute the new number of bits
43 0 : for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock )
44 0 : aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
45 : aSet.nCount = aSet.nCount -
46 0 : CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );
47 :
48 : // shift complete long-words
49 : sal_uInt16 nTarget, nSource;
50 0 : for ( nTarget = 0, nSource = nBlockDiff;
51 0 : (nSource+1) < aSet.nBlocks;
52 : ++nTarget, ++nSource )
53 0 : *(aSet.pBitmap+nTarget) =
54 0 : ( *(aSet.pBitmap+nSource) << nBitValDiff ) |
55 0 : ( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );
56 :
57 : // shift the remainder (if in total minor 32 bits, only this)
58 0 : *(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;
59 :
60 : // determine the last used block
61 0 : while ( *(aSet.pBitmap+nTarget) == 0 )
62 0 : --nTarget;
63 :
64 : // shorten the block-array
65 0 : if ( nTarget < aSet.nBlocks )
66 : {
67 0 : sal_uInt32* pNewMap = new sal_uInt32[nTarget];
68 0 : memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
69 0 : delete [] aSet.pBitmap;
70 0 : aSet.pBitmap = pNewMap;
71 0 : aSet.nBlocks = nTarget;
72 : }
73 :
74 0 : return aSet;
75 : }
76 :
77 :
78 :
79 : // subtracts nOffset from each bit-value in the set
80 :
81 0 : BitSet BitSet::operator>>( sal_uInt16 ) const
82 : {
83 0 : return BitSet();
84 : }
85 :
86 :
87 :
88 : // internal code for operator= and copy-ctor
89 :
90 0 : void BitSet::CopyFrom( const BitSet& rSet )
91 : {
92 0 : nCount = rSet.nCount;
93 0 : nBlocks = rSet.nBlocks;
94 0 : if ( rSet.nBlocks )
95 : {
96 0 : pBitmap = new sal_uInt32[nBlocks];
97 0 : memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
98 : }
99 : else
100 0 : pBitmap = 0;
101 0 : }
102 :
103 :
104 :
105 : // creates an empty bitset
106 :
107 5149 : BitSet::BitSet()
108 : {
109 5149 : nCount = 0;
110 5149 : nBlocks = 0;
111 5149 : pBitmap = 0;
112 5149 : }
113 :
114 :
115 :
116 : // creates a copy of bitset rOrig
117 :
118 0 : BitSet::BitSet( const BitSet& rOrig )
119 : {
120 0 : CopyFrom(rOrig);
121 0 : }
122 :
123 :
124 :
125 : // frees the storage
126 :
127 5000 : BitSet::~BitSet()
128 : {
129 5000 : delete [] pBitmap;
130 5000 : }
131 :
132 :
133 :
134 : // assignment from another bitset
135 :
136 0 : BitSet& BitSet::operator=( const BitSet& rOrig )
137 : {
138 0 : if ( this != &rOrig )
139 : {
140 0 : delete [] pBitmap;
141 0 : CopyFrom(rOrig);
142 : }
143 0 : return *this;
144 : }
145 :
146 :
147 :
148 : // assignment from a single bit
149 :
150 0 : BitSet& BitSet::operator=( sal_uInt16 nBit )
151 : {
152 0 : delete [] pBitmap;
153 :
154 0 : nBlocks = nBit / 32;
155 0 : sal_uInt32 nBitVal = 1L << (nBit % 32);
156 0 : nCount = 1;
157 :
158 0 : pBitmap = new sal_uInt32[nBlocks + 1];
159 0 : memset( pBitmap, 0, 4 * (nBlocks + 1) );
160 :
161 0 : *(pBitmap+nBlocks) = nBitVal;
162 :
163 0 : return *this;
164 : }
165 :
166 :
167 :
168 : // creates the asymetric difference with another bitset
169 :
170 3871 : BitSet& BitSet::operator-=(sal_uInt16 nBit)
171 : {
172 3871 : sal_uInt16 nBlock = nBit / 32;
173 3871 : sal_uInt32 nBitVal = 1L << (nBit % 32);
174 :
175 3871 : if ( nBlock >= nBlocks )
176 0 : return *this;
177 :
178 3871 : if ( (*(pBitmap+nBlock) & nBitVal) )
179 : {
180 3871 : *(pBitmap+nBlock) &= ~nBitVal;
181 3871 : --nCount;
182 : }
183 :
184 3871 : return *this;
185 : }
186 :
187 :
188 :
189 : // unites with the bits of rSet
190 :
191 0 : BitSet& BitSet::operator|=( const BitSet& rSet )
192 : {
193 0 : sal_uInt16 nMax = std::min(nBlocks, rSet.nBlocks);
194 :
195 : // expand the bitmap
196 0 : if ( nBlocks < rSet.nBlocks )
197 : {
198 0 : sal_uInt32 *pNewMap = new sal_uInt32[rSet.nBlocks];
199 0 : memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );
200 :
201 0 : if ( pBitmap )
202 : {
203 0 : memcpy( pNewMap, pBitmap, 4 * nBlocks );
204 0 : delete [] pBitmap;
205 : }
206 0 : pBitmap = pNewMap;
207 0 : nBlocks = rSet.nBlocks;
208 : }
209 :
210 : // add the bits blocks by block
211 0 : for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock )
212 : {
213 : // compute numberof additional bits
214 0 : sal_uInt32 nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
215 0 : nCount = nCount + CountBits(nDiff);
216 :
217 0 : *(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
218 : }
219 :
220 0 : return *this;
221 : }
222 :
223 :
224 :
225 : // unites with a single bit
226 :
227 3877 : BitSet& BitSet::operator|=( sal_uInt16 nBit )
228 : {
229 3877 : sal_uInt16 nBlock = nBit / 32;
230 3877 : sal_uInt32 nBitVal = 1L << (nBit % 32);
231 :
232 3877 : if ( nBlock >= nBlocks )
233 : {
234 3204 : sal_uInt32 *pNewMap = new sal_uInt32[nBlock+1];
235 3204 : memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
236 :
237 3204 : if ( pBitmap )
238 : {
239 0 : memcpy( pNewMap, pBitmap, 4 * nBlocks );
240 0 : delete [] pBitmap;
241 : }
242 3204 : pBitmap = pNewMap;
243 3204 : nBlocks = nBlock+1;
244 : }
245 :
246 3877 : if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
247 : {
248 3877 : *(pBitmap+nBlock) |= nBitVal;
249 3877 : ++nCount;
250 : }
251 :
252 3877 : return *this;
253 : }
254 :
255 :
256 :
257 : // determines if the bit is set (may be the only one)
258 :
259 3884 : bool BitSet::Contains( sal_uInt16 nBit ) const
260 : {
261 3884 : sal_uInt16 nBlock = nBit / 32;
262 3884 : sal_uInt32 nBitVal = 1L << (nBit % 32);
263 :
264 3884 : if ( nBlock >= nBlocks )
265 3204 : return false;
266 680 : return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
267 : }
268 :
269 :
270 :
271 : // determines if the bitsets are equal
272 :
273 0 : bool BitSet::operator==( const BitSet& rSet ) const
274 : {
275 0 : if ( nBlocks != rSet.nBlocks )
276 0 : return false;
277 :
278 0 : sal_uInt16 nBlock = nBlocks;
279 0 : while ( nBlock-- > 0 )
280 0 : if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
281 0 : return false;
282 :
283 0 : return true;
284 : }
285 :
286 : // counts the number of 1-bits in the parameter
287 : // Wegner/Kernighan/Ritchie method
288 0 : sal_uInt16 BitSet::CountBits(sal_uInt32 nBits)
289 : {
290 0 : sal_uInt32 nCount = 0;
291 0 : while (nBits)
292 : {
293 0 : nBits &= nBits - 1; // clear the least significant bit set
294 0 : ++nCount;
295 : }
296 0 : return nCount;
297 : }
298 :
299 3877 : sal_uInt16 IndexBitSet::GetFreeIndex()
300 : {
301 3884 : for(int i=0;i<USHRT_MAX;i++)
302 3884 : if(!Contains(i))
303 : {
304 3877 : *this|=i;
305 3877 : return i;
306 : }
307 : DBG_ASSERT(false, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
308 0 : return 0;
309 : }
310 :
311 :
312 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
