1 /* set.c 2 3 The following is a general-purpose set library originally developed 4 by Hank Dietz and enhanced by Terence Parr to allow dynamic sets. 5 6 Sets are now structs containing the #words in the set and 7 a pointer to the actual set words. 8 9 Generally, sets need not be explicitly allocated. They are 10 created/extended/shrunk when appropriate (e.g. in set_of()). 11 HOWEVER, sets need to be destroyed (free()ed) when they go out of scope 12 or are otherwise no longer needed. A routine is provided to 13 free a set. 14 15 Sets can be explicitly created with set_new(s, max_elem). 16 17 Sets can be declared to have minimum size to reduce realloc traffic. 18 Default minimum size = 1. 19 20 Sets can be explicitly initialized to have no elements (set.n == 0) 21 by using the 'empty' initializer: 22 23 Examples: 24 set a = empty; -- set_deg(a) == 0 25 26 return( empty ); 27 28 Example set creation and destruction: 29 30 set 31 set_of2(e,g) 32 unsigned e,g; 33 { 34 set a,b,c; 35 36 b = set_of(e); -- Creates space for b and sticks in e 37 set_new(c, g); -- set_new(); set_orel() ==> set_of() 38 set_orel(g, &c); 39 a = set_or(b, c); 40 . 41 . 42 . 43 set_free(b); 44 set_free(c); 45 return( a ); 46 } 47 48 1987 by Hank Dietz 49 50 Modified by: 51 Terence Parr 52 Purdue University 53 October 1989 54 55 Made it smell less bad to C++ 7/31/93 -- TJP 56 */ 57 58 #include <stdio.h> 59 #include "pcctscfg.h" 60 #ifdef __STDC__ 61 #include <stdlib.h> 62 #else 63 #include <malloc.h> 64 #endif 65 #include <string.h> 66 67 #include "set.h" 68 69 #define MIN(i,j) ( (i) > (j) ? (j) : (i)) 70 #define MAX(i,j) ( (i) < (j) ? (j) : (i)) 71 72 /* elems can be a maximum of 32 bits */ 73 static unsigned bitmask[] = { 74 0x00000001, 0x00000002, 0x00000004, 0x00000008, 75 0x00000010, 0x00000020, 0x00000040, 0x00000080, 76 0x00000100, 0x00000200, 0x00000400, 0x00000800, 77 0x00001000, 0x00002000, 0x00004000, 0x00008000, 78 #if !defined(PC) || defined(PC32) 79 0x00010000, 0x00020000, 0x00040000, 0x00080000, 80 0x00100000, 0x00200000, 0x00400000, 0x00800000, 81 0x01000000, 0x02000000, 0x04000000, 0x08000000, 82 0x10000000, 0x20000000, 0x40000000, 0x80000000 83 #endif 84 }; 85 86 set empty = set_init; 87 static unsigned min=1; 88 89 #define StrSize 200 90 91 #ifdef MEMCHK 92 #define CHK(a) \ 93 if ( a.setword != NULL ) \ 94 if ( !valid(a.setword) ) \ 95 {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);} 96 #else 97 #define CHK(a) 98 #endif 99 100 /* 101 * Set the minimum size (in words) of a set to reduce realloc calls 102 */ 103 void 104 #ifdef __USE_PROTOS 105 set_size( unsigned n ) 106 #else 107 set_size( n ) 108 unsigned n; 109 #endif 110 { 111 min = n; 112 } 113 114 unsigned int 115 #ifdef __USE_PROTOS 116 set_deg( set a ) 117 #else 118 set_deg( a ) 119 set a; 120 #endif 121 { 122 /* Fast compute degree of a set... the number 123 of elements present in the set. Assumes 124 that all word bits are used in the set 125 and that SETSIZE(a) is a multiple of WORDSIZE. 126 */ 127 register unsigned *p = &(a.setword[0]); 128 register unsigned *endp = NULL; /* MR27 Avoid false memory check report */ 129 register unsigned degree = 0; 130 131 CHK(a); 132 if ( a.n == 0 ) return(0); 133 endp = &(a.setword[a.n]); 134 while ( p < endp ) 135 { 136 register unsigned t = *p; 137 register unsigned *b = &(bitmask[0]); 138 do { 139 if (t & *b) ++degree; 140 } while (++b < &(bitmask[WORDSIZE])); 141 p++; 142 } 143 144 return(degree); 145 } 146 147 set 148 #ifdef __USE_PROTOS 149 set_or( set b, set c ) 150 #else 151 set_or( b, c ) 152 set b; 153 set c; 154 #endif 155 { 156 /* Fast set union operation */ 157 /* resultant set size is max(b, c); */ 158 set *big; 159 set t; 160 unsigned int m,n; 161 register unsigned *r, *p, *q, *endp; 162 163 CHK(b); CHK(c); 164 t = empty; 165 if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;} 166 set_ext(&t, m); 167 r = t.setword; 168 169 /* Or b,c until max of smaller set */ 170 q = c.setword; 171 p = b.setword; 172 endp = &(b.setword[n]); 173 while ( p < endp ) *r++ = *p++ | *q++; 174 175 /* Copy rest of bigger set into result */ 176 p = &(big->setword[n]); 177 endp = &(big->setword[m]); 178 while ( p < endp ) *r++ = *p++; 179 180 return(t); 181 } 182 183 set 184 #ifdef __USE_PROTOS 185 set_and( set b, set c ) 186 #else 187 set_and( b, c ) 188 set b; 189 set c; 190 #endif 191 { 192 /* Fast set intersection operation */ 193 /* resultant set size is min(b, c); */ 194 set t; 195 unsigned int n; 196 register unsigned *r, *p, *q, *endp; 197 198 CHK(b); CHK(c); 199 t = empty; 200 n = (b.n > c.n) ? c.n : b.n; 201 if ( n == 0 ) return t; /* TJP 4-27-92 fixed for empty set */ 202 set_ext(&t, n); 203 r = t.setword; 204 205 /* & b,c until max of smaller set */ 206 q = c.setword; 207 p = b.setword; 208 endp = &(b.setword[n]); 209 while ( p < endp ) *r++ = *p++ & *q++; 210 211 return(t); 212 } 213 214 set 215 #ifdef __USE_PROTOS 216 set_dif( set b, set c ) 217 #else 218 set_dif( b, c ) 219 set b; 220 set c; 221 #endif 222 { 223 /* Fast set difference operation b - c */ 224 /* resultant set size is size(b) */ 225 set t; 226 unsigned int n; 227 register unsigned *r, *p, *q, *endp; 228 229 CHK(b); CHK(c); 230 t = empty; 231 n = (b.n <= c.n) ? b.n : c.n ; 232 if ( b.n == 0 ) return t; /* TJP 4-27-92 fixed for empty set */ 233 /* WEC 12-1-92 fixed for c.n = 0 */ 234 set_ext(&t, b.n); 235 r = t.setword; 236 237 /* Dif b,c until smaller set size */ 238 q = c.setword; 239 p = b.setword; 240 endp = &(b.setword[n]); 241 while ( p < endp ) *r++ = *p++ & (~ *q++); 242 243 /* Copy rest of b into result if size(b) > c */ 244 if ( b.n > n ) 245 { 246 p = &(b.setword[n]); 247 endp = &(b.setword[b.n]); 248 while ( p < endp ) *r++ = *p++; 249 } 250 251 return(t); 252 } 253 254 set 255 #ifdef __USE_PROTOS 256 set_of( unsigned b ) 257 #else 258 set_of( b ) 259 unsigned b; 260 #endif 261 { 262 /* Fast singleton set constructor operation */ 263 static set a; 264 265 if ( b == nil ) return( empty ); 266 set_new(a, b); 267 a.setword[DIVWORD(b)] = bitmask[MODWORD(b)]; 268 269 return(a); 270 } 271 272 /* 273 * Extend (or shrink) the set passed in to have n words. 274 * 275 * if n is smaller than the minimum, boost n to have the minimum. 276 * if the new set size is the same as the old one, do nothing. 277 * 278 * TJP 4-27-92 Fixed so won't try to alloc 0 bytes 279 */ 280 void 281 #ifdef __USE_PROTOS 282 set_ext( set *a, unsigned int n ) 283 #else 284 set_ext( a, n ) 285 set *a; 286 unsigned int n; 287 #endif 288 { 289 register unsigned *p; 290 register unsigned *endp; 291 unsigned int size; 292 293 CHK((*a)); 294 if ( a->n == 0 ) 295 { 296 if ( n == 0 ) return; 297 if (a->setword != NULL) { 298 free (a->setword); /* MR20 */ 299 } 300 a->setword = (unsigned *) calloc(n, BytesPerWord); 301 if ( a->setword == NULL ) 302 { 303 fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n); 304 exit(-1); 305 } 306 a->n = n; 307 return; 308 } 309 if ( n < min ) n = min; 310 if ( a->n == n || n == 0 ) return; 311 size = a->n; 312 a->n = n; 313 a->setword = (unsigned *) realloc( (char *)a->setword, (n*BytesPerWord) ); 314 if ( a->setword == NULL ) 315 { 316 fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n); 317 exit(-1); 318 } 319 320 p = &(a->setword[size]); /* clear from old size to new size */ 321 endp = &(a->setword[a->n]); 322 do { 323 *p++ = 0; 324 } while ( p < endp ); 325 } 326 327 set 328 #ifdef __USE_PROTOS 329 set_not( set a ) 330 #else 331 set_not( a ) 332 set a; 333 #endif 334 { 335 /* Fast not of set a (assumes all bits used) */ 336 /* size of resultant set is size(a) */ 337 /* ~empty = empty cause we don't know how bit to make set */ 338 set t; 339 register unsigned *r; 340 register unsigned *p = a.setword; 341 register unsigned *endp = &(a.setword[a.n]); 342 343 CHK(a); 344 t = empty; 345 if ( a.n == 0 ) return( empty ); 346 set_ext(&t, a.n); 347 r = t.setword; 348 349 do { 350 *r++ = (~ *p++); 351 } while ( p < endp ); 352 353 return(t); 354 } 355 356 int 357 #ifdef __USE_PROTOS 358 set_equ( set a, set b ) 359 #else 360 set_equ( a, b ) 361 set a; 362 set b; 363 #endif 364 { 365 /* 8-Nov-97 Make it work with sets of different sizes */ 366 /* Easy to understand, too. Probably faster. */ 367 /* Check for a equal to b */ 368 369 unsigned int count; /* MR11 */ 370 unsigned int i; /* MR11 */ 371 372 CHK(a); CHK(b); 373 374 count=MIN(a.n,b.n); 375 if (count == 0) return 1; 376 for (i=0; i < count; i++) { 377 if (a.setword[i] != b.setword[i]) return 0; 378 }; 379 if (a.n < b.n) { 380 for (i=count; i < b.n; i++) { 381 if (b.setword[i] != 0) return 0; 382 } 383 return 1; 384 } else if (a.n > b.n) { 385 for (i=count; i < a.n; i++) { 386 if (a.setword[i] != 0) return 0; 387 } 388 return 1; 389 } else { 390 return 1; 391 }; 392 } 393 394 int 395 #ifdef __USE_PROTOS 396 set_sub( set a, set b ) 397 #else 398 set_sub( a, b ) 399 set a; 400 set b; 401 #endif 402 { 403 404 /* 8-Nov-97 Make it work with sets of different sizes */ 405 /* Easy to understand, too. Probably faster. */ 406 /* Check for a is a PROPER subset of b */ 407 408 unsigned int count; 409 unsigned int i; 410 411 CHK(a); CHK(b); 412 413 if (a.n == 0) return 1; 414 count=MIN(a.n,b.n); 415 for (i=0; i < count; i++) { 416 if (a.setword[i] & ~b.setword[i]) return 0; 417 }; 418 if (a.n <= b.n) { 419 return 1; 420 } else { 421 for (i=count; i<a.n ; i++) { 422 if (a.setword[i]) return 0; 423 }; 424 }; 425 return 1; 426 } 427 428 unsigned 429 #ifdef __USE_PROTOS 430 set_int( set b ) 431 #else 432 set_int( b ) 433 set b; 434 #endif 435 { 436 /* Fast pick any element of the set b */ 437 register unsigned *p = b.setword; 438 register unsigned *endp = &(b.setword[b.n]); 439 440 CHK(b); 441 if ( b.n == 0 ) return( nil ); 442 443 do { 444 if (*p) { 445 /* Found a non-empty word of the set */ 446 register unsigned i = ((p - b.setword) << LogWordSize); 447 register unsigned t = *p; 448 p = &(bitmask[0]); 449 while (!(*p & t)) { 450 ++i; ++p; 451 } 452 return(i); 453 } 454 } while (++p < endp); 455 456 /* Empty -- only element it contains is nil */ 457 return(nil); 458 } 459 460 int 461 #ifdef __USE_PROTOS 462 set_el( unsigned b, set a ) 463 #else 464 set_el( b, a ) 465 unsigned b; 466 set a; 467 #endif 468 { 469 CHK(a); 470 /* nil is an element of every set */ 471 if (b == nil) return(1); 472 if ( a.n == 0 || NumWords(b) > a.n ) return(0); 473 474 /* Otherwise, we have to check */ 475 return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] ); 476 } 477 478 int 479 #ifdef __USE_PROTOS 480 set_nil( set a ) 481 #else 482 set_nil( a ) 483 set a; 484 #endif 485 { 486 /* Fast check for nil set */ 487 register unsigned *p = a.setword; 488 register unsigned *endp; 489 490 CHK(a); 491 if ( a.n == 0 ) return(1); 492 endp = &(a.setword[a.n]); 493 494 /* The set is not empty if any word used to store 495 the set is non-zero. This means one must be a 496 bit careful about doing things like negation. 497 */ 498 do { 499 if (*p) return(0); 500 } while (++p < endp); 501 502 return(1); 503 } 504 505 char * 506 #ifdef __USE_PROTOS 507 set_str( set a ) 508 #else 509 set_str( a ) 510 set a; 511 #endif 512 { 513 /* Fast convert set a into ASCII char string... 514 assumes that all word bits are used in the set 515 and that SETSIZE is a multiple of WORDSIZE. 516 Trailing 0 bits are removed from the string. 517 if no bits are on or set is empty, "" is returned. 518 */ 519 register unsigned *p = a.setword; 520 register unsigned *endp = &(a.setword[a.n]); 521 static char str_tmp[StrSize+1]; 522 register char *q = &(str_tmp[0]); 523 524 CHK(a); 525 if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );} 526 do { 527 register unsigned t = *p; 528 register unsigned *b = &(bitmask[0]); 529 do { 530 *(q++) = (char) ((t & *b) ? '1' : '0'); 531 } while (++b < &(bitmask[WORDSIZE])); 532 } while (++p < endp); 533 534 /* Trim trailing 0s & NULL terminate the string */ 535 while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q; 536 *q = 0; 537 538 return(&(str_tmp[0])); 539 } 540 541 set 542 #ifdef __USE_PROTOS 543 set_val( register char *s ) 544 #else 545 set_val( s ) 546 register char *s; 547 #endif 548 { 549 /* Fast convert set ASCII char string into a set. 550 If the string ends early, the remaining set bits 551 are all made zero. 552 The resulting set size is just big enough to hold all elements. 553 */ 554 static set a; 555 register unsigned *p, *endp; 556 557 set_new(a, (unsigned) strlen(s)); 558 p = a.setword; 559 endp = &(a.setword[a.n]); 560 do { 561 register unsigned *b = &(bitmask[0]); 562 /* Start with a word with no bits on */ 563 *p = 0; 564 do { 565 if (*s) { 566 if (*s == '1') { 567 /* Turn-on this bit */ 568 *p |= *b; 569 } 570 ++s; 571 } 572 } while (++b < &(bitmask[WORDSIZE])); 573 } while (++p < endp); 574 575 return(a); 576 } 577 578 /* 579 * Or element e into set a. a can be empty. 580 */ 581 void 582 #ifdef __USE_PROTOS 583 set_orel( unsigned e, set *a ) 584 #else 585 set_orel( e, a ) 586 unsigned e; 587 set *a; 588 #endif 589 { 590 CHK((*a)); 591 if ( e == nil ) return; 592 if ( NumWords(e) > a->n ) set_ext(a, NumWords(e)); 593 a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)]; 594 } 595 596 /* 597 * Or set b into set a. a can be empty. does nothing if b empty. 598 */ 599 void 600 #ifdef __USE_PROTOS 601 set_orin( set *a, set b ) 602 #else 603 set_orin( a, b ) 604 set *a; 605 set b; 606 #endif 607 { 608 /* Fast set union operation */ 609 /* size(a) is max(a, b); */ 610 unsigned int m; 611 register unsigned *p, 612 *q = b.setword, 613 *endq; /* MR20 */ 614 615 CHK((*a)); CHK(b); 616 if ( b.n == 0 ) return; 617 endq = &(b.setword[b.n]); /* MR20 */ 618 m = (a->n > b.n) ? a->n : b.n; 619 set_ext(a, m); 620 p = a->setword; 621 do { 622 *p++ |= *q++; 623 } while ( q < endq ); 624 } 625 626 /* 627 * And set b into set a. a can be empty. does nothing if b empty. 628 */ 629 void 630 #ifdef __USE_PROTOS 631 set_andin( set *a, set b ) 632 #else 633 set_andin( a, b ) 634 set *a; 635 set b; 636 #endif 637 { 638 /* Fast set intersection operation */ 639 /* size(a) is max(a, b); */ 640 unsigned int m; 641 register unsigned *p, 642 *q = b.setword, 643 *endq = &(b.setword[b.n]); 644 645 CHK((*a)); CHK(b); 646 if ( b.n == 0 ) return; 647 m = (a->n > b.n) ? a->n : b.n; 648 set_ext(a, m); 649 p = a->setword; 650 do { 651 *p++ &= *q++; 652 } while ( q < endq ); 653 } 654 655 void 656 #ifdef __USE_PROTOS 657 set_rm( unsigned e, set a ) 658 #else 659 set_rm( e, a ) 660 unsigned e; 661 set a; 662 #endif 663 { 664 /* Does not effect size of set */ 665 CHK(a); 666 if ( (e == nil) || (NumWords(e) > a.n) ) return; 667 a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]); 668 } 669 670 void 671 #ifdef __USE_PROTOS 672 set_clr( set a ) 673 #else 674 set_clr( a ) 675 set a; 676 #endif 677 { 678 /* Does not effect size of set */ 679 register unsigned *p = a.setword; 680 register unsigned *endp; 681 682 CHK(a); 683 if ( a.n == 0 ) return; 684 endp = &(a.setword[a.n]); 685 do { 686 *p++ = 0; 687 } while ( p < endp ); 688 } 689 690 set 691 #ifdef __USE_PROTOS 692 set_dup( set a ) 693 #else 694 set_dup( a ) 695 set a; 696 #endif 697 { 698 set b; 699 register unsigned *p, 700 *q = a.setword, 701 *endq; /* MR20 */ 702 703 CHK(a); 704 b = empty; 705 if ( a.n == 0 ) return( empty ); 706 endq = &(a.setword[a.n]); /* MR20 */ 707 set_ext(&b, a.n); 708 p = b.setword; 709 do { 710 *p++ = *q++; 711 } while ( q < endq ); 712 713 return(b); 714 } 715 716 /* 717 * Return a nil terminated list of unsigned ints that represents all 718 * "on" bits in the bit set. 719 * 720 * e.g. {011011} --> {1, 2, 4, 5, nil} 721 * 722 * _set_pdq and set_pdq are useful when an operation is required on each element 723 * of a set. Normally, the sequence is: 724 * 725 * while ( set_deg(a) > 0 ) { 726 * e = set_int(a); 727 * set_rm(e, a); 728 * ...process e... 729 * } 730 * Now, 731 * 732 * t = e = set_pdq(a); 733 * while ( *e != nil ) { 734 * ...process *e... 735 * e++; 736 * } 737 * free( t ); 738 * 739 * We have saved many set calls and have not destroyed set a. 740 */ 741 void 742 #ifdef __USE_PROTOS 743 _set_pdq( set a, register unsigned *q ) 744 #else 745 _set_pdq( a, q ) 746 set a; 747 register unsigned *q; 748 #endif 749 { 750 register unsigned *p = a.setword, 751 *endp = &(a.setword[a.n]); 752 register unsigned e=0; 753 754 CHK(a); 755 /* are there any space (possibility of elements)? */ 756 if ( a.n == 0 ) return; 757 do { 758 register unsigned t = *p; 759 register unsigned *b = &(bitmask[0]); 760 do { 761 if ( t & *b ) *q++ = e; 762 ++e; 763 } while (++b < &(bitmask[WORDSIZE])); 764 } while (++p < endp); 765 *q = nil; 766 } 767 768 /* 769 * Same as _set_pdq except allocate memory. set_pdq is the natural function 770 * to use. 771 */ 772 unsigned * 773 #ifdef __USE_PROTOS 774 set_pdq( set a ) 775 #else 776 set_pdq( a ) 777 set a; 778 #endif 779 { 780 unsigned *q; 781 int max_deg; 782 783 CHK(a); 784 max_deg = WORDSIZE*a.n; 785 /* assume a.n!=0 & no elements is rare, but still ok */ 786 if ( a.n == 0 ) return(NULL); 787 q = (unsigned *) malloc((max_deg+1)*BytesPerWord); 788 if ( q == NULL ) return( NULL ); 789 _set_pdq(a, q); 790 return( q ); 791 } 792 793 /* a function that produces a hash number for the set 794 */ 795 unsigned int 796 #ifdef __USE_PROTOS 797 set_hash( set a, register unsigned int mod ) 798 #else 799 set_hash( a, mod ) 800 set a; 801 register unsigned int mod; 802 #endif 803 { 804 /* Fast hash of set a (assumes all bits used) */ 805 register unsigned *p = &(a.setword[0]); 806 register unsigned *endp = &(a.setword[a.n]); 807 register unsigned i = 0; 808 809 CHK(a); 810 while (p<endp){ 811 i += (*p); 812 ++p; 813 } 814 815 return(i % mod); 816 } 817
