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)
154 unsigned int *pn, *p1, *p2;
161 /* if one of them null then return the other */
163 return bitVectCopy (bvp2);
166 return bitVectCopy (bvp1);
168 /* if they are not the same size */
169 /* make them the same size */
170 if (bvp1->bSize < bvp2->bSize)
171 bvp1 = bitVectResize (bvp1, bvp2->size);
172 else if (bvp2->bSize < bvp1->bSize)
173 bvp2 = bitVectResize (bvp2, bvp1->size);
175 newBvp = newBitVect (bvp1->size);
179 pn = (unsigned int *)newBvp->vect;
180 p1 = (unsigned int *)bvp1->vect;
181 p2 = (unsigned int *)bvp2->vect;
183 while ((nbits - i) >= sizeof(*pn))
185 *pn++ = *p1++ | *p2++;
189 for (; i < nbits; i++)
190 newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
196 /*-----------------------------------------------------------------*/
197 /* bitVectIntersect - intersect two bitvectors */
198 /*-----------------------------------------------------------------*/
200 bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
204 unsigned int *pn, *p1, *p2;
210 /* if they are not the same size */
211 /* make them the same size */
212 if (bvp1->bSize < bvp2->bSize)
213 bvp1 = bitVectResize (bvp1, bvp2->bSize);
214 else if (bvp2->size < bvp1->size)
215 bvp2 = bitVectResize (bvp2, bvp1->size);
217 newBvp = newBitVect (bvp1->size);
221 pn = (unsigned int *)newBvp->vect;
222 p1 = (unsigned int *)bvp1->vect;
223 p2 = (unsigned int *)bvp2->vect;
225 while ((nbits - i) >= sizeof(*pn))
227 *pn++ = *p1++ & *p2++;
231 for (; i < nbits; i++)
232 newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
237 /*-----------------------------------------------------------------*/
238 /* bitVectBitsInCommon - special case of intersection determines */
239 /* if the vectors have any common bits set */
240 /*-----------------------------------------------------------------*/
242 bitVectBitsInCommon (bitVect * bvp1, bitVect * bvp2)
246 unsigned int *p1, *p2;
251 nbits = min (bvp1->bSize, bvp2->bSize);
254 p1 = (unsigned int *)bvp1->vect;
255 p2 = (unsigned int *)bvp2->vect;
257 while ((nbits-i) >= sizeof(*p1))
265 for (; i < nbits; i++)
266 if (bvp1->vect[i] & bvp2->vect[i])
272 /*-----------------------------------------------------------------*/
273 /* bitVectCplAnd - complement the second & and it with the first */
274 /*-----------------------------------------------------------------*/
276 bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
279 unsigned int *p1, *p2;
288 /* if they are not the same size */
289 /* make them the same size */
290 if (bvp1->bSize < bvp2->bSize)
291 bvp1 = bitVectResize (bvp1, bvp2->bSize);
292 else if (bvp2->size < bvp1->size)
293 bvp2 = bitVectResize (bvp2, bvp1->size);
298 p1 = (unsigned int *)bvp1->vect;
299 p2 = (unsigned int *)bvp2->vect;
301 while ((nbits - i) >= sizeof(*p1))
308 for (; i < nbits; i++)
309 bvp1->vect[i] = bvp1->vect[i] & (~bvp2->vect[i]);
314 /*-----------------------------------------------------------------*/
315 /* bitVectIsZero - bit vector has all bits turned off */
316 /*-----------------------------------------------------------------*/
318 bitVectIsZero (bitVect * bvp)
325 for (i = 0; i < bvp->bSize; i++)
326 if (bvp->vect[i] != 0)
332 /*-----------------------------------------------------------------*/
333 /* bitVectsEqual - returns 1 if the two bit vectors are equal */
334 /*-----------------------------------------------------------------*/
336 bitVectEqual (bitVect * bvp1, bitVect * bvp2)
346 if (bvp1->bSize != bvp2->bSize)
349 for (i = 0; i < bvp1->bSize; i++)
350 if (bvp1->vect[i] != bvp2->vect[i])
356 /*-----------------------------------------------------------------*/
357 /* bitVectCopy - creates a bitvector from another bit Vector */
358 /*-----------------------------------------------------------------*/
360 bitVectCopy (bitVect * bvp)
368 newBvp = newBitVect (bvp->size);
369 for (i = 0; i < bvp->bSize; i++)
370 newBvp->vect[i] = bvp->vect[i];
375 /*-----------------------------------------------------------------*/
376 /* bitVectnBitsOn - returns the number of bits that are on */
377 /*-----------------------------------------------------------------*/
379 bitVectnBitsOn (bitVect * bvp)
386 /* The bit vector is highest to lowest. Interesting. */
387 unsigned int mask[] = {
388 0, 128, 128+64, 128+64+32, 128+64+32+16,
389 128+64+32+16+8, 128+64+32+16+8+4, 128+64+32+16+8+4+2
395 /* j is the number of bytes in the bitvect */
396 j = (bvp->size+7) / 8;
398 /* Fix up the highest bits in the top byte so that we can iterate over
400 if (bvp->size%8 != 0)
402 bvp->vect[j-1] &= mask[bvp->size&7];
405 /* Take care of things in machine word chunks if possible. As we
406 are only counting bits it does not matter which order they are
410 p1 = (unsigned int *)bvp->vect;
412 while ((j-i) >= sizeof(*p1))
414 unsigned int word = *p1++;
423 /* Take care of the rest of the bitvect. */
436 /*-----------------------------------------------------------------*/
437 /* bitVectFirstBit - returns the key for the first bit that is on */
438 /*-----------------------------------------------------------------*/
440 bitVectFirstBit (bitVect * bvp)
446 for (i = 0; i < bvp->size; i++)
447 if (bitVectBitValue (bvp, i))
453 /*-----------------------------------------------------------------*/
454 /* bitVectDebugOn - prints bits that are on */
455 /*-----------------------------------------------------------------*/
457 bitVectDebugOn (bitVect * bvp, FILE * of)
466 fprintf (of, "bitvector Size = %d bSize = %d\n", bvp->size, bvp->bSize);
467 fprintf (of, "Bits on { ");
468 for (i = 0; i < bvp->size; i++)
470 if (bitVectBitValue (bvp, i))
471 fprintf (of, "(%d) ", i);