summaryrefslogtreecommitdiffstats
path: root/rx/rxbitset.c
diff options
context:
space:
mode:
Diffstat (limited to 'rx/rxbitset.c')
-rw-r--r--rx/rxbitset.c364
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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-06 07:06:21 +0000