1 /* src/toolbox/bitvector.c - bitvector implementation
3 Copyright (C) 2005, 2006
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
5 Copyright (C) 2008 Theobroma Systems Ltd.
7 This file is part of CACAO.
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.
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.
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
29 #include "mm/memory.hpp"
30 #include "toolbox/bitvector.h"
33 /******************************************************************************
35 Bitvector Implementation
37 ******************************************************************************/
41 /* Number of ints needed for size bits */
43 # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1)\
46 /* Get index in bitvector */
48 # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) + 1)
50 /* Get bit index inside int */
52 # define BV_BIT_INDEX(bit, index) ( (bit) - (index - 1) * sizeof(int) * 8 );
56 /* Number of ints needed for size bits */
58 # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1) / sizeof(int))
60 /* Get index in bitvector */
62 # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) )
64 /* Get bit index inside int */
66 # define BV_BIT_INDEX(bit, index) ( (bit) - (index) * sizeof(int) * 8 );
70 /************************************************************************
73 Transforms the bitvector bv to a string of 1's and 0's.
75 IN: bitvector bv bitvector created with bv_new()
76 int size size of bitvector bv
78 IN/OUT: char *string allocated buffer, at least size + 1 elements
80 RETURN:pointer to string
81 ******************************************************************************/
82 char *bv_to_string(bitvector bv, char *string, int size) {
85 _BV_ASSERT(bv[0] == size);
87 for(i = 0; i < size; i++)
88 if (bv_get_bit(bv, i))
97 /******************************************************************************
100 Creates a new bitvector and initializes all bits to 0.
102 IN: int size size of bitvector bv
106 *******************************************************************************/
107 bitvector bv_new(int size) {
111 /* Number of ints needed for size bits */
112 /* n = (((size+7)/8) + sizeof(int) - 1)/sizeof(int); */
113 n = BV_NUM_INTS(size);
115 bv = DumpMemory_allocate(sizeof(int) * n);
117 for(i = 0; i < n; i++) bv[i] = 0;
119 #ifdef BV_DEBUG_CHECK
126 /******************************************************************************
129 Checks if a specific bit of the bitvector is set.
132 int bit Index of bit to check (0..size(
134 RETURN: bool true if bit is set otherwise false
135 *******************************************************************************/
136 bool bv_get_bit(bitvector bv, int bit) {
139 _BV_ASSERT(bit >= 0);
141 i = BV_INT_INDEX(bit);
142 n = BV_BIT_INDEX(bit, i);
144 _BV_ASSERT(i < (BV_NUM_INTS(bv[0])));
145 return (bv[i] & (1<<n));
148 /******************************************************************************
151 Sets a specific bit of the bitvector
154 int bit Index of bit to set (0..size(
155 *******************************************************************************/
156 void bv_set_bit(bitvector bv, int bit) {
159 _BV_ASSERT(bit >= 0);
161 i = BV_INT_INDEX(bit);
162 n = BV_BIT_INDEX(bit, i);
164 _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
169 /******************************************************************************
172 Resets a specific bit of the bitvector
175 int bit Index of bit to reset (0..size(
176 *******************************************************************************/
177 void bv_reset_bit(bitvector bv, int bit) {
180 _BV_ASSERT(bit >= 0);
182 i = BV_INT_INDEX(bit);
183 n = BV_BIT_INDEX(bit, i);
185 _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
190 /******************************************************************************
193 Resets all bits of the bitvector
196 int size Size of the bitvector
197 *******************************************************************************/
198 void bv_reset(bitvector bv, int size) {
201 _BV_ASSERT(bv[0] == size);
203 n = BV_NUM_INTS(size);
205 #ifdef BV_DEBUG_CHECK
206 for(i = 1; i < n; i++)
208 for(i = 0; i < n; i++)
213 /******************************************************************************
216 Checks if no bits of the bitvector are set == bitvector is "empty"
219 int size Size of the bitvector
221 RETURN: bool return true if bv is empty, false otherwise
222 *******************************************************************************/
223 bool bv_is_empty(bitvector bv, int size) {
227 _BV_ASSERT(bv[0] == size);
229 n = BV_NUM_INTS(size);
232 #ifdef BV_DEBUG_CHECK
233 for(i = 1; (i < n) && empty; i++)
235 for(i = 0; (i < n) && empty; i++)
237 empty = empty && (bv[i] == 0);
241 /******************************************************************************
244 Copyes bitvector src to dst
246 IN: bitvector dst bitvector created with bv_new
247 bitvector src bitvector created with bv_new
248 int size Size of the bitvector
249 *******************************************************************************/
250 void bv_copy(bitvector dst, bitvector src, int size) {
252 /* copy the whole bitvector */
253 _BV_ASSERT(dst[0] == size);
254 _BV_ASSERT(src[0] == size);
255 n = BV_NUM_INTS(size);
257 #ifdef BV_DEBUG_CHECK
258 for(i = 1; i < n; i++)
260 for(i = 0; i < n; i++)
265 /******************************************************************************
268 Compares two bitvectors
270 IN: bitvector s1 bitvector created with bv_new
271 bitvector s2 bitvector created with bv_new
272 int size Size of the bitvector
274 RETURN: bool true if s1==s1, false otherwise
275 *******************************************************************************/
276 bool bv_equal(bitvector s1, bitvector s2, int size) {
280 /* copy the whole bitvector */
281 _BV_ASSERT(s1[0] == size);
282 _BV_ASSERT(s2[0] == size);
287 n = BV_NUM_INTS(size);
289 #ifdef BV_DEBUG_CHECK
290 for(i = 1; equal && (i < n-1); i++)
292 for(i = 0; equal && (i < n-1); i++)
294 equal = (s1[i] == s2[i]);
296 /* Last compare maybe has to be masked! */
298 i = BV_INT_INDEX(size - 1);
299 n = BV_BIT_INDEX(size - 1, i);
301 _BV_ASSERT(i < BV_NUM_INTS(s1[0]));
302 _BV_ASSERT(i < BV_NUM_INTS(s2[0]));
304 if (n == (sizeof(int) * 8 - 1)) {
308 mask = (1<<(n+1)) - 1;
311 equal = equal && ( (s1[i]&mask) == (s2[i]&mask));
316 /******************************************************************************
319 d = s1 \ s2. ( set minus operator )
321 IN: bitvector s1 bitvector created with bv_new
322 bitvector s2 bitvector created with bv_new
323 int size Size of the bitvector
325 IN/OUT:bitvector d bitvector created with bv_new
327 *******************************************************************************/
328 void bv_minus(bitvector d, bitvector s1, bitvector s2, int size) {
331 _BV_ASSERT(d[0] == size);
332 _BV_ASSERT(s1[0] == size);
333 _BV_ASSERT(s2[0] == size);
334 n = BV_NUM_INTS(size);
335 #ifdef BV_DEBUG_CHECK
336 for(i = 1; i < n; i++)
338 for(i = 0; i < n; i++)
340 d[i] = s1[i] & (~s2[i]);
343 /******************************************************************************
346 d = s1 "union" s2. ( set union operator )
348 IN: bitvector s1 bitvector created with bv_new
349 bitvector s2 bitvector created with bv_new
350 int size Size of the bitvector
352 IN/OUT:bitvector d bitvector created with bv_new
354 *******************************************************************************/
355 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 n = BV_NUM_INTS(size);
362 #ifdef BV_DEBUG_CHECK
363 for(i = 1; i < n; i++)
365 for(i = 0; i < n; i++)
367 d[i] = s1[i] | s2[i];
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 * ---------------------------------------------------------------------
377 * indent-tabs-mode: t