src/toolbox/bitvector.c

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