1 /*
2 set.c
3
4 Set manipulation.
5
6 Copyright (C) 2012 Bill Currie <bill@taniwha.org>
7
8 Author: Bill Currie <bill@taniwha.org>
9 Date: 2012/8/4
10
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License
13 as published by the Free Software Foundation; either version 2
14 of the License, or (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19
20 See the GNU General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to:
24
25 Free Software Foundation, Inc.
26 59 Temple Place - Suite 330
27 Boston, MA 02111-1307, USA
28
29 */
30 #ifdef HAVE_CONFIG_H
31 # include "config.h"
32 #endif
33
34 #ifdef HAVE_STRING_H
35 # include <string.h>
36 #endif
37 #ifdef HAVE_STRINGS_H
38 # include <strings.h>
39 #endif
40
41 #include <stdlib.h>
42
43 #include "QF/alloc.h"
44 #include "QF/dstring.h"
45 #include "QF/mathlib.h"
46 #include "QF/set.h"
47
48 #define BITS (sizeof (((set_t *) 0)->map[0]) * 8)
49
50 set_t *free_sets;
51 set_iter_t *free_set_iters;
52
53 static set_iter_t *
new_setiter(void)54 new_setiter (void)
55 {
56 set_iter_t *set_iter;
57 ALLOC (16, set_iter_t, set_iters, set_iter);
58 return set_iter;
59 }
60
61 static void
delete_setiter(set_iter_t * set_iter)62 delete_setiter (set_iter_t *set_iter)
63 {
64 FREE (set_iters, set_iter);
65 }
66
67 void
set_del_iter(set_iter_t * set_iter)68 set_del_iter (set_iter_t *set_iter)
69 {
70 delete_setiter (set_iter);
71 }
72
73 set_t *
set_new(void)74 set_new (void)
75 {
76 set_t *set;
77
78 ALLOC (16, set_t, sets, set);
79 set->size = sizeof (set->defmap) * 8;
80 set->map = set->defmap;
81 return set;
82 }
83
84 void
set_delete(set_t * set)85 set_delete (set_t *set)
86 {
87 if (set->map != set->defmap)
88 free (set->map);
89 FREE (sets, set);
90 }
91
92 static void
set_expand(set_t * set,unsigned x)93 set_expand (set_t *set, unsigned x)
94 {
95 unsigned *map = set->map;
96 size_t size;
97
98 if (x <= set->size)
99 return;
100
101 size = (x + BITS) & ~(BITS - 1);
102 set->map = malloc (size / 8);
103 memcpy (set->map, map, set->size / 8);
104 memset (set->map + set->size / BITS, 0, (size - set->size) / 8);
105 set->size = size;
106 if (map != set->defmap)
107 free (map);
108 }
109
110 static inline void
_set_add(set_t * set,unsigned x)111 _set_add (set_t *set, unsigned x)
112 {
113 if (x >= set->size)
114 set_expand (set, x + 1);
115 set->map[x / BITS] |= 1 << (x % BITS);
116 }
117
118 static inline void
_set_remove(set_t * set,unsigned x)119 _set_remove (set_t *set, unsigned x)
120 {
121 if (x >= set->size)
122 return;
123 set->map[x / BITS] &= ~(1 << (x % BITS));
124 }
125
126 set_t *
set_add(set_t * set,unsigned x)127 set_add (set_t *set, unsigned x)
128 {
129 if (set->inverted)
130 _set_remove (set, x);
131 else
132 _set_add (set, x);
133 return set;
134 }
135
136 set_t *
set_remove(set_t * set,unsigned x)137 set_remove (set_t *set, unsigned x)
138 {
139 if (set->inverted)
140 _set_add (set, x);
141 else
142 _set_remove (set, x);
143 return set;
144 }
145
146 set_t *
set_invert(set_t * set)147 set_invert (set_t *set)
148 {
149 set->inverted = !set->inverted;
150 return set;
151 }
152
153 static set_t *
_set_union(set_t * dst,const set_t * src)154 _set_union (set_t *dst, const set_t *src)
155 {
156 unsigned size;
157 unsigned i;
158
159 size = max (dst->size, src->size);
160 set_expand (dst, size);
161 for (i = 0; i < src->size / BITS; i++)
162 dst->map[i] |= src->map[i];
163 return dst;
164 }
165
166 static set_t *
_set_intersection(set_t * dst,const set_t * src)167 _set_intersection (set_t *dst, const set_t *src)
168 {
169 unsigned size;
170 unsigned i;
171
172 size = max (dst->size, src->size);
173 set_expand (dst, size);
174 for (i = 0; i < src->size / BITS; i++)
175 dst->map[i] &= src->map[i];
176 for ( ; i < dst->size / BITS; i++)
177 dst->map[i] = 0;
178 return dst;
179 }
180
181 static set_t *
_set_difference(set_t * dst,const set_t * src)182 _set_difference (set_t *dst, const set_t *src)
183 {
184 unsigned size;
185 unsigned i;
186
187 size = max (dst->size, src->size);
188 set_expand (dst, size);
189 for (i = 0; i < src->size / BITS; i++)
190 dst->map[i] &= ~src->map[i];
191 return dst;
192 }
193
194 static set_t *
_set_reverse_difference(set_t * dst,const set_t * src)195 _set_reverse_difference (set_t *dst, const set_t *src)
196 {
197 unsigned size;
198 unsigned i;
199
200 size = max (dst->size, src->size);
201 set_expand (dst, size);
202 for (i = 0; i < src->size / BITS; i++)
203 dst->map[i] = ~dst->map[i] & src->map[i];
204 return dst;
205 }
206
207 set_t *
set_union(set_t * dst,const set_t * src)208 set_union (set_t *dst, const set_t *src)
209 {
210 if (dst->inverted && src->inverted) {
211 return _set_intersection (dst, src);
212 } else if (src->inverted) {
213 dst->inverted = 1;
214 return _set_difference (dst, src);
215 } else if (dst->inverted) {
216 return _set_reverse_difference (dst, src);
217 } else {
218 return _set_union (dst, src);
219 }
220 }
221
222 set_t *
set_intersection(set_t * dst,const set_t * src)223 set_intersection (set_t *dst, const set_t *src)
224 {
225 if (dst->inverted && src->inverted) {
226 return _set_union (dst, src);
227 } else if (src->inverted) {
228 return _set_difference (dst, src);
229 } else if (dst->inverted) {
230 dst->inverted = 0;
231 return _set_reverse_difference (dst, src);
232 } else {
233 return _set_intersection (dst, src);
234 }
235 }
236
237 set_t *
set_difference(set_t * dst,const set_t * src)238 set_difference (set_t *dst, const set_t *src)
239 {
240 if (dst->inverted && src->inverted) {
241 dst->inverted = 0;
242 return _set_reverse_difference (dst, src);
243 } else if (src->inverted) {
244 return _set_intersection (dst, src);
245 } else if (dst->inverted) {
246 return _set_union (dst, src);
247 } else {
248 return _set_difference (dst, src);
249 }
250 }
251
252 set_t *
set_reverse_difference(set_t * dst,const set_t * src)253 set_reverse_difference (set_t *dst, const set_t *src)
254 {
255 if (dst->inverted && src->inverted) {
256 dst->inverted = 0;
257 return _set_difference (dst, src);
258 } else if (src->inverted) {
259 dst->inverted = 1;
260 return _set_union (dst, src);
261 } else if (dst->inverted) {
262 dst->inverted = 0;
263 return _set_intersection (dst, src);
264 } else {
265 return _set_reverse_difference (dst, src);
266 }
267 }
268
269 set_t *
set_assign(set_t * dst,const set_t * src)270 set_assign (set_t *dst, const set_t *src)
271 {
272 unsigned size;
273 unsigned i;
274
275 size = max (dst->size, src->size);
276 set_expand (dst, size);
277 dst->inverted = src->inverted;
278 for (i = 0; i < src->size / BITS; i++)
279 dst->map[i] = src->map[i];
280 for ( ; i < dst->size / BITS; i++)
281 dst->map[i] = 0;
282 return dst;
283 }
284
285 set_t *
set_empty(set_t * set)286 set_empty (set_t *set)
287 {
288 unsigned i;
289
290 set->inverted = 0;
291 for (i = 0; i < set->size / BITS; i++)
292 set->map[i] = 0;
293 return set;
294 }
295
296 set_t *
set_everything(set_t * set)297 set_everything (set_t *set)
298 {
299 unsigned i;
300
301 set->inverted = 1;
302 for (i = 0; i < set->size / BITS; i++)
303 set->map[i] = 0;
304 return set;
305 }
306
307 static inline int
_set_is_empty(const set_t * set)308 _set_is_empty (const set_t *set)
309 {
310 unsigned i;
311
312 for (i = 0; i < set->size / BITS; i++)
313 if (set->map[i])
314 return 0;
315 return 1;
316 }
317
318 int
set_is_empty(const set_t * set)319 set_is_empty (const set_t *set)
320 {
321 if (set->inverted)
322 return 0;
323 return _set_is_empty (set);
324 }
325
326 int
set_is_everything(const set_t * set)327 set_is_everything (const set_t *set)
328 {
329 if (!set->inverted)
330 return 0;
331 return _set_is_empty (set);
332 }
333
334 static int
set_test_n_n(const set_t * s1,const set_t * s2)335 set_test_n_n (const set_t *s1, const set_t *s2)
336 {
337 unsigned i, end;
338 unsigned intersection = 0;
339 unsigned difference = 0;
340
341 end = min (s1->size, s2->size) / BITS;
342 for (i = 0; i < end; i++) {
343 unsigned m1 = s1->map[i];
344 unsigned m2 = s2->map[i];
345
346 intersection |= m1 & m2;
347 difference |= m1 ^ m2;
348 }
349 for ( ; i < s1->size / BITS; i++) {
350 difference |= s1->map[i];
351 }
352 for ( ; i < s2->size / BITS; i++) {
353 difference |= s2->map[i];
354 }
355 return (difference != 0) | ((intersection != 0) << 1);
356 }
357
358 static int
set_test_n_i(const set_t * s1,const set_t * s2)359 set_test_n_i (const set_t *s1, const set_t *s2)
360 {
361 unsigned i, end;
362 unsigned intersection = 0;
363 unsigned difference = 0;
364
365 end = min (s1->size, s2->size) / BITS;
366 for (i = 0; i < end; i++) {
367 unsigned m1 = s1->map[i];
368 unsigned m2 = ~s2->map[i];
369
370 intersection |= m1 & m2;
371 difference |= m1 ^ m2;
372 }
373 for ( ; i < s1->size / BITS; i++) {
374 intersection |= s1->map[i];
375 difference |= ~s1->map[i];
376 }
377 for ( ; i < s2->size / BITS; i++) {
378 difference |= ~s2->map[i];
379 }
380 return (difference != 0) | ((intersection != 0) << 1);
381 }
382
383 static int
set_test_i_n(const set_t * s1,const set_t * s2)384 set_test_i_n (const set_t *s1, const set_t *s2)
385 {
386 unsigned i, end;
387 unsigned intersection = 0;
388 unsigned difference = 0;
389
390 end = min (s1->size, s2->size) / BITS;
391 for (i = 0; i < end; i++) {
392 unsigned m1 = ~s1->map[i];
393 unsigned m2 = s2->map[i];
394
395 intersection |= m1 & m2;
396 difference |= m1 ^ m2;
397 }
398 for ( ; i < s1->size / BITS; i++) {
399 difference |= ~s1->map[i];
400 }
401 for ( ; i < s2->size / BITS; i++) {
402 intersection |= s2->map[i];
403 difference |= ~s2->map[i];
404 }
405 return (difference != 0) | ((intersection != 0) << 1);
406 }
407
408 static int
set_test_i_i(const set_t * s1,const set_t * s2)409 set_test_i_i (const set_t *s1, const set_t *s2)
410 {
411 unsigned i, end;
412 unsigned intersection = 0;
413 unsigned difference = 0;
414
415 end = min (s1->size, s2->size) / BITS;
416 for (i = 0; i < end; i++) {
417 unsigned m1 = ~s1->map[i];
418 unsigned m2 = ~s2->map[i];
419
420 intersection |= m1 & m2;
421 difference |= m1 ^ m2;
422 }
423 for ( ; i < s1->size / BITS; i++) {
424 difference |= ~s1->map[i];
425 }
426 for ( ; i < s2->size / BITS; i++) {
427 intersection |= s2->map[i];
428 difference |= ~s2->map[i];
429 }
430 intersection |= ~0; // two inverted sets can never be disjoint
431 return (difference != 0) | ((intersection != 0) << 1);
432 }
433
434 static int
set_test(const set_t * s1,const set_t * s2)435 set_test (const set_t *s1, const set_t *s2)
436 {
437 if (s1->inverted && s2->inverted)
438 return set_test_i_i (s1, s2);
439 else if (s2->inverted)
440 return set_test_n_i (s1, s2);
441 else if (s1->inverted)
442 return set_test_i_n (s1, s2);
443 else
444 return set_test_n_n (s1, s2);
445 }
446
447 int
set_is_disjoint(const set_t * s1,const set_t * s2)448 set_is_disjoint (const set_t *s1, const set_t *s2)
449 {
450 return !(set_test (s1, s2) & 2);
451 }
452
453 int
set_is_intersecting(const set_t * s1,const set_t * s2)454 set_is_intersecting (const set_t *s1, const set_t *s2)
455 {
456 return !!(set_test (s1, s2) & 2);
457 }
458
459 int
set_is_equivalent(const set_t * s1,const set_t * s2)460 set_is_equivalent (const set_t *s1, const set_t *s2)
461 {
462 return !(set_test (s1, s2) & 1);
463 }
464
465 int
set_is_subset(const set_t * set,const set_t * sub)466 set_is_subset (const set_t *set, const set_t *sub)
467 {
468 unsigned i, end;
469
470 end = min (set->size, sub->size) / BITS;
471 if (set->inverted && sub->inverted) {
472 for (i = 0; i < end; i++) {
473 if (~sub->map[i] & set->map[i])
474 return 0;
475 }
476 for ( ; i < set->size / BITS; i++)
477 if (set->map[i])
478 return 0;
479 } else if (set->inverted) {
480 for (i = 0; i < end; i++) {
481 if (sub->map[i] & set->map[i])
482 return 0;
483 }
484 } else if (sub->inverted) {
485 // an inverted set cannot be a subset of a set that is not inverted
486 return 0;
487 } else {
488 for (i = 0; i < end; i++) {
489 if (sub->map[i] & ~set->map[i])
490 return 0;
491 }
492 for ( ; i < sub->size / BITS; i++)
493 if (sub->map[i])
494 return 0;
495 }
496 return 1;
497 }
498
499 static inline int
_set_is_member(const set_t * set,unsigned x)500 _set_is_member (const set_t *set, unsigned x)
501 {
502 if (x >= set->size)
503 return 0;
504 return (set->map[x / BITS] & (1 << (x % BITS))) != 0;
505 }
506
507 int
set_is_member(const set_t * set,unsigned x)508 set_is_member (const set_t *set, unsigned x)
509 {
510 if (set->inverted)
511 return !_set_is_member (set, x);
512 return _set_is_member (set, x);
513 }
514
515 unsigned
set_size(const set_t * set)516 set_size (const set_t *set)
517 {
518 unsigned count = 0;
519 unsigned i;
520
521 for (i = 0; i < set->size; i++)
522 if (_set_is_member (set, i))
523 count++;
524 return count;
525 }
526
527 set_iter_t *
set_first(const set_t * set)528 set_first (const set_t *set)
529 {
530 unsigned x;
531 set_iter_t *set_iter;
532
533 for (x = 0; x < set->size; x++) {
534 if (_set_is_member (set, x)) {
535 set_iter = new_setiter ();
536 set_iter->set = set;
537 set_iter->element = x;
538 return set_iter;
539 }
540 }
541 return 0;
542 }
543
544 set_iter_t *
set_next(set_iter_t * set_iter)545 set_next (set_iter_t *set_iter)
546 {
547 unsigned x;
548
549 for (x = set_iter->element + 1; x < set_iter->set->size; x++) {
550 if (_set_is_member (set_iter->set, x)) {
551 set_iter->element = x;
552 return set_iter;
553 }
554 }
555 delete_setiter (set_iter);
556 return 0;
557 }
558
559 const char *
set_as_string(const set_t * set)560 set_as_string (const set_t *set)
561 {
562 static dstring_t *str;
563 unsigned i;
564
565 if (!str)
566 str = dstring_new ();
567 if (set_is_empty (set)) {
568 dstring_copystr (str, "{}");
569 return str->str;
570 }
571 if (set_is_everything (set)) {
572 dstring_copystr (str, "{...}");
573 return str->str;
574 }
575 dstring_copystr (str, "{");
576 for (i = 0; i < set->size; i++) {
577 if (set_is_member (set, i)) {
578 if (str->str[1])
579 dasprintf (str, " %d", i);
580 else
581 dasprintf (str, "%d", i);
582 }
583 }
584 if (set->inverted)
585 dasprintf (str, "%s%d ...", str->str[1] ? " " : "", i);
586 dstring_appendstr (str, "}");
587 return str->str;
588 }
589