]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/Source/TianoTools/Pccts/support/set/set.c
3 The following is a general-purpose set library originally developed
4 by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.
6 Sets are now structs containing the #words in the set and
7 a pointer to the actual set words.
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
15 Sets can be explicitly created with set_new(s, max_elem).
17 Sets can be declared to have minimum size to reduce realloc traffic.
18 Default minimum size = 1.
20 Sets can be explicitly initialized to have no elements (set.n == 0)
21 by using the 'empty' initializer:
24 set a = empty; -- set_deg(a) == 0
28 Example set creation and destruction:
36 b = set_of(e); -- Creates space for b and sticks in e
37 set_new(c, g); -- set_new(); set_orel() ==> set_of()
55 Made it smell less bad to C++ 7/31/93 -- TJP
69 #define MIN(i,j) ( (i) > (j) ? (j) : (i))
70 #define MAX(i,j) ( (i) < (j) ? (j) : (i))
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
87 static unsigned min
=1;
93 if ( a.setword != NULL ) \
94 if ( !valid(a.setword) ) \
95 {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
101 * Set the minimum size (in words) of a set to reduce realloc calls
105 set_size( unsigned n
)
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.
127 register unsigned *p
= &(a
.setword
[0]);
128 register unsigned *endp
= NULL
; /* MR27 Avoid false memory check report */
129 register unsigned degree
= 0;
132 if ( a
.n
== 0 ) return(0);
133 endp
= &(a
.setword
[a
.n
]);
136 register unsigned t
= *p
;
137 register unsigned *b
= &(bitmask
[0]);
139 if (t
& *b
) ++degree
;
140 } while (++b
< &(bitmask
[WORDSIZE
]));
149 set_or( set b
, set c
)
156 /* Fast set union operation */
157 /* resultant set size is max(b, c); */
161 register unsigned *r
, *p
, *q
, *endp
;
165 if (b
.n
> c
.n
) {big
= &b
; m
=b
.n
; n
=c
.n
;} else {big
= &c
; m
=c
.n
; n
=b
.n
;}
169 /* Or b,c until max of smaller set */
172 endp
= &(b
.setword
[n
]);
173 while ( p
< endp
) *r
++ = *p
++ | *q
++;
175 /* Copy rest of bigger set into result */
176 p
= &(big
->setword
[n
]);
177 endp
= &(big
->setword
[m
]);
178 while ( p
< endp
) *r
++ = *p
++;
185 set_and( set b
, set c
)
192 /* Fast set intersection operation */
193 /* resultant set size is min(b, c); */
196 register unsigned *r
, *p
, *q
, *endp
;
200 n
= (b
.n
> c
.n
) ? c
.n
: b
.n
;
201 if ( n
== 0 ) return t
; /* TJP 4-27-92 fixed for empty set */
205 /* & b,c until max of smaller set */
208 endp
= &(b
.setword
[n
]);
209 while ( p
< endp
) *r
++ = *p
++ & *q
++;
216 set_dif( set b
, set c
)
223 /* Fast set difference operation b - c */
224 /* resultant set size is size(b) */
227 register unsigned *r
, *p
, *q
, *endp
;
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 */
237 /* Dif b,c until smaller set size */
240 endp
= &(b
.setword
[n
]);
241 while ( p
< endp
) *r
++ = *p
++ & (~ *q
++);
243 /* Copy rest of b into result if size(b) > c */
247 endp
= &(b
.setword
[b
.n
]);
248 while ( p
< endp
) *r
++ = *p
++;
262 /* Fast singleton set constructor operation */
265 if ( b
== nil
) return( empty
);
267 a
.setword
[DIVWORD(b
)] = bitmask
[MODWORD(b
)];
273 * Extend (or shrink) the set passed in to have n words.
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.
278 * TJP 4-27-92 Fixed so won't try to alloc 0 bytes
282 set_ext( set
*a
, unsigned int n
)
289 register unsigned *p
;
290 register unsigned *endp
;
296 if ( n
== 0 ) return;
297 if (a
->setword
!= NULL
) {
298 free (a
->setword
); /* MR20 */
300 a
->setword
= (unsigned *) calloc(n
, BytesPerWord
);
301 if ( a
->setword
== NULL
)
303 fprintf(stderr
, "set_ext(%d words): cannot allocate set\n", n
);
309 if ( n
< min
) n
= min
;
310 if ( a
->n
== n
|| n
== 0 ) return;
313 a
->setword
= (unsigned *) realloc( (char *)a
->setword
, (n
*BytesPerWord
) );
314 if ( a
->setword
== NULL
)
316 fprintf(stderr
, "set_ext(%d words): cannot allocate set\n", n
);
320 p
= &(a
->setword
[size
]); /* clear from old size to new size */
321 endp
= &(a
->setword
[a
->n
]);
324 } while ( p
< endp
);
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 */
339 register unsigned *r
;
340 register unsigned *p
= a
.setword
;
341 register unsigned *endp
= &(a
.setword
[a
.n
]);
345 if ( a
.n
== 0 ) return( empty
);
351 } while ( p
< endp
);
358 set_equ( set a
, set b
)
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 */
369 unsigned int count
; /* MR11 */
370 unsigned int i
; /* MR11 */
375 if (count
== 0) return 1;
376 for (i
=0; i
< count
; i
++) {
377 if (a
.setword
[i
] != b
.setword
[i
]) return 0;
380 for (i
=count
; i
< b
.n
; i
++) {
381 if (b
.setword
[i
] != 0) return 0;
384 } else if (a
.n
> b
.n
) {
385 for (i
=count
; i
< a
.n
; i
++) {
386 if (a
.setword
[i
] != 0) return 0;
396 set_sub( set a
, set b
)
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 */
413 if (a
.n
== 0) return 1;
415 for (i
=0; i
< count
; i
++) {
416 if (a
.setword
[i
] & ~b
.setword
[i
]) return 0;
421 for (i
=count
; i
<a
.n
; i
++) {
422 if (a
.setword
[i
]) return 0;
436 /* Fast pick any element of the set b */
437 register unsigned *p
= b
.setword
;
438 register unsigned *endp
= &(b
.setword
[b
.n
]);
441 if ( b
.n
== 0 ) return( nil
);
445 /* Found a non-empty word of the set */
446 register unsigned i
= ((p
- b
.setword
) << LogWordSize
);
447 register unsigned t
= *p
;
454 } while (++p
< endp
);
456 /* Empty -- only element it contains is nil */
462 set_el( unsigned b
, set 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);
474 /* Otherwise, we have to check */
475 return( a
.setword
[DIVWORD(b
)] & bitmask
[MODWORD(b
)] );
486 /* Fast check for nil set */
487 register unsigned *p
= a
.setword
;
488 register unsigned *endp
;
491 if ( a
.n
== 0 ) return(1);
492 endp
= &(a
.setword
[a
.n
]);
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.
500 } while (++p
< endp
);
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.
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]);
525 if ( a
.n
==0 ) {*q
=0; return( &(str_tmp
[0]) );}
527 register unsigned t
= *p
;
528 register unsigned *b
= &(bitmask
[0]);
530 *(q
++) = (char) ((t
& *b
) ? '1' : '0');
531 } while (++b
< &(bitmask
[WORDSIZE
]));
532 } while (++p
< endp
);
534 /* Trim trailing 0s & NULL terminate the string */
535 while ((q
> &(str_tmp
[0])) && (*(q
-1) != '1')) --q
;
538 return(&(str_tmp
[0]));
543 set_val( register char *s
)
549 /* Fast convert set ASCII char string into a set.
550 If the string ends early, the remaining set bits
552 The resulting set size is just big enough to hold all elements.
555 register unsigned *p
, *endp
;
557 set_new(a
, strlen(s
));
559 endp
= &(a
.setword
[a
.n
]);
561 register unsigned *b
= &(bitmask
[0]);
562 /* Start with a word with no bits on */
567 /* Turn-on this bit */
572 } while (++b
< &(bitmask
[WORDSIZE
]));
573 } while (++p
< endp
);
579 * Or element e into set a. a can be empty.
583 set_orel( unsigned e
, set
*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
)];
597 * Or set b into set a. a can be empty. does nothing if b empty.
601 set_orin( set
*a
, set b
)
608 /* Fast set union operation */
609 /* size(a) is max(a, b); */
611 register unsigned *p
,
616 if ( b
.n
== 0 ) return;
617 endq
= &(b
.setword
[b
.n
]); /* MR20 */
618 m
= (a
->n
> b
.n
) ? a
->n
: b
.n
;
623 } while ( q
< endq
);
627 * And set b into set a. a can be empty. does nothing if b empty.
631 set_andin( set
*a
, set b
)
638 /* Fast set intersection operation */
639 /* size(a) is max(a, b); */
641 register unsigned *p
,
643 *endq
= &(b
.setword
[b
.n
]);
646 if ( b
.n
== 0 ) return;
647 m
= (a
->n
> b
.n
) ? a
->n
: b
.n
;
652 } while ( q
< endq
);
657 set_rm( unsigned e
, set a
)
664 /* Does not effect size of set */
666 if ( (e
== nil
) || (NumWords(e
) > a
.n
) ) return;
667 a
.setword
[DIVWORD(e
)] ^= (a
.setword
[DIVWORD(e
)]&bitmask
[MODWORD(e
)]);
678 /* Does not effect size of set */
679 register unsigned *p
= a
.setword
;
680 register unsigned *endp
;
683 if ( a
.n
== 0 ) return;
684 endp
= &(a
.setword
[a
.n
]);
687 } while ( p
< endp
);
699 register unsigned *p
,
705 if ( a
.n
== 0 ) return( empty
);
706 endq
= &(a
.setword
[a
.n
]); /* MR20 */
711 } while ( q
< endq
);
717 * Return a nil terminated list of unsigned ints that represents all
718 * "on" bits in the bit set.
720 * e.g. {011011} --> {1, 2, 4, 5, nil}
722 * _set_pdq and set_pdq are useful when an operation is required on each element
723 * of a set. Normally, the sequence is:
725 * while ( set_deg(a) > 0 ) {
732 * t = e = set_pdq(a);
733 * while ( *e != nil ) {
739 * We have saved many set calls and have not destroyed set a.
743 _set_pdq( set a
, register unsigned *q
)
747 register unsigned *q
;
750 register unsigned *p
= a
.setword
,
751 *endp
= &(a
.setword
[a
.n
]);
752 register unsigned e
=0;
755 /* are there any space (possibility of elements)? */
756 if ( a
.n
== 0 ) return;
758 register unsigned t
= *p
;
759 register unsigned *b
= &(bitmask
[0]);
761 if ( t
& *b
) *q
++ = e
;
763 } while (++b
< &(bitmask
[WORDSIZE
]));
764 } while (++p
< endp
);
769 * Same as _set_pdq except allocate memory. set_pdq is the natural function
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
);
793 /* a function that produces a hash number for the set
797 set_hash( set a
, register unsigned int mod
)
801 register unsigned int mod
;
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;