home *** CD-ROM | disk | FTP | other *** search
- Listing 1 -- set.h
- ------------------------------------------------------------------------------
- 1 /* SET.H: Header to use the set manipulation routiness in set.c
- 2 *
- 3 * Copyright (c) 1986, Allen I. Holub. All rights reserved
- 4 */
- 5
- 6 #define DEFBYTES 2 /* bytes in def set (>= 1) */
- 7 #define DEFBITS (DEFBYTES * 8) /* bits in default set */
- 8
- 9 typedef struct
- 10 {
- 11 unsigned nbytes : 13; /* Number of bytes in map */
- 12 unsigned compl : 1; /* This is a negative true set */
- 13 int nbits; /* Number of bits in map */
- 14 unsigned char *map; /* Pointer to the map */
- 15 unsigned char defmap[DEFBYTES]; /* The map itself */
- 16 }
- 17 SET;
- 18
- 19 extern void set_op ( int, SET*, SET*, SET*); /* Routines in set.c */
- 20 extern int set_cmp ( SET*, SET* );
- 21 extern int subset ( SET*, SET* );
- 22 extern int num_ele ( SET* );
- 23 extern void delset ( SET* );
- 24 extern SET *newset ( );
- 25
- 26 #define UNION 0 /* x is in s1 or s2 */
- 27 #define INTERSECT 1 /* x is in s1 and s2 */
- 28 #define DIFFERENCE 2 /* x is in s1 but !s2 or in s2 but !s1 */
- 29 #define INVERT 3 /* ones complement */
- 30 #define ASSIGN 4 /* s1 = s2 */
- 31 #define CLEAR 5 /* d = all bits cleared */
- 32 #define FILL 6 /* d = all bits set */
- 33
- 34 #define union(d,s1,s2) set_op( UNION, d, s1, s2 )
- 35 #define intersection(d,s1,s2) set_op( INTERSECT, d, s1, s2 )
- 36 #define difference(d,s1,s2) set_op( DIFFERENCE, d, s1, s2 )
- 37 #define assign(d,s1) set_op( ASSIGN, d, s1, NULL )
- 38 #define invert(d,s1) set_op( INVERT, d, s1, NULL )
- 39 #define clear(d) set_op( CLEAR, d, NULL, NULL )
- 40 #define fill(d) set_op( FILL, d, NULL, NULL )
- 41 #define complement(d) ( (d)->compl = ~(d)->compl)
- 42
- 43 #define equivalent(s1,s2) ( set_cmp(s1,s2) == 0 )
- 44 #define disjoint(s1,s2) ( set_cmp(s1,s2) == 1 )
- 45
- 46 #define GBIT(x,s,op) ( ((s)->map)[(x) >> 3] op (1 << ((x) & 0x07)) )
- 47
- 48 #define remove(x,s) ( ((x) >= (s)->nbits) ? 0 : GBIT(x,s,&= ~) )
- 49 #define add(x,s) ( ((x) >= (s)->nbits) ? addset(x,s) : GBIT(x,s,|= ) )
- 50 #define ismember(x,s) ( ((x) >= (s)->nbits) ? 0 : GBIT(x,s,& ) )
- 51
- 52 #define test(x,s) ( ( ismember(x,s) ) ? !( (s)->compl ) : (s)->compl )
-
- Listing 2 -- set.c
- ------------------------------------------------------------------------------
- 1 #include <stdio.h>
- 2 #include <ctype.h>
- 3 #include <set.h>
- 4
- 5 extern char *calloc ( int, int );
- 6
- 7 /*----------------------------------------------------------------------*/
- 8
- 9 #ifdef DIAG
- 10 # define D(x) x
- 11 #else
- 12 # define D(x)
- 13 #endif
- 14
- 15 #define max(a,b) ((a) > (b) ? (a) : (b))
- 16
- 17 /*----------------------------------------------------------------------*/
- 18
- 19 SET *newset()
- 20 {
- 21 SET *p;
- 22
- 23 if( !(p=(SET *) calloc(sizeof(SET),1)) )
- 24 {
- 25 fprintf(stderr,"Can't get memory for set\n");
- 26 return NULL;
- 27 }
- 28 else
- 29 {
- 30 p->map = p->defmap;
- 31 p->nbytes = DEFBYTES;
- 32 p->nbits = DEFBITS;
- 33 }
- 34 return p;
- 35 }
- 36
- 37 /*----------------------------------------------------------------------*/
- 38
- 39 void delset( set )
- 40 SET *set;
- 41 {
- 42 /* Delete a set created with a previous newset
- 43 */
- 44
- 45 if( set->map != set->defmap )
- 46 free( set->map );
- 47
- 48 free( set );
- 49 }
- 50
- 51 /*----------------------------------------------------------------------*/
- 52
- 53 static void enlarge( need, set )
- 54 SET *set;
- 55 {
- 56 /* Enlarge the set to "need" bytes, filling in the extra
- 57 * bytes with zeros.
- 58 */
- 59
- 60 register char *new;
- 61
- 62 if( !set || need <= set->nbytes )
- 63 return;
- 64
- 65 D( printf("enlarging %d byte map to %d bytes\n", set->nbytes,need);)
- 66
- 67 if( !(new = calloc(need, 1)) )
- 68 fprintf(stderr,"Can't get memory to expand set\n");
- 69 else
- 70 {
- 71 memcpy( new, set->map, set->nbytes );
- 72
- 73 if( set->map != set->defmap )
- 74 free( set->map );
- 75
- 76 set->map = new;
- 77 set->nbytes = need;
- 78 set->nbits = need * 8;
- 79 }
- 80 }
- 81
- 82 /* ------------------------------------------------------------------- */
- 83
- 84 int addset( bit, set )
- 85 SET *set;
- 86 {
- 87 /* Addset is called by the add() macro when the set isn't
- 88 * big enough. It expands the set to the necessary size
- 89 * and sets the indicated bit.
- 90 */
- 91
- 92 enlarge( (bit >> 3) + 1, set );
- 93 GBIT ( bit, set, |= );
- 94 }
- 95
- 96 /* ------------------------------------------------------------------- */
- 97
- 98 int num_ele( set )
- 99 SET *set;
- 100 {
- 101 /* Return the number of elements (set bits) in the set.
- 102 * This routine depends on zero fill when an
- 103 * unsigned quantity is shifted to the right.
- 104 */
- 105
- 106 register unsigned j;
- 107 register unsigned count = 0;
- 108 unsigned char *p;
- 109 int i;
- 110
- 111 p = set->map;
- 112 for( i = set->nbytes; --i >= 0 ; p++)
- 113 for( j = *p; j ; j >>= 1 )
- 114 count += j & 0x1;
- 115
- 116 return count;
- 117 }
- 118
- 119 /* ------------------------------------------------------------------- */
- 120
- 121 set_cmp( set1, set2 )
- 122 SET *set1, *set2;
- 123 {
- 124 /* Compares two sets. Returns zero if they're equivalent, one if
- 125 * they're disjoint, 2 if they intersect but aren't equivalent,
- 126 * -1 is returned if the two sets are different sizes.
- 127 */
- 128
- 129 register char *p1, *p2;
- 130 register int i, disj = 0 ;
- 131
- 132 i = max( set1->nbytes, set2->nbytes);
- 133
- 134 enlarge( i, set1 ); /* Make the sets the same size */
- 135 enlarge( i, set2 );
- 136
- 137 p1 = set1->map;
- 138 p2 = set2->map;
- 139
- 140 for(; --i >= 0; p1++, p2++ )
- 141 {
- 142 if( *p1 != *p2 )
- 143 {
- 144 if( *p1 ^ ~*p2 )
- 145 return 2;
- 146 else
- 147 disj = 1;
- 148 }
- 149 }
- 150
- 151 return disj; /* They're equivalent */
- 152 }
- 153
- 154 /* ------------------------------------------------------------------- */
- 155
- 156 int subset( a, b )
- 157 SET *a, *b;
- 158 {
- 159 /* Return 1 if A is a subset of B. Set A must be either smaller
- 160 * than or the same size as B. 0 is returned if A is not a
- 161 * subset or if A is larger than B.
- 162 */
- 163
- 164 register int i;
- 165 register char *ap, *bp;
- 166
- 167 if( (i = a->nbytes) > b->nbytes )
- 168 return 0;
- 169
- 170 ap = a->map;
- 171 bp = b->map;
- 172
- 173 for(; --i >= 0; ap++, bp++ )
- 174 if( (*ap & *bp) != *ap )
- 175 return 0;
- 176 return 1;
- 177 }
- 178
- 179 /* ------------------------------------------------------------------- */
- 180
- 181 void set_op( op, dest, set1, set2 )
- 182 int op;
- 183 SET *set1, *set2, *dest;
- 184 {
- 185 /* Performs either the union or intersection of two sets
- 186 * (depending on the value of "union"). Dest is the result.
- 187 * The two source sets (set1 and set2) must be different,
- 188 * however either of the sources may be used as a destination
- 189 * if you like. If the sets are different sizes, the smaller
- 190 * set is made larger. Unused arguments should be set to NULL.
- 191 */
- 192
- 193 register char *d; /* Pointer to destiniation map */
- 194 register char *m1; /* Pointer to map in set1 */
- 195 register char *m2; /* Pointer to map in set2 */
- 196 register int i; /* Number of bytes in map */
- 197
- 198
- 199 i = dest->nbytes;
- 200 if( set1 )
- 201 i = max( i, set1->nbytes );
- 202 if( set2 )
- 203 i = max( i, set2->nbytes );
- 204
- 205 enlarge( i, set1 ); /* Make all three sets the same size */
- 206 enlarge( i, set2 ); /* if necessary. Enlarge() does nothing */
- 207 enlarge( i, dest ); /* if they're already the correct size. */
- 208
- 209 d = dest->map;
- 210 m1 = set1->map;
- 211 m2 = set2->map;
- 212
- 213 while( --i >= 0 )
- 214 {
- 215 D( printf("set_op: working on bit %d\n", i ); )
- 216
- 217 switch( op )
- 218 {
- 219 case UNION: *d++ = *m1++ | *m2++ ; break;
- 220 case INTERSECT: *d++ = *m1++ & *m2++ ; break;
- 221 case DIFFERENCE: *d++ = *m1++ ^ *m2++ ; break;
- 222 case ASSIGN: *d++ = *m1++ ; break;
- 223 case INVERT: *d++ = ~*m1++ ; break;
- 224 case CLEAR: *d++ = 0 ; break;
- 225 case FILL: *d++ = ~0 ; break;
- 226 }
- 227 }
- 228 }
- 229
- 230 /* ------------------------------------------------------------------- */
- 231 #ifdef DEBUG
- 232
- 233 pset( str, set )
- 234 char *str;
- 235 SET *set;
- 236 {
- 237 int i;
- 238
- 239 printf("+------------------------------------------------------\n");
- 240 printf("| %s\n", str );
- 241 printf("| Set at 0x%04x: %d bits, %d bytes, map (0x%04x) ",
- 242 set, set->nbits, set->nbytes, set->map);
- 243
- 244 printf("%s TRUE\n", set->compl ? "NEGATIVE" : "POSITIVE" );
- 245 printf("| map = ");
- 246
- 247 for( i = 0; i < set->nbytes; i++ )
- 248 printf("0x%02x,", (set->map)[i] );
- 249
- 250 printf("\n| bits= ");
- 251
- 252 for( i = 0; i < set->nbits; i++ )
- 253 printf( test(i, set) ? "%d," : "" , i );
- 254
- 255 printf("\n| %d elements\n", num_ele(set) );
- 256
- 257 printf("+------------------------------------------------------\n");
- 258 }
- 259
- 260 /* ------------------------------------------------------------------- */
- 261
- 262 test_stuff( a, b, d )
- 263 SET *a, *b, *d;
- 264 {
- 265 pset("set a", a );
- 266 pset("set b", b );
- 267
- 268 union (d,a,b); pset("a union b", d );
- 269 intersection (d,a,b); pset("a intersect b", d );
- 270 difference (d,a,b); pset("a difference b", d );
- 271 assign (d,a); pset("d assign a", d );
- 272 complement (d); pset("complement a", d );
- 273 complement (d);
- 274 invert (d,a); pset("invert a", d );
- 275
- 276 printf("a %s equivalent to b\n", equivalent(a,b) ? "IS" : "ISN'T" );
- 277 printf("a %s disjoint from b\n", disjoint(a,b) ? "IS" : "ISN'T" );
- 278 printf("b %s a subset of a\n", subset(b, a) ? "IS" : "ISN'T" );
- 279 printf("a %s a subset of b\n", subset(a, b) ? "IS" : "ISN'T" );
- 280
- 281 printf("-------------------------------------------------------\n");
- 282 }
- 283
- 284 /* ------------------------------------------------------------------- */
- 285
- 286 main()
- 287 {
- 288 SET *a, *b, *d;
- 289 char buf[80], *p;
- 290 int num;
- 291
- 292 a = newset(); pset( "initial a", a );
- 293 b = newset(); pset( "initial b", b );
- 294 d = newset(); pset( "initial d", d );
- 295
- 296 add(0,a);
- 297 add(1,a);
- 298 add(3,a);
- 299 add(0,b);
- 300 add(3,b);
- 301
- 302 test_stuff( a, b, d );
- 303
- 304 remove(0,a); remove(1,a); remove(3,a); remove(0,b); remove(3,b);
- 305 add(0, a); add(2, a); add(2, b); add(3, b);
- 306
- 307 test_stuff( a, b, d );
- 308
- 309 clear( a ); clear( b ); test_stuff( a, b, d );
- 310 clear( a ); fill ( b ); test_stuff( a, b, d );
- 311
- 312 delset( b );
- 313 delset( d );
- 314 delset( a );
- 315 a = newset();
- 316
- 317 printf("enter <bitnum><s|c>:");
- 318
- 319 while( gets(buf) )
- 320 {
- 321 num = atoi(buf);
- 322 for( p = buf; isdigit(*p) ; p++ )
- 323 ;
- 324
- 325 if( *p == 's' )
- 326 add(num ,a);
- 327 else
- 328 remove(num, a);
- 329
- 330 pset( "", a );
- 331 printf("enter <bitnum><s|c>:");
- 332 }
- 333 }
- 334
- 335 #endif
- [EOF]
-
