1: /*_ vec.c   Mon Oct 31 1994 */
  2: /* Copyright (C) 1986-2000 by Digital Mars              */
  3: /* Written by Walter Bright                             */
  4: /* Bit vector package                                   */
  5: 
  6: #include        <stdio.h>
  7: #include        <string.h>
  8: #ifndef assert
  9: #include        <assert.h>
 10: #endif
 11: #include        "vec.h"
 12: #include        "mem.h"
 13: 
 14: static int vec_count;           /* # of vectors allocated               */
 15: static int vec_initcount = 0;   /* # of times package is initialized    */
 16: 
 17: #define VECMAX  20
 18: static vec_t vecfreelist[VECMAX];
 19: 
 20: #if 1
 21: #define MASK(b)         (1 << ((b) & VECMASK))
 22: #else
 23: #define MASK(b)         bmask[(b) & VECMASK]
 24: static unsigned bmask[VECMASK + 1] =
 25: {
 26:         1,2,4,8,0x10,0x20,0x40,0x80,
 27:         0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,
 28: #if __INTSIZE == 4
 29:         0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
 30:         0x1000000,0x2000000,0x4000000,0x8000000,
 31:         0x10000000,0x20000000,0x40000000,0x80000000
 32: #endif
 33: };
 34: #endif
 35: 
 36: /**************************
 37:  * Initialize package.
 38:  */
 39: 
 40: void vec_init()
 41: {
 42:     assert(sizeof(vec_base_t)==2&&VECSHIFT==4||sizeof(vec_base_t)==4&&VECSHIFT== 5);
 43:     if (vec_initcount++ == 0)
 44:             vec_count = 0;
 45: }
 46: 
 47: /**************************
 48:  * Terminate package.
 49:  */
 50: 
 51: void vec_term()
 52: {
 53:     if (--vec_initcount == 0)
 54:     {
 55: 
 56: #ifdef DEBUG
 57:         if (vec_count != 0)
 58:         {
 59:                 printf("vec_count = %d\n",vec_count);
 60:                 assert(0);
 61:         }
 62: #else
 63:         assert(vec_count == 0);
 64: #endif
 65: #if TERMCODE
 66:         int i;
 67:         for (i = 0; i < VECMAX; i++)
 68:         {   void **v;
 69:             void **vn;
 70: 
 71:             for (v = (void **)vecfreelist[i]; v; v = vn)
 72:             {
 73:                 vn = (void **)(*v);
 74:                 mem_free(v);
 75:             }
 76:             vecfreelist[i] = NULL;
 77:         }
 78: #endif
 79:     }
 80: }
 81: 
 82: /********************************
 83:  * Allocate a vector given # of bits in it.
 84:  * Clear the vector.
 85:  */
 86: 
 87: vec_t vec_calloc(unsigned numbits)
 88: { vec_t v;
 89:   int dim;
 90: 
 91:   if (numbits == 0)
 92:         return (vec_t) NULL;
 93:   dim = (numbits + (VECBITS - 1)) >> VECSHIFT;
 94:   if (dim < VECMAX && (v = vecfreelist[dim]) != NULL)
 95:   {
 96:         vecfreelist[dim] = *(vec_t *)v;
 97:         v += 2;
 98:         switch (dim)
 99:         {
100:             case 5:     v[4] = 0;
101:             case 4:     v[3] = 0;
102:             case 3:     v[2] = 0;
103:             case 2:     v[1] = 0;
104:             case 1:     v[0] = 0;
105:                         break;
106:             default:    memset(v,0,dim * sizeof(vec_base_t));
107:                         break;
108:         }
109:         goto L1;
110:   }
111:   else
112:   {
113:         v = (vec_t) mem_calloc((dim + 2) * sizeof(vec_base_t));
114:   }
115:   if (v)
116:   {
117:         v += 2;
118:     L1:
119:         vec_dim(v) = dim;
120:         vec_numbits(v) = numbits;
121:         /*printf("vec_calloc(%d): v = %p vec_numbits = %d vec_dim = %d\n",
122:             numbits,v,vec_numbits(v),vec_dim(v));*/
123:         vec_count++;
124:   }
125:   return v;
126: }
127: 
128: /********************************
129:  * Allocate copy of existing vector.
130:  */
131: 
132: vec_t vec_clone(vec_t v)
133: {   vec_t vc;
134:     int dim;
135:     unsigned nbytes;
136: 
137:     if (v)
138:     {   dim = vec_dim(v);
139:         nbytes = (dim + 2) * sizeof(vec_base_t);
140:         if (dim < VECMAX && (vc = vecfreelist[dim]) != NULL)
141:         {
142:             vecfreelist[dim] = *(vec_t *)vc;
143:             goto L1;
144:         }
145:         else
146:         {
147:             vc = (vec_t) mem_calloc(nbytes);
148:         }
149:         if (vc)
150:         {
151:           L1:
152:             memcpy(vc,v - 2,nbytes);
153:             vec_count++;
154:             v = vc + 2;
155:         }
156:         else
157:             v = NULL;
158:     }
159:     return v;
160: }
161: 
162: /**************************
163:  * Free a vector.
164:  */
165: 
166: void vec_free(vec_t v)
167: {
168:     /*printf("vec_free(%p)\n",v);*/
169:     if (v)
170:     {   int dim = vec_dim(v);
171: 
172:         v -= 2;
173:         if (dim < VECMAX)
174:         {
175:             *(vec_t *)v = vecfreelist[dim];
176:             vecfreelist[dim] = v;
177:         }
178:         else
179:             mem_free(v);
180:         vec_count--;
181:     }
182: }
183: 
184: /**************************
185:  * Realloc a vector to have numbits bits in it.
186:  * Extra bits are set to 0.
187:  */
188: 
189: vec_t vec_realloc(vec_t v,unsigned numbits)
190: {       vec_t newv;
191:         unsigned vbits;
192: 
193:         /*printf("vec_realloc(%p,%d)\n",v,numbits);*/
194:         if (!v)
195:             return vec_calloc(numbits);
196:         if (!numbits)
197:         {   vec_free(v);
198:             return NULL;
199:         }
200:         vbits = vec_numbits(v);
201:         if (numbits == vbits)
202:             return v;
203:         newv = vec_calloc(numbits);
204:         if (newv)
205:         {   unsigned nbytes;
206: 
207:             nbytes = (vec_dim(v) < vec_dim(newv)) ? vec_dim(v) : vec_dim(newv);
208:             memcpy(newv,v,nbytes * sizeof(vec_base_t));
209:             vec_clearextrabits(newv);
210:         }
211:         vec_free(v);
212:         return newv;
213: }
214: 
215: /**************************
216:  * Set bit b in vector v.
217:  */
218: 
219: #ifndef vec_setbit
220: 
221: #if _M_I86 && __INTSIZE == 4 && __SC__
222: __declspec(naked) void __pascal vec_setbit(unsigned b,vec_t v)
223: {
224:     _asm
225:     {
226:         mov     EAX,b-4[ESP]
227:         mov     ECX,v-4[ESP]
228:         bts     [ECX],EAX
229:         ret     8
230:     }
231: }
232: #else
233: void vec_setbit(unsigned b,vec_t v)
234: {
235: #ifdef DEBUG
236:   if (!(v && b < vec_numbits(v)))
237:         printf("vec_setbit(v = %p,b = %d): numbits = %d dim = %d\n",
238:             v,b,v ? vec_numbits(v) : 0, v ? vec_dim(v) : 0);
239: #endif
240:   assert(v && b < vec_numbits(v));
241:   *(v + (b >> VECSHIFT)) |= MASK(b);
242: }
243: #endif
244: 
245: #endif
246: 
247: /**************************
248:  * Clear bit b in vector v.
249:  */
250: 
251: #ifndef vec_clearbit
252: 
253: #if _M_I86 && __INTSIZE == 4 && __SC__
254: __declspec(naked) void __pascal vec_clearbit(unsigned b,vec_t v)
255: {
256:     _asm
257:     {
258:         mov     EAX,b-4[ESP]
259:         mov     ECX,v-4[ESP]
260:         btr     [ECX],EAX
261:         ret     8
262:     }
263: }
264: #else
265: void vec_clearbit(unsigned b,vec_t v)
266: {
267:   assert(v && b < vec_numbits(v));
268:   *(v + (b >> VECSHIFT)) &= ~MASK(b);
269: }
270: #endif
271: 
272: #endif
273: 
274: /**************************
275:  * Test bit b in vector v.
276:  */
277: 
278: #ifndef vec_testbit
279: 
280: #if _M_I86 && __INTSIZE == 4 && __SC__
281: __declspec(naked) int __pascal vec_testbit(unsigned b,vec_t v)
282: {
283:     _asm
284:     {
285:         mov     EAX,v-4[ESP]
286:         mov     ECX,b-4[ESP]
287:         test    EAX,EAX
288:         jz      L1
289:         bt      [EAX],ECX
290:         sbb     EAX,EAX
291:     L1: ret     8
292:     }
293: }
294: #else
295: int vec_testbit(unsigned b,vec_t v)
296: {
297:   if (!v)
298:         return 0;
299: #ifdef DEBUG
300:   if (b >= vec_numbits(v))
301:   {     printf("vec_testbit(v = %p,b = %d): numbits = %d dim = %d\n",
302:             v,b,vec_numbits(v),vec_dim(v));
303:         b = (unsigned)-1;
304:   }
305: #endif
306:   assert(b < vec_numbits(v));
307: #if __I86__ >= 3 && __SC__
308:   _asm
309:   {
310: #if __INTSIZE == 4
311:         mov     EAX,b
312:         mov     ECX,v
313:         bt      [ECX],EAX
314:         sbb     EAX,EAX
315: #elif __COMPACT__ || __LARGE__ || __VCM__
316:         mov     AX,b
317:         les     BX,v
318:         bt      ES:[BX],AX
319:         sbb     AX,AX
320: #else
321:         mov     AX,b
322:         mov     CX,v
323:         bt      [CX],AX
324:         sbb     AX,AX
325: #endif
326:   }
327: #ifdef DEBUG
328:   {     int x = _AX;
329:         assert((x != 0) == ((*(v + (b >> VECSHIFT)) & MASK(b)) != 0));
330:   }
331: #endif
332: #else
333:   return *(v + (b >> VECSHIFT)) & MASK(b);
334: #endif
335: }
336: #endif
337: 
338: #endif
339: 
340: /********************************
341:  * Find first set bit starting from b in vector v.
342:  * If no bit is found, return vec_numbits(v).
343:  */
344: 
345: unsigned vec_index(unsigned b,vec_t vec)
346: {       register unsigned starv;
347:         register vec_t v,vtop;
348:         unsigned bit;
349: 
350:     if (!vec)
351:         return 0;
352:     v = vec;
353:     if (b < vec_numbits(v))
354:     {   vtop = &vec[vec_dim(v)];
355:         bit = b & VECMASK;
356:         if (bit != b)                   /* if not starting in first word */
357:                 v += b >> VECSHIFT;
358:         starv = *v >> bit;
359:         while (1)
360:         {
361:                 while (starv)
362:                 {       if (starv & 1)
363:                                 return b;
364:                         b++;
365:                         starv >>= 1;
366:                 }
367:                 b = (b + VECBITS) & ~VECMASK;   /* round up to next word */
368:                 if (++v >= vtop)
369:                     break;
370:                 starv = *v;
371:         }
372:     }
373:     return vec_numbits(vec);
374: }
375: 
376: /********************************
377:  * Compute v1 &= v2.
378:  */
379: 
380: void vec_andass(vec_t v1,vec_t v2)
381: {   vec_t vtop;
382: 
383:     if (v1)
384:     {
385:         assert(v2);
386:         assert(vec_numbits(v1)==vec_numbits(v2));
387:         vtop = &v1[vec_dim(v1)];
388:         for (; v1 < vtop; v1++,v2++)
389:             *v1 &= *v2;
390:     }
391:     else
392:         assert(!v2);
393: }
394: 
395: /********************************
396:  * Compute v1 = v2 & v3.
397:  */
398: 
399: void vec_and(vec_t v1,vec_t v2,vec_t v3)
400: {   vec_t vtop;
401: 
402:     if (v1)
403:     {
404:         assert(v2 && v3);
405:         assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
406:         vtop = &v1[vec_dim(v1)];
407:         for (; v1 < vtop; v1++,v2++,v3++)
408:             *v1 = *v2 & *v3;
409:     }
410:     else
411:         assert(!v2 && !v3);
412: }
413: 
414: /********************************
415:  * Compute v1 ^= v2.
416:  */
417: 
418: void vec_xorass(vec_t v1,vec_t v2)
419: {   vec_t vtop;
420: 
421:     if (v1)
422:     {
423:         assert(v2);
424:         assert(vec_numbits(v1)==vec_numbits(v2));
425:         vtop = &v1[vec_dim(v1)];
426:         for (; v1 < vtop; v1++,v2++)
427:             *v1 ^= *v2;
428:     }
429:     else
430:         assert(!v2);
431: }
432: 
433: /********************************
434:  * Compute v1 = v2 ^ v3.
435:  */
436: 
437: void vec_xor(vec_t v1,vec_t v2,vec_t v3)
438: {   vec_t vtop;
439: 
440:     if (v1)
441:     {
442:         assert(v2 && v3);
443:         assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3));
444:         vtop = &v1[vec_dim(v1)];
445:         for (; v1 < vtop; v1++,v2++,v3++)
446:             *v1 = *v2 ^ *v3;
447:     }
448:     else
449:         assert(!v2 && !v3);
450: }
451: 
452: /********************************
453:  * Compute v1 |= v2.
454:  */
455: 
456: void vec_orass(vec_t v1,vec_t v2)
457: {   vec_t vtop;
458: 
459:     if (v1)
460:     {
461: #ifdef DEBUG
462:         assert(v2);
463:         assert(vec_numbits(v1)==vec_numbits(v2));
464: #endif
465:         vtop = &v1[vec_dim(v1)];
466: #if __INTSIZE == 2 && __I86__ && (__COMPACT__ || __LARGE__ || __VCM__)
467:         _asm
468:         {
469:                 push    DS
470:                 lds     SI,v2
471:                 les     DI,v1
472:                 mov     CX,word ptr vtop
473:                 cmp     CX,DI
474:                 jz      L1
475:             L2: mov     AX,[SI]
476:                 add     SI,2
477:                 or      ES:[DI],AX
478:                 add     DI,2
479:                 cmp     DI,CX
480:                 jb      L2
481:             L1: pop     DS
482:         #if __SC__ <= 0x610
483:                 jmp     Lret
484:         #endif
485:         }
486: #else
487:         for (; v1 < vtop; v1++,v2++)
488:             *v1 |= *v2;
489: #endif
490:     }
491:     else
492:         assert(!v2);
493: Lret: ;
warning C4102: 'Lret' : unreferenced label
494: } 495: 496: /******************************** 497: * Compute v1 = v2 | v3. 498: */ 499: 500: void vec_or(vec_t v1,vec_t v2,vec_t v3) 501: { vec_t vtop; 502: 503: if (v1) 504: { 505: assert(v2 && v3); 506: assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 507: vtop = &v1[vec_dim(v1)]; 508: for (; v1 < vtop; v1++,v2++,v3++) 509: *v1 = *v2 | *v3; 510: } 511: else 512: assert(!v2 && !v3); 513: } 514: 515: /******************************** 516: * Compute v1 -= v2. 517: */ 518: 519: void vec_subass(vec_t v1,vec_t v2) 520: { vec_t vtop; 521: 522: if (v1) 523: { 524: assert(v2); 525: assert(vec_numbits(v1)==vec_numbits(v2)); 526: vtop = &v1[vec_dim(v1)]; 527: for (; v1 < vtop; v1++,v2++) 528: *v1 &= ~*v2; 529: } 530: else 531: assert(!v2); 532: } 533: 534: /******************************** 535: * Compute v1 = v2 - v3. 536: */ 537: 538: void vec_sub(vec_t v1,vec_t v2,vec_t v3) 539: { vec_t vtop; 540: 541: if (v1) 542: { 543: assert(v2 && v3); 544: assert(vec_numbits(v1)==vec_numbits(v2) && vec_numbits(v1)==vec_numbits(v3)); 545: vtop = &v1[vec_dim(v1)]; 546: for (; v1 < vtop; v1++,v2++,v3++) 547: *v1 = *v2 & ~*v3; 548: } 549: else 550: assert(!v2 && !v3); 551: } 552: 553: /**************** 554: * Clear vector. 555: */ 556: 557: void vec_clear(vec_t v) 558: { 559: if (v) 560: memset(v,0,sizeof(v[0]) * vec_dim(v)); 561: } 562: 563: /**************** 564: * Set vector. 565: */ 566: 567: void vec_set(vec_t v) 568: { 569: if (v) 570: { memset(v,~0,sizeof(v[0]) * vec_dim(v)); 571: vec_clearextrabits(v); 572: } 573: } 574: 575: /*************** 576: * Copy vector. 577: */ 578: 579: void vec_copy(vec_t to,vec_t from) 580: { 581: if (to != from) 582: { 583: #ifdef DEBUG 584: if (!(to && from && vec_numbits(to) == vec_numbits(from))) 585: printf("to = x%lx, from = x%lx, numbits(to) = %d, numbits(from) = %d\n", 586: (long)to,(long)from,to ? vec_numbits(to) : 0, from ? vec_numbits(from): 0); 587: #endif 588: assert(to && from && vec_numbits(to) == vec_numbits(from)); 589: memcpy(to,from,sizeof(to[0]) * vec_dim(to)); 590: } 591: } 592: 593: /**************** 594: * Return 1 if vectors are equal. 595: */ 596: 597: int vec_equal(vec_t v1,vec_t v2) 598: { 599: if (v1 == v2) 600: return 1; 601: assert(v1 && v2 && vec_numbits(v1) == vec_numbits(v2)); 602: return !memcmp(v1,v2,sizeof(v1[0]) * vec_dim(v1)); 603: } 604: 605: /******************************** 606: * Return 1 if (v1 & v2) == 0 607: */ 608: 609: int vec_disjoint(vec_t v1,vec_t v2) 610: { vec_t vtop; 611: 612: assert(v1 && v2); 613: assert(vec_numbits(v1)==vec_numbits(v2)); 614: vtop = &v1[vec_dim(v1)]; 615: for (; v1 < vtop; v1++,v2++) 616: if (*v1 & *v2) 617: return 0; 618: return 1; 619: } 620: 621: /********************* 622: * Clear any extra bits in vector. 623: */ 624: 625: void vec_clearextrabits(vec_t v) 626: { unsigned n; 627: 628: assert(v); 629: n = vec_numbits(v); 630: if (n & VECMASK) 631: v[vec_dim(v) - 1] &= MASK(n) - 1; 632: } 633: 634: /****************** 635: * Write out vector. 636: */ 637: 638: void vec_println(vec_t v) 639: { 640: #ifdef DEBUG 641: vec_print(v); 642: fputc('\n',stdout); 643: #endif 644: } 645: 646: void vec_print(vec_t v) 647: { register unsigned i;
warning C4101: 'i' : unreferenced local variable
648: 649: #ifdef DEBUG 650: printf(" Vec %p, numbits %d dim %d",v,vec_numbits(v),vec_dim(v)); 651: if (v) 652: { fputc('\t',stdout); 653: for (i = 0; i < vec_numbits(v); i++) 654: fputc((vec_testbit(i,v)) ? '1' : '0',stdout); 655: } 656: #endif 657: } 658: