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