pd.if.org Git - pccts/blob - support/set/set.c

   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 #ifdef __cplusplus
  60 #ifndef __STDC__
  61 #define __STDC__
  62 #endif
  63 #endif
  64 #ifdef __STDC__
  65 #include <stdlib.h>
  66 #else
  67 #include <malloc.h>
  68 #endif
  69 #include <string.h>
  70
  71 #include "set.h"
  72
  73 /* elems can be a maximum of 32 bits */
  74 static unsigned bitmask[] = {
  75         0x00000001, 0x00000002, 0x00000004, 0x00000008,
  76         0x00000010, 0x00000020, 0x00000040, 0x00000080,
  77         0x00000100, 0x00000200, 0x00000400, 0x00000800,
  78         0x00001000, 0x00002000, 0x00004000, 0x00008000,
  79 #if !defined(PC) || defined(PC32)
  80         0x00010000, 0x00020000, 0x00040000, 0x00080000,
  81         0x00100000, 0x00200000, 0x00400000, 0x00800000,
  82         0x01000000, 0x02000000, 0x04000000, 0x08000000,
  83         0x10000000, 0x20000000, 0x40000000, 0x80000000
  84 #endif
  85 };
  86
  87 set empty = set_init;
  88 static unsigned min=1;
  89
  90 #define StrSize         200
  91
  92 #ifdef MEMCHK
  93 #define CHK(a)                                  \
  94         if ( a.setword != NULL )        \
  95           if ( !valid(a.setword) )      \
  96                 {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
  97 #else
  98 #define CHK(a)
  99 #endif
 100
 101 /*
 102  * Set the minimum size (in words) of a set to reduce realloc calls
 103  */
 104 void
 105 #ifdef __STDC__
 106 set_size( unsigned n )
 107 #else
 108 set_size( n )
 109 unsigned n;
 110 #endif
 111 {
 112         min = n;
 113 }
 114
 115 unsigned int
 116 #ifdef __STDC__
 117 set_deg( set a )
 118 #else
 119 set_deg( a )
 120 set a;
 121 #endif
 122 {
 123         /* Fast compute degree of a set... the number
 124            of elements present in the set.  Assumes
 125            that all word bits are used in the set
 126            and that SETSIZE(a) is a multiple of WORDSIZE.
 127         */
 128         register unsigned *p = &(a.setword[0]);
 129         register unsigned *endp = &(a.setword[a.n]);
 130         register unsigned degree = 0;
 131
 132         CHK(a);
 133         if ( a.n == 0 ) return(0);
 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 __STDC__
 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 __STDC__
 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 __STDC__
 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 __STDC__
 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 __STDC__
 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         a->setword = (unsigned *) calloc(n, BytesPerWord);
 298         if ( a->setword == NULL )
 299         {
 300             fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
 301             exit(-1);
 302         }
 303         a->n = n;
 304         return;
 305     }
 306         if ( n < min ) n = min;
 307         if ( a->n == n || n == 0 ) return;
 308         size = a->n;
 309         a->n = n;
 310         a->setword = (unsigned *) realloc( (char *)a->setword, (n*BytesPerWord) );
 311         if ( a->setword == NULL )
 312         {
 313                 fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
 314                 exit(-1);
 315         }
 316
 317         p    = &(a->setword[size]);             /* clear from old size to new size */
 318         endp = &(a->setword[a->n]);
 319         do {
 320                 *p++ = 0;
 321         } while ( p < endp );
 322 }
 323
 324 set
 325 #ifdef __STDC__
 326 set_not( set a )
 327 #else
 328 set_not( a )
 329 set a;
 330 #endif
 331 {
 332         /* Fast not of set a (assumes all bits used) */
 333         /* size of resultant set is size(a) */
 334         /* ~empty = empty cause we don't know how bit to make set */
 335         set t;
 336         register unsigned *r;
 337         register unsigned *p = a.setword;
 338         register unsigned *endp = &(a.setword[a.n]);
 339
 340         CHK(a);
 341         t = empty;
 342         if ( a.n == 0 ) return( empty );
 343         set_ext(&t, a.n);
 344         r = t.setword;
 345
 346         do {
 347                 *r++ = (~ *p++);
 348         } while ( p < endp );
 349
 350         return(t);
 351 }
 352
 353 int
 354 #ifdef __STDC__
 355 set_equ( set a, set b )
 356 #else
 357 set_equ( a, b )
 358 set a;
 359 set b;
 360 #endif
 361 {
 362         /* Fast set equality comparison operation */
 363         register unsigned *p = a.setword;
 364         register unsigned *q = b.setword;
 365         register unsigned *endp = &(a.setword[a.n]);
 366
 367         CHK(a); CHK(b);
 368 /*      if ( a.n != b.n ) return(0);*/
 369         if ( set_deg(a) != set_deg(b) ) return(0);
 370         else if ( a.n==0 ) return(1);   /* empty == empty */
 371
 372         do {
 373                 if (*p != *q) return(0);
 374                 ++q;
 375         } while ( ++p < endp );
 376
 377         return(1);
 378 }
 379
 380 int
 381 #ifdef __STDC__
 382 set_sub( set a, set b )
 383 #else
 384 set_sub( a, b )
 385 set a;
 386 set b;
 387 #endif
 388 {
 389         /* Fast check for a is a proper subset of b (alias a < b) */
 390         register unsigned *p = a.setword;
 391         register unsigned *q = b.setword;
 392         register unsigned *endp = &(a.setword[a.n]);
 393         register int asubset = 0;
 394
 395         CHK(a); CHK(b);
 396         if ( set_deg(a) > set_deg(b) ) return(0);
 397         if ( set_deg(a)==0 && set_deg(b)==0) return(1);/* empty prop sub of empty */
 398         if ( set_deg(a) == 0 ) return(1);               /* empty is sub of everything */
 399 #ifdef DUH
 400 /* Was: */
 401         if ( a.n > b.n ) return(0);
 402         if (a.n==0 && b.n==0) return(1);/* empty prop sub of empty */
 403         if ( a.n == 0 ) return(1);              /* empty is sub of everything */
 404 #endif
 405
 406         do {
 407                 /* Prune tests based on guess that most set words
 408                    will match, particularly if a is a subset of b.
 409                 */
 410                 if (*p != *q) {
 411                         if (*p & ~(*q)) {
 412                                 /* Fail -- a contains something b does not */
 413                                 return(0);
 414                         }
 415                         /* At least this word was a proper subset, hence
 416                            even if all other words are equal, a is a
 417                            proper subset of b.
 418                         */
 419                         asubset = 1;
 420                 }
 421                 ++q;
 422         } while (++p < endp);
 423
 424         /* at this point, a,b are equ or a subset */
 425         if ( asubset || b.n == a.n ) return(asubset);
 426
 427         /* if !asubset, size(b) > size(a), then a=b and must check rest of b */
 428         p = q;
 429         endp = &(b.setword[b.n]);
 430         do
 431         {
 432                 if ( *p++ ) return(1);
 433         } while ( p < endp );
 434
 435         return(0);
 436 }
 437
 438 unsigned
 439 #ifdef __STDC__
 440 set_int( set b )
 441 #else
 442 set_int( b )
 443 set b;
 444 #endif
 445 {
 446         /* Fast pick any element of the set b */
 447         register unsigned *p = b.setword;
 448         register unsigned *endp = &(b.setword[b.n]);
 449
 450         CHK(b);
 451         if ( b.n == 0 ) return( nil );
 452
 453         do {
 454                 if (*p) {
 455                         /* Found a non-empty word of the set */
 456                         register unsigned i = ((p - b.setword) << LogWordSize);
 457                         register unsigned t = *p;
 458                         p = &(bitmask[0]);
 459                         while (!(*p & t)) {
 460                                 ++i; ++p;
 461                         }
 462                         return(i);
 463                 }
 464         } while (++p < endp);
 465
 466         /* Empty -- only element it contains is nil */
 467         return(nil);
 468 }
 469
 470 int
 471 #ifdef __STDC__
 472 set_el( unsigned b, set a )
 473 #else
 474 set_el( b, a )
 475 unsigned b;
 476 set a;
 477 #endif
 478 {
 479         CHK(a);
 480         /* nil is an element of every set */
 481         if (b == nil) return(1);
 482         if ( a.n == 0 || NumWords(b) > a.n ) return(0);
 483
 484         /* Otherwise, we have to check */
 485         return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
 486 }
 487
 488 int
 489 #ifdef __STDC__
 490 set_nil( set a )
 491 #else
 492 set_nil( a )
 493 set a;
 494 #endif
 495 {
 496         /* Fast check for nil set */
 497         register unsigned *p = a.setword;
 498         register unsigned *endp = &(a.setword[a.n]);
 499
 500         CHK(a);
 501         if ( a.n == 0 ) return(1);
 502         /* The set is not empty if any word used to store
 503            the set is non-zero.  This means one must be a
 504            bit careful about doing things like negation.
 505         */
 506         do {
 507                 if (*p) return(0);
 508         } while (++p < endp);
 509
 510         return(1);
 511 }
 512
 513 char *
 514 #ifdef __STDC__
 515 set_str( set a )
 516 #else
 517 set_str( a )
 518 set a;
 519 #endif
 520 {
 521         /* Fast convert set a into ASCII char string...
 522            assumes that all word bits are used in the set
 523            and that SETSIZE is a multiple of WORDSIZE.
 524            Trailing 0 bits are removed from the string.
 525            if no bits are on or set is empty, "" is returned.
 526         */
 527         register unsigned *p = a.setword;
 528         register unsigned *endp = &(a.setword[a.n]);
 529         static char str_tmp[StrSize+1];
 530         register char *q = &(str_tmp[0]);
 531
 532         CHK(a);
 533         if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
 534         do {
 535                 register unsigned t = *p;
 536                 register unsigned *b = &(bitmask[0]);
 537                 do {
 538                         *(q++) = (char) ((t & *b) ? '1' : '0');
 539                 } while (++b < &(bitmask[WORDSIZE]));
 540         } while (++p < endp);
 541
 542         /* Trim trailing 0s & NULL terminate the string */
 543         while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
 544         *q = 0;
 545
 546         return(&(str_tmp[0]));
 547 }
 548
 549 set
 550 #ifdef __STDC__
 551 set_val( register char *s )
 552 #else
 553 set_val( s )
 554 register char *s;
 555 #endif
 556 {
 557         /* Fast convert set ASCII char string into a set.
 558            If the string ends early, the remaining set bits
 559            are all made zero.
 560            The resulting set size is just big enough to hold all elements.
 561         */
 562         static set a;
 563         register unsigned *p, *endp;
 564
 565         set_new(a, strlen(s));
 566         p = a.setword;
 567         endp = &(a.setword[a.n]);
 568         do {
 569                 register unsigned *b = &(bitmask[0]);
 570                 /* Start with a word with no bits on */
 571                 *p = 0;
 572                 do {
 573                         if (*s) {
 574                                 if (*s == '1') {
 575                                         /* Turn-on this bit */
 576                                         *p |= *b;
 577                                 }
 578                                 ++s;
 579                         }
 580                 } while (++b < &(bitmask[WORDSIZE]));
 581         } while (++p < endp);
 582
 583         return(a);
 584 }
 585
 586 /*
 587  * Or element e into set a.  a can be empty.
 588  */
 589 void
 590 #ifdef __STDC__
 591 set_orel( unsigned e, set *a )
 592 #else
 593 set_orel( e, a )
 594 unsigned e;
 595 set *a;
 596 #endif
 597 {
 598         CHK((*a));
 599         if ( e == nil ) return;
 600         if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
 601         a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
 602 }
 603
 604 /*
 605  * Or set b into set a.  a can be empty. does nothing if b empty.
 606  */
 607 void
 608 #ifdef __STDC__
 609 set_orin( set *a, set b )
 610 #else
 611 set_orin( a, b )
 612 set *a;
 613 set b;
 614 #endif
 615 {
 616         /* Fast set union operation */
 617         /* size(a) is max(a, b); */
 618         unsigned int m;
 619         register unsigned *p,
 620                                           *q    = b.setword,
 621                                           *endq = &(b.setword[b.n]);
 622
 623         CHK((*a)); CHK(b);
 624         if ( b.n == 0 ) return;
 625         m = (a->n > b.n) ? a->n : b.n;
 626         set_ext(a, m);
 627         p = a->setword;
 628         do {
 629                 *p++ |= *q++;
 630         } while ( q < endq );
 631 }
 632
 633 void
 634 #ifdef __STDC__
 635 set_rm( unsigned e, set a )
 636 #else
 637 set_rm( e, a )
 638 unsigned e;
 639 set a;
 640 #endif
 641 {
 642         /* Does not effect size of set */
 643         CHK(a);
 644         if ( (e == nil) || (NumWords(e) > a.n) ) return;
 645         a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
 646 }
 647
 648 void
 649 #ifdef __STDC__
 650 set_clr( set a )
 651 #else
 652 set_clr( a )
 653 set a;
 654 #endif
 655 {
 656         /* Does not effect size of set */
 657         register unsigned *p = a.setword;
 658         register unsigned *endp = &(a.setword[a.n]);
 659
 660         CHK(a);
 661         if ( a.n == 0 ) return;
 662         do {
 663                 *p++ = 0;
 664         } while ( p < endp );
 665 }
 666
 667 set
 668 #ifdef __STDC__
 669 set_dup( set a )
 670 #else
 671 set_dup( a )
 672 set a;
 673 #endif
 674 {
 675         set b;
 676         register unsigned *p,
 677                                           *q    = a.setword,
 678                                           *endq = &(a.setword[a.n]);
 679
 680         CHK(a);
 681         b = empty;
 682         if ( a.n == 0 ) return( empty );
 683         set_ext(&b, a.n);
 684         p = b.setword;
 685         do {
 686                 *p++ = *q++;
 687         } while ( q < endq );
 688
 689         return(b);
 690 }
 691
 692 /*
 693  * Return a nil terminated list of unsigned ints that represents all
 694  * "on" bits in the bit set.
 695  *
 696  * e.g. {011011} --> {1, 2, 4, 5, nil}
 697  *
 698  * _set_pdq and set_pdq are useful when an operation is required on each element
 699  * of a set.  Normally, the sequence is:
 700  *
 701  *              while ( set_deg(a) > 0 ) {
 702  *                      e = set_int(a);
 703  *                      set_rm(e, a);
 704  *                      ...process e...
 705  *              }
 706  * Now,
 707  *
 708  *              t = e = set_pdq(a);
 709  *              while ( *e != nil ) {
 710  *                      ...process *e...
 711  *                      e++;
 712  *              }
 713  *              free( t );
 714  *
 715  * We have saved many set calls and have not destroyed set a.
 716  */
 717 void
 718 #ifdef __STDC__
 719 _set_pdq( set a, register unsigned *q )
 720 #else
 721 _set_pdq( a, q )
 722 set a;
 723 register unsigned *q;
 724 #endif
 725 {
 726         register unsigned *p = a.setword,
 727                                           *endp = &(a.setword[a.n]);
 728         register unsigned e=0;
 729
 730         CHK(a);
 731         /* are there any space (possibility of elements)? */
 732         if ( a.n == 0 ) return;
 733         do {
 734                 register unsigned t = *p;
 735                 register unsigned *b = &(bitmask[0]);
 736                 do {
 737                         if ( t & *b ) *q++ = e;
 738                         ++e;
 739                 } while (++b < &(bitmask[WORDSIZE]));
 740         } while (++p < endp);
 741         *q = nil;
 742 }
 743
 744 /*
 745  * Same as _set_pdq except allocate memory.  set_pdq is the natural function
 746  * to use.
 747  */
 748 unsigned *
 749 #ifdef __STDC__
 750 set_pdq( set a )
 751 #else
 752 set_pdq( a )
 753 set a;
 754 #endif
 755 {
 756         unsigned *q;
 757         int max_deg;
 758
 759         CHK(a);
 760         max_deg = WORDSIZE*a.n;
 761         /* assume a.n!=0 & no elements is rare, but still ok */
 762         if ( a.n == 0 ) return(NULL);
 763         q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
 764         if ( q == NULL ) return( NULL );
 765         _set_pdq(a, q);
 766         return( q );
 767 }
 768
 769 /* a function that produces a hash number for the set
 770  */
 771 unsigned int
 772 #ifdef __STDC__
 773 set_hash( set a, register unsigned int mod )
 774 #else
 775 set_hash( a, mod )
 776 set a;
 777 register unsigned int mod;
 778 #endif
 779 {
 780         /* Fast hash of set a (assumes all bits used) */
 781         register unsigned *p = &(a.setword[0]);
 782         register unsigned *endp = &(a.setword[a.n]);
 783         register unsigned i = 0;
 784
 785         CHK(a);
 786         while (p<endp){
 787                 i += (*p);
 788                 ++p;
 789         }
 790
 791         return(i % mod);
 792 }