1 /*-----------------------------------------------------------------
2 SDCCbitv.c - contains support routines for bitvectors
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
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
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.
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.
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 -------------------------------------------------------------------------*/
29 int bitVectDefault = 1024;
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 /*-----------------------------------------------------------------*/
44 bvp = Safe_calloc (1, sizeof (bitVect));
47 bvp->bSize = byteSize = (size / 8) + 1;
48 bvp->vect = Safe_calloc (1, byteSize);
52 /*-----------------------------------------------------------------*/
53 /* bitVectResize - changes the size of a bit vector */
54 /*-----------------------------------------------------------------*/
56 bitVectResize (bitVect * bvp, int size)
58 int bSize = (size / 8) + 1;
61 return newBitVect (size);
63 /* if we already have enough space */
64 if (bvp->bSize >= bSize)
71 bvp->vect = Clear_realloc (bvp->vect, bvp->bSize, bSize);
78 /*-----------------------------------------------------------------*/
79 /* bitVectSetBit - sets a given bit in the bit vector */
80 /*-----------------------------------------------------------------*/
82 bitVectSetBit (bitVect * bvp, int pos)
87 /* if set is null then allocate it */
89 bvp = newBitVect (bitVectDefault); /* allocate for twice the size */
92 bvp = bitVectResize (bvp, pos + 2); /* conservatively resize */
96 bvp->vect[byteSize] |= (((unsigned char) 1) <<
101 /*-----------------------------------------------------------------*/
102 /* bitVectUnSetBit - unsets the value of a bit in a bitvector */
103 /*-----------------------------------------------------------------*/
105 bitVectUnSetBit (bitVect * bvp, int pos)
114 if (bvp->bSize <= byteSize)
119 bvp->vect[byteSize] &= ~(((unsigned char) 1) <<
123 /*-----------------------------------------------------------------*/
124 /* bitVectBitValue - returns value value at bit position */
125 /*-----------------------------------------------------------------*/
127 bitVectBitValue (bitVect * bvp, int pos)
137 if (bvp->bSize <= byteSize)
142 return ((bvp->vect[byteSize] >> (7 - offset)) & ((unsigned char) 1));
146 /*-----------------------------------------------------------------*/
147 /* bitVectUnion - unions two bitvectors */
148 /*-----------------------------------------------------------------*/
150 bitVectUnion (bitVect * bvp1, bitVect * bvp2)
159 /* if one of them null then return the other */
161 return bitVectCopy (bvp2);
164 return bitVectCopy (bvp1);
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);
173 newBvp = newBitVect (bvp1->size);
175 for (i = 0; i < bvp1->bSize; i++)
176 newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
182 /*-----------------------------------------------------------------*/
183 /* bitVectIntersect - intersect two bitvectors */
184 /*-----------------------------------------------------------------*/
186 bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
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);
201 newBvp = newBitVect (bvp1->size);
203 for (i = 0; i < bvp1->bSize; i++)
204 newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
209 /*-----------------------------------------------------------------*/
210 /* bitVectBitsInCommon - special case of intersection determines */
211 /* if the vectors have any common bits set */
212 /*-----------------------------------------------------------------*/
214 bitVectBitsInCommon (bitVect * bvp1, bitVect * bvp2)
221 for (i = 0; i < min (bvp1->bSize, bvp2->bSize); i++)
222 if (bvp1->vect[i] & bvp2->vect[i])
228 /*-----------------------------------------------------------------*/
229 /* bitVectCplAnd - complement the second & and it with the first */
230 /*-----------------------------------------------------------------*/
232 bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
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);
249 for (i = 0; i < bvp1->bSize; i++)
250 bvp1->vect[i] = bvp1->vect[i] & (~bvp2->vect[i]);
255 /*-----------------------------------------------------------------*/
256 /* bitVectIsZero - bit vector has all bits turned off */
257 /*-----------------------------------------------------------------*/
259 bitVectIsZero (bitVect * bvp)
266 for (i = 0; i < bvp->bSize; i++)
267 if (bvp->vect[i] != 0)
273 /*-----------------------------------------------------------------*/
274 /* bitVectsEqual - returns 1 if the two bit vectors are equal */
275 /*-----------------------------------------------------------------*/
277 bitVectEqual (bitVect * bvp1, bitVect * bvp2)
287 if (bvp1->bSize != bvp2->bSize)
290 for (i = 0; i < bvp1->bSize; i++)
291 if (bvp1->vect[i] != bvp2->vect[i])
297 /*-----------------------------------------------------------------*/
298 /* bitVectCopy - creates a bitvector from another bit Vector */
299 /*-----------------------------------------------------------------*/
301 bitVectCopy (bitVect * bvp)
309 newBvp = newBitVect (bvp->size);
310 for (i = 0; i < bvp->bSize; i++)
311 newBvp->vect[i] = bvp->vect[i];
316 /*-----------------------------------------------------------------*/
317 /* bitVectnBitsOn - returns the number of bits that are on */
318 /*-----------------------------------------------------------------*/
320 bitVectnBitsOn (bitVect * bvp)
329 /* rip through most of the data in byte sized chunks */
331 for (i = 0; i < j; i++)
334 for (k = 0; k < 8; k++)
341 /* finish up the last fractional byte, if any */
342 for (i = j * 8; i < bvp->size; i++)
343 count += bitVectBitValue (bvp, i);
349 /*-----------------------------------------------------------------*/
350 /* bitVectFirstBit - returns the key for the first bit that is on */
351 /*-----------------------------------------------------------------*/
353 bitVectFirstBit (bitVect * bvp)
359 for (i = 0; i < bvp->size; i++)
360 if (bitVectBitValue (bvp, i))
366 /*-----------------------------------------------------------------*/
367 /* bitVectDebugOn - prints bits that are on */
368 /*-----------------------------------------------------------------*/
370 bitVectDebugOn (bitVect * bvp, FILE * of)
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++)
383 if (bitVectBitValue (bvp, i))
384 fprintf (of, "(%d) ", i);