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 : #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_uIntPtr 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_uIntPtr* pNewMap = new sal_uIntPtr[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 : // substracts 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_uIntPtr[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 1903 : BitSet::BitSet()
108 : {
109 1903 : nCount = 0;
110 1903 : nBlocks = 0;
111 1903 : pBitmap = 0;
112 1903 : }
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 1689 : BitSet::~BitSet()
128 : {
129 1689 : delete [] pBitmap;
130 1689 : }
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_uIntPtr nBitVal = 1L << (nBit % 32);
156 0 : nCount = 1;
157 :
158 0 : pBitmap = new sal_uIntPtr[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 1672 : BitSet& BitSet::operator-=(sal_uInt16 nBit)
171 : {
172 1672 : sal_uInt16 nBlock = nBit / 32;
173 1672 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
174 :
175 1672 : if ( nBlock >= nBlocks )
176 0 : return *this;
177 :
178 1672 : if ( (*(pBitmap+nBlock) & nBitVal) )
179 : {
180 1672 : *(pBitmap+nBlock) &= ~nBitVal;
181 1672 : --nCount;
182 : }
183 :
184 1672 : 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_uIntPtr *pNewMap = new sal_uIntPtr[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_uIntPtr 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 1674 : BitSet& BitSet::operator|=( sal_uInt16 nBit )
228 : {
229 1674 : sal_uInt16 nBlock = nBit / 32;
230 1674 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
231 :
232 1674 : if ( nBlock >= nBlocks )
233 : {
234 1095 : sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1];
235 1095 : memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
236 :
237 1095 : if ( pBitmap )
238 : {
239 0 : memcpy( pNewMap, pBitmap, 4 * nBlocks );
240 0 : delete [] pBitmap;
241 : }
242 1095 : pBitmap = pNewMap;
243 1095 : nBlocks = nBlock+1;
244 : }
245 :
246 1674 : if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
247 : {
248 1674 : *(pBitmap+nBlock) |= nBitVal;
249 1674 : ++nCount;
250 : }
251 :
252 1674 : return *this;
253 : }
254 :
255 : //--------------------------------------------------------------------
256 :
257 : // determines if the bit is set (may be the only one)
258 :
259 1684 : sal_Bool BitSet::Contains( sal_uInt16 nBit ) const
260 : {
261 1684 : sal_uInt16 nBlock = nBit / 32;
262 1684 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
263 :
264 1684 : if ( nBlock >= nBlocks )
265 1095 : return sal_False;
266 589 : return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
267 : }
268 :
269 : //--------------------------------------------------------------------
270 :
271 : // determines if the bitsets are equal
272 :
273 0 : sal_Bool BitSet::operator==( const BitSet& rSet ) const
274 : {
275 0 : if ( nBlocks != rSet.nBlocks )
276 0 : return sal_False;
277 :
278 0 : sal_uInt16 nBlock = nBlocks;
279 0 : while ( nBlock-- > 0 )
280 0 : if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
281 0 : return sal_False;
282 :
283 0 : return sal_True;
284 : }
285 :
286 : //--------------------------------------------------------------------
287 :
288 : // counts the number of 1-bits in the parameter
289 :
290 0 : sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits )
291 : {
292 0 : sal_uInt16 nCount = 0;
293 0 : int nBit = 32;
294 0 : while ( nBit-- && nBits )
295 0 : { if ( ( (long)nBits ) < 0 )
296 0 : ++nCount;
297 0 : nBits = nBits << 1;
298 : }
299 0 : return nCount;
300 : }
301 :
302 : //--------------------------------------------------------------------
303 :
304 1674 : sal_uInt16 IndexBitSet::GetFreeIndex()
305 : {
306 1684 : for(sal_uInt16 i=0;i<USHRT_MAX;i++)
307 1684 : if(!Contains(i))
308 : {
309 1674 : *this|=i;
310 1674 : return i;
311 : }
312 : DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
313 0 : return 0;
314 : }
315 :
316 :
317 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
