1 /* bitset.c - bitsets
2 *
3 ****************************************************************
4 * Copyright (C) 1998, 2000 Thomas Lord
5 *
6 * See the file "COPYING" for further information about
7 * the copyright and warranty status of this work.
8 */
9
10
11
12 #include "hackerlab/bugs/panic.h"
13 #include "hackerlab/mem/mem.h"
14 #include "hackerlab/bitsets/bitset.h"
15
16
17 /************************************************************************
18 *(h1 "Flat Bitsets"
19 * :includes ("hackerlab/bitset/bitset.h"))
20 *
21 * |subset|
22 * |flat bitset|
23 *
24 * A "bitset" (or "flat bitset") is a packed array whose elements are
25 * each 1 bit. A bitset can be considered a finite, ordered set of
26 * numbered entities.
27 *
28 * The type `bitset_subset' is a bitset small enough to fit in a
29 * variable of type `void *'. (See xref:"Portability Assumptions in
30 * the Hackerlab C Library".
31 *
32 * The type `bitset' is pointer to `bitset_subset'. Bitset functions
33 * generally operate on a pair of values: the `size' (measured in
34 * bits, an integer of type `bit_t') and the `set' (a pointer of type
35 * `bitset_subset *').
36 *
37 * |ranges (in bitset functions)| Some functions operate on an
38 * arbitrary subsequence of a bitset. Their arguments include a
39 * starting bit (`from'), and an ending bit (`to'); these have names
40 * that end in the suffix `_range'. When a function operates on a
41 * range of bits, the range is specified as a half-open interval. For
42 * example,
43 *
44 * bitset_clear_range (bits, from, to)
45 *
46 * changes the bits numbered:
47 *
48 * from ... to - 1
49 *
50 * and the bit numbered `to' is unaffected. This permits bit addresses
51 * to be used similarly to pointers: a range of `n' bits beginning
52 * at bit `pos' is:
53 *
54 * pos, pos + n
55 *
56 * Bitsets are ordinarily allocated in sizes rounded up to the
57 * nearest `sizeof (bitset_subset)'. Operations on bitsets, however,
58 * are precise: they modify only the bits in a bitset and no others.
59 * For that reason, it is safe to operate on a bitset with `N'
60 * elements as if it had only `M' elements (with `M < N'). Bits
61 * `M..N-1' will be unaffected.
62 */
63 /*(menu)
64 */
65
66 /*(include-documentation "bitset.h")
67 */
68
69
70 /* bitset_access(B,N,OP)
71 *
72 * Apply OP to the subset of bitset `B' containing element `N' and to
73 * a singleton subset containing a 1-bit in the position where element
74 * `N' resides.
75 */
76 #define bitset_access(B,N,OP) ((B)[bitset_which_subset(N)] OP ((bitset_subset)1 << ((N) & bitset_subset_mask)))
77
78
79 /************************************************************************
80 *(h2 "Allocating and Freeing Bitsets")
81 *
82 */
83
84
85 /*(c bitset_alloc)
86 * bitset bitset_alloc (alloc_limits limits, bit_t size);
87 *
88 * Allocate an empty bitset large enough to hold `size' members.
89 *
90 * Allocation is performed by `lim_malloc' using `limits'. See
91 * xref:"Allocation With Limitations".
92 */
93 bitset
bitset_alloc(alloc_limits limits,bit_t size)94 bitset_alloc (alloc_limits limits, bit_t size)
95 {
96 bitset b;
97 b = (bitset) lim_malloc (limits, sizeof_bitset (size));
98 bitset_clear (size, b);
99 return b;
100 }
101
102 /*(c bitset_free)
103 * void bitset_free (alloc_limits limits, bitset a);
104 *
105 * Free the bitset `a'.
106 *
107 * Deallocation is performed by `lim_free' using `limits'. See
108 * xref:"Allocation With Limitations".
109 */
110 void
bitset_free(alloc_limits limits,bitset a)111 bitset_free (alloc_limits limits, bitset a)
112 {
113 lim_free (limits, a);
114 }
115
116
117 /*(c bitset_dup)
118 * bitset bitset_dup (alloc_limits limits, bit_t size, bitset a);
119 *
120 * Allocate a copy of bitset `a' which has `size' members.
121 *
122 * Allocation is performed by `lim_malloc' using `limits'. See
123 * xref:"Allocation With Limitations".
124 */
125 bitset
bitset_dup(alloc_limits limits,bit_t size,bitset a)126 bitset_dup (alloc_limits limits, bit_t size, bitset a)
127 {
128 bitset cs;
129
130 cs = lim_malloc (limits, sizeof_bitset (size));
131 bitset_assign (size, cs, a);
132 return cs;
133 }
134
135
136
137
138
139 /************************************************************************
140 *(h2 "Tests on Bitsets")
141 *
142 *
143 *
144 */
145
146
147
148 /*(c bitset_is_member)
149 * int bitset_is_member (bitset b, bit_t n);
150 *
151 * Return bit `n' of bitset `b' (either 0 or 1).
152 */
153 int
bitset_is_member(bitset b,bit_t n)154 bitset_is_member (bitset b, bit_t n)
155 {
156 return !!bitset_access((b), (n), &);
157 }
158
159
160 /*(c bitset_is_equal)
161 * int bitset_is_equal (bit_t size, bitset a, bitset b);
162 *
163 * Compare two bitsets for equality. Both bitsets have `size'
164 * members. Return 1 if they are equal, 0 otherwise.
165 */
166 int
bitset_is_equal(bit_t size,bitset a,bitset b)167 bitset_is_equal (bit_t size, bitset a, bitset b)
168 {
169 bit_t x;
170 bit_t bits_in_last_subset;
171 bitset_subset last_bitset_subset_mask;
172
173 if (!size)
174 return 1;
175
176 x = bitset_numb_subsets(size) - 1;
177 bits_in_last_subset = (size - bits_per_subset * x);
178 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
179
180 if ((a[x] & last_bitset_subset_mask) != (b[x] & last_bitset_subset_mask))
181 return 0;
182
183 while (x--)
184 {
185 if (a[x] != b[x])
186 return 0;
187 }
188
189 return 1;
190 }
191
192
193 /*(c bitset_is_subset)
194 * int bitset_is_subset (bit_t size, bitset a, bitset b);
195 *
196 * Return 1 if bitset `b' is a subset of bitset `a', 0 otherwise.
197 */
198 int
bitset_is_subset(bit_t size,bitset a,bitset b)199 bitset_is_subset (bit_t size, bitset a, bitset b)
200 {
201 bit_t x;
202 bit_t bits_in_last_subset;
203 bitset_subset last_bitset_subset_mask;
204 bitset_subset a_bits;
205 bitset_subset b_bits;
206
207 if (!size)
208 return 1;
209
210 x = bitset_numb_subsets(size) - 1;
211 bits_in_last_subset = (size - bits_per_subset * x);
212 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
213
214 a_bits = (a[x] & last_bitset_subset_mask);
215 b_bits = (b[x] & last_bitset_subset_mask);
216 if ((a_bits | b_bits) != a_bits)
217 return 0;
218
219 while (x-- && ((a[x] | b[x]) == a[x]))
220 ;
221
222 return x == -1;
223 }
224
225
226 /*(c bitset_is_empty)
227 * int bitset_is_empty (bit_t size, bitset a);
228 *
229 * Return 1 if bitset `a' has no members.
230 */
231 int
bitset_is_empty(bit_t size,bitset a)232 bitset_is_empty (bit_t size, bitset a)
233 {
234 bit_t x;
235 bit_t bits_in_last_subset;
236 bitset_subset last_bitset_subset_mask;
237
238 if (!size)
239 return 1;
240
241 x = bitset_numb_subsets(size) - 1;
242 bits_in_last_subset = (size - bits_per_subset * x);
243 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
244
245 if (a[x] & last_bitset_subset_mask)
246 return 0;
247
248 while (x-- && !a[x])
249 ;
250
251 return x == -1;
252 }
253
254
255 /*(c bitset_is_empty_range)
256 * int bitset_is_empty_range (bitset a, bit_t from, bit_t to);
257 *
258 * Return 1 if bitset `a' has no members in the closed
259 * interval `[from ... to-1]'.
260 */
261 int
bitset_is_empty_range(bitset a,bit_t from,bit_t to)262 bitset_is_empty_range (bitset a, bit_t from, bit_t to)
263 {
264 bit_t first_subset;
265 bitset_subset first_bitset_subset_mask;
266 bit_t last_subset;
267 bitset_subset last_bitset_subset_mask;
268 bit_t x;
269
270 if (to <= from)
271 return 1;
272
273 --to;
274
275 first_subset = bitset_which_subset (from);
276 last_subset = bitset_which_subset (to);
277
278 first_bitset_subset_mask = ~(bitset_subset)0 << bitset_which_bit (from);
279 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - (1 + bitset_which_bit (to)));
280
281 if (first_subset == last_subset)
282 return !(a[first_subset] & first_bitset_subset_mask & last_bitset_subset_mask);
283
284 if (a[first_subset] & first_bitset_subset_mask)
285 return 0;
286
287 if (a[last_subset] & last_bitset_subset_mask)
288 return 0;
289
290 for (x = first_subset + 1; x < last_subset; ++x)
291 if (a[x])
292 return 0;
293
294 return 1;
295 }
296
297
298
299 /*(c bitset_is_full)
300 * int bitset_is_full (bit_t size, bitset a);
301 *
302 * Return 1 if bitset `a' is filled (all ones).
303 */
304 int
bitset_is_full(bit_t size,bitset a)305 bitset_is_full (bit_t size, bitset a)
306 {
307 bit_t x;
308 bit_t bits_in_last_subset;
309 bitset_subset last_bitset_subset_mask;
310
311 if (!size)
312 return 1;
313
314 x = bitset_numb_subsets(size) - 1;
315 bits_in_last_subset = (size - bits_per_subset * x);
316 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
317
318 if ((a[x] & last_bitset_subset_mask) != last_bitset_subset_mask)
319 return 0;
320
321 while (x-- && (a[x] == (bitset_subset)-1L))
322 ;
323
324 return x == -1;
325 }
326
327
328 /*(c bitset_is_full_range)
329 * int bitset_is_full_range (bitset a, bit_t from, bit_t to);
330 *
331 * Return 1 if bitset `a' is filled in the closed
332 * interval `[from .. to-1]'.
333 */
334 int
bitset_is_full_range(bitset a,bit_t from,bit_t to)335 bitset_is_full_range (bitset a, bit_t from, bit_t to)
336 {
337 bit_t first_subset;
338 bitset_subset first_bitset_subset_mask;
339 bit_t last_subset;
340 bitset_subset last_bitset_subset_mask;
341 bit_t x;
342
343 if (to <= from)
344 return 1;
345
346 first_subset = bitset_which_subset (from);
347 last_subset = bitset_which_subset (to);
348 first_bitset_subset_mask = ~(((bitset_subset)1 << (from & bitset_subset_mask)) - 1);
349 last_bitset_subset_mask = (((bitset_subset)1 << (to & bitset_subset_mask)) - 1);
350
351 if (first_subset == last_subset)
352 return ( (a[first_subset] & first_bitset_subset_mask & last_bitset_subset_mask)
353 == (first_bitset_subset_mask & last_bitset_subset_mask));
354
355 if ((a[first_subset] & first_bitset_subset_mask) != first_bitset_subset_mask)
356 return 0;
357
358 if ((a[last_subset] & last_bitset_subset_mask) != last_bitset_subset_mask)
359 return 0;
360
361 for (x = first_subset + 1; x < last_subset - 1; ++x)
362 if (a[x] != (bitset_subset)-1L)
363 return 0;
364
365 return 1;
366 }
367
368
369 /************************************************************************
370 *(h2 "Set Operations")
371 *
372 *
373 *
374 */
375
376
377 /*(c bitset_adjoin)
378 * void bitset_adjoin (bitset b, bit_t n);
379 *
380 * Set bit `n' of bitset `b' to 1.
381 */
382 void
bitset_adjoin(bitset b,bit_t n)383 bitset_adjoin (bitset b, bit_t n)
384 {
385 bitset_access((b), (n), |=);
386 }
387
388
389 /*(c bitset_remove)
390 * void bitset_remove (bitset b, bit_t n);
391 *
392 * Set bit `n' of bitset `b' to 0.
393 */
394 void
bitset_remove(bitset b,bit_t n)395 bitset_remove (bitset b, bit_t n)
396 {
397 bitset_access((b), (n), &= ~);
398 }
399
400
401 /*(c bitset_toggle)
402 * void bitset_toggle (bitset b, bit_t n);
403 *
404 * If bit `n' of bitset `b' is 1, set it to 0; if 0,
405 * set it to 1.
406 */
407 void
bitset_toggle(bitset b,bit_t n)408 bitset_toggle (bitset b, bit_t n)
409 {
410 bitset_access((b), (n), ^= );
411 }
412
413
414 /*(c bitset_clear)
415 * void bitset_clear (bit_t size, bitset b);
416 *
417 * Clear all bits of bitset `b'.
418 */
419 void
bitset_clear(bit_t size,bitset b)420 bitset_clear (bit_t size, bitset b)
421 {
422 bit_t x;
423 bit_t bits_in_last_subset;
424 bitset_subset last_bitset_subset_mask;
425
426 if (!size)
427 return;
428
429 x = bitset_numb_subsets(size) - 1;
430 bits_in_last_subset = (size - bits_per_subset * x);
431 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
432 b[x] &= ~last_bitset_subset_mask;
433 mem_set ((char *)b, 0, x * sizeof (bitset_subset));
434 }
435
436
437
438 /*(c bitset_clear_range)
439 * void bitset_clear_range (bitset b, bit_t from, bit_t to);
440 *
441 * Clear the bits `from .. to - 1' of bitset `b'.
442 */
443 void
bitset_clear_range(bitset b,bit_t from,bit_t to)444 bitset_clear_range (bitset b, bit_t from, bit_t to)
445 {
446 bitset bp;
447
448 while ((from < to) && (from % bits_per_subset))
449 {
450 bitset_remove (b, from);
451 ++from;
452 }
453
454 bp = b + bitset_which_subset (from);
455 while (from + bits_per_subset < to)
456 {
457 *bp = (bitset_subset)0;
458 ++bp;
459 from += bits_per_subset;
460 }
461
462 while (from < to)
463 {
464 bitset_remove (b, from);
465 ++from;
466 }
467 }
468
469
470 /*(c bitset_fill)
471 * void bitset_fill (bit_t size, bitset b);
472 *
473 * Set all bits of bitset `b'.
474 */
475 void
bitset_fill(bit_t size,bitset b)476 bitset_fill (bit_t size, bitset b)
477 {
478 bit_t x;
479 bit_t bits_in_last_subset;
480 bitset_subset last_bitset_subset_mask;
481
482 if (!size)
483 return;
484
485 x = bitset_numb_subsets(size) - 1;
486 bits_in_last_subset = (size - bits_per_subset * x);
487 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
488 b[x] |= last_bitset_subset_mask;
489 mem_set ((t_uchar *)b, 0xff, x * sizeof (bitset_subset));
490 }
491
492
493 /*(c bitset_fill_range)
494 * void bitset_fill_range (bitset b, bit_t from, bit_t to);
495 *
496 * Set the bits `from .. to - 1' of bitset `b'.
497 */
498 void
bitset_fill_range(bitset b,bit_t from,bit_t to)499 bitset_fill_range (bitset b, bit_t from, bit_t to)
500 {
501 bitset bp;
502
503 while ((from < to) && (from % bits_per_subset))
504 {
505 bitset_adjoin (b, from);
506 ++from;
507 }
508
509 bp = b + bitset_which_subset (from);
510 while (from + bits_per_subset < to)
511 {
512 *bp = ~(bitset_subset)0;
513 ++bp;
514 from += bits_per_subset;
515 }
516
517 while (from < to)
518 {
519 bitset_adjoin (b, from);
520 ++from;
521 }
522 }
523
524
525 /*(c bitset_complement)
526 * void bitset_complement (bit_t size, bitset b);
527 *
528 * Toggle all bits in bitset `b'.
529 */
530 void
bitset_complement(bit_t size,bitset b)531 bitset_complement (bit_t size, bitset b)
532 {
533 bit_t x;
534 bit_t bits_in_last_subset;
535 bitset_subset last_bitset_subset_mask;
536
537 if (!size)
538 return;
539
540 x = bitset_numb_subsets(size) - 1;
541 bits_in_last_subset = (size - bits_per_subset * x);
542 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
543
544 b[x] = ((b[x] & ~last_bitset_subset_mask) | (~b[x] & last_bitset_subset_mask));
545
546 while (x--)
547 {
548 *b = ~*b;
549 ++b;
550 }
551 }
552
553
554 /*(c bitset_assign)
555 * void bitset_assign (bit_t size, bitset a, bitset b);
556 *
557 * Copy bitset `b' to bitset `a'.
558 */
559 void
bitset_assign(bit_t size,bitset a,bitset b)560 bitset_assign (bit_t size, bitset a, bitset b)
561 {
562 bit_t x;
563 bit_t bits_in_last_subset;
564 bitset_subset last_bitset_subset_mask;
565
566 if (!size)
567 return;
568
569 x = bitset_numb_subsets(size) - 1;
570 bits_in_last_subset = (size - bits_per_subset * x);
571 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
572
573 a[x] = (a[x] & ~last_bitset_subset_mask) | (b[x] & last_bitset_subset_mask);
574
575 while (x--)
576 a[x] = b[x];
577 }
578
579
580 /*(c bitset_union)
581 * void bitset_union (bit_t size, bitset a, bitset b);
582 *
583 * Add all elements of bitset `b' to bitset `a'.
584 */
585 void
bitset_union(bit_t size,bitset a,bitset b)586 bitset_union (bit_t size, bitset a, bitset b)
587 {
588 bit_t x;
589 bit_t bits_in_last_subset;
590 bitset_subset last_bitset_subset_mask;
591
592 if (!size)
593 return;
594
595 x = bitset_numb_subsets(size) - 1;
596 bits_in_last_subset = (size - bits_per_subset * x);
597 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
598 a[x] |= (b[x] & last_bitset_subset_mask);
599
600 while (x--)
601 a[x] |= b[x];
602 }
603
604
605 /*(c bitset_intersection)
606 * void bitset_intersection (bit_t size, bitset a, bitset b);
607 *
608 * Remove from bitset `a' all alements that are not also in bitset
609 * `b'.
610 */
611 void
bitset_intersection(bit_t size,bitset a,bitset b)612 bitset_intersection (bit_t size, bitset a, bitset b)
613 {
614 bit_t x;
615 bit_t bits_in_last_subset;
616 bitset_subset last_bitset_subset_mask;
617
618 if (!size)
619 return;
620
621 x = bitset_numb_subsets(size) - 1;
622 bits_in_last_subset = (size - bits_per_subset * x);
623 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
624 a[x] = (a[x] & ~last_bitset_subset_mask) | ((a[x] & b[x]) & last_bitset_subset_mask);
625
626 while (x--)
627 a[x] &= b[x];
628 }
629
630
631 /*(c bitset_difference)
632 * void bitset_difference (bit_t size, bitset a, bitset b);
633 *
634 * Remove from bitset `a' all alements that are in bitset `b'.
635 */
636 void
bitset_difference(bit_t size,bitset a,bitset b)637 bitset_difference (bit_t size, bitset a, bitset b)
638 {
639 bit_t x;
640 bit_t bits_in_last_subset;
641 bitset_subset last_bitset_subset_mask;
642
643 if (!size)
644 return;
645
646 x = bitset_numb_subsets(size) - 1;
647 bits_in_last_subset = (size - bits_per_subset * x);
648 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
649 a[x] = (a[x] & ~last_bitset_subset_mask) | ((a[x] & ~b[x]) & last_bitset_subset_mask);
650
651 while (x--)
652 a[x] &= ~ b[x];
653 }
654
655
656 /*(c bitset_revdifference)
657 * void bitset_revdifference (bit_t size, bitset a, bitset b);
658 *
659 * Set all bits in `a' that are set in bitset `b' but not in `a';
660 * clear all other bits of bitset `a'.
661 *
662 * This is similar to `bitset_difference (size, b, a)' except that
663 * the result is assigned to bitset `a' instead of bitset `b'.
664 */
665 void
bitset_revdifference(bit_t size,bitset a,bitset b)666 bitset_revdifference (bit_t size, bitset a, bitset b)
667 {
668 bit_t x;
669 bit_t bits_in_last_subset;
670 bitset_subset last_bitset_subset_mask;
671
672 if (!size)
673 return;
674
675 x = bitset_numb_subsets(size) - 1;
676 bits_in_last_subset = (size - bits_per_subset * x);
677 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
678 a[x] = (a[x] & ~last_bitset_subset_mask) | ((~a[x] & b[x]) & last_bitset_subset_mask);
679
680 while (x--)
681 a[x] = ~a[x] & b[x];
682 }
683
684
685 /*(c bitset_xor)
686 * void bitset_xor (bit_t size, bitset a, bitset b);
687 *
688 * Toggle all bits in bitset `a' that are set in bitset `b'.
689 */
690 void
bitset_xor(bit_t size,bitset a,bitset b)691 bitset_xor (bit_t size, bitset a, bitset b)
692 {
693 bit_t x;
694 bit_t bits_in_last_subset;
695 bitset_subset last_bitset_subset_mask;
696
697 if (!size)
698 return;
699
700 x = bitset_numb_subsets(size) - 1;
701 bits_in_last_subset = (size - bits_per_subset * x);
702 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
703 a[x] ^= (b[x] & last_bitset_subset_mask);
704
705 while (x--)
706 a[x] ^= b[x];
707 }
708
709
710 /************************************************************************
711 *(h2 "Population Size")
712 *
713 *
714 *
715 */
716
717
718 /*
719 * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
720 * (define lb (map (lambda (n) (number->string n 2)) l))
721 * (define lc (map string->list lb))
722 * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
723 * (define lt (map (lambda (l) (apply + l)) ln))
724 */
725 static int bitset_byte_populations[256] =
726 {
727 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
728 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
729 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
730 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
731 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
732 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
733 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
734 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
735 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
736 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
737 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
738 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
739 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
740 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
741 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
742 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
743 };
744
745
746 /*(c bitset_population)
747 * bit_t bitset_population (bit_t size, bitset a);
748 *
749 * Return the number of bits set in bitset `a'.
750 */
751 bit_t
bitset_population(bit_t size,bitset a)752 bitset_population (bit_t size, bitset a)
753 {
754 bit_t x;
755 bit_t bits_in_last_subset;
756 bitset_subset last_bitset_subset_mask;
757 bitset_subset a_subset;
758 bit_t total;
759
760 if (!size)
761 return 0;
762
763 x = bitset_numb_subsets(size) - 1;
764 bits_in_last_subset = (size - bits_per_subset * x);
765 last_bitset_subset_mask = ~(bitset_subset)0 >> (bits_per_subset - bits_in_last_subset);
766 total = 0;
767 a_subset = a[x] & last_bitset_subset_mask;
768 while (a_subset)
769 {
770 total += bitset_byte_populations[a_subset & 0xff];
771 a_subset >>= 8;
772 }
773 while (x--)
774 {
775 a_subset = a[x];
776 while (a_subset)
777 {
778 total += bitset_byte_populations[a_subset & 0xff];
779 a_subset >>= 8;
780 }
781 }
782 return total;
783 }
784
785
786
787 /*(c bitset_population_range)
788 * bit_t bitset_population (bitset a, bit_t from, bit_t to);
789 *
790 * Return the number of bits set in bitset `a' couning only
791 * members in the closed interval `[from .. to-1]'.
792 */
793 bit_t
bitset_population_range(bitset a,bit_t from,bit_t to)794 bitset_population_range (bitset a, bit_t from, bit_t to)
795 {
796 bit_t first_subset;
797 bit_t first_subset_offset;
798 bit_t overcount;
799 bit_t count_error;
800
801
802 if (to <= from)
803 return 0;
804
805 first_subset = bitset_which_subset (from);
806 first_subset_offset = first_subset * bits_per_subset;
807 overcount = bitset_population (to - first_subset_offset, a + first_subset);
808 count_error = bitset_population (from - first_subset_offset, a + first_subset);
809 return overcount - count_error;
810 }
811
812
813 /************************************************************************
814 *(h2 "First Bit Set -- First Bit Clear")
815 *
816 *
817 *
818 */
819
820 static int bitset_byte_ffs[256] =
821 {
822 -1, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
823 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
824 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
825 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
826 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
827 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
828 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
829 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
830 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
831 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
832 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
833 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
834 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
835 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
836 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
837 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
838 };
839
840
841 /* static bit_t subset_ffs (bitset_subset a);
842 *
843 * Return the address of the first bit set in a bitset_subset.
844 * For bitset_subset 0, return -1.
845 */
846 static bit_t
subset_ffs(bitset_subset a)847 subset_ffs (bitset_subset a)
848 {
849 bit_t offset;
850 bit_t x;
851
852 if (!a)
853 return -1;
854
855 offset = 0;
856 x = sizeof (a);
857 while (x--)
858 {
859 bit_t q;
860 q = bitset_byte_ffs [a & 0xff];
861 if (q >= 0)
862 return q + offset;
863 offset += 8;
864 a >>= 8;
865 }
866
867 while (1)
868 panic ("not reached");
869 }
870
871
872 /*(c bitset_ffs)
873 * bit_t bitset_ffs (bit_t size, bitset b);
874 *
875 * Return the (bit) address of the first bit set in bitset `b'.
876 * Return -1 if no bit is set.
877 */
878 bit_t
bitset_ffs(bit_t size,bitset b)879 bitset_ffs (bit_t size, bitset b)
880 {
881 bit_t offset;
882 bit_t x;
883 bit_t bound;
884
885 offset = 0;
886 x = 0;
887 bound = bitset_numb_subsets(size);
888
889 while (x < bound)
890 {
891 bit_t fs;
892
893 fs = subset_ffs (b[x]);
894
895 if (fs >= 0)
896 {
897 bit_t answer;
898 answer = offset + fs;
899 return (answer < size) ? answer : -1;
900 }
901
902 offset += bits_per_subset;
903 ++x;
904 }
905 return -1;
906 }
907
908
909 /*(c bitset_ffs_range)
910 * bit_t bitset_ffs_range (bitset b, bit_t from, bit_t to);
911 *
912 * Return the (bit) address of the first bit set in bitset `b'
913 * in the range `from .. to-1'. Return -1 if no bit is set.
914 */
915 bit_t
bitset_ffs_range(bitset b,bit_t from,bit_t to)916 bitset_ffs_range (bitset b, bit_t from, bit_t to)
917 {
918 bit_t n_bits;
919 bit_t first_subset_skip;
920 bit_t f;
921 bit_t answer;
922
923 n_bits = to - from;
924 first_subset_skip = (from % bits_per_subset);
925 if (first_subset_skip)
926 {
927 bitset_subset s;
928 bit_t first_in_s;
929
930 s = b[bitset_which_subset (from)];
931 s &= ~(((bitset_subset)1 << first_subset_skip) - 1);
932 first_in_s = subset_ffs (s);
933 if (first_in_s != -1)
934 {
935 answer = first_in_s + from - first_subset_skip;
936 return (answer < (from + n_bits)) ? answer : -1;
937 }
938 from += bits_per_subset - first_subset_skip;
939 n_bits -= bits_per_subset - first_subset_skip;
940 }
941 f = bitset_ffs (n_bits, b + bitset_which_subset (from));
942 if (f < 0)
943 return f;
944 answer = from + f;
945 return (answer < (from + n_bits)) ? answer : -1;
946 }
947
948
949
950
951 static int bitset_byte_ffc[256] =
952 {
953 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
954 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
955 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
956 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
957 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
958 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
959 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
960 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7,
961 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
962 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
963 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
964 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
965 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
966 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
967 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
968 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, -1
969 };
970
971
972 /* static bit_t subset_ffc (bitset_subset a);
973 *
974 * Return the address of the first bit set in a subset.
975 * For bitset_subset 0, return -1.
976 */
977 static bit_t
subset_ffc(bitset_subset a)978 subset_ffc (bitset_subset a)
979 {
980 bit_t offset;
981 bit_t x;
982
983 if (a == (bitset_subset)-1L)
984 return -1;
985
986 offset = 0;
987 x = sizeof (a);
988 while (x--)
989 {
990 bit_t q;
991 q = bitset_byte_ffc [a & 0xff];
992 if (q >= 0)
993 return q + offset;
994 offset += 8;
995 a >>= 8;
996 }
997
998 while (1)
999 panic ("not reached");
1000 }
1001
1002 /*(c bitset_ffc)
1003 * bit_t bitset_ffc (bit_t size, bitset b);
1004 *
1005 * Return the (bit) address of the first bit clear in bitset `b'.
1006 * Return -1 if no bit is clear.
1007 */
1008 bit_t
bitset_ffc(bit_t size,bitset b)1009 bitset_ffc (bit_t size, bitset b)
1010 {
1011 bit_t offset;
1012 bit_t x;
1013 bit_t bound;
1014
1015 offset = 0;
1016 x = 0;
1017 bound = bitset_numb_subsets(size);
1018
1019 while (x < bound)
1020 {
1021 bit_t fs;
1022
1023 fs = subset_ffc (b[x]);
1024
1025 if (fs >= 0)
1026 {
1027 bit_t answer;
1028 answer = offset + fs;
1029 return (answer < size) ? answer : -1;
1030 }
1031
1032 offset += bits_per_subset;
1033 ++x;
1034 }
1035 return -1;
1036 }
1037
1038
1039 /*(c bitset_ffc_range)
1040 * bit_t bitset_ffc_range (bitset b, bit_t from, bit_t to);
1041 *
1042 * Return the (bit) address of the first bit clear in bitset `b'
1043 * in the range `from .. to-1'. Return -1 if no bit is set.
1044 */
1045 bit_t
bitset_ffc_range(bitset b,bit_t from,bit_t to)1046 bitset_ffc_range (bitset b, bit_t from, bit_t to)
1047 {
1048 bit_t n_bits;
1049 bit_t first_subset_skip;
1050 bit_t f;
1051 bit_t answer;
1052
1053 n_bits = to - from;
1054 first_subset_skip = (from % bits_per_subset);
1055 if (first_subset_skip)
1056 {
1057 bitset_subset s;
1058 bit_t first_in_s;
1059
1060 s = b[bitset_which_subset (from)];
1061 s |= (((bitset_subset)1 << first_subset_skip) - 1);
1062 first_in_s = subset_ffc (s);
1063 if (first_in_s != -1)
1064 {
1065 answer = first_in_s + from - first_subset_skip;
1066 return (answer < (from + n_bits)) ? answer : -1;
1067 }
1068 from += bits_per_subset - first_subset_skip;
1069 n_bits -= bits_per_subset - first_subset_skip;
1070 }
1071 f = bitset_ffc (n_bits, b + bitset_which_subset (from));
1072 if (f < 0)
1073 return f;
1074 answer = from + f;
1075 return (answer < (from + n_bits)) ? answer : -1;
1076 }
1077
1078