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 668 : BitSet::BitSet()
107 : {
108 668 : nCount = 0;
109 668 : nBlocks = 0;
110 668 : pBitmap = 0;
111 668 : }
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 322 : BitSet::~BitSet()
127 : {
128 322 : delete [] pBitmap;
129 322 : }
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 63 : BitSet& BitSet::operator-=(sal_uInt16 nBit)
170 : {
171 63 : sal_uInt16 nBlock = nBit / 32;
172 63 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
173 :
174 63 : if ( nBlock >= nBlocks )
175 0 : return *this;
176 :
177 63 : if ( (*(pBitmap+nBlock) & nBitVal) )
178 : {
179 63 : *(pBitmap+nBlock) &= ~nBitVal;
180 63 : --nCount;
181 : }
182 :
183 63 : 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 237 : BitSet& BitSet::operator|=( sal_uInt16 nBit )
227 : {
228 237 : sal_uInt16 nBlock = nBit / 32;
229 237 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
230 :
231 237 : if ( nBlock >= nBlocks )
232 : {
233 237 : sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1];
234 237 : memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );
235 :
236 237 : if ( pBitmap )
237 : {
238 0 : memcpy( pNewMap, pBitmap, 4 * nBlocks );
239 0 : delete [] pBitmap;
240 : }
241 237 : pBitmap = pNewMap;
242 237 : nBlocks = nBlock+1;
243 : }
244 :
245 237 : if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
246 : {
247 237 : *(pBitmap+nBlock) |= nBitVal;
248 237 : ++nCount;
249 : }
250 :
251 237 : return *this;
252 : }
253 :
254 : //--------------------------------------------------------------------
255 :
256 : // determines if the bit is set (may be the only one)
257 :
258 237 : sal_Bool BitSet::Contains( sal_uInt16 nBit ) const
259 : {
260 237 : sal_uInt16 nBlock = nBit / 32;
261 237 : sal_uIntPtr nBitVal = 1L << (nBit % 32);
262 :
263 237 : if ( nBlock >= nBlocks )
264 237 : return sal_False;
265 0 : 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 237 : sal_uInt16 IndexBitSet::GetFreeIndex()
304 : {
305 237 : for(sal_uInt16 i=0;i<USHRT_MAX;i++)
306 237 : if(!Contains(i))
307 : {
308 237 : *this|=i;
309 237 : return i;
310 : }
311 : DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
312 0 : return 0;
313 : }
314 :
315 :
316 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
