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 /* freeBitVect - frees the memory used by the bitVector */
54 /*-----------------------------------------------------------------*/
56 freeBitVect (bitVect * bvp)
61 Safe_free (bvp->vect);
65 /*-----------------------------------------------------------------*/
66 /* bitVectResize - changes the size of a bit vector */
67 /*-----------------------------------------------------------------*/
69 bitVectResize (bitVect * bvp, int size)
71 int bSize = (size / 8) + 1;
74 return newBitVect (size);
76 /* if we already have enough space */
77 if (bvp->bSize >= bSize)
84 bvp->vect = Clear_realloc (bvp->vect, bvp->bSize, bSize);
91 /*-----------------------------------------------------------------*/
92 /* bitVectSetBit - sets a given bit in the bit vector */
93 /*-----------------------------------------------------------------*/
95 bitVectSetBit (bitVect * bvp, int pos)
100 /* if set is null then allocate it */
102 bvp = newBitVect (bitVectDefault); /* allocate for twice the size */
104 if (bvp->size <= pos)
105 bvp = bitVectResize (bvp, pos + 2); /* conservatively resize */
109 bvp->vect[byteSize] |= (((unsigned char) 1) <<
114 /*-----------------------------------------------------------------*/
115 /* bitVectUnSetBit - unsets the value of a bit in a bitvector */
116 /*-----------------------------------------------------------------*/
118 bitVectUnSetBit (bitVect * bvp, int pos)
127 if (bvp->bSize <= byteSize)
132 bvp->vect[byteSize] &= ~(((unsigned char) 1) <<
136 /*-----------------------------------------------------------------*/
137 /* bitVectBitValue - returns value value at bit position */
138 /*-----------------------------------------------------------------*/
140 bitVectBitValue (bitVect * bvp, int pos)
150 if (bvp->bSize <= byteSize)
155 return ((bvp->vect[byteSize] >> (7 - offset)) & ((unsigned char) 1));
159 /*-----------------------------------------------------------------*/
160 /* bitVectUnion - unions two bitvectors */
161 /*-----------------------------------------------------------------*/
163 bitVectUnion (bitVect * bvp1, bitVect * bvp2)
167 unsigned int *pn, *p1, *p2;
174 /* if one of them null then return the other */
176 return bitVectCopy (bvp2);
179 return bitVectCopy (bvp1);
181 /* if they are not the same size */
182 /* make them the same size */
183 if (bvp1->bSize < bvp2->bSize)
184 bvp1 = bitVectResize (bvp1, bvp2->size);
185 else if (bvp2->bSize < bvp1->bSize)
186 bvp2 = bitVectResize (bvp2, bvp1->size);
188 newBvp = newBitVect (bvp1->size);
192 pn = (unsigned int *)newBvp->vect;
193 p1 = (unsigned int *)bvp1->vect;
194 p2 = (unsigned int *)bvp2->vect;
196 while ((nbits - i) >= sizeof(*pn))
198 *pn++ = *p1++ | *p2++;
202 for (; i < nbits; i++)
203 newBvp->vect[i] = bvp1->vect[i] | bvp2->vect[i];
209 /*-----------------------------------------------------------------*/
210 /* bitVectIntersect - intersect two bitvectors */
211 /*-----------------------------------------------------------------*/
213 bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
217 unsigned int *pn, *p1, *p2;
223 /* if they are not the same size */
224 /* make them the same size */
225 if (bvp1->bSize < bvp2->bSize)
226 bvp1 = bitVectResize (bvp1, bvp2->bSize);
227 else if (bvp2->size < bvp1->size)
228 bvp2 = bitVectResize (bvp2, bvp1->size);
230 newBvp = newBitVect (bvp1->size);
234 pn = (unsigned int *)newBvp->vect;
235 p1 = (unsigned int *)bvp1->vect;
236 p2 = (unsigned int *)bvp2->vect;
238 while ((nbits - i) >= sizeof(*pn))
240 *pn++ = *p1++ & *p2++;
244 for (; i < nbits; i++)
245 newBvp->vect[i] = bvp1->vect[i] & bvp2->vect[i];
250 /*-----------------------------------------------------------------*/
251 /* bitVectBitsInCommon - special case of intersection determines */
252 /* if the vectors have any common bits set */
253 /*-----------------------------------------------------------------*/
255 bitVectBitsInCommon (bitVect * bvp1, bitVect * bvp2)
259 unsigned int *p1, *p2;
264 nbits = min (bvp1->bSize, bvp2->bSize);
267 p1 = (unsigned int *)bvp1->vect;
268 p2 = (unsigned int *)bvp2->vect;
270 while ((nbits-i) >= sizeof(*p1))
278 for (; i < nbits; i++)
279 if (bvp1->vect[i] & bvp2->vect[i])
285 /*-----------------------------------------------------------------*/
286 /* bitVectCplAnd - complement the second & and it with the first */
287 /*-----------------------------------------------------------------*/
289 bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
292 unsigned int *p1, *p2;
301 /* if they are not the same size */
302 /* make them the same size */
303 if (bvp1->bSize < bvp2->bSize)
304 bvp1 = bitVectResize (bvp1, bvp2->bSize);
305 else if (bvp2->size < bvp1->size)
306 bvp2 = bitVectResize (bvp2, bvp1->size);
311 p1 = (unsigned int *)bvp1->vect;
312 p2 = (unsigned int *)bvp2->vect;
314 while ((nbits - i) >= sizeof(*p1))
321 for (; i < nbits; i++)
322 bvp1->vect[i] = bvp1->vect[i] & (~bvp2->vect[i]);
327 /*-----------------------------------------------------------------*/
328 /* bitVectIsZero - bit vector has all bits turned off */
329 /*-----------------------------------------------------------------*/
331 bitVectIsZero (bitVect * bvp)
338 for (i = 0; i < bvp->bSize; i++)
339 if (bvp->vect[i] != 0)
345 /*-----------------------------------------------------------------*/
346 /* bitVectsEqual - returns 1 if the two bit vectors are equal */
347 /*-----------------------------------------------------------------*/
349 bitVectEqual (bitVect * bvp1, bitVect * bvp2)
359 if (bvp1->bSize != bvp2->bSize)
362 for (i = 0; i < bvp1->bSize; i++)
363 if (bvp1->vect[i] != bvp2->vect[i])
369 /*-----------------------------------------------------------------*/
370 /* bitVectCopy - creates a bitvector from another bit Vector */
371 /*-----------------------------------------------------------------*/
373 bitVectCopy (bitVect * bvp)
381 newBvp = newBitVect (bvp->size);
382 for (i = 0; i < bvp->bSize; i++)
383 newBvp->vect[i] = bvp->vect[i];
388 /*-----------------------------------------------------------------*/
389 /* bitVectnBitsOn - returns the number of bits that are on */
390 /*-----------------------------------------------------------------*/
392 bitVectnBitsOn (bitVect * bvp)
399 /* The bit vector is highest to lowest. Interesting. */
400 unsigned int mask[] = {
401 0, 128, 128+64, 128+64+32, 128+64+32+16,
402 128+64+32+16+8, 128+64+32+16+8+4, 128+64+32+16+8+4+2
408 /* j is the number of bytes in the bitvect */
409 j = (bvp->size+7) / 8;
411 /* Fix up the highest bits in the top byte so that we can iterate over
413 if (bvp->size%8 != 0)
415 bvp->vect[j-1] &= mask[bvp->size&7];
418 /* Take care of things in machine word chunks if possible. As we
419 are only counting bits it does not matter which order they are
423 p1 = (unsigned int *)bvp->vect;
425 while ((j-i) >= sizeof(*p1))
427 unsigned int word = *p1++;
436 /* Take care of the rest of the bitvect. */
449 /*-----------------------------------------------------------------*/
450 /* bitVectFirstBit - returns the key for the first bit that is on */
451 /*-----------------------------------------------------------------*/
453 bitVectFirstBit (bitVect * bvp)
459 for (i = 0; i < bvp->size; i++)
460 if (bitVectBitValue (bvp, i))
466 /*-----------------------------------------------------------------*/
467 /* bitVectDebugOn - prints bits that are on */
468 /*-----------------------------------------------------------------*/
470 bitVectDebugOn (bitVect * bvp, FILE * of)
479 fprintf (of, "bitvector Size = %d bSize = %d\n", bvp->size, bvp->bSize);
480 fprintf (of, "Bits on { ");
481 for (i = 0; i < bvp->size; i++)
483 if (bitVectBitValue (bvp, i))
484 fprintf (of, "(%d) ", i);