1 /*-----------------------------------------------------------------
2 SDCCbitv.c - contains support routines for bitvectors
3
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
5
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
9 later version.
10
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.
15
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.
19
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 -------------------------------------------------------------------------*/
24
25 #include "common.h"
26
27 #include "newalloc.h"
28
29 int bitVectDefault = 1024;
30
31 #define BYTE_SIZEOF_ELEMENT (sizeof(unsigned int))
32 #define BIT_SIZEOF_ELEMENT (BYTE_SIZEOF_ELEMENT*8)
33
34 /* genernal note about a bitvectors:
35 bit positions must start from 0 */
36 /*-----------------------------------------------------------------*/
37 /* newBitVect - returns a new bitvector of size */
38 /*-----------------------------------------------------------------*/
39 bitVect *
newBitVect(int size)40 newBitVect (int size)
41 {
42 bitVect *bvp;
43
44 bvp = Safe_calloc (1, sizeof (bitVect));
45
46 bvp->size = size;
47 bvp->allocSize = (size+BIT_SIZEOF_ELEMENT-1) / BIT_SIZEOF_ELEMENT;
48 bvp->vect = Safe_calloc (BYTE_SIZEOF_ELEMENT, bvp->allocSize);
49 return bvp;
50 }
51
52
53 /*-----------------------------------------------------------------*/
54 /* freeBitVect - frees the memory used by the bitVector */
55 /*-----------------------------------------------------------------*/
56 void
freeBitVect(bitVect * bvp)57 freeBitVect (bitVect * bvp)
58 {
59 if (!bvp)
60 return;
61
62 Safe_free (bvp->vect);
63 Safe_free (bvp);
64 }
65
66 /*-----------------------------------------------------------------*/
67 /* bitVectResize - changes the size of a bit vector */
68 /*-----------------------------------------------------------------*/
69 bitVect *
bitVectResize(bitVect * bvp,int size)70 bitVectResize (bitVect * bvp, int size)
71 {
72 int allocSize;
73
74 if (!bvp)
75 return newBitVect (size);
76
77 allocSize = (size+BIT_SIZEOF_ELEMENT-1) / BIT_SIZEOF_ELEMENT;
78
79 /* if we already have enough space */
80 if (bvp->allocSize >= allocSize)
81 {
82 if (size > bvp->size)
83 bvp->size = size;
84 return bvp;
85 }
86
87 bvp->vect = Clear_realloc (bvp->vect, bvp->allocSize*BYTE_SIZEOF_ELEMENT, allocSize*BYTE_SIZEOF_ELEMENT);
88 bvp->size = size;
89 bvp->allocSize = allocSize;
90
91 return bvp;
92 }
93
94 /*-----------------------------------------------------------------*/
95 /* bitVectSetBit - sets a given bit in the bit vector */
96 /*-----------------------------------------------------------------*/
97 bitVect *
bitVectSetBit(bitVect * bvp,int pos)98 bitVectSetBit (bitVect * bvp, int pos)
99 {
100 unsigned int index;
101 unsigned int bitofs;
102
103 assert (pos>=0);
104 /* if set is null then allocate it */
105 if (!bvp)
106 bvp = newBitVect (bitVectDefault); /* allocate for twice the size */
107
108 if (bvp->size <= pos)
109 bvp = bitVectResize (bvp, pos + 2); /* conservatively resize */
110
111 index = pos / BIT_SIZEOF_ELEMENT;
112 bitofs = pos % BIT_SIZEOF_ELEMENT;
113 bvp->vect[index] |= 1u << bitofs;
114 return bvp;
115 }
116
117 /*-----------------------------------------------------------------*/
118 /* bitVectUnSetBit - unsets the value of a bit in a bitvector */
119 /*-----------------------------------------------------------------*/
120 void
bitVectUnSetBit(const bitVect * bvp,int pos)121 bitVectUnSetBit (const bitVect *bvp, int pos)
122 {
123 unsigned int index;
124 unsigned int bitofs;
125
126 assert (pos>=0);
127 if (!bvp)
128 return;
129
130 if (bvp->size <= pos)
131 return;
132
133 index = pos / BIT_SIZEOF_ELEMENT;
134 bitofs = pos % BIT_SIZEOF_ELEMENT;
135 bvp->vect[index] &= ~(1u << bitofs);
136 }
137
138 /*-----------------------------------------------------------------*/
139 /* bitVectBitValue - returns value value at bit position */
140 /*-----------------------------------------------------------------*/
141 int
bitVectBitValue(const bitVect * bvp,int pos)142 bitVectBitValue (const bitVect *bvp, int pos)
143 {
144 unsigned int index;
145 unsigned int bitofs;
146
147 assert (pos>=0);
148 if (!bvp)
149 return 0;
150
151 index = pos / BIT_SIZEOF_ELEMENT;
152 bitofs = pos % BIT_SIZEOF_ELEMENT;
153
154 if (bvp->size <= pos)
155 return 0;
156
157
158 return (bvp->vect[index] >> bitofs) & 1;
159 }
160
161 /*-----------------------------------------------------------------*/
162 /* bitVectUnion - unions two bitvectors */
163 /*-----------------------------------------------------------------*/
164 bitVect *
bitVectUnion(bitVect * bvp1,bitVect * bvp2)165 bitVectUnion (bitVect * bvp1, bitVect * bvp2)
166 {
167 bitVect *newBvp;
168 unsigned int *pn, *p1, *p2;
169 int elements;
170
171 /* if both null */
172 if (!bvp1 && !bvp2)
173 return NULL;
174
175 /* if one of them null then return the other */
176 if (!bvp1 && bvp2)
177 return bitVectCopy (bvp2);
178
179 if (bvp1 && !bvp2)
180 return bitVectCopy (bvp1);
181
182 /* if they are not the same size */
183 /* make them the same size */
184 if (bvp1->size < bvp2->size)
185 bvp1 = bitVectResize (bvp1, bvp2->size);
186 else if (bvp2->size < bvp1->size)
187 bvp2 = bitVectResize (bvp2, bvp1->size);
188
189 newBvp = newBitVect (bvp1->size);
190 elements = bvp1->allocSize;
191
192 pn = newBvp->vect;
193 p1 = bvp1->vect;
194 p2 = bvp2->vect;
195
196 while (elements--)
197 {
198 *pn++ = *p1++ | *p2++;
199 }
200
201 return newBvp;
202 }
203
204 /*-----------------------------------------------------------------*/
205 /* bitVectInplaceUnion - unions two bitvectors */
206 /*-----------------------------------------------------------------*/
207 bitVect *
bitVectInplaceUnion(bitVect * bvp1,bitVect * bvp2)208 bitVectInplaceUnion (bitVect * bvp1, bitVect * bvp2)
209 {
210 unsigned int *p1, *p2;
211 int elements;
212
213 /* if both null */
214 if (!bvp1 && !bvp2)
215 return NULL;
216
217 /* if one of them null then return the other */
218 if (!bvp1 && bvp2)
219 return bitVectCopy (bvp2);
220
221 if (bvp1 && !bvp2)
222 return bvp1;
223
224 /* if they are not the same size */
225 /* make them the same size */
226 if (bvp1->size < bvp2->size)
227 bvp1 = bitVectResize (bvp1, bvp2->size);
228 else if (bvp2->size < bvp1->size)
229 bvp2 = bitVectResize (bvp2, bvp1->size);
230
231 elements = bvp1->allocSize;
232
233 p1 = bvp1->vect;
234 p2 = bvp2->vect;
235
236 while (elements--)
237 {
238 *p1 |= *p2;
239 p1++; p2++;
240 }
241
242 return bvp1;
243 }
244
245
246 /*-----------------------------------------------------------------*/
247 /* bitVectIntersect - intersect two bitvectors */
248 /*-----------------------------------------------------------------*/
249 bitVect *
bitVectIntersect(bitVect * bvp1,bitVect * bvp2)250 bitVectIntersect (bitVect * bvp1, bitVect * bvp2)
251 {
252 bitVect *newBvp;
253 unsigned int *pn, *p1, *p2;
254 int elements;
255
256 if (!bvp2 || !bvp1)
257 return NULL;
258
259 /* if they are not the same size */
260 /* make them the same size */
261 if (bvp1->size < bvp2->size)
262 bvp1 = bitVectResize (bvp1, bvp2->size);
263 else if (bvp2->size < bvp1->size)
264 bvp2 = bitVectResize (bvp2, bvp1->size);
265
266 newBvp = newBitVect (bvp1->size);
267 elements = bvp1->allocSize;
268
269 pn = newBvp->vect;
270 p1 = bvp1->vect;
271 p2 = bvp2->vect;
272
273 while (elements--)
274 {
275 *pn++ = *p1++ & *p2++;
276 }
277
278 return newBvp;
279 }
280
281 /*-----------------------------------------------------------------*/
282 /* bitVectInplaceIntersect - intersect two bitvectors */
283 /*-----------------------------------------------------------------*/
284 bitVect *
bitVectInplaceIntersect(bitVect * bvp1,bitVect * bvp2)285 bitVectInplaceIntersect (bitVect * bvp1, bitVect * bvp2)
286 {
287 unsigned int *p1, *p2;
288 int elements;
289
290 if (!bvp2 || !bvp1)
291 return NULL;
292
293 /* if they are not the same size */
294 /* make them the same size */
295 if (bvp1->size < bvp2->size)
296 bvp1 = bitVectResize (bvp1, bvp2->size);
297 else if (bvp2->size < bvp1->size)
298 bvp2 = bitVectResize (bvp2, bvp1->size);
299
300 elements = bvp1->allocSize;
301
302 p1 = bvp1->vect;
303 p2 = bvp2->vect;
304
305 while (elements--)
306 {
307 *p1 &= *p2;
308 p1++; p2++;
309 }
310
311 return bvp1;
312 }
313
314 /*-----------------------------------------------------------------*/
315 /* bitVectBitsInCommon - special case of intersection determines */
316 /* if the vectors have any common bits set */
317 /*-----------------------------------------------------------------*/
318 int
bitVectBitsInCommon(const bitVect * bvp1,const bitVect * bvp2)319 bitVectBitsInCommon (const bitVect * bvp1, const bitVect * bvp2)
320 {
321 int elements;
322 unsigned int *p1, *p2;
323
324 if (!bvp1 || !bvp2)
325 return 0;
326
327 elements = min (bvp1->allocSize, bvp2->allocSize);
328
329 p1 = bvp1->vect;
330 p2 = bvp2->vect;
331
332 while (elements--)
333 {
334 if (*p1 & *p2)
335 return 1;
336 p1++; p2++;
337 }
338
339 return 0;
340 }
341
342 /*-----------------------------------------------------------------*/
343 /* bitVectCplAnd - complement the second & and it with the first */
344 /*-----------------------------------------------------------------*/
345 bitVect *
bitVectCplAnd(bitVect * bvp1,bitVect * bvp2)346 bitVectCplAnd (bitVect * bvp1, bitVect * bvp2)
347 {
348 unsigned int *p1, *p2;
349 int elements;
350
351 if (!bvp2)
352 return bvp1;
353
354 if (!bvp1)
355 return bvp1;
356
357 /* if they are not the same size */
358 /* make them the same size */
359 if (bvp1->size < bvp2->size)
360 bvp1 = bitVectResize (bvp1, bvp2->size);
361 else if (bvp2->size < bvp1->size)
362 bvp2 = bitVectResize (bvp2, bvp1->size);
363
364 elements = bvp1->allocSize;
365 p1 = bvp1->vect;
366 p2 = bvp2->vect;
367
368 while (elements--)
369 {
370 *p1 = *p1 & ~ *p2;
371 p2++; p1++;
372 }
373
374 return bvp1;
375 }
376
377 /*-----------------------------------------------------------------*/
378 /* bitVectIsZero - bit vector has all bits turned off */
379 /*-----------------------------------------------------------------*/
380 int
bitVectIsZero(const bitVect * bvp)381 bitVectIsZero (const bitVect * bvp)
382 {
383 int i;
384
385 if (!bvp)
386 return 1;
387
388 for (i = 0; i < bvp->allocSize; i++)
389 if (bvp->vect[i] != 0)
390 return 0;
391
392 return 1;
393 }
394
395 /*-----------------------------------------------------------------*/
396 /* bitVectsEqual - returns 1 if the two bit vectors are equal */
397 /*-----------------------------------------------------------------*/
398 int
bitVectEqual(bitVect * bvp1,bitVect * bvp2)399 bitVectEqual (bitVect * bvp1, bitVect * bvp2)
400 {
401 int i;
402 int elements;
403
404 if (!bvp1 || !bvp2)
405 return 0;
406
407 if (bvp1 == bvp2)
408 return 1;
409
410 /* elements common to both allocations must match */
411 elements = min (bvp1->allocSize, bvp2->allocSize);
412 for (i = 0; i < elements; i++)
413 if (bvp1->vect[i] != bvp2->vect[i])
414 return 0;
415
416 /* any extra elements allocated must be 0 */
417 if (bvp1->allocSize > elements)
418 {
419 for (i = elements; i < bvp1->allocSize; i++)
420 if (bvp1->vect[i])
421 return 0;
422 }
423 if (bvp2->allocSize > elements)
424 {
425 for (i = elements; i < bvp2->allocSize; i++)
426 if (bvp2->vect[i])
427 return 0;
428 }
429
430 return 1;
431 }
432
433 /*-----------------------------------------------------------------*/
434 /* bitVectCopy - creates a bitvector from another bit Vector */
435 /*-----------------------------------------------------------------*/
436 bitVect *
bitVectCopy(const bitVect * bvp)437 bitVectCopy (const bitVect * bvp)
438 {
439 bitVect *newBvp;
440 int i;
441
442 if (!bvp)
443 return NULL;
444
445 newBvp = newBitVect (bvp->size);
446 for (i = 0; i < bvp->allocSize; i++)
447 newBvp->vect[i] = bvp->vect[i];
448
449 return newBvp;
450 }
451
452 /*-----------------------------------------------------------------*/
453 /* bitVectnBitsOn - returns the number of bits that are on */
454 /*-----------------------------------------------------------------*/
455 int
bitVectnBitsOn(const bitVect * bvp)456 bitVectnBitsOn (const bitVect * bvp)
457 {
458 int count = 0;
459 unsigned int *p1;
460 int elements;
461
462 if (!bvp)
463 return 0;
464
465 p1 = bvp->vect;
466 elements = bvp->allocSize;
467
468 while (elements--)
469 {
470 unsigned int word = *p1++;
471 while (word)
472 {
473 count++;
474 word &= word-1;
475 }
476 }
477
478 return count;
479 }
480
481 /*-----------------------------------------------------------------*/
482 /* bitVectFirstBit - returns the key for the first bit that is on */
483 /*-----------------------------------------------------------------*/
484 int
bitVectFirstBit(const bitVect * bvp)485 bitVectFirstBit (const bitVect * bvp)
486 {
487 int i;
488 int index;
489
490 if (!bvp)
491 return -1;
492
493 for (i = 0, index = 0; i < bvp->size; i+=BIT_SIZEOF_ELEMENT, index++)
494 if (bvp->vect[index])
495 break;
496
497 for (; i < bvp->size; i++)
498 if (bitVectBitValue (bvp, i))
499 return i;
500
501 return -1;
502 }
503
504 /*-----------------------------------------------------------------*/
505 /* bitVectClear - clear all bits */
506 /*-----------------------------------------------------------------*/
507 void
bitVectClear(bitVect * bvp)508 bitVectClear (bitVect *bvp)
509 {
510 int i;
511
512 if (!bvp)
513 return;
514
515 for (i = 0; i < bvp->allocSize; i++)
516 bvp->vect[i] = 0;
517 }
518
519 /*-----------------------------------------------------------------*/
520 /* bitVectDebugOn - prints bits that are on */
521 /*-----------------------------------------------------------------*/
522 void
bitVectDebugOn(bitVect * bvp,FILE * of)523 bitVectDebugOn (bitVect * bvp, FILE * of)
524 {
525 int i;
526
527 if (of == NULL)
528 of = stdout;
529 if (!bvp)
530 return;
531
532 fprintf (of, "bitvector Size = %d allocSize = %d\n", bvp->size, bvp->allocSize);
533 fprintf (of, "Bits on { ");
534 for (i = 0; i < bvp->size; i++)
535 {
536 if (bitVectBitValue (bvp, i))
537 fprintf (of, "(%d) ", i);
538 }
539 fprintf (of, "}\n");
540 }
541
542