Category : Files from Magazines
Archive   : DDJ8611.ZIP
Filename : HOLUB.NOV

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
2 #include
3 #include
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 :");
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 :");
332 }
333 }
334
335 #endif
[EOF]