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 -------------------------------------------------------------------------*/
27 int bitVectDefault = 1024;
29 /* genernal note about a bitvectors:
30 bit vectors are stored from left to right i.e.
31 bit position 0 is the MS bit of the first byte
32 this also means that bit positions must start from 0*/
33 /*-----------------------------------------------------------------*/
34 /* newBitVect - returns a new bitvector of size */
35 /*-----------------------------------------------------------------*/
36 bitVect *newBitVect (int size)
41 ALLOC(bvp,sizeof (bitVect));
44 bvp->bSize = byteSize = ( size / 8) + 1 ;
45 ALLOC(bvp->vect,byteSize);
49 /*-----------------------------------------------------------------*/
50 /* bitVectResize - changes the size of a bit vector */
51 /*-----------------------------------------------------------------*/
52 bitVect *bitVectResize (bitVect *bvp, int size)
54 int bSize = ( size / 8) + 1 ;
57 return newBitVect (size);
59 /* if we already have enough space */
60 if (bvp->bSize >= bSize ) {
68 bvp->vect = GC_realloc(bvp->vect, bSize);
72 /*-----------------------------------------------------------------*/
73 /* bitVectSetBit - sets a given bit in the bit vector */
74 /*-----------------------------------------------------------------*/
75 bitVect *bitVectSetBit (bitVect *bvp, int pos)
80 /* if set is null then allocate it */
82 bvp = newBitVect(bitVectDefault) ; /* allocate for twice the size */
84 if (bvp->size <= pos )
85 bvp = bitVectResize (bvp,pos+2); /* conservatively resize */
89 bvp->vect[byteSize] |= (((unsigned char)1) <<
94 /*-----------------------------------------------------------------*/
95 /* bitVectUnSetBit - unsets the value of a bit in a bitvector */
96 /*-----------------------------------------------------------------*/
97 void bitVectUnSetBit (bitVect *bvp, int pos)
106 if (bvp->bSize <= byteSize)
111 bvp->vect[byteSize] &= ~ (((unsigned char)1) <<
115 /*-----------------------------------------------------------------*/
116 /* bitVectBitValue - returns value value at bit position */
117 /*-----------------------------------------------------------------*/
118 int bitVectBitValue (bitVect *bvp, int pos)
128 if ( bvp->bSize <= byteSize )
133 return ((bvp->vect[byteSize] >> (7-offset)) & ((unsigned char)1) );
137 /*-----------------------------------------------------------------*/
138 /* bitVectUnion - unions two bitvectors */
139 /*-----------------------------------------------------------------*/
140 bitVect *bitVectUnion ( bitVect *bvp1, bitVect *bvp2)
149 /* if one of them null then return the other */
151 return bitVectCopy (bvp2);
153 if ( bvp1 && ! bvp2 )
154 return bitVectCopy (bvp1);
156 /* if they are not the same size */
157 /* make them the same size */
158 if (bvp1->bSize < bvp2->bSize)
159 bvp1 = bitVectResize (bvp1,bvp2->size);
161 if (bvp2->bSize < bvp1->bSize)
162 bvp2 = bitVectResize (bvp2,bvp1->size);
164 newBvp = newBitVect(bvp1->size);
166 for ( i = 0 ; i < bvp1->bSize ;i++)
167 newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
173 /*-----------------------------------------------------------------*/
174 /* bitVectIntersect - intersect two bitvectors */
175 /*-----------------------------------------------------------------*/
176 bitVect *bitVectIntersect ( bitVect *bvp1, bitVect *bvp2)
181 if (! bvp2 || ! bvp1 )
184 /* if they are not the same size */
185 /* make them the same size */
186 if (bvp1->bSize < bvp2->bSize)
187 bvp1 = bitVectResize (bvp1,bvp2->bSize);
189 if (bvp2->size < bvp1->size)
190 bvp2 = bitVectResize (bvp2,bvp1->size);
192 newBvp = newBitVect(bvp1->size);
194 for ( i = 0 ; i < bvp1->bSize ;i++)
195 newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
200 /*-----------------------------------------------------------------*/
201 /* bitVectBitsInCommon - special case of intersection determines */
202 /* if the vectors have any common bits set */
203 /*-----------------------------------------------------------------*/
204 int bitVectBitsInCommon ( bitVect *bvp1, bitVect *bvp2 )
208 if ( ! bvp1 || ! bvp2 )
211 for ( i = 0 ; i < min(bvp1->bSize,bvp2->bSize) ; i ++ )
212 if ( bvp1->vect[i] & bvp2->vect[i] )
218 /*-----------------------------------------------------------------*/
219 /* bitVectCplAnd - complement the second & and it with the first */
220 /*-----------------------------------------------------------------*/
221 bitVect *bitVectCplAnd ( bitVect *bvp1, bitVect *bvp2)
231 /* if they are not the same size */
232 /* make them the same size */
233 if (bvp1->bSize < bvp2->bSize)
234 bvp1 = bitVectResize (bvp1,bvp2->bSize);
236 if (bvp2->size < bvp1->size)
237 bvp2 = bitVectResize (bvp2,bvp1->size);
239 for ( i = 0 ; i < bvp1->bSize ;i++)
240 bvp1->vect[i] = bvp1->vect[i] & (~ bvp2->vect[i]);
245 /*-----------------------------------------------------------------*/
246 /* bitVectIsZero - bit vector has all bits turned off */
247 /*-----------------------------------------------------------------*/
248 int bitVectIsZero (bitVect *bvp)
255 for ( i = 0 ; i < bvp->bSize ; i++ )
256 if (bvp->vect[i] != 0)
262 /*-----------------------------------------------------------------*/
263 /* bitVectsEqual - returns 1 if the two bit vectors are equal */
264 /*-----------------------------------------------------------------*/
265 int bitVectEqual ( bitVect *bvp1, bitVect *bvp2)
275 if (bvp1->bSize != bvp2->bSize)
278 for (i = 0 ; i < bvp1->bSize ; i++ )
279 if ( bvp1->vect[i] != bvp2->vect[i] )
285 /*-----------------------------------------------------------------*/
286 /* bitVectCopy - creates a bitvector from another bit Vector */
287 /*-----------------------------------------------------------------*/
288 bitVect *bitVectCopy (bitVect *bvp)
296 newBvp = newBitVect(bvp->size);
297 for ( i = 0 ; i < bvp->bSize; i++ )
298 newBvp->vect[i] = bvp->vect[i];
303 /*-----------------------------------------------------------------*/
304 /* bitVectnBitsOn - returns the number of bits that are on */
305 /*-----------------------------------------------------------------*/
306 int bitVectnBitsOn (bitVect *bvp)
315 /* rip through most of the data in byte sized chunks */
317 for (i = 0 ; i < j; i++) {
319 for (k=0; k<8; k++) { count += byte&1; byte = byte>>1; }
322 /* finish up the last fractional byte, if any */
323 for (i = j*8 ; i < bvp->size; i++)
324 count += bitVectBitValue(bvp,i);
330 /*-----------------------------------------------------------------*/
331 /* bitVectFirstBit - returns the key for the first bit that is on */
332 /*-----------------------------------------------------------------*/
333 int bitVectFirstBit (bitVect *bvp)
339 for (i = 0; i < bvp->size ; i++ )
340 if (bitVectBitValue(bvp,i))
346 /*-----------------------------------------------------------------*/
347 /* bitVectDebugOn - prints bits that are on */
348 /*-----------------------------------------------------------------*/
349 void bitVectDebugOn (bitVect *bvp, FILE *of)
358 fprintf(of,"bitvector Size = %d bSize = %d\n",bvp->size,bvp->bSize);
359 fprintf(of,"Bits on { ");
360 for (i = 0 ; i < bvp->size ; i++) {
361 if (bitVectBitValue(bvp,i))
362 fprintf(of,"(%d) ",i);