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