Line data Source code
1 : /* src/toolbox/bitvector.c - bitvector implementation
2 :
3 : Copyright (C) 2005-2013
4 : CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
5 : Copyright (C) 2008 Theobroma Systems Ltd.
6 :
7 : This file is part of CACAO.
8 :
9 : This program is free software; you can redistribute it and/or
10 : modify it under the terms of the GNU General Public License as
11 : published by the Free Software Foundation; either version 2, or (at
12 : your option) any later version.
13 :
14 : This program is distributed in the hope that it will be useful, but
15 : WITHOUT ANY WARRANTY; without even the implied warranty of
16 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : General Public License for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with this program; if not, write to the Free Software
21 : Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
22 : 02111-1307, USA.
23 :
24 : */
25 :
26 :
27 :
28 : #include "toolbox/bitvector.hpp"
29 : #include <assert.h>
30 : #include "config.h"
31 : #include "mm/dumpmemory.hpp"
32 :
33 : #if !defined(NDEBUG)
34 :
35 : /// define BV_DEBUG_CHECK to activate the bound checks
36 : // #define BV_DEBUG_CHECK
37 :
38 : #endif
39 :
40 : #if defined(BV_DEBUG_CHECK)
41 : #define _BV_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
42 : #define _BV_ASSERT(a) assert((a));
43 : #else
44 : #define _BV_CHECK_BOUNDS(i,l,h);
45 : #define _BV_ASSERT(a);
46 : #endif
47 :
48 : /******************************************************************************
49 :
50 : Bitvector Implementation
51 :
52 : ******************************************************************************/
53 :
54 : #ifdef BV_DEBUG_CHECK
55 :
56 : /* Number of ints needed for size bits */
57 :
58 : # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1)\
59 : / sizeof(int) + 1)
60 :
61 : /* Get index in bitvector */
62 :
63 : # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) + 1)
64 :
65 : /* Get bit index inside int */
66 :
67 : # define BV_BIT_INDEX(bit, index) ( (bit) - (index - 1) * sizeof(int) * 8 );
68 :
69 : #else
70 :
71 : /* Number of ints needed for size bits */
72 :
73 : # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1) / sizeof(int))
74 :
75 : /* Get index in bitvector */
76 :
77 : # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) )
78 :
79 : /* Get bit index inside int */
80 :
81 : # define BV_BIT_INDEX(bit, index) ( (bit) - (index) * sizeof(int) * 8 );
82 :
83 : #endif
84 :
85 : /************************************************************************
86 : bv_to_string
87 :
88 : Transforms the bitvector bv to a string of 1's and 0's.
89 :
90 : IN: bitvector bv bitvector created with bv_new()
91 : int size size of bitvector bv
92 :
93 : IN/OUT: char *string allocated buffer, at least size + 1 elements
94 :
95 : RETURN:pointer to string
96 : ******************************************************************************/
97 0 : char *bv_to_string(bitvector bv, char *string, int size) {
98 : int i;
99 :
100 : _BV_ASSERT(bv[0] == size);
101 :
102 0 : for(i = 0; i < size; i++)
103 0 : if (bv_get_bit(bv, i))
104 0 : string[i]='1';
105 : else
106 0 : string[i]='0';
107 :
108 0 : string[i]=0;
109 0 : return string;
110 : }
111 :
112 : /******************************************************************************
113 : bv_new
114 :
115 : Creates a new bitvector and initializes all bits to 0.
116 :
117 : IN: int size size of bitvector bv
118 :
119 : RETURN: bitvector
120 :
121 : *******************************************************************************/
122 0 : bitvector bv_new(int size) {
123 : /* Number of ints needed for size bits */
124 : /* n = (((size+7)/8) + sizeof(int) - 1)/sizeof(int); */
125 0 : int n = BV_NUM_INTS(size);
126 :
127 0 : int *bv = (int*) DumpMemory::allocate(sizeof(int) * n);
128 :
129 0 : for(int i = 0; i < n; i++) bv[i] = 0;
130 :
131 : #ifdef BV_DEBUG_CHECK
132 : bv[0] = size;
133 : #endif
134 :
135 0 : return bv;
136 : }
137 :
138 : /******************************************************************************
139 : bv_get_bit
140 :
141 : Checks if a specific bit of the bitvector is set.
142 :
143 : IN: bitvector bv
144 : int bit Index of bit to check (0..size(
145 :
146 : RETURN: bool true if bit is set otherwise false
147 : *******************************************************************************/
148 0 : bool bv_get_bit(bitvector bv, int bit) {
149 : _BV_ASSERT(bit >= 0);
150 :
151 0 : int i = BV_INT_INDEX(bit);
152 0 : int n = BV_BIT_INDEX(bit, i);
153 :
154 : _BV_ASSERT(i < (BV_NUM_INTS(bv[0])));
155 0 : return (bv[i] & (1<<n));
156 : }
157 :
158 : /******************************************************************************
159 : bv_set_bit
160 :
161 : Sets a specific bit of the bitvector
162 :
163 : IN: bitvector bv
164 : int bit Index of bit to set (0..size(
165 : *******************************************************************************/
166 0 : void bv_set_bit(bitvector bv, int bit) {
167 : _BV_ASSERT(bit >= 0);
168 :
169 0 : int i = BV_INT_INDEX(bit);
170 0 : int n = BV_BIT_INDEX(bit, i);
171 :
172 : _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
173 :
174 0 : bv[i] |= 1<<n;
175 0 : }
176 :
177 : /******************************************************************************
178 : bv_reset_bit
179 :
180 : Resets a specific bit of the bitvector
181 :
182 : IN: bitvector bv
183 : int bit Index of bit to reset (0..size(
184 : *******************************************************************************/
185 0 : void bv_reset_bit(bitvector bv, int bit) {
186 : _BV_ASSERT(bit >= 0);
187 :
188 0 : int i = BV_INT_INDEX(bit);
189 0 : int n = BV_BIT_INDEX(bit, i);
190 :
191 : _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
192 :
193 0 : bv[i] &= ~(1<<n);
194 0 : }
195 :
196 : /******************************************************************************
197 : bv_reset
198 :
199 : Resets all bits of the bitvector
200 :
201 : IN: bitvector bv
202 : int size Size of the bitvector
203 : *******************************************************************************/
204 0 : void bv_reset(bitvector bv, int size) {
205 : _BV_ASSERT(bv[0] == size);
206 :
207 0 : int n = BV_NUM_INTS(size);
208 :
209 : #ifdef BV_DEBUG_CHECK
210 : for(int i = 1; i < n; i++)
211 : #else
212 0 : for(int i = 0; i < n; i++)
213 : #endif
214 0 : bv[i] = 0;
215 0 : }
216 :
217 : /******************************************************************************
218 : bv_is_empty
219 :
220 : Checks if no bits of the bitvector are set == bitvector is "empty"
221 :
222 : IN: bitvector bv
223 : int size Size of the bitvector
224 :
225 : RETURN: bool return true if bv is empty, false otherwise
226 : *******************************************************************************/
227 0 : bool bv_is_empty(bitvector bv, int size) {
228 : _BV_ASSERT(bv[0] == size);
229 :
230 0 : int n = BV_NUM_INTS(size);
231 :
232 0 : bool empty = true;
233 : #ifdef BV_DEBUG_CHECK
234 : for(int i = 1; (i < n) && empty; i++)
235 : #else
236 0 : for(int i = 0; (i < n) && empty; i++)
237 : #endif
238 0 : empty = empty && (bv[i] == 0);
239 0 : return empty;
240 : }
241 :
242 : /******************************************************************************
243 : bv_copy
244 :
245 : Copyes bitvector src to dst
246 :
247 : IN: bitvector dst bitvector created with bv_new
248 : bitvector src bitvector created with bv_new
249 : int size Size of the bitvector
250 : *******************************************************************************/
251 0 : void bv_copy(bitvector dst, bitvector src, int size) {
252 : int i,n;
253 : /* copy the whole bitvector */
254 : _BV_ASSERT(dst[0] == size);
255 : _BV_ASSERT(src[0] == size);
256 0 : n = BV_NUM_INTS(size);
257 :
258 : #ifdef BV_DEBUG_CHECK
259 : for(i = 1; i < n; i++)
260 : #else
261 0 : for(i = 0; i < n; i++)
262 : #endif
263 0 : dst[i] = src[i];
264 0 : }
265 :
266 : /******************************************************************************
267 : bv_equal
268 :
269 : Compares two bitvectors
270 :
271 : IN: bitvector s1 bitvector created with bv_new
272 : bitvector s2 bitvector created with bv_new
273 : int size Size of the bitvector
274 :
275 : RETURN: bool true if s1==s1, false otherwise
276 : *******************************************************************************/
277 0 : bool bv_equal(bitvector s1, bitvector s2, int size) {
278 0 : bool equal = true;
279 :
280 : /* copy the whole bitvector */
281 : _BV_ASSERT(s1[0] == size);
282 : _BV_ASSERT(s2[0] == size);
283 :
284 0 : if (size == 0)
285 0 : return true;
286 :
287 0 : int n = BV_NUM_INTS(size);
288 :
289 : #ifdef BV_DEBUG_CHECK
290 : for(int i = 1; equal && (i < n-1); i++)
291 : #else
292 0 : for(int i = 0; equal && (i < n-1); i++)
293 : #endif
294 0 : equal = (s1[i] == s2[i]);
295 :
296 : /* Last compare maybe has to be masked! */
297 :
298 0 : int i = BV_INT_INDEX(size - 1);
299 0 : n = BV_BIT_INDEX(size - 1, i);
300 :
301 : _BV_ASSERT(i < BV_NUM_INTS(s1[0]));
302 : _BV_ASSERT(i < BV_NUM_INTS(s2[0]));
303 :
304 : int mask;
305 :
306 0 : if (n == (sizeof(int) * 8 - 1)) {
307 : /* full mask */
308 0 : mask = -1;
309 : } else {
310 0 : mask = (1<<(n+1)) - 1;
311 : }
312 :
313 0 : equal = equal && ( (s1[i]&mask) == (s2[i]&mask));
314 :
315 0 : return equal;
316 : }
317 :
318 : /******************************************************************************
319 : bv_minus
320 :
321 : d = s1 \ s2. ( set minus operator )
322 :
323 : IN: bitvector s1 bitvector created with bv_new
324 : bitvector s2 bitvector created with bv_new
325 : int size Size of the bitvector
326 :
327 : IN/OUT:bitvector d bitvector created with bv_new
328 :
329 : *******************************************************************************/
330 0 : void bv_minus(bitvector d, bitvector s1, bitvector s2, int size) {
331 : /* d = s1 - s2 */
332 : _BV_ASSERT(d[0] == size);
333 : _BV_ASSERT(s1[0] == size);
334 : _BV_ASSERT(s2[0] == size);
335 0 : int n = BV_NUM_INTS(size);
336 : #ifdef BV_DEBUG_CHECK
337 : for(int i = 1; i < n; i++)
338 : #else
339 0 : for(int i = 0; i < n; i++)
340 : #endif
341 0 : d[i] = s1[i] & (~s2[i]);
342 0 : }
343 :
344 : /******************************************************************************
345 : bv_minus
346 :
347 : d = s1 "union" s2. ( set union operator )
348 :
349 : IN: bitvector s1 bitvector created with bv_new
350 : bitvector s2 bitvector created with bv_new
351 : int size Size of the bitvector
352 :
353 : IN/OUT:bitvector d bitvector created with bv_new
354 :
355 : *******************************************************************************/
356 0 : void bv_union(bitvector d, bitvector s1, bitvector s2, int size) {
357 : /* d = s1 union s2 */
358 : _BV_ASSERT(d[0] == size);
359 : _BV_ASSERT(s1[0] == size);
360 : _BV_ASSERT(s2[0] == size);
361 0 : int n = BV_NUM_INTS(size);
362 : #ifdef BV_DEBUG_CHECK
363 : for(int i = 1; i < n; i++)
364 : #else
365 0 : for(int i = 0; i < n; i++)
366 : #endif
367 0 : d[i] = s1[i] | s2[i];
368 0 : }
369 :
370 : /*
371 : * These are local overrides for various environment variables in Emacs.
372 : * Please do not remove this and leave it at the end of the file, where
373 : * Emacs will automagically detect them.
374 : * ---------------------------------------------------------------------
375 : * Local variables:
376 : * mode: c++
377 : * indent-tabs-mode: t
378 : * c-basic-offset: 4
379 : * tab-width: 4
380 : * End:
381 : */
|
