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 /*-----------------------------------------------------------------*/
38 bitVect *newBitVect (int size)
43 bvp = Safe_calloc(sizeof (bitVect));
46 bvp->bSize = byteSize = ( size / 8) + 1 ;
47 bvp->vect = Safe_calloc(byteSize);
51 /*-----------------------------------------------------------------*/
52 /* bitVectResize - changes the size of a bit vector */
53 /*-----------------------------------------------------------------*/
54 bitVect *bitVectResize (bitVect *bvp, int size)
56 int bSize = ( size / 8) + 1 ;
59 return newBitVect (size);
61 /* if we already have enough space */
62 if (bvp->bSize >= bSize ) {
68 bvp->vect = Clear_realloc(bvp->vect, bvp -> bSize, bSize);
75 /*-----------------------------------------------------------------*/
76 /* bitVectSetBit - sets a given bit in the bit vector */
77 /*-----------------------------------------------------------------*/
78 bitVect *bitVectSetBit (bitVect *bvp, int pos)
83 /* if set is null then allocate it */
85 bvp = newBitVect(bitVectDefault) ; /* allocate for twice the size */
87 if (bvp->size <= pos )
88 bvp = bitVectResize (bvp,pos+2); /* conservatively resize */
92 bvp->vect[byteSize] |= (((unsigned char)1) <<
97 /*-----------------------------------------------------------------*/
98 /* bitVectUnSetBit - unsets the value of a bit in a bitvector */
99 /*-----------------------------------------------------------------*/
100 void bitVectUnSetBit (bitVect *bvp, int pos)
109 if (bvp->bSize <= byteSize)
114 bvp->vect[byteSize] &= ~ (((unsigned char)1) <<
118 /*-----------------------------------------------------------------*/
119 /* bitVectBitValue - returns value value at bit position */
120 /*-----------------------------------------------------------------*/
121 int bitVectBitValue (bitVect *bvp, int pos)
131 if ( bvp->bSize <= byteSize )
136 return ((bvp->vect[byteSize] >> (7-offset)) & ((unsigned char)1) );
140 /*-----------------------------------------------------------------*/
141 /* bitVectUnion - unions two bitvectors */
142 /*-----------------------------------------------------------------*/
143 bitVect *bitVectUnion ( bitVect *bvp1, bitVect *bvp2)
152 /* if one of them null then return the other */
154 return bitVectCopy (bvp2);
156 if ( bvp1 && ! bvp2 )
157 return bitVectCopy (bvp1);
159 /* if they are not the same size */
160 /* make them the same size */
161 if (bvp1->bSize < bvp2->bSize)
162 bvp1 = bitVectResize (bvp1,bvp2->size);
164 if (bvp2->bSize < bvp1->bSize)
165 bvp2 = bitVectResize (bvp2,bvp1->size);
167 newBvp = newBitVect(bvp1->size);
169 for ( i = 0 ; i < bvp1->bSize ;i++)
170 newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
176 /*-----------------------------------------------------------------*/
177 /* bitVectIntersect - intersect two bitvectors */
178 /*-----------------------------------------------------------------*/
179 bitVect *bitVectIntersect ( bitVect *bvp1, bitVect *bvp2)
184 if (! bvp2 || ! bvp1 )
187 /* if they are not the same size */
188 /* make them the same size */
189 if (bvp1->bSize < bvp2->bSize)
190 bvp1 = bitVectResize (bvp1,bvp2->bSize);
192 if (bvp2->size < bvp1->size)
193 bvp2 = bitVectResize (bvp2,bvp1->size);
195 newBvp = newBitVect(bvp1->size);
197 for ( i = 0 ; i < bvp1->bSize ;i++)
198 newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
203 /*-----------------------------------------------------------------*/
204 /* bitVectBitsInCommon - special case of intersection determines */
205 /* if the vectors have any common bits set */
206 /*-----------------------------------------------------------------*/
207 int bitVectBitsInCommon ( bitVect *bvp1, bitVect *bvp2 )
211 if ( ! bvp1 || ! bvp2 )
214 for ( i = 0 ; i < min(bvp1->bSize,bvp2->bSize) ; i ++ )
215 if ( bvp1->vect[i] & bvp2->vect[i] )
221 /*-----------------------------------------------------------------*/
222 /* bitVectCplAnd - complement the second & and it with the first */
223 /*-----------------------------------------------------------------*/
224 bitVect *bitVectCplAnd ( bitVect *bvp1, bitVect *bvp2)
234 /* if they are not the same size */
235 /* make them the same size */
236 if (bvp1->bSize < bvp2->bSize)
237 bvp1 = bitVectResize (bvp1,bvp2->bSize);
239 if (bvp2->size < bvp1->size)
240 bvp2 = bitVectResize (bvp2,bvp1->size);
242 for ( i = 0 ; i < bvp1->bSize ;i++)
243 bvp1->vect[i] = bvp1->vect[i] & (~ bvp2->vect[i]);
248 /*-----------------------------------------------------------------*/
249 /* bitVectIsZero - bit vector has all bits turned off */
250 /*-----------------------------------------------------------------*/
251 int bitVectIsZero (bitVect *bvp)
258 for ( i = 0 ; i < bvp->bSize ; i++ )
259 if (bvp->vect[i] != 0)
265 /*-----------------------------------------------------------------*/
266 /* bitVectsEqual - returns 1 if the two bit vectors are equal */
267 /*-----------------------------------------------------------------*/
268 int bitVectEqual ( bitVect *bvp1, bitVect *bvp2)
278 if (bvp1->bSize != bvp2->bSize)
281 for (i = 0 ; i < bvp1->bSize ; i++ )
282 if ( bvp1->vect[i] != bvp2->vect[i] )
288 /*-----------------------------------------------------------------*/
289 /* bitVectCopy - creates a bitvector from another bit Vector */
290 /*-----------------------------------------------------------------*/
291 bitVect *bitVectCopy (bitVect *bvp)
299 newBvp = newBitVect(bvp->size);
300 for ( i = 0 ; i < bvp->bSize; i++ )
301 newBvp->vect[i] = bvp->vect[i];
306 /*-----------------------------------------------------------------*/
307 /* bitVectnBitsOn - returns the number of bits that are on */
308 /*-----------------------------------------------------------------*/
309 int bitVectnBitsOn (bitVect *bvp)
318 /* rip through most of the data in byte sized chunks */
320 for (i = 0 ; i < j; i++) {
322 for (k=0; k<8; k++) { count += byte&1; byte = byte>>1; }
325 /* finish up the last fractional byte, if any */
326 for (i = j*8 ; i < bvp->size; i++)
327 count += bitVectBitValue(bvp,i);
333 /*-----------------------------------------------------------------*/
334 /* bitVectFirstBit - returns the key for the first bit that is on */
335 /*-----------------------------------------------------------------*/
336 int bitVectFirstBit (bitVect *bvp)
342 for (i = 0; i < bvp->size ; i++ )
343 if (bitVectBitValue(bvp,i))
349 /*-----------------------------------------------------------------*/
350 /* bitVectDebugOn - prints bits that are on */
351 /*-----------------------------------------------------------------*/
352 void bitVectDebugOn (bitVect *bvp, FILE *of)
361 fprintf(of,"bitvector Size = %d bSize = %d\n",bvp->size,bvp->bSize);
362 fprintf(of,"Bits on { ");
363 for (i = 0 ; i < bvp->size ; i++) {
364 if (bitVectBitValue(bvp,i))
365 fprintf(of,"(%d) ",i);