1 /* Copyright (C) 1995, 1996 Tom Lord
3 * This program is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU Library General Public License as published by
5 * the Free Software Foundation; either version 2, or (at your option)
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU Library General Public License for more details.
13 * You should have received a copy of the GNU Library General Public License
14 * along with this software; see the file COPYING. If not, write to
15 * the Free Software Foundation, 59 Temple Place - Suite 330,
16 * Boston, MA 02111-1307, USA.
21 * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
31 rx_bitset_is_equal (int size
, rx_Bitset a
, rx_Bitset b
)
34 rx_bitset_is_equal (size
, a
, b
)
49 for (x
= rx_bitset_numb_subsets(size
) - 1; a
[x
] == b
[x
]; --x
)
53 return !x
&& (s
== a
[0]);
59 rx_bitset_is_subset (int size
, rx_Bitset a
, rx_Bitset b
)
62 rx_bitset_is_subset (size
, a
, b
)
69 x
= rx_bitset_numb_subsets(size
) - 1;
70 while (x
-- && ((a
[x
] & b
[x
]) == a
[x
]));
77 rx_bitset_empty (int size
, rx_Bitset set
)
80 rx_bitset_empty (size
, set
)
89 for (x
= rx_bitset_numb_subsets(size
) - 1; !set
[x
]; --x
)
97 rx_bitset_null (int size
, rx_Bitset b
)
100 rx_bitset_null (size
, b
)
105 rx_bzero ((char *)b
, rx_sizeof_bitset(size
));
111 rx_bitset_universe (int size
, rx_Bitset b
)
114 rx_bitset_universe (size
, b
)
119 int x
= rx_bitset_numb_subsets (size
);
121 *b
++ = ~(RX_subset
)0;
127 rx_bitset_complement (int size
, rx_Bitset b
)
130 rx_bitset_complement (size
, b
)
135 int x
= rx_bitset_numb_subsets (size
);
146 rx_bitset_assign (int size
, rx_Bitset a
, rx_Bitset b
)
149 rx_bitset_assign (size
, a
, b
)
156 for (x
= rx_bitset_numb_subsets(size
) - 1; x
>=0; --x
)
163 rx_bitset_union (int size
, rx_Bitset a
, rx_Bitset b
)
166 rx_bitset_union (size
, a
, b
)
173 for (x
= rx_bitset_numb_subsets(size
) - 1; x
>=0; --x
)
180 rx_bitset_intersection (int size
,
181 rx_Bitset a
, rx_Bitset b
)
184 rx_bitset_intersection (size
, a
, b
)
191 for (x
= rx_bitset_numb_subsets(size
) - 1; x
>=0; --x
)
198 rx_bitset_difference (int size
, rx_Bitset a
, rx_Bitset b
)
201 rx_bitset_difference (size
, a
, b
)
208 for (x
= rx_bitset_numb_subsets(size
) - 1; x
>=0; --x
)
215 rx_bitset_revdifference (int size
,
216 rx_Bitset a
, rx_Bitset b
)
219 rx_bitset_revdifference (size
, a
, b
)
226 for (x
= rx_bitset_numb_subsets(size
) - 1; x
>=0; --x
)
232 rx_bitset_xor (int size
, rx_Bitset a
, rx_Bitset b
)
235 rx_bitset_xor (size
, a
, b
)
242 for (x
= rx_bitset_numb_subsets(size
) - 1; x
>=0; --x
)
249 rx_bitset_hash (int size
, rx_Bitset b
)
252 rx_bitset_hash (size
, b
)
258 unsigned long answer
;
262 for (x
= 0; x
< size
; ++x
)
264 if (RX_bitset_member (b
, x
))
265 answer
+= (answer
<< 3) + x
;
271 RX_subset rx_subset_singletons
[RX_subset_bits
] =
309 * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
310 * (define lb (map (lambda (n) (number->string n 2)) l))
311 * (define lc (map string->list lb))
312 * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
313 * (define lt (map (lambda (l) (apply + l)) ln))
316 static int char_pops
[256] =
318 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
319 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
320 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
321 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
322 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
323 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
324 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
325 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
326 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
327 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
328 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
329 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
330 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
331 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
332 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
333 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
336 #define RX_char_population(C) (char_pops[C])
340 rx_bitset_population (int size
, rx_Bitset a
)
343 rx_bitset_population (size
, a
)
356 x
= sizeof (RX_subset
) * rx_bitset_numb_subsets(size
) - 1;
359 s
= ((unsigned char *)a
)[x
];
361 total
= total
+ RX_char_population (s
);