git.gag.com Git - fw/sdcc/blob - src/SDCCbitv.c

   1 /*-----------------------------------------------------------------
   2     SDCCbitv.c - contains support routines for bitvectors
   3
   4     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
   5
   6     This program is free software; you can redistribute it and/or modify it
   7     under the terms of the GNU General Public License as published by the
   8     Free Software Foundation; either version 2, or (at your option) any
   9     later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20     In other words, you are welcome to use, share and improve this program.
  21     You are forbidden to forbid anyone else to use, share and improve
  22     what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24
  25 #include "common.h"
  26
  27 #include "newalloc.h"
  28
  29 int bitVectDefault = 1024;
  30
  31 /* genernal note about a bitvectors:
  32    bit vectors are stored from left to right i.e.
  33    bit position 0 is the MS bit of the first byte
  34    this also means that bit positions must start from 0 */
  35 /*-----------------------------------------------------------------*/
  36 /* newBitVect - returns a new bitvector of size                    */
  37 /*-----------------------------------------------------------------*/
  38 bitVect *
  39 newBitVect (int size)
  40 {
  41   bitVect *bvp;
  42   int byteSize;
  43
  44   bvp = Safe_calloc (1, sizeof (bitVect));
  45
  46   bvp->size = size;
  47   bvp->bSize = byteSize = (size / 8) + 1;
  48   bvp->vect = Safe_calloc (1, byteSize);
  49   return bvp;
  50 }
  51
  52 /*-----------------------------------------------------------------*/
  53 /* bitVectResize - changes the size of a bit vector                */
  54 /*-----------------------------------------------------------------*/
  55 bitVect *
  56 bitVectResize (bitVect * bvp, int size)
  57 {
  58   int bSize = (size / 8) + 1;
  59
  60   if (!bvp)
  61     return newBitVect (size);
  62
  63   /* if we already have enough space */
  64   if (bvp->bSize >= bSize)
  65     {
  66       if (size > bvp->size)
  67         bvp->size = size;
  68       return bvp;
  69     }
  70
  71   bvp->vect = Clear_realloc (bvp->vect, bvp->bSize, bSize);
  72   bvp->size = size;
  73   bvp->bSize = bSize;
  74
  75   return bvp;
  76 }
  77
  78 /*-----------------------------------------------------------------*/
  79 /* bitVectSetBit - sets a given bit in the bit vector              */
  80 /*-----------------------------------------------------------------*/
  81 bitVect *
  82 bitVectSetBit (bitVect * bvp, int pos)
  83 {
  84   int byteSize;
  85   int offset;
  86
  87   /* if set is null then allocate it */
  88   if (!bvp)
  89     bvp = newBitVect (bitVectDefault);  /* allocate for twice the size */
  90
  91   if (bvp->size <= pos)
  92     bvp = bitVectResize (bvp, pos + 2);         /* conservatively resize */
  93
  94   byteSize = pos / 8;
  95   offset = pos % 8;
  96   bvp->vect[byteSize] |= (((unsigned char) 1) <<
  97                           (7 - offset));
  98   return bvp;
  99 }
 100
 101 /*-----------------------------------------------------------------*/
 102 /* bitVectUnSetBit - unsets the value of a bit in a bitvector      */
 103 /*-----------------------------------------------------------------*/
 104 void
 105 bitVectUnSetBit (bitVect * bvp, int pos)
 106 {
 107   int byteSize;
 108   int offset;
 109
 110   if (!bvp)
 111     return;
 112
 113   byteSize = pos / 8;
 114   if (bvp->bSize <= byteSize)
 115     return;
 116
 117   offset = pos % 8;
 118
 119   bvp->vect[byteSize] &= ~(((unsigned char) 1) <<
 120                            (7 - offset));
 121 }
 122
 123 /*-----------------------------------------------------------------*/
 124 /* bitVectBitValue - returns value value at bit position           */
 125 /*-----------------------------------------------------------------*/
 126 int
 127 bitVectBitValue (bitVect * bvp, int pos)
 128 {
 129   int byteSize;
 130   int offset;
 131
 132   if (!bvp)
 133     return 0;
 134
 135   byteSize = pos / 8;
 136
 137   if (bvp->bSize <= byteSize)
 138     return 0;
 139
 140   offset = pos % 8;
 141
 142   return ((bvp->vect[byteSize] >> (7 - offset)) & ((unsigned char) 1));
 143
 144 }
 145
 146 /*-----------------------------------------------------------------*/
 147 /* bitVectUnion - unions two bitvectors                            */
 148 /*-----------------------------------------------------------------*/
 149 bitVect *
 150 bitVectUnion (bitVect * bvp1, bitVect * bvp2)
 151 {
 152   int i;
 153   bitVect *newBvp;
 154
 155   /* if both null */
 156   if (!bvp1 && !bvp2)
 157     return NULL;
 158
 159   /* if one of them null then return the other */
 160   if (!bvp1 && bvp2)
 161     return bitVectCopy (bvp2);
 162
 163   if (bvp1 && !bvp2)
 164     return bitVectCopy (bvp1);
 165
 166   /* if they are not the same size */
 167   /* make them the same size */
 168   if (bvp1->bSize < bvp2->bSize)
 169     bvp1 = bitVectResize (bvp1, bvp2->size);
 170   else if (bvp2->bSize < bvp1->bSize)
 171     bvp2 = bitVectResize (bvp2, bvp1->size);
 172
 173   newBvp = newBitVect (bvp1->size);
 174
 175   for (i = 0; i < bvp1->bSize; i++)
 176     newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
 177
 178
 179   return newBvp;
 180 }
 181
 182 /*-----------------------------------------------------------------*/
 183 /* bitVectIntersect - intersect  two bitvectors                    */
 184 /*-----------------------------------------------------------------*/
 185 bitVect *
 186 bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
 187 {
 188   int i;
 189   bitVect *newBvp;
 190
 191   if (!bvp2 || !bvp1)
 192     return NULL;
 193
 194   /* if they are not the same size */
 195   /* make them the same size */
 196   if (bvp1->bSize < bvp2->bSize)
 197     bvp1 = bitVectResize (bvp1, bvp2->bSize);
 198   else if (bvp2->size < bvp1->size)
 199     bvp2 = bitVectResize (bvp2, bvp1->size);
 200
 201   newBvp = newBitVect (bvp1->size);
 202
 203   for (i = 0; i < bvp1->bSize; i++)
 204     newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
 205
 206   return newBvp;
 207 }
 208
 209 /*-----------------------------------------------------------------*/
 210 /* bitVectBitsInCommon - special case of intersection determines   */
 211 /*                       if the vectors have any common bits set   */
 212 /*-----------------------------------------------------------------*/
 213 int
 214 bitVectBitsInCommon (bitVect * bvp1, bitVect * bvp2)
 215 {
 216   int i;
 217
 218   if (!bvp1 || !bvp2)
 219     return 0;
 220
 221   for (i = 0; i < min (bvp1->bSize, bvp2->bSize); i++)
 222     if (bvp1->vect[i] & bvp2->vect[i])
 223       return 1;
 224
 225   return 0;
 226 }
 227
 228 /*-----------------------------------------------------------------*/
 229 /* bitVectCplAnd - complement the second & and it with the first   */
 230 /*-----------------------------------------------------------------*/
 231 bitVect *
 232 bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
 233 {
 234   int i;
 235
 236   if (!bvp2)
 237     return bvp1;
 238
 239   if (!bvp1)
 240     return bvp1;
 241
 242   /* if they are not the same size */
 243   /* make them the same size */
 244   if (bvp1->bSize < bvp2->bSize)
 245     bvp1 = bitVectResize (bvp1, bvp2->bSize);
 246   else if (bvp2->size < bvp1->size)
 247     bvp2 = bitVectResize (bvp2, bvp1->size);
 248
 249   for (i = 0; i < bvp1->bSize; i++)
 250     bvp1->vect[i] = bvp1->vect[i] & (~bvp2->vect[i]);
 251
 252   return bvp1;
 253 }
 254
 255 /*-----------------------------------------------------------------*/
 256 /* bitVectIsZero - bit vector has all bits turned off              */
 257 /*-----------------------------------------------------------------*/
 258 int
 259 bitVectIsZero (bitVect * bvp)
 260 {
 261   int i;
 262
 263   if (!bvp)
 264     return 1;
 265
 266   for (i = 0; i < bvp->bSize; i++)
 267     if (bvp->vect[i] != 0)
 268       return 0;
 269
 270   return 1;
 271 }
 272
 273 /*-----------------------------------------------------------------*/
 274 /* bitVectsEqual - returns 1 if the two bit vectors are equal      */
 275 /*-----------------------------------------------------------------*/
 276 int
 277 bitVectEqual (bitVect * bvp1, bitVect * bvp2)
 278 {
 279   int i;
 280
 281   if (!bvp1 || !bvp1)
 282     return 0;
 283
 284   if (bvp1 == bvp2)
 285     return 1;
 286
 287   if (bvp1->bSize != bvp2->bSize)
 288     return 0;
 289
 290   for (i = 0; i < bvp1->bSize; i++)
 291     if (bvp1->vect[i] != bvp2->vect[i])
 292       return 0;
 293
 294   return 1;
 295 }
 296
 297 /*-----------------------------------------------------------------*/
 298 /* bitVectCopy - creates a bitvector from another bit Vector       */
 299 /*-----------------------------------------------------------------*/
 300 bitVect *
 301 bitVectCopy (bitVect * bvp)
 302 {
 303   bitVect *newBvp;
 304   int i;
 305
 306   if (!bvp)
 307     return NULL;
 308
 309   newBvp = newBitVect (bvp->size);
 310   for (i = 0; i < bvp->bSize; i++)
 311     newBvp->vect[i] = bvp->vect[i];
 312
 313   return newBvp;
 314 }
 315
 316 /*-----------------------------------------------------------------*/
 317 /* bitVectnBitsOn - returns the number of bits that are on         */
 318 /*-----------------------------------------------------------------*/
 319 int
 320 bitVectnBitsOn (bitVect * bvp)
 321 {
 322   int i, j, k;
 323   unsigned char byte;
 324   int count = 0;
 325
 326   if (!bvp)
 327     return 0;
 328
 329   /* rip through most of the data in byte sized chunks */
 330   j = (bvp->size) / 8;
 331   for (i = 0; i < j; i++)
 332     {
 333       byte = bvp->vect[i];
 334       for (k = 0; k < 8; k++)
 335         {
 336           count += byte & 1;
 337           byte = byte >> 1;
 338         }
 339     }
 340
 341   /* finish up the last fractional byte, if any */
 342   for (i = j * 8; i < bvp->size; i++)
 343     count += bitVectBitValue (bvp, i);
 344
 345   return count;
 346
 347 }
 348
 349 /*-----------------------------------------------------------------*/
 350 /* bitVectFirstBit - returns the key for the first bit that is on  */
 351 /*-----------------------------------------------------------------*/
 352 int
 353 bitVectFirstBit (bitVect * bvp)
 354 {
 355   int i;
 356
 357   if (!bvp)
 358     return -1;
 359   for (i = 0; i < bvp->size; i++)
 360     if (bitVectBitValue (bvp, i))
 361       return i;
 362
 363   return -1;
 364 }
 365
 366 /*-----------------------------------------------------------------*/
 367 /* bitVectDebugOn - prints bits that are on                        */
 368 /*-----------------------------------------------------------------*/
 369 void
 370 bitVectDebugOn (bitVect * bvp, FILE * of)
 371 {
 372   int i;
 373
 374   if (of == NULL)
 375     of = stdout;
 376   if (!bvp)
 377     return;
 378
 379   fprintf (of, "bitvector Size = %d bSize = %d\n", bvp->size, bvp->bSize);
 380   fprintf (of, "Bits on { ");
 381   for (i = 0; i < bvp->size; i++)
 382     {
 383       if (bitVectBitValue (bvp, i))
 384         fprintf (of, "(%d) ", i);
 385     }
 386   fprintf (of, "}\n");
 387 }