src/toolbox/bitvector.c

   1 /* toolbox/bitvector.c - bitvector implementation
   2
   3    Copyright (C) 1996-2005 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
  44 #ifdef BV_DEBUG_CHECK
  45   /* Number of ints needed for size bits */
  46 # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1) / sizeof(int) + 1)
  47   /* Get index in bitvector */
  48 # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) + 1)
  49   /* Get bit index inside int */
  50 # define BV_BIT_INDEX(bit, index) ( (bit) - (index - 1) * sizeof(int) * 8 );
  51 #else
  52   /* Number of ints needed for size bits */
  53 # define BV_NUM_INTS(size) (((((size) + 7)/ 8) + sizeof(int) - 1) / sizeof(int))
  54   /* Get index in bitvector */
  55 # define BV_INT_INDEX(bit) ( ((bit) / 8) / sizeof(int) )
  56   /* Get bit index inside int */
  57 # define BV_BIT_INDEX(bit, index) ( (bit) - (index) * sizeof(int) * 8 );
  58 #endif
  59
  60
  61 char *bv_to_string(bitvector bv, char *string, int size) {
  62         int i;
  63
  64         _BV_ASSERT(bv[0] == size);
  65
  66         for(i = 0; i < size; i++)
  67                 if (bv_get_bit(bv, i))
  68                         string[i]='1';
  69                 else
  70                         string[i]='0';
  71
  72         string[i]=0;
  73         return string;
  74 }
  75
  76 int *bv_new(int size) {
  77         int i,n;
  78         int *bv;
  79
  80         /* Number of ints needed for size bits */
  81 /*      n = (((size+7)/8) + sizeof(int) - 1)/sizeof(int);  */
  82         n = BV_NUM_INTS(size);
  83
  84         bv = DMNEW(int, n);
  85
  86         for(i = 0; i < n; i++) bv[i] = 0;
  87
  88 #ifdef BV_DEBUG_CHECK
  89         bv[0] = size;
  90 #endif
  91
  92         return bv;
  93 }
  94
  95 bool bv_get_bit(bitvector bv, int bit) {
  96         int i, n;
  97
  98         _BV_ASSERT(bit >= 0);
  99
 100         i = BV_INT_INDEX(bit);
 101         n = BV_BIT_INDEX(bit, i);
 102
 103         _BV_ASSERT(i < (BV_NUM_INTS(bv[0])));
 104         return (bv[i] & (1<<n));
 105 }
 106
 107 void bv_set_bit(bitvector bv, int bit) {
 108         int i, n;
 109
 110         _BV_ASSERT(bit >= 0);
 111
 112         i = BV_INT_INDEX(bit);
 113         n = BV_BIT_INDEX(bit, i);
 114
 115         _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
 116
 117         bv[i] |= 1<<n;
 118 }
 119
 120 void bv_reset_bit(bitvector bv, int bit) {
 121         int i, n;
 122
 123         _BV_ASSERT(bit >= 0);
 124
 125         i = BV_INT_INDEX(bit);
 126         n = BV_BIT_INDEX(bit, i);
 127
 128         _BV_ASSERT(i < BV_NUM_INTS(bv[0]));
 129
 130         bv[i] &= ~(1<<n);
 131 }
 132
 133 void bv_reset(bitvector bv, int size) {
 134         int i,n;
 135
 136         _BV_ASSERT(bv[0] == size);
 137
 138         n = BV_NUM_INTS(size);
 139
 140 #ifdef BV_DEBUG_CHECK
 141         for(i = 1; i < n; i++)
 142 #else
 143         for(i = 0; i < n; i++)
 144 #endif
 145                 bv[i] = 0;
 146 }
 147
 148 bool bv_is_empty(bitvector bv, int size) {
 149         int i,n;
 150         bool empty;
 151
 152         _BV_ASSERT(bv[0] == size);
 153
 154         n = BV_NUM_INTS(size);
 155
 156         empty = true;
 157 #ifdef BV_DEBUG_CHECK
 158         for(i = 1; (i < n) && empty; i++)
 159 #else
 160         for(i = 0; (i < n) && empty; i++)
 161 #endif
 162                 empty = empty && (bv[i] == 0);
 163         return empty;
 164 }
 165
 166 void bv_copy(bitvector dst, bitvector src, int size) {
 167         int i,n;
 168         /* copy the whole bitvector    */
 169         _BV_ASSERT(dst[0] == size);
 170         _BV_ASSERT(src[0] == size);
 171         n = BV_NUM_INTS(size);
 172
 173 #ifdef BV_DEBUG_CHECK
 174         for(i = 1; i < n; i++)
 175 #else
 176         for(i = 0; i < n; i++)
 177 #endif
 178                 dst[i] = src[i];
 179 }
 180
 181 bool bv_equal(bitvector s1, bitvector s2, int size) {
 182         int i,n;
 183         int mask;
 184         bool equal = true;
 185         /* copy the whole bitvector    */
 186         _BV_ASSERT(s1[0] == size);
 187         _BV_ASSERT(s2[0] == size);
 188
 189         if (size == 0)
 190                 return true;
 191
 192         n = BV_NUM_INTS(size);
 193
 194 #ifdef BV_DEBUG_CHECK
 195         for(i = 1; equal && (i < n-1); i++)
 196 #else
 197         for(i = 0; equal && (i < n-1); i++)
 198 #endif
 199                 equal = (s1[i] == s2[i]);
 200
 201         /* Last compare maybe has to be masked! */
 202
 203         i = BV_INT_INDEX(size - 1);
 204         n = BV_BIT_INDEX(size - 1, i);
 205
 206         _BV_ASSERT(i < BV_NUM_INTS(s1[0]));
 207         _BV_ASSERT(i < BV_NUM_INTS(s2[0]));
 208
 209         if (n == (sizeof(int) * 8 - 1)) {
 210                 /* full mask */
 211                 mask = -1;
 212         } else {
 213                 mask = (1<<(n+1)) - 1;
 214         }
 215
 216         equal = equal && ( (s1[i]&mask) == (s2[i]&mask));
 217
 218         return equal;
 219 }
 220
 221 void bv_minus(bitvector d, bitvector s1, bitvector s2, int size) {
 222         int i,n;
 223     /* d = s1 - s2     */
 224         _BV_ASSERT(d[0] == size);
 225         _BV_ASSERT(s1[0] == size);
 226         _BV_ASSERT(s2[0] == size);
 227         n = BV_NUM_INTS(size);
 228 #ifdef BV_DEBUG_CHECK
 229         for(i = 1; i < n; i++)
 230 #else
 231         for(i = 0; i < n; i++)
 232 #endif
 233                 d[i] = s1[i] & (~s2[i]);
 234 }
 235
 236 void bv_union(bitvector d, bitvector s1, bitvector s2, int size) {
 237         int i,n;
 238     /* d = s1 union s2 */
 239         _BV_ASSERT(d[0] == size);
 240         _BV_ASSERT(s1[0] == size);
 241         _BV_ASSERT(s2[0] == size);
 242         n = BV_NUM_INTS(size);
 243 #ifdef BV_DEBUG_CHECK
 244         for(i = 1; i < n; i++)
 245 #else
 246         for(i = 0; i < n; i++)
 247 #endif
 248                 d[i] = s1[i] | s2[i];
 249 }
 250
 251 /*
 252  * These are local overrides for various environment variables in Emacs.
 253  * Please do not remove this and leave it at the end of the file, where
 254  * Emacs will automagically detect them.
 255  * ---------------------------------------------------------------------
 256  * Local variables:
 257  * mode: c
 258  * indent-tabs-mode: t
 259  * c-basic-offset: 4
 260  * tab-width: 4
 261  * End:
 262  */