diff options
Diffstat (limited to 'rx/rxbitset.c')
-rw-r--r-- | rx/rxbitset.c | 364 |
1 files changed, 364 insertions, 0 deletions
diff --git a/rx/rxbitset.c b/rx/rxbitset.c new file mode 100644 index 00000000..a34b8b33 --- /dev/null +++ b/rx/rxbitset.c @@ -0,0 +1,364 @@ +/* Copyright (C) 1995, 1996 Tom Lord + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public License + * along with this software; see the file COPYING. If not, write to + * the Free Software Foundation, 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + + +/* + * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu) + */ + + +#include "rxall.h" +#include "rxbitset.h" + + +#ifdef __STDC__ +int +rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b) +#else +int +rx_bitset_is_equal (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + RX_subset s; + + if (size == 0) + return 1; + + s = b[0]; + b[0] = ~a[0]; + + for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x) + ; + + b[0] = s; + return !x && (s == a[0]); +} + + +#ifdef __STDC__ +int +rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b) +#else +int +rx_bitset_is_subset (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + x = rx_bitset_numb_subsets(size) - 1; + while (x-- && ((a[x] & b[x]) == a[x])); + return x == -1; +} + + +#ifdef __STDC__ +int +rx_bitset_empty (int size, rx_Bitset set) +#else +int +rx_bitset_empty (size, set) + int size; + rx_Bitset set; +#endif +{ + int x; + RX_subset s; + s = set[0]; + set[0] = 1; + for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x) + ; + set[0] = s; + return !s; +} + +#ifdef __STDC__ +void +rx_bitset_null (int size, rx_Bitset b) +#else +void +rx_bitset_null (size, b) + int size; + rx_Bitset b; +#endif +{ + rx_bzero ((char *)b, rx_sizeof_bitset(size)); +} + + +#ifdef __STDC__ +void +rx_bitset_universe (int size, rx_Bitset b) +#else +void +rx_bitset_universe (size, b) + int size; + rx_Bitset b; +#endif +{ + int x = rx_bitset_numb_subsets (size); + while (x--) + *b++ = ~(RX_subset)0; +} + + +#ifdef __STDC__ +void +rx_bitset_complement (int size, rx_Bitset b) +#else +void +rx_bitset_complement (size, b) + int size; + rx_Bitset b; +#endif +{ + int x = rx_bitset_numb_subsets (size); + while (x--) + { + *b = ~*b; + ++b; + } +} + + +#ifdef __STDC__ +void +rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b) +#else +void +rx_bitset_assign (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] = b[x]; +} + + +#ifdef __STDC__ +void +rx_bitset_union (int size, rx_Bitset a, rx_Bitset b) +#else +void +rx_bitset_union (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] |= b[x]; +} + + +#ifdef __STDC__ +void +rx_bitset_intersection (int size, + rx_Bitset a, rx_Bitset b) +#else +void +rx_bitset_intersection (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] &= b[x]; +} + + +#ifdef __STDC__ +void +rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b) +#else +void +rx_bitset_difference (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] &= ~ b[x]; +} + + +#ifdef __STDC__ +void +rx_bitset_revdifference (int size, + rx_Bitset a, rx_Bitset b) +#else +void +rx_bitset_revdifference (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] = ~a[x] & b[x]; +} + +#ifdef __STDC__ +void +rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b) +#else +void +rx_bitset_xor (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] ^= b[x]; +} + + +#ifdef __STDC__ +unsigned long +rx_bitset_hash (int size, rx_Bitset b) +#else +unsigned long +rx_bitset_hash (size, b) + int size; + rx_Bitset b; +#endif +{ + int x; + unsigned long answer; + + answer = 0; + + for (x = 0; x < size; ++x) + { + if (RX_bitset_member (b, x)) + answer += (answer << 3) + x; + } + return answer; +} + + +RX_subset rx_subset_singletons [RX_subset_bits] = +{ + 0x1, + 0x2, + 0x4, + 0x8, + 0x10, + 0x20, + 0x40, + 0x80, + 0x100, + 0x200, + 0x400, + 0x800, + 0x1000, + 0x2000, + 0x4000, + 0x8000, + 0x10000, + 0x20000, + 0x40000, + 0x80000, + 0x100000, + 0x200000, + 0x400000, + 0x800000, + 0x1000000, + 0x2000000, + 0x4000000, + 0x8000000, + 0x10000000, + 0x20000000, + 0x40000000, + 0x80000000 +}; + + +/* + * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l))))) + * (define lb (map (lambda (n) (number->string n 2)) l)) + * (define lc (map string->list lb)) + * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc)) + * (define lt (map (lambda (l) (apply + l)) ln)) + */ + +static int char_pops[256] = +{ + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 +}; + +#define RX_char_population(C) (char_pops[C]) + +#ifdef __STDC__ +int +rx_bitset_population (int size, rx_Bitset a) +#else +int +rx_bitset_population (size, a) + int size; + rx_Bitset a; +#endif +{ + int x; + int total; + unsigned char s; + + if (size == 0) + return 0; + + total = 0; + x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1; + while (x >= 0) + { + s = ((unsigned char *)a)[x]; + --x; + total = total + RX_char_population (s); + } + return total; +} |