1 /* tag: Tom Lord Tue Dec 4 14:41:34 2001 (bitset-tree.c)
2 */
3 /* bitset-tree.c -
4 *
5 ****************************************************************
6 * Copyright (C) 2000 Tom Lord
7 *
8 * See the file "COPYING" for further information about
9 * the copyright and warranty status of this work.
10 */
11
12
13 #include "hackerlab/mem/mem.h"
14 #include "hackerlab/bitsets/bitset-tree.h"
15
16
17 /************************************************************************
18 *(h1 "Bitset Trees"
19 * :includes ("hackerlab/bitsets/bitset-tree.h"))
20 *
21 * A "bitset tree" is a sparse representation for a large bitset which
22 * is mostly homogenous (i.e., containing large runs which are all 0
23 * or all 1). A bitset tree saves time and memory by compressing the
24 * representation of homogenous subsets.
25 *
26 * It is important to note that if your bitsets do not contain large,
27 * contiguous, homogenous (all 0 or all 1) subsets, then bitset trees
28 * are of no help -- they add space and time overhead and offer no
29 * advantage. If your sets do have homogenous subsets, bitset trees
30 * can lead to significant space and time savings.
31 *
32 * Usually, you will not want to use bitset trees directly. Instead,
33 * you will want to use ``shared bitset trees''. (See xref:"Shared
34 * Bitset Trees".) Nevertheless, even if you will use shared bitset
35 * trees, it is important to understand how bitset trees work.
36 */
37
38
39 /************************************************************************
40 *(h2 "The Bitset Tree Data Structure")
41 *
42 * This section describes the internal representation of bitset trees.
43 * The public interface to bitset trees hides most of the details of
44 * this representation -- but understanding it will help you predict
45 * the performance of programs which use bitset trees, and design
46 * bitset tree rules. (See xref:"Bitset Tree Rules".)
47 *
48 * Bitset trees are defined recursively: a bitset tree is an array of
49 * (pointers to) bitset trees. The leaf nodes of a bitset trees are
50 * (pointers to) ordinary bitsets. (See xref:"Flat Bitsets".)
51 *
52 * A bitset tree represents a single logical bitset which is the
53 * concatenation of its sub-trees. Each subtree at a given distance
54 * from the root has the same number of members and the same depth and
55 * branching structure.
56 *
57 * As an optimization, if a particular subtree is all 0s, that subtree
58 * may be replaced by a null pointer. If a particular subtree is all
59 * 1s, it may be replaced by the pointer `(bits_tree)-1'. Whenever
60 * practical, functions which operate on bitset trees use this
61 * optimization automatically. For example, `bits_fill_range' will
62 * store a subtree of all 0s or all 1s efficiently. In some cases,
63 * the optimization is not practical. For example, `bits_adjoin'
64 * does not attempt to optimize the subtrees it modifies.
65 *
66 * The function `bits_tree_compact' recursively searches a bitset tree,
67 * replacing homogenous sub-trees with 0 or `-1'.
68 *
69 */
70
71 /*(include-documentation "bitset-tree.h")
72 */
73
74
75
76 /************************************************************************
77 *(h2 "Allocating Bitset Trees")
78 *
79 *
80 *
81 */
82
83 /*(c bits_tree_alloc)
84 * bits_tree bits_tree_alloc (alloc_limits lim,
85 * struct bits_tree_rule * rule);
86 *
87 * Allocate a new bitset tree.
88 *
89 * `lim' describes allocation limits that apply to this bitset tree.
90 * For more information about allocation limits, see xref:"Allocation
91 * With Limitations".
92 *
93 * `rule' describes the branching structure of the bitset tree.
94 * See xref:"Bitset Tree Rules".
95 *
96 * The new set is initialized to all `0's.
97 *
98 * If allocation fails, 0 is returned.
99 */
100 bits_tree
bits_tree_alloc(alloc_limits lim,struct bits_tree_rule * rule)101 bits_tree_alloc (alloc_limits lim,
102 struct bits_tree_rule * rule)
103 {
104 bits_tree answer;
105
106 if (!rule->fanout)
107 return (bits_tree)bitset_alloc (lim, rule->subset_size);
108
109 answer = (bits_tree)lim_malloc (lim, rule->fanout * sizeof (bits_tree));
110 if (answer)
111 mem_set0 ((t_uchar *)answer, rule->fanout * sizeof (bits_tree));
112 return answer;
113 }
114
115
116 /*(c bits_tree_free)
117 * void bits_tree_free (alloc_limits lim,
118 * struct bits_tree_rule * rule,
119 * bits_tree b);
120 *
121 * Free all storage associated with a bitset tree.
122 *
123 * `lim' describes allocation limits that apply to this bitset tree.
124 * For more information about allocation limits, see xref:"Allocation
125 * With Limitations".
126 *
127 * `rule' describes the branching structure of the bitset tree.
128 * See xref:"Bitset Tree Rules".
129 *
130 */
131 void
bits_tree_free(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b)132 bits_tree_free (alloc_limits lim,
133 struct bits_tree_rule * rule,
134 bits_tree b)
135 {
136 int x;
137
138 if (!rule->fanout)
139 {
140 bitset_free (lim, (bitset)b);
141 return;
142 }
143
144 for (x = 0; x < rule->fanout; ++x)
145 {
146 if ( (((bits_tree *)b)[x] != bits_tree_full_bitset)
147 && (((bits_tree *)b)[x] != bits_tree_empty_bitset))
148 bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
149 }
150 lim_free (lim, (t_uchar *)b);
151 }
152
153
154 /*(c bits_tree_compact)
155 * bit_t bits_tree_compact (alloc_limits lim,
156 * struct bits_tree_rule * rule,
157 * bits_tree a);
158 *
159 * Optimize a bitset tree by compacting homogenous
160 * sub-trees. See xref:"The Bitset Tree Data Structure".
161 *
162 * `lim' describes allocation limits that apply to this bitset tree.
163 * For more information about allocation limits, see xref:"Allocation
164 * With Limitations".
165 *
166 * `rule' describes the branching structure of the bitset tree.
167 * See xref:"Bitset Tree Rules".
168 *
169 * The population size of the set is returned.
170 */
171 bit_t
bits_tree_compact(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)172 bits_tree_compact (alloc_limits lim,
173 struct bits_tree_rule * rule,
174 bits_tree a)
175 {
176 int x;
177 bit_t pop;
178
179 if (!rule->fanout)
180 {
181 return bits_tree_population (lim, rule, a);
182 }
183
184 pop = 0;
185 for (x = 0; x < rule->fanout; ++x)
186 {
187 if (((bits_tree *)a)[x] == bits_tree_full_bitset)
188 {
189 pop += rule->subset_size;
190 }
191 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
192 continue;
193 else
194 {
195 bit_t sub_pop;
196
197 sub_pop = bits_tree_compact (lim, rule + 1, ((bits_tree *)a)[x]);
198
199 if (sub_pop == 0)
200 {
201 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
202 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
203 }
204 else if (sub_pop == rule->subset_size)
205 {
206 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
207 ((bits_tree *)a)[x] = bits_tree_full_bitset;
208 }
209
210 pop += sub_pop;
211 }
212 }
213 return pop;
214 }
215
216
217 /*(c bits_tree_dup)
218 * bits_tree bits_tree_dup (alloc_limits lim,
219 * struct bits_tree_rule * rule,
220 * bits_tree a);
221 *
222 * Allocate a new copy of bitset tree `a'.
223 *
224 * `lim' describes allocation limits that apply to this bitset tree.
225 * For more information about allocation limits, see xref:"Allocation
226 * With Limitations".
227 *
228 * `rule' describes the branching structure of the bitset tree.
229 * See xref:"Bitset Tree Rules".
230 *
231 * If allocation fails, 0 is returned.
232 */
233 bits_tree
bits_tree_dup(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)234 bits_tree_dup (alloc_limits lim,
235 struct bits_tree_rule * rule,
236 bits_tree a)
237 {
238 bits_tree answer;
239 int x;
240
241 if (!rule->fanout)
242 {
243 return (bits_tree)bitset_dup (lim, rule->subset_size, (bitset)a);
244 }
245
246 answer = (bits_tree)lim_malloc (lim, rule->fanout * sizeof (bits_tree));
247 if (answer)
248 {
249 for (x = 0; x < rule->fanout; ++x)
250 {
251 if (((bits_tree *)a)[x] == bits_tree_full_bitset)
252 ((bits_tree *)answer)[x] = bits_tree_full_bitset;
253 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
254 ((bits_tree *)answer)[x] = bits_tree_empty_bitset;
255 else
256 {
257 ((bits_tree *)answer)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)a)[x]);
258 if ((!((bits_tree *)answer)[x]) && ((bits_tree *)a)[x])
259 {
260 int y;
261 for (y = x; y < rule->fanout; ++y)
262 ((bits_tree *)answer)[y] = bits_tree_empty_bitset;
263 bits_tree_free (lim, rule, answer);
264 return 0;
265 }
266 }
267 }
268 }
269 return answer;
270 }
271
272
273 /************************************************************************
274 *h2 "Accessing Individual Subsets of a Bitset Tree")
275 *
276 *
277 *
278 */
279
280 /*c bits_tree_get_subset)
281 * int bits_tree_get_subset (bitset_subset * answer,
282 * alloc_limits lim,
283 * struct bits_tree_rule * rule,
284 * bits_tree b,
285 * bit_t n);
286 *
287 * Return (in `*answer') the `bitset_subet' containing bit `n' of
288 * bitset tree `b'. See xref:"bitset_subset".
289 *
290 * `lim' describes allocation limits that apply to this
291 * bitset tree. For more information about allocation limits, see
292 * xref:"Allocation With Limitations".
293 *
294 * `rule' describes the branching structure of the bitset tree.
295 * See xref:"Bitset Tree Rules".
296 *
297 * If the indicated subset does not exist (because it is part of
298 * a homogenous subtree whose representation has been optimized)
299 * the corresponding subtree is newly allocated.
300 *
301 * If allocation fails, -1 is returned. Otherwise, 0 is returned.
302 */
303 int
bits_tree_get_subset(bitset_subset * answer,alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,bit_t n)304 bits_tree_get_subset (bitset_subset * answer,
305 alloc_limits lim,
306 struct bits_tree_rule * rule,
307 bits_tree b,
308 bit_t n)
309 {
310 int bs;
311
312 if (!rule->fanout)
313 {
314 *answer = ((bitset)b)[bitset_which_subset (n)];
315 return 0;
316 }
317
318 bs = bits_tree_which_bitset (lim, rule, n);
319
320 if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
321 {
322 ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
323 if (!((bits_tree *)b)[bs])
324 {
325 ((bits_tree *)b)[bs] = bits_tree_empty_bitset;
326 return -1;
327 }
328 }
329 else if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
330 {
331 ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
332 if (!((bits_tree *)b)[bs])
333 {
334 ((bits_tree *)b)[bs] = bits_tree_full_bitset;
335 return -1;
336 }
337 bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[bs]);
338 }
339
340 return bits_tree_get_subset (answer, lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit(lim, rule, n));
341 }
342
343
344 /************************************************************************
345 *(h2 "Operations on Bitset Trees")
346 *
347 *
348 * Each of the operations defined for flat bitsets has a corresponding
349 * operation for bitset trees. See xref:"Flat Bitsets".
350 *
351 * The bitset tree operations are:
352 *
353 *
354 * |$bits_tree_is_member| |$bits_tree_is_equal| |$bits_tree_is_subset|
355 * |$bits_tree_is_empty| |$bits_tree_is_full| |$bits_tree_is_empty_range|
356 * |$bits_tree_is_full_range| |$bits_tree_adjoin| |$bits_tree_remove|
357 * |$bits_tree_toggle| |$bits_tree_clear| |$bits_tree_fill| |$bits_tree_clear_range|
358 * |$bits_tree_fill_range| |$bits_tree_complement| |$bits_tree_assign|
359 * |$bits_tree_union| |$bits_tree_intersection| |$bits_tree_difference|
360 * |$bits_tree_revdifference| |$bits_tree_xor| |$bits_tree_population|
361 * |$bits_tree_population_range| |$bits_tree_ffs| |$bits_tree_ffc|
362 * |$bits_tree_ffs_range| |$bits_tree_ffc_range|
363 *
364 * int bits_tree_is_member (alloc_limits lim,
365 * struct bits_tree_rule * rule,
366 * bits_tree b,
367 * int n);
368 * int bits_tree_is_equal (alloc_limits lim,
369 * struct bits_tree_rule * rule,
370 * bits_tree a, bits_tree b);
371 * int bits_tree_is_subset (alloc_limits lim,
372 * struct bits_tree_rule * rule,
373 * bits_tree a,
374 * bits_tree b);
375 * int bits_tree_is_empty (alloc_limits lim,
376 * struct bits_tree_rule * rule,
377 * bits_tree a);
378 * int bits_tree_is_full (alloc_limits lim,
379 * struct bits_tree_rule * rule,
380 * bits_tree a);
381 * int bits_tree_is_empty_range (alloc_limits lim,
382 * struct bits_tree_rule * rule,
383 * bits_tree a,
384 * int from,
385 * int to);
386 * int bits_tree_is_full_range (alloc_limits lim,
387 * struct bits_tree_rule * rule,
388 * bits_tree a,
389 * int from,
390 * int to);
391 * int bits_tree_adjoin (alloc_limits lim,
392 * struct bits_tree_rule * rule,
393 * bits_tree b,
394 * int n);
395 * int bits_tree_remove (alloc_limits lim,
396 * struct bits_tree_rule * rule,
397 * bits_tree b, int n);
398 * int bits_tree_toggle (alloc_limits lim,
399 * struct bits_tree_rule * rule,
400 * bits_tree b,
401 * int n);
402 * void bits_tree_clear (alloc_limits lim,
403 * struct bits_tree_rule * rule,
404 * bits_tree b);
405 * void bits_tree_fill (alloc_limits lim,
406 * struct bits_tree_rule * rule,
407 * bits_tree b);
408 * int bits_tree_clear_range (alloc_limits lim,
409 * struct bits_tree_rule * rule,
410 * bits_tree b,
411 * int from,
412 * int to);
413 * int bits_tree_fill_range (alloc_limits lim,
414 * struct bits_tree_rule * rule,
415 * bits_tree b,
416 * int from,
417 * int to);
418 * void bits_tree_complement (alloc_limits lim,
419 * struct bits_tree_rule * rule,
420 * bits_tree b);
421 * int bits_tree_assign (alloc_limits lim,
422 * struct bits_tree_rule * rule,
423 * bits_tree a,
424 * bits_tree b);
425 * int bits_tree_union (alloc_limits lim,
426 * struct bits_tree_rule * rule,
427 * bits_tree a,
428 * bits_tree b);
429 * int bits_tree_intersection (alloc_limits lim,
430 * struct bits_tree_rule * rule,
431 * bits_tree a,
432 * bits_tree b);
433 * int bits_tree_difference (alloc_limits lim,
434 * struct bits_tree_rule * rule,
435 * bits_tree a,
436 * bits_tree b);
437 * int bits_tree_revdifference (alloc_limits lim,
438 * struct bits_tree_rule * rule,
439 * bits_tree a,
440 * bits_tree b);
441 * int bits_tree_xor (alloc_limits lim,
442 * struct bits_tree_rule * rule,
443 * bits_tree a,
444 * bits_tree b);
445 * int bits_tree_population (alloc_limits lim,
446 * struct bits_tree_rule * rule,
447 * bits_tree a);
448 * int bits_tree_population_range (alloc_limits lim,
449 * struct bits_tree_rule * rule,
450 * bits_tree a, int from, int to);
451 * int bits_tree_ffs (alloc_limits lim,
452 * struct bits_tree_rule * rule,
453 * bits_tree b);
454 * int bits_tree_ffc (alloc_limits lim,
455 * struct bits_tree_rule * rule,
456 * bits_tree b);
457 * int bits_tree_ffs_range (alloc_limits lim,
458 * struct bits_tree_rule * rule,
459 * bits_tree b,
460 * int from,
461 * int to);
462 * int bits_tree_ffc_range (alloc_limits lim,
463 * struct bits_tree_rule * rule,
464 * bits_tree b,
465 * int from,
466 * int to);
467 *
468 * Each function performs the same operation as the corresponding
469 * `bitset_' function (replace `bits_tree' with `bitset_'.)
470 * For documentation, see xref:"Flat Bitsets". For that reason,
471 * the `bits_tree_' functions are not individually documented.
472 *
473 * Each `bits_tree' function takes two initial parameters, `lim' and `rule'.
474 *
475 * `lim' describes allocation limits that apply to the bitset tree(s)
476 * being operated upon. For more information about allocation limits,
477 * see xref:"Allocation With Limitations".
478 *
479 * `rule' describes the branching structure of the bitset trees.
480 * See xref:"Bitset Tree Rules".
481 *
482 * These functions:
483 *
484 * bits_tree_adjoin
485 * bits_tree_remove
486 * bits_tree_toggle
487 * bits_tree_clear
488 * bits_tree_fill
489 * bits_tree_clear_range
490 * bits_tree_fill_range
491 * bits_tree_complement
492 * bits_tree_assign
493 * bits_tree_union
494 * bits_tree_intersection
495 * bits_tree_difference
496 * bits_tree_revdifference
497 * bits_tree_xor
498 *
499 * return a value of type `int'. All of them will sometimes allocate
500 * memory.
501 *
502 * If an allocation fails, these functions return -1 and have
503 * indeterminate side effect on the set being operated upon.
504 *
505 * If all allocations succeed, they return 0 (and have the intended
506 * side effect on the set being operated upon).
507 */
508
509 int
bits_tree_is_member(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int n)510 bits_tree_is_member (alloc_limits lim,
511 struct bits_tree_rule * rule,
512 bits_tree b,
513 int n)
514 {
515 int bs;
516
517 if (!rule->fanout)
518 {
519 return bitset_is_member ((bitset)b, n);
520 }
521
522 bs = bits_tree_which_bitset (lim, rule, n);
523 if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
524 return 1;
525 else if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
526 return 0;
527 else
528 return bits_tree_is_member (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
529 }
530
531
532 static int
bits_tree_is_full_bitset(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)533 bits_tree_is_full_bitset (alloc_limits lim,
534 struct bits_tree_rule * rule,
535 bits_tree a)
536 {
537 return ( (a == bits_tree_full_bitset)
538 || ( (a != bits_tree_empty_bitset)
539 && (rule->subset_size == bits_tree_population (lim, rule + 1, a))));
540 }
541
542
543 static int
bits_tree_is_empty_bitset(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)544 bits_tree_is_empty_bitset (alloc_limits lim,
545 struct bits_tree_rule * rule,
546 bits_tree a)
547 {
548 return ( (a == bits_tree_empty_bitset)
549 || ( (a != bits_tree_full_bitset)
550 && (0 == bits_tree_population (lim, rule + 1, a))));
551 }
552
553
554
555 int
bits_tree_is_equal(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)556 bits_tree_is_equal (alloc_limits lim,
557 struct bits_tree_rule * rule,
558 bits_tree a, bits_tree b)
559 {
560 int x;
561
562 if (!rule->fanout)
563 {
564 return bitset_is_equal (rule->subset_size, (bitset)a, (bitset)b);
565 }
566
567 for (x = 0; x < rule->fanout; ++x)
568 {
569 if (((bits_tree *)a)[x] == bits_tree_full_bitset)
570 {
571 if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)b)[x]))
572 return 0;
573 }
574 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
575 {
576 if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)b)[x]))
577 return 0;
578 }
579 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
580 {
581 if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[x]))
582 return 0;
583 }
584 else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
585 {
586 if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[x]))
587 return 0;
588 }
589 else if (!bits_tree_is_equal (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
590 return 0;
591 }
592 return 1;
593 }
594
595
596 int
bits_tree_is_subset(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)597 bits_tree_is_subset (alloc_limits lim,
598 struct bits_tree_rule * rule,
599 bits_tree a,
600 bits_tree b)
601 {
602 int x;
603
604 if (!rule->fanout)
605 {
606 return bitset_is_subset (rule->subset_size, (bitset)a, (bitset)b);
607 }
608
609 for (x = 0; x < rule->fanout; ++x)
610 {
611 if (((bits_tree *)a)[x] == bits_tree_full_bitset)
612 continue;
613 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
614 {
615 if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)b)[x]))
616 return 0;
617 }
618 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
619 return 0;
620 else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
621 continue;
622 else
623 if (!bits_tree_is_subset (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
624 return 0;
625 }
626 return 1;
627 }
628
629
630 int
bits_tree_is_empty(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)631 bits_tree_is_empty (alloc_limits lim,
632 struct bits_tree_rule * rule,
633 bits_tree a)
634 {
635 int x;
636
637 if (!rule->fanout)
638 {
639 return bitset_is_empty (rule->subset_size, (bitset)a);
640 }
641
642 for (x = 0; x < rule->fanout; ++x)
643 {
644 if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[x]))
645 return 0;
646 }
647 return 1;
648 }
649
650
651 int
bits_tree_is_full(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)652 bits_tree_is_full (alloc_limits lim,
653 struct bits_tree_rule * rule,
654 bits_tree a)
655 {
656 int x;
657
658 if (!rule->fanout)
659 {
660 return bitset_is_full (rule->subset_size, (bitset)a);
661 }
662
663 for (x = 0; x < rule->fanout; ++x)
664 {
665 if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[x]))
666 return 0;
667 }
668 return 1;
669 }
670
671
672 int
bits_tree_is_empty_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,int from,int to)673 bits_tree_is_empty_range (alloc_limits lim,
674 struct bits_tree_rule * rule,
675 bits_tree a,
676 int from,
677 int to)
678 {
679 int first_bs;
680 int first_bit;
681 int last_bs;
682 int last_bit;
683
684 if (!rule->fanout)
685 {
686 return bitset_is_empty_range ((bitset)a, from, to);
687 }
688
689 if (to <= from)
690 return 1;
691
692 first_bs = bits_tree_which_bitset (lim, rule, from);
693 first_bit = bits_tree_which_bit (lim, rule, from);
694
695 last_bs = bits_tree_which_bitset (lim, rule, to);
696 last_bit = bits_tree_which_bit (lim, rule, to);
697
698 if (first_bs == last_bs)
699 {
700 if (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
701 return 0;
702 if (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
703 return 1;
704 return bits_tree_is_empty_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, last_bit);
705 }
706 else
707 {
708 int x;
709
710 if ( (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
711 || ( (((bits_tree *)a)[first_bs] != bits_tree_empty_bitset)
712 && !bits_tree_is_empty_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, rule->subset_size)))
713 return 0;
714
715 if ( last_bit
716 && ((((bits_tree *)a)[last_bs] == bits_tree_full_bitset)
717 || ( (((bits_tree *)a)[last_bs] != bits_tree_empty_bitset)
718 && !bits_tree_is_empty_range (lim, rule + 1, ((bits_tree *)a)[last_bs], 0, last_bit))))
719 return 0;
720
721 for (x = first_bs + 1; x < last_bs; ++x)
722 {
723 if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[x]))
724 return 0;
725 }
726 return 1;
727 }
728 }
729
730 int
bits_tree_is_full_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,int from,int to)731 bits_tree_is_full_range (alloc_limits lim,
732 struct bits_tree_rule * rule,
733 bits_tree a,
734 int from,
735 int to)
736 {
737 int first_bs;
738 int first_bit;
739 int last_bs;
740 int last_bit;
741
742 if (!rule->fanout)
743 {
744 return bitset_is_full_range ((bitset)a, from, to);
745 }
746
747 if (to <= from)
748 return 1;
749
750 first_bs = bits_tree_which_bitset (lim, rule, from);
751 first_bit = bits_tree_which_bit (lim, rule, from);
752
753 last_bs = bits_tree_which_bitset (lim, rule, to);
754 last_bit = bits_tree_which_bit (lim, rule, to);
755
756 if (first_bs == last_bs)
757 {
758 if (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
759 return 1;
760 if (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
761 return 0;
762 return bits_tree_is_full_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, last_bit);
763 }
764 else
765 {
766 int x;
767
768 if ( (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
769 || ( (((bits_tree *)a)[first_bs] != bits_tree_full_bitset)
770 && !bits_tree_is_full_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, rule->subset_size)))
771 return 0;
772
773 if ( last_bit
774 && ((((bits_tree *)a)[last_bs] == bits_tree_empty_bitset)
775 || ( (((bits_tree *)a)[last_bs] != bits_tree_full_bitset)
776 && !bits_tree_is_full_range (lim, rule + 1, ((bits_tree *)a)[last_bs], 0, last_bit))))
777 return 0;
778
779 for (x = first_bs + 1; x < last_bs; ++x)
780 {
781 if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[x]))
782 return 0;
783 }
784 return 1;
785 }
786 }
787
788 int
bits_tree_adjoin(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int n)789 bits_tree_adjoin (alloc_limits lim,
790 struct bits_tree_rule * rule,
791 bits_tree b,
792 int n)
793 {
794 int bs;
795
796 if (!rule->fanout)
797 {
798 bitset_adjoin ((bitset)b, n);
799 return 0;
800 }
801
802 bs = bits_tree_which_bitset (lim, rule, n);
803 if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
804 return 0;
805
806 if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
807 {
808 ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
809 if (!((bits_tree *)b)[bs])
810 {
811 ((bits_tree *)b)[bs] = bits_tree_empty_bitset;
812 return -1;
813 }
814 }
815
816 return bits_tree_adjoin (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
817 }
818
819
820 int
bits_tree_remove(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int n)821 bits_tree_remove (alloc_limits lim,
822 struct bits_tree_rule * rule,
823 bits_tree b, int n)
824 {
825 int bs;
826
827 if (!rule->fanout)
828 {
829 bitset_remove ((bitset)b, n);
830 return 0;
831 }
832
833 bs = bits_tree_which_bitset (lim, rule, n);
834
835 if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
836 return 0;
837
838 if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
839 {
840 ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
841 if (!((bits_tree *)b)[bs])
842 {
843 ((bits_tree *)b)[bs] = bits_tree_full_bitset;
844 return -1;
845 }
846 bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[bs]);
847 }
848 return bits_tree_remove (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
849 }
850
851
852 int
bits_tree_toggle(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int n)853 bits_tree_toggle (alloc_limits lim,
854 struct bits_tree_rule * rule,
855 bits_tree b,
856 int n)
857 {
858 int bs;
859
860 if (!rule->fanout)
861 {
862 bitset_toggle ((bitset)b, n);
863 return 0;
864 }
865
866 bs = bits_tree_which_bitset (lim, rule, n);
867
868 if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
869 {
870 ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
871 if (!((bits_tree *)b)[bs])
872 {
873 ((bits_tree *)b)[bs] = bits_tree_empty_bitset;
874 return -1;
875 }
876 }
877 else if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
878 {
879 ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
880 if (!((bits_tree *)b)[bs])
881 {
882 ((bits_tree *)b)[bs] = bits_tree_full_bitset;
883 return -1;
884 }
885 bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[bs]);
886 }
887 return bits_tree_toggle (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
888 }
889
890
891 void
bits_tree_clear(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b)892 bits_tree_clear (alloc_limits lim,
893 struct bits_tree_rule * rule,
894 bits_tree b)
895 {
896 int x;
897
898 if (!rule->fanout)
899 {
900 bitset_clear (rule->subset_size, (bitset)b);
901 return;
902 }
903
904 for (x = 0; x < rule->fanout; ++x)
905 {
906 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
907 ((bits_tree *)b)[x] = bits_tree_empty_bitset;
908 else if (((bits_tree *)b)[x] != bits_tree_empty_bitset)
909 {
910 bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
911 ((bits_tree *)b)[x] = bits_tree_empty_bitset;
912 }
913 }
914 }
915
916
917 void
bits_tree_fill(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b)918 bits_tree_fill (alloc_limits lim,
919 struct bits_tree_rule * rule,
920 bits_tree b)
921 {
922 int x;
923
924 if (!rule->fanout)
925 {
926 bitset_fill (rule->subset_size, (bitset)b);
927 return;
928 }
929
930 for (x = 0; x < rule->fanout; ++x)
931 {
932 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
933 ((bits_tree *)b)[x] = bits_tree_full_bitset;
934 else if (((bits_tree *)b)[x] != bits_tree_full_bitset)
935 {
936 bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
937 ((bits_tree *)b)[x] = bits_tree_full_bitset;
938 }
939 }
940 }
941
942
943 int
bits_tree_clear_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int from,int to)944 bits_tree_clear_range (alloc_limits lim,
945 struct bits_tree_rule * rule,
946 bits_tree b,
947 int from,
948 int to)
949 {
950 int first_bs;
951 int first_bit;
952 int last_bs;
953 int last_bit;
954
955 if (!rule->fanout)
956 {
957 bitset_clear_range ((bitset)b, from, to);
958 return 0;
959 }
960
961 if (to <= from)
962 return 0;
963
964 first_bs = bits_tree_which_bitset (lim, rule, from);
965 first_bit = bits_tree_which_bit (lim, rule, from);
966
967 last_bs = bits_tree_which_bitset (lim, rule, to);
968 last_bit = bits_tree_which_bit (lim, rule, to);
969
970 if (first_bs == last_bs)
971 {
972 if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
973 return 0;
974
975 if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
976 {
977 ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
978 if (!((bits_tree *)b)[first_bs])
979 {
980 ((bits_tree *)b)[first_bs] = bits_tree_full_bitset;
981 return -1;
982 }
983 bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[first_bs]);
984 }
985
986 return bits_tree_clear_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);
987 }
988 else
989 {
990 int x;
991
992 if (((bits_tree *)b)[first_bs] != bits_tree_empty_bitset)
993 {
994 if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
995 {
996 ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
997 if (!((bits_tree *)b)[first_bs])
998 {
999 ((bits_tree *)b)[first_bs] = bits_tree_full_bitset;
1000 return -1;
1001 }
1002 bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[first_bs]);
1003 }
1004 if (bits_tree_clear_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size))
1005 return -1;
1006 }
1007
1008 if (last_bit)
1009 {
1010 if (((bits_tree *)b)[last_bs] != bits_tree_empty_bitset)
1011 {
1012 if (((bits_tree *)b)[last_bs] == bits_tree_full_bitset)
1013 {
1014 ((bits_tree *)b)[last_bs] = bits_tree_alloc (lim, rule + 1);
1015 if (!((bits_tree *)b)[last_bs])
1016 {
1017 ((bits_tree *)b)[last_bs] = bits_tree_full_bitset;
1018 return -1;
1019 }
1020 bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[last_bs]);
1021 }
1022 if (bits_tree_clear_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit))
1023 return -1;
1024 }
1025 }
1026
1027 for (x = first_bs + 1; x < last_bs; ++x)
1028 {
1029 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1030 continue;
1031 if (((bits_tree *)b)[x] != bits_tree_full_bitset)
1032 bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
1033 ((bits_tree *)b)[x] = bits_tree_empty_bitset;
1034 }
1035 return 0;
1036 }
1037 }
1038
1039
1040 int
bits_tree_fill_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int from,int to)1041 bits_tree_fill_range (alloc_limits lim,
1042 struct bits_tree_rule * rule,
1043 bits_tree b,
1044 int from,
1045 int to)
1046 {
1047 int first_bs;
1048 int first_bit;
1049 int last_bs;
1050 int last_bit;
1051
1052 if (!rule->fanout)
1053 {
1054 bitset_fill_range ((bitset)b, from, to);
1055 return 0;
1056 }
1057
1058 if (to <= from)
1059 return 0;
1060
1061 first_bs = bits_tree_which_bitset (lim, rule, from);
1062 first_bit = bits_tree_which_bit (lim, rule, from);
1063
1064 last_bs = bits_tree_which_bitset (lim, rule, to);
1065 last_bit = bits_tree_which_bit (lim, rule, to);
1066
1067 if (first_bs == last_bs)
1068 {
1069 if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
1070 return 0;
1071
1072 if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
1073 {
1074 ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
1075 if (!((bits_tree *)b)[first_bs])
1076 {
1077 ((bits_tree *)b)[first_bs] = bits_tree_empty_bitset;
1078 return -1;
1079 }
1080 }
1081
1082 return bits_tree_fill_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);
1083 }
1084 else
1085 {
1086 int x;
1087
1088 if (((bits_tree *)b)[first_bs] != bits_tree_full_bitset)
1089 {
1090 if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
1091 {
1092 ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
1093 if (!((bits_tree *)b)[first_bs])
1094 {
1095 ((bits_tree *)b)[first_bs] = bits_tree_full_bitset;
1096 return -1;
1097 }
1098 }
1099 if (bits_tree_fill_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size))
1100 return -1;
1101 }
1102
1103 if (last_bit)
1104 {
1105 if (((bits_tree *)b)[last_bs] != bits_tree_full_bitset)
1106 {
1107 if (((bits_tree *)b)[last_bs] == bits_tree_empty_bitset)
1108 {
1109 ((bits_tree *)b)[last_bs] = bits_tree_alloc (lim, rule + 1);
1110 if (!((bits_tree *)b)[last_bs])
1111 {
1112 ((bits_tree *)b)[last_bs] = bits_tree_empty_bitset;
1113 return -1;
1114 }
1115 }
1116 if (bits_tree_fill_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit))
1117 return -1;
1118 }
1119 }
1120
1121 for (x = first_bs + 1; x < last_bs; ++x)
1122 {
1123 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1124 continue;
1125 if (((bits_tree *)b)[x] != bits_tree_empty_bitset)
1126 bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
1127 ((bits_tree *)b)[x] = bits_tree_full_bitset;
1128 }
1129 return 0;
1130 }
1131 }
1132
1133
1134 void
bits_tree_complement(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b)1135 bits_tree_complement (alloc_limits lim,
1136 struct bits_tree_rule * rule,
1137 bits_tree b)
1138 {
1139 int x;
1140
1141 if (!rule->fanout)
1142 {
1143 bitset_complement (rule->subset_size, (bitset)b);
1144 return;
1145 }
1146
1147 for (x = 0; x < rule->fanout; ++x)
1148 {
1149 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1150 ((bits_tree *)b)[x] = bits_tree_full_bitset;
1151 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1152 ((bits_tree *)b)[x] = bits_tree_empty_bitset;
1153 else
1154 bits_tree_complement (lim, rule + 1, ((bits_tree *)b)[x]);
1155 }
1156 }
1157
1158
1159 int
bits_tree_assign(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)1160 bits_tree_assign (alloc_limits lim,
1161 struct bits_tree_rule * rule,
1162 bits_tree a,
1163 bits_tree b)
1164 {
1165 int x;
1166
1167 if (!rule->fanout)
1168 {
1169 bitset_assign (rule->subset_size, (bitset)a, (bitset)b);
1170 return 0;
1171 }
1172
1173 for (x = 0; x < rule->fanout; ++x)
1174 {
1175 if ( (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1176 || (((bits_tree *)b)[x] == bits_tree_full_bitset))
1177 {
1178 if ( (((bits_tree *)a)[x] != bits_tree_empty_bitset)
1179 && (((bits_tree *)a)[x] != bits_tree_full_bitset))
1180 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
1181 ((bits_tree *)a)[x] = ((bits_tree *)b)[x];
1182 }
1183 else
1184 {
1185 if ( (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1186 || (((bits_tree *)a)[x] == bits_tree_full_bitset))
1187 {
1188 ((bits_tree *)a)[x] = bits_tree_alloc (lim, rule + 1);
1189 if (!((bits_tree *)a)[x])
1190 {
1191 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1192 return -1;
1193 }
1194 }
1195 if (bits_tree_assign (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
1196 return -1;
1197 }
1198 }
1199 return 0;
1200 }
1201
1202
1203 int
bits_tree_union(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)1204 bits_tree_union (alloc_limits lim,
1205 struct bits_tree_rule * rule,
1206 bits_tree a,
1207 bits_tree b)
1208 {
1209 int x;
1210
1211 if (!rule->fanout)
1212 {
1213 bitset_union (rule->subset_size, (bitset)a, (bitset)b);
1214 return 0;
1215 }
1216
1217 for (x = 0; x < rule->fanout; ++x)
1218 {
1219 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1220 {
1221 if ( (((bits_tree *)a)[x] != bits_tree_empty_bitset)
1222 && (((bits_tree *)a)[x] != bits_tree_full_bitset))
1223 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
1224 ((bits_tree *)a)[x] = bits_tree_full_bitset;
1225 }
1226 else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1227 continue;
1228 else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1229 continue;
1230 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1231 {
1232 ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
1233 if (!((bits_tree *)a)[x])
1234 {
1235 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1236 return -1;
1237 }
1238 }
1239 else
1240 if (bits_tree_union (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
1241 return -1;
1242 }
1243 return 0;
1244 }
1245
1246
1247 int
bits_tree_intersection(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)1248 bits_tree_intersection (alloc_limits lim,
1249 struct bits_tree_rule * rule,
1250 bits_tree a,
1251 bits_tree b)
1252 {
1253 int x;
1254
1255 if (!rule->fanout)
1256 {
1257 bitset_intersection (rule->subset_size, (bitset)a, (bitset)b);
1258 return 0;
1259 }
1260
1261 for (x = 0; x < rule->fanout; ++x)
1262 {
1263 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1264 {
1265 if ( (((bits_tree *)a)[x] != bits_tree_empty_bitset)
1266 && (((bits_tree *)a)[x] != bits_tree_full_bitset))
1267 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
1268 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1269 }
1270 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1271 continue;
1272 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1273 continue;
1274 else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1275 {
1276 ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
1277 if (!((bits_tree *)a)[x])
1278 {
1279 ((bits_tree *)a)[x] = bits_tree_full_bitset;
1280 return -1;
1281 }
1282 }
1283 else
1284 if (bits_tree_intersection (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
1285 return -1;
1286 }
1287 return 0;
1288 }
1289
1290
1291 int
bits_tree_difference(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)1292 bits_tree_difference (alloc_limits lim,
1293 struct bits_tree_rule * rule,
1294 bits_tree a,
1295 bits_tree b)
1296 {
1297 int x;
1298
1299 if (!rule->fanout)
1300 {
1301 bitset_difference (rule->subset_size, (bitset)a, (bitset)b);
1302 return 0;
1303 }
1304
1305 for (x = 0; x < rule->fanout; ++x)
1306 {
1307 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1308 {
1309 if ( (((bits_tree *)a)[x] != bits_tree_empty_bitset)
1310 && (((bits_tree *)a)[x] != bits_tree_full_bitset))
1311 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
1312 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1313 }
1314 else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1315 continue;
1316 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1317 continue;
1318 else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1319 {
1320 ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
1321 if (!((bits_tree *)a)[x])
1322 {
1323 ((bits_tree *)a)[x] = bits_tree_full_bitset;
1324 return -1;
1325 }
1326 bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
1327 }
1328 else
1329 if (bits_tree_difference (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
1330 return -1;
1331 }
1332 return 0;
1333 }
1334
1335
1336 int
bits_tree_revdifference(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)1337 bits_tree_revdifference (alloc_limits lim,
1338 struct bits_tree_rule * rule,
1339 bits_tree a,
1340 bits_tree b)
1341 {
1342 int x;
1343
1344 if (!rule->fanout)
1345 {
1346 bitset_revdifference (rule->subset_size, (bitset)a, (bitset)b);
1347 return 0;
1348 }
1349
1350 for (x = 0; x < rule->fanout; ++x)
1351 {
1352 if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1353 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1354 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1355 {
1356 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1357 continue;
1358 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1359 ((bits_tree *)a)[x] = ((bits_tree *)b)[x];
1360 else
1361 {
1362 ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
1363 if (!((bits_tree *)a)[x])
1364 {
1365 ((bits_tree *)a)[x] = bits_tree_full_bitset;
1366 return -1;
1367 }
1368 }
1369 }
1370 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1371 bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
1372 else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1373 {
1374 if ( (((bits_tree *)a)[x] != bits_tree_empty_bitset)
1375 && (((bits_tree *)a)[x] != bits_tree_full_bitset))
1376 bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
1377 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1378 }
1379 else
1380 {
1381 if (bits_tree_revdifference (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
1382 return -1;
1383 }
1384 }
1385 return 0;
1386 }
1387
1388
1389 int
bits_tree_xor(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,bits_tree b)1390 bits_tree_xor (alloc_limits lim,
1391 struct bits_tree_rule * rule,
1392 bits_tree a,
1393 bits_tree b)
1394 {
1395 int x;
1396
1397 if (!rule->fanout)
1398 {
1399 bitset_xor (rule->subset_size, (bitset)a, (bitset)b);
1400 return 0;
1401 }
1402
1403 for (x = 0; x < rule->fanout; ++x)
1404 {
1405 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1406 continue;
1407 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1408 {
1409 if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1410 ((bits_tree *)a)[x] = bits_tree_full_bitset;
1411 else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1412 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1413 else
1414 bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
1415 }
1416 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1417 {
1418 if ( (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1419 || (((bits_tree *)b)[x] == bits_tree_full_bitset))
1420 ((bits_tree *)a)[x] = ((bits_tree *)b)[x];
1421 else
1422 {
1423 ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
1424 if (!((bits_tree *)a)[x])
1425 {
1426 ((bits_tree *)a)[x] = bits_tree_empty_bitset;
1427 return -1;
1428 }
1429 }
1430 }
1431 else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1432 {
1433 ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
1434 if (!((bits_tree *)a)[x])
1435 {
1436 ((bits_tree *)a)[x] = bits_tree_full_bitset;
1437 return -1;
1438 }
1439 bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
1440 }
1441 else
1442 {
1443 if (bits_tree_xor (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
1444 return -1;
1445 }
1446 }
1447 return 0;
1448 }
1449
1450
1451 int
bits_tree_population(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a)1452 bits_tree_population (alloc_limits lim,
1453 struct bits_tree_rule * rule,
1454 bits_tree a)
1455 {
1456 int x;
1457 int pop;
1458
1459 if (!rule->fanout)
1460 {
1461 return bitset_population (rule->subset_size, (bitset)a);
1462 }
1463
1464 pop = 0;
1465 for (x = 0; x < rule->fanout; ++x)
1466 {
1467 if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1468 pop += rule->subset_size;
1469 else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1470 continue;
1471 else
1472 pop += bits_tree_population (lim, rule + 1, ((bits_tree *)a)[x]);
1473 }
1474 return pop;
1475 }
1476
1477
1478 int
bits_tree_population_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree a,int from,int to)1479 bits_tree_population_range (alloc_limits lim,
1480 struct bits_tree_rule * rule,
1481 bits_tree a, int from, int to)
1482 {
1483 int first_bs;
1484 int first_bit;
1485 int last_bs;
1486 int last_bit;
1487
1488 if (!rule->fanout)
1489 {
1490 return bitset_population_range ((bitset)a, from, to);
1491 }
1492
1493 if (to <= from)
1494 return 0;
1495
1496 first_bs = bits_tree_which_bitset (lim, rule, from);
1497 first_bit = bits_tree_which_bit (lim, rule, from);
1498
1499 last_bs = bits_tree_which_bitset (lim, rule, to);
1500 last_bit = bits_tree_which_bit (lim, rule, to);
1501
1502 if (first_bs == last_bs)
1503 {
1504 if (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
1505 return last_bit - first_bit;
1506 if (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
1507 return 0;
1508 return bits_tree_population_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, last_bit);
1509 }
1510 else
1511 {
1512 int pop;
1513 int x;
1514
1515 if (bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[first_bs]))
1516 pop = 0;
1517 else if (bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[first_bs]))
1518 pop = rule->subset_size - first_bit;
1519 else
1520 pop = bits_tree_population_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, rule->subset_size);
1521
1522 if (last_bit)
1523 {
1524 if (bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[last_bs]))
1525 pop += 0;
1526 else if (bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[last_bs]))
1527 pop += last_bit;
1528 else
1529 pop += bits_tree_population_range (lim, rule + 1, ((bits_tree *)a)[last_bs], 0, last_bit);
1530 }
1531
1532 for (x = first_bs + 1; x < last_bs; ++x)
1533 {
1534 if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
1535 pop += 0;
1536 else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
1537 pop += rule->subset_size;
1538 else
1539 pop += bits_tree_population (lim, rule + 1, ((bits_tree *)a)[x]);
1540 }
1541 return pop;
1542 }
1543 }
1544
1545
1546 int
bits_tree_ffs(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b)1547 bits_tree_ffs (alloc_limits lim,
1548 struct bits_tree_rule * rule,
1549 bits_tree b)
1550 {
1551 int x;
1552 int offset;
1553
1554 if (!rule->fanout)
1555 {
1556 return bitset_ffs (rule->subset_size, (bitset)b);
1557 }
1558
1559 for (x = 0, offset = 0; x < rule->fanout; ++x, offset += rule->subset_size)
1560 {
1561 int fs;
1562
1563 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1564 continue;
1565 else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1566 return offset;
1567 else
1568 {
1569 fs = bits_tree_ffs (lim, rule + 1, ((bits_tree *)b)[x]);
1570 if (fs >= 0)
1571 return fs + offset;
1572 }
1573 }
1574 return -1;
1575 }
1576
1577
1578 int
bits_tree_ffc(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b)1579 bits_tree_ffc (alloc_limits lim, struct bits_tree_rule * rule, bits_tree b)
1580 {
1581 int x;
1582 int offset;
1583
1584 if (!rule->fanout)
1585 {
1586 return bitset_ffc (rule->subset_size, (bitset)b);
1587 }
1588
1589 for (x = 0, offset = 0; x < rule->fanout; ++x, offset += rule->subset_size)
1590 {
1591 int fc;
1592
1593 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1594 continue;
1595 else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1596 return offset;
1597 else
1598 {
1599 fc = bits_tree_ffc (lim, rule + 1, ((bits_tree *)b)[x]);
1600 if (fc >= 0)
1601 return fc + offset;
1602 }
1603 }
1604 return -1;
1605 }
1606
1607
1608 int
bits_tree_ffs_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int from,int to)1609 bits_tree_ffs_range (alloc_limits lim,
1610 struct bits_tree_rule * rule,
1611 bits_tree b,
1612 int from,
1613 int to)
1614 {
1615 int first_bs;
1616 int first_bit;
1617 int last_bs;
1618 int last_bit;
1619
1620 if (!rule->fanout)
1621 {
1622 return bitset_ffs_range ((bitset)b, from, to);
1623 }
1624
1625 if (to <= from)
1626 return -1;
1627
1628 first_bs = bits_tree_which_bitset (lim, rule, from);
1629 first_bit = bits_tree_which_bit (lim, rule, from);
1630
1631 last_bs = bits_tree_which_bitset (lim, rule, to);
1632 last_bit = bits_tree_which_bit (lim, rule, to);
1633
1634 if (first_bs == last_bs)
1635 {
1636 int fs;
1637
1638 if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
1639 return -1;
1640
1641 if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
1642 return from;
1643
1644 fs = bits_tree_ffs_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);
1645
1646 if (fs < 0)
1647 return -1;
1648 else
1649 return (first_bs * rule->subset_size) + fs;
1650 }
1651 else
1652 {
1653 int x;
1654
1655 if (((bits_tree *)b)[first_bs] != bits_tree_empty_bitset)
1656 {
1657 int fs;
1658 if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
1659 return from;
1660
1661 fs = bits_tree_ffs_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size);
1662 if (fs >= 0)
1663 return (first_bs * rule->subset_size) + fs;
1664 }
1665
1666 for (x = first_bs + 1; x < last_bs; ++x)
1667 {
1668 int fs;
1669 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1670 continue;
1671 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1672 return (x * rule->subset_size);
1673 fs = bits_tree_ffs (lim, rule + 1, ((bits_tree *)b)[x]);
1674 if (fs >= 0)
1675 return (x * rule->subset_size) + fs;
1676 }
1677
1678 if (last_bit)
1679 {
1680 if (((bits_tree *)b)[last_bs] != bits_tree_empty_bitset)
1681 {
1682 if (((bits_tree *)b)[last_bs] == bits_tree_full_bitset)
1683 return (last_bs * rule->subset_size);
1684 else
1685 {
1686 int fs;
1687
1688 fs = bits_tree_ffs_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit);
1689 if (fs >= 0)
1690 return (last_bs * rule->subset_size) + fs;
1691 }
1692 }
1693 }
1694
1695 return -1;
1696 }
1697 }
1698
1699
1700 int
bits_tree_ffc_range(alloc_limits lim,struct bits_tree_rule * rule,bits_tree b,int from,int to)1701 bits_tree_ffc_range (alloc_limits lim,
1702 struct bits_tree_rule * rule,
1703 bits_tree b,
1704 int from,
1705 int to)
1706 {
1707 int first_bs;
1708 int first_bit;
1709 int last_bs;
1710 int last_bit;
1711
1712 if (!rule->fanout)
1713 {
1714 return bitset_ffc_range ((bitset)b, from, to);
1715 }
1716
1717 if (to <= from)
1718 return -1;
1719
1720 first_bs = bits_tree_which_bitset (lim, rule, from);
1721 first_bit = bits_tree_which_bit (lim, rule, from);
1722
1723 last_bs = bits_tree_which_bitset (lim, rule, to);
1724 last_bit = bits_tree_which_bit (lim, rule, to);
1725
1726 if (first_bs == last_bs)
1727 {
1728 int fs;
1729
1730 if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
1731 return -1;
1732
1733 if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
1734 return from;
1735
1736 fs = bits_tree_ffc_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);
1737
1738 if (fs < 0)
1739 return -1;
1740 else
1741 return (first_bs * rule->subset_size) + fs;
1742 }
1743 else
1744 {
1745 int x;
1746
1747 if (((bits_tree *)b)[first_bs] != bits_tree_full_bitset)
1748 {
1749 int fs;
1750 if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
1751 return from;
1752
1753 fs = bits_tree_ffc_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size);
1754 if (fs >= 0)
1755 return (first_bs * rule->subset_size) + fs;
1756 }
1757
1758 for (x = first_bs + 1; x < last_bs; ++x)
1759 {
1760 int fs;
1761 if (((bits_tree *)b)[x] == bits_tree_full_bitset)
1762 continue;
1763 if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
1764 return (x * rule->subset_size);
1765 fs = bits_tree_ffc (lim, rule + 1, ((bits_tree *)b)[x]);
1766 if (fs >= 0)
1767 return (x * rule->subset_size) + fs;
1768 }
1769
1770 if (last_bit)
1771 {
1772 if (((bits_tree *)b)[last_bs] != bits_tree_full_bitset)
1773 {
1774 if (((bits_tree *)b)[last_bs] == bits_tree_empty_bitset)
1775 return (last_bs * rule->subset_size);
1776 else
1777 {
1778 int fs;
1779
1780 fs = bits_tree_ffc_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit);
1781 if (fs >= 0)
1782 return (last_bs * rule->subset_size) + fs;
1783 }
1784 }
1785 }
1786
1787 return -1;
1788 }
1789 }
1790
1791
1792