This is rxbitset.c in view mode; [Download] [Up]
/* 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;
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.