1 /********************************************************************/
2 /* */
3 /* set_rtl.c Primitive actions for the set type. */
4 /* Copyright (C) 1989 - 2019 Thomas Mertes */
5 /* */
6 /* This file is part of the Seed7 Runtime Library. */
7 /* */
8 /* The Seed7 Runtime Library is free software; you can */
9 /* redistribute it and/or modify it under the terms of the GNU */
10 /* Lesser General Public License as published by the Free Software */
11 /* Foundation; either version 2.1 of the License, or (at your */
12 /* option) any later version. */
13 /* */
14 /* The Seed7 Runtime Library is distributed in the hope that it */
15 /* will be useful, but WITHOUT ANY WARRANTY; without even the */
16 /* implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR */
17 /* PURPOSE. See the GNU Lesser General Public License for more */
18 /* details. */
19 /* */
20 /* You should have received a copy of the GNU Lesser General */
21 /* Public License along with this program; if not, write to the */
22 /* Free Software Foundation, Inc., 51 Franklin Street, */
23 /* Fifth Floor, Boston, MA 02110-1301, USA. */
24 /* */
25 /* Module: Seed7 Runtime Library */
26 /* File: seed7/src/set_rtl.c */
27 /* Changes: 2004, 2005, 2010, 2012 - 2014 Thomas Mertes */
28 /* Content: Primitive actions for the set type. */
29 /* */
30 /********************************************************************/
31
32 #define LOG_FUNCTIONS 0
33 #define VERBOSE_EXCEPTIONS 0
34
35 #include "version.h"
36
37 #include "stdlib.h"
38 #include "stdio.h"
39 #include "string.h"
40 #include "limits.h"
41
42 #include "common.h"
43 #include "data_rtl.h"
44 #include "heaputl.h"
45 #include "rtl_err.h"
46 #include "int_rtl.h"
47
48 #undef EXTERN
49 #define EXTERN
50 #include "set_rtl.h"
51
52
53
54 /**
55 * Determine the number of one bits in a bitset.
56 * The function uses a combination of sideways additions and
57 * a multiplication to count the bits set in a bitset element.
58 * @return the number of one bits.
59 */
bitsetPopulation(bitSetType bitset)60 static inline uintType bitsetPopulation (bitSetType bitset)
61
62 { /* bitsetPopulation */
63 #if BITSETTYPE_SIZE == 32
64 bitset -= (bitset >> 1) & UINT32_SUFFIX(0x55555555);
65 bitset = (bitset & UINT32_SUFFIX(0x33333333)) +
66 ((bitset >> 2) & UINT32_SUFFIX(0x33333333));
67 bitset = (bitset + (bitset >> 4)) & UINT32_SUFFIX(0x0f0f0f0f);
68 return (uintType) ((bitset * UINT32_SUFFIX(0x01010101)) >> 24);
69 #elif BITSETTYPE_SIZE == 64
70 bitset -= (bitset >> 1) & UINT64_SUFFIX(0x5555555555555555);
71 bitset = (bitset & UINT64_SUFFIX(0x3333333333333333)) +
72 ((bitset >> 2) & UINT64_SUFFIX(0x3333333333333333));
73 bitset = (bitset + (bitset >> 4)) & UINT64_SUFFIX(0x0f0f0f0f0f0f0f0f);
74 return (uintType) ((bitset * UINT64_SUFFIX(0x0101010101010101)) >> 56);
75 #endif
76 } /* bitsetPopulation */
77
78
79
80 /**
81 * Find a a non-zero bitSet in an array of bitSets.
82 * This function uses loop unrolling inspired by Duff's device.
83 * @return a pointer to the non-zero bitSet or NULL if there was none.
84 */
bitsetNonZero(register const bitSetType * bitset,const memSizeType len)85 static inline const bitSetType *bitsetNonZero (register const bitSetType *bitset,
86 const memSizeType len)
87
88 {
89 register memSizeType blockCount;
90
91 /* bitsetNonZero */
92 if (len != 0) {
93 blockCount = (len + 31) >> 5;
94 switch (len & 31) {
95 case 0: do { if (unlikely(*bitset != 0)) return bitset; bitset++;
96 case 31: if (unlikely(*bitset != 0)) return bitset; bitset++;
97 case 30: if (unlikely(*bitset != 0)) return bitset; bitset++;
98 case 29: if (unlikely(*bitset != 0)) return bitset; bitset++;
99 case 28: if (unlikely(*bitset != 0)) return bitset; bitset++;
100 case 27: if (unlikely(*bitset != 0)) return bitset; bitset++;
101 case 26: if (unlikely(*bitset != 0)) return bitset; bitset++;
102 case 25: if (unlikely(*bitset != 0)) return bitset; bitset++;
103 case 24: if (unlikely(*bitset != 0)) return bitset; bitset++;
104 case 23: if (unlikely(*bitset != 0)) return bitset; bitset++;
105 case 22: if (unlikely(*bitset != 0)) return bitset; bitset++;
106 case 21: if (unlikely(*bitset != 0)) return bitset; bitset++;
107 case 20: if (unlikely(*bitset != 0)) return bitset; bitset++;
108 case 19: if (unlikely(*bitset != 0)) return bitset; bitset++;
109 case 18: if (unlikely(*bitset != 0)) return bitset; bitset++;
110 case 17: if (unlikely(*bitset != 0)) return bitset; bitset++;
111 case 16: if (unlikely(*bitset != 0)) return bitset; bitset++;
112 case 15: if (unlikely(*bitset != 0)) return bitset; bitset++;
113 case 14: if (unlikely(*bitset != 0)) return bitset; bitset++;
114 case 13: if (unlikely(*bitset != 0)) return bitset; bitset++;
115 case 12: if (unlikely(*bitset != 0)) return bitset; bitset++;
116 case 11: if (unlikely(*bitset != 0)) return bitset; bitset++;
117 case 10: if (unlikely(*bitset != 0)) return bitset; bitset++;
118 case 9: if (unlikely(*bitset != 0)) return bitset; bitset++;
119 case 8: if (unlikely(*bitset != 0)) return bitset; bitset++;
120 case 7: if (unlikely(*bitset != 0)) return bitset; bitset++;
121 case 6: if (unlikely(*bitset != 0)) return bitset; bitset++;
122 case 5: if (unlikely(*bitset != 0)) return bitset; bitset++;
123 case 4: if (unlikely(*bitset != 0)) return bitset; bitset++;
124 case 3: if (unlikely(*bitset != 0)) return bitset; bitset++;
125 case 2: if (unlikely(*bitset != 0)) return bitset; bitset++;
126 case 1: if (unlikely(*bitset != 0)) return bitset; bitset++;
127 } while (--blockCount > 0);
128 } /* switch */
129 } /* if */
130 return NULL;
131 } /* bitsetNonZero */
132
133
134
setArrlit(const_rtlArrayType arr1)135 setType setArrlit (const_rtlArrayType arr1)
136
137 {
138 memSizeType length;
139 intType number;
140 intType position;
141 unsigned int bit_index;
142 memSizeType array_index;
143 setType result;
144
145 /* setArrlit */
146 length = arraySize(arr1);
147 if (unlikely(!ALLOC_SET(result, 1))) {
148 raise_error(MEMORY_ERROR);
149 return NULL;
150 } else {
151 if (length == 0) {
152 result->min_position = 0;
153 result->max_position = 0;
154 result->bitset[0] = (bitSetType) 0;
155 } else {
156 number = arr1->arr[0].value.intValue;
157 position = bitset_pos(number);
158 result->min_position = position;
159 result->max_position = position;
160 bit_index = ((unsigned int) number) & bitset_mask;
161 result->bitset[0] = (bitSetType) 1 << bit_index;
162 for (array_index = 1; array_index < length; array_index++) {
163 setIncl(&result, arr1->arr[array_index].value.intValue);
164 #ifdef OUT_OF_ORDER
165 if (fail_flag) {
166 FREE_SET(result, bitsetSize(result));
167 return fail_value;
168 } /* if */
169 #endif
170 } /* for */
171 } /* if */
172 return result;
173 } /* if */
174 } /* setArrlit */
175
176
177
setBaselit(const intType number)178 setType setBaselit (const intType number)
179
180 {
181 intType position;
182 unsigned int bit_index;
183 setType result;
184
185 /* setBaselit */
186 if (unlikely(!ALLOC_SET(result, 1))) {
187 raise_error(MEMORY_ERROR);
188 return NULL;
189 } else {
190 position = bitset_pos(number);
191 result->min_position = position;
192 result->max_position = position;
193 bit_index = ((unsigned int) number) & bitset_mask;
194 result->bitset[0] = (bitSetType) 1 << bit_index;
195 return result;
196 } /* if */
197 } /* setBaselit */
198
199
200
201 /**
202 * Compute the cardinality of a set.
203 * The function is based on the function bitsetPopulation, which
204 * uses a combination of sideways additions and a multiplication
205 * to count the bits set in a bitset element.
206 * @return the number of elements in 'aSet'.
207 * @exception RANGE_ERROR Result does not fit into an integer.
208 */
setCard(const const_setType aSet)209 intType setCard (const const_setType aSet)
210
211 {
212 memSizeType index_beyond;
213 memSizeType bitset_index;
214 bitSetType bitset;
215 uintType card = 0;
216 intType cardinality;
217
218 /* setCard */
219 index_beyond = bitsetSize(aSet);
220 for (bitset_index = index_beyond; bitset_index > 0; bitset_index--) {
221 bitset = aSet->bitset[bitset_index - 1];
222 card += bitsetPopulation(bitset);
223 } /* for */
224 if (unlikely(card > INTTYPE_MAX)) {
225 logError(printf("setCard(): Result does not fit into an integer.\n"););
226 raise_error(RANGE_ERROR);
227 cardinality = 0;
228 } else {
229 cardinality = (intType) card;
230 } /* if */
231 logFunction(printf("setCard --> " FMT_D "\n", cardinality););
232 return cardinality;
233 } /* setCard */
234
235
236
237 /**
238 * Compares two sets to make them useable as key in a hash table.
239 * The sets are compared by determining the biggest element that is
240 * not present or absent in both sets. The set in which this element
241 * is not present is the smaller one. Note that the set comparison
242 * is not related to the concepts of subset or superset. With the
243 * comparison function setCmp it is possible to sort an array of
244 * sets or to use sets as key in a hash table. The functions
245 * setIsSubset and setIsProperSubset are used to check if a set is
246 * a (proper) subset or superset of another set.
247 * @return -1, 0 or 1 if the first argument is considered to be
248 * respectively less than, equal to, or greater than the
249 * second.
250 */
setCmp(const const_setType set1,const const_setType set2)251 intType setCmp (const const_setType set1, const const_setType set2)
252
253 {
254 memSizeType index_beyond;
255 memSizeType bitset_index;
256 memSizeType size;
257 const bitSetType *bitset1;
258 const bitSetType *bitset2;
259
260 /* setCmp */
261 if (set1->max_position >= set2->max_position) {
262 if (set1->min_position > set2->max_position) {
263 bitset_index = 0;
264 size = 0;
265 bitset1 = NULL;
266 bitset2 = NULL;
267 } else {
268 bitset_index = bitsetIndex(set1, set2->max_position + 1);
269 if (set1->min_position >= set2->min_position) {
270 size = bitset_index;
271 } else {
272 size = bitsetSize(set2);
273 } /* if */
274 bitset1 = &set1->bitset[bitset_index - 1];
275 bitset2 = &set2->bitset[set2->max_position - set2->min_position];
276 } /* if */
277 index_beyond = bitsetSize(set1);
278 for (; bitset_index < index_beyond; bitset_index++) {
279 if (set1->bitset[bitset_index] != 0) {
280 return 1;
281 } /* if */
282 } /* for */
283 } else {
284 if (set1->max_position < set2->min_position) {
285 bitset_index = 0;
286 size = 0;
287 bitset1 = NULL;
288 bitset2 = NULL;
289 } else {
290 bitset_index = bitsetIndex(set2, set1->max_position + 1);
291 if (set1->min_position <= set2->min_position) {
292 size = bitset_index;
293 } else {
294 size = bitsetSize(set1);
295 } /* if */
296 bitset1 = &set1->bitset[set1->max_position - set1->min_position];
297 bitset2 = &set2->bitset[bitset_index - 1];
298 } /* if */
299 index_beyond = bitsetSize(set2);
300 for (; bitset_index < index_beyond; bitset_index++) {
301 if (set2->bitset[bitset_index] != 0) {
302 return -1;
303 } /* if */
304 } /* for */
305 } /* if */
306 for (bitset_index = 0; bitset_index < size; bitset_index++, bitset1--, bitset2--) {
307 if (*bitset1 != *bitset2) {
308 if (*bitset1 > *bitset2) {
309 return 1;
310 } else {
311 return -1;
312 } /* if */
313 } /* if */
314 } /* for */
315 if (set1->min_position < set2->min_position) {
316 if (set1->max_position < set2->min_position) {
317 index_beyond = bitsetSize(set1);
318 } else {
319 index_beyond = bitsetIndex(set1, set2->min_position);
320 } /* if */
321 for (bitset_index = 0; bitset_index < index_beyond; bitset_index++) {
322 if (set1->bitset[bitset_index] != 0) {
323 return 1;
324 } /* if */
325 } /* for */
326 } else if (set1->min_position > set2->min_position) {
327 if (set1->min_position > set2->max_position) {
328 index_beyond = bitsetSize(set2);
329 } else {
330 index_beyond = bitsetIndex(set2, set1->min_position);
331 } /* if */
332 for (bitset_index = 0; bitset_index < index_beyond; bitset_index++) {
333 if (set2->bitset[bitset_index] != 0) {
334 return -1;
335 } /* if */
336 } /* for */
337 } /* if */
338 return 0;
339 } /* setCmp */
340
341
342
343 /**
344 * Reinterpret the generic parameters as setType and call setCmp.
345 * Function pointers in C programs generated by the Seed7 compiler
346 * may point to this function. This assures correct behaviour even
347 * if sizeof(genericType) != sizeof(setType).
348 * @return -1, 0 or 1 if the first argument is considered to be
349 * respectively less than, equal to, or greater than the
350 * second.
351 */
setCmpGeneric(const genericType value1,const genericType value2)352 intType setCmpGeneric (const genericType value1, const genericType value2)
353
354 { /* setCmpGeneric */
355 return setCmp(((const_rtlObjectType *) &value1)->value.setValue,
356 ((const_rtlObjectType *) &value2)->value.setValue);
357 } /* setCmpGeneric */
358
359
360
361 /**
362 * Assign source to *dest.
363 * A copy function assumes that *dest contains a legal value.
364 * @exception MEMORY_ERROR Not enough memory to create dest.
365 */
setCpy(setType * const dest,const const_setType source)366 void setCpy (setType *const dest, const const_setType source)
367
368 {
369 setType set_dest;
370 memSizeType set_dest_size;
371 memSizeType set_source_size;
372
373 /* setCpy */
374 set_dest = *dest;
375 set_source_size = bitsetSize(source);
376 if (set_dest->min_position != source->min_position ||
377 set_dest->max_position != source->max_position) {
378 set_dest_size = bitsetSize(set_dest);
379 if (set_dest_size != set_source_size) {
380 if (unlikely(!ALLOC_SET(set_dest, set_source_size))) {
381 raise_error(MEMORY_ERROR);
382 return;
383 } else {
384 FREE_SET(*dest, set_dest_size);
385 *dest = set_dest;
386 } /* if */
387 } /* if */
388 set_dest->min_position = source->min_position;
389 set_dest->max_position = source->max_position;
390 } /* if */
391 /* It is possible that *dest == source holds. The */
392 /* behavior of memcpy() is undefined if source and */
393 /* destination areas overlap (or are identical). */
394 /* Therefore memmove() is used instead of memcpy(). */
395 memmove(set_dest->bitset, source->bitset,
396 (size_t) set_source_size * sizeof(bitSetType));
397 } /* setCpy */
398
399
400
401 /**
402 * Reinterpret the generic parameters as setType and call setCpy.
403 * Function pointers in C programs generated by the Seed7 compiler
404 * may point to this function. This assures correct behaviour even
405 * if sizeof(genericType) != sizeof(setType).
406 */
setCpyGeneric(genericType * const dest,const genericType source)407 void setCpyGeneric (genericType *const dest, const genericType source)
408
409 { /* setCpyGeneric */
410 setCpy(&((rtlObjectType *) dest)->value.setValue,
411 ((const_rtlObjectType *) &source)->value.setValue);
412 } /* setCpyGeneric */
413
414
415
416 /**
417 * Return a copy of source, that can be assigned to a new destination.
418 * It is assumed that the destination of the assignment is undefined.
419 * Create functions can be used to initialize Seed7 constants.
420 * @return a copy of source.
421 * @exception MEMORY_ERROR Not enough memory to represent the result.
422 */
setCreate(const const_setType source)423 setType setCreate (const const_setType source)
424
425 {
426 memSizeType new_size;
427 setType result;
428
429 /* setCreate */
430 new_size = bitsetSize(source);
431 if (unlikely(!ALLOC_SET(result, new_size))) {
432 raise_error(MEMORY_ERROR);
433 } else {
434 result->min_position = source->min_position;
435 result->max_position = source->max_position;
436 memcpy(result->bitset, source->bitset,
437 (size_t) new_size * sizeof(bitSetType));
438 } /* if */
439 return result;
440 } /* setCreate */
441
442
443
444 /**
445 * Generic Create function to be used via function pointers.
446 * Function pointers in C programs generated by the Seed7 compiler
447 * may point to this function. This assures correct behaviour even
448 * if sizeof(genericType) != sizeof(setType).
449 */
setCreateGeneric(const genericType from_value)450 genericType setCreateGeneric (const genericType from_value)
451
452 {
453 rtlObjectType result;
454
455 /* setCreateGeneric */
456 INIT_GENERIC_PTR(result.value.genericValue);
457 result.value.setValue =
458 setCreate(((const_rtlObjectType *) &from_value)->value.setValue);
459 return result.value.genericValue;
460 } /* setCreateGeneric */
461
462
463
464 /**
465 * Free the memory referred by 'old_set'.
466 * After setDestr is left 'old_set' refers to not existing memory.
467 * The memory where 'old_set' is stored can be freed afterwards.
468 */
setDestr(const const_setType old_set)469 void setDestr (const const_setType old_set)
470
471 { /* setDestr */
472 if (old_set != NULL) {
473 FREE_SET(old_set, bitsetSize(old_set));
474 } /* if */
475 } /* setDestr */
476
477
478
479 /**
480 * Generic Destr function to be used via function pointers.
481 * Function pointers in C programs generated by the Seed7 compiler
482 * may point to this function. This assures correct behaviour even
483 * if sizeof(genericType) != sizeof(setType).
484 */
setDestrGeneric(const genericType old_value)485 void setDestrGeneric (const genericType old_value)
486
487 { /* setDestrGeneric */
488 setDestr(((const_rtlObjectType *) &old_value)->value.setValue);
489 } /* setDestrGeneric */
490
491
492
493 /**
494 * Difference of two sets.
495 * @return the difference of the two sets.
496 * @exception MEMORY_ERROR Not enough memory for the result.
497 */
setDiff(const const_setType set1,const const_setType set2)498 setType setDiff (const const_setType set1, const const_setType set2)
499
500 {
501 memSizeType bitset_index;
502 memSizeType bitset_index2;
503 memSizeType index_beyond;
504 setType difference;
505
506 /* setDiff */
507 logFunction(printf("setDiff(");
508 prot_set(set1);
509 printf(", ");
510 prot_set(set2);
511 printf(")\n"););
512 if (unlikely(!ALLOC_SET(difference, bitsetSize(set1)))) {
513 raise_error(MEMORY_ERROR);
514 } else {
515 difference->min_position = set1->min_position;
516 difference->max_position = set1->max_position;
517 if (set1->max_position < set2->min_position ||
518 set1->min_position > set2->max_position) {
519 memcpy(difference->bitset, set1->bitset, bitsetSize(set1) * sizeof(bitSetType));
520 } else {
521 if (set2->min_position > set1->min_position) {
522 bitset_index = bitsetIndex(set1, set2->min_position);
523 bitset_index2 = 0;
524 memcpy(difference->bitset, set1->bitset, bitset_index * sizeof(bitSetType));
525 } else {
526 bitset_index = 0;
527 bitset_index2 = bitsetIndex(set2, set1->min_position);
528 } /* if */
529 if (set1->max_position > set2->max_position) {
530 index_beyond = bitsetIndex(set1, set2->max_position + 1);
531 memcpy(&difference->bitset[index_beyond], &set1->bitset[index_beyond],
532 (size_t) (uintType) (set1->max_position - set2->max_position) *
533 sizeof(bitSetType));
534 } else {
535 index_beyond = bitsetSize(set1);
536 } /* if */
537 for (; bitset_index < index_beyond; bitset_index++, bitset_index2++) {
538 difference->bitset[bitset_index] = set1->bitset[bitset_index] &
539 ~ set2->bitset[bitset_index2];
540 } /* for */
541 } /* if */
542 } /* if */
543 logFunction(printf("setDiff --> ");
544 prot_set(difference);
545 printf("\n"););
546 return difference;
547 } /* setDiff */
548
549
550
551 /**
552 * Assign the difference of *dest and delta to *dest.
553 * @exception MEMORY_ERROR Not enough memory to create dest.
554 */
setDiffAssign(setType * const dest,const const_setType delta)555 void setDiffAssign (setType *const dest, const const_setType delta)
556
557 {
558 setType set1;
559 intType min_position;
560 intType max_position;
561 intType position;
562 setType new_set1;
563
564 /* setDiffAssign */
565 logFunction(printf("setDiffAssign(");
566 prot_set(*dest);
567 printf(", ");
568 prot_set(delta);
569 printf(")\n"););
570 set1 = *dest;
571 min_position = set1->min_position;
572 max_position = set1->max_position;
573 while (min_position <= max_position &&
574 (set1->bitset[min_position - set1->min_position] == 0 ||
575 (min_position >= delta->min_position &&
576 min_position <= delta->max_position &&
577 (set1->bitset[min_position - set1->min_position] &
578 ~ delta->bitset[min_position - delta->min_position]) == 0))) {
579 min_position++;
580 } /* while */
581 while (min_position <= max_position &&
582 (set1->bitset[max_position - set1->min_position] == 0 ||
583 (max_position >= delta->min_position &&
584 max_position <= delta->max_position &&
585 (set1->bitset[max_position - set1->min_position] &
586 ~ delta->bitset[max_position - delta->min_position]) == 0))) {
587 max_position--;
588 } /* while */
589 if (min_position > max_position) {
590 new_set1 = REALLOC_SET(set1, bitsetSize(set1), 1);
591 if (unlikely(new_set1 == NULL)) {
592 /* Strange case if a 'realloc', which shrinks memory, fails. */
593 /* The destination set stays unchanged. */
594 raise_error(MEMORY_ERROR);
595 } else {
596 new_set1->min_position = 0;
597 new_set1->max_position = 0;
598 new_set1->bitset[0] = (bitSetType) 0;
599 *dest = new_set1;
600 } /* if */
601 } else if (min_position == set1->min_position) {
602 if (max_position != set1->max_position) {
603 new_set1 = REALLOC_SET(set1, bitsetSize(set1), bitsetSize2(min_position, max_position));
604 if (unlikely(new_set1 == NULL)) {
605 /* Strange case if a 'realloc', which shrinks memory, fails. */
606 /* The destination set stays unchanged. */
607 raise_error(MEMORY_ERROR);
608 return;
609 } else {
610 set1 = new_set1;
611 set1->max_position = max_position;
612 *dest = set1;
613 } /* if */
614 } /* if */
615 for (position = min_position; position <= max_position; position++) {
616 if (position >= delta->min_position &&
617 position <= delta->max_position) {
618 set1->bitset[position - min_position] &=
619 ~ delta->bitset[position - delta->min_position];
620 } /* if */
621 } /* for */
622 } else {
623 for (position = min_position; position <= max_position; position++) {
624 if (position >= delta->min_position &&
625 position <= delta->max_position) {
626 set1->bitset[position - min_position] =
627 set1->bitset[position - set1->min_position] &
628 ~ delta->bitset[position - delta->min_position];
629 } else {
630 set1->bitset[position - min_position] =
631 set1->bitset[position - set1->min_position];
632 } /* if */
633 } /* for */
634 new_set1 = REALLOC_SET(set1, bitsetSize(set1), bitsetSize2(min_position, max_position));
635 if (unlikely(new_set1 == NULL)) {
636 /* Strange case if a 'realloc', which shrinks memory, fails. */
637 /* Deliver the result in the original set (that is too big). */
638 set1->min_position = min_position;
639 set1->max_position = max_position;
640 raise_error(MEMORY_ERROR);
641 } else {
642 new_set1->min_position = min_position;
643 new_set1->max_position = max_position;
644 *dest = new_set1;
645 } /* if */
646 } /* if */
647 logFunction(printf("setDiffAssign --> ");
648 prot_set(*dest);
649 printf("\n"););
650 } /* setDiffAssign */
651
652
653
654 /**
655 * Set membership test.
656 * Determine if 'number' is a member of the set 'aSet'.
657 * @return TRUE if 'number' is a member of 'aSet',
658 * FALSE otherwise.
659 */
setElem(const intType number,const const_setType aSet)660 boolType setElem (const intType number, const const_setType aSet)
661
662 {
663 intType position;
664 memSizeType bitset_index;
665 unsigned int bit_index;
666
667 /* setElem */
668 position = bitset_pos(number);
669 if (position >= aSet->min_position && position <= aSet->max_position) {
670 bitset_index = bitsetIndex(aSet, position);
671 bit_index = ((unsigned int) number) & bitset_mask;
672 if (aSet->bitset[bitset_index] & (bitSetType) 1 << bit_index) {
673 return TRUE;
674 } else {
675 return FALSE;
676 } /* if */
677 } else {
678 return FALSE;
679 } /* if */
680 } /* setElem */
681
682
683
684 /**
685 * Check if two sets are equal.
686 * @return TRUE if the two sets are equal,
687 * FALSE otherwise.
688 */
setEq(const const_setType set1,const const_setType set2)689 boolType setEq (const const_setType set1, const const_setType set2)
690
691 {
692 memSizeType index_beyond;
693 memSizeType bitset_index;
694 memSizeType size;
695 const bitSetType *bitset1;
696 const bitSetType *bitset2;
697
698 /* setEq */
699 logFunction(printf("setEq(");
700 prot_set(set1);
701 printf(", ");
702 prot_set(set2);
703 printf(")\n"););
704 if (set1->min_position == set2->min_position &&
705 set1->max_position == set2->max_position) {
706 return memcmp(set1->bitset, set2->bitset,
707 bitsetSize(set1) * sizeof(bitSetType)) == 0;
708 } else {
709 if (set1->min_position < set2->min_position) {
710 if (set1->max_position < set2->min_position) {
711 size = 0;
712 index_beyond = bitsetSize(set1);
713 bitset1 = NULL;
714 bitset2 = NULL;
715 } else {
716 if (set1->max_position <= set2->max_position) {
717 size = bitsetIndex(set2, set1->max_position + 1);
718 } else {
719 size = bitsetSize(set2);
720 } /* if */
721 index_beyond = bitsetIndex(set1, set2->min_position);
722 bitset1 = &set1->bitset[index_beyond];
723 bitset2 = set2->bitset;
724 } /* if */
725 for (bitset_index = 0; bitset_index < index_beyond; bitset_index++) {
726 if (set1->bitset[bitset_index] != 0) {
727 return FALSE;
728 } /* if */
729 } /* for */
730 } else {
731 if (set1->min_position > set2->max_position) {
732 size = 0;
733 index_beyond = bitsetSize(set2);
734 bitset1 = NULL;
735 bitset2 = NULL;
736 } else {
737 if (set1->max_position >= set2->max_position) {
738 size = bitsetIndex(set1, set2->max_position + 1);
739 } else {
740 size = bitsetSize(set1);
741 } /* if */
742 index_beyond = bitsetIndex(set2, set1->min_position);
743 bitset1 = set1->bitset;
744 bitset2 = &set2->bitset[index_beyond];
745 } /* if */
746 for (bitset_index = 0; bitset_index < index_beyond; bitset_index++) {
747 if (set2->bitset[bitset_index] != 0) {
748 return FALSE;
749 } /* if */
750 } /* for */
751 } /* if */
752 if (set1->max_position > set2->max_position) {
753 if (set1->min_position > set2->max_position) {
754 bitset_index = 0;
755 } else {
756 bitset_index = bitsetIndex(set1, set2->max_position + 1);
757 } /* if */
758 index_beyond = bitsetSize(set1);
759 for (; bitset_index < index_beyond; bitset_index++) {
760 if (set1->bitset[bitset_index] != 0) {
761 return FALSE;
762 } /* if */
763 } /* for */
764 } else {
765 if (set1->max_position < set2->min_position) {
766 bitset_index = 0;
767 } else {
768 bitset_index = bitsetIndex(set2, set1->max_position + 1);
769 } /* if */
770 index_beyond = bitsetSize(set2);
771 for (; bitset_index < index_beyond; bitset_index++) {
772 if (set2->bitset[bitset_index] != 0) {
773 return FALSE;
774 } /* if */
775 } /* for */
776 } /* if */
777 /* 'bitset1' and 'bitset2' might be NULL. In this case 'size' is 0. */
778 /* According to the specification memcmp() returns 0 when size is 0. */
779 return memcmp(bitset1, bitset2, size * sizeof(bitSetType)) == 0;
780 } /* if */
781 } /* setEq */
782
783
784
785 /**
786 * Remove 'number' from the set 'set_to'.
787 * If 'number' is not element of 'set_to' then 'set_to' stays unchanged.
788 */
setExcl(setType * const set_to,const intType number)789 void setExcl (setType *const set_to, const intType number)
790
791 {
792 setType set_dest;
793 intType position;
794 memSizeType bitset_index;
795 unsigned int bit_index;
796
797 /* setExcl */
798 set_dest = *set_to;
799 position = bitset_pos(number);
800 if (position >= set_dest->min_position && position <= set_dest->max_position) {
801 bitset_index = bitsetIndex(set_dest, position);
802 bit_index = ((unsigned int) number) & bitset_mask;
803 set_dest->bitset[bitset_index] &= ~((bitSetType) 1 << bit_index);
804 #ifdef OUT_OF_ORDER
805 if (set_dest->bitset[bitset_index] == 0) {
806 if
807 } /* if */
808 #endif
809 } /* if */
810 } /* setExcl */
811
812
813
814 /**
815 * Compute the hash value of a set.
816 * @return the hash value.
817 */
818 intType setHashCode (const const_setType set1)
819
820 {
821 memSizeType bitset_size;
822 memSizeType bitset_index;
823 intType hashCode;
824
825 /* setHashCode */
826 hashCode = 0;
827 bitset_size = bitsetSize(set1);
828 for (bitset_index = 0; bitset_index < bitset_size; bitset_index++) {
829 hashCode ^= (intType) set1->bitset[bitset_index];
830 } /* for */
831 return hashCode;
832 } /* setHashCode */
833
834
835
836 /**
837 * Convert an integer number to a bitset.
838 * @return a bitset which corresponds to the given integer.
839 * @exception RANGE_ERROR Number is negative.
840 * @exception MEMORY_ERROR Not enough memory to represent the result.
841 */
842 setType setIConv (intType number)
843
844 {
845 memSizeType result_size;
846 setType result;
847
848 /* setIConv */
849 if (unlikely(number < 0)) {
850 logError(printf("setIConv(): Number is negative.\n"););
851 raise_error(RANGE_ERROR);
852 result = NULL;
853 } else {
854 result_size = sizeof(intType) / sizeof(bitSetType);
855 if (unlikely(!ALLOC_SET(result, result_size))) {
856 raise_error(MEMORY_ERROR);
857 } else {
858 result->min_position = 0;
859 result->max_position = (intType) (result_size - 1);
860 result->bitset[0] = (bitSetType) number;
861 #if BITSETTYPE_SIZE < INTTYPE_SIZE
862 {
863 memSizeType pos;
864
865 for (pos = 1; pos < result_size; pos++) {
866 number >>= CHAR_BIT * sizeof(bitSetType);
867 result->bitset[pos] = (bitSetType) number;
868 } /* for */
869 }
870 #endif
871 } /* if */
872 } /* if */
873 return result;
874 } /* setIConv */
875
876
877
878 /**
879 * Add 'number' to the set 'set_to'.
880 * If 'number' is already in 'set_to' then 'set_to' stays unchanged.
881 * @exception MEMORY_ERROR If there is not enough memory.
882 */
883 void setIncl (setType *const set_to, const intType number)
884
885 {
886 setType set_dest;
887 intType position;
888 memSizeType old_size;
889 memSizeType new_size;
890 setType old_set;
891 memSizeType bitset_index;
892 unsigned int bit_index;
893
894 /* setIncl */
895 set_dest = *set_to;
896 position = bitset_pos(number);
897 if (position > set_dest->max_position) {
898 old_size = bitsetSize(set_dest);
899 if (unlikely((uintType) (position - set_dest->min_position + 1) > MAX_SET_LEN)) {
900 raise_error(MEMORY_ERROR);
901 return;
902 } else {
903 new_size = bitsetSize2(set_dest->min_position, position);
904 set_dest = REALLOC_SET(set_dest, old_size, new_size);
905 if (unlikely(set_dest == NULL)) {
906 raise_error(MEMORY_ERROR);
907 return;
908 } else {
909 COUNT3_SET(old_size, new_size);
910 *set_to = set_dest;
911 set_dest->max_position = position;
912 memset(&set_dest->bitset[old_size], 0, (new_size - old_size) * sizeof(bitSetType));
913 } /* if */
914 } /* if */
915 } else if (position < set_dest->min_position) {
916 old_size = bitsetSize(set_dest);
917 if (unlikely((uintType) (set_dest->max_position - position + 1) > MAX_SET_LEN)) {
918 raise_error(MEMORY_ERROR);
919 return;
920 } else {
921 new_size = bitsetSize2(position, set_dest->max_position);
922 old_set = set_dest;
923 if (unlikely(!ALLOC_SET(set_dest, new_size))) {
924 raise_error(MEMORY_ERROR);
925 return;
926 } else {
927 *set_to = set_dest;
928 set_dest->min_position = position;
929 set_dest->max_position = old_set->max_position;
930 memset(set_dest->bitset, 0, (new_size - old_size) * sizeof(bitSetType));
931 memcpy(&set_dest->bitset[new_size - old_size], old_set->bitset,
932 old_size * sizeof(bitSetType));
933 FREE_SET(old_set, old_size);
934 } /* if */
935 } /* if */
936 } /* if */
937 bitset_index = bitsetIndex(set_dest, position);
938 bit_index = ((unsigned int) number) & bitset_mask;
939 set_dest->bitset[bitset_index] |= (bitSetType) 1 << bit_index;
940 } /* setIncl */
941
942
943
944 /**
945 * Intersection of two sets.
946 * @return the intersection of the two sets.
947 * @exception MEMORY_ERROR Not enough memory for the result.
948 */
949 setType setIntersect (const const_setType set1, const const_setType set2)
950
951 {
952 intType min_position;
953 intType max_position;
954 intType position;
955 setType intersection;
956
957 /* setIntersect */
958 logFunction(printf("setIntersect(\n");
959 prot_set(set1);
960 printf(",\n");
961 prot_set(set2);
962 printf(")\n"););
963 if (set1->min_position > set2->min_position) {
964 min_position = set1->min_position;
965 } else {
966 min_position = set2->min_position;
967 } /* if */
968 if (set1->max_position < set2->max_position) {
969 max_position = set1->max_position;
970 } else {
971 max_position = set2->max_position;
972 } /* if */
973 while (min_position <= max_position &&
974 (set1->bitset[min_position - set1->min_position] &
975 set2->bitset[min_position - set2->min_position]) == 0) {
976 min_position++;
977 } /* while */
978 while (min_position <= max_position &&
979 (set1->bitset[max_position - set1->min_position] &
980 set2->bitset[max_position - set2->min_position]) == 0) {
981 max_position--;
982 } /* while */
983 if (min_position > max_position) {
984 if (unlikely(!ALLOC_SET(intersection, 1))) {
985 raise_error(MEMORY_ERROR);
986 } else {
987 intersection->min_position = 0;
988 intersection->max_position = 0;
989 intersection->bitset[0] = (bitSetType) 0;
990 } /* if */
991 } else {
992 if (unlikely(!ALLOC_SET(intersection, (uintType) (max_position - min_position + 1)))) {
993 raise_error(MEMORY_ERROR);
994 } else {
995 intersection->min_position = min_position;
996 intersection->max_position = max_position;
997 for (position = min_position; position <= max_position; position++) {
998 intersection->bitset[position - min_position] =
999 set1->bitset[position - set1->min_position] &
1000 set2->bitset[position - set2->min_position];
1001 } /* for */
1002 } /* if */
1003 } /* if */
1004 logFunction(printf("setIntersect --> ");
1005 prot_set(intersection);
1006 printf("\n"););
1007 return intersection;
1008 } /* setIntersect */
1009
1010
1011
1012 /**
1013 * Assign the intersection of *dest and delta to *dest.
1014 * @exception MEMORY_ERROR Not enough memory to create dest.
1015 */
1016 void setIntersectAssign (setType *const dest, const const_setType delta)
1017
1018 {
1019 setType set1;
1020 intType min_position;
1021 intType max_position;
1022 intType position;
1023 setType new_set1;
1024
1025 /* setIntersectAssign */
1026 logFunction(printf("setIntersectAssign(\n");
1027 prot_set(*dest);
1028 printf(",\n");
1029 prot_set(delta);
1030 printf(")\n"););
1031 set1 = *dest;
1032 if (set1->min_position > delta->min_position) {
1033 min_position = set1->min_position;
1034 } else {
1035 min_position = delta->min_position;
1036 } /* if */
1037 if (set1->max_position < delta->max_position) {
1038 max_position = set1->max_position;
1039 } else {
1040 max_position = delta->max_position;
1041 } /* if */
1042 while (min_position <= max_position &&
1043 (set1->bitset[min_position - set1->min_position] &
1044 delta->bitset[min_position - delta->min_position]) == 0) {
1045 min_position++;
1046 } /* while */
1047 while (min_position <= max_position &&
1048 (set1->bitset[max_position - set1->min_position] &
1049 delta->bitset[max_position - delta->min_position]) == 0) {
1050 max_position--;
1051 } /* while */
1052 if (min_position > max_position) {
1053 new_set1 = REALLOC_SET(set1, bitsetSize(set1), 1);
1054 if (unlikely(new_set1 == NULL)) {
1055 /* Strange case if a 'realloc', which shrinks memory, fails. */
1056 /* The destination set stays unchanged. */
1057 raise_error(MEMORY_ERROR);
1058 } else {
1059 new_set1->min_position = 0;
1060 new_set1->max_position = 0;
1061 new_set1->bitset[0] = (bitSetType) 0;
1062 *dest = new_set1;
1063 } /* if */
1064 } else if (min_position == set1->min_position) {
1065 if (max_position != set1->max_position) {
1066 new_set1 = REALLOC_SET(set1, bitsetSize(set1), bitsetSize2(min_position, max_position));
1067 if (unlikely(new_set1 == NULL)) {
1068 /* Strange case if a 'realloc', which shrinks memory, fails. */
1069 /* The destination set stays unchanged. */
1070 raise_error(MEMORY_ERROR);
1071 return;
1072 } else {
1073 set1 = new_set1;
1074 set1->max_position = max_position;
1075 *dest = set1;
1076 } /* if */
1077 } /* if */
1078 for (position = min_position; position <= max_position; position++) {
1079 set1->bitset[position - min_position] &=
1080 delta->bitset[position - delta->min_position];
1081 } /* for */
1082 } else {
1083 for (position = min_position; position <= max_position; position++) {
1084 set1->bitset[position - min_position] =
1085 set1->bitset[position - set1->min_position] &
1086 delta->bitset[position - delta->min_position];
1087 } /* for */
1088 new_set1 = REALLOC_SET(set1, bitsetSize(set1), bitsetSize2(min_position, max_position));
1089 if (unlikely(new_set1 == NULL)) {
1090 /* Strange case if a 'realloc', which shrinks memory, fails. */
1091 /* Deliver the result in the original set (that is too big). */
1092 set1->min_position = min_position;
1093 set1->max_position = max_position;
1094 raise_error(MEMORY_ERROR);
1095 } else {
1096 new_set1->min_position = min_position;
1097 new_set1->max_position = max_position;
1098 *dest = new_set1;
1099 } /* if */
1100 } /* if */
1101 logFunction(printf("setIntersectAssign --> ");
1102 prot_set(*dest);
1103 printf("\n"););
1104 } /* setIntersectAssign */
1105
1106
1107
1108 /**
1109 * Determine if 'set1' is the empty set.
1110 * @return TRUE if 'set1' is the empty set,
1111 * FALSE otherwise.
1112 */
1113 boolType setIsEmpty (const const_setType set1)
1114
1115 {
1116 register memSizeType bitset_index;
1117
1118 /* setIsEmpty */
1119 bitset_index = bitsetSize(set1);
1120 do {
1121 bitset_index--;
1122 if (set1->bitset[bitset_index] != 0) {
1123 return FALSE;
1124 } /* if */
1125 } while (bitset_index != 0);
1126 return TRUE;
1127 } /* setIsEmpty */
1128
1129
1130
1131 /**
1132 * Determine if 'set1' is a proper subset of 'set2'.
1133 * 'set1' is a proper subset of 'set2' if
1134 * set1 <= set2 and set1 <> set2
1135 * holds.
1136 * @return TRUE if 'set1' is a proper subset of 'set2',
1137 * FALSE otherwise.
1138 */
1139 boolType setIsProperSubset (const const_setType set1, const const_setType set2)
1140
1141 {
1142 memSizeType index_beyond;
1143 memSizeType bitset_index;
1144 memSizeType size;
1145 const bitSetType *bitset1;
1146 const bitSetType *bitset2;
1147 boolType equal;
1148
1149 /* setIsProperSubset */
1150 logFunction(printf("setIsProperSubset(");
1151 prot_set(set1);
1152 printf(", ");
1153 prot_set(set2);
1154 printf(")\n"););
1155 equal = TRUE;
1156 if (set1->min_position < set2->min_position) {
1157 if (set1->max_position < set2->min_position) {
1158 size = 0;
1159 index_beyond = bitsetSize(set1);
1160 bitset1 = NULL;
1161 bitset2 = NULL;
1162 } else {
1163 if (set1->max_position <= set2->max_position) {
1164 size = bitsetIndex(set2, set1->max_position + 1);
1165 } else {
1166 size = bitsetSize(set2);
1167 } /* if */
1168 index_beyond = bitsetIndex(set1, set2->min_position);
1169 bitset1 = &set1->bitset[index_beyond];
1170 bitset2 = set2->bitset;
1171 } /* if */
1172 for (bitset_index = 0; bitset_index < index_beyond; bitset_index++) {
1173 if (set1->bitset[bitset_index] != 0) {
1174 return FALSE;
1175 } /* if */
1176 } /* for */
1177 } else {
1178 if (set1->min_position > set2->max_position) {
1179 size = 0;
1180 index_beyond = bitsetSize(set2);
1181 bitset1 = NULL;
1182 bitset2 = NULL;
1183 } else {
1184 if (set1->max_position >= set2->max_position) {
1185 size = bitsetIndex(set1, set2->max_position + 1);
1186 } else {
1187 size = bitsetSize(set1);
1188 } /* if */
1189 index_beyond = bitsetIndex(set2, set1->min_position);
1190 bitset1 = set1->bitset;
1191 bitset2 = &set2->bitset[index_beyond];
1192 } /* if */
1193 for (bitset_index = 0; bitset_index < index_beyond && equal; bitset_index++) {
1194 if (set2->bitset[bitset_index] != 0) {
1195 equal = FALSE;
1196 } /* if */
1197 } /* for */
1198 } /* if */
1199 if (set1->max_position > set2->max_position) {
1200 if (set1->min_position > set2->max_position) {
1201 bitset_index = 0;
1202 } else {
1203 bitset_index = bitsetIndex(set1, set2->max_position + 1);
1204 } /* if */
1205 index_beyond = bitsetSize(set1);
1206 for (; bitset_index < index_beyond; bitset_index++) {
1207 if (set1->bitset[bitset_index] != 0) {
1208 return FALSE;
1209 } /* if */
1210 } /* for */
1211 } else {
1212 if (set1->max_position < set2->min_position) {
1213 bitset_index = 0;
1214 } else {
1215 bitset_index = bitsetIndex(set2, set1->max_position + 1);
1216 } /* if */
1217 index_beyond = bitsetSize(set2);
1218 for (; bitset_index < index_beyond && equal; bitset_index++) {
1219 if (set2->bitset[bitset_index] != 0) {
1220 equal = FALSE;
1221 } /* if */
1222 } /* for */
1223 } /* if */
1224 for (bitset_index = 0; bitset_index < size; bitset_index++, bitset1++, bitset2++) {
1225 if ((~ *bitset1 | *bitset2) != ~(bitSetType) 0) {
1226 return FALSE;
1227 } /* if */
1228 if (*bitset1 != *bitset2) {
1229 equal = FALSE;
1230 } /* if */
1231 } /* for */
1232 return !equal;
1233 } /* setIsProperSubset */
1234
1235
1236
1237 /**
1238 * Determine if 'set1' is a subset of 'set2'.
1239 * 'set1' is a subset of 'set2' if no element X exists for which
1240 * X in set1 and X not in set2
1241 * holds.
1242 * @return TRUE if 'set1' is a subset of 'set2',
1243 * FALSE otherwise.
1244 */
1245 boolType setIsSubset (const const_setType set1, const const_setType set2)
1246
1247 {
1248 memSizeType index_beyond;
1249 memSizeType bitset_index;
1250 memSizeType size;
1251 const bitSetType *bitset1;
1252 const bitSetType *bitset2;
1253
1254 /* setIsSubset */
1255 logFunction(printf("setIsSubset(");
1256 prot_set(set1);
1257 printf(", ");
1258 prot_set(set2);
1259 printf(")\n"););
1260 if (set1->min_position < set2->min_position) {
1261 if (set1->max_position < set2->min_position) {
1262 size = 0;
1263 index_beyond = bitsetSize(set1);
1264 bitset1 = NULL;
1265 bitset2 = NULL;
1266 } else {
1267 if (set1->max_position <= set2->max_position) {
1268 size = bitsetIndex(set2, set1->max_position + 1);
1269 } else {
1270 size = bitsetSize(set2);
1271 } /* if */
1272 index_beyond = bitsetIndex(set1, set2->min_position);
1273 bitset1 = &set1->bitset[index_beyond];
1274 bitset2 = set2->bitset;
1275 } /* if */
1276 for (bitset_index = 0; bitset_index < index_beyond; bitset_index++) {
1277 if (set1->bitset[bitset_index] != 0) {
1278 return FALSE;
1279 } /* if */
1280 } /* for */
1281 } else {
1282 if (set1->min_position > set2->max_position) {
1283 size = 0;
1284 bitset1 = NULL;
1285 bitset2 = NULL;
1286 } else {
1287 if (set1->max_position >= set2->max_position) {
1288 size = bitsetIndex(set1, set2->max_position + 1);
1289 } else {
1290 size = bitsetSize(set1);
1291 } /* if */
1292 bitset1 = set1->bitset;
1293 bitset2 = &set2->bitset[set1->min_position - set2->min_position];
1294 } /* if */
1295 } /* if */
1296 if (set1->max_position > set2->max_position) {
1297 if (set1->min_position > set2->max_position) {
1298 bitset_index = 0;
1299 } else {
1300 bitset_index = bitsetIndex(set1, set2->max_position + 1);
1301 } /* if */
1302 index_beyond = bitsetSize(set1);
1303 for (; bitset_index < index_beyond; bitset_index++) {
1304 if (set1->bitset[bitset_index] != 0) {
1305 return FALSE;
1306 } /* if */
1307 } /* for */
1308 } /* if */
1309 for (bitset_index = 0; bitset_index < size; bitset_index++, bitset1++, bitset2++) {
1310 if ((~ *bitset1 | *bitset2) != ~(bitSetType) 0) {
1311 return FALSE;
1312 } /* if */
1313 } /* for */
1314 return TRUE;
1315 } /* setIsSubset */
1316
1317
1318
1319 /**
1320 * Maximum element of a set.
1321 * Delivers the element from 'aSet' for which the following condition holds:
1322 * element >= X
1323 * for all X which are in the set.
1324 * @return the maximal element of 'aSet'.
1325 * @exception RANGE_ERROR If 'aSet' is the empty set.
1326 */
1327 intType setMax (const const_setType aSet)
1328
1329 {
1330 memSizeType bitset_index;
1331 bitSetType curr_bitset;
1332 intType result;
1333
1334 /* setMax */
1335 bitset_index = bitsetSize(aSet);
1336 while (bitset_index > 0) {
1337 bitset_index--;
1338 curr_bitset = aSet->bitset[bitset_index];
1339 if (curr_bitset != 0) {
1340 result = bitsetMostSignificantBit(curr_bitset);
1341 result += lowestBitsetPosAsInteger(aSet->min_position + (intType) bitset_index);
1342 return result;
1343 } /* if */
1344 } /* while */
1345 logError(printf("setMax(): Set is empty.\n"););
1346 raise_error(RANGE_ERROR);
1347 return 0;
1348 } /* setMax */
1349
1350
1351
1352 /**
1353 * Minimum element of a set.
1354 * Delivers the element from 'aSet' for which the following condition holds:
1355 * element <= X
1356 * for all X which are in the set.
1357 * @return the minimum element of 'aSet'.
1358 * @exception RANGE_ERROR If 'aSet' is the empty set.
1359 */
1360 intType setMin (const const_setType aSet)
1361
1362 {
1363 memSizeType bitset_size;
1364 memSizeType bitset_index;
1365 bitSetType curr_bitset;
1366 intType result;
1367
1368 /* setMin */
1369 bitset_size = bitsetSize(aSet);
1370 bitset_index = 0;
1371 while (bitset_index < bitset_size) {
1372 curr_bitset = aSet->bitset[bitset_index];
1373 if (curr_bitset != 0) {
1374 result = bitsetLeastSignificantBit(curr_bitset);
1375 result += lowestBitsetPosAsInteger(aSet->min_position + (intType) bitset_index);
1376 return result;
1377 } /* if */
1378 bitset_index++;
1379 } /* while */
1380 logError(printf("setMin(): Set is empty.\n"););
1381 raise_error(RANGE_ERROR);
1382 return 0;
1383 } /* setMin */
1384
1385
1386
1387 /**
1388 * Minimum element of 'aSet' that is larger than 'number'.
1389 * @return the minimum element of 'aSet' that is larger than 'number'.
1390 * @exception RANGE_ERROR If 'aSet' has no element larger than 'number'.
1391 */
1392 intType setNext (const const_setType aSet, const intType number)
1393
1394 {
1395 intType position;
1396 memSizeType bitset_size;
1397 memSizeType bitset_index;
1398 unsigned int bit_index;
1399 bitSetType curr_bitset;
1400 const bitSetType *bitset_ptr;
1401 intType nextNumber;
1402
1403 /* setNext */
1404 logFunction(printf("setNext(");
1405 prot_set(aSet);
1406 printf(", " FMT_D ")\n", number););
1407 if (unlikely(number == INTTYPE_MAX)) {
1408 logError(printf("setNext(aSet, " FMT_D "): "
1409 "The maximum integer has no successor.\n",
1410 number););
1411 raise_error(RANGE_ERROR);
1412 nextNumber = 0;
1413 } else {
1414 position = bitset_pos(number + 1);
1415 if (position < aSet->min_position) {
1416 position = aSet->min_position;
1417 bit_index = 0;
1418 } else {
1419 bit_index = ((unsigned int) (number + 1)) & bitset_mask;
1420 } /* if */
1421 bitset_size = bitsetSize(aSet);
1422 bitset_index = bitsetIndex(aSet, position);
1423 if (unlikely(bitset_index >= bitset_size)) {
1424 logError(printf("setNext(aSet, " FMT_D "): "
1425 "The number is beyond the maximum element of the set.\n",
1426 number););
1427 raise_error(RANGE_ERROR);
1428 nextNumber = 0;
1429 } else {
1430 curr_bitset = (aSet->bitset[bitset_index] >> bit_index) << bit_index;
1431 if (curr_bitset != 0) {
1432 nextNumber = bitsetLeastSignificantBit(curr_bitset);
1433 nextNumber += lowestBitsetPosAsInteger(aSet->min_position + (intType) bitset_index);
1434 } else {
1435 bitset_index++;
1436 bitset_ptr = bitsetNonZero(&aSet->bitset[bitset_index], bitset_size - bitset_index);
1437 if (unlikely(bitset_ptr == NULL)) {
1438 logError(printf("setNext(aSet, " FMT_D "): "
1439 "The maximum element of a set has no next element.\n",
1440 number););
1441 raise_error(RANGE_ERROR);
1442 nextNumber = 0;
1443 } else {
1444 bitset_index = (memSizeType) (bitset_ptr - aSet->bitset);
1445 nextNumber = bitsetLeastSignificantBit(*bitset_ptr);
1446 nextNumber += lowestBitsetPosAsInteger(aSet->min_position + (intType) bitset_index);
1447 } /* if */
1448 } /* if */
1449 } /* if */
1450 } /* if */
1451 logFunction(printf("setNext --> " FMT_D "\n", nextNumber););
1452 return nextNumber;
1453 } /* setNext */
1454
1455
1456
1457 /**
1458 * Compute pseudo-random element from 'aSet'.
1459 * The random values are uniform distributed.
1460 * @return a random number such that setRand(aSet) in aSet holds.
1461 * @exception RANGE_ERROR If 'aSet' is empty.
1462 */
1463 intType setRand (const const_setType aSet)
1464
1465 {
1466 intType num_elements;
1467 intType elem_index;
1468 memSizeType bitset_index;
1469 bitSetType curr_bitset;
1470 intType result;
1471
1472 /* setRand */
1473 num_elements = setCard(aSet);
1474 if (unlikely(num_elements == 0)) {
1475 logError(printf("setRand(): Set is empty.\n"););
1476 raise_error(RANGE_ERROR);
1477 return 0;
1478 } else {
1479 elem_index = intRand(1, num_elements);
1480 for (bitset_index = bitsetSize(aSet);
1481 bitset_index > 0 && elem_index > BITSETTYPE_SIZE; bitset_index--) {
1482 curr_bitset = aSet->bitset[bitset_index - 1];
1483 /* If elem_index > BITSETTYPE_SIZE holds */
1484 /* the element cannot be in curr_bitset. */
1485 elem_index -= (intType) bitsetPopulation(curr_bitset);
1486 } /* for */
1487 for (; bitset_index > 0; bitset_index--) {
1488 curr_bitset = aSet->bitset[bitset_index - 1];
1489 while (curr_bitset != 0) {
1490 elem_index--;
1491 if (elem_index == 0) {
1492 result = bitsetLeastSignificantBit(curr_bitset) +
1493 lowestBitsetPosAsInteger(aSet->min_position + (intType) (bitset_index - 1));
1494 return result;
1495 } /* if */
1496 /* Turn off the rightmost one bit of curr_bitset: */
1497 curr_bitset &= curr_bitset - 1;
1498 } /* while */
1499 } /* for */
1500 /* This place should never be reached, since the */
1501 /* check for an empty set has been done before. */
1502 } /* if */
1503 raise_error(RANGE_ERROR);
1504 return 0;
1505 } /* setRand */
1506
1507
1508
1509 /**
1510 * Create set with all values from 'lowValue' to 'highValue' inclusive.
1511 * @param lowValue lowest value to be added to the result set.
1512 * @param highValue highest value to be added to the result set.
1513 * @return set with all values from 'lowValue' to 'highValue' inclusive, or
1514 * an empty set if 'lowValue' is greater than 'highValue'.
1515 */
1516 setType setRangelit (const intType lowValue, const intType highValue)
1517
1518 {
1519 intType min_position;
1520 intType max_position;
1521 memSizeType bitset_size;
1522 unsigned int bit_index;
1523 setType result;
1524
1525 /* setRangelit */
1526 logFunction(printf("setRangelit(" FMT_D ", " FMT_D ")\n",
1527 lowValue, highValue););
1528 min_position = bitset_pos(lowValue);
1529 max_position = bitset_pos(highValue);
1530 if (min_position > max_position) {
1531 if (unlikely(!ALLOC_SET(result, 1))) {
1532 raise_error(MEMORY_ERROR);
1533 } else {
1534 result->min_position = 0;
1535 result->max_position = 0;
1536 result->bitset[0] = (bitSetType) 0;
1537 } /* if */
1538 } else if (unlikely((uintType) (max_position - min_position + 1) > MAX_SET_LEN ||
1539 !ALLOC_SET(result, (uintType) (max_position - min_position + 1)))) {
1540 raise_error(MEMORY_ERROR);
1541 result = NULL;
1542 } else {
1543 result->min_position = min_position;
1544 result->max_position = max_position;
1545 bit_index = ((unsigned int) lowValue) & bitset_mask;
1546 result->bitset[0] = ~(bitSetType) 0 << bit_index;
1547 if (min_position == max_position) {
1548 bit_index = ((unsigned int) highValue) & bitset_mask;
1549 result->bitset[0] &= ~(~(bitSetType) 1 << bit_index);
1550 } else {
1551 bitset_size = bitsetSize2(min_position, max_position);
1552 memset(&result->bitset[1], 0xff, (bitset_size - 2) * sizeof(bitSetType));
1553 bit_index = ((unsigned int) highValue) & bitset_mask;
1554 result->bitset[bitset_size - 1] = ~(~(bitSetType) 1 << bit_index);
1555 } /* if */
1556 } /* if */
1557 logFunction(printf("setRangelit --> ");
1558 prot_set(result);
1559 printf("\n"););
1560 return result;
1561 } /* setRangelit */
1562
1563
1564
1565 /**
1566 * Convert a bitset to integer.
1567 * @return an integer which corresponds to the given bitset.
1568 * @exception RANGE_ERROR If 'aSet' contains negative values or
1569 * if it does not fit into a non-negative integer.
1570 */
1571 intType setSConv (const const_setType aSet)
1572
1573 {
1574 intType number;
1575
1576 /* setSConv */
1577 if (likely(aSet->min_position == 0 && aSet->max_position == 0)) {
1578 #if BITSETTYPE_SIZE > INTTYPE_SIZE
1579 if (unlikely(aSet->bitset[0] >> INTTYPE_SIZE != 0)) {
1580 logError(printf("setSConv(): "
1581 "Set does not fit into an integer.\n"););
1582 raise_error(RANGE_ERROR);
1583 return 0;
1584 } /* if */
1585 #endif
1586 number = (intType) aSet->bitset[0];
1587 #if BITSETTYPE_SIZE >= INTTYPE_SIZE
1588 if (unlikely(number < 0)) {
1589 logError(printf("setSConv(): "
1590 "Set does not fit into a non-negative integer.\n"););
1591 raise_error(RANGE_ERROR);
1592 return 0;
1593 } /* if */
1594 #endif
1595 } else {
1596 logError(printf("setSConv(): "
1597 "Set contains negative values or does not fit into an integer.\n"););
1598 raise_error(RANGE_ERROR);
1599 return 0;
1600 } /* if */
1601 return number;
1602 } /* setSConv */
1603
1604
1605
1606 /**
1607 * Symmetric difference of two sets.
1608 * @return the symmetric difference of the two sets.
1609 * @exception MEMORY_ERROR Not enough memory for the result.
1610 */
1611 setType setSymdiff (const const_setType set1, const const_setType set2)
1612
1613 {
1614 intType position;
1615 intType min_position;
1616 intType max_position;
1617 intType start_position;
1618 intType stop_position;
1619 setType symDiff;
1620
1621 /* setSymdiff */
1622 logFunction(printf("setSymdiff(\n");
1623 prot_set(set1);
1624 printf(",\n");
1625 prot_set(set2);
1626 printf(")\n"););
1627 if (set1->min_position < set2->min_position) {
1628 min_position = set1->min_position;
1629 start_position = set2->min_position;
1630 } else {
1631 min_position = set2->min_position;
1632 start_position = set1->min_position;
1633 } /* if */
1634 if (set1->max_position > set2->max_position) {
1635 max_position = set1->max_position;
1636 stop_position = set2->max_position;
1637 } else {
1638 max_position = set2->max_position;
1639 stop_position = set1->max_position;
1640 } /* if */
1641 if (unlikely((uintType) (max_position - min_position + 1) > MAX_SET_LEN ||
1642 !ALLOC_SET(symDiff, (uintType) (max_position - min_position + 1)))) {
1643 raise_error(MEMORY_ERROR);
1644 symDiff = NULL;
1645 } else {
1646 symDiff->min_position = min_position;
1647 symDiff->max_position = max_position;
1648 if (set1->max_position < set2->min_position ||
1649 set1->min_position > set2->max_position) {
1650 memcpy(&symDiff->bitset[set1->min_position - min_position], set1->bitset,
1651 bitsetSize(set1) * sizeof(bitSetType));
1652 memcpy(&symDiff->bitset[set2->min_position - min_position], set2->bitset,
1653 bitsetSize(set2) * sizeof(bitSetType));
1654 memset(&symDiff->bitset[stop_position - min_position + 1], 0,
1655 (size_t) (uintType) (start_position - stop_position - 1) *
1656 sizeof(bitSetType));
1657 } else {
1658 if (set2->min_position > set1->min_position) {
1659 memcpy(&symDiff->bitset[set1->min_position - min_position], set1->bitset,
1660 (size_t) (uintType) (set2->min_position - set1->min_position) *
1661 sizeof(bitSetType));
1662 } else {
1663 memcpy(&symDiff->bitset[set2->min_position - min_position], set2->bitset,
1664 (size_t) (uintType) (set1->min_position - set2->min_position) *
1665 sizeof(bitSetType));
1666 } /* if */
1667 if (set2->max_position > set1->max_position) {
1668 memcpy(&symDiff->bitset[set1->max_position - min_position + 1],
1669 &set2->bitset[set1->max_position - set2->min_position + 1],
1670 (size_t) (uintType) (set2->max_position - set1->max_position) *
1671 sizeof(bitSetType));
1672 } else {
1673 memcpy(&symDiff->bitset[set2->max_position - min_position + 1],
1674 &set1->bitset[set2->max_position - set1->min_position + 1],
1675 (size_t) (uintType) (set1->max_position - set2->max_position) *
1676 sizeof(bitSetType));
1677 } /* if */
1678 for (position = start_position; position <= stop_position; position++) {
1679 symDiff->bitset[position - min_position] =
1680 set1->bitset[position - set1->min_position] ^
1681 set2->bitset[position - set2->min_position];
1682 } /* for */
1683 } /* if */
1684 } /* if */
1685 logFunction(printf("setSymdiff --> ");
1686 prot_set(symDiff);
1687 printf("\n"););
1688 return symDiff;
1689 } /* setSymdiff */
1690
1691
1692
1693 /**
1694 * Get 64 bits from a bitset starting with lowestBitNum.
1695 * This function is used by the action BIN_GET_BINARY_FROM_SET.
1696 * @return a bit pattern with 64 bits from set1.
1697 */
1698 uintType setToUInt (const const_setType set1, const intType lowestBitNum)
1699
1700 {
1701 intType position;
1702 memSizeType bitset_index;
1703 unsigned int bit_index;
1704 uintType bitPattern;
1705
1706 /* setToUInt */
1707 logFunction(printf("setToUInt(");
1708 prot_set(set1);
1709 printf(", " FMT_D ")\n", lowestBitNum););
1710 position = bitset_pos(lowestBitNum);
1711 if (position >= set1->min_position && position <= set1->max_position) {
1712 bitset_index = bitsetIndex(set1, position);
1713 bit_index = ((unsigned int) lowestBitNum) & bitset_mask;
1714 if (bit_index == 0) {
1715 bitPattern = (uintType) set1->bitset[bitset_index];
1716 } else if (position < set1->max_position) {
1717 bitPattern = (uintType) (set1->bitset[bitset_index] >> bit_index |
1718 set1->bitset[bitset_index + 1] << (CHAR_BIT * sizeof(bitSetType) - bit_index));
1719 } else {
1720 bitPattern = (uintType) (set1->bitset[bitset_index] >> bit_index);
1721 } /* if */
1722 } else if (position == set1->min_position - 1) {
1723 bitset_index = bitsetIndex(set1, position);
1724 bit_index = ((unsigned int) lowestBitNum) & bitset_mask;
1725 if (bit_index == 0) {
1726 bitPattern = 0;
1727 } else {
1728 bitPattern = (uintType)
1729 (set1->bitset[bitset_index + 1] << (CHAR_BIT * sizeof(bitSetType) - bit_index));
1730 } /* if */
1731 } else {
1732 bitPattern = 0;
1733 } /* if */
1734 logFunction(printf("setToUInt --> 0x" F_X(016) "\n", bitPattern););
1735 return bitPattern;
1736 } /* setToUInt */
1737
1738
1739
1740 /**
1741 * Union of two sets.
1742 * @return the union of the two sets.
1743 * @exception MEMORY_ERROR Not enough memory for the result.
1744 */
1745 setType setUnion (const const_setType set1, const const_setType set2)
1746
1747 {
1748 intType position;
1749 intType min_position;
1750 intType max_position;
1751 intType start_position;
1752 intType stop_position;
1753 setType unionOfSets;
1754
1755 /* setUnion */
1756 logFunction(printf("setUnion(\n");
1757 prot_set(set1);
1758 printf(",\n");
1759 prot_set(set2);
1760 printf(")\n"););
1761 if (set1->min_position < set2->min_position) {
1762 min_position = set1->min_position;
1763 start_position = set2->min_position;
1764 } else {
1765 min_position = set2->min_position;
1766 start_position = set1->min_position;
1767 } /* if */
1768 if (set1->max_position > set2->max_position) {
1769 max_position = set1->max_position;
1770 stop_position = set2->max_position;
1771 } else {
1772 max_position = set2->max_position;
1773 stop_position = set1->max_position;
1774 } /* if */
1775 if (unlikely((uintType) (max_position - min_position + 1) > MAX_SET_LEN ||
1776 !ALLOC_SET(unionOfSets, (uintType) (max_position - min_position + 1)))) {
1777 raise_error(MEMORY_ERROR);
1778 unionOfSets = NULL;
1779 } else {
1780 unionOfSets->min_position = min_position;
1781 unionOfSets->max_position = max_position;
1782 if (set1->max_position < set2->min_position ||
1783 set1->min_position > set2->max_position) {
1784 memcpy(&unionOfSets->bitset[set1->min_position - min_position], set1->bitset,
1785 bitsetSize(set1) * sizeof(bitSetType));
1786 memcpy(&unionOfSets->bitset[set2->min_position - min_position], set2->bitset,
1787 bitsetSize(set2) * sizeof(bitSetType));
1788 memset(&unionOfSets->bitset[stop_position - min_position + 1], 0,
1789 (size_t) (uintType) (start_position - stop_position - 1) *
1790 sizeof(bitSetType));
1791 } else {
1792 if (set2->min_position > set1->min_position) {
1793 memcpy(&unionOfSets->bitset[set1->min_position - min_position], set1->bitset,
1794 (size_t) (uintType) (set2->min_position - set1->min_position) *
1795 sizeof(bitSetType));
1796 } else {
1797 memcpy(&unionOfSets->bitset[set2->min_position - min_position], set2->bitset,
1798 (size_t) (uintType) (set1->min_position - set2->min_position) *
1799 sizeof(bitSetType));
1800 } /* if */
1801 if (set2->max_position > set1->max_position) {
1802 memcpy(&unionOfSets->bitset[set1->max_position - min_position + 1],
1803 &set2->bitset[set1->max_position - set2->min_position + 1],
1804 (size_t) (uintType) (set2->max_position - set1->max_position) *
1805 sizeof(bitSetType));
1806 } else {
1807 memcpy(&unionOfSets->bitset[set2->max_position - min_position + 1],
1808 &set1->bitset[set2->max_position - set1->min_position + 1],
1809 (size_t) (uintType) (set1->max_position - set2->max_position) *
1810 sizeof(bitSetType));
1811 } /* if */
1812 for (position = start_position; position <= stop_position; position++) {
1813 unionOfSets->bitset[position - min_position] =
1814 set1->bitset[position - set1->min_position] |
1815 set2->bitset[position - set2->min_position];
1816 } /* for */
1817 } /* if */
1818 } /* if */
1819 logFunction(printf("setUnion --> ");
1820 prot_set(unionOfSets);
1821 printf("\n"););
1822 return unionOfSets;
1823 } /* setUnion */
1824
1825
1826
1827 /**
1828 * Assign the union of *dest and delta to *dest.
1829 * @exception MEMORY_ERROR Not enough memory to create dest.
1830 */
1831 void setUnionAssign (setType *const dest, const const_setType delta)
1832
1833 {
1834 setType set1;
1835 intType position;
1836 intType min_position;
1837 intType max_position;
1838 intType start_position;
1839 intType stop_position;
1840 setType new_dest;
1841
1842 /* setUnionAssign */
1843 logFunction(printf("setUnionAssign(\n");
1844 prot_set(*dest);
1845 printf(",\n");
1846 prot_set(delta);
1847 printf(")\n"););
1848 set1 = *dest;
1849 if (set1->min_position < delta->min_position) {
1850 min_position = set1->min_position;
1851 start_position = delta->min_position;
1852 } else {
1853 min_position = delta->min_position;
1854 start_position = set1->min_position;
1855 } /* if */
1856 if (set1->max_position > delta->max_position) {
1857 max_position = set1->max_position;
1858 stop_position = delta->max_position;
1859 } else {
1860 max_position = delta->max_position;
1861 stop_position = set1->max_position;
1862 } /* if */
1863 if (set1->min_position == min_position &&
1864 set1->max_position == max_position) {
1865 for (position = start_position; position <= stop_position; position++) {
1866 set1->bitset[position - min_position] |=
1867 delta->bitset[position - delta->min_position];
1868 } /* for */
1869 } else {
1870 if (unlikely((uintType) (max_position - min_position + 1) > MAX_SET_LEN ||
1871 !ALLOC_SET(new_dest, (uintType) (max_position - min_position + 1)))) {
1872 raise_error(MEMORY_ERROR);
1873 } else {
1874 new_dest->min_position = min_position;
1875 new_dest->max_position = max_position;
1876 if (set1->max_position < delta->min_position ||
1877 set1->min_position > delta->max_position) {
1878 memcpy(&new_dest->bitset[set1->min_position - min_position], set1->bitset,
1879 bitsetSize(set1) * sizeof(bitSetType));
1880 memcpy(&new_dest->bitset[delta->min_position - min_position], delta->bitset,
1881 bitsetSize(delta) * sizeof(bitSetType));
1882 memset(&new_dest->bitset[stop_position - min_position + 1], 0,
1883 (size_t) (uintType) (start_position - stop_position - 1) *
1884 sizeof(bitSetType));
1885 } else {
1886 if (delta->min_position > set1->min_position) {
1887 memcpy(&new_dest->bitset[set1->min_position - min_position], set1->bitset,
1888 (size_t) (uintType) (delta->min_position - set1->min_position) *
1889 sizeof(bitSetType));
1890 } else {
1891 memcpy(&new_dest->bitset[delta->min_position - min_position], delta->bitset,
1892 (size_t) (uintType) (set1->min_position - delta->min_position) *
1893 sizeof(bitSetType));
1894 } /* if */
1895 if (delta->max_position > set1->max_position) {
1896 memcpy(&new_dest->bitset[set1->max_position - min_position + 1],
1897 &delta->bitset[set1->max_position - delta->min_position + 1],
1898 (size_t) (uintType) (delta->max_position - set1->max_position) *
1899 sizeof(bitSetType));
1900 } else {
1901 memcpy(&new_dest->bitset[delta->max_position - min_position + 1],
1902 &set1->bitset[delta->max_position - set1->min_position + 1],
1903 (size_t) (uintType) (set1->max_position - delta->max_position) *
1904 sizeof(bitSetType));
1905 } /* if */
1906 for (position = start_position; position <= stop_position; position++) {
1907 new_dest->bitset[position - min_position] =
1908 set1->bitset[position - set1->min_position] |
1909 delta->bitset[position - delta->min_position];
1910 } /* for */
1911 } /* if */
1912 *dest = new_dest;
1913 FREE_SET(set1, bitsetSize(set1));
1914 } /* if */
1915 } /* if */
1916 logFunction(printf("setUnionAssign --> ");
1917 prot_set(*dest);
1918 printf("\n"););
1919 } /* setUnionAssign */
1920