src/toolbox/bitvector.c

   1 /* src/toolbox/bitvector.c - bitvector implementation
   2
   3    Copyright (C) 2005, 2006
   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 #include "config.h"
  28
  29 #include "mm/memory.h"
  30 #include "toolbox/bitvector.h"
  31
  32
  33 /******************************************************************************
  34
  35 Bitvector Implementation
  36
  37 ******************************************************************************/
  38
  39 #ifdef BV_DEBUG_CHECK
  40
  41   /* Number of ints needed for size bits */
  42
  43 # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1)\
  44                                                         / sizeof(int) + 1)
  45
  46   /* Get index in bitvector */
  47
  48 # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) + 1)
  49
  50   /* Get bit index inside int */
  51
  52 # define BV_BIT_INDEX(bit, index) ( (bit) - (index - 1) * sizeof(int) * 8 );
  53
  54 #else
  55
  56   /* Number of ints needed for size bits */
  57
  58 # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1) / sizeof(int))
  59
  60   /* Get index in bitvector */
  61
  62 # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) )
  63
  64   /* Get bit index inside int */
  65
  66 # define BV_BIT_INDEX(bit, index) ( (bit) - (index) * sizeof(int) * 8 );
  67
  68 #endif
  69
  70 /************************************************************************
  71 bv_to_string
  72
  73 Transforms the bitvector bv to a string of 1's and 0's.
  74
  75 IN: bitvector bv      bitvector created with bv_new()
  76     int       size    size of bitvector bv
  77
  78 IN/OUT:   char      *string allocated buffer, at least size + 1 elements
  79
  80 RETURN:pointer to string
  81 ******************************************************************************/
  82 char *bv_to_string(bitvector bv, char *string, int size) {
  83         int i;
  84
  85         _BV_ASSERT(bv[0] == size);
  86
  87         for(i = 0; i < size; i++)
  88                 if (bv_get_bit(bv, i))
  89                         string[i]='1';
  90                 else
  91                         string[i]='0';
  92
  93         string[i]=0;
  94         return string;
  95 }
  96
  97 /******************************************************************************
  98 bv_new
  99
 100 Creates a new bitvector and initializes all bits to 0.
 101
 102 IN: int       size    size of bitvector bv
 103
 104 RETURN: bitvector
 105
 106 *******************************************************************************/
 107 bitvector bv_new(int size) {
 108         int i,n;
 109         int *bv;
 110
 111         /* Number of ints needed for size bits */
 112     /* n = (((size+7)/8) + sizeof(int) - 1)/sizeof(int);  */
 113         n = BV_NUM_INTS(size);
 114
 115         bv = DumpMemory_allocate(sizeof(int) * n);
 116
 117         for(i = 0; i < n; i++) bv[i] = 0;
 118
 119 #ifdef BV_DEBUG_CHECK
 120         bv[0] = size;
 121 #endif
 122
 123         return bv;
 124 }
 125
 126 /******************************************************************************
 127 bv_get_bit
 128
 129 Checks if a specific bit of the bitvector is set.
 130
 131 IN:   bitvector bv
 132       int       bit    Index of bit to check (0..size(
 133
 134 RETURN:  bool      true if bit is set otherwise false
 135 *******************************************************************************/
 136 bool bv_get_bit(bitvector bv, int bit) {
 137         int i, n;
 138
 139         _BV_ASSERT(bit >= 0);
 140
 141         i = BV_INT_INDEX(bit);
 142         n = BV_BIT_INDEX(bit, i);
 143
 144         _BV_ASSERT(i < (BV_NUM_INTS(bv[0])));
 145         return (bv[i] & (1<<n));
 146 }
 147
 148 /******************************************************************************
 149 bv_set_bit
 150
 151 Sets a specific bit of the bitvector
 152
 153 IN:   bitvector bv
 154       int       bit    Index of bit to set (0..size(
 155 *******************************************************************************/
 156 void bv_set_bit(bitvector bv, int bit) {
 157         int i, n;
 158
 159         _BV_ASSERT(bit >= 0);
 160
 161         i = BV_INT_INDEX(bit);
 162         n = BV_BIT_INDEX(bit, i);
 163
 164         _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
 165
 166         bv[i] |= 1<<n;
 167 }
 168
 169 /******************************************************************************
 170 bv_reset_bit
 171
 172 Resets a specific bit of the bitvector
 173
 174 IN:   bitvector bv
 175       int       bit    Index of bit to reset (0..size(
 176 *******************************************************************************/
 177 void bv_reset_bit(bitvector bv, int bit) {
 178         int i, n;
 179
 180         _BV_ASSERT(bit >= 0);
 181
 182         i = BV_INT_INDEX(bit);
 183         n = BV_BIT_INDEX(bit, i);
 184
 185         _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
 186
 187         bv[i] &= ~(1<<n);
 188 }
 189
 190 /******************************************************************************
 191 bv_reset
 192
 193 Resets all bits of the bitvector
 194
 195 IN:   bitvector bv
 196       int       size    Size of the bitvector
 197 *******************************************************************************/
 198 void bv_reset(bitvector bv, int size) {
 199         int i,n;
 200
 201         _BV_ASSERT(bv[0] == size);
 202
 203         n = BV_NUM_INTS(size);
 204
 205 #ifdef BV_DEBUG_CHECK
 206         for(i = 1; i < n; i++)
 207 #else
 208         for(i = 0; i < n; i++)
 209 #endif
 210                 bv[i] = 0;
 211 }
 212
 213 /******************************************************************************
 214 bv_is_empty
 215
 216 Checks if no bits of the bitvector are set == bitvector is "empty"
 217
 218 IN:   bitvector bv
 219       int       size    Size of the bitvector
 220
 221 RETURN: bool  return true if bv is empty, false otherwise
 222 *******************************************************************************/
 223 bool bv_is_empty(bitvector bv, int size) {
 224         int i,n;
 225         bool empty;
 226
 227         _BV_ASSERT(bv[0] == size);
 228
 229         n = BV_NUM_INTS(size);
 230
 231         empty = true;
 232 #ifdef BV_DEBUG_CHECK
 233         for(i = 1; (i < n) && empty; i++)
 234 #else
 235         for(i = 0; (i < n) && empty; i++)
 236 #endif
 237                 empty = empty && (bv[i] == 0);
 238         return empty;
 239 }
 240
 241 /******************************************************************************
 242 bv_copy
 243
 244 Copyes bitvector src to dst
 245
 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) {
 251         int i,n;
 252         /* copy the whole bitvector    */
 253         _BV_ASSERT(dst[0] == size);
 254         _BV_ASSERT(src[0] == size);
 255         n = BV_NUM_INTS(size);
 256
 257 #ifdef BV_DEBUG_CHECK
 258         for(i = 1; i < n; i++)
 259 #else
 260         for(i = 0; i < n; i++)
 261 #endif
 262                 dst[i] = src[i];
 263 }
 264
 265 /******************************************************************************
 266 bv_equal
 267
 268 Compares two  bitvectors
 269
 270 IN:   bitvector s1      bitvector created with bv_new
 271       bitvector s2      bitvector created with bv_new
 272       int       size    Size of the bitvector
 273
 274 RETURN: bool    true if s1==s1, false otherwise
 275 *******************************************************************************/
 276 bool bv_equal(bitvector s1, bitvector s2, int size) {
 277         int i,n;
 278         int mask;
 279         bool equal = true;
 280         /* copy the whole bitvector    */
 281         _BV_ASSERT(s1[0] == size);
 282         _BV_ASSERT(s2[0] == size);
 283
 284         if (size == 0)
 285                 return true;
 286
 287         n = BV_NUM_INTS(size);
 288
 289 #ifdef BV_DEBUG_CHECK
 290         for(i = 1; equal && (i < n-1); i++)
 291 #else
 292         for(i = 0; equal && (i < n-1); i++)
 293 #endif
 294                 equal = (s1[i] == s2[i]);
 295
 296         /* Last compare maybe has to be masked! */
 297
 298         i = BV_INT_INDEX(size - 1);
 299         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         if (n == (sizeof(int) * 8 - 1)) {
 305                 /* full mask */
 306                 mask = -1;
 307         } else {
 308                 mask = (1<<(n+1)) - 1;
 309         }
 310
 311         equal = equal && ( (s1[i]&mask) == (s2[i]&mask));
 312
 313         return equal;
 314 }
 315
 316 /******************************************************************************
 317 bv_minus
 318
 319 d = s1 \ s2. ( set minus operator )
 320
 321 IN:    bitvector s1      bitvector created with bv_new
 322        bitvector s2      bitvector created with bv_new
 323        int       size    Size of the bitvector
 324
 325 IN/OUT:bitvector d       bitvector created with bv_new
 326
 327 *******************************************************************************/
 328 void bv_minus(bitvector d, bitvector s1, bitvector s2, int size) {
 329         int i,n;
 330     /* d = s1 - s2     */
 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++)
 337 #else
 338         for(i = 0; i < n; i++)
 339 #endif
 340                 d[i] = s1[i] & (~s2[i]);
 341 }
 342
 343 /******************************************************************************
 344 bv_minus
 345
 346 d = s1 "union" s2. ( set union operator )
 347
 348 IN:    bitvector s1      bitvector created with bv_new
 349        bitvector s2      bitvector created with bv_new
 350        int       size    Size of the bitvector
 351
 352 IN/OUT:bitvector d       bitvector created with bv_new
 353
 354 *******************************************************************************/
 355 void bv_union(bitvector d, bitvector s1, bitvector s2, int size) {
 356         int i,n;
 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++)
 364 #else
 365         for(i = 0; i < n; i++)
 366 #endif
 367                 d[i] = s1[i] | s2[i];
 368 }
 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  */